utils/TableGen/DFAPacketizerEmitter.cpp

   1 //===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This class parses the Schedule.td file and produces an API that can be used
  10 // to reason about whether an instruction can be added to a packet on a VLIW
  11 // architecture. The class internally generates a deterministic finite
  12 // automaton (DFA) that models all possible mappings of machine instructions
  13 // to functional units as instructions are added to a packet.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define DEBUG_TYPE "dfa-emitter"
  18
  19 #include "CodeGenTarget.h"
  20 #include "DFAEmitter.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 <unordered_map>
  34 #include <vector>
  35
  36 using namespace llvm;
  37
  38 // --------------------------------------------------------------------
  39 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
  40
  41 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
  42 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
  43 //
  44 // e.g. terms x resource bit combinations that fit in uint32_t:
  45 //      4 terms x 8  bits = 32 bits
  46 //      3 terms x 10 bits = 30 bits
  47 //      2 terms x 16 bits = 32 bits
  48 //
  49 // e.g. terms x resource bit combinations that fit in uint64_t:
  50 //      8 terms x 8  bits = 64 bits
  51 //      7 terms x 9  bits = 63 bits
  52 //      6 terms x 10 bits = 60 bits
  53 //      5 terms x 12 bits = 60 bits
  54 //      4 terms x 16 bits = 64 bits <--- current
  55 //      3 terms x 21 bits = 63 bits
  56 //      2 terms x 32 bits = 64 bits
  57 //
  58 #define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
  59 #define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.
  60
  61 typedef uint64_t                DFAInput;
  62 typedef int64_t                 DFAStateInput;
  63 #define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
  64
  65 namespace {
  66
  67   DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
  68     return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
  69   }
  70
  71   /// Return the DFAInput for an instruction class input vector.
  72   /// This function is used in both DFAPacketizer.cpp and in
  73   /// DFAPacketizerEmitter.cpp.
  74   DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
  75     DFAInput InsnInput = 0;
  76     assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
  77            "Exceeded maximum number of DFA terms");
  78     for (auto U : InsnClass)
  79       InsnInput = addDFAFuncUnits(InsnInput, U);
  80     return InsnInput;
  81   }
  82
  83 } // end anonymous namespace
  84
  85 // --------------------------------------------------------------------
  86
  87 #ifndef NDEBUG
  88 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
  89 //
  90 // dbgsInsnClass - When debugging, print instruction class stages.
  91 //
  92 void dbgsInsnClass(const std::vector<unsigned> &InsnClass);
  93 //
  94 // dbgsStateInfo - When debugging, print the set of state info.
  95 //
  96 void dbgsStateInfo(const std::set<unsigned> &stateInfo);
  97 //
  98 // dbgsIndent - When debugging, indent by the specified amount.
  99 //
 100 void dbgsIndent(unsigned indent);
 101 #endif
 102
 103 //
 104 // class DFAPacketizerEmitter: class that generates and prints out the DFA
 105 // for resource tracking.
 106 //
 107 namespace {
 108
 109 class DFAPacketizerEmitter {
 110 private:
 111   std::string TargetName;
 112   //
 113   // allInsnClasses is the set of all possible resources consumed by an
 114   // InstrStage.
 115   //
 116   std::vector<std::vector<unsigned>> allInsnClasses;
 117   RecordKeeper &Records;
 118
 119 public:
 120   DFAPacketizerEmitter(RecordKeeper &R);
 121
 122   //
 123   // collectAllFuncUnits - Construct a map of function unit names to bits.
 124   //
 125   int collectAllFuncUnits(std::vector<Record*> &ProcItinList,
 126                            std::map<std::string, unsigned> &FUNameToBitsMap,
 127                            int &maxResources,
 128                            raw_ostream &OS);
 129
 130   //
 131   // collectAllComboFuncs - Construct a map from a combo function unit bit to
 132   //                        the bits of all included functional units.
 133   //
 134   int collectAllComboFuncs(std::vector<Record*> &ComboFuncList,
 135                            std::map<std::string, unsigned> &FUNameToBitsMap,
 136                            std::map<unsigned, unsigned> &ComboBitToBitsMap,
 137                            raw_ostream &OS);
 138
 139   //
 140   // collectOneInsnClass - Populate allInsnClasses with one instruction class.
 141   //
 142   int collectOneInsnClass(const std::string &ProcName,
 143                            std::vector<Record*> &ProcItinList,
 144                            std::map<std::string, unsigned> &FUNameToBitsMap,
 145                            Record *ItinData,
 146                            raw_ostream &OS);
 147
 148   //
 149   // collectAllInsnClasses - Populate allInsnClasses which is a set of units
 150   // used in each stage.
 151   //
 152   int collectAllInsnClasses(const std::string &ProcName,
 153                            std::vector<Record*> &ProcItinList,
 154                            std::map<std::string, unsigned> &FUNameToBitsMap,
 155                            std::vector<Record*> &ItinDataList,
 156                            int &maxStages,
 157                            raw_ostream &OS);
 158
 159   // Emit code for a subset of itineraries.
 160   void emitForItineraries(raw_ostream &OS,
 161                           std::vector<Record *> &ProcItinList,
 162                           std::string DFAName);
 163
 164   void run(raw_ostream &OS);
 165 };
 166 } // end anonymous namespace
 167
 168 #ifndef NDEBUG
 169 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
 170 //
 171 // dbgsInsnClass - When debugging, print instruction class stages.
 172 //
 173 void dbgsInsnClass(const std::vector<unsigned> &InsnClass) {
 174   LLVM_DEBUG(dbgs() << "InsnClass: ");
 175   for (unsigned i = 0; i < InsnClass.size(); ++i) {
 176     if (i > 0) {
 177       LLVM_DEBUG(dbgs() << ", ");
 178     }
 179     LLVM_DEBUG(dbgs() << "0x" << Twine::utohexstr(InsnClass[i]));
 180   }
 181   DFAInput InsnInput = getDFAInsnInput(InsnClass);
 182   LLVM_DEBUG(dbgs() << " (input: 0x" << Twine::utohexstr(InsnInput) << ")");
 183 }
 184
 185 //
 186 // dbgsIndent - When debugging, indent by the specified amount.
 187 //
 188 void dbgsIndent(unsigned indent) {
 189   for (unsigned i = 0; i < indent; ++i) {
 190     LLVM_DEBUG(dbgs() << " ");
 191   }
 192 }
 193 #endif // NDEBUG
 194
 195 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R):
 196   TargetName(CodeGenTarget(R).getName()), Records(R) {}
 197
 198 //
 199 // collectAllFuncUnits - Construct a map of function unit names to bits.
 200 //
 201 int DFAPacketizerEmitter::collectAllFuncUnits(
 202                             std::vector<Record*> &ProcItinList,
 203                             std::map<std::string, unsigned> &FUNameToBitsMap,
 204                             int &maxFUs,
 205                             raw_ostream &OS) {
 206   LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
 207                        "----------------------\n");
 208   LLVM_DEBUG(dbgs() << "collectAllFuncUnits");
 209   LLVM_DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n");
 210
 211   int totalFUs = 0;
 212   // Parse functional units for all the itineraries.
 213   for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) {
 214     Record *Proc = ProcItinList[i];
 215     std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU");
 216
 217     LLVM_DEBUG(dbgs() << "    FU:" << i << " (" << FUs.size() << " FUs) "
 218                       << Proc->getName());
 219
 220     // Convert macros to bits for each stage.
 221     unsigned numFUs = FUs.size();
 222     for (unsigned j = 0; j < numFUs; ++j) {
 223       assert ((j < DFA_MAX_RESOURCES) &&
 224                       "Exceeded maximum number of representable resources");
 225       unsigned FuncResources = (unsigned) (1U << j);
 226       FUNameToBitsMap[FUs[j]->getName()] = FuncResources;
 227       LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"
 228                         << Twine::utohexstr(FuncResources));
 229     }
 230     if (((int) numFUs) > maxFUs) {
 231       maxFUs = numFUs;
 232     }
 233     totalFUs += numFUs;
 234     LLVM_DEBUG(dbgs() << "\n");
 235   }
 236   return totalFUs;
 237 }
 238
 239 //
 240 // collectAllComboFuncs - Construct a map from a combo function unit bit to
 241 //                        the bits of all included functional units.
 242 //
 243 int DFAPacketizerEmitter::collectAllComboFuncs(
 244                             std::vector<Record*> &ComboFuncList,
 245                             std::map<std::string, unsigned> &FUNameToBitsMap,
 246                             std::map<unsigned, unsigned> &ComboBitToBitsMap,
 247                             raw_ostream &OS) {
 248   LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
 249                        "----------------------\n");
 250   LLVM_DEBUG(dbgs() << "collectAllComboFuncs");
 251   LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");
 252
 253   int numCombos = 0;
 254   for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
 255     Record *Func = ComboFuncList[i];
 256     std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD");
 257
 258     LLVM_DEBUG(dbgs() << "    CFD:" << i << " (" << FUs.size() << " combo FUs) "
 259                       << Func->getName() << "\n");
 260
 261     // Convert macros to bits for each stage.
 262     for (unsigned j = 0, N = FUs.size(); j < N; ++j) {
 263       assert ((j < DFA_MAX_RESOURCES) &&
 264                       "Exceeded maximum number of DFA resources");
 265       Record *FuncData = FUs[j];
 266       Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");
 267       const std::vector<Record*> &FuncList =
 268                                    FuncData->getValueAsListOfDefs("FuncList");
 269       const std::string &ComboFuncName = ComboFunc->getName();
 270       unsigned ComboBit = FUNameToBitsMap[ComboFuncName];
 271       unsigned ComboResources = ComboBit;
 272       LLVM_DEBUG(dbgs() << "      combo: " << ComboFuncName << ":0x"
 273                         << Twine::utohexstr(ComboResources) << "\n");
 274       for (unsigned k = 0, M = FuncList.size(); k < M; ++k) {
 275         std::string FuncName = FuncList[k]->getName();
 276         unsigned FuncResources = FUNameToBitsMap[FuncName];
 277         LLVM_DEBUG(dbgs() << "        " << FuncName << ":0x"
 278                           << Twine::utohexstr(FuncResources) << "\n");
 279         ComboResources |= FuncResources;
 280       }
 281       ComboBitToBitsMap[ComboBit] = ComboResources;
 282       numCombos++;
 283       LLVM_DEBUG(dbgs() << "          => combo bits: " << ComboFuncName << ":0x"
 284                         << Twine::utohexstr(ComboBit) << " = 0x"
 285                         << Twine::utohexstr(ComboResources) << "\n");
 286     }
 287   }
 288   return numCombos;
 289 }
 290
 291 //
 292 // collectOneInsnClass - Populate allInsnClasses with one instruction class
 293 //
 294 int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName,
 295                         std::vector<Record*> &ProcItinList,
 296                         std::map<std::string, unsigned> &FUNameToBitsMap,
 297                         Record *ItinData,
 298                         raw_ostream &OS) {
 299   const std::vector<Record*> &StageList =
 300     ItinData->getValueAsListOfDefs("Stages");
 301
 302   // The number of stages.
 303   unsigned NStages = StageList.size();
 304
 305   LLVM_DEBUG(dbgs() << "    " << ItinData->getValueAsDef("TheClass")->getName()
 306                     << "\n");
 307
 308   std::vector<unsigned> UnitBits;
 309
 310   // Compute the bitwise or of each unit used in this stage.
 311   for (unsigned i = 0; i < NStages; ++i) {
 312     const Record *Stage = StageList[i];
 313
 314     // Get unit list.
 315     const std::vector<Record*> &UnitList =
 316       Stage->getValueAsListOfDefs("Units");
 317
 318     LLVM_DEBUG(dbgs() << "        stage:" << i << " [" << UnitList.size()
 319                       << " units]:");
 320     unsigned dbglen = 26;  // cursor after stage dbgs
 321
 322     // Compute the bitwise or of each unit used in this stage.
 323     unsigned UnitBitValue = 0;
 324     for (unsigned j = 0, M = UnitList.size(); j < M; ++j) {
 325       // Conduct bitwise or.
 326       std::string UnitName = UnitList[j]->getName();
 327       LLVM_DEBUG(dbgs() << " " << j << ":" << UnitName);
 328       dbglen += 3 + UnitName.length();
 329       assert(FUNameToBitsMap.count(UnitName));
 330       UnitBitValue |= FUNameToBitsMap[UnitName];
 331     }
 332
 333     if (UnitBitValue != 0)
 334       UnitBits.push_back(UnitBitValue);
 335
 336     while (dbglen <= 64) {   // line up bits dbgs
 337         dbglen += 8;
 338         LLVM_DEBUG(dbgs() << "\t");
 339     }
 340     LLVM_DEBUG(dbgs() << " (bits: 0x" << Twine::utohexstr(UnitBitValue)
 341                       << ")\n");
 342   }
 343
 344   if (!UnitBits.empty())
 345     allInsnClasses.push_back(UnitBits);
 346
 347   LLVM_DEBUG({
 348     dbgs() << "        ";
 349     dbgsInsnClass(UnitBits);
 350     dbgs() << "\n";
 351   });
 352
 353   return NStages;
 354 }
 355
 356 //
 357 // collectAllInsnClasses - Populate allInsnClasses which is a set of units
 358 // used in each stage.
 359 //
 360 int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName,
 361                             std::vector<Record*> &ProcItinList,
 362                             std::map<std::string, unsigned> &FUNameToBitsMap,
 363                             std::vector<Record*> &ItinDataList,
 364                             int &maxStages,
 365                             raw_ostream &OS) {
 366   // Collect all instruction classes.
 367   unsigned M = ItinDataList.size();
 368
 369   int numInsnClasses = 0;
 370   LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
 371                        "----------------------\n"
 372                     << "collectAllInsnClasses " << ProcName << " (" << M
 373                     << " classes)\n");
 374
 375   // Collect stages for each instruction class for all itinerary data
 376   for (unsigned j = 0; j < M; j++) {
 377     Record *ItinData = ItinDataList[j];
 378     int NStages = collectOneInsnClass(ProcName, ProcItinList,
 379                                       FUNameToBitsMap, ItinData, OS);
 380     if (NStages > maxStages) {
 381       maxStages = NStages;
 382     }
 383     numInsnClasses++;
 384   }
 385   return numInsnClasses;
 386 }
 387
 388 //
 389 // Run the worklist algorithm to generate the DFA.
 390 //
 391 void DFAPacketizerEmitter::run(raw_ostream &OS) {
 392   OS << "\n"
 393      << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
 394   OS << "namespace llvm {\n";
 395
 396   OS << "\n// Input format:\n";
 397   OS << "#define DFA_MAX_RESTERMS        " << DFA_MAX_RESTERMS
 398      << "\t// maximum AND'ed resource terms\n";
 399   OS << "#define DFA_MAX_RESOURCES       " << DFA_MAX_RESOURCES
 400      << "\t// maximum resource bits in one term\n";
 401
 402   // Collect processor iteraries.
 403   std::vector<Record*> ProcItinList =
 404     Records.getAllDerivedDefinitions("ProcessorItineraries");
 405
 406   std::unordered_map<std::string, std::vector<Record*>> ItinsByNamespace;
 407   for (Record *R : ProcItinList)
 408     ItinsByNamespace[R->getValueAsString("PacketizerNamespace")].push_back(R);
 409
 410   for (auto &KV : ItinsByNamespace)
 411     emitForItineraries(OS, KV.second, KV.first);
 412   OS << "} // end namespace llvm\n";
 413 }
 414
 415 void DFAPacketizerEmitter::emitForItineraries(
 416     raw_ostream &OS, std::vector<Record *> &ProcItinList,
 417     std::string DFAName) {
 418   //
 419   // Collect the Functional units.
 420   //
 421   std::map<std::string, unsigned> FUNameToBitsMap;
 422   int maxResources = 0;
 423   collectAllFuncUnits(ProcItinList,
 424                               FUNameToBitsMap, maxResources, OS);
 425
 426   //
 427   // Collect the Combo Functional units.
 428   //
 429   std::map<unsigned, unsigned> ComboBitToBitsMap;
 430   std::vector<Record*> ComboFuncList =
 431     Records.getAllDerivedDefinitions("ComboFuncUnits");
 432   collectAllComboFuncs(ComboFuncList, FUNameToBitsMap, ComboBitToBitsMap, OS);
 433
 434   //
 435   // Collect the itineraries.
 436   //
 437   int maxStages = 0;
 438   int numInsnClasses = 0;
 439   for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) {
 440     Record *Proc = ProcItinList[i];
 441
 442     // Get processor itinerary name.
 443     const std::string &ProcName = Proc->getName();
 444
 445     // Skip default.
 446     if (ProcName == "NoItineraries")
 447       continue;
 448
 449     // Sanity check for at least one instruction itinerary class.
 450     unsigned NItinClasses =
 451       Records.getAllDerivedDefinitions("InstrItinClass").size();
 452     if (NItinClasses == 0)
 453       return;
 454
 455     // Get itinerary data list.
 456     std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID");
 457
 458     // Collect all instruction classes
 459     numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList,
 460                           FUNameToBitsMap, ItinDataList, maxStages, OS);
 461   }
 462
 463   // The type of a state in the nondeterministic automaton we're defining.
 464   using NfaStateTy = unsigned;
 465
 466   // Given a resource state, return all resource states by applying
 467   // InsnClass.
 468   auto applyInsnClass = [&](ArrayRef<unsigned> InsnClass,
 469                             NfaStateTy State) -> std::deque<unsigned> {
 470     std::deque<unsigned> V(1, State);
 471     // Apply every stage in the class individually.
 472     for (unsigned Stage : InsnClass) {
 473       // Apply this stage to every existing member of V in turn.
 474       size_t Sz = V.size();
 475       for (unsigned I = 0; I < Sz; ++I) {
 476         unsigned S = V.front();
 477         V.pop_front();
 478
 479         // For this stage, state combination, try all possible resources.
 480         for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) {
 481           unsigned ResourceMask = 1U << J;
 482           if ((ResourceMask & Stage) == 0)
 483             // This resource isn't required by this stage.
 484             continue;
 485           unsigned Combo = ComboBitToBitsMap[ResourceMask];
 486           if (Combo && ((~S & Combo) != Combo))
 487             // This combo units bits are not available.
 488             continue;
 489           unsigned ResultingResourceState = S | ResourceMask | Combo;
 490           if (ResultingResourceState == S)
 491             continue;
 492           V.push_back(ResultingResourceState);
 493         }
 494       }
 495     }
 496     return V;
 497   };
 498
 499   // Given a resource state, return a quick (conservative) guess as to whether
 500   // InsnClass can be applied. This is a filter for the more heavyweight
 501   // applyInsnClass.
 502   auto canApplyInsnClass = [](ArrayRef<unsigned> InsnClass,
 503                               NfaStateTy State) -> bool {
 504     for (unsigned Resources : InsnClass) {
 505       if ((State | Resources) == State)
 506         return false;
 507     }
 508     return true;
 509   };
 510
 511   DfaEmitter Emitter;
 512   std::deque<NfaStateTy> Worklist(1, 0);
 513   std::set<NfaStateTy> SeenStates;
 514   SeenStates.insert(Worklist.front());
 515   while (!Worklist.empty()) {
 516     NfaStateTy State = Worklist.front();
 517     Worklist.pop_front();
 518     for (unsigned i = 0; i < allInsnClasses.size(); i++) {
 519       const std::vector<unsigned> &InsnClass = allInsnClasses[i];
 520       if (!canApplyInsnClass(InsnClass, State))
 521         continue;
 522       for (unsigned NewState : applyInsnClass(InsnClass, State)) {
 523         if (SeenStates.emplace(NewState).second)
 524           Worklist.emplace_back(NewState);
 525         Emitter.addTransition(State, NewState, getDFAInsnInput(InsnClass));
 526       }
 527     }
 528   }
 529
 530   OS << "} // end namespace llvm\n\n";
 531   OS << "namespace {\n";
 532   std::string TargetAndDFAName = TargetName + DFAName;
 533   Emitter.emit(TargetAndDFAName, OS);
 534   OS << "} // end anonymous namespace\n\n";
 535
 536   std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
 537   OS << "namespace llvm {\n";
 538   OS << "DFAPacketizer *" << SubTargetClassName << "::"
 539      << "create" << DFAName
 540      << "DFAPacketizer(const InstrItineraryData *IID) const {\n"
 541      << "  static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName
 542      << "Transition>(" << TargetAndDFAName << "Transitions), "
 543      << TargetAndDFAName << "TransitionInfo);\n"
 544      << "  return new DFAPacketizer(IID, A);\n"
 545      << "\n}\n\n";
 546 }
 547
 548 namespace llvm {
 549
 550 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
 551   emitSourceFileHeader("Target DFA Packetizer Tables", OS);
 552   DFAPacketizerEmitter(RK).run(OS);
 553 }
 554
 555 } // end namespace llvm