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