[llvm] [cmake] Add possibility to use ChooseMSVCCRT.cmake when include LLVM library
[llvm-core.git] / utils / TableGen / DFAPacketizerEmitter.cpp
blob8ac187e86ea36e1a50887980904df5b833a051c4
1 //===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This class parses the Schedule.td file and produces an API that can be used
10 // to reason about whether an instruction can be added to a packet on a VLIW
11 // architecture. The class internally generates a deterministic finite
12 // automaton (DFA) that models all possible mappings of machine instructions
13 // to functional units as instructions are added to a packet.
15 //===----------------------------------------------------------------------===//
17 #define DEBUG_TYPE "dfa-emitter"
19 #include "CodeGenTarget.h"
20 #include "llvm/ADT/DenseSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/StringExtras.h"
23 #include "llvm/TableGen/Record.h"
24 #include "llvm/TableGen/TableGenBackend.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include <cassert>
28 #include <cstdint>
29 #include <map>
30 #include <set>
31 #include <string>
32 #include <unordered_map>
33 #include <vector>
35 using namespace llvm;
37 // --------------------------------------------------------------------
38 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
40 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
41 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
43 // e.g. terms x resource bit combinations that fit in uint32_t:
44 // 4 terms x 8 bits = 32 bits
45 // 3 terms x 10 bits = 30 bits
46 // 2 terms x 16 bits = 32 bits
48 // e.g. terms x resource bit combinations that fit in uint64_t:
49 // 8 terms x 8 bits = 64 bits
50 // 7 terms x 9 bits = 63 bits
51 // 6 terms x 10 bits = 60 bits
52 // 5 terms x 12 bits = 60 bits
53 // 4 terms x 16 bits = 64 bits <--- current
54 // 3 terms x 21 bits = 63 bits
55 // 2 terms x 32 bits = 64 bits
57 #define DFA_MAX_RESTERMS 4 // The max # of AND'ed resource terms.
58 #define DFA_MAX_RESOURCES 16 // The max # of resource bits in one term.
60 typedef uint64_t DFAInput;
61 typedef int64_t DFAStateInput;
62 #define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable.
64 namespace {
66 DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
67 return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
70 /// Return the DFAInput for an instruction class input vector.
71 /// This function is used in both DFAPacketizer.cpp and in
72 /// DFAPacketizerEmitter.cpp.
73 DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
74 DFAInput InsnInput = 0;
75 assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
76 "Exceeded maximum number of DFA terms");
77 for (auto U : InsnClass)
78 InsnInput = addDFAFuncUnits(InsnInput, U);
79 return InsnInput;
82 } // end anonymous namespace
84 // --------------------------------------------------------------------
86 #ifndef NDEBUG
87 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
89 // dbgsInsnClass - When debugging, print instruction class stages.
91 void dbgsInsnClass(const std::vector<unsigned> &InsnClass);
93 // dbgsStateInfo - When debugging, print the set of state info.
95 void dbgsStateInfo(const std::set<unsigned> &stateInfo);
97 // dbgsIndent - When debugging, indent by the specified amount.
99 void dbgsIndent(unsigned indent);
100 #endif
103 // class DFAPacketizerEmitter: class that generates and prints out the DFA
104 // for resource tracking.
106 namespace {
108 class DFAPacketizerEmitter {
109 private:
110 std::string TargetName;
112 // allInsnClasses is the set of all possible resources consumed by an
113 // InstrStage.
115 std::vector<std::vector<unsigned>> allInsnClasses;
116 RecordKeeper &Records;
118 public:
119 DFAPacketizerEmitter(RecordKeeper &R);
122 // collectAllFuncUnits - Construct a map of function unit names to bits.
124 int collectAllFuncUnits(std::vector<Record*> &ProcItinList,
125 std::map<std::string, unsigned> &FUNameToBitsMap,
126 int &maxResources,
127 raw_ostream &OS);
130 // collectAllComboFuncs - Construct a map from a combo function unit bit to
131 // the bits of all included functional units.
133 int collectAllComboFuncs(std::vector<Record*> &ComboFuncList,
134 std::map<std::string, unsigned> &FUNameToBitsMap,
135 std::map<unsigned, unsigned> &ComboBitToBitsMap,
136 raw_ostream &OS);
139 // collectOneInsnClass - Populate allInsnClasses with one instruction class.
141 int collectOneInsnClass(const std::string &ProcName,
142 std::vector<Record*> &ProcItinList,
143 std::map<std::string, unsigned> &FUNameToBitsMap,
144 Record *ItinData,
145 raw_ostream &OS);
148 // collectAllInsnClasses - Populate allInsnClasses which is a set of units
149 // used in each stage.
151 int collectAllInsnClasses(const std::string &ProcName,
152 std::vector<Record*> &ProcItinList,
153 std::map<std::string, unsigned> &FUNameToBitsMap,
154 std::vector<Record*> &ItinDataList,
155 int &maxStages,
156 raw_ostream &OS);
158 // Emit code for a subset of itineraries.
159 void emitForItineraries(raw_ostream &OS,
160 std::vector<Record *> &ProcItinList,
161 std::string DFAName);
163 void run(raw_ostream &OS);
167 // State represents the usage of machine resources if the packet contains
168 // a set of instruction classes.
170 // Specifically, currentState is a set of bit-masks.
171 // The nth bit in a bit-mask indicates whether the nth resource is being used
172 // by this state. The set of bit-masks in a state represent the different
173 // possible outcomes of transitioning to this state.
174 // For example: consider a two resource architecture: resource L and resource M
175 // with three instruction classes: L, M, and L_or_M.
176 // From the initial state (currentState = 0x00), if we add instruction class
177 // L_or_M we will transition to a state with currentState = [0x01, 0x10]. This
178 // represents the possible resource states that can result from adding a L_or_M
179 // instruction
181 // Another way of thinking about this transition is we are mapping a NDFA with
182 // two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10].
184 // A State instance also contains a collection of transitions from that state:
185 // a map from inputs to new states.
187 class State {
188 public:
189 static int currentStateNum;
190 // stateNum is the only member used for equality/ordering, all other members
191 // can be mutated even in const State objects.
192 const int stateNum;
193 mutable bool isInitial;
194 mutable std::set<unsigned> stateInfo;
196 struct TransitionInfo {
197 // Maps from a resource bitmask in this state to the equivalent resource
198 // bitmap in the transitioned-to state. This is a 1-to-N mapping.
199 std::vector<std::pair<unsigned, unsigned>> ResourceTransitions;
200 const State *S;
202 using TransitionMap = std::map<std::vector<unsigned>, TransitionInfo>;
203 mutable TransitionMap Transitions;
205 State();
207 bool operator<(const State &s) const {
208 return stateNum < s.stateNum;
212 // canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass
213 // may be a valid transition from this state i.e., can an instruction of type
214 // InsnClass be added to the packet represented by this state.
216 // Note that for multiple stages, this quick check does not take into account
217 // any possible resource competition between the stages themselves. That is
218 // enforced in AddInsnClassStages which checks the cross product of all
219 // stages for resource availability (which is a more involved check).
221 bool canMaybeAddInsnClass(std::vector<unsigned> &InsnClass,
222 std::map<unsigned, unsigned> &ComboBitToBitsMap) const;
225 // AddInsnClass - Return all combinations of resource reservation
226 // which are possible from this state (PossibleStates).
228 // PossibleStates is the set of valid resource states that ensue from valid
229 // transitions.
231 // TransitionInfo maps from a resource bitmask B in this state to a resource
232 // bitmask B' in PossibleStates. This is a one-to-many (or none) mapping.
234 void AddInsnClass(
235 std::vector<unsigned> &InsnClass,
236 std::map<unsigned, unsigned> &ComboBitToBitsMap,
237 std::set<unsigned> &PossibleStates,
238 std::vector<std::pair<unsigned, unsigned>> &TransitionInfo) const;
241 // AddInsnClassStages - Return all combinations of resource reservation
242 // resulting from the cross product of all stages for this InsnClass
243 // which are possible from this state (PossibleStates).
245 void AddInsnClassStages(std::vector<unsigned> &InsnClass,
246 std::map<unsigned, unsigned> &ComboBitToBitsMap,
247 unsigned chkstage, unsigned numstages,
248 unsigned prevState, unsigned origState,
249 DenseSet<unsigned> &VisitedResourceStates) const;
252 // addTransition - Add a transition from this state given the input InsnClass.
254 void addTransition(
255 std::vector<unsigned> InsnClass, const State *To,
256 const std::vector<std::pair<unsigned, unsigned>> &TransitionInfo) const;
259 // hasTransition - Returns true if there is a transition from this state
260 // given the input InsnClass
262 bool hasTransition(std::vector<unsigned> InsnClass) const;
266 // class DFA: deterministic finite automaton for processor resource tracking.
268 class DFA {
269 public:
270 DFA() = default;
272 // Set of states. Need to keep this sorted to emit the transition table.
273 typedef std::set<State> StateSet;
274 StateSet states;
276 State *currentState = nullptr;
279 // Modify the DFA.
281 const State &newState();
284 // writeTable: Print out a table representing the DFA.
286 void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName,
287 int numInsnClasses = 0,
288 int maxResources = 0, int numCombos = 0, int maxStages = 0);
291 } // end anonymous namespace
293 #ifndef NDEBUG
294 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
296 // dbgsInsnClass - When debugging, print instruction class stages.
298 void dbgsInsnClass(const std::vector<unsigned> &InsnClass) {
299 LLVM_DEBUG(dbgs() << "InsnClass: ");
300 for (unsigned i = 0; i < InsnClass.size(); ++i) {
301 if (i > 0) {
302 LLVM_DEBUG(dbgs() << ", ");
304 LLVM_DEBUG(dbgs() << "0x" << Twine::utohexstr(InsnClass[i]));
306 DFAInput InsnInput = getDFAInsnInput(InsnClass);
307 LLVM_DEBUG(dbgs() << " (input: 0x" << Twine::utohexstr(InsnInput) << ")");
311 // dbgsStateInfo - When debugging, print the set of state info.
313 void dbgsStateInfo(const std::set<unsigned> &stateInfo) {
314 LLVM_DEBUG(dbgs() << "StateInfo: ");
315 unsigned i = 0;
316 for (std::set<unsigned>::iterator SI = stateInfo.begin();
317 SI != stateInfo.end(); ++SI, ++i) {
318 unsigned thisState = *SI;
319 if (i > 0) {
320 LLVM_DEBUG(dbgs() << ", ");
322 LLVM_DEBUG(dbgs() << "0x" << Twine::utohexstr(thisState));
327 // dbgsIndent - When debugging, indent by the specified amount.
329 void dbgsIndent(unsigned indent) {
330 for (unsigned i = 0; i < indent; ++i) {
331 LLVM_DEBUG(dbgs() << " ");
334 #endif // NDEBUG
337 // Constructors and destructors for State and DFA
339 State::State() :
340 stateNum(currentStateNum++), isInitial(false) {}
343 // addTransition - Add a transition from this state given the input InsnClass
345 void State::addTransition(
346 std::vector<unsigned> InsnClass, const State *To,
347 const std::vector<std::pair<unsigned, unsigned>> &TransitionInfo) const {
348 assert(!Transitions.count(InsnClass) &&
349 "Cannot have multiple transitions for the same input");
350 Transitions[InsnClass] = {TransitionInfo, To};
354 // hasTransition - Returns true if there is a transition from this state
355 // given the input InsnClass
357 bool State::hasTransition(std::vector<unsigned> InsnClass) const {
358 return Transitions.count(InsnClass) > 0;
362 // AddInsnClass - Return all combinations of resource reservation
363 // which are possible from this state (PossibleStates).
365 // PossibleStates is the set of valid resource states that ensue from valid
366 // transitions.
368 void State::AddInsnClass(
369 std::vector<unsigned> &InsnClass,
370 std::map<unsigned, unsigned> &ComboBitToBitsMap,
371 std::set<unsigned> &PossibleStates,
372 std::vector<std::pair<unsigned, unsigned>> &TransitionInfo) const {
374 // Iterate over all resource states in currentState.
376 unsigned numstages = InsnClass.size();
377 assert((numstages > 0) && "InsnClass has no stages");
379 for (std::set<unsigned>::iterator SI = stateInfo.begin();
380 SI != stateInfo.end(); ++SI) {
381 unsigned ThisState = *SI;
383 DenseSet<unsigned> VisitedResourceStates;
385 LLVM_DEBUG(dbgs() << " thisState: 0x" << Twine::utohexstr(ThisState)
386 << "\n");
387 AddInsnClassStages(InsnClass, ComboBitToBitsMap, numstages - 1, numstages,
388 ThisState, ThisState, VisitedResourceStates);
389 for (unsigned NewState : VisitedResourceStates) {
390 PossibleStates.insert(NewState);
391 TransitionInfo.emplace_back(ThisState, NewState);
396 void State::AddInsnClassStages(
397 std::vector<unsigned> &InsnClass,
398 std::map<unsigned, unsigned> &ComboBitToBitsMap, unsigned chkstage,
399 unsigned numstages, unsigned prevState, unsigned origState,
400 DenseSet<unsigned> &VisitedResourceStates) const {
401 assert((chkstage < numstages) && "AddInsnClassStages: stage out of range");
402 unsigned thisStage = InsnClass[chkstage];
404 LLVM_DEBUG({
405 dbgsIndent((1 + numstages - chkstage) << 1);
406 dbgs() << "AddInsnClassStages " << chkstage << " (0x"
407 << Twine::utohexstr(thisStage) << ") from ";
408 dbgsInsnClass(InsnClass);
409 dbgs() << "\n";
413 // Iterate over all possible resources used in thisStage.
414 // For ex: for thisStage = 0x11, all resources = {0x01, 0x10}.
416 for (unsigned int j = 0; j < DFA_MAX_RESOURCES; ++j) {
417 unsigned resourceMask = (0x1 << j);
418 if (resourceMask & thisStage) {
419 unsigned combo = ComboBitToBitsMap[resourceMask];
420 if (combo && ((~prevState & combo) != combo)) {
421 LLVM_DEBUG(dbgs() << "\tSkipped Add 0x" << Twine::utohexstr(prevState)
422 << " - combo op 0x" << Twine::utohexstr(resourceMask)
423 << " (0x" << Twine::utohexstr(combo)
424 << ") cannot be scheduled\n");
425 continue;
428 // For each possible resource used in thisStage, generate the
429 // resource state if that resource was used.
431 unsigned ResultingResourceState = prevState | resourceMask | combo;
432 LLVM_DEBUG({
433 dbgsIndent((2 + numstages - chkstage) << 1);
434 dbgs() << "0x" << Twine::utohexstr(prevState) << " | 0x"
435 << Twine::utohexstr(resourceMask);
436 if (combo)
437 dbgs() << " | 0x" << Twine::utohexstr(combo);
438 dbgs() << " = 0x" << Twine::utohexstr(ResultingResourceState) << " ";
442 // If this is the final stage for this class
444 if (chkstage == 0) {
446 // Check if the resulting resource state can be accommodated in this
447 // packet.
448 // We compute resource OR prevState (originally started as origState).
449 // If the result of the OR is different than origState, it implies
450 // that there is at least one resource that can be used to schedule
451 // thisStage in the current packet.
452 // Insert ResultingResourceState into PossibleStates only if we haven't
453 // processed ResultingResourceState before.
455 if (ResultingResourceState != prevState) {
456 if (VisitedResourceStates.count(ResultingResourceState) == 0) {
457 VisitedResourceStates.insert(ResultingResourceState);
458 LLVM_DEBUG(dbgs()
459 << "\tResultingResourceState: 0x"
460 << Twine::utohexstr(ResultingResourceState) << "\n");
461 } else {
462 LLVM_DEBUG(dbgs() << "\tSkipped Add - state already seen\n");
464 } else {
465 LLVM_DEBUG(dbgs()
466 << "\tSkipped Add - no final resources available\n");
468 } else {
470 // If the current resource can be accommodated, check the next
471 // stage in InsnClass for available resources.
473 if (ResultingResourceState != prevState) {
474 LLVM_DEBUG(dbgs() << "\n");
475 AddInsnClassStages(InsnClass, ComboBitToBitsMap, chkstage - 1,
476 numstages, ResultingResourceState, origState,
477 VisitedResourceStates);
478 } else {
479 LLVM_DEBUG(dbgs() << "\tSkipped Add - no resources available\n");
487 // canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass
488 // may be a valid transition from this state i.e., can an instruction of type
489 // InsnClass be added to the packet represented by this state.
491 // Note that this routine is performing conservative checks that can be
492 // quickly executed acting as a filter before calling AddInsnClassStages.
493 // Any cases allowed through here will be caught later in AddInsnClassStages
494 // which performs the more expensive exact check.
496 bool State::canMaybeAddInsnClass(std::vector<unsigned> &InsnClass,
497 std::map<unsigned, unsigned> &ComboBitToBitsMap) const {
498 for (std::set<unsigned>::const_iterator SI = stateInfo.begin();
499 SI != stateInfo.end(); ++SI) {
500 // Check to see if all required resources are available.
501 bool available = true;
503 // Inspect each stage independently.
504 // note: This is a conservative check as we aren't checking for
505 // possible resource competition between the stages themselves
506 // The full cross product is examined later in AddInsnClass.
507 for (unsigned i = 0; i < InsnClass.size(); ++i) {
508 unsigned resources = *SI;
509 if ((~resources & InsnClass[i]) == 0) {
510 available = false;
511 break;
513 // Make sure _all_ resources for a combo function are available.
514 // note: This is a quick conservative check as it won't catch an
515 // unscheduleable combo if this stage is an OR expression
516 // containing a combo.
517 // These cases are caught later in AddInsnClass.
518 unsigned combo = ComboBitToBitsMap[InsnClass[i]];
519 if (combo && ((~resources & combo) != combo)) {
520 LLVM_DEBUG(dbgs() << "\tSkipped canMaybeAdd 0x"
521 << Twine::utohexstr(resources) << " - combo op 0x"
522 << Twine::utohexstr(InsnClass[i]) << " (0x"
523 << Twine::utohexstr(combo)
524 << ") cannot be scheduled\n");
525 available = false;
526 break;
530 if (available) {
531 return true;
534 return false;
537 const State &DFA::newState() {
538 auto IterPair = states.insert(State());
539 assert(IterPair.second && "State already exists");
540 return *IterPair.first;
543 int State::currentStateNum = 0;
545 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R):
546 TargetName(CodeGenTarget(R).getName()), Records(R) {}
549 // writeTableAndAPI - Print out a table representing the DFA and the
550 // associated API to create a DFA packetizer.
552 // Format:
553 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
554 // transitions.
555 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for
556 // the ith state.
559 void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName,
560 int numInsnClasses,
561 int maxResources, int numCombos, int maxStages) {
562 unsigned numStates = states.size();
564 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
565 "----------------------\n");
566 LLVM_DEBUG(dbgs() << "writeTableAndAPI\n");
567 LLVM_DEBUG(dbgs() << "Total states: " << numStates << "\n");
569 OS << "\n// " << TargetName << "DFAStateInputTable[][2] = "
570 << "pairs of <Input, NextState> for all valid\n";
571 OS << "// transitions.\n";
572 OS << "// " << numStates << "\tstates\n";
573 OS << "// " << numInsnClasses << "\tinstruction classes\n";
574 OS << "// " << maxResources << "\tresources max\n";
575 OS << "// " << numCombos << "\tcombo resources\n";
576 OS << "// " << maxStages << "\tstages max\n";
577 OS << "const " << DFA_TBLTYPE << " "
578 << TargetName << "DFAStateInputTable[][2] = {\n";
580 // This table provides a map to the beginning of the transitions for State s
581 // in DFAStateInputTable.
582 std::vector<int> StateEntry(numStates+1);
583 static const std::string SentinelEntry = "{-1, -1}";
585 // Tracks the total valid transitions encountered so far. It is used
586 // to construct the StateEntry table.
587 int ValidTransitions = 0;
588 DFA::StateSet::iterator SI = states.begin();
589 for (unsigned i = 0; i < numStates; ++i, ++SI) {
590 assert ((SI->stateNum == (int) i) && "Mismatch in state numbers");
591 StateEntry[i] = ValidTransitions;
592 for (State::TransitionMap::iterator
593 II = SI->Transitions.begin(), IE = SI->Transitions.end();
594 II != IE; ++II) {
595 OS << "{0x" << Twine::utohexstr(getDFAInsnInput(II->first)) << ", "
596 << II->second.S->stateNum << "},\t";
598 ValidTransitions += SI->Transitions.size();
600 OS << " // state " << i << ": " << StateEntry[i];
601 if (StateEntry[i] != (ValidTransitions-1)) { // More than one transition.
602 OS << "-" << (ValidTransitions-1);
604 OS << "\n";
607 // Print out a sentinel entry at the end of the StateInputTable. This is
608 // needed to iterate over StateInputTable in DFAPacketizer::ReadTable()
609 OS << SentinelEntry << "\t";
610 OS << " // state " << numStates << ": " << ValidTransitions;
611 OS << "\n";
613 OS << "};\n\n";
614 OS << "// " << TargetName << "DFAStateEntryTable[i] = "
615 << "Index of the first entry in DFAStateInputTable for\n";
616 OS << "// "
617 << "the ith state.\n";
618 OS << "// " << numStates << " states\n";
619 OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n";
621 unsigned lastState = 0;
622 for (unsigned i = 0; i < numStates; ++i) {
623 if (i && ((i % 10) == 0)) {
624 lastState = i-1;
625 OS << " // states " << (i-10) << ":" << lastState << "\n";
627 OS << StateEntry[i] << ", ";
629 // Print out the index to the sentinel entry in StateInputTable
630 OS << ValidTransitions << ", ";
631 OS << " // states " << (lastState+1) << ":" << numStates << "\n";
632 OS << "};\n";
634 // Generate the resource transition table.
635 OS << "const unsigned " << TargetName
636 << "DFAResourceTransitionTable[][2] = { \n";
637 int N = 0;
638 StateEntry.clear();
639 for (const State &S : states) {
640 for (auto &KV : S.Transitions) {
641 StateEntry.push_back(N);
642 for (std::pair<unsigned, unsigned> &T : KV.second.ResourceTransitions) {
643 OS << "{0x" << utohexstr(T.first) << ", 0x" << utohexstr(T.second)
644 << "}, ";
645 ++N;
648 OS << "\n ";
650 // Add a sentinel entry to terminate the search.
651 StateEntry.push_back(N);
652 OS << "\n {~0U,~0U}\n};\n\n";
654 OS << "// " << TargetName << "DFAResourceTransitionEntryTable[i] = "
655 << "Index of the first entry in DFAResourceTransitionTable for\n";
656 OS << "// the ith transition.\n";
657 OS << "const unsigned int " << TargetName
658 << "DFAResourceTransitionEntryTable[] = { \n";
660 N = 0;
661 for (int S : StateEntry) {
662 OS << S << ",";
663 if (N++ % 10 == 0)
664 OS << "\n ";
666 OS << "\n ~0U\n};\n";
670 // collectAllFuncUnits - Construct a map of function unit names to bits.
672 int DFAPacketizerEmitter::collectAllFuncUnits(
673 std::vector<Record*> &ProcItinList,
674 std::map<std::string, unsigned> &FUNameToBitsMap,
675 int &maxFUs,
676 raw_ostream &OS) {
677 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
678 "----------------------\n");
679 LLVM_DEBUG(dbgs() << "collectAllFuncUnits");
680 LLVM_DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n");
682 int totalFUs = 0;
683 // Parse functional units for all the itineraries.
684 for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) {
685 Record *Proc = ProcItinList[i];
686 std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU");
688 LLVM_DEBUG(dbgs() << " FU:" << i << " (" << FUs.size() << " FUs) "
689 << Proc->getName());
691 // Convert macros to bits for each stage.
692 unsigned numFUs = FUs.size();
693 for (unsigned j = 0; j < numFUs; ++j) {
694 assert ((j < DFA_MAX_RESOURCES) &&
695 "Exceeded maximum number of representable resources");
696 unsigned FuncResources = (unsigned) (1U << j);
697 FUNameToBitsMap[FUs[j]->getName()] = FuncResources;
698 LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"
699 << Twine::utohexstr(FuncResources));
701 if (((int) numFUs) > maxFUs) {
702 maxFUs = numFUs;
704 totalFUs += numFUs;
705 LLVM_DEBUG(dbgs() << "\n");
707 return totalFUs;
711 // collectAllComboFuncs - Construct a map from a combo function unit bit to
712 // the bits of all included functional units.
714 int DFAPacketizerEmitter::collectAllComboFuncs(
715 std::vector<Record*> &ComboFuncList,
716 std::map<std::string, unsigned> &FUNameToBitsMap,
717 std::map<unsigned, unsigned> &ComboBitToBitsMap,
718 raw_ostream &OS) {
719 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
720 "----------------------\n");
721 LLVM_DEBUG(dbgs() << "collectAllComboFuncs");
722 LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");
724 int numCombos = 0;
725 for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
726 Record *Func = ComboFuncList[i];
727 std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD");
729 LLVM_DEBUG(dbgs() << " CFD:" << i << " (" << FUs.size() << " combo FUs) "
730 << Func->getName() << "\n");
732 // Convert macros to bits for each stage.
733 for (unsigned j = 0, N = FUs.size(); j < N; ++j) {
734 assert ((j < DFA_MAX_RESOURCES) &&
735 "Exceeded maximum number of DFA resources");
736 Record *FuncData = FUs[j];
737 Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");
738 const std::vector<Record*> &FuncList =
739 FuncData->getValueAsListOfDefs("FuncList");
740 const std::string &ComboFuncName = ComboFunc->getName();
741 unsigned ComboBit = FUNameToBitsMap[ComboFuncName];
742 unsigned ComboResources = ComboBit;
743 LLVM_DEBUG(dbgs() << " combo: " << ComboFuncName << ":0x"
744 << Twine::utohexstr(ComboResources) << "\n");
745 for (unsigned k = 0, M = FuncList.size(); k < M; ++k) {
746 std::string FuncName = FuncList[k]->getName();
747 unsigned FuncResources = FUNameToBitsMap[FuncName];
748 LLVM_DEBUG(dbgs() << " " << FuncName << ":0x"
749 << Twine::utohexstr(FuncResources) << "\n");
750 ComboResources |= FuncResources;
752 ComboBitToBitsMap[ComboBit] = ComboResources;
753 numCombos++;
754 LLVM_DEBUG(dbgs() << " => combo bits: " << ComboFuncName << ":0x"
755 << Twine::utohexstr(ComboBit) << " = 0x"
756 << Twine::utohexstr(ComboResources) << "\n");
759 return numCombos;
763 // collectOneInsnClass - Populate allInsnClasses with one instruction class
765 int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName,
766 std::vector<Record*> &ProcItinList,
767 std::map<std::string, unsigned> &FUNameToBitsMap,
768 Record *ItinData,
769 raw_ostream &OS) {
770 const std::vector<Record*> &StageList =
771 ItinData->getValueAsListOfDefs("Stages");
773 // The number of stages.
774 unsigned NStages = StageList.size();
776 LLVM_DEBUG(dbgs() << " " << ItinData->getValueAsDef("TheClass")->getName()
777 << "\n");
779 std::vector<unsigned> UnitBits;
781 // Compute the bitwise or of each unit used in this stage.
782 for (unsigned i = 0; i < NStages; ++i) {
783 const Record *Stage = StageList[i];
785 // Get unit list.
786 const std::vector<Record*> &UnitList =
787 Stage->getValueAsListOfDefs("Units");
789 LLVM_DEBUG(dbgs() << " stage:" << i << " [" << UnitList.size()
790 << " units]:");
791 unsigned dbglen = 26; // cursor after stage dbgs
793 // Compute the bitwise or of each unit used in this stage.
794 unsigned UnitBitValue = 0;
795 for (unsigned j = 0, M = UnitList.size(); j < M; ++j) {
796 // Conduct bitwise or.
797 std::string UnitName = UnitList[j]->getName();
798 LLVM_DEBUG(dbgs() << " " << j << ":" << UnitName);
799 dbglen += 3 + UnitName.length();
800 assert(FUNameToBitsMap.count(UnitName));
801 UnitBitValue |= FUNameToBitsMap[UnitName];
804 if (UnitBitValue != 0)
805 UnitBits.push_back(UnitBitValue);
807 while (dbglen <= 64) { // line up bits dbgs
808 dbglen += 8;
809 LLVM_DEBUG(dbgs() << "\t");
811 LLVM_DEBUG(dbgs() << " (bits: 0x" << Twine::utohexstr(UnitBitValue)
812 << ")\n");
815 if (!UnitBits.empty())
816 allInsnClasses.push_back(UnitBits);
818 LLVM_DEBUG({
819 dbgs() << " ";
820 dbgsInsnClass(UnitBits);
821 dbgs() << "\n";
824 return NStages;
828 // collectAllInsnClasses - Populate allInsnClasses which is a set of units
829 // used in each stage.
831 int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName,
832 std::vector<Record*> &ProcItinList,
833 std::map<std::string, unsigned> &FUNameToBitsMap,
834 std::vector<Record*> &ItinDataList,
835 int &maxStages,
836 raw_ostream &OS) {
837 // Collect all instruction classes.
838 unsigned M = ItinDataList.size();
840 int numInsnClasses = 0;
841 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
842 "----------------------\n"
843 << "collectAllInsnClasses " << ProcName << " (" << M
844 << " classes)\n");
846 // Collect stages for each instruction class for all itinerary data
847 for (unsigned j = 0; j < M; j++) {
848 Record *ItinData = ItinDataList[j];
849 int NStages = collectOneInsnClass(ProcName, ProcItinList,
850 FUNameToBitsMap, ItinData, OS);
851 if (NStages > maxStages) {
852 maxStages = NStages;
854 numInsnClasses++;
856 return numInsnClasses;
860 // Run the worklist algorithm to generate the DFA.
862 void DFAPacketizerEmitter::run(raw_ostream &OS) {
863 OS << "\n"
864 << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
865 OS << "namespace llvm {\n";
867 OS << "\n// Input format:\n";
868 OS << "#define DFA_MAX_RESTERMS " << DFA_MAX_RESTERMS
869 << "\t// maximum AND'ed resource terms\n";
870 OS << "#define DFA_MAX_RESOURCES " << DFA_MAX_RESOURCES
871 << "\t// maximum resource bits in one term\n";
873 // Collect processor iteraries.
874 std::vector<Record*> ProcItinList =
875 Records.getAllDerivedDefinitions("ProcessorItineraries");
877 std::unordered_map<std::string, std::vector<Record*>> ItinsByNamespace;
878 for (Record *R : ProcItinList)
879 ItinsByNamespace[R->getValueAsString("PacketizerNamespace")].push_back(R);
881 for (auto &KV : ItinsByNamespace)
882 emitForItineraries(OS, KV.second, KV.first);
883 OS << "} // end namespace llvm\n";
886 void DFAPacketizerEmitter::emitForItineraries(
887 raw_ostream &OS, std::vector<Record *> &ProcItinList,
888 std::string DFAName) {
890 // Collect the Functional units.
892 std::map<std::string, unsigned> FUNameToBitsMap;
893 int maxResources = 0;
894 collectAllFuncUnits(ProcItinList,
895 FUNameToBitsMap, maxResources, OS);
898 // Collect the Combo Functional units.
900 std::map<unsigned, unsigned> ComboBitToBitsMap;
901 std::vector<Record*> ComboFuncList =
902 Records.getAllDerivedDefinitions("ComboFuncUnits");
903 int numCombos = collectAllComboFuncs(ComboFuncList,
904 FUNameToBitsMap, ComboBitToBitsMap, OS);
907 // Collect the itineraries.
909 int maxStages = 0;
910 int numInsnClasses = 0;
911 for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) {
912 Record *Proc = ProcItinList[i];
914 // Get processor itinerary name.
915 const std::string &ProcName = Proc->getName();
917 // Skip default.
918 if (ProcName == "NoItineraries")
919 continue;
921 // Sanity check for at least one instruction itinerary class.
922 unsigned NItinClasses =
923 Records.getAllDerivedDefinitions("InstrItinClass").size();
924 if (NItinClasses == 0)
925 return;
927 // Get itinerary data list.
928 std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID");
930 // Collect all instruction classes
931 numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList,
932 FUNameToBitsMap, ItinDataList, maxStages, OS);
936 // Run a worklist algorithm to generate the DFA.
938 DFA D;
939 const State *Initial = &D.newState();
940 Initial->isInitial = true;
941 Initial->stateInfo.insert(0x0);
942 SmallVector<const State*, 32> WorkList;
943 std::map<std::set<unsigned>, const State*> Visited;
945 WorkList.push_back(Initial);
948 // Worklist algorithm to create a DFA for processor resource tracking.
949 // C = {set of InsnClasses}
950 // Begin with initial node in worklist. Initial node does not have
951 // any consumed resources,
952 // ResourceState = 0x0
953 // Visited = {}
954 // While worklist != empty
955 // S = first element of worklist
956 // For every instruction class C
957 // if we can accommodate C in S:
958 // S' = state with resource states = {S Union C}
959 // Add a new transition: S x C -> S'
960 // If S' is not in Visited:
961 // Add S' to worklist
962 // Add S' to Visited
964 while (!WorkList.empty()) {
965 const State *current = WorkList.pop_back_val();
966 LLVM_DEBUG({
967 dbgs() << "---------------------\n";
968 dbgs() << "Processing state: " << current->stateNum << " - ";
969 dbgsStateInfo(current->stateInfo);
970 dbgs() << "\n";
972 for (unsigned i = 0; i < allInsnClasses.size(); i++) {
973 std::vector<unsigned> InsnClass = allInsnClasses[i];
974 LLVM_DEBUG({
975 dbgs() << i << " ";
976 dbgsInsnClass(InsnClass);
977 dbgs() << "\n";
980 std::set<unsigned> NewStateResources;
982 // If we haven't already created a transition for this input
983 // and the state can accommodate this InsnClass, create a transition.
985 if (!current->hasTransition(InsnClass) &&
986 current->canMaybeAddInsnClass(InsnClass, ComboBitToBitsMap)) {
987 const State *NewState = nullptr;
988 std::vector<std::pair<unsigned, unsigned>> TransitionInfo;
989 current->AddInsnClass(InsnClass, ComboBitToBitsMap, NewStateResources,
990 TransitionInfo);
991 if (NewStateResources.empty()) {
992 LLVM_DEBUG(dbgs() << " Skipped - no new states generated\n");
993 continue;
996 LLVM_DEBUG({
997 dbgs() << "\t";
998 dbgsStateInfo(NewStateResources);
999 dbgs() << "\n";
1003 // If we have seen this state before, then do not create a new state.
1005 auto VI = Visited.find(NewStateResources);
1006 if (VI != Visited.end()) {
1007 NewState = VI->second;
1008 LLVM_DEBUG({
1009 dbgs() << "\tFound existing state: " << NewState->stateNum
1010 << " - ";
1011 dbgsStateInfo(NewState->stateInfo);
1012 dbgs() << "\n";
1014 } else {
1015 NewState = &D.newState();
1016 NewState->stateInfo = NewStateResources;
1017 Visited[NewStateResources] = NewState;
1018 WorkList.push_back(NewState);
1019 LLVM_DEBUG({
1020 dbgs() << "\tAccepted new state: " << NewState->stateNum << " - ";
1021 dbgsStateInfo(NewState->stateInfo);
1022 dbgs() << "\n";
1026 current->addTransition(InsnClass, NewState, TransitionInfo);
1031 // Print out the table.
1032 D.writeTableAndAPI(OS, TargetName + DFAName, numInsnClasses, maxResources,
1033 numCombos, maxStages);
1035 OS << "} // end namespace llvm\n";
1037 std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
1038 OS << "namespace llvm {\n";
1039 OS << "DFAPacketizer *" << SubTargetClassName << "::"
1040 << "create" << DFAName
1041 << "DFAPacketizer(const InstrItineraryData *IID) const {\n"
1042 << " return new DFAPacketizer(IID, " << TargetName << DFAName
1043 << "DFAStateInputTable, " << TargetName << DFAName
1044 << "DFAStateEntryTable, " << TargetName << DFAName
1045 << "DFAResourceTransitionTable, " << TargetName << DFAName
1046 << "DFAResourceTransitionEntryTable"
1047 << ");\n}\n\n";
1050 namespace llvm {
1052 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
1053 emitSourceFileHeader("Target DFA Packetizer Tables", OS);
1054 DFAPacketizerEmitter(RK).run(OS);
1057 } // end namespace llvm