1//===- CodeGenSchedule.h - Scheduling Machine Models ------------*- 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 structures to encapsulate the machine model as decribed in 11// the target description. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef CODEGEN_SCHEDULE_H 16#define CODEGEN_SCHEDULE_H 17 18#include "SetTheory.h" 19#include "llvm/TableGen/Record.h" 20#include "llvm/Support/ErrorHandling.h" 21#include "llvm/ADT/DenseMap.h" 22#include "llvm/ADT/StringMap.h" 23 24namespace llvm { 25 26class CodeGenTarget; 27class CodeGenSchedModels; 28class CodeGenInstruction; 29 30typedef std::vector<Record*> RecVec; 31typedef std::vector<Record*>::const_iterator RecIter; 32 33typedef std::vector<unsigned> IdxVec; 34typedef std::vector<unsigned>::const_iterator IdxIter; 35 36void splitSchedReadWrites(const RecVec &RWDefs, 37 RecVec &WriteDefs, RecVec &ReadDefs); 38 39/// We have two kinds of SchedReadWrites. Explicitly defined and inferred 40/// sequences. TheDef is nonnull for explicit SchedWrites, but Sequence may or 41/// may not be empty. TheDef is null for inferred sequences, and Sequence must 42/// be nonempty. 43/// 44/// IsVariadic controls whether the variants are expanded into multiple operands 45/// or a sequence of writes on one operand. 46struct CodeGenSchedRW { 47 unsigned Index; 48 std::string Name; 49 Record *TheDef; 50 bool IsRead; 51 bool IsAlias; 52 bool HasVariants; 53 bool IsVariadic; 54 bool IsSequence; 55 IdxVec Sequence; 56 RecVec Aliases; 57 58 CodeGenSchedRW(): Index(0), TheDef(0), IsAlias(false), HasVariants(false), 59 IsVariadic(false), IsSequence(false) {} 60 CodeGenSchedRW(unsigned Idx, Record *Def): Index(Idx), TheDef(Def), 61 IsAlias(false), IsVariadic(false) { 62 Name = Def->getName(); 63 IsRead = Def->isSubClassOf("SchedRead"); 64 HasVariants = Def->isSubClassOf("SchedVariant"); 65 if (HasVariants) 66 IsVariadic = Def->getValueAsBit("Variadic"); 67 68 // Read records don't currently have sequences, but it can be easily 69 // added. Note that implicit Reads (from ReadVariant) may have a Sequence 70 // (but no record). 71 IsSequence = Def->isSubClassOf("WriteSequence"); 72 } 73 74 CodeGenSchedRW(unsigned Idx, bool Read, const IdxVec &Seq, 75 const std::string &Name): 76 Index(Idx), Name(Name), TheDef(0), IsRead(Read), IsAlias(false), 77 HasVariants(false), IsVariadic(false), IsSequence(true), Sequence(Seq) { 78 assert(Sequence.size() > 1 && "implied sequence needs >1 RWs"); 79 } 80 81 bool isValid() const { 82 assert((!HasVariants || TheDef) && "Variant write needs record def"); 83 assert((!IsVariadic || HasVariants) && "Variadic write needs variants"); 84 assert((!IsSequence || !HasVariants) && "Sequence can't have variant"); 85 assert((!IsSequence || !Sequence.empty()) && "Sequence should be nonempty"); 86 assert((!IsAlias || Aliases.empty()) && "Alias cannot have aliases"); 87 return TheDef || !Sequence.empty(); 88 } 89 90#ifndef NDEBUG 91 void dump() const; 92#endif 93}; 94 95/// Represent a transition between SchedClasses induced by SchedVariant. 96struct CodeGenSchedTransition { 97 unsigned ToClassIdx; 98 IdxVec ProcIndices; 99 RecVec PredTerm; 100}; 101 102/// Scheduling class. 103/// 104/// Each instruction description will be mapped to a scheduling class. There are 105/// four types of classes: 106/// 107/// 1) An explicitly defined itinerary class with ItinClassDef set. 108/// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor. 109/// 110/// 2) An implied class with a list of SchedWrites and SchedReads that are 111/// defined in an instruction definition and which are common across all 112/// subtargets. ProcIndices contains 0 for any processor. 113/// 114/// 3) An implied class with a list of InstRW records that map instructions to 115/// SchedWrites and SchedReads per-processor. InstrClassMap should map the same 116/// instructions to this class. ProcIndices contains all the processors that 117/// provided InstrRW records for this class. ItinClassDef or Writes/Reads may 118/// still be defined for processors with no InstRW entry. 119/// 120/// 4) An inferred class represents a variant of another class that may be 121/// resolved at runtime. ProcIndices contains the set of processors that may 122/// require the class. ProcIndices are propagated through SchedClasses as 123/// variants are expanded. Multiple SchedClasses may be inferred from an 124/// itinerary class. Each inherits the processor index from the ItinRW record 125/// that mapped the itinerary class to the variant Writes or Reads. 126struct CodeGenSchedClass { 127 std::string Name; 128 Record *ItinClassDef; 129 130 IdxVec Writes; 131 IdxVec Reads; 132 // Sorted list of ProcIdx, where ProcIdx==0 implies any processor. 133 IdxVec ProcIndices; 134 135 std::vector<CodeGenSchedTransition> Transitions; 136 137 // InstRW records associated with this class. These records may refer to an 138 // Instruction no longer mapped to this class by InstrClassMap. These 139 // Instructions should be ignored by this class because they have been split 140 // off to join another inferred class. 141 RecVec InstRWs; 142 143 CodeGenSchedClass(): ItinClassDef(0) {} 144 CodeGenSchedClass(Record *rec): ItinClassDef(rec) { 145 Name = rec->getName(); 146 ProcIndices.push_back(0); 147 } 148 149#ifndef NDEBUG 150 void dump(const CodeGenSchedModels *SchedModels) const; 151#endif 152}; 153 154// Processor model. 155// 156// ModelName is a unique name used to name an instantiation of MCSchedModel. 157// 158// ModelDef is NULL for inferred Models. This happens when a processor defines 159// an itinerary but no machine model. If the processer defines neither a machine 160// model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has 161// the special "NoModel" field set to true. 162// 163// ItinsDef always points to a valid record definition, but may point to the 164// default NoItineraries. NoItineraries has an empty list of InstrItinData 165// records. 166// 167// ItinDefList orders this processor's InstrItinData records by SchedClass idx. 168struct CodeGenProcModel { 169 unsigned Index; 170 std::string ModelName; 171 Record *ModelDef; 172 Record *ItinsDef; 173 174 // Derived members... 175 176 // Array of InstrItinData records indexed by a CodeGenSchedClass index. 177 // This list is empty if the Processor has no value for Itineraries. 178 // Initialized by collectProcItins(). 179 RecVec ItinDefList; 180 181 // Map itinerary classes to per-operand resources. 182 // This list is empty if no ItinRW refers to this Processor. 183 RecVec ItinRWDefs; 184 185 // All read/write resources associated with this processor. 186 RecVec WriteResDefs; 187 RecVec ReadAdvanceDefs; 188 189 // Per-operand machine model resources associated with this processor. 190 RecVec ProcResourceDefs; 191 192 CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef, 193 Record *IDef) : 194 Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {} 195 196 bool hasInstrSchedModel() const { 197 return !WriteResDefs.empty() || !ItinRWDefs.empty(); 198 } 199 200 unsigned getProcResourceIdx(Record *PRDef) const; 201 202#ifndef NDEBUG 203 void dump() const; 204#endif 205}; 206 207/// Top level container for machine model data. 208class CodeGenSchedModels { 209 RecordKeeper &Records; 210 const CodeGenTarget &Target; 211 212 // Map dag expressions to Instruction lists. 213 SetTheory Sets; 214 215 // List of unique processor models. 216 std::vector<CodeGenProcModel> ProcModels; 217 218 // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index. 219 typedef DenseMap<Record*, unsigned> ProcModelMapTy; 220 ProcModelMapTy ProcModelMap; 221 222 // Per-operand SchedReadWrite types. 223 std::vector<CodeGenSchedRW> SchedWrites; 224 std::vector<CodeGenSchedRW> SchedReads; 225 226 // List of unique SchedClasses. 227 std::vector<CodeGenSchedClass> SchedClasses; 228 229 // Map SchedClass name to itinerary index. 230 // These are either explicit itinerary classes or classes implied by 231 // instruction definitions with SchedReadWrite lists. 232 StringMap<unsigned> SchedClassIdxMap; 233 234 // SchedClass indices 1 up to and including NumItineraryClasses identify 235 // itinerary classes that are explicitly used for this target's instruction 236 // definitions. NoItinerary always has index 0 regardless of whether it is 237 // explicitly referenced. 238 // 239 // Any implied SchedClass has an index greater than NumItineraryClasses. 240 unsigned NumItineraryClasses; 241 242 // Any inferred SchedClass has an index greater than NumInstrSchedClassses. 243 unsigned NumInstrSchedClasses; 244 245 // Map Instruction to SchedClass index. Only for Instructions mentioned in 246 // InstRW records. 247 typedef DenseMap<Record*, unsigned> InstClassMapTy; 248 InstClassMapTy InstrClassMap; 249 250public: 251 CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT); 252 253 Record *getModelOrItinDef(Record *ProcDef) const { 254 Record *ModelDef = ProcDef->getValueAsDef("SchedModel"); 255 Record *ItinsDef = ProcDef->getValueAsDef("ProcItin"); 256 if (!ItinsDef->getValueAsListOfDefs("IID").empty()) { 257 assert(ModelDef->getValueAsBit("NoModel") 258 && "Itineraries must be defined within SchedMachineModel"); 259 return ItinsDef; 260 } 261 return ModelDef; 262 } 263 264 const CodeGenProcModel &getModelForProc(Record *ProcDef) const { 265 Record *ModelDef = getModelOrItinDef(ProcDef); 266 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); 267 assert(I != ProcModelMap.end() && "missing machine model"); 268 return ProcModels[I->second]; 269 } 270 271 const CodeGenProcModel &getProcModel(Record *ModelDef) const { 272 ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); 273 assert(I != ProcModelMap.end() && "missing machine model"); 274 return ProcModels[I->second]; 275 } 276 277 // Iterate over the unique processor models. 278 typedef std::vector<CodeGenProcModel>::const_iterator ProcIter; 279 ProcIter procModelBegin() const { return ProcModels.begin(); } 280 ProcIter procModelEnd() const { return ProcModels.end(); } 281 282 // Get a SchedWrite from its index. 283 const CodeGenSchedRW &getSchedWrite(unsigned Idx) const { 284 assert(Idx < SchedWrites.size() && "bad SchedWrite index"); 285 assert(SchedWrites[Idx].isValid() && "invalid SchedWrite"); 286 return SchedWrites[Idx]; 287 } 288 // Get a SchedWrite from its index. 289 const CodeGenSchedRW &getSchedRead(unsigned Idx) const { 290 assert(Idx < SchedReads.size() && "bad SchedRead index"); 291 assert(SchedReads[Idx].isValid() && "invalid SchedRead"); 292 return SchedReads[Idx]; 293 } 294 295 const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const { 296 return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx); 297 } 298 CodeGenSchedRW &getSchedRW(Record *Def) { 299 bool IsRead = Def->isSubClassOf("SchedRead"); 300 unsigned Idx = getSchedRWIdx(Def, IsRead); 301 return const_cast<CodeGenSchedRW&>( 302 IsRead ? getSchedRead(Idx) : getSchedWrite(Idx)); 303 } 304 const CodeGenSchedRW &getSchedRW(Record*Def) const { 305 return const_cast<CodeGenSchedModels&>(*this).getSchedRW(Def); 306 } 307 308 unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const; 309 310 // Return true if the given write record is referenced by a ReadAdvance. 311 bool hasReadOfWrite(Record *WriteDef) const; 312 313 // Check if any instructions are assigned to an explicit itinerary class other 314 // than NoItinerary. 315 bool hasItineraryClasses() const { return NumItineraryClasses > 0; } 316 317 // Return the number of itinerary classes in use by this target's instruction 318 // descriptions, not including "NoItinerary". 319 unsigned numItineraryClasses() const { 320 return NumItineraryClasses; 321 } 322 323 // Get a SchedClass from its index. 324 CodeGenSchedClass &getSchedClass(unsigned Idx) { 325 assert(Idx < SchedClasses.size() && "bad SchedClass index"); 326 return SchedClasses[Idx]; 327 } 328 const CodeGenSchedClass &getSchedClass(unsigned Idx) const { 329 assert(Idx < SchedClasses.size() && "bad SchedClass index"); 330 return SchedClasses[Idx]; 331 } 332 333 // Get the SchedClass index for an instruction. Instructions with no 334 // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0 335 // for NoItinerary. 336 unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const; 337 338 unsigned getSchedClassIdx(const RecVec &RWDefs) const; 339 340 unsigned getSchedClassIdxForItin(const Record *ItinDef) { 341 return SchedClassIdxMap[ItinDef->getName()]; 342 } 343 344 typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter; 345 SchedClassIter schedClassBegin() const { return SchedClasses.begin(); } 346 SchedClassIter schedClassEnd() const { return SchedClasses.end(); } 347 348 void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const; 349 void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const; 350 void expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, bool IsRead) const; 351 void expandRWSeqForProc(unsigned RWIdx, IdxVec &RWSeq, bool IsRead, 352 const CodeGenProcModel &ProcModel) const; 353 354 unsigned addSchedClass(const IdxVec &OperWrites, const IdxVec &OperReads, 355 const IdxVec &ProcIndices); 356 357 unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead); 358 359 unsigned findSchedClassIdx(const IdxVec &Writes, const IdxVec &Reads) const; 360 361 Record *findProcResUnits(Record *ProcResKind, 362 const CodeGenProcModel &PM) const; 363 364private: 365 void collectProcModels(); 366 367 // Initialize a new processor model if it is unique. 368 void addProcModel(Record *ProcDef); 369 370 void collectSchedRW(); 371 372 std::string genRWName(const IdxVec& Seq, bool IsRead); 373 unsigned findRWForSequence(const IdxVec &Seq, bool IsRead); 374 375 void collectSchedClasses(); 376 377 std::string createSchedClassName(const IdxVec &OperWrites, 378 const IdxVec &OperReads); 379 std::string createSchedClassName(const RecVec &InstDefs); 380 void createInstRWClass(Record *InstRWDef); 381 382 void collectProcItins(); 383 384 void collectProcItinRW(); 385 386 void inferSchedClasses(); 387 388 void inferFromRW(const IdxVec &OperWrites, const IdxVec &OperReads, 389 unsigned FromClassIdx, const IdxVec &ProcIndices); 390 void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx); 391 void inferFromInstRWs(unsigned SCIdx); 392 393 void collectProcResources(); 394 395 void collectItinProcResources(Record *ItinClassDef); 396 397 void collectRWResources(unsigned RWIdx, bool IsRead, 398 const IdxVec &ProcIndices); 399 400 void collectRWResources(const IdxVec &Writes, const IdxVec &Reads, 401 const IdxVec &ProcIndices); 402 403 void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM); 404 405 void addWriteRes(Record *ProcWriteResDef, unsigned PIdx); 406 407 void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx); 408}; 409 410} // namespace llvm 411 412#endif 413