From a00b4f6e5d7cab3ef3a6e2b7b1da20fdf1841c81 Mon Sep 17 00:00:00 2001 From: Krzysztof Parzyszek Date: Sat, 21 Nov 2015 17:38:33 +0000 Subject: [PATCH] Revert r253790: it breaks all builds for some reason. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253791 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/DFAPacketizer.h | 48 +- include/llvm/Target/TargetItinerary.td | 16 - lib/CodeGen/DFAPacketizer.cpp | 39 +- lib/Target/Hexagon/HexagonScheduleV60.td | 9 - utils/TableGen/DFAPacketizerEmitter.cpp | 646 ++++------------------- 5 files changed, 120 insertions(+), 638 deletions(-) diff --git a/include/llvm/CodeGen/DFAPacketizer.h b/include/llvm/CodeGen/DFAPacketizer.h index 4689a2b89ad..791b66e1429 100644 --- a/include/llvm/CodeGen/DFAPacketizer.h +++ b/include/llvm/CodeGen/DFAPacketizer.h @@ -40,47 +40,22 @@ class InstrItineraryData; class DefaultVLIWScheduler; class SUnit; -// DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput. -// This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer. -// -// e.g. terms x resource bit combinations that fit in uint32_t: -// 4 terms x 8 bits = 32 bits -// 3 terms x 10 bits = 30 bits -// 2 terms x 16 bits = 32 bits -// -// e.g. terms x resource bit combinations that fit in uint64_t: -// 8 terms x 8 bits = 64 bits -// 7 terms x 9 bits = 63 bits -// 6 terms x 10 bits = 60 bits -// 5 terms x 12 bits = 60 bits -// 4 terms x 16 bits = 64 bits <--- current -// 3 terms x 21 bits = 63 bits -// 2 terms x 32 bits = 64 bits -// -#define DFA_MAX_RESTERMS 4 // The max # of AND'ed resource terms. -#define DFA_MAX_RESOURCES 16 // The max # of resource bits in one term. - -typedef uint64_t DFAInput; -typedef int64_t DFAStateInput; -#define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable. - class DFAPacketizer { private: - typedef std::pair UnsignPair; - + typedef std::pair UnsignPair; const InstrItineraryData *InstrItins; int CurrentState; - const DFAStateInput (*DFAStateInputTable)[2]; + const int (*DFAStateInputTable)[2]; const unsigned *DFAStateEntryTable; // CachedTable is a map from to ToState. DenseMap CachedTable; // ReadTable - Read the DFA transition table and update CachedTable. - void ReadTable(unsigned state); + void ReadTable(unsigned int state); public: - DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2], + DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2], const unsigned *SET); // Reset the current state to make all resources available. @@ -88,21 +63,6 @@ public: CurrentState = 0; } - // getInsnInput - Return the DFAInput for an instruction class. - DFAInput getInsnInput(unsigned InsnClass); - - // getInsnInput - Return the DFAInput for an instruction class input vector. - static DFAInput getInsnInput(const std::vector &InsnClass) { - DFAInput InsnInput = 0; - unsigned N = InsnClass.size(); - assert ((N <= DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA terms"); - for (unsigned i = 0; i < N; i++) { - InsnInput <<= DFA_MAX_RESOURCES; // Shift over any previous AND'ed terms. - InsnInput |= InsnClass[i]; - } - return(InsnInput); - } - // canReserveResources - Check if the resources occupied by a MCInstrDesc // are available in the current state. bool canReserveResources(const llvm::MCInstrDesc *MID); diff --git a/include/llvm/Target/TargetItinerary.td b/include/llvm/Target/TargetItinerary.td index a37bbf2474c..cc74006dc9f 100644 --- a/include/llvm/Target/TargetItinerary.td +++ b/include/llvm/Target/TargetItinerary.td @@ -134,19 +134,3 @@ class ProcessorItineraries fu, list bp, // info. Subtargets using NoItineraries can bypass the scheduler's // expensive HazardRecognizer because no reservation table is needed. def NoItineraries : ProcessorItineraries<[], [], []>; - -//===----------------------------------------------------------------------===// -// Combo Function Unit data - This is a map of combo function unit names to -// the list of functional units that are included in the combination. -// -class ComboFuncData funclist> { - FuncUnit TheComboFunc = ComboFunc; - list FuncList = funclist; -} - -//===----------------------------------------------------------------------===// -// Combo Function Units - This is a list of all combo function unit data. -class ComboFuncUnits cfd> { - list CFD = cfd; -} - diff --git a/lib/CodeGen/DFAPacketizer.cpp b/lib/CodeGen/DFAPacketizer.cpp index 40450b46fcb..ee50f972aa7 100644 --- a/lib/CodeGen/DFAPacketizer.cpp +++ b/lib/CodeGen/DFAPacketizer.cpp @@ -31,17 +31,10 @@ #include "llvm/Target/TargetInstrInfo.h" using namespace llvm; -DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, - const DFAStateInput (*SIT)[2], +DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2], const unsigned *SET): InstrItins(I), CurrentState(0), DFAStateInputTable(SIT), - DFAStateEntryTable(SET) { - // Make sure DFA types are large enough for the number of terms & resources. - assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAInput)) - && "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput"); - assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)) - && "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput"); -} + DFAStateEntryTable(SET) {} // @@ -67,40 +60,26 @@ void DFAPacketizer::ReadTable(unsigned int state) { DFAStateInputTable[i][1]; } -// -// getInsnInput - Return the DFAInput for an instruction class. -// -DFAInput DFAPacketizer::getInsnInput(unsigned InsnClass) { - // note: this logic must match that in DFAPacketizer.h for input vectors - DFAInput InsnInput = 0; - unsigned i = 0; - for (const InstrStage *IS = InstrItins->beginStage(InsnClass), - *IE = InstrItins->endStage(InsnClass); IS != IE; ++IS, ++i) { - unsigned FuncUnits = IS->getUnits(); - InsnInput <<= DFA_MAX_RESOURCES; // Shift over any previous AND'ed terms. - InsnInput |= FuncUnits; - assert ((i < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs"); - } - - return InsnInput; -} // canReserveResources - Check if the resources occupied by a MCInstrDesc // are available in the current state. bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc *MID) { unsigned InsnClass = MID->getSchedClass(); - DFAInput InsnInput = getInsnInput(InsnClass); - UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); + const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass); + unsigned FuncUnits = IS->getUnits(); + UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); ReadTable(CurrentState); return (CachedTable.count(StateTrans) != 0); } + // reserveResources - Reserve the resources occupied by a MCInstrDesc and // change the current state to reflect that change. void DFAPacketizer::reserveResources(const llvm::MCInstrDesc *MID) { unsigned InsnClass = MID->getSchedClass(); - DFAInput InsnInput = getInsnInput(InsnClass); - UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); + const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass); + unsigned FuncUnits = IS->getUnits(); + UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); ReadTable(CurrentState); assert(CachedTable.count(StateTrans) != 0); CurrentState = CachedTable[StateTrans]; diff --git a/lib/Target/Hexagon/HexagonScheduleV60.td b/lib/Target/Hexagon/HexagonScheduleV60.td index 2ccff8242a4..7cda4a74319 100644 --- a/lib/Target/Hexagon/HexagonScheduleV60.td +++ b/lib/Target/Hexagon/HexagonScheduleV60.td @@ -20,15 +20,6 @@ def CVI_XLSHF : FuncUnit; def CVI_MPY01 : FuncUnit; def CVI_ALL : FuncUnit; -// Combined functional unit data. -def HexagonComboFuncsV60 : - ComboFuncUnits<[ - ComboFuncData, - ComboFuncData, - ComboFuncData - ]>; - // Note: When adding additional vector scheduling classes, add the // corresponding methods to the class HexagonInstrInfo. def CVI_VA : InstrItinClass; diff --git a/utils/TableGen/DFAPacketizerEmitter.cpp b/utils/TableGen/DFAPacketizerEmitter.cpp index 68a480249c8..5060b6e9ce7 100644 --- a/utils/TableGen/DFAPacketizerEmitter.cpp +++ b/utils/TableGen/DFAPacketizerEmitter.cpp @@ -15,36 +15,16 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "dfa-emitter" - #include "CodeGenTarget.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/StringExtras.h" -#include "llvm/CodeGen/DFAPacketizer.h" #include "llvm/TableGen/Record.h" #include "llvm/TableGen/TableGenBackend.h" -#include "llvm/Support/Debug.h" #include #include #include -#include using namespace llvm; -// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter". -// -// dbgsInsnClass - When debugging, print instruction class stages. -// -void dbgsInsnClass(const std::vector &InsnClass); -// -// dbgsStateInfo - When debugging, print the set of state info. -// -void dbgsStateInfo(const std::set &stateInfo); -// -// dbgsIndent - When debugging, indent by the specified amount. -// -void dbgsIndent(unsigned indent); - // // class DFAPacketizerEmitter: class that generates and prints out the DFA // for resource tracking. @@ -57,48 +37,20 @@ private: // allInsnClasses is the set of all possible resources consumed by an // InstrStage. // - std::vector> allInsnClasses; + DenseSet allInsnClasses; RecordKeeper &Records; public: DFAPacketizerEmitter(RecordKeeper &R); // - // collectAllFuncUnits - Construct a map of function unit names to bits. - // - int collectAllFuncUnits(std::vector &ProcItinList, - std::map &FUNameToBitsMap, - int &maxResources, - raw_ostream &OS); - - // - // collectAllComboFuncs - Construct a map from a combo function unit bit to - // the bits of all included functional units. - // - int collectAllComboFuncs(std::vector &ComboFuncList, - std::map &FUNameToBitsMap, - std::map &ComboBitToBitsMap, - raw_ostream &OS); - - // - // collectOneInsnClass - Populate allInsnClasses with one instruction class. - // - int collectOneInsnClass(const std::string &ProcName, - std::vector &ProcItinList, - std::map &FUNameToBitsMap, - Record *ItinData, - raw_ostream &OS); - - // - // collectAllInsnClasses - Populate allInsnClasses which is a set of units + // collectAllInsnClasses: Populate allInsnClasses which is a set of units // used in each stage. // - int collectAllInsnClasses(const std::string &ProcName, - std::vector &ProcItinList, - std::map &FUNameToBitsMap, - std::vector &ItinDataList, - int &maxStages, - raw_ostream &OS); + void collectAllInsnClasses(const std::string &Name, + Record *ItinData, + unsigned &NStages, + raw_ostream &OS); void run(raw_ostream &OS); }; @@ -135,7 +87,7 @@ class State { const int stateNum; mutable bool isInitial; mutable std::set stateInfo; - typedef std::map, const State *> TransitionMap; + typedef std::map TransitionMap; mutable TransitionMap Transitions; State(); @@ -145,47 +97,28 @@ class State { } // - // canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass - // may be a valid transition from this state i.e., can an instruction of type - // InsnClass be added to the packet represented by this state. - // - // Note that for multiple stages, this quick check does not take into account - // any possible resource competition between the stages themselves. That is - // enforced in AddInsnClassStages which checks the cross product of all - // stages for resource availability (which is a more involved check). - // - bool canMaybeAddInsnClass(std::vector &InsnClass, - std::map &ComboBitToBitsMap) const; - // - // AddInsnClass - Return all combinations of resource reservation - // which are possible from this state (PossibleStates). + // canAddInsnClass - Returns true if an instruction of type InsnClass is a + // valid transition from this state, i.e., can an instruction of type InsnClass + // be added to the packet represented by this state. // // PossibleStates is the set of valid resource states that ensue from valid // transitions. // - void AddInsnClass(std::vector &InsnClass, - std::map &ComboBitToBitsMap, - std::set &PossibleStates) const; + bool canAddInsnClass(unsigned InsnClass) const; // - // AddInsnClassStages - Return all combinations of resource reservation - // resulting from the cross product of all stages for this InsnClass + // AddInsnClass - Return all combinations of resource reservation // which are possible from this state (PossibleStates). // - void AddInsnClassStages(std::vector &InsnClass, - std::map &ComboBitToBitsMap, - unsigned chkstage, unsigned numstages, - unsigned prevState, unsigned origState, - DenseSet &VisitedResourceStates, - std::set &PossibleStates) const; - // + void AddInsnClass(unsigned InsnClass, std::set &PossibleStates) const; + // // addTransition - Add a transition from this state given the input InsnClass // - void addTransition(std::vector InsnClass, const State *To) const; + void addTransition(unsigned InsnClass, const State *To) const; // // hasTransition - Returns true if there is a transition from this state // given the input InsnClass // - bool hasTransition(std::vector InsnClass) const; + bool hasTransition(unsigned InsnClass) const; }; } // End anonymous namespace. @@ -211,52 +144,10 @@ public: // // writeTable: Print out a table representing the DFA. // - void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName, - int numInsnClasses = 0, - int maxResources = 0, int numCombos = 0, int maxStages = 0); + void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName); }; } // End anonymous namespace. -// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter". -// -// dbgsInsnClass - When debugging, print instruction class stages. -// -void dbgsInsnClass(const std::vector &InsnClass) { - DEBUG(dbgs() << "InsnClass: "); - for (unsigned i = 0; i < InsnClass.size(); ++i) { - if (i > 0) { - DEBUG(dbgs() << ", "); - } - DEBUG(dbgs() << "0x" << utohexstr(InsnClass[i])); - } - DFAInput InsnInput = DFAPacketizer::getInsnInput(InsnClass); - DEBUG(dbgs() << " (input: 0x" << utohexstr(InsnInput) << ")"); -} - -// -// dbgsStateInfo - When debugging, print the set of state info. -// -void dbgsStateInfo(const std::set &stateInfo) { - DEBUG(dbgs() << "StateInfo: "); - unsigned i = 0; - for (std::set::iterator SI = stateInfo.begin(); - SI != stateInfo.end(); ++SI, ++i) { - unsigned thisState = *SI; - if (i > 0) { - DEBUG(dbgs() << ", "); - } - DEBUG(dbgs() << "0x" << utohexstr(thisState)); - } -} - -// -// dbgsIndent - When debugging, indent by the specified amount. -// -void dbgsIndent(unsigned indent) { - for (unsigned i = 0; i < indent; ++i) { - DEBUG(dbgs() << " "); - } -} // // Constructors and destructors for State and DFA @@ -266,11 +157,10 @@ State::State() : DFA::DFA(): currentState(nullptr) {} -// +// // addTransition - Add a transition from this state given the input InsnClass // -void State::addTransition(std::vector InsnClass, const State *To) - const { +void State::addTransition(unsigned InsnClass, const State *To) const { assert(!Transitions.count(InsnClass) && "Cannot have multiple transitions for the same input"); Transitions[InsnClass] = To; @@ -280,7 +170,7 @@ void State::addTransition(std::vector InsnClass, const State *To) // hasTransition - Returns true if there is a transition from this state // given the input InsnClass // -bool State::hasTransition(std::vector InsnClass) const { +bool State::hasTransition(unsigned InsnClass) const { return Transitions.count(InsnClass) > 0; } @@ -288,167 +178,61 @@ bool State::hasTransition(std::vector InsnClass) const { // AddInsnClass - Return all combinations of resource reservation // which are possible from this state (PossibleStates). // -// PossibleStates is the set of valid resource states that ensue from valid -// transitions. -// -void State::AddInsnClass(std::vector &InsnClass, - std::map &ComboBitToBitsMap, - std::set &PossibleStates) const { +void State::AddInsnClass(unsigned InsnClass, + std::set &PossibleStates) const { // // Iterate over all resource states in currentState. // - unsigned numstages = InsnClass.size(); - assert((numstages > 0) && "InsnClass has no stages"); for (std::set::iterator SI = stateInfo.begin(); SI != stateInfo.end(); ++SI) { unsigned thisState = *SI; - DenseSet VisitedResourceStates; - - DEBUG(dbgs() << " thisState: 0x" << utohexstr(thisState) << "\n"); - AddInsnClassStages(InsnClass, ComboBitToBitsMap, - numstages - 1, numstages, - thisState, thisState, - VisitedResourceStates, PossibleStates); - } -} - -void State::AddInsnClassStages(std::vector &InsnClass, - std::map &ComboBitToBitsMap, - unsigned chkstage, unsigned numstages, - unsigned prevState, unsigned origState, - DenseSet &VisitedResourceStates, - std::set &PossibleStates) const { - - assert((chkstage < numstages) && "AddInsnClassStages: stage out of range"); - unsigned thisStage = InsnClass[chkstage]; + // + // Iterate over all possible resources used in InsnClass. + // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}. + // - dbgsIndent((1 + numstages - chkstage) << 1); - DEBUG(dbgs() << "AddInsnClassStages " << chkstage - << " (0x" << utohexstr(thisStage) << ") from "); - dbgsInsnClass(InsnClass); - DEBUG(dbgs() << "\n"); - - // - // Iterate over all possible resources used in thisStage. - // For ex: for thisStage = 0x11, all resources = {0x01, 0x10}. - // - for (unsigned int j = 0; j < DFA_MAX_RESOURCES; ++j) { - unsigned resourceMask = (0x1 << j); - if (resourceMask & thisStage) { - unsigned combo = ComboBitToBitsMap[resourceMask]; - if (combo && ((~prevState & combo) != combo)) { - DEBUG(dbgs() << "\tSkipped Add 0x" << utohexstr(prevState) - << " - combo op 0x" << utohexstr(resourceMask) - << " (0x" << utohexstr(combo) <<") cannot be scheduled\n"); - continue; - } - // - // For each possible resource used in thisStage, generate the - // resource state if that resource was used. - // - unsigned ResultingResourceState = prevState | resourceMask | combo; - dbgsIndent((2 + numstages - chkstage) << 1); - DEBUG(dbgs() << "0x" << utohexstr(prevState) - << " | 0x" << utohexstr(resourceMask)); - if (combo) { - DEBUG(dbgs() << " | 0x" << utohexstr(combo)); - } - DEBUG(dbgs() << " = 0x" << utohexstr(ResultingResourceState) << " "); - - // - // If this is the final stage for this class - // - if (chkstage == 0) { + DenseSet VisitedResourceStates; + for (unsigned int j = 0; j < sizeof(InsnClass) * 8; ++j) { + if ((0x1 << j) & InsnClass) { + // + // For each possible resource used in InsnClass, generate the + // resource state if that resource was used. + // + unsigned ResultingResourceState = thisState | (0x1 << j); // // Check if the resulting resource state can be accommodated in this // packet. - // We compute resource OR prevState (originally started as origState). - // If the result of the OR is different than origState, it implies + // We compute ResultingResourceState OR thisState. + // If the result of the OR is different than thisState, it implies // that there is at least one resource that can be used to schedule - // thisStage in the current packet. + // InsnClass in the current packet. // Insert ResultingResourceState into PossibleStates only if we haven't // processed ResultingResourceState before. // - if (ResultingResourceState != prevState) { - if (VisitedResourceStates.count(ResultingResourceState) == 0) { - VisitedResourceStates.insert(ResultingResourceState); - PossibleStates.insert(ResultingResourceState); - DEBUG(dbgs() << "\tResultingResourceState: 0x" - << utohexstr(ResultingResourceState) << "\n"); - } else { - DEBUG(dbgs() << "\tSkipped Add - state already seen\n"); - } - } else { - DEBUG(dbgs() << "\tSkipped Add - no final resources available\n"); - } - } else { - // - // If the current resource can be accommodated, check the next - // stage in InsnClass for available resources. - // - if (ResultingResourceState != prevState) { - DEBUG(dbgs() << "\n"); - AddInsnClassStages(InsnClass, ComboBitToBitsMap, - chkstage - 1, numstages, - ResultingResourceState, origState, - VisitedResourceStates, PossibleStates); - } else { - DEBUG(dbgs() << "\tSkipped Add - no resources available\n"); + if ((ResultingResourceState != thisState) && + (VisitedResourceStates.count(ResultingResourceState) == 0)) { + VisitedResourceStates.insert(ResultingResourceState); + PossibleStates.insert(ResultingResourceState); } } } } + } // -// canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass -// may be a valid transition from this state i.e., can an instruction of type -// InsnClass be added to the packet represented by this state. +// canAddInsnClass - Quickly verifies if an instruction of type InsnClass is a +// valid transition from this state i.e., can an instruction of type InsnClass +// be added to the packet represented by this state. // -// Note that this routine is performing conservative checks that can be -// quickly executed acting as a filter before calling AddInsnClassStages. -// Any cases allowed through here will be caught later in AddInsnClassStages -// which performs the more expensive exact check. -// -bool State::canMaybeAddInsnClass(std::vector &InsnClass, - std::map &ComboBitToBitsMap) const { +bool State::canAddInsnClass(unsigned InsnClass) const { for (std::set::const_iterator SI = stateInfo.begin(); SI != stateInfo.end(); ++SI) { - - // Check to see if all required resources are available. - bool available = true; - - // Inspect each stage independently. - // note: This is a conservative check as we aren't checking for - // possible resource competition between the stages themselves - // The full cross product is examined later in AddInsnClass. - for (unsigned i = 0; i < InsnClass.size(); ++i) { - unsigned resources = *SI; - if ((~resources & InsnClass[i]) == 0) { - available = false; - break; - } - // Make sure _all_ resources for a combo function are available. - // note: This is a quick conservative check as it won't catch an - // unscheduleable combo if this stage is an OR expression - // containing a combo. - // These cases are caught later in AddInsnClass. - unsigned combo = ComboBitToBitsMap[InsnClass[i]]; - if (combo && ((~resources & combo) != combo)) { - DEBUG(dbgs() << "\tSkipped canMaybeAdd 0x" << utohexstr(resources) - << " - combo op 0x" << utohexstr(InsnClass[i]) - << " (0x" << utohexstr(combo) <<") cannot be scheduled\n"); - available = false; - break; - } - } - - if (available) { + if (~*SI & InsnClass) return true; - } } return false; } @@ -460,6 +244,7 @@ const State &DFA::newState() { return *IterPair.first; } + int State::currentStateNum = 0; DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): @@ -478,100 +263,57 @@ DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): // the ith state. // // -void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName, - int numInsnClasses, - int maxResources, int numCombos, int maxStages) { - - unsigned numStates = states.size(); - - DEBUG(dbgs() << "-----------------------------------------------------------------------------\n"); - DEBUG(dbgs() << "writeTableAndAPI\n"); - DEBUG(dbgs() << "Total states: " << numStates << "\n"); - - OS << "namespace llvm {\n"; - - OS << "\n// Input format:\n"; - OS << "#define DFA_MAX_RESTERMS " << DFA_MAX_RESTERMS - << "\t// maximum AND'ed resource terms\n"; - OS << "#define DFA_MAX_RESOURCES " << DFA_MAX_RESOURCES - << "\t// maximum resource bits in one term\n"; - - OS << "\n// " << TargetName << "DFAStateInputTable[][2] = " - << "pairs of for all valid\n"; - OS << "// transitions.\n"; - OS << "// " << numStates << "\tstates\n"; - OS << "// " << numInsnClasses << "\tinstruction classes\n"; - OS << "// " << maxResources << "\tresources max\n"; - OS << "// " << numCombos << "\tcombo resources\n"; - OS << "// " << maxStages << "\tstages max\n"; - OS << "const " << DFA_TBLTYPE << " " - << TargetName << "DFAStateInputTable[][2] = {\n"; - +void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { + static const std::string SentinelEntry = "{-1, -1}"; + DFA::StateSet::iterator SI = states.begin(); // This table provides a map to the beginning of the transitions for State s // in DFAStateInputTable. - std::vector StateEntry(numStates+1); - static const std::string SentinelEntry = "{-1, -1}"; + std::vector StateEntry(states.size()); + + OS << "namespace llvm {\n\n"; + OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n"; // Tracks the total valid transitions encountered so far. It is used // to construct the StateEntry table. int ValidTransitions = 0; - DFA::StateSet::iterator SI = states.begin(); - for (unsigned i = 0; i < numStates; ++i, ++SI) { + for (unsigned i = 0; i < states.size(); ++i, ++SI) { assert ((SI->stateNum == (int) i) && "Mismatch in state numbers"); StateEntry[i] = ValidTransitions; for (State::TransitionMap::iterator II = SI->Transitions.begin(), IE = SI->Transitions.end(); II != IE; ++II) { - OS << "{0x" << utohexstr(DFAPacketizer::getInsnInput(II->first)) << ", " + OS << "{" << II->first << ", " << II->second->stateNum - << "},\t"; + << "}, "; } ValidTransitions += SI->Transitions.size(); // If there are no valid transitions from this stage, we need a sentinel // transition. if (ValidTransitions == StateEntry[i]) { - OS << SentinelEntry << ",\t"; + OS << SentinelEntry << ","; ++ValidTransitions; } - OS << " // state " << i << ": " << StateEntry[i]; - if (StateEntry[i] != (ValidTransitions-1)) { // More than one transition. - OS << "-" << (ValidTransitions-1); - } OS << "\n"; } // Print out a sentinel entry at the end of the StateInputTable. This is // needed to iterate over StateInputTable in DFAPacketizer::ReadTable() - OS << SentinelEntry << "\t"; - OS << " // state " << numStates << ": " << ValidTransitions; - OS << "\n"; - + OS << SentinelEntry << "\n"; + OS << "};\n\n"; - OS << "// " << TargetName << "DFAStateEntryTable[i] = " - << "Index of the first entry in DFAStateInputTable for\n"; - OS << "// " - << "the ith state.\n"; - OS << "// " << numStates << " states\n"; OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; // Multiply i by 2 since each entry in DFAStateInputTable is a set of // two numbers. - unsigned lastState = 0; - for (unsigned i = 0; i < numStates; ++i) { - if (i && ((i % 10) == 0)) { - lastState = i-1; - OS << " // states " << (i-10) << ":" << lastState << "\n"; - } + for (unsigned i = 0; i < states.size(); ++i) OS << StateEntry[i] << ", "; - } // Print out the index to the sentinel entry in StateInputTable OS << ValidTransitions << ", "; - OS << " // states " << (lastState+1) << ":" << numStates << "\n"; - OS << "};\n"; + OS << "\n};\n"; OS << "} // namespace\n"; @@ -590,123 +332,40 @@ void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName, // -// collectAllFuncUnits - Construct a map of function unit names to bits. +// collectAllInsnClasses - Populate allInsnClasses which is a set of units +// used in each stage. // -int DFAPacketizerEmitter::collectAllFuncUnits( - std::vector &ProcItinList, - std::map &FUNameToBitsMap, - int &maxFUs, - raw_ostream &OS) { - DEBUG(dbgs() << "-----------------------------------------------------------------------------\n"); - DEBUG(dbgs() << "collectAllFuncUnits"); - DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n"); +void DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name, + Record *ItinData, + unsigned &NStages, + raw_ostream &OS) { + // Collect processor itineraries. + std::vector ProcItinList = + Records.getAllDerivedDefinitions("ProcessorItineraries"); + + // If just no itinerary then don't bother. + if (ProcItinList.size() < 2) + return; + std::map NameToBitsMap; - int totalFUs = 0; // Parse functional units for all the itineraries. for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { Record *Proc = ProcItinList[i]; - const std::string &ProcName = Proc->getName(); std::vector FUs = Proc->getValueAsListOfDefs("FU"); - DEBUG(dbgs() << " FU:" << i - << " (" << FUs.size() << " FUs) " - << ProcName); - - - // Convert macros to bits for each stage. - unsigned numFUs = FUs.size(); - for (unsigned j = 0; j < numFUs; ++j) { - assert ((j < DFA_MAX_RESOURCES) && - "Exceeded maximum number of representable resources"); - unsigned FuncResources = (unsigned) (1U << j); - FUNameToBitsMap[FUs[j]->getName()] = FuncResources; - DEBUG(dbgs() << " " << FUs[j]->getName() - << ":0x" << utohexstr(FuncResources)); - } - if (((int) numFUs) > maxFUs) { - maxFUs = numFUs; - } - totalFUs += numFUs; - DEBUG(dbgs() << "\n"); - } - return totalFUs; -} - -// -// collectAllComboFuncs - Construct a map from a combo function unit bit to -// the bits of all included functional units. -// -int DFAPacketizerEmitter::collectAllComboFuncs( - std::vector &ComboFuncList, - std::map &FUNameToBitsMap, - std::map &ComboBitToBitsMap, - raw_ostream &OS) { - DEBUG(dbgs() << "-----------------------------------------------------------------------------\n"); - DEBUG(dbgs() << "collectAllComboFuncs"); - DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n"); - - int numCombos = 0; - for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) { - Record *Func = ComboFuncList[i]; - const std::string &ProcName = Func->getName(); - std::vector FUs = Func->getValueAsListOfDefs("CFD"); - - DEBUG(dbgs() << " CFD:" << i - << " (" << FUs.size() << " combo FUs) " - << ProcName << "\n"); - // Convert macros to bits for each stage. - for (unsigned j = 0, N = FUs.size(); j < N; ++j) { - assert ((j < DFA_MAX_RESOURCES) && - "Exceeded maximum number of DFA resources"); - Record *FuncData = FUs[j]; - Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc"); - const std::vector &FuncList = - FuncData->getValueAsListOfDefs("FuncList"); - std::string ComboFuncName = ComboFunc->getName(); - unsigned ComboBit = FUNameToBitsMap[ComboFuncName]; - unsigned ComboResources = ComboBit; - DEBUG(dbgs() << " combo: " << ComboFuncName - << ":0x" << utohexstr(ComboResources) << "\n"); - for (unsigned k = 0, M = FuncList.size(); k < M; ++k) { - std::string FuncName = FuncList[k]->getName(); - unsigned FuncResources = FUNameToBitsMap[FuncName]; - DEBUG(dbgs() << " " << FuncName - << ":0x" << utohexstr(FuncResources) << "\n"); - ComboResources |= FuncResources; - } - ComboBitToBitsMap[ComboBit] = ComboResources; - numCombos++; - DEBUG(dbgs() << " => combo bits: " << ComboFuncName << ":0x" - << utohexstr(ComboBit) << " = 0x" - << utohexstr(ComboResources) << "\n"); - } + for (unsigned i = 0, N = FUs.size(); i < N; ++i) + NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); } - return numCombos; -} - - -// -// collectOneInsnClass - Populate allInsnClasses with one instruction class -// -int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName, - std::vector &ProcItinList, - std::map &FUNameToBitsMap, - Record *ItinData, - raw_ostream &OS) { - // Collect instruction classes. - Record *ItinDef = ItinData->getValueAsDef("TheClass"); const std::vector &StageList = ItinData->getValueAsListOfDefs("Stages"); // The number of stages. - unsigned NStages = StageList.size(); + NStages = StageList.size(); - DEBUG(dbgs() << " " << ItinDef->getName() - << "\n"); - - std::vector UnitBits; + // For each unit. + unsigned UnitBitValue = 0; // Compute the bitwise or of each unit used in this stage. for (unsigned i = 0; i < NStages; ++i) { @@ -716,72 +375,18 @@ int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName, const std::vector &UnitList = Stage->getValueAsListOfDefs("Units"); - DEBUG(dbgs() << " stage:" << i - << " [" << UnitList.size() << " units]:"); - unsigned dbglen = 26; // cursor after stage dbgs - - // Compute the bitwise or of each unit used in this stage. - unsigned UnitBitValue = 0; for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { // Conduct bitwise or. std::string UnitName = UnitList[j]->getName(); - DEBUG(dbgs() << " " << j << ":" << UnitName); - dbglen += 3 + UnitName.length(); - assert(FUNameToBitsMap.count(UnitName)); - UnitBitValue |= FUNameToBitsMap[UnitName]; + assert(NameToBitsMap.count(UnitName)); + UnitBitValue |= NameToBitsMap[UnitName]; } if (UnitBitValue != 0) - UnitBits.push_back(UnitBitValue); - - while (dbglen <= 64) { // line up bits dbgs - dbglen += 8; - DEBUG(dbgs() << "\t"); - } - DEBUG(dbgs() << " (bits: 0x" << utohexstr(UnitBitValue) << ")\n"); + allInsnClasses.insert(UnitBitValue); } - - if (UnitBits.size() > 0) - allInsnClasses.push_back(UnitBits); - - DEBUG(dbgs() << " "); - dbgsInsnClass(UnitBits); - DEBUG(dbgs() << "\n"); - - return NStages; } -// -// collectAllInsnClasses - Populate allInsnClasses which is a set of units -// used in each stage. -// -int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName, - std::vector &ProcItinList, - std::map &FUNameToBitsMap, - std::vector &ItinDataList, - int &maxStages, - raw_ostream &OS) { - // Collect all instruction classes. - unsigned M = ItinDataList.size(); - - int numInsnClasses = 0; - DEBUG(dbgs() << "-----------------------------------------------------------------------------\n" - << "collectAllInsnClasses " - << ProcName - << " (" << M << " classes)\n"); - - // Collect stages for each instruction class for all itinerary data - for (unsigned j = 0; j < M; j++) { - Record *ItinData = ItinDataList[j]; - int NStages = collectOneInsnClass(ProcName, ProcItinList, - FUNameToBitsMap, ItinData, OS); - if (NStages > maxStages) { - maxStages = NStages; - } - numInsnClasses++; - } - return numInsnClasses; -} // // Run the worklist algorithm to generate the DFA. @@ -793,35 +398,16 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) { Records.getAllDerivedDefinitions("ProcessorItineraries"); // - // Collect the Functional units. + // Collect the instruction classes. // - std::map FUNameToBitsMap; - int maxResources = 0; - collectAllFuncUnits(ProcItinList, - FUNameToBitsMap, maxResources, OS); - - // - // Collect the Combo Functional units. - // - std::map ComboBitToBitsMap; - std::vector ComboFuncList = - Records.getAllDerivedDefinitions("ComboFuncUnits"); - int numCombos = collectAllComboFuncs(ComboFuncList, - FUNameToBitsMap, ComboBitToBitsMap, OS); - - // - // Collect the itineraries. - // - int maxStages = 0; - int numInsnClasses = 0; for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { Record *Proc = ProcItinList[i]; // Get processor itinerary name. - const std::string &ProcName = Proc->getName(); + const std::string &Name = Proc->getName(); // Skip default. - if (ProcName == "NoItineraries") + if (Name == "NoItineraries") continue; // Sanity check for at least one instruction itinerary class. @@ -833,11 +419,15 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) { // Get itinerary data list. std::vector ItinDataList = Proc->getValueAsListOfDefs("IID"); - // Collect all instruction classes - numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList, - FUNameToBitsMap, ItinDataList, maxStages, OS); + // Collect instruction classes for all itinerary data. + for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { + Record *ItinData = ItinDataList[j]; + unsigned NStages; + collectAllInsnClasses(Name, ItinData, NStages, OS); + } } + // // Run a worklist algorithm to generate the DFA. // @@ -846,7 +436,6 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) { Initial->isInitial = true; Initial->stateInfo.insert(0x0); SmallVector WorkList; -// std::queue WorkList; std::map, const State*> Visited; WorkList.push_back(Initial); @@ -870,15 +459,9 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) { // while (!WorkList.empty()) { const State *current = WorkList.pop_back_val(); - DEBUG(dbgs() << "---------------------\n"); - DEBUG(dbgs() << "Processing state: " << current->stateNum << " - "); - dbgsStateInfo(current->stateInfo); - DEBUG(dbgs() << "\n"); - for (unsigned i = 0; i < allInsnClasses.size(); i++) { - std::vector InsnClass = allInsnClasses[i]; - DEBUG(dbgs() << i << " "); - dbgsInsnClass(InsnClass); - DEBUG(dbgs() << "\n"); + for (DenseSet::iterator CI = allInsnClasses.begin(), + CE = allInsnClasses.end(); CI != CE; ++CI) { + unsigned InsnClass = *CI; std::set NewStateResources; // @@ -886,47 +469,32 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) { // and the state can accommodate this InsnClass, create a transition. // if (!current->hasTransition(InsnClass) && - current->canMaybeAddInsnClass(InsnClass, ComboBitToBitsMap)) { - const State *NewState = NULL; - current->AddInsnClass(InsnClass, ComboBitToBitsMap, NewStateResources); - if (NewStateResources.size() == 0) { - DEBUG(dbgs() << " Skipped - no new states generated\n"); - continue; - } - - DEBUG(dbgs() << "\t"); - dbgsStateInfo(NewStateResources); - DEBUG(dbgs() << "\n"); + current->canAddInsnClass(InsnClass)) { + const State *NewState; + current->AddInsnClass(InsnClass, NewStateResources); + assert(!NewStateResources.empty() && "New states must be generated"); // // If we have seen this state before, then do not create a new state. // + // auto VI = Visited.find(NewStateResources); - if (VI != Visited.end()) { + if (VI != Visited.end()) NewState = VI->second; - DEBUG(dbgs() << "\tFound existing state: " - << NewState->stateNum << " - "); - dbgsStateInfo(NewState->stateInfo); - DEBUG(dbgs() << "\n"); - } else { + else { NewState = &D.newState(); NewState->stateInfo = NewStateResources; Visited[NewStateResources] = NewState; WorkList.push_back(NewState); - DEBUG(dbgs() << "\tAccepted new state: " - << NewState->stateNum << " - "); - dbgsStateInfo(NewState->stateInfo); - DEBUG(dbgs() << "\n"); } - + current->addTransition(InsnClass, NewState); } } } // Print out the table. - D.writeTableAndAPI(OS, TargetName, - numInsnClasses, maxResources, numCombos, maxStages); + D.writeTableAndAPI(OS, TargetName); } namespace llvm { -- 2.34.1