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" << Twine::utohexstr(InsnClass[i]));
 287   }
 288   DFAInput InsnInput = getDFAInsnInput(InsnClass);
 289   DEBUG(dbgs() << " (input: 0x" << Twine::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" << Twine::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" << Twine::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            << Twine::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" << Twine::utohexstr(prevState)
 399                      << " - combo op 0x" << Twine::utohexstr(resourceMask)
 400                      << " (0x" << Twine::utohexstr(combo)
 401                      << ") cannot be scheduled\n");
 402         continue;
 403       }
 404       //
 405       // For each possible resource used in thisStage, generate the
 406       // resource state if that resource was used.
 407       //
 408       unsigned ResultingResourceState = prevState | resourceMask | combo;
 409       DEBUG({
 410         dbgsIndent((2 + numstages - chkstage) << 1);
 411         dbgs() << "0x" << Twine::utohexstr(prevState) << " | 0x"
 412                << Twine::utohexstr(resourceMask);
 413         if (combo)
 414           dbgs() << " | 0x" << Twine::utohexstr(combo);
 415         dbgs() << " = 0x" << Twine::utohexstr(ResultingResourceState) << " ";
 416       });
 417
 418       //
 419       // If this is the final stage for this class
 420       //
 421       if (chkstage == 0) {
 422         //
 423         // Check if the resulting resource state can be accommodated in this
 424         // packet.
 425         // We compute resource OR prevState (originally started as origState).
 426         // If the result of the OR is different than origState, it implies
 427         // that there is at least one resource that can be used to schedule
 428         // thisStage in the current packet.
 429         // Insert ResultingResourceState into PossibleStates only if we haven't
 430         // processed ResultingResourceState before.
 431         //
 432         if (ResultingResourceState != prevState) {
 433           if (VisitedResourceStates.count(ResultingResourceState) == 0) {
 434             VisitedResourceStates.insert(ResultingResourceState);
 435             PossibleStates.insert(ResultingResourceState);
 436             DEBUG(dbgs() << "\tResultingResourceState: 0x"
 437                          << Twine::utohexstr(ResultingResourceState) << "\n");
 438           } else {
 439             DEBUG(dbgs() << "\tSkipped Add - state already seen\n");
 440           }
 441         } else {
 442           DEBUG(dbgs() << "\tSkipped Add - no final resources available\n");
 443         }
 444       } else {
 445         //
 446         // If the current resource can be accommodated, check the next
 447         // stage in InsnClass for available resources.
 448         //
 449         if (ResultingResourceState != prevState) {
 450           DEBUG(dbgs() << "\n");
 451           AddInsnClassStages(InsnClass, ComboBitToBitsMap,
 452                                 chkstage - 1, numstages,
 453                                 ResultingResourceState, origState,
 454                                 VisitedResourceStates, PossibleStates);
 455         } else {
 456           DEBUG(dbgs() << "\tSkipped Add - no resources available\n");
 457         }
 458       }
 459     }
 460   }
 461 }
 462
 463 //
 464 // canMaybeAddInsnClass - Quickly verifies if an instruction of type InsnClass
 465 // may be a valid transition from this state i.e., can an instruction of type
 466 // InsnClass be added to the packet represented by this state.
 467 //
 468 // Note that this routine is performing conservative checks that can be
 469 // quickly executed acting as a filter before calling AddInsnClassStages.
 470 // Any cases allowed through here will be caught later in AddInsnClassStages
 471 // which performs the more expensive exact check.
 472 //
 473 bool State::canMaybeAddInsnClass(std::vector<unsigned> &InsnClass,
 474                     std::map<unsigned, unsigned> &ComboBitToBitsMap) const {
 475   for (std::set<unsigned>::const_iterator SI = stateInfo.begin();
 476        SI != stateInfo.end(); ++SI) {
 477     // Check to see if all required resources are available.
 478     bool available = true;
 479
 480     // Inspect each stage independently.
 481     // note: This is a conservative check as we aren't checking for
 482     //       possible resource competition between the stages themselves
 483     //       The full cross product is examined later in AddInsnClass.
 484     for (unsigned i = 0; i < InsnClass.size(); ++i) {
 485       unsigned resources = *SI;
 486       if ((~resources & InsnClass[i]) == 0) {
 487         available = false;
 488         break;
 489       }
 490       // Make sure _all_ resources for a combo function are available.
 491       // note: This is a quick conservative check as it won't catch an
 492       //       unscheduleable combo if this stage is an OR expression
 493       //       containing a combo.
 494       //       These cases are caught later in AddInsnClass.
 495       unsigned combo = ComboBitToBitsMap[InsnClass[i]];
 496       if (combo && ((~resources & combo) != combo)) {
 497         DEBUG(dbgs() << "\tSkipped canMaybeAdd 0x"
 498                      << Twine::utohexstr(resources) << " - combo op 0x"
 499                      << Twine::utohexstr(InsnClass[i]) << " (0x"
 500                      << Twine::utohexstr(combo) << ") cannot be scheduled\n");
 501         available = false;
 502         break;
 503       }
 504     }
 505
 506     if (available) {
 507       return true;
 508     }
 509   }
 510   return false;
 511 }
 512
 513 const State &DFA::newState() {
 514   auto IterPair = states.insert(State());
 515   assert(IterPair.second && "State already exists");
 516   return *IterPair.first;
 517 }
 518
 519 int State::currentStateNum = 0;
 520
 521 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R):
 522   TargetName(CodeGenTarget(R).getName()), Records(R) {}
 523
 524 //
 525 // writeTableAndAPI - Print out a table representing the DFA and the
 526 // associated API to create a DFA packetizer.
 527 //
 528 // Format:
 529 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
 530 //                           transitions.
 531 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for
 532 //                         the ith state.
 533 //
 534 //
 535 void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName,
 536                            int numInsnClasses,
 537                            int maxResources, int numCombos, int maxStages) {
 538   unsigned numStates = states.size();
 539
 540   DEBUG(dbgs() << "-----------------------------------------------------------------------------\n");
 541   DEBUG(dbgs() << "writeTableAndAPI\n");
 542   DEBUG(dbgs() << "Total states: " << numStates << "\n");
 543
 544   OS << "namespace llvm {\n";
 545
 546   OS << "\n// Input format:\n";
 547   OS << "#define DFA_MAX_RESTERMS        " << DFA_MAX_RESTERMS
 548      << "\t// maximum AND'ed resource terms\n";
 549   OS << "#define DFA_MAX_RESOURCES       " << DFA_MAX_RESOURCES
 550      << "\t// maximum resource bits in one term\n";
 551
 552   OS << "\n// " << TargetName << "DFAStateInputTable[][2] = "
 553      << "pairs of <Input, NextState> for all valid\n";
 554   OS << "//                           transitions.\n";
 555   OS << "// " << numStates << "\tstates\n";
 556   OS << "// " << numInsnClasses << "\tinstruction classes\n";
 557   OS << "// " << maxResources << "\tresources max\n";
 558   OS << "// " << numCombos << "\tcombo resources\n";
 559   OS << "// " << maxStages << "\tstages max\n";
 560   OS << "const " << DFA_TBLTYPE << " "
 561      << TargetName << "DFAStateInputTable[][2] = {\n";
 562
 563   // This table provides a map to the beginning of the transitions for State s
 564   // in DFAStateInputTable.
 565   std::vector<int> StateEntry(numStates+1);
 566   static const std::string SentinelEntry = "{-1, -1}";
 567
 568   // Tracks the total valid transitions encountered so far. It is used
 569   // to construct the StateEntry table.
 570   int ValidTransitions = 0;
 571   DFA::StateSet::iterator SI = states.begin();
 572   for (unsigned i = 0; i < numStates; ++i, ++SI) {
 573     assert ((SI->stateNum == (int) i) && "Mismatch in state numbers");
 574     StateEntry[i] = ValidTransitions;
 575     for (State::TransitionMap::iterator
 576         II = SI->Transitions.begin(), IE = SI->Transitions.end();
 577         II != IE; ++II) {
 578       OS << "{0x" << Twine::utohexstr(getDFAInsnInput(II->first)) << ", "
 579          << II->second->stateNum << "},\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   // Emit DFA Packetizer tables if the target is a VLIW machine.
 631   //
 632   std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
 633   OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
 634   OS << "namespace llvm {\n";
 635   OS << "DFAPacketizer *" << SubTargetClassName << "::"
 636      << "createDFAPacketizer(const InstrItineraryData *IID) const {\n"
 637      << "   return new DFAPacketizer(IID, " << TargetName
 638      << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n";
 639   OS << "} // End llvm namespace \n";
 640 }
 641
 642 //
 643 // collectAllFuncUnits - Construct a map of function unit names to bits.
 644 //
 645 int DFAPacketizerEmitter::collectAllFuncUnits(
 646                             std::vector<Record*> &ProcItinList,
 647                             std::map<std::string, unsigned> &FUNameToBitsMap,
 648                             int &maxFUs,
 649                             raw_ostream &OS) {
 650   DEBUG(dbgs() << "-----------------------------------------------------------------------------\n");
 651   DEBUG(dbgs() << "collectAllFuncUnits");
 652   DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n");
 653
 654   int totalFUs = 0;
 655   // Parse functional units for all the itineraries.
 656   for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) {
 657     Record *Proc = ProcItinList[i];
 658     std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU");
 659
 660     DEBUG(dbgs() << "    FU:" << i
 661                  << " (" << FUs.size() << " FUs) "
 662                  << Proc->getName());
 663
 664
 665     // Convert macros to bits for each stage.
 666     unsigned numFUs = FUs.size();
 667     for (unsigned j = 0; j < numFUs; ++j) {
 668       assert ((j < DFA_MAX_RESOURCES) &&
 669                       "Exceeded maximum number of representable resources");
 670       unsigned FuncResources = (unsigned) (1U << j);
 671       FUNameToBitsMap[FUs[j]->getName()] = FuncResources;
 672       DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"
 673                    << Twine::utohexstr(FuncResources));
 674     }
 675     if (((int) numFUs) > maxFUs) {
 676       maxFUs = numFUs;
 677     }
 678     totalFUs += numFUs;
 679     DEBUG(dbgs() << "\n");
 680   }
 681   return totalFUs;
 682 }
 683
 684 //
 685 // collectAllComboFuncs - Construct a map from a combo function unit bit to
 686 //                        the bits of all included functional units.
 687 //
 688 int DFAPacketizerEmitter::collectAllComboFuncs(
 689                             std::vector<Record*> &ComboFuncList,
 690                             std::map<std::string, unsigned> &FUNameToBitsMap,
 691                             std::map<unsigned, unsigned> &ComboBitToBitsMap,
 692                             raw_ostream &OS) {
 693   DEBUG(dbgs() << "-----------------------------------------------------------------------------\n");
 694   DEBUG(dbgs() << "collectAllComboFuncs");
 695   DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");
 696
 697   int numCombos = 0;
 698   for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
 699     Record *Func = ComboFuncList[i];
 700     std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD");
 701
 702     DEBUG(dbgs() << "    CFD:" << i
 703                  << " (" << FUs.size() << " combo FUs) "
 704                  << Func->getName() << "\n");
 705
 706     // Convert macros to bits for each stage.
 707     for (unsigned j = 0, N = FUs.size(); j < N; ++j) {
 708       assert ((j < DFA_MAX_RESOURCES) &&
 709                       "Exceeded maximum number of DFA resources");
 710       Record *FuncData = FUs[j];
 711       Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");
 712       const std::vector<Record*> &FuncList =
 713                                    FuncData->getValueAsListOfDefs("FuncList");
 714       const std::string &ComboFuncName = ComboFunc->getName();
 715       unsigned ComboBit = FUNameToBitsMap[ComboFuncName];
 716       unsigned ComboResources = ComboBit;
 717       DEBUG(dbgs() << "      combo: " << ComboFuncName << ":0x"
 718                    << Twine::utohexstr(ComboResources) << "\n");
 719       for (unsigned k = 0, M = FuncList.size(); k < M; ++k) {
 720         std::string FuncName = FuncList[k]->getName();
 721         unsigned FuncResources = FUNameToBitsMap[FuncName];
 722         DEBUG(dbgs() << "        " << FuncName << ":0x"
 723                      << Twine::utohexstr(FuncResources) << "\n");
 724         ComboResources |= FuncResources;
 725       }
 726       ComboBitToBitsMap[ComboBit] = ComboResources;
 727       numCombos++;
 728       DEBUG(dbgs() << "          => combo bits: " << ComboFuncName << ":0x"
 729                    << Twine::utohexstr(ComboBit) << " = 0x"
 730                    << Twine::utohexstr(ComboResources) << "\n");
 731     }
 732   }
 733   return numCombos;
 734 }
 735
 736 //
 737 // collectOneInsnClass - Populate allInsnClasses with one instruction class
 738 //
 739 int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName,
 740                         std::vector<Record*> &ProcItinList,
 741                         std::map<std::string, unsigned> &FUNameToBitsMap,
 742                         Record *ItinData,
 743                         raw_ostream &OS) {
 744   const std::vector<Record*> &StageList =
 745     ItinData->getValueAsListOfDefs("Stages");
 746
 747   // The number of stages.
 748   unsigned NStages = StageList.size();
 749
 750   DEBUG(dbgs() << "    " << ItinData->getValueAsDef("TheClass")->getName()
 751                << "\n");
 752
 753   std::vector<unsigned> UnitBits;
 754
 755   // Compute the bitwise or of each unit used in this stage.
 756   for (unsigned i = 0; i < NStages; ++i) {
 757     const Record *Stage = StageList[i];
 758
 759     // Get unit list.
 760     const std::vector<Record*> &UnitList =
 761       Stage->getValueAsListOfDefs("Units");
 762
 763     DEBUG(dbgs() << "        stage:" << i
 764                  << " [" << UnitList.size() << " units]:");
 765     unsigned dbglen = 26;  // cursor after stage dbgs
 766
 767     // Compute the bitwise or of each unit used in this stage.
 768     unsigned UnitBitValue = 0;
 769     for (unsigned j = 0, M = UnitList.size(); j < M; ++j) {
 770       // Conduct bitwise or.
 771       std::string UnitName = UnitList[j]->getName();
 772       DEBUG(dbgs() << " " << j << ":" << UnitName);
 773       dbglen += 3 + UnitName.length();
 774       assert(FUNameToBitsMap.count(UnitName));
 775       UnitBitValue |= FUNameToBitsMap[UnitName];
 776     }
 777
 778     if (UnitBitValue != 0)
 779       UnitBits.push_back(UnitBitValue);
 780
 781     while (dbglen <= 64) {   // line up bits dbgs
 782         dbglen += 8;
 783         DEBUG(dbgs() << "\t");
 784     }
 785     DEBUG(dbgs() << " (bits: 0x" << Twine::utohexstr(UnitBitValue) << ")\n");
 786   }
 787
 788   if (!UnitBits.empty())
 789     allInsnClasses.push_back(UnitBits);
 790
 791   DEBUG({
 792     dbgs() << "        ";
 793     dbgsInsnClass(UnitBits);
 794     dbgs() << "\n";
 795   });
 796
 797   return NStages;
 798 }
 799
 800 //
 801 // collectAllInsnClasses - Populate allInsnClasses which is a set of units
 802 // used in each stage.
 803 //
 804 int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName,
 805                             std::vector<Record*> &ProcItinList,
 806                             std::map<std::string, unsigned> &FUNameToBitsMap,
 807                             std::vector<Record*> &ItinDataList,
 808                             int &maxStages,
 809                             raw_ostream &OS) {
 810   // Collect all instruction classes.
 811   unsigned M = ItinDataList.size();
 812
 813   int numInsnClasses = 0;
 814   DEBUG(dbgs() << "-----------------------------------------------------------------------------\n"
 815                << "collectAllInsnClasses "
 816                << ProcName
 817                << " (" << M << " classes)\n");
 818
 819   // Collect stages for each instruction class for all itinerary data
 820   for (unsigned j = 0; j < M; j++) {
 821     Record *ItinData = ItinDataList[j];
 822     int NStages = collectOneInsnClass(ProcName, ProcItinList,
 823                                       FUNameToBitsMap, ItinData, OS);
 824     if (NStages > maxStages) {
 825       maxStages = NStages;
 826     }
 827     numInsnClasses++;
 828   }
 829   return numInsnClasses;
 830 }
 831
 832 //
 833 // Run the worklist algorithm to generate the DFA.
 834 //
 835 void DFAPacketizerEmitter::run(raw_ostream &OS) {
 836   // Collect processor iteraries.
 837   std::vector<Record*> ProcItinList =
 838     Records.getAllDerivedDefinitions("ProcessorItineraries");
 839
 840   //
 841   // Collect the Functional units.
 842   //
 843   std::map<std::string, unsigned> FUNameToBitsMap;
 844   int maxResources = 0;
 845   collectAllFuncUnits(ProcItinList,
 846                               FUNameToBitsMap, maxResources, OS);
 847
 848   //
 849   // Collect the Combo Functional units.
 850   //
 851   std::map<unsigned, unsigned> ComboBitToBitsMap;
 852   std::vector<Record*> ComboFuncList =
 853     Records.getAllDerivedDefinitions("ComboFuncUnits");
 854   int numCombos = collectAllComboFuncs(ComboFuncList,
 855                               FUNameToBitsMap, ComboBitToBitsMap, OS);
 856
 857   //
 858   // Collect the itineraries.
 859   //
 860   int maxStages = 0;
 861   int numInsnClasses = 0;
 862   for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) {
 863     Record *Proc = ProcItinList[i];
 864
 865     // Get processor itinerary name.
 866     const std::string &ProcName = Proc->getName();
 867
 868     // Skip default.
 869     if (ProcName == "NoItineraries")
 870       continue;
 871
 872     // Sanity check for at least one instruction itinerary class.
 873     unsigned NItinClasses =
 874       Records.getAllDerivedDefinitions("InstrItinClass").size();
 875     if (NItinClasses == 0)
 876       return;
 877
 878     // Get itinerary data list.
 879     std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID");
 880
 881     // Collect all instruction classes
 882     numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList,
 883                           FUNameToBitsMap, ItinDataList, maxStages, OS);
 884   }
 885
 886   //
 887   // Run a worklist algorithm to generate the DFA.
 888   //
 889   DFA D;
 890   const State *Initial = &D.newState();
 891   Initial->isInitial = true;
 892   Initial->stateInfo.insert(0x0);
 893   SmallVector<const State*, 32> 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.empty()) {
 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 namespace llvm