1239310Sdim//===- CodeGenSchedule.h - Scheduling Machine Models ------------*- C++ -*-===// 2239310Sdim// 3239310Sdim// The LLVM Compiler Infrastructure 4239310Sdim// 5239310Sdim// This file is distributed under the University of Illinois Open Source 6239310Sdim// License. See LICENSE.TXT for details. 7239310Sdim// 8239310Sdim//===----------------------------------------------------------------------===// 9239310Sdim// 10239310Sdim// This file defines structures to encapsulate the machine model as decribed in 11239310Sdim// the target description. 12239310Sdim// 13239310Sdim//===----------------------------------------------------------------------===// 14239310Sdim 15239310Sdim#ifndef CODEGEN_SCHEDULE_H 16239310Sdim#define CODEGEN_SCHEDULE_H 17239310Sdim 18243830Sdim#include "SetTheory.h" 19239310Sdim#include "llvm/ADT/DenseMap.h" 20239310Sdim#include "llvm/ADT/StringMap.h" 21249423Sdim#include "llvm/Support/ErrorHandling.h" 22249423Sdim#include "llvm/TableGen/Record.h" 23239310Sdim 24239310Sdimnamespace llvm { 25239310Sdim 26239310Sdimclass CodeGenTarget; 27243830Sdimclass CodeGenSchedModels; 28243830Sdimclass CodeGenInstruction; 29239310Sdim 30243830Sdimtypedef std::vector<Record*> RecVec; 31243830Sdimtypedef std::vector<Record*>::const_iterator RecIter; 32243830Sdim 33243830Sdimtypedef std::vector<unsigned> IdxVec; 34243830Sdimtypedef std::vector<unsigned>::const_iterator IdxIter; 35243830Sdim 36243830Sdimvoid splitSchedReadWrites(const RecVec &RWDefs, 37243830Sdim RecVec &WriteDefs, RecVec &ReadDefs); 38243830Sdim 39243830Sdim/// We have two kinds of SchedReadWrites. Explicitly defined and inferred 40243830Sdim/// sequences. TheDef is nonnull for explicit SchedWrites, but Sequence may or 41243830Sdim/// may not be empty. TheDef is null for inferred sequences, and Sequence must 42243830Sdim/// be nonempty. 43243830Sdim/// 44243830Sdim/// IsVariadic controls whether the variants are expanded into multiple operands 45243830Sdim/// or a sequence of writes on one operand. 46243830Sdimstruct CodeGenSchedRW { 47243830Sdim unsigned Index; 48243830Sdim std::string Name; 49243830Sdim Record *TheDef; 50243830Sdim bool IsRead; 51243830Sdim bool IsAlias; 52243830Sdim bool HasVariants; 53243830Sdim bool IsVariadic; 54243830Sdim bool IsSequence; 55243830Sdim IdxVec Sequence; 56243830Sdim RecVec Aliases; 57243830Sdim 58249423Sdim CodeGenSchedRW() 59249423Sdim : Index(0), TheDef(0), IsRead(false), IsAlias(false), 60249423Sdim HasVariants(false), IsVariadic(false), IsSequence(false) {} 61249423Sdim CodeGenSchedRW(unsigned Idx, Record *Def) 62249423Sdim : Index(Idx), TheDef(Def), IsAlias(false), IsVariadic(false) { 63243830Sdim Name = Def->getName(); 64243830Sdim IsRead = Def->isSubClassOf("SchedRead"); 65243830Sdim HasVariants = Def->isSubClassOf("SchedVariant"); 66243830Sdim if (HasVariants) 67243830Sdim IsVariadic = Def->getValueAsBit("Variadic"); 68243830Sdim 69243830Sdim // Read records don't currently have sequences, but it can be easily 70243830Sdim // added. Note that implicit Reads (from ReadVariant) may have a Sequence 71243830Sdim // (but no record). 72243830Sdim IsSequence = Def->isSubClassOf("WriteSequence"); 73243830Sdim } 74243830Sdim 75243830Sdim CodeGenSchedRW(unsigned Idx, bool Read, const IdxVec &Seq, 76249423Sdim const std::string &Name) 77249423Sdim : Index(Idx), Name(Name), TheDef(0), IsRead(Read), IsAlias(false), 78249423Sdim HasVariants(false), IsVariadic(false), IsSequence(true), Sequence(Seq) { 79243830Sdim assert(Sequence.size() > 1 && "implied sequence needs >1 RWs"); 80243830Sdim } 81243830Sdim 82243830Sdim bool isValid() const { 83243830Sdim assert((!HasVariants || TheDef) && "Variant write needs record def"); 84243830Sdim assert((!IsVariadic || HasVariants) && "Variadic write needs variants"); 85243830Sdim assert((!IsSequence || !HasVariants) && "Sequence can't have variant"); 86243830Sdim assert((!IsSequence || !Sequence.empty()) && "Sequence should be nonempty"); 87243830Sdim assert((!IsAlias || Aliases.empty()) && "Alias cannot have aliases"); 88243830Sdim return TheDef || !Sequence.empty(); 89243830Sdim } 90243830Sdim 91243830Sdim#ifndef NDEBUG 92243830Sdim void dump() const; 93243830Sdim#endif 94243830Sdim}; 95243830Sdim 96243830Sdim/// Represent a transition between SchedClasses induced by SchedVariant. 97243830Sdimstruct CodeGenSchedTransition { 98243830Sdim unsigned ToClassIdx; 99243830Sdim IdxVec ProcIndices; 100243830Sdim RecVec PredTerm; 101243830Sdim}; 102243830Sdim 103243830Sdim/// Scheduling class. 104243830Sdim/// 105243830Sdim/// Each instruction description will be mapped to a scheduling class. There are 106243830Sdim/// four types of classes: 107243830Sdim/// 108243830Sdim/// 1) An explicitly defined itinerary class with ItinClassDef set. 109243830Sdim/// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor. 110243830Sdim/// 111243830Sdim/// 2) An implied class with a list of SchedWrites and SchedReads that are 112243830Sdim/// defined in an instruction definition and which are common across all 113243830Sdim/// subtargets. ProcIndices contains 0 for any processor. 114243830Sdim/// 115243830Sdim/// 3) An implied class with a list of InstRW records that map instructions to 116243830Sdim/// SchedWrites and SchedReads per-processor. InstrClassMap should map the same 117243830Sdim/// instructions to this class. ProcIndices contains all the processors that 118243830Sdim/// provided InstrRW records for this class. ItinClassDef or Writes/Reads may 119243830Sdim/// still be defined for processors with no InstRW entry. 120243830Sdim/// 121243830Sdim/// 4) An inferred class represents a variant of another class that may be 122243830Sdim/// resolved at runtime. ProcIndices contains the set of processors that may 123243830Sdim/// require the class. ProcIndices are propagated through SchedClasses as 124243830Sdim/// variants are expanded. Multiple SchedClasses may be inferred from an 125243830Sdim/// itinerary class. Each inherits the processor index from the ItinRW record 126243830Sdim/// that mapped the itinerary class to the variant Writes or Reads. 127239310Sdimstruct CodeGenSchedClass { 128249423Sdim unsigned Index; 129239310Sdim std::string Name; 130239310Sdim Record *ItinClassDef; 131239310Sdim 132243830Sdim IdxVec Writes; 133243830Sdim IdxVec Reads; 134243830Sdim // Sorted list of ProcIdx, where ProcIdx==0 implies any processor. 135243830Sdim IdxVec ProcIndices; 136243830Sdim 137243830Sdim std::vector<CodeGenSchedTransition> Transitions; 138243830Sdim 139243830Sdim // InstRW records associated with this class. These records may refer to an 140243830Sdim // Instruction no longer mapped to this class by InstrClassMap. These 141243830Sdim // Instructions should be ignored by this class because they have been split 142243830Sdim // off to join another inferred class. 143243830Sdim RecVec InstRWs; 144243830Sdim 145249423Sdim CodeGenSchedClass(): Index(0), ItinClassDef(0) {} 146249423Sdim 147249423Sdim bool isKeyEqual(Record *IC, const IdxVec &W, const IdxVec &R) { 148249423Sdim return ItinClassDef == IC && Writes == W && Reads == R; 149239310Sdim } 150243830Sdim 151249423Sdim // Is this class generated from a variants if existing classes? Instructions 152249423Sdim // are never mapped directly to inferred scheduling classes. 153249423Sdim bool isInferred() const { return !ItinClassDef; } 154249423Sdim 155243830Sdim#ifndef NDEBUG 156243830Sdim void dump(const CodeGenSchedModels *SchedModels) const; 157243830Sdim#endif 158239310Sdim}; 159239310Sdim 160239310Sdim// Processor model. 161239310Sdim// 162239310Sdim// ModelName is a unique name used to name an instantiation of MCSchedModel. 163239310Sdim// 164239310Sdim// ModelDef is NULL for inferred Models. This happens when a processor defines 165239310Sdim// an itinerary but no machine model. If the processer defines neither a machine 166239310Sdim// model nor itinerary, then ModelDef remains pointing to NoModel. NoModel has 167239310Sdim// the special "NoModel" field set to true. 168239310Sdim// 169239310Sdim// ItinsDef always points to a valid record definition, but may point to the 170239310Sdim// default NoItineraries. NoItineraries has an empty list of InstrItinData 171239310Sdim// records. 172239310Sdim// 173239310Sdim// ItinDefList orders this processor's InstrItinData records by SchedClass idx. 174239310Sdimstruct CodeGenProcModel { 175243830Sdim unsigned Index; 176239310Sdim std::string ModelName; 177239310Sdim Record *ModelDef; 178239310Sdim Record *ItinsDef; 179239310Sdim 180243830Sdim // Derived members... 181239310Sdim 182243830Sdim // Array of InstrItinData records indexed by a CodeGenSchedClass index. 183243830Sdim // This list is empty if the Processor has no value for Itineraries. 184243830Sdim // Initialized by collectProcItins(). 185243830Sdim RecVec ItinDefList; 186243830Sdim 187243830Sdim // Map itinerary classes to per-operand resources. 188243830Sdim // This list is empty if no ItinRW refers to this Processor. 189243830Sdim RecVec ItinRWDefs; 190243830Sdim 191243830Sdim // All read/write resources associated with this processor. 192243830Sdim RecVec WriteResDefs; 193243830Sdim RecVec ReadAdvanceDefs; 194243830Sdim 195243830Sdim // Per-operand machine model resources associated with this processor. 196243830Sdim RecVec ProcResourceDefs; 197249423Sdim RecVec ProcResGroupDefs; 198243830Sdim 199243830Sdim CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef, 200243830Sdim Record *IDef) : 201243830Sdim Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {} 202243830Sdim 203249423Sdim bool hasItineraries() const { 204249423Sdim return !ItinsDef->getValueAsListOfDefs("IID").empty(); 205249423Sdim } 206249423Sdim 207243830Sdim bool hasInstrSchedModel() const { 208243830Sdim return !WriteResDefs.empty() || !ItinRWDefs.empty(); 209243830Sdim } 210243830Sdim 211243830Sdim unsigned getProcResourceIdx(Record *PRDef) const; 212243830Sdim 213243830Sdim#ifndef NDEBUG 214243830Sdim void dump() const; 215243830Sdim#endif 216239310Sdim}; 217239310Sdim 218243830Sdim/// Top level container for machine model data. 219239310Sdimclass CodeGenSchedModels { 220239310Sdim RecordKeeper &Records; 221239310Sdim const CodeGenTarget &Target; 222239310Sdim 223243830Sdim // Map dag expressions to Instruction lists. 224243830Sdim SetTheory Sets; 225243830Sdim 226243830Sdim // List of unique processor models. 227243830Sdim std::vector<CodeGenProcModel> ProcModels; 228243830Sdim 229243830Sdim // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index. 230243830Sdim typedef DenseMap<Record*, unsigned> ProcModelMapTy; 231243830Sdim ProcModelMapTy ProcModelMap; 232243830Sdim 233243830Sdim // Per-operand SchedReadWrite types. 234243830Sdim std::vector<CodeGenSchedRW> SchedWrites; 235243830Sdim std::vector<CodeGenSchedRW> SchedReads; 236243830Sdim 237239310Sdim // List of unique SchedClasses. 238239310Sdim std::vector<CodeGenSchedClass> SchedClasses; 239239310Sdim 240243830Sdim // Any inferred SchedClass has an index greater than NumInstrSchedClassses. 241243830Sdim unsigned NumInstrSchedClasses; 242239310Sdim 243249423Sdim // Map each instruction to its unique SchedClass index considering the 244249423Sdim // combination of it's itinerary class, SchedRW list, and InstRW records. 245243830Sdim typedef DenseMap<Record*, unsigned> InstClassMapTy; 246243830Sdim InstClassMapTy InstrClassMap; 247239310Sdim 248239310Sdimpublic: 249239310Sdim CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT); 250239310Sdim 251243830Sdim Record *getModelOrItinDef(Record *ProcDef) const { 252243830Sdim Record *ModelDef = ProcDef->getValueAsDef("SchedModel"); 253243830Sdim Record *ItinsDef = ProcDef->getValueAsDef("ProcItin"); 254243830Sdim if (!ItinsDef->getValueAsListOfDefs("IID").empty()) { 255243830Sdim assert(ModelDef->getValueAsBit("NoModel") 256243830Sdim && "Itineraries must be defined within SchedMachineModel"); 257243830Sdim return ItinsDef; 258243830Sdim } 259243830Sdim return ModelDef; 260243830Sdim } 261243830Sdim 262243830Sdim const CodeGenProcModel &getModelForProc(Record *ProcDef) const { 263243830Sdim Record *ModelDef = getModelOrItinDef(ProcDef); 264243830Sdim ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); 265243830Sdim assert(I != ProcModelMap.end() && "missing machine model"); 266243830Sdim return ProcModels[I->second]; 267243830Sdim } 268243830Sdim 269263508Sdim CodeGenProcModel &getProcModel(Record *ModelDef) { 270243830Sdim ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); 271243830Sdim assert(I != ProcModelMap.end() && "missing machine model"); 272243830Sdim return ProcModels[I->second]; 273243830Sdim } 274263508Sdim const CodeGenProcModel &getProcModel(Record *ModelDef) const { 275263508Sdim return const_cast<CodeGenSchedModels*>(this)->getProcModel(ModelDef); 276263508Sdim } 277243830Sdim 278243830Sdim // Iterate over the unique processor models. 279243830Sdim typedef std::vector<CodeGenProcModel>::const_iterator ProcIter; 280243830Sdim ProcIter procModelBegin() const { return ProcModels.begin(); } 281243830Sdim ProcIter procModelEnd() const { return ProcModels.end(); } 282243830Sdim 283249423Sdim // Return true if any processors have itineraries. 284249423Sdim bool hasItineraries() const; 285249423Sdim 286243830Sdim // Get a SchedWrite from its index. 287243830Sdim const CodeGenSchedRW &getSchedWrite(unsigned Idx) const { 288243830Sdim assert(Idx < SchedWrites.size() && "bad SchedWrite index"); 289243830Sdim assert(SchedWrites[Idx].isValid() && "invalid SchedWrite"); 290243830Sdim return SchedWrites[Idx]; 291243830Sdim } 292243830Sdim // Get a SchedWrite from its index. 293243830Sdim const CodeGenSchedRW &getSchedRead(unsigned Idx) const { 294243830Sdim assert(Idx < SchedReads.size() && "bad SchedRead index"); 295243830Sdim assert(SchedReads[Idx].isValid() && "invalid SchedRead"); 296243830Sdim return SchedReads[Idx]; 297243830Sdim } 298243830Sdim 299243830Sdim const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const { 300243830Sdim return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx); 301243830Sdim } 302243830Sdim CodeGenSchedRW &getSchedRW(Record *Def) { 303243830Sdim bool IsRead = Def->isSubClassOf("SchedRead"); 304243830Sdim unsigned Idx = getSchedRWIdx(Def, IsRead); 305243830Sdim return const_cast<CodeGenSchedRW&>( 306243830Sdim IsRead ? getSchedRead(Idx) : getSchedWrite(Idx)); 307243830Sdim } 308243830Sdim const CodeGenSchedRW &getSchedRW(Record*Def) const { 309243830Sdim return const_cast<CodeGenSchedModels&>(*this).getSchedRW(Def); 310243830Sdim } 311243830Sdim 312243830Sdim unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const; 313243830Sdim 314243830Sdim // Return true if the given write record is referenced by a ReadAdvance. 315243830Sdim bool hasReadOfWrite(Record *WriteDef) const; 316243830Sdim 317239310Sdim // Get a SchedClass from its index. 318243830Sdim CodeGenSchedClass &getSchedClass(unsigned Idx) { 319239310Sdim assert(Idx < SchedClasses.size() && "bad SchedClass index"); 320239310Sdim return SchedClasses[Idx]; 321239310Sdim } 322243830Sdim const CodeGenSchedClass &getSchedClass(unsigned Idx) const { 323243830Sdim assert(Idx < SchedClasses.size() && "bad SchedClass index"); 324243830Sdim return SchedClasses[Idx]; 325239310Sdim } 326239310Sdim 327243830Sdim // Get the SchedClass index for an instruction. Instructions with no 328243830Sdim // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0 329243830Sdim // for NoItinerary. 330243830Sdim unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const; 331239310Sdim 332243830Sdim typedef std::vector<CodeGenSchedClass>::const_iterator SchedClassIter; 333243830Sdim SchedClassIter schedClassBegin() const { return SchedClasses.begin(); } 334243830Sdim SchedClassIter schedClassEnd() const { return SchedClasses.end(); } 335239310Sdim 336249423Sdim unsigned numInstrSchedClasses() const { return NumInstrSchedClasses; } 337249423Sdim 338243830Sdim void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const; 339243830Sdim void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const; 340243830Sdim void expandRWSequence(unsigned RWIdx, IdxVec &RWSeq, bool IsRead) const; 341243830Sdim void expandRWSeqForProc(unsigned RWIdx, IdxVec &RWSeq, bool IsRead, 342243830Sdim const CodeGenProcModel &ProcModel) const; 343243830Sdim 344249423Sdim unsigned addSchedClass(Record *ItinDef, const IdxVec &OperWrites, 345249423Sdim const IdxVec &OperReads, const IdxVec &ProcIndices); 346243830Sdim 347243830Sdim unsigned findOrInsertRW(ArrayRef<unsigned> Seq, bool IsRead); 348243830Sdim 349249423Sdim unsigned findSchedClassIdx(Record *ItinClassDef, 350249423Sdim const IdxVec &Writes, 351249423Sdim const IdxVec &Reads) const; 352243830Sdim 353243830Sdim Record *findProcResUnits(Record *ProcResKind, 354243830Sdim const CodeGenProcModel &PM) const; 355243830Sdim 356239310Sdimprivate: 357243830Sdim void collectProcModels(); 358239310Sdim 359239310Sdim // Initialize a new processor model if it is unique. 360239310Sdim void addProcModel(Record *ProcDef); 361239310Sdim 362243830Sdim void collectSchedRW(); 363243830Sdim 364243830Sdim std::string genRWName(const IdxVec& Seq, bool IsRead); 365243830Sdim unsigned findRWForSequence(const IdxVec &Seq, bool IsRead); 366243830Sdim 367243830Sdim void collectSchedClasses(); 368243830Sdim 369249423Sdim std::string createSchedClassName(Record *ItinClassDef, 370249423Sdim const IdxVec &OperWrites, 371243830Sdim const IdxVec &OperReads); 372243830Sdim std::string createSchedClassName(const RecVec &InstDefs); 373243830Sdim void createInstRWClass(Record *InstRWDef); 374243830Sdim 375243830Sdim void collectProcItins(); 376243830Sdim 377243830Sdim void collectProcItinRW(); 378243830Sdim 379243830Sdim void inferSchedClasses(); 380243830Sdim 381243830Sdim void inferFromRW(const IdxVec &OperWrites, const IdxVec &OperReads, 382243830Sdim unsigned FromClassIdx, const IdxVec &ProcIndices); 383243830Sdim void inferFromItinClass(Record *ItinClassDef, unsigned FromClassIdx); 384243830Sdim void inferFromInstRWs(unsigned SCIdx); 385243830Sdim 386251662Sdim bool hasSuperGroup(RecVec &SubUnits, CodeGenProcModel &PM); 387251662Sdim void verifyProcResourceGroups(CodeGenProcModel &PM); 388251662Sdim 389243830Sdim void collectProcResources(); 390243830Sdim 391243830Sdim void collectItinProcResources(Record *ItinClassDef); 392243830Sdim 393243830Sdim void collectRWResources(unsigned RWIdx, bool IsRead, 394243830Sdim const IdxVec &ProcIndices); 395243830Sdim 396243830Sdim void collectRWResources(const IdxVec &Writes, const IdxVec &Reads, 397243830Sdim const IdxVec &ProcIndices); 398243830Sdim 399243830Sdim void addProcResource(Record *ProcResourceKind, CodeGenProcModel &PM); 400243830Sdim 401243830Sdim void addWriteRes(Record *ProcWriteResDef, unsigned PIdx); 402243830Sdim 403243830Sdim void addReadAdvance(Record *ProcReadAdvanceDef, unsigned PIdx); 404239310Sdim}; 405239310Sdim 406239310Sdim} // namespace llvm 407239310Sdim 408239310Sdim#endif 409