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