MCInstrItineraries.h revision 0076ad7eebb46c07288eec20e385dd8eaff736fb
1//===-- llvm/MC/MCInstrItineraries.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 describes the structures used for instruction 11// itineraries, stages, and operand reads/writes. This is used by 12// schedulers to determine instruction stages and latencies. 13// 14//===----------------------------------------------------------------------===// 15 16#ifndef LLVM_MC_MCINSTRITINERARIES_H 17#define LLVM_MC_MCINSTRITINERARIES_H 18 19#include <algorithm> 20 21namespace llvm { 22 23//===----------------------------------------------------------------------===// 24/// Instruction stage - These values represent a non-pipelined step in 25/// the execution of an instruction. Cycles represents the number of 26/// discrete time slots needed to complete the stage. Units represent 27/// the choice of functional units that can be used to complete the 28/// stage. Eg. IntUnit1, IntUnit2. NextCycles indicates how many 29/// cycles should elapse from the start of this stage to the start of 30/// the next stage in the itinerary. A value of -1 indicates that the 31/// next stage should start immediately after the current one. 32/// For example: 33/// 34/// { 1, x, -1 } 35/// indicates that the stage occupies FU x for 1 cycle and that 36/// the next stage starts immediately after this one. 37/// 38/// { 2, x|y, 1 } 39/// indicates that the stage occupies either FU x or FU y for 2 40/// consecuative cycles and that the next stage starts one cycle 41/// after this stage starts. That is, the stage requirements 42/// overlap in time. 43/// 44/// { 1, x, 0 } 45/// indicates that the stage occupies FU x for 1 cycle and that 46/// the next stage starts in this same cycle. This can be used to 47/// indicate that the instruction requires multiple stages at the 48/// same time. 49/// 50/// FU reservation can be of two different kinds: 51/// - FUs which instruction actually requires 52/// - FUs which instruction just reserves. Reserved unit is not available for 53/// execution of other instruction. However, several instructions can reserve 54/// the same unit several times. 55/// Such two types of units reservation is used to model instruction domain 56/// change stalls, FUs using the same resource (e.g. same register file), etc. 57 58struct InstrStage { 59 enum ReservationKinds { 60 Required = 0, 61 Reserved = 1 62 }; 63 64 unsigned Cycles_; ///< Length of stage in machine cycles 65 unsigned Units_; ///< Choice of functional units 66 int NextCycles_; ///< Number of machine cycles to next stage 67 ReservationKinds Kind_; ///< Kind of the FU reservation 68 69 /// getCycles - returns the number of cycles the stage is occupied 70 unsigned getCycles() const { 71 return Cycles_; 72 } 73 74 /// getUnits - returns the choice of FUs 75 unsigned getUnits() const { 76 return Units_; 77 } 78 79 ReservationKinds getReservationKind() const { 80 return Kind_; 81 } 82 83 /// getNextCycles - returns the number of cycles from the start of 84 /// this stage to the start of the next stage in the itinerary 85 unsigned getNextCycles() const { 86 return (NextCycles_ >= 0) ? (unsigned)NextCycles_ : Cycles_; 87 } 88}; 89 90 91//===----------------------------------------------------------------------===// 92/// Instruction itinerary - An itinerary represents the scheduling 93/// information for an instruction. This includes a set of stages 94/// occupies by the instruction, and the pipeline cycle in which 95/// operands are read and written. 96/// 97struct InstrItinerary { 98 unsigned NumMicroOps; ///< # of micro-ops, 0 means it's variable 99 unsigned FirstStage; ///< Index of first stage in itinerary 100 unsigned LastStage; ///< Index of last + 1 stage in itinerary 101 unsigned FirstOperandCycle; ///< Index of first operand rd/wr 102 unsigned LastOperandCycle; ///< Index of last + 1 operand rd/wr 103}; 104 105 106//===----------------------------------------------------------------------===// 107/// Instruction itinerary properties - These properties provide general 108/// information about the microarchitecture to the scheduler. 109/// 110struct InstrItineraryProps { 111 // IssueWidth is the maximum number of instructions that may be scheduled in 112 // the same per-cycle group. 113 unsigned IssueWidth; 114 static const unsigned DefaultIssueWidth = 1; 115 116 // MinLatency is the minimum latency between a register write 117 // followed by a data dependent read. This determines which 118 // instructions may be scheduled in the same per-cycle group. This 119 // is distinct from *expected* latency, which determines the likely 120 // critical path but does not guarantee a pipeline 121 // hazard. MinLatency can always be overridden by the number of 122 // InstrStage cycles. 123 // 124 // (-1) Standard in-order processor. 125 // Use InstrItinerary OperandCycles as MinLatency. 126 // If no OperandCycles exist, then use the cycle of the last InstrStage. 127 // 128 // (0) Out-of-order processor, or in-order with bundled dependencies. 129 // RAW dependencies may be dispatched in the same cycle. 130 // Optional InstrItinerary OperandCycles provides expected latency. 131 // 132 // (>0) In-order processor with variable latencies. 133 // Use the greater of this value or the cycle of the last InstrStage. 134 // Optional InstrItinerary OperandCycles provides expected latency. 135 // TODO: can't yet specify both min and expected latency per operand. 136 int MinLatency; 137 static const unsigned DefaultMinLatency = -1; 138 139 // LoadLatency is the expected latency of load instructions. 140 // 141 // If MinLatency >= 0, this may be overriden for individual load opcodes by 142 // InstrItinerary OperandCycles. 143 unsigned LoadLatency; 144 static const unsigned DefaultLoadLatency = 4; 145 146 // HighLatency is the expected latency of "very high latency" operations. 147 // See TargetInstrInfo::isHighLatencyDef(). 148 // By default, this is set to an arbitrarily high number of cycles 149 // likely to have some impact on scheduling heuristics. 150 // If MinLatency >= 0, this may be overriden by InstrItinData OperandCycles. 151 unsigned HighLatency; 152 static const unsigned DefaultHighLatency = 10; 153 154 // Default's must be specified as static const literals so that tablegenerated 155 // target code can use it in static initializers. The defaults need to be 156 // initialized in this default ctor because some clients directly instantiate 157 // InstrItineraryData instead of using a generated itinerary. 158 InstrItineraryProps(): IssueWidth(DefaultMinLatency), 159 MinLatency(DefaultMinLatency), 160 LoadLatency(DefaultLoadLatency), 161 HighLatency(DefaultHighLatency) {} 162 163 InstrItineraryProps(unsigned iw, int ml, unsigned ll, unsigned hl): 164 IssueWidth(iw), MinLatency(ml), LoadLatency(ll), HighLatency(hl) {} 165}; 166 167//===----------------------------------------------------------------------===// 168/// Encapsulate all subtarget specific information for scheduling for use with 169/// SubtargetInfoKV. 170struct InstrItinerarySubtargetValue { 171 const InstrItineraryProps *Props; 172 const InstrItinerary *Itineraries; 173}; 174 175//===----------------------------------------------------------------------===// 176/// Instruction itinerary Data - Itinerary data supplied by a subtarget to be 177/// used by a target. 178/// 179class InstrItineraryData { 180public: 181 InstrItineraryProps Props; 182 const InstrStage *Stages; ///< Array of stages selected 183 const unsigned *OperandCycles; ///< Array of operand cycles selected 184 const unsigned *Forwardings; ///< Array of pipeline forwarding pathes 185 const InstrItinerary *Itineraries; ///< Array of itineraries selected 186 187 /// Ctors. 188 /// 189 InstrItineraryData() : Stages(0), OperandCycles(0), Forwardings(0), 190 Itineraries(0) {} 191 192 InstrItineraryData(const InstrItineraryProps *P, const InstrStage *S, 193 const unsigned *OS, const unsigned *F, 194 const InstrItinerary *I) 195 : Props(*P), Stages(S), OperandCycles(OS), Forwardings(F), Itineraries(I) {} 196 197 /// isEmpty - Returns true if there are no itineraries. 198 /// 199 bool isEmpty() const { return Itineraries == 0; } 200 201 /// isEndMarker - Returns true if the index is for the end marker 202 /// itinerary. 203 /// 204 bool isEndMarker(unsigned ItinClassIndx) const { 205 return ((Itineraries[ItinClassIndx].FirstStage == ~0U) && 206 (Itineraries[ItinClassIndx].LastStage == ~0U)); 207 } 208 209 /// beginStage - Return the first stage of the itinerary. 210 /// 211 const InstrStage *beginStage(unsigned ItinClassIndx) const { 212 unsigned StageIdx = Itineraries[ItinClassIndx].FirstStage; 213 return Stages + StageIdx; 214 } 215 216 /// endStage - Return the last+1 stage of the itinerary. 217 /// 218 const InstrStage *endStage(unsigned ItinClassIndx) const { 219 unsigned StageIdx = Itineraries[ItinClassIndx].LastStage; 220 return Stages + StageIdx; 221 } 222 223 /// getStageLatency - Return the total stage latency of the given 224 /// class. The latency is the maximum completion time for any stage 225 /// in the itinerary. 226 /// 227 /// InstrStages override the itinerary's MinLatency property. In fact, if the 228 /// stage latencies, which may be zero, are less than MinLatency, 229 /// getStageLatency returns a value less than MinLatency. 230 /// 231 /// If no stages exist, MinLatency is used. If MinLatency is invalid (<0), 232 /// then it defaults to one cycle. 233 unsigned getStageLatency(unsigned ItinClassIndx) const { 234 // If the target doesn't provide itinerary information, use a simple 235 // non-zero default value for all instructions. Some target's provide a 236 // dummy (Generic) itinerary which should be handled as if it's itinerary is 237 // empty. We identify this by looking for a reference to stage zero (invalid 238 // stage). This is different from beginStage == endStage != 0, which could 239 // be used for zero-latency pseudo ops. 240 if (isEmpty() || Itineraries[ItinClassIndx].FirstStage == 0) 241 return (Props.MinLatency < 0) ? 1 : Props.MinLatency; 242 243 // Calculate the maximum completion time for any stage. 244 unsigned Latency = 0, StartCycle = 0; 245 for (const InstrStage *IS = beginStage(ItinClassIndx), 246 *E = endStage(ItinClassIndx); IS != E; ++IS) { 247 Latency = std::max(Latency, StartCycle + IS->getCycles()); 248 StartCycle += IS->getNextCycles(); 249 } 250 251 return Latency; 252 } 253 254 /// getOperandCycle - Return the cycle for the given class and 255 /// operand. Return -1 if no cycle is specified for the operand. 256 /// 257 int getOperandCycle(unsigned ItinClassIndx, unsigned OperandIdx) const { 258 if (isEmpty()) 259 return -1; 260 261 unsigned FirstIdx = Itineraries[ItinClassIndx].FirstOperandCycle; 262 unsigned LastIdx = Itineraries[ItinClassIndx].LastOperandCycle; 263 if ((FirstIdx + OperandIdx) >= LastIdx) 264 return -1; 265 266 return (int)OperandCycles[FirstIdx + OperandIdx]; 267 } 268 269 /// hasPipelineForwarding - Return true if there is a pipeline forwarding 270 /// between instructions of itinerary classes DefClass and UseClasses so that 271 /// value produced by an instruction of itinerary class DefClass, operand 272 /// index DefIdx can be bypassed when it's read by an instruction of 273 /// itinerary class UseClass, operand index UseIdx. 274 bool hasPipelineForwarding(unsigned DefClass, unsigned DefIdx, 275 unsigned UseClass, unsigned UseIdx) const { 276 unsigned FirstDefIdx = Itineraries[DefClass].FirstOperandCycle; 277 unsigned LastDefIdx = Itineraries[DefClass].LastOperandCycle; 278 if ((FirstDefIdx + DefIdx) >= LastDefIdx) 279 return false; 280 if (Forwardings[FirstDefIdx + DefIdx] == 0) 281 return false; 282 283 unsigned FirstUseIdx = Itineraries[UseClass].FirstOperandCycle; 284 unsigned LastUseIdx = Itineraries[UseClass].LastOperandCycle; 285 if ((FirstUseIdx + UseIdx) >= LastUseIdx) 286 return false; 287 288 return Forwardings[FirstDefIdx + DefIdx] == 289 Forwardings[FirstUseIdx + UseIdx]; 290 } 291 292 /// getOperandLatency - Compute and return the use operand latency of a given 293 /// itinerary class and operand index if the value is produced by an 294 /// instruction of the specified itinerary class and def operand index. 295 int getOperandLatency(unsigned DefClass, unsigned DefIdx, 296 unsigned UseClass, unsigned UseIdx) const { 297 if (isEmpty()) 298 return -1; 299 300 int DefCycle = getOperandCycle(DefClass, DefIdx); 301 if (DefCycle == -1) 302 return -1; 303 304 int UseCycle = getOperandCycle(UseClass, UseIdx); 305 if (UseCycle == -1) 306 return -1; 307 308 UseCycle = DefCycle - UseCycle + 1; 309 if (UseCycle > 0 && 310 hasPipelineForwarding(DefClass, DefIdx, UseClass, UseIdx)) 311 // FIXME: This assumes one cycle benefit for every pipeline forwarding. 312 --UseCycle; 313 return UseCycle; 314 } 315 316 /// isMicroCoded - Return true if the instructions in the given class decode 317 /// to more than one micro-ops. 318 bool isMicroCoded(unsigned ItinClassIndx) const { 319 if (isEmpty()) 320 return false; 321 return Itineraries[ItinClassIndx].NumMicroOps != 1; 322 } 323}; 324 325 326} // End llvm namespace 327 328#endif 329