X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDFAPacketizerEmitter.cpp;h=2549c47c33187e11a41947b23f45374c6b51c5ca;hb=be5c1fd43fd1cef8a18f41978d147190b50f5510;hp=b5aeec61efd295051ec0fb53fd5638cfb7e65dda;hpb=dc81e5da271ed394e2029c83458773c4ae2fc5f4;p=oota-llvm.git diff --git a/utils/TableGen/DFAPacketizerEmitter.cpp b/utils/TableGen/DFAPacketizerEmitter.cpp index b5aeec61efd..2549c47c331 100644 --- a/utils/TableGen/DFAPacketizerEmitter.cpp +++ b/utils/TableGen/DFAPacketizerEmitter.cpp @@ -15,34 +15,68 @@ // //===----------------------------------------------------------------------===// -#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 // a set of instruction classes. // -// Specifically, currentState is a set of bit-masks +// Specifically, currentState is a set of bit-masks. // The nth bit in a bit-mask indicates whether the nth resource is being used // by this state. The set of bit-masks in a state represent the different // possible outcomes of transitioning to this state. -// For example: Consider a two resource architecture: Resource L and Resource M -// with three instruction classes: L, M, and L_or_M +// For example: consider a two resource architecture: resource L and resource M +// with three instruction classes: L, M, and L_or_M. // From the initial state (currentState = 0x00), if we add instruction class // L_or_M we will transition to a state with currentState = [0x01, 0x10]. This // represents the possible resource states that can result from adding a L_or_M // instruction // // 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] +// 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 { @@ -51,140 +85,122 @@ class State { int stateNum; bool isInitial; std::set stateInfo; + typedef std::map TransitionMap; + TransitionMap Transitions; State(); - State(const State& S); + 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 - // valid transition from this state i.e., can an instruction of type InsnClass - // be added to the packet represented by this state + // 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 + // 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); + // + // addTransition - Add a transition from this state given the input InsnClass + // + void addTransition(unsigned InsnClass, State *To); + // + // hasTransition - Returns true if there is a transition from this state + // given the input InsnClass + // + bool hasTransition(unsigned InsnClass); }; -} // End anonymous namespace - +} // End anonymous namespace. // -// class DFA: deterministic finite automaton for processor resource tracking +// class DFA: deterministic finite automaton for processor resource tracking. // namespace { class DFA { public: DFA(); + ~DFA(); - // Set of states. Need to keep this sorted to emit the transition table - std::set states; + // Set of states. Need to keep this sorted to emit the transition table. + 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; + State *currentState; // - // Modify the DFA + // Modify the DFA. // void initialize(); - void addState(State*); - void addTransition(Transition*); + void addState(State *); // - // 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); - + // writeTable: Print out a table representing the DFA. // - // isValidTransition: Predicate that checks if there is a valid transition - // from state From on input InsnClass - // - bool isValidTransition(State* From, unsigned InsnClass); - - // - // writeTable: Print out a table representing the DFA - // - void writeTableAndAPI(raw_ostream &OS, const std::string& ClassName); + void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName); }; -} // End anonymous namespace +} // End anonymous namespace. // -// Constructors for State, Transition, and DFA +// Constructors and destructors for State and DFA // State::State() : stateNum(currentStateNum++), isInitial(false) {} -State::State(const State& S) : +State::State(const State &S) : stateNum(currentStateNum++), isInitial(S.isInitial), stateInfo(S.stateInfo) {} +DFA::DFA(): currentState(NULL) {} -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); +DFA::~DFA() { + DeleteContainerPointers(states); } +// +// addTransition - Add a transition from this state given the input InsnClass +// +void State::addTransition(unsigned InsnClass, State *To) { + 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 // -// PossibleStates is the set of valid resource states that ensue from valid -// transitions +bool State::hasTransition(unsigned InsnClass) { + return Transitions.count(InsnClass) > 0; +} + +// +// 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) { // - // Iterate over all resource states in currentState + // Iterate over all resource states in currentState. // - bool AddedState = false; for (std::set::iterator SI = stateInfo.begin(); SI != stateInfo.end(); ++SI) { unsigned thisState = *SI; // - // Iterate over all possible resources used in InsnClass - // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10} + // Iterate over all possible resources used in InsnClass. + // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}. // DenseSet VisitedResourceStates; @@ -192,149 +208,137 @@ bool State::canAddInsnClass(unsigned InsnClass, if ((0x1 << j) & InsnClass) { // // For each possible resource used in InsnClass, generate the - // resource state if that resource was used + // 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 ResultingResourceState OR thisState + // packet. + // 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 - // InsnClass in the current packet + // InsnClass in the current packet. // Insert ResultingResourceState into PossibleStates only if we haven't - // processed ResultingResourceState before + // processed ResultingResourceState before. // if ((ResultingResourceState != thisState) && (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; +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; +} - // 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; +void DFA::initialize() { + assert(currentState && "Missing current state"); + currentState->isInitial = true; } -bool DFA::isValidTransition(State* From, unsigned InsnClass) { - return (getTransition(From, InsnClass) != NULL); +void DFA::addState(State *S) { + assert(!states.count(S) && "State already exists"); + states.insert(S); } int State::currentStateNum = 0; -int Transition::currentTransitionNum = 0; -DFAGen::DFAGen(RecordKeeper& R): +DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): TargetName(CodeGenTarget(R).getName()), allInsnClasses(), Records(R) {} // // writeTableAndAPI - Print out a table representing the DFA and the -// associated API to create a DFA packetizer +// associated API to create a DFA packetizer. // // Format: // DFAStateInputTable[][2] = pairs of for all valid -// transitions +// transitions. // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for -// the ith state +// the ith state. // // -void DFA::writeTableAndAPI(raw_ostream &OS, const std::string& TargetName) { - std::set::iterator SI = states.begin(); +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 i.e., + // in DFAStateInputTable. 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 + // 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 there are no valid transitions from this stage, we need a sentinel + // transition. + 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"; // Multiply i by 2 since each entry in DFAStateInputTable is a set of - // two numbers + // two numbers. 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"; // - // Emit DFA Packetizer tables if the target is a VLIW machine + // Emit DFA Packetizer tables if the target is a VLIW machine. // std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; OS << "namespace llvm {\n"; - OS << "DFAPacketizer* " << SubTargetClassName << "::" + OS << "DFAPacketizer *" << SubTargetClassName << "::" << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" << " return new DFAPacketizer(IID, " << TargetName << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; @@ -346,15 +350,15 @@ 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) { - // Collect processor itineraries + // Collect processor itineraries. std::vector ProcItinList = - Records.getAllDerivedDefinitions("ProcessorItineraries"); + Records.getAllDerivedDefinitions("ProcessorItineraries"); - // If just no itinerary then don't bother + // If just no itinerary then don't bother. if (ProcItinList.size() < 2) return; std::map NameToBitsMap; @@ -364,7 +368,7 @@ void DFAGen::collectAllInsnClasses(const std::string &Name, Record *Proc = ProcItinList[i]; std::vector FUs = Proc->getValueAsListOfDefs("FU"); - // Convert macros to bits for each stage + // Convert macros to bits for each stage. for (unsigned i = 0, N = FUs.size(); i < N; ++i) NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); } @@ -372,22 +376,22 @@ void DFAGen::collectAllInsnClasses(const std::string &Name, const std::vector &StageList = ItinData->getValueAsListOfDefs("Stages"); - // The number of stages + // The number of stages. NStages = StageList.size(); - // For each unit + // For each unit. unsigned UnitBitValue = 0; - // Compute the bitwise or of each unit used in this stage + // Compute the bitwise or of each unit used in this stage. for (unsigned i = 0; i < NStages; ++i) { const Record *Stage = StageList[i]; - // Get unit list + // Get unit list. const std::vector &UnitList = Stage->getValueAsListOfDefs("Units"); for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { - // Conduct bitwise or + // Conduct bitwise or. std::string UnitName = UnitList[j]->getName(); assert(NameToBitsMap.count(UnitName)); UnitBitValue |= NameToBitsMap[UnitName]; @@ -400,38 +404,37 @@ void DFAGen::collectAllInsnClasses(const std::string &Name, // -// Run the worklist algorithm to generate the DFA +// 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 + // Collect processor iteraries. std::vector ProcItinList = Records.getAllDerivedDefinitions("ProcessorItineraries"); // - // Collect the instruction classes + // Collect the instruction classes. // for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { Record *Proc = ProcItinList[i]; - // Get processor itinerary name + // Get processor itinerary name. const std::string &Name = Proc->getName(); - // Skip default + // Skip default. if (Name == "NoItineraries") continue; - // Sanity check for at least one instruction itinerary class + // Sanity check for at least one instruction itinerary class. unsigned NItinClasses = Records.getAllDerivedDefinitions("InstrItinClass").size(); if (NItinClasses == 0) return; - // Get itinerary data list + // Get itinerary data list. std::vector ItinDataList = Proc->getValueAsListOfDefs("IID"); - // Collect instruction classes for all itinerary data + // Collect instruction classes for all itinerary data. for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { Record *ItinData = ItinDataList[j]; unsigned NStages; @@ -441,10 +444,10 @@ void DFAGen::run(raw_ostream &OS) { // - // Run a worklist algorithm to generate the DFA + // Run a worklist algorithm to generate the DFA. // DFA D; - State* Initial = new State; + State *Initial = new State; Initial->isInitial = true; Initial->stateInfo.insert(0x0); D.addState(Initial); @@ -454,7 +457,7 @@ void DFAGen::run(raw_ostream &OS) { WorkList.push_back(Initial); // - // Worklist algorithm to create a DFA for processor resource tracking + // Worklist algorithm to create a DFA for processor resource tracking. // C = {set of InsnClasses} // Begin with initial node in worklist. Initial node does not have // any consumed resources, @@ -471,7 +474,7 @@ void DFAGen::run(raw_ostream &OS) { // Add S' to Visited // while (!WorkList.empty()) { - State* current = WorkList.pop_back_val(); + State *current = WorkList.pop_back_val(); for (DenseSet::iterator CI = allInsnClasses.begin(), CE = allInsnClasses.end(); CI != CE; ++CI) { unsigned InsnClass = *CI; @@ -479,14 +482,16 @@ void DFAGen::run(raw_ostream &OS) { std::set NewStateResources; // // If we haven't already created a transition for this input - // and the state can accommodate this InsnClass, create a transition + // 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)) { + 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 + // If we have seen this state before, then do not create a new state. // // std::map, State*>::iterator VI; @@ -499,14 +504,21 @@ void DFAGen::run(raw_ostream &OS) { Visited[NewStateResources] = NewState; WorkList.push_back(NewState); } - - Transition* NewTransition = new Transition(current, InsnClass, - NewState); - D.addTransition(NewTransition); + + current->addTransition(InsnClass, NewState); } } } - // Print out the table + // 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