X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDFAPacketizerEmitter.cpp;h=5060b6e9ce7c0b059fac364b563fa3b1a849ef68;hb=47f0e3f434e2e43f951c3a826c40906cb15b7285;hp=2862d0cefc14147cafe07dd2c9a867c4af1bef62;hpb=464f3a332f81364ee09794f9502f0b25671149c6;p=oota-llvm.git diff --git a/utils/TableGen/DFAPacketizerEmitter.cpp b/utils/TableGen/DFAPacketizerEmitter.cpp index 2862d0cefc1..5060b6e9ce7 100644 --- a/utils/TableGen/DFAPacketizerEmitter.cpp +++ b/utils/TableGen/DFAPacketizerEmitter.cpp @@ -15,15 +15,47 @@ // //===----------------------------------------------------------------------===// -#include "llvm/MC/MCInstrDesc.h" -#include "llvm/MC/MCInstrItineraries.h" -#include "llvm/TableGen/Record.h" #include "CodeGenTarget.h" -#include "DFAPacketizerEmitter.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/TableGen/Record.h" +#include "llvm/TableGen/TableGenBackend.h" #include - +#include +#include using namespace llvm; +// +// class DFAPacketizerEmitter: class that generates and prints out the DFA +// for resource tracking. +// +namespace { +class DFAPacketizerEmitter { +private: + std::string TargetName; + // + // allInsnClasses is the set of all possible resources consumed by an + // InstrStage. + // + DenseSet allInsnClasses; + RecordKeeper &Records; + +public: + DFAPacketizerEmitter(RecordKeeper &R); + + // + // collectAllInsnClasses: Populate allInsnClasses which is a set of units + // used in each stage. + // + void collectAllInsnClasses(const std::string &Name, + Record *ItinData, + unsigned &NStages, + raw_ostream &OS); + + void run(raw_ostream &OS); +}; +} // End anonymous namespace. + // // // State represents the usage of machine resources if the packet contains @@ -43,17 +75,26 @@ using namespace llvm; // Another way of thinking about this transition is we are mapping a NDFA with // two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10]. // +// A State instance also contains a collection of transitions from that state: +// a map from inputs to new states. // namespace { class State { public: static int currentStateNum; - int stateNum; - bool isInitial; - std::set stateInfo; + // stateNum is the only member used for equality/ordering, all other members + // can be mutated even in const State objects. + const int stateNum; + mutable bool isInitial; + mutable std::set stateInfo; + typedef std::map TransitionMap; + mutable TransitionMap Transitions; State(); - State(const State &S); + + bool operator<(const State &s) const { + return stateNum < s.stateNum; + } // // canAddInsnClass - Returns true if an instruction of type InsnClass is a @@ -63,35 +104,24 @@ class State { // PossibleStates is the set of valid resource states that ensue from valid // transitions. // - bool canAddInsnClass(unsigned InsnClass, std::set &PossibleStates); -}; -} // End anonymous namespace. - - -namespace { -struct Transition { - public: - static int currentTransitionNum; - int transitionNum; - State *from; - unsigned input; - State *to; - - Transition(State *from_, unsigned input_, State *to_); -}; -} // End anonymous namespace. - - -// -// Comparators to keep set of states sorted. -// -namespace { -struct ltState { - bool operator()(const State *s1, const State *s2) const; + bool canAddInsnClass(unsigned InsnClass) const; + // + // AddInsnClass - Return all combinations of resource reservation + // which are possible from this state (PossibleStates). + // + void AddInsnClass(unsigned InsnClass, std::set &PossibleStates) const; + // + // addTransition - Add a transition from this state given the input InsnClass + // + 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(unsigned InsnClass) const; }; } // End anonymous namespace. - // // class DFA: deterministic finite automaton for processor resource tracking. // @@ -101,33 +131,15 @@ public: DFA(); // Set of states. Need to keep this sorted to emit the transition table. - std::set states; + typedef std::set StateSet; + StateSet states; - // Map from a state to the list of transitions with that state as source. - std::map, ltState> stateTransitions; State *currentState; - // Highest valued Input seen. - unsigned LargestInput; - // // Modify the DFA. // - void initialize(); - void addState(State *); - void addTransition(Transition *); - - // - // getTransition - Return the state when a transition is made from - // State From with Input I. If a transition is not found, return NULL. - // - State *getTransition(State *, unsigned); - - // - // isValidTransition: Predicate that checks if there is a valid transition - // from state From on input InsnClass. - // - bool isValidTransition(State *From, unsigned InsnClass); + const State &newState(); // // writeTable: Print out a table representing the DFA. @@ -138,45 +150,39 @@ public: // -// Constructors for State, Transition, and DFA +// Constructors and destructors for State and DFA // State::State() : stateNum(currentStateNum++), isInitial(false) {} +DFA::DFA(): currentState(nullptr) {} -State::State(const State &S) : - stateNum(currentStateNum++), isInitial(S.isInitial), - stateInfo(S.stateInfo) {} - - -Transition::Transition(State *from_, unsigned input_, State *to_) : - transitionNum(currentTransitionNum++), from(from_), input(input_), - to(to_) {} - - -DFA::DFA() : - LargestInput(0) {} - - -bool ltState::operator()(const State *s1, const State *s2) const { - return (s1->stateNum < s2->stateNum); +// +// addTransition - Add a transition from this state given the input InsnClass +// +void State::addTransition(unsigned InsnClass, const State *To) const { + assert(!Transitions.count(InsnClass) && + "Cannot have multiple transitions for the same input"); + Transitions[InsnClass] = To; } - // -// 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. +// hasTransition - Returns true if there is a transition from this state +// given the input InsnClass +// +bool State::hasTransition(unsigned InsnClass) const { + return Transitions.count(InsnClass) > 0; +} + // -// PossibleStates is the set of valid resource states that ensue from valid -// transitions. +// AddInsnClass - Return all combinations of resource reservation +// which are possible from this state (PossibleStates). // -bool State::canAddInsnClass(unsigned InsnClass, - std::set &PossibleStates) { +void State::AddInsnClass(unsigned InsnClass, + std::set &PossibleStates) const { // // Iterate over all resource states in currentState. // - bool AddedState = false; for (std::set::iterator SI = stateInfo.begin(); SI != stateInfo.end(); ++SI) { @@ -209,66 +215,39 @@ bool State::canAddInsnClass(unsigned InsnClass, (VisitedResourceStates.count(ResultingResourceState) == 0)) { VisitedResourceStates.insert(ResultingResourceState); PossibleStates.insert(ResultingResourceState); - AddedState = true; } } } } - return AddedState; -} - - -void DFA::initialize() { - currentState->isInitial = true; -} - - -void DFA::addState(State *S) { - assert(!states.count(S) && "State already exists"); - states.insert(S); -} - - -void DFA::addTransition(Transition *T) { - // Update LargestInput. - if (T->input > LargestInput) - LargestInput = T->input; - - // Add the new transition. - stateTransitions[T->from].push_back(T); } // -// getTransition - Return the state when a transition is made from -// State From with Input I. If a transition is not found, return NULL. +// 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. // -State *DFA::getTransition(State *From, unsigned I) { - // Do we have a transition from state From? - if (!stateTransitions.count(From)) - return NULL; - - // Do we have a transition from state From with Input I? - for (SmallVector::iterator VI = - stateTransitions[From].begin(); - VI != stateTransitions[From].end(); ++VI) - if ((*VI)->input == I) - return (*VI)->to; - - return NULL; +bool State::canAddInsnClass(unsigned InsnClass) const { + for (std::set::const_iterator SI = stateInfo.begin(); + SI != stateInfo.end(); ++SI) { + if (~*SI & InsnClass) + return true; + } + return false; } -bool DFA::isValidTransition(State *From, unsigned InsnClass) { - return (getTransition(From, InsnClass) != NULL); +const State &DFA::newState() { + auto IterPair = states.insert(State()); + assert(IterPair.second && "State already exists"); + return *IterPair.first; } int State::currentStateNum = 0; -int Transition::currentTransitionNum = 0; -DFAGen::DFAGen(RecordKeeper &R): +DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): TargetName(CodeGenTarget(R).getName()), allInsnClasses(), Records(R) {} @@ -285,7 +264,8 @@ DFAGen::DFAGen(RecordKeeper &R): // // void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { - std::set::iterator SI = states.begin(); + 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(states.size()); @@ -297,25 +277,31 @@ void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { // to construct the StateEntry table. int ValidTransitions = 0; for (unsigned i = 0; i < states.size(); ++i, ++SI) { + assert ((SI->stateNum == (int) i) && "Mismatch in state numbers"); StateEntry[i] = ValidTransitions; - for (unsigned j = 0; j <= LargestInput; ++j) { - assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers"); - if (!isValidTransition(*SI, j)) - continue; - - OS << "{" << j << ", " - << getTransition(*SI, j)->stateNum + for (State::TransitionMap::iterator + II = SI->Transitions.begin(), IE = SI->Transitions.end(); + II != IE; ++II) { + OS << "{" << II->first << ", " + << II->second->stateNum << "}, "; - ++ValidTransitions; } + ValidTransitions += SI->Transitions.size(); // If there are no valid transitions from this stage, we need a sentinel // transition. - if (ValidTransitions == StateEntry[i]) - OS << "{-1, -1},"; + if (ValidTransitions == StateEntry[i]) { + OS << SentinelEntry << ","; + ++ValidTransitions; + } 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 << "\n"; + OS << "};\n\n"; OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; @@ -324,6 +310,9 @@ void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { for (unsigned i = 0; i < states.size(); ++i) OS << StateEntry[i] << ", "; + // Print out the index to the sentinel entry in StateInputTable + OS << ValidTransitions << ", "; + OS << "\n};\n"; OS << "} // namespace\n"; @@ -346,7 +335,7 @@ void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { // collectAllInsnClasses - Populate allInsnClasses which is a set of units // used in each stage. // -void DFAGen::collectAllInsnClasses(const std::string &Name, +void DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name, Record *ItinData, unsigned &NStages, raw_ostream &OS) { @@ -402,8 +391,7 @@ void DFAGen::collectAllInsnClasses(const std::string &Name, // // Run the worklist algorithm to generate the DFA. // -void DFAGen::run(raw_ostream &OS) { - EmitSourceFileHeader("Target DFA Packetizer Tables", OS); +void DFAPacketizerEmitter::run(raw_ostream &OS) { // Collect processor iteraries. std::vector ProcItinList = @@ -444,12 +432,11 @@ void DFAGen::run(raw_ostream &OS) { // Run a worklist algorithm to generate the DFA. // DFA D; - State *Initial = new State; + const State *Initial = &D.newState(); Initial->isInitial = true; Initial->stateInfo.insert(0x0); - D.addState(Initial); - SmallVector WorkList; - std::map, State*> Visited; + SmallVector WorkList; + std::map, const State*> Visited; WorkList.push_back(Initial); @@ -471,7 +458,7 @@ void DFAGen::run(raw_ostream &OS) { // Add S' to Visited // while (!WorkList.empty()) { - State *current = WorkList.pop_back_val(); + const State *current = WorkList.pop_back_val(); for (DenseSet::iterator CI = allInsnClasses.begin(), CE = allInsnClasses.end(); CI != CE; ++CI) { unsigned InsnClass = *CI; @@ -481,28 +468,27 @@ void DFAGen::run(raw_ostream &OS) { // If we haven't already created a transition for this input // and the state can accommodate this InsnClass, create a transition. // - if (!D.getTransition(current, InsnClass) && - current->canAddInsnClass(InsnClass, NewStateResources)) { - State *NewState = NULL; + if (!current->hasTransition(InsnClass) && + 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. // // - std::map, State*>::iterator VI; - if ((VI = Visited.find(NewStateResources)) != Visited.end()) + auto VI = Visited.find(NewStateResources); + if (VI != Visited.end()) NewState = VI->second; else { - NewState = new State; + NewState = &D.newState(); NewState->stateInfo = NewStateResources; - D.addState(NewState); Visited[NewStateResources] = NewState; WorkList.push_back(NewState); } - - Transition *NewTransition = new Transition(current, InsnClass, - NewState); - D.addTransition(NewTransition); + + current->addTransition(InsnClass, NewState); } } } @@ -510,3 +496,12 @@ void DFAGen::run(raw_ostream &OS) { // Print out the table. D.writeTableAndAPI(OS, TargetName); } + +namespace llvm { + +void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { + emitSourceFileHeader("Target DFA Packetizer Tables", OS); + DFAPacketizerEmitter(RK).run(OS); +} + +} // End llvm namespace