//
//===----------------------------------------------------------------------===//
-#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 <list>
#include <map>
#include <string>
-#include <queue>
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<unsigned> &InsnClass);
-//
-// dbgsStateInfo - When debugging, print the set of state info.
-//
-void dbgsStateInfo(const std::set<unsigned> &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.
// allInsnClasses is the set of all possible resources consumed by an
// InstrStage.
//
- std::vector<std::vector<unsigned>> allInsnClasses;
+ DenseSet<unsigned> allInsnClasses;
RecordKeeper &Records;
public:
DFAPacketizerEmitter(RecordKeeper &R);
//
- // collectAllFuncUnits - Construct a map of function unit names to bits.
- //
- int collectAllFuncUnits(std::vector<Record*> &ProcItinList,
- std::map<std::string, unsigned> &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<Record*> &ComboFuncList,
- std::map<std::string, unsigned> &FUNameToBitsMap,
- std::map<unsigned, unsigned> &ComboBitToBitsMap,
- raw_ostream &OS);
-
- //
- // collectOneInsnClass - Populate allInsnClasses with one instruction class.
- //
- int collectOneInsnClass(const std::string &ProcName,
- std::vector<Record*> &ProcItinList,
- std::map<std::string, unsigned> &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<Record*> &ProcItinList,
- std::map<std::string, unsigned> &FUNameToBitsMap,
- std::vector<Record*> &ItinDataList,
- int &maxStages,
- raw_ostream &OS);
+ void collectAllInsnClasses(const std::string &Name,
+ Record *ItinData,
+ unsigned &NStages,
+ raw_ostream &OS);
void run(raw_ostream &OS);
};
const int stateNum;
mutable bool isInitial;
mutable std::set<unsigned> stateInfo;
- typedef std::map<std::vector<unsigned>, const State *> TransitionMap;
+ typedef std::map<unsigned, const State *> TransitionMap;
mutable TransitionMap Transitions;
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<unsigned> &InsnClass,
- std::map<unsigned, unsigned> &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<unsigned> &InsnClass,
- std::map<unsigned, unsigned> &ComboBitToBitsMap,
- std::set<unsigned> &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<unsigned> &InsnClass,
- std::map<unsigned, unsigned> &ComboBitToBitsMap,
- unsigned chkstage, unsigned numstages,
- unsigned prevState, unsigned origState,
- DenseSet<unsigned> &VisitedResourceStates,
- std::set<unsigned> &PossibleStates) const;
- //
+ void AddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates) const;
+ //
// addTransition - Add a transition from this state given the input InsnClass
//
- void addTransition(std::vector<unsigned> 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<unsigned> InsnClass) const;
+ bool hasTransition(unsigned InsnClass) const;
};
} // End anonymous namespace.
//
// 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<unsigned> &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<unsigned> &stateInfo) {
- DEBUG(dbgs() << "StateInfo: ");
- unsigned i = 0;
- for (std::set<unsigned>::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
DFA::DFA(): currentState(nullptr) {}
-//
+//
// addTransition - Add a transition from this state given the input InsnClass
//
-void State::addTransition(std::vector<unsigned> 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;
// hasTransition - Returns true if there is a transition from this state
// given the input InsnClass
//
-bool State::hasTransition(std::vector<unsigned> InsnClass) const {
+bool State::hasTransition(unsigned InsnClass) const {
return Transitions.count(InsnClass) > 0;
}
// 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<unsigned> &InsnClass,
- std::map<unsigned, unsigned> &ComboBitToBitsMap,
- std::set<unsigned> &PossibleStates) const {
+void State::AddInsnClass(unsigned InsnClass,
+ std::set<unsigned> &PossibleStates) const {
//
// Iterate over all resource states in currentState.
//
- unsigned numstages = InsnClass.size();
- assert((numstages > 0) && "InsnClass has no stages");
for (std::set<unsigned>::iterator SI = stateInfo.begin();
SI != stateInfo.end(); ++SI) {
unsigned thisState = *SI;
- DenseSet<unsigned> VisitedResourceStates;
-
- DEBUG(dbgs() << " thisState: 0x" << utohexstr(thisState) << "\n");
- AddInsnClassStages(InsnClass, ComboBitToBitsMap,
- numstages - 1, numstages,
- thisState, thisState,
- VisitedResourceStates, PossibleStates);
- }
-}
-
-void State::AddInsnClassStages(std::vector<unsigned> &InsnClass,
- std::map<unsigned, unsigned> &ComboBitToBitsMap,
- unsigned chkstage, unsigned numstages,
- unsigned prevState, unsigned origState,
- DenseSet<unsigned> &VisitedResourceStates,
- std::set<unsigned> &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<unsigned> 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<unsigned> &InsnClass,
- std::map<unsigned, unsigned> &ComboBitToBitsMap) const {
+bool State::canAddInsnClass(unsigned InsnClass) const {
for (std::set<unsigned>::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;
}
return *IterPair.first;
}
+
int State::currentStateNum = 0;
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 <Input, NextState> 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<int> StateEntry(numStates+1);
- static const std::string SentinelEntry = "{-1, -1}";
+ std::vector<int> 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";
//
-// 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<Record*> &ProcItinList,
- std::map<std::string, unsigned> &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<Record*> ProcItinList =
+ Records.getAllDerivedDefinitions("ProcessorItineraries");
+
+ // If just no itinerary then don't bother.
+ if (ProcItinList.size() < 2)
+ return;
+ std::map<std::string, unsigned> 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<Record*> 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<Record*> &ComboFuncList,
- std::map<std::string, unsigned> &FUNameToBitsMap,
- std::map<unsigned, unsigned> &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<Record*> 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<Record*> &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<Record*> &ProcItinList,
- std::map<std::string, unsigned> &FUNameToBitsMap,
- Record *ItinData,
- raw_ostream &OS) {
- // Collect instruction classes.
- Record *ItinDef = ItinData->getValueAsDef("TheClass");
const std::vector<Record*> &StageList =
ItinData->getValueAsListOfDefs("Stages");
// The number of stages.
- unsigned NStages = StageList.size();
+ NStages = StageList.size();
- DEBUG(dbgs() << " " << ItinDef->getName()
- << "\n");
-
- std::vector<unsigned> 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) {
const std::vector<Record*> &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<Record*> &ProcItinList,
- std::map<std::string, unsigned> &FUNameToBitsMap,
- std::vector<Record*> &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.
Records.getAllDerivedDefinitions("ProcessorItineraries");
//
- // Collect the Functional units.
+ // Collect the instruction classes.
//
- std::map<std::string, unsigned> FUNameToBitsMap;
- int maxResources = 0;
- collectAllFuncUnits(ProcItinList,
- FUNameToBitsMap, maxResources, OS);
-
- //
- // Collect the Combo Functional units.
- //
- std::map<unsigned, unsigned> ComboBitToBitsMap;
- std::vector<Record*> 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.
// Get itinerary data list.
std::vector<Record*> 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.
//
Initial->isInitial = true;
Initial->stateInfo.insert(0x0);
SmallVector<const State*, 32> WorkList;
-// std::queue<State*> WorkList;
std::map<std::set<unsigned>, const State*> Visited;
WorkList.push_back(Initial);
//
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<unsigned> InsnClass = allInsnClasses[i];
- DEBUG(dbgs() << i << " ");
- dbgsInsnClass(InsnClass);
- DEBUG(dbgs() << "\n");
+ for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(),
+ CE = allInsnClasses.end(); CI != CE; ++CI) {
+ unsigned InsnClass = *CI;
std::set<unsigned> NewStateResources;
//
// 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 {
projects / oota-llvm.git / commitdiff