1 //===- TargetSchedule.td - Target Independent Scheduling ---*- tablegen -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the target-independent scheduling interfaces which should
11 // be implemented by each target which is using TableGen based scheduling.
13 // The SchedMachineModel is defined by subtargets for three categories of data:
14 // 1. Basic properties for coarse grained instruction cost model.
15 // 2. Scheduler Read/Write resources for simple per-opcode cost model.
16 // 3. Instruction itineraries for detailed reservation tables.
18 // (1) Basic properties are defined by the SchedMachineModel
19 // class. Target hooks allow subtargets to associate opcodes with
22 // (2) A per-operand machine model can be implemented in any
23 // combination of the following ways:
25 // A. Associate per-operand SchedReadWrite types with Instructions by
26 // modifying the Instruction definition to inherit from Sched. For
27 // each subtarget, define WriteRes and ReadAdvance to associate
28 // processor resources and latency with each SchedReadWrite type.
30 // B. In each instruction definition, name an ItineraryClass. For each
31 // subtarget, define ItinRW entries to map ItineraryClass to
32 // per-operand SchedReadWrite types. Unlike method A, these types may
33 // be subtarget specific and can be directly associated with resources
34 // by defining SchedWriteRes and SchedReadAdvance.
36 // C. In the subtarget, map SchedReadWrite types to specific
37 // opcodes. This overrides any SchedReadWrite types or
38 // ItineraryClasses defined by the Instruction. As in method B, the
39 // subtarget can directly associate resources with SchedReadWrite
40 // types by defining SchedWriteRes and SchedReadAdvance.
42 // D. In either the target or subtarget, define SchedWriteVariant or
43 // SchedReadVariant to map one SchedReadWrite type onto another
44 // sequence of SchedReadWrite types. This allows dynamic selection of
45 // an instruction's machine model via custom C++ code. It also allows
46 // a machine-independent SchedReadWrite type to map to a sequence of
47 // machine-dependent types.
49 // (3) A per-pipeline-stage machine model can be implemented by providing
50 // Itineraries in addition to mapping instructions to ItineraryClasses.
51 //===----------------------------------------------------------------------===//
53 // Include legacy support for instruction itineraries.
54 include "llvm/Target/TargetItinerary.td"
56 class Instruction; // Forward def
58 class Predicate; // Forward def
60 // DAG operator that interprets the DAG args as Instruction defs.
63 // DAG operator that interprets each DAG arg as a regex pattern for
64 // matching Instruction opcode names.
65 // The regex must match the beginning of the opcode (as in Python re.match).
66 // To avoid matching prefixes, append '$' to the pattern.
69 // Define the SchedMachineModel and provide basic properties for
70 // coarse grained instruction cost model. Default values for the
71 // properties are defined in MCSchedModel. A value of "-1" in the
72 // target description's SchedMachineModel indicates that the property
73 // is not overriden by the target.
75 // Target hooks allow subtargets to associate LoadLatency and
76 // HighLatency with groups of opcodes.
78 // See MCSchedule.h for detailed comments.
79 class SchedMachineModel {
80 int IssueWidth = -1; // Max micro-ops that may be scheduled per cycle.
81 int MicroOpBufferSize = -1; // Max micro-ops that can be buffered.
82 int LoopMicroOpBufferSize = -1; // Max micro-ops that can be buffered for
83 // optimized loop dispatch/execution.
84 int LoadLatency = -1; // Cycles for loads to access the cache.
85 int HighLatency = -1; // Approximation of cycles for "high latency" ops.
86 int MispredictPenalty = -1; // Extra cycles for a mispredicted branch.
88 // Per-cycle resources tables.
89 ProcessorItineraries Itineraries = NoItineraries;
91 bit PostRAScheduler = 0; // Enable Post RegAlloc Scheduler pass.
93 // Subtargets that define a model for only a subset of instructions
94 // that have a scheduling class (itinerary class or SchedRW list)
95 // and may actually be generated for that subtarget must clear this
96 // bit. Otherwise, the scheduler considers an unmodelled opcode to
97 // be an error. This should only be set during initial bringup,
98 // or there will be no way to catch simple errors in the model
99 // resulting from changes to the instruction definitions.
100 bit CompleteModel = 1;
102 // Indicates that we should do full overlap checking for multiple InstrRWs
103 // definining the same instructions within the same SchedMachineModel.
104 // FIXME: Remove when all in tree targets are clean with the full check
106 bit FullInstRWOverlapCheck = 1;
108 // A processor may only implement part of published ISA, due to either new ISA
109 // extensions, (e.g. Pentium 4 doesn't have AVX) or implementation
110 // (ARM/MIPS/PowerPC/SPARC soft float cores).
112 // For a processor which doesn't support some feature(s), the schedule model
115 // let<Predicate> UnsupportedFeatures = [HaveA,..,HaveY];
117 // to skip the checks for scheduling information when building LLVM for
118 // instructions which have any of the listed predicates in their Predicates
120 list<Predicate> UnsupportedFeatures = [];
122 bit NoModel = 0; // Special tag to indicate missing machine model.
125 def NoSchedModel : SchedMachineModel {
127 let CompleteModel = 0;
130 // Define a kind of processor resource that may be common across
131 // similar subtargets.
132 class ProcResourceKind;
134 // Define a number of interchangeable processor resources. NumUnits
135 // determines the throughput of instructions that require the resource.
137 // An optional Super resource may be given to model these resources as
138 // a subset of the more general super resources. Using one of these
139 // resources implies using one of the super resoruces.
141 // ProcResourceUnits normally model a few buffered resources within an
142 // out-of-order engine. Buffered resources may be held for multiple
143 // clock cycles, but the scheduler does not pin them to a particular
144 // clock cycle relative to instruction dispatch. Setting BufferSize=0
145 // changes this to an in-order issue/dispatch resource. In this case,
146 // the scheduler counts down from the cycle that the instruction
147 // issues in-order, forcing a stall whenever a subsequent instruction
148 // requires the same resource until the number of ResourceCycles
149 // specified in WriteRes expire. Setting BufferSize=1 changes this to
150 // an in-order latency resource. In this case, the scheduler models
151 // producer/consumer stalls between instructions that use the
154 // Examples (all assume an out-of-order engine):
156 // Use BufferSize = -1 for "issue ports" fed by a unified reservation
157 // station. Here the size of the reservation station is modeled by
158 // MicroOpBufferSize, which should be the minimum size of either the
159 // register rename pool, unified reservation station, or reorder
162 // Use BufferSize = 0 for resources that force "dispatch/issue
163 // groups". (Different processors define dispath/issue
164 // differently. Here we refer to stage between decoding into micro-ops
165 // and moving them into a reservation station.) Normally NumMicroOps
166 // is sufficient to limit dispatch/issue groups. However, some
167 // processors can form groups of with only certain combinitions of
168 // instruction types. e.g. POWER7.
170 // Use BufferSize = 1 for in-order execution units. This is used for
171 // an in-order pipeline within an out-of-order core where scheduling
172 // dependent operations back-to-back is guaranteed to cause a
173 // bubble. e.g. Cortex-a9 floating-point.
175 // Use BufferSize > 1 for out-of-order executions units with a
176 // separate reservation station. This simply models the size of the
177 // reservation station.
179 // To model both dispatch/issue groups and in-order execution units,
180 // create two types of units, one with BufferSize=0 and one with
183 // SchedModel ties these units to a processor for any stand-alone defs
185 class ProcResourceUnits<ProcResourceKind kind, int num> {
186 ProcResourceKind Kind = kind;
188 ProcResourceKind Super = ?;
190 SchedMachineModel SchedModel = ?;
193 // EponymousProcResourceKind helps implement ProcResourceUnits by
194 // allowing a ProcResourceUnits definition to reference itself. It
195 // should not be referenced anywhere else.
196 def EponymousProcResourceKind : ProcResourceKind;
198 // Subtargets typically define processor resource kind and number of
199 // units in one place.
200 class ProcResource<int num> : ProcResourceKind,
201 ProcResourceUnits<EponymousProcResourceKind, num>;
203 class ProcResGroup<list<ProcResource> resources> : ProcResourceKind {
204 list<ProcResource> Resources = resources;
205 SchedMachineModel SchedModel = ?;
209 // A target architecture may define SchedReadWrite types and associate
210 // them with instruction operands.
211 class SchedReadWrite;
213 // List the per-operand types that map to the machine model of an
214 // instruction. One SchedWrite type must be listed for each explicit
215 // def operand in order. Additional SchedWrite types may optionally be
216 // listed for implicit def operands. SchedRead types may optionally
217 // be listed for use operands in order. The order of defs relative to
218 // uses is insignificant. This way, the same SchedReadWrite list may
219 // be used for multiple forms of an operation. For example, a
220 // two-address instruction could have two tied operands or single
221 // operand that both reads and writes a reg. In both cases we have a
222 // single SchedWrite and single SchedRead in any order.
223 class Sched<list<SchedReadWrite> schedrw> {
224 list<SchedReadWrite> SchedRW = schedrw;
227 // Define a scheduler resource associated with a def operand.
228 class SchedWrite : SchedReadWrite;
229 def NoWrite : SchedWrite;
231 // Define a scheduler resource associated with a use operand.
232 class SchedRead : SchedReadWrite;
234 // Define a SchedWrite that is modeled as a sequence of other
235 // SchedWrites with additive latency. This allows a single operand to
236 // be mapped the resources composed from a set of previously defined
239 // If the final write in this sequence is a SchedWriteVariant marked
240 // Variadic, then the list of prior writes are distributed across all
241 // operands after resolving the predicate for the final write.
243 // SchedModel silences warnings but is ignored.
244 class WriteSequence<list<SchedWrite> writes, int rep = 1> : SchedWrite {
245 list<SchedWrite> Writes = writes;
247 SchedMachineModel SchedModel = ?;
250 // Define values common to WriteRes and SchedWriteRes.
252 // SchedModel ties these resources to a processor.
253 class ProcWriteResources<list<ProcResourceKind> resources> {
254 list<ProcResourceKind> ProcResources = resources;
255 list<int> ResourceCycles = [];
260 // Allow a processor to mark some scheduling classes as unsupported
261 // for stronger verification.
263 // Allow a processor to mark some scheduling classes as single-issue.
264 // SingleIssue is an alias for Begin/End Group.
266 SchedMachineModel SchedModel = ?;
269 // Define the resources and latency of a SchedWrite. This will be used
270 // directly by targets that have no itinerary classes. In this case,
271 // SchedWrite is defined by the target, while WriteResources is
272 // defined by the subtarget, and maps the SchedWrite to processor
275 // If a target already has itinerary classes, SchedWriteResources can
276 // be used instead to define subtarget specific SchedWrites and map
277 // them to processor resources in one place. Then ItinRW can map
278 // itinerary classes to the subtarget's SchedWrites.
280 // ProcResources indicates the set of resources consumed by the write.
281 // Optionally, ResourceCycles indicates the number of cycles the
282 // resource is consumed. Each ResourceCycles item is paired with the
283 // ProcResource item at the same position in its list. ResourceCycles
284 // can be `[]`: in that case, all resources are consumed for a single
285 // cycle, regardless of latency, which models a fully pipelined processing
286 // unit. A value of 0 for ResourceCycles means that the resource must
287 // be available but is not consumed, which is only relevant for
288 // unbuffered resources.
290 // By default, each SchedWrite takes one micro-op, which is counted
291 // against the processor's IssueWidth limit. If an instruction can
292 // write multiple registers with a single micro-op, the subtarget
293 // should define one of the writes to be zero micro-ops. If a
294 // subtarget requires multiple micro-ops to write a single result, it
295 // should either override the write's NumMicroOps to be greater than 1
296 // or require additional writes. Extra writes can be required either
297 // by defining a WriteSequence, or simply listing extra writes in the
298 // instruction's list of writers beyond the number of "def"
299 // operands. The scheduler assumes that all micro-ops must be
300 // dispatched in the same cycle. These micro-ops may be required to
301 // begin or end the current dispatch group.
302 class WriteRes<SchedWrite write, list<ProcResourceKind> resources>
303 : ProcWriteResources<resources> {
304 SchedWrite WriteType = write;
307 // Directly name a set of WriteResources defining a new SchedWrite
308 // type at the same time. This class is unaware of its SchedModel so
309 // must be referenced by InstRW or ItinRW.
310 class SchedWriteRes<list<ProcResourceKind> resources> : SchedWrite,
311 ProcWriteResources<resources>;
313 // Define values common to ReadAdvance and SchedReadAdvance.
315 // SchedModel ties these resources to a processor.
316 class ProcReadAdvance<int cycles, list<SchedWrite> writes = []> {
318 list<SchedWrite> ValidWrites = writes;
319 // Allow a processor to mark some scheduling classes as unsupported
320 // for stronger verification.
322 SchedMachineModel SchedModel = ?;
325 // A processor may define a ReadAdvance associated with a SchedRead
326 // to reduce latency of a prior write by N cycles. A negative advance
327 // effectively increases latency, which may be used for cross-domain
330 // A ReadAdvance may be associated with a list of SchedWrites
331 // to implement pipeline bypass. The Writes list may be empty to
332 // indicate operands that are always read this number of Cycles later
333 // than a normal register read, allowing the read's parent instruction
334 // to issue earlier relative to the writer.
335 class ReadAdvance<SchedRead read, int cycles, list<SchedWrite> writes = []>
336 : ProcReadAdvance<cycles, writes> {
337 SchedRead ReadType = read;
340 // Directly associate a new SchedRead type with a delay and optional
341 // pipeline bypass. For use with InstRW or ItinRW.
342 class SchedReadAdvance<int cycles, list<SchedWrite> writes = []> : SchedRead,
343 ProcReadAdvance<cycles, writes>;
345 // Define SchedRead defaults. Reads seldom need special treatment.
346 def ReadDefault : SchedRead;
347 def NoReadAdvance : SchedReadAdvance<0>;
349 // Define shared code that will be in the same scope as all
350 // SchedPredicates. Available variables are:
351 // (const MachineInstr *MI, const TargetSchedModel *SchedModel)
352 class PredicateProlog<code c> {
356 // Base class for scheduling predicates.
357 class SchedPredicateBase;
359 // A scheduling predicate whose logic is defined by a MCInstPredicate.
360 // This can directly be used by SchedWriteVariant definitions.
361 class MCSchedPredicate<MCInstPredicate P> : SchedPredicateBase {
362 MCInstPredicate Pred = P;
363 SchedMachineModel SchedModel = ?;
366 // Define a predicate to determine which SchedVariant applies to a
367 // particular MachineInstr. The code snippet is used as an
368 // if-statement's expression. Available variables are MI, SchedModel,
369 // and anything defined in a PredicateProlog.
371 // SchedModel silences warnings but is ignored.
372 class SchedPredicate<code pred> : SchedPredicateBase {
373 SchedMachineModel SchedModel = ?;
374 code Predicate = pred;
377 // Define a predicate to be typically used as the default case in a
378 // SchedVariant. It the SchedVariant does not use any other predicate based on
379 // MCSchedPredicate, this is the default scheduling case used by llvm-mca.
380 def NoSchedPred : MCSchedPredicate<TruePred>;
382 // Associate a predicate with a list of SchedReadWrites. By default,
383 // the selected SchedReadWrites are still associated with a single
384 // operand and assumed to execute sequentially with additive
385 // latency. However, if the parent SchedWriteVariant or
386 // SchedReadVariant is marked "Variadic", then each Selected
387 // SchedReadWrite is mapped in place to the instruction's variadic
388 // operands. In this case, latency is not additive. If the current Variant
389 // is already part of a Sequence, then that entire chain leading up to
390 // the Variant is distributed over the variadic operands.
391 class SchedVar<SchedPredicateBase pred, list<SchedReadWrite> selected> {
392 SchedPredicateBase Predicate = pred;
393 list<SchedReadWrite> Selected = selected;
396 // SchedModel silences warnings but is ignored.
397 class SchedVariant<list<SchedVar> variants> {
398 list<SchedVar> Variants = variants;
400 SchedMachineModel SchedModel = ?;
403 // A SchedWriteVariant is a single SchedWrite type that maps to a list
404 // of SchedWrite types under the conditions defined by its predicates.
406 // A Variadic write is expanded to cover multiple "def" operands. The
407 // SchedVariant's Expansion list is then interpreted as one write
408 // per-operand instead of the usual sequential writes feeding a single
410 class SchedWriteVariant<list<SchedVar> variants> : SchedWrite,
411 SchedVariant<variants> {
414 // A SchedReadVariant is a single SchedRead type that maps to a list
415 // of SchedRead types under the conditions defined by its predicates.
417 // A Variadic write is expanded to cover multiple "readsReg" operands as
419 class SchedReadVariant<list<SchedVar> variants> : SchedRead,
420 SchedVariant<variants> {
423 // Map a set of opcodes to a list of SchedReadWrite types. This allows
424 // the subtarget to easily override specific operations.
426 // SchedModel ties this opcode mapping to a processor.
427 class InstRW<list<SchedReadWrite> rw, dag instrlist> {
428 list<SchedReadWrite> OperandReadWrites = rw;
429 dag Instrs = instrlist;
430 SchedMachineModel SchedModel = ?;
431 // Allow a subtarget to mark some instructions as unsupported.
435 // Map a set of itinerary classes to SchedReadWrite resources. This is
436 // used to bootstrap a target (e.g. ARM) when itineraries already
437 // exist and changing InstrInfo is undesirable.
439 // SchedModel ties this ItineraryClass mapping to a processor.
440 class ItinRW<list<SchedReadWrite> rw, list<InstrItinClass> iic> {
441 list<InstrItinClass> MatchedItinClasses = iic;
442 list<SchedReadWrite> OperandReadWrites = rw;
443 SchedMachineModel SchedModel = ?;
446 // Alias a target-defined SchedReadWrite to a processor specific
447 // SchedReadWrite. This allows a subtarget to easily map a
448 // SchedReadWrite type onto a WriteSequence, SchedWriteVariant, or
451 // SchedModel will usually be provided by surrounding let statement
452 // and ties this SchedAlias mapping to a processor.
453 class SchedAlias<SchedReadWrite match, SchedReadWrite alias> {
454 SchedReadWrite MatchRW = match;
455 SchedReadWrite AliasRW = alias;
456 SchedMachineModel SchedModel = ?;
459 // Allow the definition of processor register files for register renaming
462 // Each processor register file declares:
463 // - The set of registers that can be renamed.
464 // - The number of physical registers which can be used for register renaming
466 // - The cost of a register rename.
467 // - The set of registers that allow move elimination.
468 // - The maximum number of moves that can be eliminated every cycle.
469 // - Whether move elimination is limited to register moves whose input
470 // is known to be zero.
472 // The cost of a rename is the number of physical registers allocated by the
473 // register alias table to map the new definition. By default, register can be
474 // renamed at the cost of a single physical register. Note that register costs
475 // are defined at register class granularity (see field `Costs`).
477 // The set of registers that are subject to register renaming is declared using
478 // a list of register classes (see field `RegClasses`). An empty list of
479 // register classes means: all the logical registers defined by the target can
482 // A register R can be renamed if its register class appears in the `RegClasses`
483 // set. When R is written, a new alias is allocated at the cost of one or more
484 // physical registers; as a result, false dependencies on R are removed.
486 // A sub-register V of register R is implicitly part of the same register file.
487 // However, V is only renamed if its register class is part of `RegClasses`.
488 // Otherwise, the processor keeps it (as well as any other different part
489 // of R) together with R, and a write of V always causes a compulsory read of R.
491 // This is what happens for example on AMD processors (at least from Bulldozer
492 // onwards), where AL and AH are not treated as independent from AX, and AX is
493 // not treated as independent from EAX. A write to AL has an implicity false
494 // dependency on the last write to EAX (or a portion of EAX). As a consequence,
495 // a write to AL cannot go in parallel with a write to AH.
497 // There is no false dependency if the partial register write belongs to a
498 // register class that is in `RegClasses`.
499 // There is also no penalty for writes that "clear the content a super-register"
500 // (see MC/MCInstrAnalysis.h - method MCInstrAnalysis::clearsSuperRegisters()).
501 // On x86-64, 32-bit GPR writes implicitly zero the upper half of the underlying
502 // physical register, effectively removing any false dependencies with the
503 // previous register definition.
505 // TODO: This implementation assumes that there is no limit in the number of
506 // renames per cycle, which might not be true for all hardware or register
507 // classes. Also, there is no limit to how many times the same logical register
508 // can be renamed during the same cycle.
510 // TODO: we don't currently model merge penalties for the case where a write to
511 // a part of a register is followed by a read from a larger part of the same
512 // register. On some Intel chips, different parts of a GPR can be stored in
513 // different physical registers. However, there is a cost to pay for when the
514 // partial write is combined with the previous super-register definition. We
515 // should add support for these cases, and correctly model merge problems with
516 // partial register accesses.
518 // Field MaxMovesEliminatedPerCycle specifies how many moves can be eliminated
519 // every cycle. A default value of zero for that field means: there is no limit
520 // to the number of moves that can be eliminated by this register file.
522 // An instruction MI is a candidate for move elimination if a call to
523 // method TargetSubtargetInfo::isOptimizableRegisterMove(MI) returns true (see
524 // llvm/CodeGen/TargetSubtargetInfo.h, and llvm/MC/MCInstrAnalysis.h).
526 // Subtargets can instantiate tablegen class IsOptimizableRegisterMove (see
527 // llvm/Target/TargetInstrPredicate.td) to customize the set of move elimination
528 // candidates. By default, no instruction is a valid move elimination candidate.
530 // A register move MI is eliminated only if:
531 // - MI is a move elimination candidate.
532 // - The destination register is from a register class that allows move
533 // elimination (see field `AllowMoveElimination` below).
534 // - Constraints on the move kind, and the maximum number of moves that can be
535 // eliminated per cycle are all met.
537 class RegisterFile<int numPhysRegs, list<RegisterClass> Classes = [],
538 list<int> Costs = [], list<bit> AllowMoveElim = [],
539 int MaxMoveElimPerCy = 0, bit AllowZeroMoveElimOnly = 0> {
540 list<RegisterClass> RegClasses = Classes;
541 list<int> RegCosts = Costs;
542 list<bit> AllowMoveElimination = AllowMoveElim;
543 int NumPhysRegs = numPhysRegs;
544 int MaxMovesEliminatedPerCycle = MaxMoveElimPerCy;
545 bit AllowZeroMoveEliminationOnly = AllowZeroMoveElimOnly;
546 SchedMachineModel SchedModel = ?;
549 // Describe the retire control unit.
550 // A retire control unit specifies the size of the reorder buffer, as well as
551 // the maximum number of opcodes that can be retired every cycle.
552 // A value less-than-or-equal-to zero for field 'ReorderBufferSize' means: "the
553 // size is unknown". The idea is that external tools can fall-back to using
554 // field MicroOpBufferSize in SchedModel if the reorder buffer size is unknown.
555 // A zero or negative value for field 'MaxRetirePerCycle' means "no
556 // restrictions on the number of instructions retired per cycle".
557 // Models can optionally specify up to one instance of RetireControlUnit per
559 class RetireControlUnit<int bufferSize, int retirePerCycle> {
560 int ReorderBufferSize = bufferSize;
561 int MaxRetirePerCycle = retirePerCycle;
562 SchedMachineModel SchedModel = ?;
565 // Base class for Load/StoreQueue. It is used to identify processor resources
566 // which describe load/store queues in the LS unit.
567 class MemoryQueue<ProcResource PR> {
568 ProcResource QueueDescriptor = PR;
569 SchedMachineModel SchedModel = ?;
572 class LoadQueue<ProcResource LDQueue> : MemoryQueue<LDQueue>;
573 class StoreQueue<ProcResource STQueue> : MemoryQueue<STQueue>;