contrib/llvm/utils/TableGen/DFAPacketizerEmitter.cpp

   1 //===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "dfa-emitter"
  19
  20 #include "CodeGenTarget.h"
  21 #include "llvm/ADT/DenseSet.h"
  22 #include "llvm/ADT/STLExtras.h"
  23 #include "llvm/ADT/StringExtras.h"
  24 #include "llvm/TableGen/Record.h"
  25 #include "llvm/TableGen/TableGenBackend.h"
  26 #include "llvm/Support/Debug.h"
  27 #include <map>
  28 #include <string>
  29 #include <queue>
  30
  31 using namespace llvm;
  32
  33 // --------------------------------------------------------------------
  34 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
  35
  36 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
  37 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
  38 //
  39 // e.g. terms x resource bit combinations that fit in uint32_t:
  40 //      4 terms x 8  bits = 32 bits
  41 //      3 terms x 10 bits = 30 bits
  42 //      2 terms x 16 bits = 32 bits
  43 //
  44 // e.g. terms x resource bit combinations that fit in uint64_t:
  45 //      8 terms x 8  bits = 64 bits
  46 //      7 terms x 9  bits = 63 bits
  47 //      6 terms x 10 bits = 60 bits
  48 //      5 terms x 12 bits = 60 bits
  49 //      4 terms x 16 bits = 64 bits <--- current
  50 //      3 terms x 21 bits = 63 bits
  51 //      2 terms x 32 bits = 64 bits
  52 //
  53 #define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
  54 #define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.
  55
  56 typedef uint64_t                DFAInput;
  57 typedef int64_t                 DFAStateInput;
  58 #define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
  59
  60 namespace {
  61   DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
  62     return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
  63   }
  64
  65   /// Return the DFAInput for an instruction class input vector.
  66   /// This function is used in both DFAPacketizer.cpp and in
  67   /// DFAPacketizerEmitter.cpp.
  68   DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
  69     DFAInput InsnInput = 0;
  70     assert ((InsnClass.size() <= DFA_MAX_RESTERMS) &&
  71             "Exceeded maximum number of DFA terms");
  72     for (auto U : InsnClass)
  73       InsnInput = addDFAFuncUnits(InsnInput, U);
  74     return InsnInput;
  75   }
  76 } // end anonymous namespace
  77
  78 // --------------------------------------------------------------------
  79
  80 #ifndef NDEBUG
  81 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
  82 //
  83 // dbgsInsnClass - When debugging, print instruction class stages.
  84 //
  85 void dbgsInsnClass(const std::vector<unsigned> &InsnClass);
  86 //
  87 // dbgsStateInfo - When debugging, print the set of state info.
  88 //
  89 void dbgsStateInfo(const std::set<unsigned> &stateInfo);
  90 //
  91 // dbgsIndent - When debugging, indent by the specified amount.
  92 //
  93 void dbgsIndent(unsigned indent);
  94 #endif
  95
  96 //
  97 // class DFAPacketizerEmitter: class that generates and prints out the DFA
  98 // for resource tracking.
  99 //
 100 namespace {
 101 class DFAPacketizerEmitter {
 102 private:
 103   std::string TargetName;
 104   //
 105   // allInsnClasses is the set of all possible resources consumed by an
 106   // InstrStage.
 107   //
 108   std::vector<std::vector<unsigned>> allInsnClasses;
 109   RecordKeeper &Records;
 110
 111 public:
 112   DFAPacketizerEmitter(RecordKeeper &R);
 113
 114   //
 115   // collectAllFuncUnits - Construct a map of function unit names to bits.
 116   //
 117   int collectAllFuncUnits(std::vector<Record*> &ProcItinList,
 118                            std::map<std::string, unsigned> &FUNameToBitsMap,
 119                            int &maxResources,
 120                            raw_ostream &OS);
 121
 122   //
 123   // collectAllComboFuncs - Construct a map from a combo function unit bit to
 124   //                        the bits of all included functional units.
 125   //
 126   int collectAllComboFuncs(std::vector<Record*> &ComboFuncList,
 127                            std::map<std::string, unsigned> &FUNameToBitsMap,
 128                            std::map<unsigned, unsigned> &ComboBitToBitsMap,
 129                            raw_ostream &OS);
 130
 131   //
 132   // collectOneInsnClass - Populate allInsnClasses with one instruction class.
 133   //
 134   int collectOneInsnClass(const std::string &ProcName,
 135                            std::vector<Record*> &ProcItinList,
 136                            std::map<std::string, unsigned> &FUNameToBitsMap,
 137                            Record *ItinData,
 138                            raw_ostream &OS);
 139
 140   //
 141   // collectAllInsnClasses - Populate allInsnClasses which is a set of units
 142   // used in each stage.
 143   //
 144   int collectAllInsnClasses(const std::string &ProcName,
 145                            std::vector<Record*> &ProcItinList,
 146                            std::map<std::string, unsigned> &FUNameToBitsMap,
 147                            std::vector<Record*> &ItinDataList,
 148                            int &maxStages,
 149                            raw_ostream &OS);
 150
 151   void run(raw_ostream &OS);
 152 };
 153 } // end anonymous namespace
 154
 155 //
 156 //
 157 // State represents the usage of machine resources if the packet contains
 158 // a set of instruction classes.
 159 //
 160 // Specifically, currentState is a set of bit-masks.
 161 // The nth bit in a bit-mask indicates whether the nth resource is being used
 162 // by this state. The set of bit-masks in a state represent the different
 163 // possible outcomes of transitioning to this state.
 164 // For example: consider a two resource architecture: resource L and resource M
 165 // with three instruction classes: L, M, and L_or_M.
 166 // From the initial state (currentState = 0x00), if we add instruction class
 167 // L_or_M we will transition to a state with currentState = [0x01, 0x10]. This
 168 // represents the possible resource states that can result from adding a L_or_M
 169 // instruction
 170 //
 171 // Another way of thinking about this transition is we are mapping a NDFA with
 172 // two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10].
 173 //
 174 // A State instance also contains a collection of transitions from that state:
 175 // a map from inputs to new states.
 176 //
 177 namespace {
 178 class State {
 179  public:
 180   static int currentStateNum;
 181   // stateNum is the only member used for equality/ordering, all other members
 182   // can be mutated even in const State objects.
 183   const int stateNum;
 184   mutable bool isInitial;
 185   mutable std::set<unsigned> stateInfo;
 186   typedef std::map<std::vector<unsigned>, const State *> TransitionMap;
 187   mutable TransitionMap Transitions;
 188
 189   State();
 190
 191   bool operator<(const State &s) const {
 192     return stateNum < s.stateNum;
 193   }
 194
 195   //
 196   // canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass
 197   // may be a valid transition from this state i.e., can an instruction of type
 198   // InsnClass be added to the packet represented by this state.
 199   //
 200   // Note that for multiple stages, this quick check does not take into account
 201   // any possible resource competition between the stages themselves.  That is
 202   // enforced in AddInsnClassStages which checks the cross product of all
 203   // stages for resource availability (which is a more involved check).
 204   //
 205   bool canMaybeAddInsnClass(std::vector<unsigned> &InsnClass,
 206                         std::map<unsigned, unsigned> &ComboBitToBitsMap) const;
 207   //
 208   // AddInsnClass - Return all combinations of resource reservation
 209   // which are possible from this state (PossibleStates).
 210   //
 211   // PossibleStates is the set of valid resource states that ensue from valid
 212   // transitions.
 213   //
 214   void AddInsnClass(std::vector<unsigned> &InsnClass,
 215                         std::map<unsigned, unsigned> &ComboBitToBitsMap,
 216                         std::set<unsigned> &PossibleStates) const;
 217   //
 218   // AddInsnClassStages - Return all combinations of resource reservation
 219   // resulting from the cross product of all stages for this InsnClass
 220   // which are possible from this state (PossibleStates).
 221   //
 222   void AddInsnClassStages(std::vector<unsigned> &InsnClass,
 223                         std::map<unsigned, unsigned> &ComboBitToBitsMap,
 224                         unsigned chkstage, unsigned numstages,
 225                         unsigned prevState, unsigned origState,
 226                         DenseSet<unsigned> &VisitedResourceStates,
 227                         std::set<unsigned> &PossibleStates) const;
 228   //
 229   // addTransition - Add a transition from this state given the input InsnClass
 230   //
 231   void addTransition(std::vector<unsigned> InsnClass, const State *To) const;
 232   //
 233   // hasTransition - Returns true if there is a transition from this state
 234   // given the input InsnClass
 235   //
 236   bool hasTransition(std::vector<unsigned> InsnClass) const;
 237 };
 238 } // end anonymous namespace
 239
 240 //
 241 // class DFA: deterministic finite automaton for processor resource tracking.
 242 //
 243 namespace {
 244 class DFA {
 245 public:
 246   DFA();
 247
 248   // Set of states. Need to keep this sorted to emit the transition table.
 249   typedef std::set<State> StateSet;
 250   StateSet states;
 251
 252   State *currentState;
 253
 254   //
 255   // Modify the DFA.
 256   //
 257   const State &newState();
 258
 259   //
 260   // writeTable: Print out a table representing the DFA.
 261   //
 262   void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName,
 263                  int numInsnClasses = 0,
 264                  int maxResources = 0, int numCombos = 0, int maxStages = 0);
 265 };
 266 } // end anonymous namespace
 267
 268 #ifndef NDEBUG
 269 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
 270 //
 271 // dbgsInsnClass - When debugging, print instruction class stages.
 272 //
 273 void dbgsInsnClass(const std::vector<unsigned> &InsnClass) {
 274   DEBUG(dbgs() << "InsnClass: ");
 275   for (unsigned i = 0; i < InsnClass.size(); ++i) {
 276     if (i > 0) {
 277       DEBUG(dbgs() << ", ");
 278     }
 279     DEBUG(dbgs() << "0x" << utohexstr(InsnClass[i]));
 280   }
 281   DFAInput InsnInput = getDFAInsnInput(InsnClass);
 282   DEBUG(dbgs() << " (input: 0x" << utohexstr(InsnInput) << ")");
 283 }
 284
 285 //
 286 // dbgsStateInfo - When debugging, print the set of state info.
 287 //
 288 void dbgsStateInfo(const std::set<unsigned> &stateInfo) {
 289   DEBUG(dbgs() << "StateInfo: ");
 290   unsigned i = 0;
 291   for (std::set<unsigned>::iterator SI = stateInfo.begin();
 292        SI != stateInfo.end(); ++SI, ++i) {
 293     unsigned thisState = *SI;
 294     if (i > 0) {
 295       DEBUG(dbgs() << ", ");
 296     }
 297     DEBUG(dbgs() << "0x" << utohexstr(thisState));
 298   }
 299 }
 300
 301 //
 302 // dbgsIndent - When debugging, indent by the specified amount.
 303 //
 304 void dbgsIndent(unsigned indent) {
 305   for (unsigned i = 0; i < indent; ++i) {
 306     DEBUG(dbgs() << " ");
 307   }
 308 }
 309 #endif // NDEBUG
 310
 311 //
 312 // Constructors and destructors for State and DFA
 313 //
 314 State::State() :
 315   stateNum(currentStateNum++), isInitial(false) {}
 316
 317 DFA::DFA(): currentState(nullptr) {}
 318
 319 //
 320 // addTransition - Add a transition from this state given the input InsnClass
 321 //
 322 void State::addTransition(std::vector<unsigned> InsnClass, const State *To)
 323       const {
 324   assert(!Transitions.count(InsnClass) &&
 325       "Cannot have multiple transitions for the same input");
 326   Transitions[InsnClass] = To;
 327 }
 328
 329 //
 330 // hasTransition - Returns true if there is a transition from this state
 331 // given the input InsnClass
 332 //
 333 bool State::hasTransition(std::vector<unsigned> InsnClass) const {
 334   return Transitions.count(InsnClass) > 0;
 335 }
 336
 337 //
 338 // AddInsnClass - Return all combinations of resource reservation
 339 // which are possible from this state (PossibleStates).
 340 //
 341 // PossibleStates is the set of valid resource states that ensue from valid
 342 // transitions.
 343 //
 344 void State::AddInsnClass(std::vector<unsigned> &InsnClass,
 345                         std::map<unsigned, unsigned> &ComboBitToBitsMap,
 346                         std::set<unsigned> &PossibleStates) const {
 347   //
 348   // Iterate over all resource states in currentState.
 349   //
 350   unsigned numstages = InsnClass.size();
 351   assert((numstages > 0) && "InsnClass has no stages");
 352
 353   for (std::set<unsigned>::iterator SI = stateInfo.begin();
 354        SI != stateInfo.end(); ++SI) {
 355     unsigned thisState = *SI;
 356
 357     DenseSet<unsigned> VisitedResourceStates;
 358
 359     DEBUG(dbgs() << "  thisState: 0x" << utohexstr(thisState) << "\n");
 360     AddInsnClassStages(InsnClass, ComboBitToBitsMap,
 361                                 numstages - 1, numstages,
 362                                 thisState, thisState,
 363                                 VisitedResourceStates, PossibleStates);
 364   }
 365 }
 366
 367 void State::AddInsnClassStages(std::vector<unsigned> &InsnClass,
 368                         std::map<unsigned, unsigned> &ComboBitToBitsMap,
 369                         unsigned chkstage, unsigned numstages,
 370                         unsigned prevState, unsigned origState,
 371                         DenseSet<unsigned> &VisitedResourceStates,
 372                         std::set<unsigned> &PossibleStates) const {
 373
 374   assert((chkstage < numstages) && "AddInsnClassStages: stage out of range");
 375   unsigned thisStage = InsnClass[chkstage];
 376
 377   DEBUG({
 378     dbgsIndent((1 + numstages - chkstage) << 1);
 379     dbgs() << "AddInsnClassStages " << chkstage << " (0x"
 380            << utohexstr(thisStage) << ") from ";
 381     dbgsInsnClass(InsnClass);
 382     dbgs() << "\n";
 383   });
 384
 385   //
 386   // Iterate over all possible resources used in thisStage.
 387   // For ex: for thisStage = 0x11, all resources = {0x01, 0x10}.
 388   //
 389   for (unsigned int j = 0; j < DFA_MAX_RESOURCES; ++j) {
 390     unsigned resourceMask = (0x1 << j);
 391     if (resourceMask & thisStage) {
 392       unsigned combo = ComboBitToBitsMap[resourceMask];
 393       if (combo && ((~prevState & combo) != combo)) {
 394         DEBUG(dbgs() << "\tSkipped Add 0x" << utohexstr(prevState)
 395                      << " - combo op 0x" << utohexstr(resourceMask)
 396                      << " (0x" << utohexstr(combo) <<") cannot be scheduled\n");
 397         continue;
 398       }
 399       //
 400       // For each possible resource used in thisStage, generate the
 401       // resource state if that resource was used.
 402       //
 403       unsigned ResultingResourceState = prevState | resourceMask | combo;
 404       DEBUG({
 405         dbgsIndent((2 + numstages - chkstage) << 1);
 406         dbgs() << "0x" << utohexstr(prevState)
 407                << " | 0x" << utohexstr(resourceMask);
 408         if (combo)
 409           dbgs() << " | 0x" << utohexstr(combo);
 410         dbgs() << " = 0x" << utohexstr(ResultingResourceState) << " ";
 411       });
 412
 413       //
 414       // If this is the final stage for this class
 415       //
 416       if (chkstage == 0) {
 417         //
 418         // Check if the resulting resource state can be accommodated in this
 419         // packet.
 420         // We compute resource OR prevState (originally started as origState).
 421         // If the result of the OR is different than origState, it implies
 422         // that there is at least one resource that can be used to schedule
 423         // thisStage in the current packet.
 424         // Insert ResultingResourceState into PossibleStates only if we haven't
 425         // processed ResultingResourceState before.
 426         //
 427         if (ResultingResourceState != prevState) {
 428           if (VisitedResourceStates.count(ResultingResourceState) == 0) {
 429             VisitedResourceStates.insert(ResultingResourceState);
 430             PossibleStates.insert(ResultingResourceState);
 431             DEBUG(dbgs() << "\tResultingResourceState: 0x"
 432                          << utohexstr(ResultingResourceState) << "\n");
 433           } else {
 434             DEBUG(dbgs() << "\tSkipped Add - state already seen\n");
 435           }
 436         } else {
 437           DEBUG(dbgs() << "\tSkipped Add - no final resources available\n");
 438         }
 439       } else {
 440         //
 441         // If the current resource can be accommodated, check the next
 442         // stage in InsnClass for available resources.
 443         //
 444         if (ResultingResourceState != prevState) {
 445           DEBUG(dbgs() << "\n");
 446           AddInsnClassStages(InsnClass, ComboBitToBitsMap,
 447                                 chkstage - 1, numstages,
 448                                 ResultingResourceState, origState,
 449                                 VisitedResourceStates, PossibleStates);
 450         } else {
 451           DEBUG(dbgs() << "\tSkipped Add - no resources available\n");
 452         }
 453       }
 454     }
 455   }
 456 }
 457
 458 //
 459 // canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass
 460 // may be a valid transition from this state i.e., can an instruction of type
 461 // InsnClass be added to the packet represented by this state.
 462 //
 463 // Note that this routine is performing conservative checks that can be
 464 // quickly executed acting as a filter before calling AddInsnClassStages.
 465 // Any cases allowed through here will be caught later in AddInsnClassStages
 466 // which performs the more expensive exact check.
 467 //
 468 bool State::canMaybeAddInsnClass(std::vector<unsigned> &InsnClass,
 469                     std::map<unsigned, unsigned> &ComboBitToBitsMap) const {
 470   for (std::set<unsigned>::const_iterator SI = stateInfo.begin();
 471        SI != stateInfo.end(); ++SI) {
 472
 473     // Check to see if all required resources are available.
 474     bool available = true;
 475
 476     // Inspect each stage independently.
 477     // note: This is a conservative check as we aren't checking for
 478     //       possible resource competition between the stages themselves
 479     //       The full cross product is examined later in AddInsnClass.
 480     for (unsigned i = 0; i < InsnClass.size(); ++i) {
 481       unsigned resources = *SI;
 482       if ((~resources & InsnClass[i]) == 0) {
 483         available = false;
 484         break;
 485       }
 486       // Make sure _all_ resources for a combo function are available.
 487       // note: This is a quick conservative check as it won't catch an
 488       //       unscheduleable combo if this stage is an OR expression
 489       //       containing a combo.
 490       //       These cases are caught later in AddInsnClass.
 491       unsigned combo = ComboBitToBitsMap[InsnClass[i]];
 492       if (combo && ((~resources & combo) != combo)) {
 493         DEBUG(dbgs() << "\tSkipped canMaybeAdd 0x" << utohexstr(resources)
 494                      << " - combo op 0x" << utohexstr(InsnClass[i])
 495                      << " (0x" << utohexstr(combo) <<") cannot be scheduled\n");
 496         available = false;
 497         break;
 498       }
 499     }
 500
 501     if (available) {
 502       return true;
 503     }
 504   }
 505   return false;
 506 }
 507
 508 const State &DFA::newState() {
 509   auto IterPair = states.insert(State());
 510   assert(IterPair.second && "State already exists");
 511   return *IterPair.first;
 512 }
 513
 514 int State::currentStateNum = 0;
 515
 516 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R):
 517   TargetName(CodeGenTarget(R).getName()),
 518   allInsnClasses(), Records(R) {}
 519
 520 //
 521 // writeTableAndAPI - Print out a table representing the DFA and the
 522 // associated API to create a DFA packetizer.
 523 //
 524 // Format:
 525 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
 526 //                           transitions.
 527 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for
 528 //                         the ith state.
 529 //
 530 //
 531 void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName,
 532                            int numInsnClasses,
 533                            int maxResources, int numCombos, int maxStages) {
 534
 535   unsigned numStates = states.size();
 536
 537   DEBUG(dbgs() << "-----------------------------------------------------------------------------\n");
 538   DEBUG(dbgs() << "writeTableAndAPI\n");
 539   DEBUG(dbgs() << "Total states: " << numStates << "\n");
 540
 541   OS << "namespace llvm {\n";
 542
 543   OS << "\n// Input format:\n";
 544   OS << "#define DFA_MAX_RESTERMS        " << DFA_MAX_RESTERMS
 545      << "\t// maximum AND'ed resource terms\n";
 546   OS << "#define DFA_MAX_RESOURCES       " << DFA_MAX_RESOURCES
 547      << "\t// maximum resource bits in one term\n";
 548
 549   OS << "\n// " << TargetName << "DFAStateInputTable[][2] = "
 550      << "pairs of <Input, NextState> for all valid\n";
 551   OS << "//                           transitions.\n";
 552   OS << "// " << numStates << "\tstates\n";
 553   OS << "// " << numInsnClasses << "\tinstruction classes\n";
 554   OS << "// " << maxResources << "\tresources max\n";
 555   OS << "// " << numCombos << "\tcombo resources\n";
 556   OS << "// " << maxStages << "\tstages max\n";
 557   OS << "const " << DFA_TBLTYPE << " "
 558      << TargetName << "DFAStateInputTable[][2] = {\n";
 559
 560   // This table provides a map to the beginning of the transitions for State s
 561   // in DFAStateInputTable.
 562   std::vector<int> StateEntry(numStates+1);
 563   static const std::string SentinelEntry = "{-1, -1}";
 564
 565   // Tracks the total valid transitions encountered so far. It is used
 566   // to construct the StateEntry table.
 567   int ValidTransitions = 0;
 568   DFA::StateSet::iterator SI = states.begin();
 569   for (unsigned i = 0; i < numStates; ++i, ++SI) {
 570     assert ((SI->stateNum == (int) i) && "Mismatch in state numbers");
 571     StateEntry[i] = ValidTransitions;
 572     for (State::TransitionMap::iterator
 573         II = SI->Transitions.begin(), IE = SI->Transitions.end();
 574         II != IE; ++II) {
 575       OS << "{0x" << utohexstr(getDFAInsnInput(II->first)) << ", "
 576          << II->second->stateNum
 577          << "},\t";
 578     }
 579     ValidTransitions += SI->Transitions.size();
 580
 581     // If there are no valid transitions from this stage, we need a sentinel
 582     // transition.
 583     if (ValidTransitions == StateEntry[i]) {
 584       OS << SentinelEntry << ",\t";
 585       ++ValidTransitions;
 586     }
 587
 588     OS << " // state " << i << ": " << StateEntry[i];
 589     if (StateEntry[i] != (ValidTransitions-1)) {   // More than one transition.
 590        OS << "-" << (ValidTransitions-1);
 591     }
 592     OS << "\n";
 593   }
 594
 595   // Print out a sentinel entry at the end of the StateInputTable. This is
 596   // needed to iterate over StateInputTable in DFAPacketizer::ReadTable()
 597   OS << SentinelEntry << "\t";
 598   OS << " // state " << numStates << ": " << ValidTransitions;
 599   OS << "\n";
 600
 601   OS << "};\n\n";
 602   OS << "// " << TargetName << "DFAStateEntryTable[i] = "
 603      << "Index of the first entry in DFAStateInputTable for\n";
 604   OS << "//                         "
 605      << "the ith state.\n";
 606   OS << "// " << numStates << " states\n";
 607   OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n";
 608
 609   // Multiply i by 2 since each entry in DFAStateInputTable is a set of
 610   // two numbers.
 611   unsigned lastState = 0;
 612   for (unsigned i = 0; i < numStates; ++i) {
 613     if (i && ((i % 10) == 0)) {
 614         lastState = i-1;
 615         OS << "   // states " << (i-10) << ":" << lastState << "\n";
 616     }
 617     OS << StateEntry[i] << ", ";
 618   }
 619
 620   // Print out the index to the sentinel entry in StateInputTable
 621   OS << ValidTransitions << ", ";
 622   OS << "   // states " << (lastState+1) << ":" << numStates << "\n";
 623
 624   OS << "};\n";
 625   OS << "} // namespace\n";
 626
 627   //
 628   // Emit DFA Packetizer tables if the target is a VLIW machine.
 629   //
 630   std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
 631   OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
 632   OS << "namespace llvm {\n";
 633   OS << "DFAPacketizer *" << SubTargetClassName << "::"
 634      << "createDFAPacketizer(const InstrItineraryData *IID) const {\n"
 635      << "   return new DFAPacketizer(IID, " << TargetName
 636      << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n";
 637   OS << "} // End llvm namespace \n";
 638 }
 639
 640 //
 641 // collectAllFuncUnits - Construct a map of function unit names to bits.
 642 //
 643 int DFAPacketizerEmitter::collectAllFuncUnits(
 644                             std::vector<Record*> &ProcItinList,
 645                             std::map<std::string, unsigned> &FUNameToBitsMap,
 646                             int &maxFUs,
 647                             raw_ostream &OS) {
 648   DEBUG(dbgs() << "-----------------------------------------------------------------------------\n");
 649   DEBUG(dbgs() << "collectAllFuncUnits");
 650   DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n");
 651
 652   int totalFUs = 0;
 653   // Parse functional units for all the itineraries.
 654   for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) {
 655     Record *Proc = ProcItinList[i];
 656     std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU");
 657
 658     DEBUG(dbgs() << "    FU:" << i
 659                  << " (" << FUs.size() << " FUs) "
 660                  << Proc->getName());
 661
 662
 663     // Convert macros to bits for each stage.
 664     unsigned numFUs = FUs.size();
 665     for (unsigned j = 0; j < numFUs; ++j) {
 666       assert ((j < DFA_MAX_RESOURCES) &&
 667                       "Exceeded maximum number of representable resources");
 668       unsigned FuncResources = (unsigned) (1U << j);
 669       FUNameToBitsMap[FUs[j]->getName()] = FuncResources;
 670       DEBUG(dbgs() << " " << FUs[j]->getName()
 671                    << ":0x" << utohexstr(FuncResources));
 672     }
 673     if (((int) numFUs) > maxFUs) {
 674       maxFUs = numFUs;
 675     }
 676     totalFUs += numFUs;
 677     DEBUG(dbgs() << "\n");
 678   }
 679   return totalFUs;
 680 }
 681
 682 //
 683 // collectAllComboFuncs - Construct a map from a combo function unit bit to
 684 //                        the bits of all included functional units.
 685 //
 686 int DFAPacketizerEmitter::collectAllComboFuncs(
 687                             std::vector<Record*> &ComboFuncList,
 688                             std::map<std::string, unsigned> &FUNameToBitsMap,
 689                             std::map<unsigned, unsigned> &ComboBitToBitsMap,
 690                             raw_ostream &OS) {
 691   DEBUG(dbgs() << "-----------------------------------------------------------------------------\n");
 692   DEBUG(dbgs() << "collectAllComboFuncs");
 693   DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");
 694
 695   int numCombos = 0;
 696   for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
 697     Record *Func = ComboFuncList[i];
 698     std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD");
 699
 700     DEBUG(dbgs() << "    CFD:" << i
 701                  << " (" << FUs.size() << " combo FUs) "
 702                  << Func->getName() << "\n");
 703
 704     // Convert macros to bits for each stage.
 705     for (unsigned j = 0, N = FUs.size(); j < N; ++j) {
 706       assert ((j < DFA_MAX_RESOURCES) &&
 707                       "Exceeded maximum number of DFA resources");
 708       Record *FuncData = FUs[j];
 709       Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");
 710       const std::vector<Record*> &FuncList =
 711                                    FuncData->getValueAsListOfDefs("FuncList");
 712       const std::string &ComboFuncName = ComboFunc->getName();
 713       unsigned ComboBit = FUNameToBitsMap[ComboFuncName];
 714       unsigned ComboResources = ComboBit;
 715       DEBUG(dbgs() << "      combo: " << ComboFuncName
 716                    << ":0x" << utohexstr(ComboResources) << "\n");
 717       for (unsigned k = 0, M = FuncList.size(); k < M; ++k) {
 718         std::string FuncName = FuncList[k]->getName();
 719         unsigned FuncResources = FUNameToBitsMap[FuncName];
 720         DEBUG(dbgs() << "        " << FuncName
 721                      << ":0x" << utohexstr(FuncResources) << "\n");
 722         ComboResources |= FuncResources;
 723       }
 724       ComboBitToBitsMap[ComboBit] = ComboResources;
 725       numCombos++;
 726       DEBUG(dbgs() << "          => combo bits: " << ComboFuncName << ":0x"
 727                    << utohexstr(ComboBit) << " = 0x"
 728                    << utohexstr(ComboResources) << "\n");
 729     }
 730   }
 731   return numCombos;
 732 }
 733
 734 //
 735 // collectOneInsnClass - Populate allInsnClasses with one instruction class
 736 //
 737 int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName,
 738                         std::vector<Record*> &ProcItinList,
 739                         std::map<std::string, unsigned> &FUNameToBitsMap,
 740                         Record *ItinData,
 741                         raw_ostream &OS) {
 742   const std::vector<Record*> &StageList =
 743     ItinData->getValueAsListOfDefs("Stages");
 744
 745   // The number of stages.
 746   unsigned NStages = StageList.size();
 747
 748   DEBUG(dbgs() << "    " << ItinData->getValueAsDef("TheClass")->getName()
 749                << "\n");
 750
 751   std::vector<unsigned> UnitBits;
 752
 753   // Compute the bitwise or of each unit used in this stage.
 754   for (unsigned i = 0; i < NStages; ++i) {
 755     const Record *Stage = StageList[i];
 756
 757     // Get unit list.
 758     const std::vector<Record*> &UnitList =
 759       Stage->getValueAsListOfDefs("Units");
 760
 761     DEBUG(dbgs() << "        stage:" << i
 762                  << " [" << UnitList.size() << " units]:");
 763     unsigned dbglen = 26;  // cursor after stage dbgs
 764
 765     // Compute the bitwise or of each unit used in this stage.
 766     unsigned UnitBitValue = 0;
 767     for (unsigned j = 0, M = UnitList.size(); j < M; ++j) {
 768       // Conduct bitwise or.
 769       std::string UnitName = UnitList[j]->getName();
 770       DEBUG(dbgs() << " " << j << ":" << UnitName);
 771       dbglen += 3 + UnitName.length();
 772       assert(FUNameToBitsMap.count(UnitName));
 773       UnitBitValue |= FUNameToBitsMap[UnitName];
 774     }
 775
 776     if (UnitBitValue != 0)
 777       UnitBits.push_back(UnitBitValue);
 778
 779     while (dbglen <= 64) {   // line up bits dbgs
 780         dbglen += 8;
 781         DEBUG(dbgs() << "\t");
 782     }
 783     DEBUG(dbgs() << " (bits: 0x" << utohexstr(UnitBitValue) << ")\n");
 784   }
 785
 786   if (UnitBits.size() > 0)
 787     allInsnClasses.push_back(UnitBits);
 788
 789   DEBUG({
 790     dbgs() << "        ";
 791     dbgsInsnClass(UnitBits);
 792     dbgs() << "\n";
 793   });
 794
 795   return NStages;
 796 }
 797
 798 //
 799 // collectAllInsnClasses - Populate allInsnClasses which is a set of units
 800 // used in each stage.
 801 //
 802 int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName,
 803                             std::vector<Record*> &ProcItinList,
 804                             std::map<std::string, unsigned> &FUNameToBitsMap,
 805                             std::vector<Record*> &ItinDataList,
 806                             int &maxStages,
 807                             raw_ostream &OS) {
 808   // Collect all instruction classes.
 809   unsigned M = ItinDataList.size();
 810
 811   int numInsnClasses = 0;
 812   DEBUG(dbgs() << "-----------------------------------------------------------------------------\n"
 813                << "collectAllInsnClasses "
 814                << ProcName
 815                << " (" << M << " classes)\n");
 816
 817   // Collect stages for each instruction class for all itinerary data
 818   for (unsigned j = 0; j < M; j++) {
 819     Record *ItinData = ItinDataList[j];
 820     int NStages = collectOneInsnClass(ProcName, ProcItinList,
 821                                       FUNameToBitsMap, ItinData, OS);
 822     if (NStages > maxStages) {
 823       maxStages = NStages;
 824     }
 825     numInsnClasses++;
 826   }
 827   return numInsnClasses;
 828 }
 829
 830 //
 831 // Run the worklist algorithm to generate the DFA.
 832 //
 833 void DFAPacketizerEmitter::run(raw_ostream &OS) {
 834
 835   // Collect processor iteraries.
 836   std::vector<Record*> ProcItinList =
 837     Records.getAllDerivedDefinitions("ProcessorItineraries");
 838
 839   //
 840   // Collect the Functional units.
 841   //
 842   std::map<std::string, unsigned> FUNameToBitsMap;
 843   int maxResources = 0;
 844   collectAllFuncUnits(ProcItinList,
 845                               FUNameToBitsMap, maxResources, OS);
 846
 847   //
 848   // Collect the Combo Functional units.
 849   //
 850   std::map<unsigned, unsigned> ComboBitToBitsMap;
 851   std::vector<Record*> ComboFuncList =
 852     Records.getAllDerivedDefinitions("ComboFuncUnits");
 853   int numCombos = collectAllComboFuncs(ComboFuncList,
 854                               FUNameToBitsMap, ComboBitToBitsMap, OS);
 855
 856   //
 857   // Collect the itineraries.
 858   //
 859   int maxStages = 0;
 860   int numInsnClasses = 0;
 861   for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) {
 862     Record *Proc = ProcItinList[i];
 863
 864     // Get processor itinerary name.
 865     const std::string &ProcName = Proc->getName();
 866
 867     // Skip default.
 868     if (ProcName == "NoItineraries")
 869       continue;
 870
 871     // Sanity check for at least one instruction itinerary class.
 872     unsigned NItinClasses =
 873       Records.getAllDerivedDefinitions("InstrItinClass").size();
 874     if (NItinClasses == 0)
 875       return;
 876
 877     // Get itinerary data list.
 878     std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID");
 879
 880     // Collect all instruction classes
 881     numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList,
 882                           FUNameToBitsMap, ItinDataList, maxStages, OS);
 883   }
 884
 885   //
 886   // Run a worklist algorithm to generate the DFA.
 887   //
 888   DFA D;
 889   const State *Initial = &D.newState();
 890   Initial->isInitial = true;
 891   Initial->stateInfo.insert(0x0);
 892   SmallVector<const State*, 32> WorkList;
 893 //  std::queue<State*> WorkList;
 894   std::map<std::set<unsigned>, const State*> Visited;
 895
 896   WorkList.push_back(Initial);
 897
 898   //
 899   // Worklist algorithm to create a DFA for processor resource tracking.
 900   // C = {set of InsnClasses}
 901   // Begin with initial node in worklist. Initial node does not have
 902   // any consumed resources,
 903   //     ResourceState = 0x0
 904   // Visited = {}
 905   // While worklist != empty
 906   //    S = first element of worklist
 907   //    For every instruction class C
 908   //      if we can accommodate C in S:
 909   //          S' = state with resource states = {S Union C}
 910   //          Add a new transition: S x C -> S'
 911   //          If S' is not in Visited:
 912   //             Add S' to worklist
 913   //             Add S' to Visited
 914   //
 915   while (!WorkList.empty()) {
 916     const State *current = WorkList.pop_back_val();
 917     DEBUG({
 918       dbgs() << "---------------------\n";
 919       dbgs() << "Processing state: " << current->stateNum << " - ";
 920       dbgsStateInfo(current->stateInfo);
 921       dbgs() << "\n";
 922     });
 923     for (unsigned i = 0; i < allInsnClasses.size(); i++) {
 924       std::vector<unsigned> InsnClass = allInsnClasses[i];
 925       DEBUG({
 926         dbgs() << i << " ";
 927         dbgsInsnClass(InsnClass);
 928         dbgs() << "\n";
 929       });
 930
 931       std::set<unsigned> NewStateResources;
 932       //
 933       // If we haven't already created a transition for this input
 934       // and the state can accommodate this InsnClass, create a transition.
 935       //
 936       if (!current->hasTransition(InsnClass) &&
 937           current->canMaybeAddInsnClass(InsnClass, ComboBitToBitsMap)) {
 938         const State *NewState = nullptr;
 939         current->AddInsnClass(InsnClass, ComboBitToBitsMap, NewStateResources);
 940         if (NewStateResources.size() == 0) {
 941           DEBUG(dbgs() << "  Skipped - no new states generated\n");
 942           continue;
 943         }
 944
 945         DEBUG({
 946           dbgs() << "\t";
 947           dbgsStateInfo(NewStateResources);
 948           dbgs() << "\n";
 949         });
 950
 951         //
 952         // If we have seen this state before, then do not create a new state.
 953         //
 954         auto VI = Visited.find(NewStateResources);
 955         if (VI != Visited.end()) {
 956           NewState = VI->second;
 957           DEBUG({
 958             dbgs() << "\tFound existing state: " << NewState->stateNum
 959                    << " - ";
 960             dbgsStateInfo(NewState->stateInfo);
 961             dbgs() << "\n";
 962           });
 963         } else {
 964           NewState = &D.newState();
 965           NewState->stateInfo = NewStateResources;
 966           Visited[NewStateResources] = NewState;
 967           WorkList.push_back(NewState);
 968           DEBUG({
 969             dbgs() << "\tAccepted new state: " << NewState->stateNum << " - ";
 970             dbgsStateInfo(NewState->stateInfo);
 971             dbgs() << "\n";
 972           });
 973         }
 974
 975         current->addTransition(InsnClass, NewState);
 976       }
 977     }
 978   }
 979
 980   // Print out the table.
 981   D.writeTableAndAPI(OS, TargetName,
 982                numInsnClasses, maxResources, numCombos, maxStages);
 983 }
 984
 985 namespace llvm {
 986
 987 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
 988   emitSourceFileHeader("Target DFA Packetizer Tables", OS);
 989   DFAPacketizerEmitter(RK).run(OS);
 990 }
 991
 992 } // end namespaec llvm