1 //===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine-----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This class parses the Schedule.td file and produces an API that can be used
11 // to reason about whether an instruction can be added to a packet on a VLIW
12 // architecture. The class internally generates a deterministic finite
13 // automaton (DFA) that models all possible mappings of machine instructions
14 // to functional units as instructions are added to a packet.
16 //===----------------------------------------------------------------------===//
18 #include "CodeGenTarget.h"
19 #include "llvm/ADT/DenseSet.h"
20 #include "llvm/TableGen/Record.h"
21 #include "llvm/TableGen/TableGenBackend.h"
28 // class DFAPacketizerEmitter: class that generates and prints out the DFA
29 // for resource tracking.
32 class DFAPacketizerEmitter {
34 std::string TargetName;
36 // allInsnClasses is the set of all possible resources consumed by an
39 DenseSet<unsigned> allInsnClasses;
40 RecordKeeper &Records;
43 DFAPacketizerEmitter(RecordKeeper &R);
46 // collectAllInsnClasses: Populate allInsnClasses which is a set of units
47 // used in each stage.
49 void collectAllInsnClasses(const std::string &Name,
54 void run(raw_ostream &OS);
56 } // End anonymous namespace.
60 // State represents the usage of machine resources if the packet contains
61 // a set of instruction classes.
63 // Specifically, currentState is a set of bit-masks.
64 // The nth bit in a bit-mask indicates whether the nth resource is being used
65 // by this state. The set of bit-masks in a state represent the different
66 // possible outcomes of transitioning to this state.
67 // For example: consider a two resource architecture: resource L and resource M
68 // with three instruction classes: L, M, and L_or_M.
69 // From the initial state (currentState = 0x00), if we add instruction class
70 // L_or_M we will transition to a state with currentState = [0x01, 0x10]. This
71 // represents the possible resource states that can result from adding a L_or_M
74 // Another way of thinking about this transition is we are mapping a NDFA with
75 // two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10].
81 static int currentStateNum;
84 std::set<unsigned> stateInfo;
87 State(const State &S);
90 // canAddInsnClass - Returns true if an instruction of type InsnClass is a
91 // valid transition from this state, i.e., can an instruction of type InsnClass
92 // be added to the packet represented by this state.
94 // PossibleStates is the set of valid resource states that ensue from valid
97 bool canAddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates);
99 } // End anonymous namespace.
105 static int currentTransitionNum;
111 Transition(State *from_, unsigned input_, State *to_);
113 } // End anonymous namespace.
117 // Comparators to keep set of states sorted.
121 bool operator()(const State *s1, const State *s2) const;
123 } // End anonymous namespace.
127 // class DFA: deterministic finite automaton for processor resource tracking.
134 // Set of states. Need to keep this sorted to emit the transition table.
135 std::set<State*, ltState> states;
137 // Map from a state to the list of transitions with that state as source.
138 std::map<State*, SmallVector<Transition*, 16>, ltState> stateTransitions;
141 // Highest valued Input seen.
142 unsigned LargestInput;
148 void addState(State *);
149 void addTransition(Transition *);
152 // getTransition - Return the state when a transition is made from
153 // State From with Input I. If a transition is not found, return NULL.
155 State *getTransition(State *, unsigned);
158 // isValidTransition: Predicate that checks if there is a valid transition
159 // from state From on input InsnClass.
161 bool isValidTransition(State *From, unsigned InsnClass);
164 // writeTable: Print out a table representing the DFA.
166 void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName);
168 } // End anonymous namespace.
172 // Constructors for State, Transition, and DFA
175 stateNum(currentStateNum++), isInitial(false) {}
178 State::State(const State &S) :
179 stateNum(currentStateNum++), isInitial(S.isInitial),
180 stateInfo(S.stateInfo) {}
183 Transition::Transition(State *from_, unsigned input_, State *to_) :
184 transitionNum(currentTransitionNum++), from(from_), input(input_),
192 bool ltState::operator()(const State *s1, const State *s2) const {
193 return (s1->stateNum < s2->stateNum);
198 // canAddInsnClass - Returns true if an instruction of type InsnClass is a
199 // valid transition from this state i.e., can an instruction of type InsnClass
200 // be added to the packet represented by this state.
202 // PossibleStates is the set of valid resource states that ensue from valid
205 bool State::canAddInsnClass(unsigned InsnClass,
206 std::set<unsigned> &PossibleStates) {
208 // Iterate over all resource states in currentState.
210 bool AddedState = false;
212 for (std::set<unsigned>::iterator SI = stateInfo.begin();
213 SI != stateInfo.end(); ++SI) {
214 unsigned thisState = *SI;
217 // Iterate over all possible resources used in InsnClass.
218 // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}.
221 DenseSet<unsigned> VisitedResourceStates;
222 for (unsigned int j = 0; j < sizeof(InsnClass) * 8; ++j) {
223 if ((0x1 << j) & InsnClass) {
225 // For each possible resource used in InsnClass, generate the
226 // resource state if that resource was used.
228 unsigned ResultingResourceState = thisState | (0x1 << j);
230 // Check if the resulting resource state can be accommodated in this
232 // We compute ResultingResourceState OR thisState.
233 // If the result of the OR is different than thisState, it implies
234 // that there is at least one resource that can be used to schedule
235 // InsnClass in the current packet.
236 // Insert ResultingResourceState into PossibleStates only if we haven't
237 // processed ResultingResourceState before.
239 if ((ResultingResourceState != thisState) &&
240 (VisitedResourceStates.count(ResultingResourceState) == 0)) {
241 VisitedResourceStates.insert(ResultingResourceState);
242 PossibleStates.insert(ResultingResourceState);
253 void DFA::initialize() {
254 currentState->isInitial = true;
258 void DFA::addState(State *S) {
259 assert(!states.count(S) && "State already exists");
264 void DFA::addTransition(Transition *T) {
265 // Update LargestInput.
266 if (T->input > LargestInput)
267 LargestInput = T->input;
269 // Add the new transition.
270 stateTransitions[T->from].push_back(T);
275 // getTransition - Return the state when a transition is made from
276 // State From with Input I. If a transition is not found, return NULL.
278 State *DFA::getTransition(State *From, unsigned I) {
279 // Do we have a transition from state From?
280 if (!stateTransitions.count(From))
283 // Do we have a transition from state From with Input I?
284 for (SmallVector<Transition*, 16>::iterator VI =
285 stateTransitions[From].begin();
286 VI != stateTransitions[From].end(); ++VI)
287 if ((*VI)->input == I)
294 bool DFA::isValidTransition(State *From, unsigned InsnClass) {
295 return (getTransition(From, InsnClass) != NULL);
299 int State::currentStateNum = 0;
300 int Transition::currentTransitionNum = 0;
302 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R):
303 TargetName(CodeGenTarget(R).getName()),
304 allInsnClasses(), Records(R) {}
308 // writeTableAndAPI - Print out a table representing the DFA and the
309 // associated API to create a DFA packetizer.
312 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
314 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for
318 void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) {
319 std::set<State*, ltState>::iterator SI = states.begin();
320 // This table provides a map to the beginning of the transitions for State s
321 // in DFAStateInputTable.
322 std::vector<int> StateEntry(states.size());
324 OS << "namespace llvm {\n\n";
325 OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n";
327 // Tracks the total valid transitions encountered so far. It is used
328 // to construct the StateEntry table.
329 int ValidTransitions = 0;
330 for (unsigned i = 0; i < states.size(); ++i, ++SI) {
331 StateEntry[i] = ValidTransitions;
332 for (unsigned j = 0; j <= LargestInput; ++j) {
333 assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers");
334 if (!isValidTransition(*SI, j))
337 OS << "{" << j << ", "
338 << getTransition(*SI, j)->stateNum
343 // If there are no valid transitions from this stage, we need a sentinel
345 if (ValidTransitions == StateEntry[i]) {
353 OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n";
355 // Multiply i by 2 since each entry in DFAStateInputTable is a set of
357 for (unsigned i = 0; i < states.size(); ++i)
358 OS << StateEntry[i] << ", ";
361 OS << "} // namespace\n";
365 // Emit DFA Packetizer tables if the target is a VLIW machine.
367 std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
368 OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
369 OS << "namespace llvm {\n";
370 OS << "DFAPacketizer *" << SubTargetClassName << "::"
371 << "createDFAPacketizer(const InstrItineraryData *IID) const {\n"
372 << " return new DFAPacketizer(IID, " << TargetName
373 << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n";
374 OS << "} // End llvm namespace \n";
379 // collectAllInsnClasses - Populate allInsnClasses which is a set of units
380 // used in each stage.
382 void DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name,
386 // Collect processor itineraries.
387 std::vector<Record*> ProcItinList =
388 Records.getAllDerivedDefinitions("ProcessorItineraries");
390 // If just no itinerary then don't bother.
391 if (ProcItinList.size() < 2)
393 std::map<std::string, unsigned> NameToBitsMap;
395 // Parse functional units for all the itineraries.
396 for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) {
397 Record *Proc = ProcItinList[i];
398 std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU");
400 // Convert macros to bits for each stage.
401 for (unsigned i = 0, N = FUs.size(); i < N; ++i)
402 NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i);
405 const std::vector<Record*> &StageList =
406 ItinData->getValueAsListOfDefs("Stages");
408 // The number of stages.
409 NStages = StageList.size();
412 unsigned UnitBitValue = 0;
414 // Compute the bitwise or of each unit used in this stage.
415 for (unsigned i = 0; i < NStages; ++i) {
416 const Record *Stage = StageList[i];
419 const std::vector<Record*> &UnitList =
420 Stage->getValueAsListOfDefs("Units");
422 for (unsigned j = 0, M = UnitList.size(); j < M; ++j) {
423 // Conduct bitwise or.
424 std::string UnitName = UnitList[j]->getName();
425 assert(NameToBitsMap.count(UnitName));
426 UnitBitValue |= NameToBitsMap[UnitName];
429 if (UnitBitValue != 0)
430 allInsnClasses.insert(UnitBitValue);
436 // Run the worklist algorithm to generate the DFA.
438 void DFAPacketizerEmitter::run(raw_ostream &OS) {
440 // Collect processor iteraries.
441 std::vector<Record*> ProcItinList =
442 Records.getAllDerivedDefinitions("ProcessorItineraries");
445 // Collect the instruction classes.
447 for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) {
448 Record *Proc = ProcItinList[i];
450 // Get processor itinerary name.
451 const std::string &Name = Proc->getName();
454 if (Name == "NoItineraries")
457 // Sanity check for at least one instruction itinerary class.
458 unsigned NItinClasses =
459 Records.getAllDerivedDefinitions("InstrItinClass").size();
460 if (NItinClasses == 0)
463 // Get itinerary data list.
464 std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID");
466 // Collect instruction classes for all itinerary data.
467 for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) {
468 Record *ItinData = ItinDataList[j];
470 collectAllInsnClasses(Name, ItinData, NStages, OS);
476 // Run a worklist algorithm to generate the DFA.
479 State *Initial = new State;
480 Initial->isInitial = true;
481 Initial->stateInfo.insert(0x0);
483 SmallVector<State*, 32> WorkList;
484 std::map<std::set<unsigned>, State*> Visited;
486 WorkList.push_back(Initial);
489 // Worklist algorithm to create a DFA for processor resource tracking.
490 // C = {set of InsnClasses}
491 // Begin with initial node in worklist. Initial node does not have
492 // any consumed resources,
493 // ResourceState = 0x0
495 // While worklist != empty
496 // S = first element of worklist
497 // For every instruction class C
498 // if we can accommodate C in S:
499 // S' = state with resource states = {S Union C}
500 // Add a new transition: S x C -> S'
501 // If S' is not in Visited:
502 // Add S' to worklist
505 while (!WorkList.empty()) {
506 State *current = WorkList.pop_back_val();
507 for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(),
508 CE = allInsnClasses.end(); CI != CE; ++CI) {
509 unsigned InsnClass = *CI;
511 std::set<unsigned> NewStateResources;
513 // If we haven't already created a transition for this input
514 // and the state can accommodate this InsnClass, create a transition.
516 if (!D.getTransition(current, InsnClass) &&
517 current->canAddInsnClass(InsnClass, NewStateResources)) {
518 State *NewState = NULL;
521 // If we have seen this state before, then do not create a new state.
524 std::map<std::set<unsigned>, State*>::iterator VI;
525 if ((VI = Visited.find(NewStateResources)) != Visited.end())
526 NewState = VI->second;
528 NewState = new State;
529 NewState->stateInfo = NewStateResources;
530 D.addState(NewState);
531 Visited[NewStateResources] = NewState;
532 WorkList.push_back(NewState);
535 Transition *NewTransition = new Transition(current, InsnClass,
537 D.addTransition(NewTransition);
542 // Print out the table.
543 D.writeTableAndAPI(OS, TargetName);
548 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
549 emitSourceFileHeader("Target DFA Packetizer Tables", OS);
550 DFAPacketizerEmitter(RK).run(OS);
553 } // End llvm namespace