1 //===-- llvm/MC/MCSchedule.h - Scheduling -----------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the classes used to describe a subtarget's machine model 11 // for scheduling and other instruction cost heuristics. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_MC_MCSCHEDULE_H 16 #define LLVM_MC_MCSCHEDULE_H 17 18 #include "llvm/Support/DataTypes.h" 19 #include <cassert> 20 21 namespace llvm { 22 23 struct InstrItinerary; 24 25 /// Define a kind of processor resource that will be modeled by the scheduler. 26 struct MCProcResourceDesc { 27 #ifndef NDEBUG 28 const char *Name; 29 #endif 30 unsigned NumUnits; // Number of resource of this kind 31 unsigned SuperIdx; // Index of the resources kind that contains this kind. 32 33 // Number of resources that may be buffered. 34 // 35 // Buffered resources (BufferSize != 0) may be consumed at some indeterminate 36 // cycle after dispatch. This should be used for out-of-order cpus when 37 // instructions that use this resource can be buffered in a reservaton 38 // station. 39 // 40 // Unbuffered resources (BufferSize == 0) always consume their resource some 41 // fixed number of cycles after dispatch. If a resource is unbuffered, then 42 // the scheduler will avoid scheduling instructions with conflicting resources 43 // in the same cycle. This is for in-order cpus, or the in-order portion of 44 // an out-of-order cpus. 45 int BufferSize; 46 47 bool operator==(const MCProcResourceDesc &Other) const { 48 return NumUnits == Other.NumUnits && SuperIdx == Other.SuperIdx 49 && BufferSize == Other.BufferSize; 50 } 51 }; 52 53 /// Identify one of the processor resource kinds consumed by a particular 54 /// scheduling class for the specified number of cycles. 55 struct MCWriteProcResEntry { 56 unsigned ProcResourceIdx; 57 unsigned Cycles; 58 59 bool operator==(const MCWriteProcResEntry &Other) const { 60 return ProcResourceIdx == Other.ProcResourceIdx && Cycles == Other.Cycles; 61 } 62 }; 63 64 /// Specify the latency in cpu cycles for a particular scheduling class and def 65 /// index. -1 indicates an invalid latency. Heuristics would typically consider 66 /// an instruction with invalid latency to have infinite latency. Also identify 67 /// the WriteResources of this def. When the operand expands to a sequence of 68 /// writes, this ID is the last write in the sequence. 69 struct MCWriteLatencyEntry { 70 int Cycles; 71 unsigned WriteResourceID; 72 73 bool operator==(const MCWriteLatencyEntry &Other) const { 74 return Cycles == Other.Cycles && WriteResourceID == Other.WriteResourceID; 75 } 76 }; 77 78 /// Specify the number of cycles allowed after instruction issue before a 79 /// particular use operand reads its registers. This effectively reduces the 80 /// write's latency. Here we allow negative cycles for corner cases where 81 /// latency increases. This rule only applies when the entry's WriteResource 82 /// matches the write's WriteResource. 83 /// 84 /// MCReadAdvanceEntries are sorted first by operand index (UseIdx), then by 85 /// WriteResourceIdx. 86 struct MCReadAdvanceEntry { 87 unsigned UseIdx; 88 unsigned WriteResourceID; 89 int Cycles; 90 91 bool operator==(const MCReadAdvanceEntry &Other) const { 92 return UseIdx == Other.UseIdx && WriteResourceID == Other.WriteResourceID 93 && Cycles == Other.Cycles; 94 } 95 }; 96 97 /// Summarize the scheduling resources required for an instruction of a 98 /// particular scheduling class. 99 /// 100 /// Defined as an aggregate struct for creating tables with initializer lists. 101 struct MCSchedClassDesc { 102 static const unsigned short InvalidNumMicroOps = UINT16_MAX; 103 static const unsigned short VariantNumMicroOps = UINT16_MAX - 1; 104 105 #ifndef NDEBUG 106 const char* Name; 107 #endif 108 unsigned short NumMicroOps; 109 bool BeginGroup; 110 bool EndGroup; 111 unsigned WriteProcResIdx; // First index into WriteProcResTable. 112 unsigned NumWriteProcResEntries; 113 unsigned WriteLatencyIdx; // First index into WriteLatencyTable. 114 unsigned NumWriteLatencyEntries; 115 unsigned ReadAdvanceIdx; // First index into ReadAdvanceTable. 116 unsigned NumReadAdvanceEntries; 117 118 bool isValid() const { 119 return NumMicroOps != InvalidNumMicroOps; 120 } 121 bool isVariant() const { 122 return NumMicroOps == VariantNumMicroOps; 123 } 124 }; 125 126 /// Machine model for scheduling, bundling, and heuristics. 127 /// 128 /// The machine model directly provides basic information about the 129 /// microarchitecture to the scheduler in the form of properties. It also 130 /// optionally refers to scheduler resource tables and itinerary 131 /// tables. Scheduler resource tables model the latency and cost for each 132 /// instruction type. Itinerary tables are an independent mechanism that 133 /// provides a detailed reservation table describing each cycle of instruction 134 /// execution. Subtargets may define any or all of the above categories of data 135 /// depending on the type of CPU and selected scheduler. 136 class MCSchedModel { 137 public: 138 static MCSchedModel DefaultSchedModel; // For unknown processors. 139 140 // IssueWidth is the maximum number of instructions that may be scheduled in 141 // the same per-cycle group. 142 unsigned IssueWidth; 143 static const unsigned DefaultIssueWidth = 1; 144 145 // MicroOpBufferSize is the number of micro-ops that the processor may buffer 146 // for out-of-order execution. 147 // 148 // "0" means operations that are not ready in this cycle are not considered 149 // for scheduling (they go in the pending queue). Latency is paramount. This 150 // may be more efficient if many instructions are pending in a schedule. 151 // 152 // "1" means all instructions are considered for scheduling regardless of 153 // whether they are ready in this cycle. Latency still causes issue stalls, 154 // but we balance those stalls against other heuristics. 155 // 156 // "> 1" means the processor is out-of-order. This is a machine independent 157 // estimate of highly machine specific characteristics such as the register 158 // renaming pool and reorder buffer. 159 unsigned MicroOpBufferSize; 160 static const unsigned DefaultMicroOpBufferSize = 0; 161 162 // LoopMicroOpBufferSize is the number of micro-ops that the processor may 163 // buffer for optimized loop execution. More generally, this represents the 164 // optimal number of micro-ops in a loop body. A loop may be partially 165 // unrolled to bring the count of micro-ops in the loop body closer to this 166 // number. 167 unsigned LoopMicroOpBufferSize; 168 static const unsigned DefaultLoopMicroOpBufferSize = 0; 169 170 // LoadLatency is the expected latency of load instructions. 171 // 172 // If MinLatency >= 0, this may be overriden for individual load opcodes by 173 // InstrItinerary OperandCycles. 174 unsigned LoadLatency; 175 static const unsigned DefaultLoadLatency = 4; 176 177 // HighLatency is the expected latency of "very high latency" operations. 178 // See TargetInstrInfo::isHighLatencyDef(). 179 // By default, this is set to an arbitrarily high number of cycles 180 // likely to have some impact on scheduling heuristics. 181 // If MinLatency >= 0, this may be overriden by InstrItinData OperandCycles. 182 unsigned HighLatency; 183 static const unsigned DefaultHighLatency = 10; 184 185 // MispredictPenalty is the typical number of extra cycles the processor 186 // takes to recover from a branch misprediction. 187 unsigned MispredictPenalty; 188 static const unsigned DefaultMispredictPenalty = 10; 189 190 bool CompleteModel; 191 192 private: 193 unsigned ProcID; 194 const MCProcResourceDesc *ProcResourceTable; 195 const MCSchedClassDesc *SchedClassTable; 196 unsigned NumProcResourceKinds; 197 unsigned NumSchedClasses; 198 // Instruction itinerary tables used by InstrItineraryData. 199 friend class InstrItineraryData; 200 const InstrItinerary *InstrItineraries; 201 202 public: 203 // Default's must be specified as static const literals so that tablegenerated 204 // target code can use it in static initializers. The defaults need to be 205 // initialized in this default ctor because some clients directly instantiate 206 // MCSchedModel instead of using a generated itinerary. 207 MCSchedModel(): IssueWidth(DefaultIssueWidth), 208 MicroOpBufferSize(DefaultMicroOpBufferSize), 209 LoopMicroOpBufferSize(DefaultLoopMicroOpBufferSize), 210 LoadLatency(DefaultLoadLatency), 211 HighLatency(DefaultHighLatency), 212 MispredictPenalty(DefaultMispredictPenalty), 213 CompleteModel(true), ProcID(0), ProcResourceTable(nullptr), 214 SchedClassTable(nullptr), NumProcResourceKinds(0), 215 NumSchedClasses(0), InstrItineraries(nullptr) { 216 (void)NumProcResourceKinds; 217 (void)NumSchedClasses; 218 } 219 220 // Table-gen driven ctor. 221 MCSchedModel(unsigned iw, int mbs, int lmbs, unsigned ll, unsigned hl, 222 unsigned mp, bool cm, unsigned pi, const MCProcResourceDesc *pr, 223 const MCSchedClassDesc *sc, unsigned npr, unsigned nsc, 224 const InstrItinerary *ii): 225 IssueWidth(iw), MicroOpBufferSize(mbs), LoopMicroOpBufferSize(lmbs), 226 LoadLatency(ll), HighLatency(hl), 227 MispredictPenalty(mp), CompleteModel(cm), ProcID(pi), 228 ProcResourceTable(pr), SchedClassTable(sc), NumProcResourceKinds(npr), 229 NumSchedClasses(nsc), InstrItineraries(ii) {} 230 231 unsigned getProcessorID() const { return ProcID; } 232 233 /// Does this machine model include instruction-level scheduling. 234 bool hasInstrSchedModel() const { return SchedClassTable; } 235 236 /// Return true if this machine model data for all instructions with a 237 /// scheduling class (itinerary class or SchedRW list). 238 bool isComplete() const { return CompleteModel; } 239 240 unsigned getNumProcResourceKinds() const { 241 return NumProcResourceKinds; 242 } 243 244 const MCProcResourceDesc *getProcResource(unsigned ProcResourceIdx) const { 245 assert(hasInstrSchedModel() && "No scheduling machine model"); 246 247 assert(ProcResourceIdx < NumProcResourceKinds && "bad proc resource idx"); 248 return &ProcResourceTable[ProcResourceIdx]; 249 } 250 251 const MCSchedClassDesc *getSchedClassDesc(unsigned SchedClassIdx) const { 252 assert(hasInstrSchedModel() && "No scheduling machine model"); 253 254 assert(SchedClassIdx < NumSchedClasses && "bad scheduling class idx"); 255 return &SchedClassTable[SchedClassIdx]; 256 } 257 }; 258 259 } // End llvm namespace 260 261 #endif 262
