xref: /freebsd/contrib/llvm-project/llvm/utils/TableGen/DFAPacketizerEmitter.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
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 "Common/CodeGenSchedule.h"
18 #include "Common/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 <deque>
28 #include <map>
29 #include <set>
30 #include <string>
31 #include <unordered_map>
32 #include <vector>
33 
34 #define DEBUG_TYPE "dfa-emitter"
35 
36 using namespace llvm;
37 
38 // We use a uint64_t to represent a resource bitmask.
39 #define DFA_MAX_RESOURCES 64
40 
41 namespace {
42 using ResourceVector = SmallVector<uint64_t, 4>;
43 
44 struct ScheduleClass {
45   /// The parent itinerary index (processor model ID).
46   unsigned ItineraryID;
47 
48   /// Index within this itinerary of the schedule class.
49   unsigned Idx;
50 
51   /// The index within the uniqued set of required resources of Resources.
52   unsigned ResourcesIdx;
53 
54   /// Conjunctive list of resource requirements:
55   ///   {a|b, b|c} => (a OR b) AND (b or c).
56   /// Resources are unique across all itineraries.
57   ResourceVector Resources;
58 };
59 
60 // Generates and prints out the DFA for resource tracking.
61 class DFAPacketizerEmitter {
62 private:
63   std::string TargetName;
64   RecordKeeper &Records;
65 
66   UniqueVector<ResourceVector> UniqueResources;
67   std::vector<ScheduleClass> ScheduleClasses;
68   std::map<std::string, uint64_t> FUNameToBitsMap;
69   std::map<unsigned, uint64_t> ComboBitToBitsMap;
70 
71 public:
72   DFAPacketizerEmitter(RecordKeeper &R);
73 
74   // Construct a map of function unit names to bits.
75   int collectAllFuncUnits(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 
DFAPacketizerEmitter(RecordKeeper & R)93 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R)
94     : TargetName(std::string(CodeGenTarget(R).getName())), Records(R) {}
95 
collectAllFuncUnits(ArrayRef<const CodeGenProcModel * > ProcModels)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 
collectAllComboFuncs(ArrayRef<Record * > ComboFuncList)131 int DFAPacketizerEmitter::collectAllComboFuncs(
132     ArrayRef<Record *> ComboFuncList) {
133   LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
134                        "----------------------\n");
135   LLVM_DEBUG(dbgs() << "collectAllComboFuncs");
136   LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");
137 
138   int numCombos = 0;
139   for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
140     Record *Func = ComboFuncList[i];
141     std::vector<Record *> FUs = Func->getValueAsListOfDefs("CFD");
142 
143     LLVM_DEBUG(dbgs() << "    CFD:" << i << " (" << FUs.size() << " combo FUs) "
144                       << Func->getName() << "\n");
145 
146     // Convert macros to bits for each stage.
147     for (unsigned j = 0, N = FUs.size(); j < N; ++j) {
148       assert((j < DFA_MAX_RESOURCES) &&
149              "Exceeded maximum number of DFA resources");
150       Record *FuncData = FUs[j];
151       Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");
152       const std::vector<Record *> &FuncList =
153           FuncData->getValueAsListOfDefs("FuncList");
154       const std::string &ComboFuncName = std::string(ComboFunc->getName());
155       uint64_t ComboBit = FUNameToBitsMap[ComboFuncName];
156       uint64_t ComboResources = ComboBit;
157       LLVM_DEBUG(dbgs() << "      combo: " << ComboFuncName << ":0x"
158                         << Twine::utohexstr(ComboResources) << "\n");
159       for (auto *K : FuncList) {
160         std::string FuncName = std::string(K->getName());
161         uint64_t FuncResources = FUNameToBitsMap[FuncName];
162         LLVM_DEBUG(dbgs() << "        " << FuncName << ":0x"
163                           << Twine::utohexstr(FuncResources) << "\n");
164         ComboResources |= FuncResources;
165       }
166       ComboBitToBitsMap[ComboBit] = ComboResources;
167       numCombos++;
168       LLVM_DEBUG(dbgs() << "          => combo bits: " << ComboFuncName << ":0x"
169                         << Twine::utohexstr(ComboBit) << " = 0x"
170                         << Twine::utohexstr(ComboResources) << "\n");
171     }
172   }
173   return numCombos;
174 }
175 
176 ResourceVector
getResourcesForItinerary(Record * Itinerary)177 DFAPacketizerEmitter::getResourcesForItinerary(Record *Itinerary) {
178   ResourceVector Resources;
179   assert(Itinerary);
180   for (Record *StageDef : Itinerary->getValueAsListOfDefs("Stages")) {
181     uint64_t StageResources = 0;
182     for (Record *Unit : StageDef->getValueAsListOfDefs("Units")) {
183       StageResources |= FUNameToBitsMap[std::string(Unit->getName())];
184     }
185     if (StageResources != 0)
186       Resources.push_back(StageResources);
187   }
188   return Resources;
189 }
190 
createScheduleClasses(unsigned ItineraryIdx,const RecVec & Itineraries)191 void DFAPacketizerEmitter::createScheduleClasses(unsigned ItineraryIdx,
192                                                  const RecVec &Itineraries) {
193   unsigned Idx = 0;
194   for (Record *Itinerary : Itineraries) {
195     if (!Itinerary) {
196       ScheduleClasses.push_back({ItineraryIdx, Idx++, 0, ResourceVector{}});
197       continue;
198     }
199     ResourceVector Resources = getResourcesForItinerary(Itinerary);
200     ScheduleClasses.push_back(
201         {ItineraryIdx, Idx++, UniqueResources.insert(Resources), Resources});
202   }
203 }
204 
205 //
206 // Run the worklist algorithm to generate the DFA.
207 //
run(raw_ostream & OS)208 void DFAPacketizerEmitter::run(raw_ostream &OS) {
209   emitSourceFileHeader("Target DFA Packetizer Tables", 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 
emitForItineraries(raw_ostream & OS,std::vector<const CodeGenProcModel * > & ProcModels,std::string DFAName)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 static TableGen::Emitter::OptClass<DFAPacketizerEmitter>
358     X("gen-dfa-packetizer", "Generate DFA Packetizer for VLIW targets");
359