1 //===-- llvm/MC/MCSchedule.h - Scheduling -----------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the classes used to describe a subtarget's machine model 10 // for scheduling and other instruction cost heuristics. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_MC_MCSCHEDULE_H 15 #define LLVM_MC_MCSCHEDULE_H 16 17 #include "llvm/ADT/Optional.h" 18 #include "llvm/Config/llvm-config.h" 19 #include "llvm/Support/DataTypes.h" 20 #include <cassert> 21 22 namespace llvm { 23 24 template <typename T> class ArrayRef; 25 struct InstrItinerary; 26 class MCSubtargetInfo; 27 class MCInstrInfo; 28 class MCInst; 29 class InstrItineraryData; 30 31 /// Define a kind of processor resource that will be modeled by the scheduler. 32 struct MCProcResourceDesc { 33 const char *Name; 34 unsigned NumUnits; // Number of resource of this kind 35 unsigned SuperIdx; // Index of the resources kind that contains this kind. 36 37 // Number of resources that may be buffered. 38 // 39 // Buffered resources (BufferSize != 0) may be consumed at some indeterminate 40 // cycle after dispatch. This should be used for out-of-order cpus when 41 // instructions that use this resource can be buffered in a reservaton 42 // station. 43 // 44 // Unbuffered resources (BufferSize == 0) always consume their resource some 45 // fixed number of cycles after dispatch. If a resource is unbuffered, then 46 // the scheduler will avoid scheduling instructions with conflicting resources 47 // in the same cycle. This is for in-order cpus, or the in-order portion of 48 // an out-of-order cpus. 49 int BufferSize; 50 51 // If the resource has sub-units, a pointer to the first element of an array 52 // of `NumUnits` elements containing the ProcResourceIdx of the sub units. 53 // nullptr if the resource does not have sub-units. 54 const unsigned *SubUnitsIdxBegin; 55 56 bool operator==(const MCProcResourceDesc &Other) const { 57 return NumUnits == Other.NumUnits && SuperIdx == Other.SuperIdx 58 && BufferSize == Other.BufferSize; 59 } 60 }; 61 62 /// Identify one of the processor resource kinds consumed by a particular 63 /// scheduling class for the specified number of cycles. 64 struct MCWriteProcResEntry { 65 uint16_t ProcResourceIdx; 66 uint16_t Cycles; 67 68 bool operator==(const MCWriteProcResEntry &Other) const { 69 return ProcResourceIdx == Other.ProcResourceIdx && Cycles == Other.Cycles; 70 } 71 }; 72 73 /// Specify the latency in cpu cycles for a particular scheduling class and def 74 /// index. -1 indicates an invalid latency. Heuristics would typically consider 75 /// an instruction with invalid latency to have infinite latency. Also identify 76 /// the WriteResources of this def. When the operand expands to a sequence of 77 /// writes, this ID is the last write in the sequence. 78 struct MCWriteLatencyEntry { 79 int16_t Cycles; 80 uint16_t WriteResourceID; 81 82 bool operator==(const MCWriteLatencyEntry &Other) const { 83 return Cycles == Other.Cycles && WriteResourceID == Other.WriteResourceID; 84 } 85 }; 86 87 /// Specify the number of cycles allowed after instruction issue before a 88 /// particular use operand reads its registers. This effectively reduces the 89 /// write's latency. Here we allow negative cycles for corner cases where 90 /// latency increases. This rule only applies when the entry's WriteResource 91 /// matches the write's WriteResource. 92 /// 93 /// MCReadAdvanceEntries are sorted first by operand index (UseIdx), then by 94 /// WriteResourceIdx. 95 struct MCReadAdvanceEntry { 96 unsigned UseIdx; 97 unsigned WriteResourceID; 98 int Cycles; 99 100 bool operator==(const MCReadAdvanceEntry &Other) const { 101 return UseIdx == Other.UseIdx && WriteResourceID == Other.WriteResourceID 102 && Cycles == Other.Cycles; 103 } 104 }; 105 106 /// Summarize the scheduling resources required for an instruction of a 107 /// particular scheduling class. 108 /// 109 /// Defined as an aggregate struct for creating tables with initializer lists. 110 struct MCSchedClassDesc { 111 static const unsigned short InvalidNumMicroOps = (1U << 13) - 1; 112 static const unsigned short VariantNumMicroOps = InvalidNumMicroOps - 1; 113 114 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 115 const char* Name; 116 #endif 117 uint16_t NumMicroOps : 13; 118 uint16_t BeginGroup : 1; 119 uint16_t EndGroup : 1; 120 uint16_t RetireOOO : 1; 121 uint16_t WriteProcResIdx; // First index into WriteProcResTable. 122 uint16_t NumWriteProcResEntries; 123 uint16_t WriteLatencyIdx; // First index into WriteLatencyTable. 124 uint16_t NumWriteLatencyEntries; 125 uint16_t ReadAdvanceIdx; // First index into ReadAdvanceTable. 126 uint16_t NumReadAdvanceEntries; 127 128 bool isValid() const { 129 return NumMicroOps != InvalidNumMicroOps; 130 } 131 bool isVariant() const { 132 return NumMicroOps == VariantNumMicroOps; 133 } 134 }; 135 136 /// Specify the cost of a register definition in terms of number of physical 137 /// register allocated at register renaming stage. For example, AMD Jaguar. 138 /// natively supports 128-bit data types, and operations on 256-bit registers 139 /// (i.e. YMM registers) are internally split into two COPs (complex operations) 140 /// and each COP updates a physical register. Basically, on Jaguar, a YMM 141 /// register write effectively consumes two physical registers. That means, 142 /// the cost of a YMM write in the BtVer2 model is 2. 143 struct MCRegisterCostEntry { 144 unsigned RegisterClassID; 145 unsigned Cost; 146 bool AllowMoveElimination; 147 }; 148 149 /// A register file descriptor. 150 /// 151 /// This struct allows to describe processor register files. In particular, it 152 /// helps describing the size of the register file, as well as the cost of 153 /// allocating a register file at register renaming stage. 154 /// FIXME: this struct can be extended to provide information about the number 155 /// of read/write ports to the register file. A value of zero for field 156 /// 'NumPhysRegs' means: this register file has an unbounded number of physical 157 /// registers. 158 struct MCRegisterFileDesc { 159 const char *Name; 160 uint16_t NumPhysRegs; 161 uint16_t NumRegisterCostEntries; 162 // Index of the first cost entry in MCExtraProcessorInfo::RegisterCostTable. 163 uint16_t RegisterCostEntryIdx; 164 // A value of zero means: there is no limit in the number of moves that can be 165 // eliminated every cycle. 166 uint16_t MaxMovesEliminatedPerCycle; 167 // Ture if this register file only knows how to optimize register moves from 168 // known zero registers. 169 bool AllowZeroMoveEliminationOnly; 170 }; 171 172 /// Provide extra details about the machine processor. 173 /// 174 /// This is a collection of "optional" processor information that is not 175 /// normally used by the LLVM machine schedulers, but that can be consumed by 176 /// external tools like llvm-mca to improve the quality of the peformance 177 /// analysis. 178 struct MCExtraProcessorInfo { 179 // Actual size of the reorder buffer in hardware. 180 unsigned ReorderBufferSize; 181 // Number of instructions retired per cycle. 182 unsigned MaxRetirePerCycle; 183 const MCRegisterFileDesc *RegisterFiles; 184 unsigned NumRegisterFiles; 185 const MCRegisterCostEntry *RegisterCostTable; 186 unsigned NumRegisterCostEntries; 187 unsigned LoadQueueID; 188 unsigned StoreQueueID; 189 }; 190 191 /// Machine model for scheduling, bundling, and heuristics. 192 /// 193 /// The machine model directly provides basic information about the 194 /// microarchitecture to the scheduler in the form of properties. It also 195 /// optionally refers to scheduler resource tables and itinerary 196 /// tables. Scheduler resource tables model the latency and cost for each 197 /// instruction type. Itinerary tables are an independent mechanism that 198 /// provides a detailed reservation table describing each cycle of instruction 199 /// execution. Subtargets may define any or all of the above categories of data 200 /// depending on the type of CPU and selected scheduler. 201 /// 202 /// The machine independent properties defined here are used by the scheduler as 203 /// an abstract machine model. A real micro-architecture has a number of 204 /// buffers, queues, and stages. Declaring that a given machine-independent 205 /// abstract property corresponds to a specific physical property across all 206 /// subtargets can't be done. Nonetheless, the abstract model is 207 /// useful. Futhermore, subtargets typically extend this model with processor 208 /// specific resources to model any hardware features that can be exploited by 209 /// scheduling heuristics and aren't sufficiently represented in the abstract. 210 /// 211 /// The abstract pipeline is built around the notion of an "issue point". This 212 /// is merely a reference point for counting machine cycles. The physical 213 /// machine will have pipeline stages that delay execution. The scheduler does 214 /// not model those delays because they are irrelevant as long as they are 215 /// consistent. Inaccuracies arise when instructions have different execution 216 /// delays relative to each other, in addition to their intrinsic latency. Those 217 /// special cases can be handled by TableGen constructs such as, ReadAdvance, 218 /// which reduces latency when reading data, and ResourceCycles, which consumes 219 /// a processor resource when writing data for a number of abstract 220 /// cycles. 221 /// 222 /// TODO: One tool currently missing is the ability to add a delay to 223 /// ResourceCycles. That would be easy to add and would likely cover all cases 224 /// currently handled by the legacy itinerary tables. 225 /// 226 /// A note on out-of-order execution and, more generally, instruction 227 /// buffers. Part of the CPU pipeline is always in-order. The issue point, which 228 /// is the point of reference for counting cycles, only makes sense as an 229 /// in-order part of the pipeline. Other parts of the pipeline are sometimes 230 /// falling behind and sometimes catching up. It's only interesting to model 231 /// those other, decoupled parts of the pipeline if they may be predictably 232 /// resource constrained in a way that the scheduler can exploit. 233 /// 234 /// The LLVM machine model distinguishes between in-order constraints and 235 /// out-of-order constraints so that the target's scheduling strategy can apply 236 /// appropriate heuristics. For a well-balanced CPU pipeline, out-of-order 237 /// resources would not typically be treated as a hard scheduling 238 /// constraint. For example, in the GenericScheduler, a delay caused by limited 239 /// out-of-order resources is not directly reflected in the number of cycles 240 /// that the scheduler sees between issuing an instruction and its dependent 241 /// instructions. In other words, out-of-order resources don't directly increase 242 /// the latency between pairs of instructions. However, they can still be used 243 /// to detect potential bottlenecks across a sequence of instructions and bias 244 /// the scheduling heuristics appropriately. 245 struct MCSchedModel { 246 // IssueWidth is the maximum number of instructions that may be scheduled in 247 // the same per-cycle group. This is meant to be a hard in-order constraint 248 // (a.k.a. "hazard"). In the GenericScheduler strategy, no more than 249 // IssueWidth micro-ops can ever be scheduled in a particular cycle. 250 // 251 // In practice, IssueWidth is useful to model any bottleneck between the 252 // decoder (after micro-op expansion) and the out-of-order reservation 253 // stations or the decoder bandwidth itself. If the total number of 254 // reservation stations is also a bottleneck, or if any other pipeline stage 255 // has a bandwidth limitation, then that can be naturally modeled by adding an 256 // out-of-order processor resource. 257 unsigned IssueWidth; 258 static const unsigned DefaultIssueWidth = 1; 259 260 // MicroOpBufferSize is the number of micro-ops that the processor may buffer 261 // for out-of-order execution. 262 // 263 // "0" means operations that are not ready in this cycle are not considered 264 // for scheduling (they go in the pending queue). Latency is paramount. This 265 // may be more efficient if many instructions are pending in a schedule. 266 // 267 // "1" means all instructions are considered for scheduling regardless of 268 // whether they are ready in this cycle. Latency still causes issue stalls, 269 // but we balance those stalls against other heuristics. 270 // 271 // "> 1" means the processor is out-of-order. This is a machine independent 272 // estimate of highly machine specific characteristics such as the register 273 // renaming pool and reorder buffer. 274 unsigned MicroOpBufferSize; 275 static const unsigned DefaultMicroOpBufferSize = 0; 276 277 // LoopMicroOpBufferSize is the number of micro-ops that the processor may 278 // buffer for optimized loop execution. More generally, this represents the 279 // optimal number of micro-ops in a loop body. A loop may be partially 280 // unrolled to bring the count of micro-ops in the loop body closer to this 281 // number. 282 unsigned LoopMicroOpBufferSize; 283 static const unsigned DefaultLoopMicroOpBufferSize = 0; 284 285 // LoadLatency is the expected latency of load instructions. 286 unsigned LoadLatency; 287 static const unsigned DefaultLoadLatency = 4; 288 289 // HighLatency is the expected latency of "very high latency" operations. 290 // See TargetInstrInfo::isHighLatencyDef(). 291 // By default, this is set to an arbitrarily high number of cycles 292 // likely to have some impact on scheduling heuristics. 293 unsigned HighLatency; 294 static const unsigned DefaultHighLatency = 10; 295 296 // MispredictPenalty is the typical number of extra cycles the processor 297 // takes to recover from a branch misprediction. 298 unsigned MispredictPenalty; 299 static const unsigned DefaultMispredictPenalty = 10; 300 301 bool PostRAScheduler; // default value is false 302 303 bool CompleteModel; 304 305 unsigned ProcID; 306 const MCProcResourceDesc *ProcResourceTable; 307 const MCSchedClassDesc *SchedClassTable; 308 unsigned NumProcResourceKinds; 309 unsigned NumSchedClasses; 310 // Instruction itinerary tables used by InstrItineraryData. 311 friend class InstrItineraryData; 312 const InstrItinerary *InstrItineraries; 313 314 const MCExtraProcessorInfo *ExtraProcessorInfo; 315 316 bool hasExtraProcessorInfo() const { return ExtraProcessorInfo; } 317 318 unsigned getProcessorID() const { return ProcID; } 319 320 /// Does this machine model include instruction-level scheduling. 321 bool hasInstrSchedModel() const { return SchedClassTable; } 322 323 const MCExtraProcessorInfo &getExtraProcessorInfo() const { 324 assert(hasExtraProcessorInfo() && 325 "No extra information available for this model"); 326 return *ExtraProcessorInfo; 327 } 328 329 /// Return true if this machine model data for all instructions with a 330 /// scheduling class (itinerary class or SchedRW list). 331 bool isComplete() const { return CompleteModel; } 332 333 /// Return true if machine supports out of order execution. 334 bool isOutOfOrder() const { return MicroOpBufferSize > 1; } 335 336 unsigned getNumProcResourceKinds() const { 337 return NumProcResourceKinds; 338 } 339 340 const MCProcResourceDesc *getProcResource(unsigned ProcResourceIdx) const { 341 assert(hasInstrSchedModel() && "No scheduling machine model"); 342 343 assert(ProcResourceIdx < NumProcResourceKinds && "bad proc resource idx"); 344 return &ProcResourceTable[ProcResourceIdx]; 345 } 346 347 const MCSchedClassDesc *getSchedClassDesc(unsigned SchedClassIdx) const { 348 assert(hasInstrSchedModel() && "No scheduling machine model"); 349 350 assert(SchedClassIdx < NumSchedClasses && "bad scheduling class idx"); 351 return &SchedClassTable[SchedClassIdx]; 352 } 353 354 /// Returns the latency value for the scheduling class. 355 static int computeInstrLatency(const MCSubtargetInfo &STI, 356 const MCSchedClassDesc &SCDesc); 357 358 int computeInstrLatency(const MCSubtargetInfo &STI, unsigned SClass) const; 359 int computeInstrLatency(const MCSubtargetInfo &STI, const MCInstrInfo &MCII, 360 const MCInst &Inst) const; 361 362 // Returns the reciprocal throughput information from a MCSchedClassDesc. 363 static double 364 getReciprocalThroughput(const MCSubtargetInfo &STI, 365 const MCSchedClassDesc &SCDesc); 366 367 static double 368 getReciprocalThroughput(unsigned SchedClass, const InstrItineraryData &IID); 369 370 double 371 getReciprocalThroughput(const MCSubtargetInfo &STI, const MCInstrInfo &MCII, 372 const MCInst &Inst) const; 373 374 /// Returns the maximum forwarding delay for register reads dependent on 375 /// writes of scheduling class WriteResourceIdx. 376 static unsigned getForwardingDelayCycles(ArrayRef<MCReadAdvanceEntry> Entries, 377 unsigned WriteResourceIdx = 0); 378 379 /// Returns the default initialized model. 380 static const MCSchedModel &GetDefaultSchedModel() { return Default; } 381 static const MCSchedModel Default; 382 }; 383 384 } // namespace llvm 385 386 #endif 387