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 "CodeGenSchedule.h"
20 #include "CodeGenTarget.h"
21 #include "DFAEmitter.h"
22 #include "llvm/ADT/DenseSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/StringExtras.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include "llvm/TableGen/Record.h"
28 #include "llvm/TableGen/TableGenBackend.h"
29 #include <cassert>
30 #include <cstdint>
31 #include <map>
32 #include <set>
33 #include <string>
34 #include <unordered_map>
35 #include <vector>
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(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[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 = 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 (unsigned k = 0, M = FuncList.size(); k < M; ++k) {
161         std::string FuncName = FuncList[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[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[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 << "unsigned " << TargetName << DFAName << "ResourceIndices[] = {";
250   for (const ScheduleClass &SC : ScheduleClasses) {
251     if (Idx++ % 32 == 0)
252       OS << "\n  ";
253     OS << SC.ResourcesIdx << ", ";
254   }
255   OS << "\n};\n\n";
256 
257   // And the mapping from Itinerary index into the previous table.
258   OS << "unsigned " << TargetName << DFAName
259      << "ProcResourceIndexStart[] = {\n";
260   OS << "  0, // NoSchedModel\n";
261   for (const CodeGenProcModel *Model : ProcModels) {
262     OS << "  " << ProcModelStartIdx[Model] << ", // " << Model->ModelName
263        << "\n";
264   }
265   OS << ScheduleClasses.size() << "\n};\n\n";
266 
267   // The type of a state in the nondeterministic automaton we're defining.
268   using NfaStateTy = uint64_t;
269 
270   // Given a resource state, return all resource states by applying
271   // InsnClass.
272   auto applyInsnClass = [&](const ResourceVector &InsnClass,
273                             NfaStateTy State) -> std::deque<NfaStateTy> {
274     std::deque<NfaStateTy> V(1, State);
275     // Apply every stage in the class individually.
276     for (NfaStateTy Stage : InsnClass) {
277       // Apply this stage to every existing member of V in turn.
278       size_t Sz = V.size();
279       for (unsigned I = 0; I < Sz; ++I) {
280         NfaStateTy S = V.front();
281         V.pop_front();
282 
283         // For this stage, state combination, try all possible resources.
284         for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) {
285           NfaStateTy ResourceMask = 1ULL << J;
286           if ((ResourceMask & Stage) == 0)
287             // This resource isn't required by this stage.
288             continue;
289           NfaStateTy Combo = ComboBitToBitsMap[ResourceMask];
290           if (Combo && ((~S & Combo) != Combo))
291             // This combo units bits are not available.
292             continue;
293           NfaStateTy ResultingResourceState = S | ResourceMask | Combo;
294           if (ResultingResourceState == S)
295             continue;
296           V.push_back(ResultingResourceState);
297         }
298       }
299     }
300     return V;
301   };
302 
303   // Given a resource state, return a quick (conservative) guess as to whether
304   // InsnClass can be applied. This is a filter for the more heavyweight
305   // applyInsnClass.
306   auto canApplyInsnClass = [](const ResourceVector &InsnClass,
307                               NfaStateTy State) -> bool {
308     for (NfaStateTy Resources : InsnClass) {
309       if ((State | Resources) == State)
310         return false;
311     }
312     return true;
313   };
314 
315   DfaEmitter Emitter;
316   std::deque<NfaStateTy> Worklist(1, 0);
317   std::set<NfaStateTy> SeenStates;
318   SeenStates.insert(Worklist.front());
319   while (!Worklist.empty()) {
320     NfaStateTy State = Worklist.front();
321     Worklist.pop_front();
322     for (const ResourceVector &Resources : UniqueResources) {
323       if (!canApplyInsnClass(Resources, State))
324         continue;
325       unsigned ResourcesID = UniqueResources.idFor(Resources);
326       for (uint64_t NewState : applyInsnClass(Resources, State)) {
327         if (SeenStates.emplace(NewState).second)
328           Worklist.emplace_back(NewState);
329         Emitter.addTransition(State, NewState, ResourcesID);
330       }
331     }
332   }
333 
334   std::string TargetAndDFAName = TargetName + DFAName;
335   Emitter.emit(TargetAndDFAName, OS);
336   OS << "} // end anonymous namespace\n\n";
337 
338   std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
339   OS << "namespace llvm {\n";
340   OS << "DFAPacketizer *" << SubTargetClassName << "::"
341      << "create" << DFAName
342      << "DFAPacketizer(const InstrItineraryData *IID) const {\n"
343      << "  static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName
344      << "Transition>(" << TargetAndDFAName << "Transitions), "
345      << TargetAndDFAName << "TransitionInfo);\n"
346      << "  unsigned ProcResIdxStart = " << TargetAndDFAName
347      << "ProcResourceIndexStart[IID->SchedModel.ProcID];\n"
348      << "  unsigned ProcResIdxNum = " << TargetAndDFAName
349      << "ProcResourceIndexStart[IID->SchedModel.ProcID + 1] - "
350         "ProcResIdxStart;\n"
351      << "  return new DFAPacketizer(IID, A, {&" << TargetAndDFAName
352      << "ResourceIndices[ProcResIdxStart], ProcResIdxNum});\n"
353      << "\n}\n\n";
354 }
355 
356 namespace llvm {
357 
358 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
359   emitSourceFileHeader("Target DFA Packetizer Tables", OS);
360   DFAPacketizerEmitter(RK).run(OS);
361 }
362 
363 } // end namespace llvm
364