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 21 namespace 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 58 struct 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 /// 97 struct 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 Data - Itinerary data supplied by a subtarget to be 108 /// used by a target. 109 /// 110 class InstrItineraryData { 111 public: 112 const InstrStage *Stages; ///< Array of stages selected 113 const unsigned *OperandCycles; ///< Array of operand cycles selected 114 const unsigned *Forwardings; ///< Array of pipeline forwarding pathes 115 const InstrItinerary *Itineraries; ///< Array of itineraries selected 116 unsigned IssueWidth; ///< Max issue per cycle. 0=Unknown. 117 118 /// Ctors. 119 /// 120 InstrItineraryData() : Stages(0), OperandCycles(0), Forwardings(0), 121 Itineraries(0), IssueWidth(0) {} 122 123 InstrItineraryData(const InstrStage *S, const unsigned *OS, 124 const unsigned *F, const InstrItinerary *I) 125 : Stages(S), OperandCycles(OS), Forwardings(F), Itineraries(I), 126 IssueWidth(0) {} 127 128 /// isEmpty - Returns true if there are no itineraries. 129 /// 130 bool isEmpty() const { return Itineraries == 0; } 131 132 /// isEndMarker - Returns true if the index is for the end marker 133 /// itinerary. 134 /// 135 bool isEndMarker(unsigned ItinClassIndx) const { 136 return ((Itineraries[ItinClassIndx].FirstStage == ~0U) && 137 (Itineraries[ItinClassIndx].LastStage == ~0U)); 138 } 139 140 /// beginStage - Return the first stage of the itinerary. 141 /// 142 const InstrStage *beginStage(unsigned ItinClassIndx) const { 143 unsigned StageIdx = Itineraries[ItinClassIndx].FirstStage; 144 return Stages + StageIdx; 145 } 146 147 /// endStage - Return the last+1 stage of the itinerary. 148 /// 149 const InstrStage *endStage(unsigned ItinClassIndx) const { 150 unsigned StageIdx = Itineraries[ItinClassIndx].LastStage; 151 return Stages + StageIdx; 152 } 153 154 /// getStageLatency - Return the total stage latency of the given 155 /// class. The latency is the maximum completion time for any stage 156 /// in the itinerary. 157 /// 158 unsigned getStageLatency(unsigned ItinClassIndx) const { 159 // If the target doesn't provide itinerary information, use a simple 160 // non-zero default value for all instructions. Some target's provide a 161 // dummy (Generic) itinerary which should be handled as if it's itinerary is 162 // empty. We identify this by looking for a reference to stage zero (invalid 163 // stage). This is different from beginStage == endState != 0, which could 164 // be used for zero-latency pseudo ops. 165 if (isEmpty() || Itineraries[ItinClassIndx].FirstStage == 0) 166 return 1; 167 168 // Calculate the maximum completion time for any stage. 169 unsigned Latency = 0, StartCycle = 0; 170 for (const InstrStage *IS = beginStage(ItinClassIndx), 171 *E = endStage(ItinClassIndx); IS != E; ++IS) { 172 Latency = std::max(Latency, StartCycle + IS->getCycles()); 173 StartCycle += IS->getNextCycles(); 174 } 175 176 return Latency; 177 } 178 179 /// getOperandCycle - Return the cycle for the given class and 180 /// operand. Return -1 if no cycle is specified for the operand. 181 /// 182 int getOperandCycle(unsigned ItinClassIndx, unsigned OperandIdx) const { 183 if (isEmpty()) 184 return -1; 185 186 unsigned FirstIdx = Itineraries[ItinClassIndx].FirstOperandCycle; 187 unsigned LastIdx = Itineraries[ItinClassIndx].LastOperandCycle; 188 if ((FirstIdx + OperandIdx) >= LastIdx) 189 return -1; 190 191 return (int)OperandCycles[FirstIdx + OperandIdx]; 192 } 193 194 /// hasPipelineForwarding - Return true if there is a pipeline forwarding 195 /// between instructions of itinerary classes DefClass and UseClasses so that 196 /// value produced by an instruction of itinerary class DefClass, operand 197 /// index DefIdx can be bypassed when it's read by an instruction of 198 /// itinerary class UseClass, operand index UseIdx. 199 bool hasPipelineForwarding(unsigned DefClass, unsigned DefIdx, 200 unsigned UseClass, unsigned UseIdx) const { 201 unsigned FirstDefIdx = Itineraries[DefClass].FirstOperandCycle; 202 unsigned LastDefIdx = Itineraries[DefClass].LastOperandCycle; 203 if ((FirstDefIdx + DefIdx) >= LastDefIdx) 204 return false; 205 if (Forwardings[FirstDefIdx + DefIdx] == 0) 206 return false; 207 208 unsigned FirstUseIdx = Itineraries[UseClass].FirstOperandCycle; 209 unsigned LastUseIdx = Itineraries[UseClass].LastOperandCycle; 210 if ((FirstUseIdx + UseIdx) >= LastUseIdx) 211 return false; 212 213 return Forwardings[FirstDefIdx + DefIdx] == 214 Forwardings[FirstUseIdx + UseIdx]; 215 } 216 217 /// getOperandLatency - Compute and return the use operand latency of a given 218 /// itinerary class and operand index if the value is produced by an 219 /// instruction of the specified itinerary class and def operand index. 220 int getOperandLatency(unsigned DefClass, unsigned DefIdx, 221 unsigned UseClass, unsigned UseIdx) const { 222 if (isEmpty()) 223 return -1; 224 225 int DefCycle = getOperandCycle(DefClass, DefIdx); 226 if (DefCycle == -1) 227 return -1; 228 229 int UseCycle = getOperandCycle(UseClass, UseIdx); 230 if (UseCycle == -1) 231 return -1; 232 233 UseCycle = DefCycle - UseCycle + 1; 234 if (UseCycle > 0 && 235 hasPipelineForwarding(DefClass, DefIdx, UseClass, UseIdx)) 236 // FIXME: This assumes one cycle benefit for every pipeline forwarding. 237 --UseCycle; 238 return UseCycle; 239 } 240 241 /// isMicroCoded - Return true if the instructions in the given class decode 242 /// to more than one micro-ops. 243 bool isMicroCoded(unsigned ItinClassIndx) const { 244 if (isEmpty()) 245 return false; 246 return Itineraries[ItinClassIndx].NumMicroOps != 1; 247 } 248 }; 249 250 251 } // End llvm namespace 252 253 #endif 254
