diff options
Diffstat (limited to 'utils/TableGen/DFAPacketizerEmitter.cpp')
| -rw-r--r-- | utils/TableGen/DFAPacketizerEmitter.cpp | 125 |
1 files changed, 97 insertions, 28 deletions
diff --git a/utils/TableGen/DFAPacketizerEmitter.cpp b/utils/TableGen/DFAPacketizerEmitter.cpp index 4abf54ebae2e..8bfecead6d2e 100644 --- a/utils/TableGen/DFAPacketizerEmitter.cpp +++ b/utils/TableGen/DFAPacketizerEmitter.cpp @@ -15,14 +15,47 @@ // //===----------------------------------------------------------------------===// -#include "llvm/TableGen/Record.h" #include "CodeGenTarget.h" -#include "DFAPacketizerEmitter.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/TableGen/Record.h" +#include "llvm/TableGen/TableGenBackend.h" #include <list> - +#include <map> +#include <string> 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<unsigned> 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 // a set of instruction classes. @@ -61,7 +94,12 @@ class State { // PossibleStates is the set of valid resource states that ensue from valid // transitions. // - bool canAddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates); + 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<unsigned> &PossibleStates); }; } // End anonymous namespace. @@ -87,6 +125,10 @@ namespace { struct ltState { bool operator()(const State *s1, const State *s2) const; }; + +struct ltTransition { + bool operator()(const Transition *s1, const Transition *s2) const; +}; } // End anonymous namespace. @@ -102,7 +144,8 @@ public: std::set<State*, ltState> states; // Map from a state to the list of transitions with that state as source. - std::map<State*, SmallVector<Transition*, 16>, ltState> stateTransitions; + std::map<State*, std::set<Transition*, ltTransition>, ltState> + stateTransitions; State *currentState; // Highest valued Input seen. @@ -160,21 +203,19 @@ bool ltState::operator()(const State *s1, const State *s2) const { return (s1->stateNum < s2->stateNum); } +bool ltTransition::operator()(const Transition *s1, const Transition *s2) const { + return (s1->input < s2->input); +} // -// 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. +// AddInsnClass - Return all combinations of resource reservation +// which are possible from this state (PossibleStates). // -bool State::canAddInsnClass(unsigned InsnClass, +void State::AddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates) { // // Iterate over all resource states in currentState. // - bool AddedState = false; for (std::set<unsigned>::iterator SI = stateInfo.begin(); SI != stateInfo.end(); ++SI) { @@ -207,13 +248,26 @@ bool State::canAddInsnClass(unsigned InsnClass, (VisitedResourceStates.count(ResultingResourceState) == 0)) { VisitedResourceStates.insert(ResultingResourceState); PossibleStates.insert(ResultingResourceState); - AddedState = true; } } } } - return AddedState; +} + + +// +// 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. +// +bool State::canAddInsnClass(unsigned InsnClass) const { + for (std::set<unsigned>::const_iterator SI = stateInfo.begin(); + SI != stateInfo.end(); ++SI) { + if (~*SI & InsnClass) + return true; + } + return false; } @@ -234,7 +288,9 @@ void DFA::addTransition(Transition *T) { LargestInput = T->input; // Add the new transition. - stateTransitions[T->from].push_back(T); + bool Added = stateTransitions[T->from].insert(T).second; + assert(Added && "Cannot have multiple states for the same input"); + (void)Added; } @@ -248,11 +304,13 @@ State *DFA::getTransition(State *From, unsigned I) { return NULL; // Do we have a transition from state From with Input I? - for (SmallVector<Transition*, 16>::iterator VI = - stateTransitions[From].begin(); - VI != stateTransitions[From].end(); ++VI) - if ((*VI)->input == I) - return (*VI)->to; + Transition TVal(NULL, I, NULL); + // Do not count this temporal instance + Transition::currentTransitionNum--; + std::set<Transition*, ltTransition>::iterator T = + stateTransitions[From].find(&TVal); + if (T != stateTransitions[From].end()) + return (*T)->to; return NULL; } @@ -266,7 +324,7 @@ bool DFA::isValidTransition(State *From, unsigned InsnClass) { int State::currentStateNum = 0; int Transition::currentTransitionNum = 0; -DFAGen::DFAGen(RecordKeeper &R): +DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): TargetName(CodeGenTarget(R).getName()), allInsnClasses(), Records(R) {} @@ -298,11 +356,12 @@ void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { StateEntry[i] = ValidTransitions; for (unsigned j = 0; j <= LargestInput; ++j) { assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers"); - if (!isValidTransition(*SI, j)) + State *To = getTransition(*SI, j); + if (To == NULL) continue; OS << "{" << j << ", " - << getTransition(*SI, j)->stateNum + << To->stateNum << "}, "; ++ValidTransitions; } @@ -346,7 +405,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 +461,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<Record*> ProcItinList = @@ -482,8 +540,10 @@ void DFAGen::run(raw_ostream &OS) { // and the state can accommodate this InsnClass, create a transition. // if (!D.getTransition(current, InsnClass) && - current->canAddInsnClass(InsnClass, NewStateResources)) { + current->canAddInsnClass(InsnClass)) { State *NewState = NULL; + current->AddInsnClass(InsnClass, NewStateResources); + assert(NewStateResources.size() && "New states must be generated"); // // If we have seen this state before, then do not create a new state. @@ -510,3 +570,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 |