llvm/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 #include "CodeGenSchedule.h"
  18 #include "CodeGenTarget.h"
  19 #include "DFAEmitter.h"
  20 #include "llvm/ADT/DenseSet.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/ADT/StringExtras.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/raw_ostream.h"
  25 #include "llvm/TableGen/Record.h"
  26 #include "llvm/TableGen/TableGenBackend.h"
  27 #include <cassert>
  28 #include <cstdint>
  29 #include <map>
  30 #include <set>
  31 #include <string>
  32 #include <unordered_map>
  33 #include <vector>
  34
  35 #define DEBUG_TYPE "dfa-emitter"
  36
  37 using namespace llvm;
  38
  39 // We use a uint64_t to represent a resource bitmask.
  40 #define DFA_MAX_RESOURCES 64
  41
  42 namespace {
  43 using ResourceVector = SmallVector<uint64_t, 4>;
  44
  45 struct ScheduleClass {
  46   /// The parent itinerary index (processor model ID).
  47   unsigned ItineraryID;
  48
  49   /// Index within this itinerary of the schedule class.
  50   unsigned Idx;
  51
  52   /// The index within the uniqued set of required resources of Resources.
  53   unsigned ResourcesIdx;
  54
  55   /// Conjunctive list of resource requirements:
  56   ///   {a|b, b|c} => (a OR b) AND (b or c).
  57   /// Resources are unique across all itineraries.
  58   ResourceVector Resources;
  59 };
  60
  61 // Generates and prints out the DFA for resource tracking.
  62 class DFAPacketizerEmitter {
  63 private:
  64   std::string TargetName;
  65   RecordKeeper &Records;
  66
  67   UniqueVector<ResourceVector> UniqueResources;
  68   std::vector<ScheduleClass> ScheduleClasses;
  69   std::map<std::string, uint64_t> FUNameToBitsMap;
  70   std::map<unsigned, uint64_t> ComboBitToBitsMap;
  71
  72 public:
  73   DFAPacketizerEmitter(RecordKeeper &R);
  74
  75   // Construct a map of function unit names to bits.
  76   int collectAllFuncUnits(
  77       ArrayRef<const CodeGenProcModel *> ProcModels);
  78
  79   // Construct a map from a combo function unit bit to the bits of all included
  80   // functional units.
  81   int collectAllComboFuncs(ArrayRef<Record *> ComboFuncList);
  82
  83   ResourceVector getResourcesForItinerary(Record *Itinerary);
  84   void createScheduleClasses(unsigned ItineraryIdx, const RecVec &Itineraries);
  85
  86   // Emit code for a subset of itineraries.
  87   void emitForItineraries(raw_ostream &OS,
  88                           std::vector<const CodeGenProcModel *> &ProcItinList,
  89                           std::string DFAName);
  90
  91   void run(raw_ostream &OS);
  92 };
  93 } // end anonymous namespace
  94
  95 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R)
  96     : TargetName(std::string(CodeGenTarget(R).getName())), Records(R) {}
  97
  98 int DFAPacketizerEmitter::collectAllFuncUnits(
  99     ArrayRef<const CodeGenProcModel *> ProcModels) {
 100   LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
 101                        "----------------------\n");
 102   LLVM_DEBUG(dbgs() << "collectAllFuncUnits");
 103   LLVM_DEBUG(dbgs() << " (" << ProcModels.size() << " itineraries)\n");
 104
 105   std::set<Record *> ProcItinList;
 106   for (const CodeGenProcModel *Model : ProcModels)
 107     ProcItinList.insert(Model->ItinsDef);
 108
 109   int totalFUs = 0;
 110   // Parse functional units for all the itineraries.
 111   for (Record *Proc : ProcItinList) {
 112     std::vector<Record *> FUs = Proc->getValueAsListOfDefs("FU");
 113
 114     LLVM_DEBUG(dbgs() << "    FU:"
 115                       << " (" << FUs.size() << " FUs) " << Proc->getName());
 116
 117     // Convert macros to bits for each stage.
 118     unsigned numFUs = FUs.size();
 119     for (unsigned j = 0; j < numFUs; ++j) {
 120       assert((j < DFA_MAX_RESOURCES) &&
 121              "Exceeded maximum number of representable resources");
 122       uint64_t FuncResources = 1ULL << j;
 123       FUNameToBitsMap[std::string(FUs[j]->getName())] = FuncResources;
 124       LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"
 125                         << Twine::utohexstr(FuncResources));
 126     }
 127     totalFUs += numFUs;
 128     LLVM_DEBUG(dbgs() << "\n");
 129   }
 130   return totalFUs;
 131 }
 132
 133 int DFAPacketizerEmitter::collectAllComboFuncs(ArrayRef<Record *> ComboFuncList) {
 134   LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
 135                        "----------------------\n");
 136   LLVM_DEBUG(dbgs() << "collectAllComboFuncs");
 137   LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");
 138
 139   int numCombos = 0;
 140   for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
 141     Record *Func = ComboFuncList[i];
 142     std::vector<Record *> FUs = Func->getValueAsListOfDefs("CFD");
 143
 144     LLVM_DEBUG(dbgs() << "    CFD:" << i << " (" << FUs.size() << " combo FUs) "
 145                       << Func->getName() << "\n");
 146
 147     // Convert macros to bits for each stage.
 148     for (unsigned j = 0, N = FUs.size(); j < N; ++j) {
 149       assert((j < DFA_MAX_RESOURCES) &&
 150              "Exceeded maximum number of DFA resources");
 151       Record *FuncData = FUs[j];
 152       Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");
 153       const std::vector<Record *> &FuncList =
 154           FuncData->getValueAsListOfDefs("FuncList");
 155       const std::string &ComboFuncName = std::string(ComboFunc->getName());
 156       uint64_t ComboBit = FUNameToBitsMap[ComboFuncName];
 157       uint64_t ComboResources = ComboBit;
 158       LLVM_DEBUG(dbgs() << "      combo: " << ComboFuncName << ":0x"
 159                         << Twine::utohexstr(ComboResources) << "\n");
 160       for (auto *K : FuncList) {
 161         std::string FuncName = std::string(K->getName());
 162         uint64_t FuncResources = FUNameToBitsMap[FuncName];
 163         LLVM_DEBUG(dbgs() << "        " << FuncName << ":0x"
 164                           << Twine::utohexstr(FuncResources) << "\n");
 165         ComboResources |= FuncResources;
 166       }
 167       ComboBitToBitsMap[ComboBit] = ComboResources;
 168       numCombos++;
 169       LLVM_DEBUG(dbgs() << "          => combo bits: " << ComboFuncName << ":0x"
 170                         << Twine::utohexstr(ComboBit) << " = 0x"
 171                         << Twine::utohexstr(ComboResources) << "\n");
 172     }
 173   }
 174   return numCombos;
 175 }
 176
 177 ResourceVector
 178 DFAPacketizerEmitter::getResourcesForItinerary(Record *Itinerary) {
 179   ResourceVector Resources;
 180   assert(Itinerary);
 181   for (Record *StageDef : Itinerary->getValueAsListOfDefs("Stages")) {
 182     uint64_t StageResources = 0;
 183     for (Record *Unit : StageDef->getValueAsListOfDefs("Units")) {
 184       StageResources |= FUNameToBitsMap[std::string(Unit->getName())];
 185     }
 186     if (StageResources != 0)
 187       Resources.push_back(StageResources);
 188   }
 189   return Resources;
 190 }
 191
 192 void DFAPacketizerEmitter::createScheduleClasses(unsigned ItineraryIdx,
 193                                                  const RecVec &Itineraries) {
 194   unsigned Idx = 0;
 195   for (Record *Itinerary : Itineraries) {
 196     if (!Itinerary) {
 197       ScheduleClasses.push_back({ItineraryIdx, Idx++, 0, ResourceVector{}});
 198       continue;
 199     }
 200     ResourceVector Resources = getResourcesForItinerary(Itinerary);
 201     ScheduleClasses.push_back(
 202         {ItineraryIdx, Idx++, UniqueResources.insert(Resources), Resources});
 203   }
 204 }
 205
 206 //
 207 // Run the worklist algorithm to generate the DFA.
 208 //
 209 void DFAPacketizerEmitter::run(raw_ostream &OS) {
 210   OS << "\n"
 211      << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
 212   OS << "namespace llvm {\n";
 213
 214   CodeGenTarget CGT(Records);
 215   CodeGenSchedModels CGS(Records, CGT);
 216
 217   std::unordered_map<std::string, std::vector<const CodeGenProcModel *>>
 218       ItinsByNamespace;
 219   for (const CodeGenProcModel &ProcModel : CGS.procModels()) {
 220     if (ProcModel.hasItineraries()) {
 221       auto NS = ProcModel.ItinsDef->getValueAsString("PacketizerNamespace");
 222       ItinsByNamespace[std::string(NS)].push_back(&ProcModel);
 223     }
 224   }
 225
 226   for (auto &KV : ItinsByNamespace)
 227     emitForItineraries(OS, KV.second, KV.first);
 228   OS << "} // end namespace llvm\n";
 229 }
 230
 231 void DFAPacketizerEmitter::emitForItineraries(
 232     raw_ostream &OS, std::vector<const CodeGenProcModel *> &ProcModels,
 233     std::string DFAName) {
 234   OS << "} // end namespace llvm\n\n";
 235   OS << "namespace {\n";
 236   collectAllFuncUnits(ProcModels);
 237   collectAllComboFuncs(Records.getAllDerivedDefinitions("ComboFuncUnits"));
 238
 239   // Collect the itineraries.
 240   DenseMap<const CodeGenProcModel *, unsigned> ProcModelStartIdx;
 241   for (const CodeGenProcModel *Model : ProcModels) {
 242     assert(Model->hasItineraries());
 243     ProcModelStartIdx[Model] = ScheduleClasses.size();
 244     createScheduleClasses(Model->Index, Model->ItinDefList);
 245   }
 246
 247   // Output the mapping from ScheduleClass to ResourcesIdx.
 248   unsigned Idx = 0;
 249   OS << "constexpr unsigned " << TargetName << DFAName
 250      << "ResourceIndices[] = {";
 251   for (const ScheduleClass &SC : ScheduleClasses) {
 252     if (Idx++ % 32 == 0)
 253       OS << "\n  ";
 254     OS << SC.ResourcesIdx << ", ";
 255   }
 256   OS << "\n};\n\n";
 257
 258   // And the mapping from Itinerary index into the previous table.
 259   OS << "constexpr unsigned " << TargetName << DFAName
 260      << "ProcResourceIndexStart[] = {\n";
 261   OS << "  0, // NoSchedModel\n";
 262   for (const CodeGenProcModel *Model : ProcModels) {
 263     OS << "  " << ProcModelStartIdx[Model] << ", // " << Model->ModelName
 264        << "\n";
 265   }
 266   OS << "  " << ScheduleClasses.size() << "\n};\n\n";
 267
 268   // The type of a state in the nondeterministic automaton we're defining.
 269   using NfaStateTy = uint64_t;
 270
 271   // Given a resource state, return all resource states by applying
 272   // InsnClass.
 273   auto applyInsnClass = [&](const ResourceVector &InsnClass,
 274                             NfaStateTy State) -> std::deque<NfaStateTy> {
 275     std::deque<NfaStateTy> V(1, State);
 276     // Apply every stage in the class individually.
 277     for (NfaStateTy Stage : InsnClass) {
 278       // Apply this stage to every existing member of V in turn.
 279       size_t Sz = V.size();
 280       for (unsigned I = 0; I < Sz; ++I) {
 281         NfaStateTy S = V.front();
 282         V.pop_front();
 283
 284         // For this stage, state combination, try all possible resources.
 285         for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) {
 286           NfaStateTy ResourceMask = 1ULL << J;
 287           if ((ResourceMask & Stage) == 0)
 288             // This resource isn't required by this stage.
 289             continue;
 290           NfaStateTy Combo = ComboBitToBitsMap[ResourceMask];
 291           if (Combo && ((~S & Combo) != Combo))
 292             // This combo units bits are not available.
 293             continue;
 294           NfaStateTy ResultingResourceState = S | ResourceMask | Combo;
 295           if (ResultingResourceState == S)
 296             continue;
 297           V.push_back(ResultingResourceState);
 298         }
 299       }
 300     }
 301     return V;
 302   };
 303
 304   // Given a resource state, return a quick (conservative) guess as to whether
 305   // InsnClass can be applied. This is a filter for the more heavyweight
 306   // applyInsnClass.
 307   auto canApplyInsnClass = [](const ResourceVector &InsnClass,
 308                               NfaStateTy State) -> bool {
 309     for (NfaStateTy Resources : InsnClass) {
 310       if ((State | Resources) == State)
 311         return false;
 312     }
 313     return true;
 314   };
 315
 316   DfaEmitter Emitter;
 317   std::deque<NfaStateTy> Worklist(1, 0);
 318   std::set<NfaStateTy> SeenStates;
 319   SeenStates.insert(Worklist.front());
 320   while (!Worklist.empty()) {
 321     NfaStateTy State = Worklist.front();
 322     Worklist.pop_front();
 323     for (const ResourceVector &Resources : UniqueResources) {
 324       if (!canApplyInsnClass(Resources, State))
 325         continue;
 326       unsigned ResourcesID = UniqueResources.idFor(Resources);
 327       for (uint64_t NewState : applyInsnClass(Resources, State)) {
 328         if (SeenStates.emplace(NewState).second)
 329           Worklist.emplace_back(NewState);
 330         Emitter.addTransition(State, NewState, ResourcesID);
 331       }
 332     }
 333   }
 334
 335   std::string TargetAndDFAName = TargetName + DFAName;
 336   Emitter.emit(TargetAndDFAName, OS);
 337   OS << "} // end anonymous namespace\n\n";
 338
 339   std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
 340   OS << "namespace llvm {\n";
 341   OS << "DFAPacketizer *" << SubTargetClassName << "::"
 342      << "create" << DFAName
 343      << "DFAPacketizer(const InstrItineraryData *IID) const {\n"
 344      << "  static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName
 345      << "Transition>(" << TargetAndDFAName << "Transitions), "
 346      << TargetAndDFAName << "TransitionInfo);\n"
 347      << "  unsigned ProcResIdxStart = " << TargetAndDFAName
 348      << "ProcResourceIndexStart[IID->SchedModel.ProcID];\n"
 349      << "  unsigned ProcResIdxNum = " << TargetAndDFAName
 350      << "ProcResourceIndexStart[IID->SchedModel.ProcID + 1] - "
 351         "ProcResIdxStart;\n"
 352      << "  return new DFAPacketizer(IID, A, {&" << TargetAndDFAName
 353      << "ResourceIndices[ProcResIdxStart], ProcResIdxNum});\n"
 354      << "\n}\n\n";
 355 }
 356
 357 namespace llvm {
 358
 359 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
 360   emitSourceFileHeader("Target DFA Packetizer Tables", OS);
 361   DFAPacketizerEmitter(RK).run(OS);
 362 }
 363
 364 } // end namespace llvm