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