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