From 48605c340614fc1fb2ae1d975fc565a4188182e0 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Sat, 15 Sep 2012 00:19:57 +0000 Subject: [PATCH] TableGen subtarget parser. Handle new machine model. Collect SchedClasses and SchedRW types from the subtarget defs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163951 91177308-0d34-0410-b5e6-96231b3b80d8 --- utils/TableGen/CodeGenSchedule.cpp | 663 +++++++++++++++++++++++++++++++----- utils/TableGen/CodeGenSchedule.h | 284 ++++++++++++--- utils/TableGen/SubtargetEmitter.cpp | 6 +- 3 files changed, 816 insertions(+), 137 deletions(-) diff --git a/utils/TableGen/CodeGenSchedule.cpp b/utils/TableGen/CodeGenSchedule.cpp index f57fd182eaf..d9095d74806 100644 --- a/utils/TableGen/CodeGenSchedule.cpp +++ b/utils/TableGen/CodeGenSchedule.cpp @@ -16,41 +16,299 @@ #include "CodeGenSchedule.h" #include "CodeGenTarget.h" +#include "llvm/TableGen/Error.h" #include "llvm/Support/Debug.h" using namespace llvm; -// CodeGenModels ctor interprets machine model records and populates maps. +#ifndef NDEBUG +static void dumpIdxVec(const IdxVec &V) { + for (unsigned i = 0, e = V.size(); i < e; ++i) { + dbgs() << V[i] << ", "; + } +} +#endif + +/// CodeGenModels ctor interprets machine model records and populates maps. CodeGenSchedModels::CodeGenSchedModels(RecordKeeper &RK, const CodeGenTarget &TGT): - Records(RK), Target(TGT), NumItineraryClasses(0), HasProcItineraries(false) { + Records(RK), Target(TGT), NumItineraryClasses(0) { + + // Instantiate a CodeGenProcModel for each SchedMachineModel with the values + // that are explicitly referenced in tablegen records. Resources associated + // with each processor will be derived later. Populate ProcModelMap with the + // CodeGenProcModel instances. + collectProcModels(); + + // Instantiate a CodeGenSchedRW for each SchedReadWrite record explicitly + // defined, and populate SchedReads and SchedWrites vectors. Implicit + // SchedReadWrites that represent sequences derived from expanded variant will + // be inferred later. + collectSchedRW(); + + // Instantiate a CodeGenSchedClass for each unique SchedRW signature directly + // required by an instruction definition, and populate SchedClassIdxMap. Set + // NumItineraryClasses to the number of explicit itinerary classes referenced + // by instructions. Set NumInstrSchedClasses to the number of itinerary + // classes plus any classes implied by instructions that derive from class + // Sched and provide SchedRW list. This does not infer any new classes from + // SchedVariant. + collectSchedClasses(); + + // Find instruction itineraries for each processor. Sort and populate + // CodeGenProcMode::ItinDefList. (Cycle-to-cycle itineraries). This requires + // all itinerary classes to be discovered. + collectProcItins(); + + // Find ItinRW records for each processor and itinerary class. + // (For per-operand resources mapped to itinerary classes). + collectProcItinRW(); +} + +/// Gather all processor models. +void CodeGenSchedModels::collectProcModels() { + RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor"); + std::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName()); + + // Reserve space because we can. Reallocation would be ok. + ProcModels.reserve(ProcRecords.size()+1); + + // Use idx=0 for NoModel/NoItineraries. + Record *NoModelDef = Records.getDef("NoSchedModel"); + Record *NoItinsDef = Records.getDef("NoItineraries"); + ProcModels.push_back(CodeGenProcModel(0, "NoSchedModel", + NoModelDef, NoItinsDef)); + ProcModelMap[NoModelDef] = 0; + + // For each processor, find a unique machine model. + for (unsigned i = 0, N = ProcRecords.size(); i < N; ++i) + addProcModel(ProcRecords[i]); +} + +/// Get a unique processor model based on the defined MachineModel and +/// ProcessorItineraries. +void CodeGenSchedModels::addProcModel(Record *ProcDef) { + Record *ModelKey = getModelOrItinDef(ProcDef); + if (!ProcModelMap.insert(std::make_pair(ModelKey, ProcModels.size())).second) + return; + + std::string Name = ModelKey->getName(); + if (ModelKey->isSubClassOf("SchedMachineModel")) { + Record *ItinsDef = ModelKey->getValueAsDef("Itineraries"); + ProcModels.push_back( + CodeGenProcModel(ProcModels.size(), Name, ModelKey, ItinsDef)); + } + else { + // An itinerary is defined without a machine model. Infer a new model. + if (!ModelKey->getValueAsListOfDefs("IID").empty()) + Name = Name + "Model"; + ProcModels.push_back( + CodeGenProcModel(ProcModels.size(), Name, + ProcDef->getValueAsDef("SchedModel"), ModelKey)); + } + DEBUG(ProcModels.back().dump()); +} + +// Recursively find all reachable SchedReadWrite records. +static void scanSchedRW(Record *RWDef, RecVec &RWDefs, + SmallPtrSet &RWSet) { + if (!RWSet.insert(RWDef)) + return; + RWDefs.push_back(RWDef); + // Reads don't current have sequence records, but it can be added later. + if (RWDef->isSubClassOf("WriteSequence")) { + RecVec Seq = RWDef->getValueAsListOfDefs("Writes"); + for (RecIter I = Seq.begin(), E = Seq.end(); I != E; ++I) + scanSchedRW(*I, RWDefs, RWSet); + } + else if (RWDef->isSubClassOf("SchedVariant")) { + // Visit each variant (guarded by a different predicate). + RecVec Vars = RWDef->getValueAsListOfDefs("Variants"); + for (RecIter VI = Vars.begin(), VE = Vars.end(); VI != VE; ++VI) { + // Visit each RW in the sequence selected by the current variant. + RecVec Selected = (*VI)->getValueAsListOfDefs("Selected"); + for (RecIter I = Selected.begin(), E = Selected.end(); I != E; ++I) + scanSchedRW(*I, RWDefs, RWSet); + } + } +} + +// Collect and sort all SchedReadWrites reachable via tablegen records. +// More may be inferred later when inferring new SchedClasses from variants. +void CodeGenSchedModels::collectSchedRW() { + // Reserve idx=0 for invalid writes/reads. + SchedWrites.resize(1); + SchedReads.resize(1); - // Populate SchedClassIdxMap and set NumItineraryClasses. - CollectSchedClasses(); + SmallPtrSet RWSet; - // Populate ProcModelMap. - CollectProcModels(); + // Find all SchedReadWrites referenced by instruction defs. + RecVec SWDefs, SRDefs; + for (CodeGenTarget::inst_iterator I = Target.inst_begin(), + E = Target.inst_end(); I != E; ++I) { + Record *SchedDef = (*I)->TheDef; + if (!SchedDef->isSubClassOf("Sched")) + continue; + RecVec RWs = SchedDef->getValueAsListOfDefs("SchedRW"); + for (RecIter RWI = RWs.begin(), RWE = RWs.end(); RWI != RWE; ++RWI) { + if ((*RWI)->isSubClassOf("SchedWrite")) + scanSchedRW(*RWI, SWDefs, RWSet); + else { + assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); + scanSchedRW(*RWI, SRDefs, RWSet); + } + } + } + // Find all ReadWrites referenced by InstRW. + RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); + for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) { + // For all OperandReadWrites. + RecVec RWDefs = (*OI)->getValueAsListOfDefs("OperandReadWrites"); + for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); + RWI != RWE; ++RWI) { + if ((*RWI)->isSubClassOf("SchedWrite")) + scanSchedRW(*RWI, SWDefs, RWSet); + else { + assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); + scanSchedRW(*RWI, SRDefs, RWSet); + } + } + } + // Find all ReadWrites referenced by ItinRW. + RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); + for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) { + // For all OperandReadWrites. + RecVec RWDefs = (*II)->getValueAsListOfDefs("OperandReadWrites"); + for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); + RWI != RWE; ++RWI) { + if ((*RWI)->isSubClassOf("SchedWrite")) + scanSchedRW(*RWI, SWDefs, RWSet); + else { + assert((*RWI)->isSubClassOf("SchedRead") && "Unknown SchedReadWrite"); + scanSchedRW(*RWI, SRDefs, RWSet); + } + } + } + // Sort and add the SchedReadWrites directly referenced by instructions or + // itinerary resources. Index reads and writes in separate domains. + std::sort(SWDefs.begin(), SWDefs.end(), LessRecord()); + for (RecIter SWI = SWDefs.begin(), SWE = SWDefs.end(); SWI != SWE; ++SWI) { + assert(!getSchedRWIdx(*SWI, /*IsRead=*/false) && "duplicate SchedWrite"); + SchedWrites.push_back(CodeGenSchedRW(*SWI)); + } + std::sort(SRDefs.begin(), SRDefs.end(), LessRecord()); + for (RecIter SRI = SRDefs.begin(), SRE = SRDefs.end(); SRI != SRE; ++SRI) { + assert(!getSchedRWIdx(*SRI, /*IsRead-*/true) && "duplicate SchedWrite"); + SchedReads.push_back(CodeGenSchedRW(*SRI)); + } + // Initialize WriteSequence vectors. + for (std::vector::iterator WI = SchedWrites.begin(), + WE = SchedWrites.end(); WI != WE; ++WI) { + if (!WI->IsSequence) + continue; + findRWs(WI->TheDef->getValueAsListOfDefs("Writes"), WI->Sequence, + /*IsRead=*/false); + } + DEBUG( + for (unsigned WIdx = 0, WEnd = SchedWrites.size(); WIdx != WEnd; ++WIdx) { + dbgs() << WIdx << ": "; + SchedWrites[WIdx].dump(); + dbgs() << '\n'; + } + for (unsigned RIdx = 0, REnd = SchedReads.size(); RIdx != REnd; ++RIdx) { + dbgs() << RIdx << ": "; + SchedReads[RIdx].dump(); + dbgs() << '\n'; + } + RecVec RWDefs = Records.getAllDerivedDefinitions("SchedReadWrite"); + for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); + RI != RE; ++RI) { + if (!getSchedRWIdx(*RI, (*RI)->isSubClassOf("SchedRead"))) { + const std::string &Name = (*RI)->getName(); + if (Name != "NoWrite" && Name != "ReadDefault") + dbgs() << "Unused SchedReadWrite " << (*RI)->getName() << '\n'; + } + }); +} + +/// Compute a SchedWrite name from a sequence of writes. +std::string CodeGenSchedModels::genRWName(const IdxVec& Seq, bool IsRead) { + std::string Name("("); + for (IdxIter I = Seq.begin(), E = Seq.end(); I != E; ++I) { + if (I != Seq.begin()) + Name += '_'; + Name += getSchedRW(*I, IsRead).Name; + } + Name += ')'; + return Name; +} + +unsigned CodeGenSchedModels::getSchedRWIdx(Record *Def, bool IsRead, + unsigned After) const { + const std::vector &RWVec = IsRead ? SchedReads : SchedWrites; + assert(After < RWVec.size() && "start position out of bounds"); + for (std::vector::const_iterator I = RWVec.begin() + After, + E = RWVec.end(); I != E; ++I) { + if (I->TheDef == Def) + return I - RWVec.begin(); + } + return 0; +} + +namespace llvm { +void splitSchedReadWrites(const RecVec &RWDefs, + RecVec &WriteDefs, RecVec &ReadDefs) { + for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); RWI != RWE; ++RWI) { + if ((*RWI)->isSubClassOf("SchedWrite")) + WriteDefs.push_back(*RWI); + else { + assert((*RWI)->isSubClassOf("SchedRead") && "unknown SchedReadWrite"); + ReadDefs.push_back(*RWI); + } + } +} +} // namespace llvm + +// Split the SchedReadWrites defs and call findRWs for each list. +void CodeGenSchedModels::findRWs(const RecVec &RWDefs, + IdxVec &Writes, IdxVec &Reads) const { + RecVec WriteDefs; + RecVec ReadDefs; + splitSchedReadWrites(RWDefs, WriteDefs, ReadDefs); + findRWs(WriteDefs, Writes, false); + findRWs(ReadDefs, Reads, true); +} + +// Call getSchedRWIdx for all elements in a sequence of SchedRW defs. +void CodeGenSchedModels::findRWs(const RecVec &RWDefs, IdxVec &RWs, + bool IsRead) const { + for (RecIter RI = RWDefs.begin(), RE = RWDefs.end(); RI != RE; ++RI) { + unsigned Idx = getSchedRWIdx(*RI, IsRead); + assert(Idx && "failed to collect SchedReadWrite"); + RWs.push_back(Idx); + } } -// Visit all the instruction definitions for this target to gather and enumerate -// the itinerary classes. These are the explicitly specified SchedClasses. More -// SchedClasses may be inferred. -void CodeGenSchedModels::CollectSchedClasses() { +/// Visit all the instruction definitions for this target to gather and +/// enumerate the itinerary classes. These are the explicitly specified +/// SchedClasses. More SchedClasses may be inferred. +void CodeGenSchedModels::collectSchedClasses() { - // NoItinerary is always the first class at Index=0 + // NoItinerary is always the first class at Idx=0 SchedClasses.resize(1); SchedClasses.back().Name = "NoItinerary"; + SchedClasses.back().ProcIndices.push_back(0); SchedClassIdxMap[SchedClasses.back().Name] = 0; // Gather and sort all itinerary classes used by instruction descriptions. - std::vector ItinClassList; + RecVec ItinClassList; for (CodeGenTarget::inst_iterator I = Target.inst_begin(), E = Target.inst_end(); I != E; ++I) { - Record *SchedDef = (*I)->TheDef->getValueAsDef("Itinerary"); + Record *ItinDef = (*I)->TheDef->getValueAsDef("Itinerary"); // Map a new SchedClass with no index. - if (!SchedClassIdxMap.count(SchedDef->getName())) { - SchedClassIdxMap[SchedDef->getName()] = 0; - ItinClassList.push_back(SchedDef); + if (!SchedClassIdxMap.count(ItinDef->getName())) { + SchedClassIdxMap[ItinDef->getName()] = 0; + ItinClassList.push_back(ItinDef); } } // Assign each itinerary class unique number, skipping NoItinerary==0 @@ -61,91 +319,340 @@ void CodeGenSchedModels::CollectSchedClasses() { SchedClassIdxMap[ItinDef->getName()] = SchedClasses.size(); SchedClasses.push_back(CodeGenSchedClass(ItinDef)); } + // Infer classes from SchedReadWrite resources listed for each + // instruction definition that inherits from class Sched. + for (CodeGenTarget::inst_iterator I = Target.inst_begin(), + E = Target.inst_end(); I != E; ++I) { + if (!(*I)->TheDef->isSubClassOf("Sched")) + continue; + IdxVec Writes, Reads; + findRWs((*I)->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads); + // ProcIdx == 0 indicates the class applies to all processors. + IdxVec ProcIndices(1, 0); + addSchedClass(Writes, Reads, ProcIndices); + } + // Create classes for InstReadWrite defs. + RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW"); + std::sort(InstRWDefs.begin(), InstRWDefs.end(), LessRecord()); + for (RecIter OI = InstRWDefs.begin(), OE = InstRWDefs.end(); OI != OE; ++OI) + createInstRWClass(*OI); - // TODO: Infer classes from non-itinerary scheduler resources. + NumInstrSchedClasses = SchedClasses.size(); + + bool EnableDump = false; + DEBUG(EnableDump = true); + if (!EnableDump) + return; + for (CodeGenTarget::inst_iterator I = Target.inst_begin(), + E = Target.inst_end(); I != E; ++I) { + Record *SchedDef = (*I)->TheDef; + std::string InstName = (*I)->TheDef->getName(); + if (SchedDef->isSubClassOf("Sched")) { + IdxVec Writes; + IdxVec Reads; + findRWs((*I)->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads); + dbgs() << "SchedRW machine model for " << InstName; + for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI) + dbgs() << " " << SchedWrites[*WI].Name; + for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI) + dbgs() << " " << SchedReads[*RI].Name; + dbgs() << '\n'; + } + unsigned SCIdx = InstrClassMap.lookup((*I)->TheDef); + if (SCIdx) { + const RecVec &RWDefs = SchedClasses[SCIdx].InstRWs; + for (RecIter RWI = RWDefs.begin(), RWE = RWDefs.end(); + RWI != RWE; ++RWI) { + const CodeGenProcModel &ProcModel = + getProcModel((*RWI)->getValueAsDef("SchedModel")); + dbgs() << "InstrRW on " << ProcModel.ModelName << " for " << InstName; + IdxVec Writes; + IdxVec Reads; + findRWs((*RWI)->getValueAsListOfDefs("OperandReadWrites"), + Writes, Reads); + for (IdxIter WI = Writes.begin(), WE = Writes.end(); WI != WE; ++WI) + dbgs() << " " << SchedWrites[*WI].Name; + for (IdxIter RI = Reads.begin(), RE = Reads.end(); RI != RE; ++RI) + dbgs() << " " << SchedReads[*RI].Name; + dbgs() << '\n'; + } + continue; + } + if (!SchedDef->isSubClassOf("Sched") + && (SchedDef->getValueAsDef("Itinerary")->getName() == "NoItinerary")) { + dbgs() << "No machine model for " << (*I)->TheDef->getName() << '\n'; + } + } } -// Gather all processor models. -void CodeGenSchedModels::CollectProcModels() { - std::vector ProcRecords = - Records.getAllDerivedDefinitions("Processor"); - std::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName()); +unsigned CodeGenSchedModels::getSchedClassIdx( + const RecVec &RWDefs) const { - // Reserve space because we can. Reallocation would be ok. - ProcModels.reserve(ProcRecords.size()); + IdxVec Writes, Reads; + findRWs(RWDefs, Writes, Reads); + return findSchedClassIdx(Writes, Reads); +} - // For each processor, find a unique machine model. - for (unsigned i = 0, N = ProcRecords.size(); i < N; ++i) - addProcModel(ProcRecords[i]); +/// Find an SchedClass that has been inferred from a per-operand list of +/// SchedWrites and SchedReads. +unsigned CodeGenSchedModels::findSchedClassIdx(const IdxVec &Writes, + const IdxVec &Reads) const { + for (SchedClassIter I = schedClassBegin(), E = schedClassEnd(); I != E; ++I) { + // Classes with InstRWs may have the same Writes/Reads as a class originally + // produced by a SchedRW definition. We need to be able to recover the + // original class index for processors that don't match any InstRWs. + if (I->ItinClassDef || !I->InstRWs.empty()) + continue; + + if (I->Writes == Writes && I->Reads == Reads) { + return I - schedClassBegin(); + } + } + return 0; } -// Get a unique processor model based on the defined MachineModel and -// ProcessorItineraries. -void CodeGenSchedModels::addProcModel(Record *ProcDef) { - unsigned Idx = getProcModelIdx(ProcDef); - if (Idx < ProcModels.size()) - return; +// Get the SchedClass index for an instruction. +unsigned CodeGenSchedModels::getSchedClassIdx( + const CodeGenInstruction &Inst) const { - Record *ModelDef = ProcDef->getValueAsDef("SchedModel"); - Record *ItinsDef = ProcDef->getValueAsDef("ProcItin"); + unsigned SCIdx = InstrClassMap.lookup(Inst.TheDef); + if (SCIdx) + return SCIdx; - std::string ModelName = ModelDef->getName(); - const std::string &ItinName = ItinsDef->getName(); + // If this opcode isn't mapped by the subtarget fallback to the instruction + // definition's SchedRW or ItinDef values. + if (Inst.TheDef->isSubClassOf("Sched")) { + RecVec RWs = Inst.TheDef->getValueAsListOfDefs("SchedRW"); + return getSchedClassIdx(RWs); + } + Record *ItinDef = Inst.TheDef->getValueAsDef("Itinerary"); + assert(SchedClassIdxMap.count(ItinDef->getName()) && "missing ItinClass"); + unsigned Idx = SchedClassIdxMap.lookup(ItinDef->getName()); + assert(Idx <= NumItineraryClasses && "bad ItinClass index"); + return Idx; +} - bool NoModel = ModelDef->getValueAsBit("NoModel"); - bool hasTopLevelItin = !ItinsDef->getValueAsListOfDefs("IID").empty(); - if (NoModel) { - // If an itinerary is defined without a machine model, infer a new model. - if (NoModel && hasTopLevelItin) { - ModelName = ItinName + "Model"; - ModelDef = NULL; - } +std::string CodeGenSchedModels::createSchedClassName( + const IdxVec &OperWrites, const IdxVec &OperReads) { + + std::string Name; + for (IdxIter WI = OperWrites.begin(), WE = OperWrites.end(); WI != WE; ++WI) { + if (WI != OperWrites.begin()) + Name += '_'; + Name += SchedWrites[*WI].Name; } - else { - // If a machine model is defined, the itinerary must be defined within it - // rather than in the Processor definition itself. - assert(!hasTopLevelItin && "Itinerary must be defined in SchedModel"); - ItinsDef = ModelDef->getValueAsDef("Itineraries"); + for (IdxIter RI = OperReads.begin(), RE = OperReads.end(); RI != RE; ++RI) { + Name += '_'; + Name += SchedReads[*RI].Name; } + return Name; +} - ProcModelMap[getProcModelKey(ProcDef)]= ProcModels.size(); +std::string CodeGenSchedModels::createSchedClassName(const RecVec &InstDefs) { - ProcModels.push_back(CodeGenProcModel(ModelName, ModelDef, ItinsDef)); + std::string Name; + for (RecIter I = InstDefs.begin(), E = InstDefs.end(); I != E; ++I) { + if (I != InstDefs.begin()) + Name += '_'; + Name += (*I)->getName(); + } + return Name; +} + +/// Add an inferred sched class from a per-operand list of SchedWrites and +/// SchedReads. ProcIndices contains the set of IDs of processors that may +/// utilize this class. +unsigned CodeGenSchedModels::addSchedClass(const IdxVec &OperWrites, + const IdxVec &OperReads, + const IdxVec &ProcIndices) +{ + assert(!ProcIndices.empty() && "expect at least one ProcIdx"); + + unsigned Idx = findSchedClassIdx(OperWrites, OperReads); + if (Idx) { + IdxVec PI; + std::set_union(SchedClasses[Idx].ProcIndices.begin(), + SchedClasses[Idx].ProcIndices.end(), + ProcIndices.begin(), ProcIndices.end(), + std::back_inserter(PI)); + SchedClasses[Idx].ProcIndices.swap(PI); + return Idx; + } + Idx = SchedClasses.size(); + SchedClasses.resize(Idx+1); + CodeGenSchedClass &SC = SchedClasses.back(); + SC.Name = createSchedClassName(OperWrites, OperReads); + SC.Writes = OperWrites; + SC.Reads = OperReads; + SC.ProcIndices = ProcIndices; - std::vector ItinRecords = ItinsDef->getValueAsListOfDefs("IID"); - CollectProcItin(ProcModels.back(), ItinRecords); + return Idx; +} + +// Create classes for each set of opcodes that are in the same InstReadWrite +// definition across all processors. +void CodeGenSchedModels::createInstRWClass(Record *InstRWDef) { + // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that + // intersects with an existing class via a previous InstRWDef. Instrs that do + // not intersect with an existing class refer back to their former class as + // determined from ItinDef or SchedRW. + SmallVector >, 4> ClassInstrs; + // Sort Instrs into sets. + RecVec InstDefs = InstRWDef->getValueAsListOfDefs("Instrs"); + std::sort(InstDefs.begin(), InstDefs.end(), LessRecord()); + for (RecIter I = InstDefs.begin(), E = InstDefs.end(); I != E; ++I) { + unsigned SCIdx = 0; + InstClassMapTy::const_iterator Pos = InstrClassMap.find(*I); + if (Pos != InstrClassMap.end()) + SCIdx = Pos->second; + else { + // This instruction has not been mapped yet. Get the original class. All + // instructions in the same InstrRW class must be from the same original + // class because that is the fall-back class for other processors. + Record *ItinDef = (*I)->getValueAsDef("Itinerary"); + SCIdx = SchedClassIdxMap.lookup(ItinDef->getName()); + if (!SCIdx && (*I)->isSubClassOf("Sched")) + SCIdx = getSchedClassIdx((*I)->getValueAsListOfDefs("SchedRW")); + } + unsigned CIdx = 0, CEnd = ClassInstrs.size(); + for (; CIdx != CEnd; ++CIdx) { + if (ClassInstrs[CIdx].first == SCIdx) + break; + } + if (CIdx == CEnd) { + ClassInstrs.resize(CEnd + 1); + ClassInstrs[CIdx].first = SCIdx; + } + ClassInstrs[CIdx].second.push_back(*I); + } + // For each set of Instrs, create a new class if necessary, and map or remap + // the Instrs to it. + unsigned CIdx = 0, CEnd = ClassInstrs.size(); + for (; CIdx != CEnd; ++CIdx) { + unsigned OldSCIdx = ClassInstrs[CIdx].first; + ArrayRef InstDefs = ClassInstrs[CIdx].second; + // If the all instrs in the current class are accounted for, then leave + // them mapped to their old class. + if (SchedClasses[OldSCIdx].InstRWs.size() == InstDefs.size()) { + assert(SchedClasses[OldSCIdx].ProcIndices[0] == 0 && + "expected a generic SchedClass"); + continue; + } + unsigned SCIdx = SchedClasses.size(); + SchedClasses.resize(SCIdx+1); + CodeGenSchedClass &SC = SchedClasses.back(); + SC.Name = createSchedClassName(InstDefs); + // Preserve ItinDef and Writes/Reads for processors without an InstRW entry. + SC.ItinClassDef = SchedClasses[OldSCIdx].ItinClassDef; + SC.Writes = SchedClasses[OldSCIdx].Writes; + SC.Reads = SchedClasses[OldSCIdx].Reads; + SC.ProcIndices.push_back(0); + // Map each Instr to this new class. + // Note that InstDefs may be a smaller list than InstRWDef's "Instrs". + for (ArrayRef::const_iterator + II = InstDefs.begin(), IE = InstDefs.end(); II != IE; ++II) { + unsigned OldSCIdx = InstrClassMap[*II]; + if (OldSCIdx) { + SC.InstRWs.insert(SC.InstRWs.end(), + SchedClasses[OldSCIdx].InstRWs.begin(), + SchedClasses[OldSCIdx].InstRWs.end()); + } + InstrClassMap[*II] = SCIdx; + } + SC.InstRWs.push_back(InstRWDef); + } } // Gather the processor itineraries. -void CodeGenSchedModels::CollectProcItin(CodeGenProcModel &ProcModel, - std::vector ItinRecords) { - // Skip empty itinerary. - if (ItinRecords.empty()) - return; +void CodeGenSchedModels::collectProcItins() { + for (std::vector::iterator PI = ProcModels.begin(), + PE = ProcModels.end(); PI != PE; ++PI) { + CodeGenProcModel &ProcModel = *PI; + RecVec ItinRecords = ProcModel.ItinsDef->getValueAsListOfDefs("IID"); + // Skip empty itinerary. + if (ItinRecords.empty()) + continue; - HasProcItineraries = true; + ProcModel.ItinDefList.resize(NumItineraryClasses+1); - ProcModel.ItinDefList.resize(NumItineraryClasses+1); + // Insert each itinerary data record in the correct position within + // the processor model's ItinDefList. + for (unsigned i = 0, N = ItinRecords.size(); i < N; i++) { + Record *ItinData = ItinRecords[i]; + Record *ItinDef = ItinData->getValueAsDef("TheClass"); + if (!SchedClassIdxMap.count(ItinDef->getName())) { + DEBUG(dbgs() << ProcModel.ItinsDef->getName() + << " has unused itinerary class " << ItinDef->getName() << '\n'); + continue; + } + assert(SchedClassIdxMap.count(ItinDef->getName()) && "missing ItinClass"); + unsigned Idx = SchedClassIdxMap.lookup(ItinDef->getName()); + assert(Idx <= NumItineraryClasses && "bad ItinClass index"); + ProcModel.ItinDefList[Idx] = ItinData; + } + // Check for missing itinerary entries. + assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec"); + DEBUG( + for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) { + if (!ProcModel.ItinDefList[i]) + dbgs() << ProcModel.ItinsDef->getName() + << " missing itinerary for class " + << SchedClasses[i].Name << '\n'; + }); + } +} - // Insert each itinerary data record in the correct position within - // the processor model's ItinDefList. - for (unsigned i = 0, N = ItinRecords.size(); i < N; i++) { - Record *ItinData = ItinRecords[i]; - Record *ItinDef = ItinData->getValueAsDef("TheClass"); - if (!SchedClassIdxMap.count(ItinDef->getName())) { - DEBUG(dbgs() << ProcModel.ItinsDef->getName() - << " has unused itinerary class " << ItinDef->getName() << '\n'); - continue; +// Gather the read/write types for each itinerary class. +void CodeGenSchedModels::collectProcItinRW() { + RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW"); + std::sort(ItinRWDefs.begin(), ItinRWDefs.end(), LessRecord()); + for (RecIter II = ItinRWDefs.begin(), IE = ItinRWDefs.end(); II != IE; ++II) { + if (!(*II)->getValueInit("SchedModel")->isComplete()) + throw TGError((*II)->getLoc(), "SchedModel is undefined"); + Record *ModelDef = (*II)->getValueAsDef("SchedModel"); + ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); + if (I == ProcModelMap.end()) { + throw TGError((*II)->getLoc(), "Undefined SchedMachineModel " + + ModelDef->getName()); } - ProcModel.ItinDefList[getItinClassIdx(ItinDef)] = ItinData; + ProcModels[I->second].ItinRWDefs.push_back(*II); } +} + #ifndef NDEBUG - // Check for missing itinerary entries. - assert(!ProcModel.ItinDefList[0] && "NoItinerary class can't have rec"); - for (unsigned i = 1, N = ProcModel.ItinDefList.size(); i < N; ++i) { - if (!ProcModel.ItinDefList[i]) - DEBUG(dbgs() << ProcModel.ItinsDef->getName() - << " missing itinerary for class " << SchedClasses[i].Name << '\n'); +void CodeGenProcModel::dump() const { + dbgs() << Index << ": " << ModelName << " " + << (ModelDef ? ModelDef->getName() : "inferred") << " " + << (ItinsDef ? ItinsDef->getName() : "no itinerary") << '\n'; +} + +void CodeGenSchedRW::dump() const { + dbgs() << Name << (IsVariadic ? " (V) " : " "); + if (IsSequence) { + dbgs() << "("; + dumpIdxVec(Sequence); + dbgs() << ")"; } -#endif } + +void CodeGenSchedClass::dump(const CodeGenSchedModels* SchedModels) const { + dbgs() << "SCHEDCLASS " << Name << '\n' + << " Writes: "; + for (unsigned i = 0, N = Writes.size(); i < N; ++i) { + SchedModels->getSchedWrite(Writes[i]).dump(); + if (i < N-1) { + dbgs() << '\n'; + dbgs().indent(10); + } + } + dbgs() << "\n Reads: "; + for (unsigned i = 0, N = Reads.size(); i < N; ++i) { + SchedModels->getSchedRead(Reads[i]).dump(); + if (i < N-1) { + dbgs() << '\n'; + dbgs().indent(10); + } + } + dbgs() << "\n ProcIdx: "; dumpIdxVec(ProcIndices); dbgs() << '\n'; +} +#endif // NDEBUG diff --git a/utils/TableGen/CodeGenSchedule.h b/utils/TableGen/CodeGenSchedule.h index 9da0145732b..5e8b711fcbb 100644 --- a/utils/TableGen/CodeGenSchedule.h +++ b/utils/TableGen/CodeGenSchedule.h @@ -23,21 +23,112 @@ namespace llvm { class CodeGenTarget; +class CodeGenSchedModels; +class CodeGenInstruction; -// Scheduling class. -// -// Each instruction description will be mapped to a scheduling class. It may be -// an explicitly defined itinerary class, or an inferred class in which case -// ItinClassDef == NULL. +typedef std::vector RecVec; +typedef std::vector::const_iterator RecIter; + +typedef std::vector IdxVec; +typedef std::vector::const_iterator IdxIter; + +void splitSchedReadWrites(const RecVec &RWDefs, + RecVec &WriteDefs, RecVec &ReadDefs); + +/// We have two kinds of SchedReadWrites. Explicitly defined and inferred +/// sequences. TheDef is nonnull for explicit SchedWrites, but Sequence may or +/// may not be empty. TheDef is null for inferred sequences, and Sequence must +/// be nonempty. +/// +/// IsVariadic controls whether the variants are expanded into multiple operands +/// or a sequence of writes on one operand. +struct CodeGenSchedRW { + std::string Name; + Record *TheDef; + bool HasVariants; + bool IsVariadic; + bool IsSequence; + IdxVec Sequence; + + CodeGenSchedRW(): TheDef(0), HasVariants(false), IsVariadic(false), + IsSequence(false) {} + CodeGenSchedRW(Record *Def): TheDef(Def), IsVariadic(false) { + Name = Def->getName(); + HasVariants = Def->isSubClassOf("SchedVariant"); + if (HasVariants) + IsVariadic = Def->getValueAsBit("Variadic"); + + // Read records don't currently have sequences, but it can be easily + // added. Note that implicit Reads (from ReadVariant) may have a Sequence + // (but no record). + IsSequence = Def->isSubClassOf("WriteSequence"); + } + + CodeGenSchedRW(const IdxVec &Seq, const std::string &Name): + Name(Name), TheDef(0), HasVariants(false), IsVariadic(false), + IsSequence(true), Sequence(Seq) { + assert(Sequence.size() > 1 && "implied sequence needs >1 RWs"); + } + + bool isValid() const { + assert((!HasVariants || TheDef) && "Variant write needs record def"); + assert((!IsVariadic || HasVariants) && "Variadic write needs variants"); + assert((!IsSequence || !HasVariants) && "Sequence can't have variant"); + assert((!IsSequence || !Sequence.empty()) && "Sequence should be nonempty"); + return TheDef || !Sequence.empty(); + } + +#ifndef NDEBUG + void dump() const; +#endif +}; + +/// Scheduling class. +/// +/// Each instruction description will be mapped to a scheduling class. There are +/// four types of classes: +/// +/// 1) An explicitly defined itinerary class with ItinClassDef set. +/// Writes and ReadDefs are empty. ProcIndices contains 0 for any processor. +/// +/// 2) An implied class with a list of SchedWrites and SchedReads that are +/// defined in an instruction definition and which are common across all +/// subtargets. ProcIndices contains 0 for any processor. +/// +/// 3) An implied class with a list of InstRW records that map instructions to +/// SchedWrites and SchedReads per-processor. InstrClassMap should map the same +/// instructions to this class. ProcIndices contains all the processors that +/// provided InstrRW records for this class. ItinClassDef or Writes/Reads may +/// still be defined for processors with no InstRW entry. +/// +/// 4) An inferred class represents a variant of another class that may be +/// resolved at runtime. ProcIndices contains the set of processors that may +/// require the class. ProcIndices are propagated through SchedClasses as +/// variants are expanded. Multiple SchedClasses may be inferred from an +/// itinerary class. Each inherits the processor index from the ItinRW record +/// that mapped the itinerary class to the variant Writes or Reads. struct CodeGenSchedClass { std::string Name; - unsigned Index; Record *ItinClassDef; - CodeGenSchedClass(): Index(0), ItinClassDef(0) {} - CodeGenSchedClass(Record *rec): Index(0), ItinClassDef(rec) { + IdxVec Writes; + IdxVec Reads; + // Sorted list of ProcIdx, where ProcIdx==0 implies any processor. + IdxVec ProcIndices; + + // InstReadWrite records associated with this class. Any Instrs that the + // definitions refer to that are not mapped to this class should be ignored. + RecVec InstRWs; + + CodeGenSchedClass(): ItinClassDef(0) {} + CodeGenSchedClass(Record *rec): ItinClassDef(rec) { Name = rec->getName(); + ProcIndices.push_back(0); } + +#ifndef NDEBUG + void dump(const CodeGenSchedModels *SchedModels) const; +#endif }; // Processor model. @@ -55,28 +146,53 @@ struct CodeGenSchedClass { // // ItinDefList orders this processor's InstrItinData records by SchedClass idx. struct CodeGenProcModel { + unsigned Index; std::string ModelName; Record *ModelDef; Record *ItinsDef; - // Array of InstrItinData records indexed by CodeGenSchedClass::Index. - // The list is empty if the subtarget has no itineraries. - std::vector ItinDefList; + // Derived members... + + // Array of InstrItinData records indexed by a CodeGenSchedClass index. + // This list is empty if the Processor has no value for Itineraries. + // Initialized by collectProcItins(). + RecVec ItinDefList; + + // Map itinerary classes to per-operand resources. + // This list is empty if no ItinRW refers to this Processor. + RecVec ItinRWDefs; + + CodeGenProcModel(unsigned Idx, const std::string &Name, Record *MDef, + Record *IDef) : + Index(Idx), ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {} - CodeGenProcModel(const std::string &Name, Record *MDef, Record *IDef): - ModelName(Name), ModelDef(MDef), ItinsDef(IDef) {} +#ifndef NDEBUG + void dump() const; +#endif }; -// Top level container for machine model data. +/// Top level container for machine model data. class CodeGenSchedModels { RecordKeeper &Records; const CodeGenTarget &Target; + // List of unique processor models. + std::vector ProcModels; + + // Map Processor's MachineModel or ProcItin to a CodeGenProcModel index. + typedef DenseMap ProcModelMapTy; + ProcModelMapTy ProcModelMap; + + // Per-operand SchedReadWrite types. + std::vector SchedWrites; + std::vector SchedReads; + // List of unique SchedClasses. std::vector SchedClasses; // Map SchedClass name to itinerary index. - // These are either explicit itinerary classes or inferred classes. + // These are either explicit itinerary classes or classes implied by + // instruction definitions with SchedReadWrite lists. StringMap SchedClassIdxMap; // SchedClass indices 1 up to and including NumItineraryClasses identify @@ -84,22 +200,68 @@ class CodeGenSchedModels { // definitions. NoItinerary always has index 0 regardless of whether it is // explicitly referenced. // - // Any inferred SchedClass have a index greater than NumItineraryClasses. + // Any implied SchedClass has an index greater than NumItineraryClasses. unsigned NumItineraryClasses; - // List of unique processor models. - std::vector ProcModels; + // Any inferred SchedClass has an index greater than NumInstrSchedClassses. + unsigned NumInstrSchedClasses; - // Map Processor's MachineModel + ProcItin fields to a CodeGenProcModel index. - typedef DenseMap, unsigned> ProcModelMapTy; - ProcModelMapTy ProcModelMap; - - // True if any processors have nonempty itineraries. - bool HasProcItineraries; + // Map Instruction to SchedClass index. Only for Instructions mentioned in + // OpReadWrites. + typedef DenseMap InstClassMapTy; + InstClassMapTy InstrClassMap; public: CodeGenSchedModels(RecordKeeper& RK, const CodeGenTarget &TGT); + Record *getModelOrItinDef(Record *ProcDef) const { + Record *ModelDef = ProcDef->getValueAsDef("SchedModel"); + Record *ItinsDef = ProcDef->getValueAsDef("ProcItin"); + if (!ItinsDef->getValueAsListOfDefs("IID").empty()) { + assert(ModelDef->getValueAsBit("NoModel") + && "Itineraries must be defined within SchedMachineModel"); + return ItinsDef; + } + return ModelDef; + } + + const CodeGenProcModel &getModelForProc(Record *ProcDef) const { + Record *ModelDef = getModelOrItinDef(ProcDef); + ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); + assert(I != ProcModelMap.end() && "missing machine model"); + return ProcModels[I->second]; + } + + const CodeGenProcModel &getProcModel(Record *ModelDef) const { + ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef); + assert(I != ProcModelMap.end() && "missing machine model"); + return ProcModels[I->second]; + } + + // Iterate over the unique processor models. + typedef std::vector::const_iterator ProcIter; + ProcIter procModelBegin() const { return ProcModels.begin(); } + ProcIter procModelEnd() const { return ProcModels.end(); } + + // Get a SchedWrite from its index. + const CodeGenSchedRW &getSchedWrite(unsigned Idx) const { + assert(Idx < SchedWrites.size() && "bad SchedWrite index"); + assert(SchedWrites[Idx].isValid() && "invalid SchedWrite"); + return SchedWrites[Idx]; + } + // Get a SchedWrite from its index. + const CodeGenSchedRW &getSchedRead(unsigned Idx) const { + assert(Idx < SchedReads.size() && "bad SchedRead index"); + assert(SchedReads[Idx].isValid() && "invalid SchedRead"); + return SchedReads[Idx]; + } + + const CodeGenSchedRW &getSchedRW(unsigned Idx, bool IsRead) const { + return IsRead ? getSchedRead(Idx) : getSchedWrite(Idx); + } + + unsigned getSchedRWIdx(Record *Def, bool IsRead, unsigned After = 0) const; + // Check if any instructions are assigned to an explicit itinerary class other // than NoItinerary. bool hasItineraryClasses() const { return NumItineraryClasses > 0; } @@ -111,7 +273,11 @@ public: } // Get a SchedClass from its index. - const CodeGenSchedClass &getSchedClass(unsigned Idx) { + CodeGenSchedClass &getSchedClass(unsigned Idx) { + assert(Idx < SchedClasses.size() && "bad SchedClass index"); + return SchedClasses[Idx]; + } + const CodeGenSchedClass &getSchedClass(unsigned Idx) const { assert(Idx < SchedClasses.size() && "bad SchedClass index"); return SchedClasses[Idx]; } @@ -125,46 +291,52 @@ public: return Idx; } - bool hasProcessorItineraries() const { - return HasProcItineraries; - } + // Get the SchedClass index for an instruction. Instructions with no + // itinerary, no SchedReadWrites, and no InstrReadWrites references return 0 + // for NoItinerary. + unsigned getSchedClassIdx(const CodeGenInstruction &Inst) const; - // Get an existing machine model for a processor definition. - const CodeGenProcModel &getProcModel(Record *ProcDef) const { - unsigned idx = getProcModelIdx(ProcDef); - assert(idx < ProcModels.size() && "missing machine model"); - return ProcModels[idx]; + unsigned getSchedClassIdx(const RecVec &RWDefs) const; + + unsigned getSchedClassIdxForItin(const Record *ItinDef) { + return SchedClassIdxMap[ItinDef->getName()]; } - // Iterate over the unique processor models. - typedef std::vector::const_iterator ProcIter; - ProcIter procModelBegin() const { return ProcModels.begin(); } - ProcIter procModelEnd() const { return ProcModels.end(); } + typedef std::vector::const_iterator SchedClassIter; + SchedClassIter schedClassBegin() const { return SchedClasses.begin(); } + SchedClassIter schedClassEnd() const { return SchedClasses.end(); } -private: - // Get a key that can uniquely identify a machine model. - ProcModelMapTy::key_type getProcModelKey(Record *ProcDef) const { - Record *ModelDef = ProcDef->getValueAsDef("SchedModel"); - Record *ItinsDef = ProcDef->getValueAsDef("ProcItin"); - return std::make_pair(ModelDef, ItinsDef); - } + void findRWs(const RecVec &RWDefs, IdxVec &Writes, IdxVec &Reads) const; + void findRWs(const RecVec &RWDefs, IdxVec &RWs, bool IsRead) const; - // Get the unique index of a machine model. - unsigned getProcModelIdx(Record *ProcDef) const { - ProcModelMapTy::const_iterator I = - ProcModelMap.find(getProcModelKey(ProcDef)); - if (I == ProcModelMap.end()) - return ProcModels.size(); - return I->second; - } + unsigned addSchedClass(const IdxVec &OperWrites, const IdxVec &OperReads, + const IdxVec &ProcIndices); + + unsigned findOrInsertRW(ArrayRef Seq, bool IsRead); + + unsigned findSchedClassIdx(const IdxVec &Writes, const IdxVec &Reads) const; + +private: + void collectProcModels(); // Initialize a new processor model if it is unique. void addProcModel(Record *ProcDef); - void CollectSchedClasses(); - void CollectProcModels(); - void CollectProcItin(CodeGenProcModel &ProcModel, - std::vector ItinRecords); + void collectSchedRW(); + + std::string genRWName(const IdxVec& Seq, bool IsRead); + unsigned findRWForSequence(const IdxVec &Seq, bool IsRead); + + void collectSchedClasses(); + + std::string createSchedClassName(const IdxVec &OperWrites, + const IdxVec &OperReads); + std::string createSchedClassName(const RecVec &InstDefs); + void createInstRWClass(Record *InstRWDef); + + void collectProcItins(); + + void collectProcItinRW(); }; } // namespace llvm diff --git a/utils/TableGen/SubtargetEmitter.cpp b/utils/TableGen/SubtargetEmitter.cpp index 5dfd716d897..2fdd930c35b 100644 --- a/utils/TableGen/SubtargetEmitter.cpp +++ b/utils/TableGen/SubtargetEmitter.cpp @@ -521,7 +521,7 @@ EmitItineraries(raw_ostream &OS, std::vector >::iterator ProcItinListsIter = ProcItinLists.begin(); for (CodeGenSchedModels::ProcIter PI = SchedModels.procModelBegin(), - PE = SchedModels.procModelEnd(); PI != PE; ++PI) { + PE = SchedModels.procModelEnd(); PI != PE; ++PI, ++ProcItinListsIter) { Record *ItinsDef = PI->ItinsDef; if (!ItinsDefSet.insert(ItinsDef)) @@ -532,7 +532,7 @@ EmitItineraries(raw_ostream &OS, // Get the itinerary list for the processor. assert(ProcItinListsIter != ProcItinLists.end() && "bad iterator"); - std::vector &ItinList = *ProcItinListsIter++; + std::vector &ItinList = *ProcItinListsIter; OS << "\n"; OS << "static const llvm::InstrItinerary "; @@ -621,7 +621,7 @@ void SubtargetEmitter::EmitProcessorLookup(raw_ostream &OS) { const std::string &Name = Processor->getValueAsString("Name"); const std::string &ProcModelName = - SchedModels.getProcModel(Processor).ModelName; + SchedModels.getModelForProc(Processor).ModelName; // Emit as { "cpu", procinit }, OS << " { " -- 2.11.0