11541Srgrimes//===-- llvm/MC/MCInstrItineraries.h - Scheduling ---------------*- C++ -*-===// 21541Srgrimes// 31541Srgrimes// The LLVM Compiler Infrastructure 41541Srgrimes// 51541Srgrimes// This file is distributed under the University of Illinois Open Source 61541Srgrimes// License. See LICENSE.TXT for details. 71541Srgrimes// 81541Srgrimes//===----------------------------------------------------------------------===// 91541Srgrimes// 101541Srgrimes// This file describes the structures used for instruction 111541Srgrimes// itineraries, stages, and operand reads/writes. This is used by 121541Srgrimes// schedulers to determine instruction stages and latencies. 131541Srgrimes// 141541Srgrimes//===----------------------------------------------------------------------===// 151541Srgrimes 161541Srgrimes#ifndef LLVM_MC_MCINSTRITINERARIES_H 171541Srgrimes#define LLVM_MC_MCINSTRITINERARIES_H 181541Srgrimes 191541Srgrimes#include "llvm/MC/MCSchedule.h" 201541Srgrimes#include <algorithm> 211541Srgrimes 221541Srgrimesnamespace llvm { 231541Srgrimes 241541Srgrimes//===----------------------------------------------------------------------===// 251541Srgrimes/// Instruction stage - These values represent a non-pipelined step in 261541Srgrimes/// the execution of an instruction. Cycles represents the number of 271541Srgrimes/// discrete time slots needed to complete the stage. Units represent 281541Srgrimes/// the choice of functional units that can be used to complete the 291541Srgrimes/// stage. Eg. IntUnit1, IntUnit2. NextCycles indicates how many 301541Srgrimes/// cycles should elapse from the start of this stage to the start of 311541Srgrimes/// the next stage in the itinerary. A value of -1 indicates that the 321541Srgrimes/// next stage should start immediately after the current one. 331541Srgrimes/// For example: 341541Srgrimes/// 351541Srgrimes/// { 1, x, -1 } 361541Srgrimes/// indicates that the stage occupies FU x for 1 cycle and that 371541Srgrimes/// the next stage starts immediately after this one. 381541Srgrimes/// 3913456Sbde/// { 2, x|y, 1 } 401541Srgrimes/// indicates that the stage occupies either FU x or FU y for 2 411541Srgrimes/// consecuative cycles and that the next stage starts one cycle 422165Spaul/// after this stage starts. That is, the stage requirements 432865Sbde/// overlap in time. 442165Spaul/// 451549Srgrimes/// { 1, x, 0 } 467566Sjoerg/// indicates that the stage occupies FU x for 1 cycle and that 471549Srgrimes/// the next stage starts in this same cycle. This can be used to 481541Srgrimes/// indicate that the instruction requires multiple stages at the 491541Srgrimes/// same time. 501541Srgrimes/// 511541Srgrimes/// FU reservation can be of two different kinds: 521541Srgrimes/// - FUs which instruction actually requires 531541Srgrimes/// - FUs which instruction just reserves. Reserved unit is not available for 541541Srgrimes/// execution of other instruction. However, several instructions can reserve 551541Srgrimes/// the same unit several times. 561541Srgrimes/// Such two types of units reservation is used to model instruction domain 571541Srgrimes/// change stalls, FUs using the same resource (e.g. same register file), etc. 581541Srgrimes 591541Srgrimesstruct InstrStage { 608876Srgrimes enum ReservationKinds { 611541Srgrimes Required = 0, 621541Srgrimes Reserved = 1 631541Srgrimes }; 641541Srgrimes 651541Srgrimes unsigned Cycles_; ///< Length of stage in machine cycles 661541Srgrimes unsigned Units_; ///< Choice of functional units 671541Srgrimes int NextCycles_; ///< Number of machine cycles to next stage 681541Srgrimes ReservationKinds Kind_; ///< Kind of the FU reservation 691541Srgrimes 701858Sdg /// getCycles - returns the number of cycles the stage is occupied 711541Srgrimes unsigned getCycles() const { 721541Srgrimes return Cycles_; 731541Srgrimes } 741541Srgrimes 751541Srgrimes /// getUnits - returns the choice of FUs 767090Sbde unsigned getUnits() const { 777090Sbde return Units_; 781541Srgrimes } 791541Srgrimes 801541Srgrimes ReservationKinds getReservationKind() const { 811541Srgrimes return Kind_; 821541Srgrimes } 831541Srgrimes 848504Sdg /// getNextCycles - returns the number of cycles from the start of 851541Srgrimes /// this stage to the start of the next stage in the itinerary 861541Srgrimes unsigned getNextCycles() const { 871541Srgrimes return (NextCycles_ >= 0) ? (unsigned)NextCycles_ : Cycles_; 881541Srgrimes } 891541Srgrimes}; 901541Srgrimes 911541Srgrimes 921541Srgrimes//===----------------------------------------------------------------------===// 931541Srgrimes/// Instruction itinerary - An itinerary represents the scheduling 941541Srgrimes/// information for an instruction. This includes a set of stages 951541Srgrimes/// occupies by the instruction, and the pipeline cycle in which 961541Srgrimes/// operands are read and written. 971541Srgrimes/// 981541Srgrimesstruct InstrItinerary { 991541Srgrimes int NumMicroOps; ///< # of micro-ops, -1 means it's variable 1001541Srgrimes unsigned FirstStage; ///< Index of first stage in itinerary 1011541Srgrimes unsigned LastStage; ///< Index of last + 1 stage in itinerary 1021541Srgrimes unsigned FirstOperandCycle; ///< Index of first operand rd/wr 1031541Srgrimes unsigned LastOperandCycle; ///< Index of last + 1 operand rd/wr 1041541Srgrimes}; 1051541Srgrimes 1061541Srgrimes 1071541Srgrimes//===----------------------------------------------------------------------===// 1081541Srgrimes/// Instruction itinerary Data - Itinerary data supplied by a subtarget to be 1091541Srgrimes/// used by a target. 1101541Srgrimes/// 1113304Sphkclass InstrItineraryData { 1121541Srgrimespublic: 1137612Sdg const MCSchedModel *SchedModel; ///< Basic machine properties. 1141541Srgrimes const InstrStage *Stages; ///< Array of stages selected 1152059Sdg const unsigned *OperandCycles; ///< Array of operand cycles selected 1162059Sdg const unsigned *Forwardings; ///< Array of pipeline forwarding pathes 1171541Srgrimes const InstrItinerary *Itineraries; ///< Array of itineraries selected 1181541Srgrimes 11913446Sphk /// Ctors. 1201541Srgrimes /// 1211541Srgrimes InstrItineraryData() : SchedModel(&MCSchedModel::DefaultSchedModel), 12213446Sphk Stages(0), OperandCycles(0), 1232112Swollman Forwardings(0), Itineraries(0) {} 12413446Sphk 1251541Srgrimes InstrItineraryData(const MCSchedModel *SM, const InstrStage *S, 1261541Srgrimes const unsigned *OS, const unsigned *F) 1278215Sdg : SchedModel(SM), Stages(S), OperandCycles(OS), Forwardings(F), 1288215Sdg Itineraries(SchedModel->InstrItineraries) {} 12913414Sphk 1301541Srgrimes /// isEmpty - Returns true if there are no itineraries. 1318215Sdg /// 1328215Sdg bool isEmpty() const { return Itineraries == 0; } 13313456Sbde 13413456Sbde /// isEndMarker - Returns true if the index is for the end marker 13513456Sbde /// itinerary. 13613456Sbde /// 13713456Sbde bool isEndMarker(unsigned ItinClassIndx) const { 13813456Sbde return ((Itineraries[ItinClassIndx].FirstStage == ~0U) && 1391541Srgrimes (Itineraries[ItinClassIndx].LastStage == ~0U)); 14013456Sbde } 14113456Sbde 1421541Srgrimes /// beginStage - Return the first stage of the itinerary. 1431541Srgrimes /// 14413456Sbde const InstrStage *beginStage(unsigned ItinClassIndx) const { 1451541Srgrimes unsigned StageIdx = Itineraries[ItinClassIndx].FirstStage; 1466358Sphk return Stages + StageIdx; 1471541Srgrimes } 1481541Srgrimes 1491541Srgrimes /// endStage - Return the last+1 stage of the itinerary. 1501541Srgrimes /// 1511541Srgrimes const InstrStage *endStage(unsigned ItinClassIndx) const { 1521541Srgrimes unsigned StageIdx = Itineraries[ItinClassIndx].LastStage; 1531541Srgrimes return Stages + StageIdx; 1541541Srgrimes } 1551541Srgrimes 1561541Srgrimes /// getStageLatency - Return the total stage latency of the given 1571541Srgrimes /// class. The latency is the maximum completion time for any stage 1581541Srgrimes /// in the itinerary. 1591541Srgrimes /// 1603484Sphk /// If no stages exist, it defaults to one cycle. 1617109Sphk unsigned getStageLatency(unsigned ItinClassIndx) const { 1622112Swollman // If the target doesn't provide itinerary information, use a simple 1632112Swollman // non-zero default value for all instructions. 1642112Swollman if (isEmpty()) 1652112Swollman return 1; 1662112Swollman 1672112Swollman // Calculate the maximum completion time for any stage. 1682112Swollman unsigned Latency = 0, StartCycle = 0; 1692112Swollman for (const InstrStage *IS = beginStage(ItinClassIndx), 1707090Sbde *E = endStage(ItinClassIndx); IS != E; ++IS) { 1717090Sbde Latency = std::max(Latency, StartCycle + IS->getCycles()); 1727090Sbde StartCycle += IS->getNextCycles(); 1737090Sbde } 1747090Sbde return Latency; 1757090Sbde } 1767090Sbde 1777090Sbde /// getOperandCycle - Return the cycle for the given class and 1787090Sbde /// operand. Return -1 if no cycle is specified for the operand. 1797090Sbde /// 1802112Swollman int getOperandCycle(unsigned ItinClassIndx, unsigned OperandIdx) const { 1812112Swollman if (isEmpty()) 1822112Swollman return -1; 1832112Swollman 1842112Swollman unsigned FirstIdx = Itineraries[ItinClassIndx].FirstOperandCycle; 1852112Swollman unsigned LastIdx = Itineraries[ItinClassIndx].LastOperandCycle; 1863484Sphk if ((FirstIdx + OperandIdx) >= LastIdx) 1872165Spaul return -1; 18813438Sphk 18913438Sphk return (int)OperandCycles[FirstIdx + OperandIdx]; 19013438Sphk } 19113438Sphk 19213438Sphk /// hasPipelineForwarding - Return true if there is a pipeline forwarding 19313438Sphk /// between instructions of itinerary classes DefClass and UseClasses so that 19413438Sphk /// value produced by an instruction of itinerary class DefClass, operand 1952865Sbde /// index DefIdx can be bypassed when it's read by an instruction of 196 /// itinerary class UseClass, operand index UseIdx. 197 bool hasPipelineForwarding(unsigned DefClass, unsigned DefIdx, 198 unsigned UseClass, unsigned UseIdx) const { 199 unsigned FirstDefIdx = Itineraries[DefClass].FirstOperandCycle; 200 unsigned LastDefIdx = Itineraries[DefClass].LastOperandCycle; 201 if ((FirstDefIdx + DefIdx) >= LastDefIdx) 202 return false; 203 if (Forwardings[FirstDefIdx + DefIdx] == 0) 204 return false; 205 206 unsigned FirstUseIdx = Itineraries[UseClass].FirstOperandCycle; 207 unsigned LastUseIdx = Itineraries[UseClass].LastOperandCycle; 208 if ((FirstUseIdx + UseIdx) >= LastUseIdx) 209 return false; 210 211 return Forwardings[FirstDefIdx + DefIdx] == 212 Forwardings[FirstUseIdx + UseIdx]; 213 } 214 215 /// getOperandLatency - Compute and return the use operand latency of a given 216 /// itinerary class and operand index if the value is produced by an 217 /// instruction of the specified itinerary class and def operand index. 218 int getOperandLatency(unsigned DefClass, unsigned DefIdx, 219 unsigned UseClass, unsigned UseIdx) const { 220 if (isEmpty()) 221 return -1; 222 223 int DefCycle = getOperandCycle(DefClass, DefIdx); 224 if (DefCycle == -1) 225 return -1; 226 227 int UseCycle = getOperandCycle(UseClass, UseIdx); 228 if (UseCycle == -1) 229 return -1; 230 231 UseCycle = DefCycle - UseCycle + 1; 232 if (UseCycle > 0 && 233 hasPipelineForwarding(DefClass, DefIdx, UseClass, UseIdx)) 234 // FIXME: This assumes one cycle benefit for every pipeline forwarding. 235 --UseCycle; 236 return UseCycle; 237 } 238 239 /// getNumMicroOps - Return the number of micro-ops that the given class 240 /// decodes to. Return -1 for classes that require dynamic lookup via 241 /// TargetInstrInfo. 242 int getNumMicroOps(unsigned ItinClassIndx) const { 243 if (isEmpty()) 244 return 1; 245 return Itineraries[ItinClassIndx].NumMicroOps; 246 } 247}; 248 249} // End llvm namespace 250 251#endif 252