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
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 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(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
93DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R)
94 : TargetName(std::string(CodeGenTarget(R).getName())), Records(R) {}
95
96int 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(x: 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(FieldName: "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
131int 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(FieldName: "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(FieldName: "TheComboFunc");
152 const std::vector<Record *> &FuncList =
153 FuncData->getValueAsListOfDefs(FieldName: "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
176ResourceVector
177DFAPacketizerEmitter::getResourcesForItinerary(Record *Itinerary) {
178 ResourceVector Resources;
179 assert(Itinerary);
180 for (Record *StageDef : Itinerary->getValueAsListOfDefs(FieldName: "Stages")) {
181 uint64_t StageResources = 0;
182 for (Record *Unit : StageDef->getValueAsListOfDefs(FieldName: "Units")) {
183 StageResources |= FUNameToBitsMap[std::string(Unit->getName())];
184 }
185 if (StageResources != 0)
186 Resources.push_back(Elt: StageResources);
187 }
188 return Resources;
189}
190
191void DFAPacketizerEmitter::createScheduleClasses(unsigned ItineraryIdx,
192 const RecVec &Itineraries) {
193 unsigned Idx = 0;
194 for (Record *Itinerary : Itineraries) {
195 if (!Itinerary) {
196 ScheduleClasses.push_back(x: {.ItineraryID: ItineraryIdx, .Idx: Idx++, .ResourcesIdx: 0, .Resources: ResourceVector{}});
197 continue;
198 }
199 ResourceVector Resources = getResourcesForItinerary(Itinerary);
200 ScheduleClasses.push_back(
201 x: {.ItineraryID: ItineraryIdx, .Idx: Idx++, .ResourcesIdx: UniqueResources.insert(Entry: Resources), .Resources: Resources});
202 }
203}
204
205//
206// Run the worklist algorithm to generate the DFA.
207//
208void DFAPacketizerEmitter::run(raw_ostream &OS) {
209 emitSourceFileHeader(Desc: "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(FieldName: "PacketizerNamespace");
222 ItinsByNamespace[std::string(NS)].push_back(x: &ProcModel);
223 }
224 }
225
226 for (auto &KV : ItinsByNamespace)
227 emitForItineraries(OS, ProcItinList&: KV.second, DFAName: KV.first);
228 OS << "} // end namespace llvm\n";
229}
230
231void 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(ComboFuncList: Records.getAllDerivedDefinitions(ClassName: "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(ItineraryIdx: Model->Index, Itineraries: 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(x: 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(x: 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(Entry: Resources);
327 for (uint64_t NewState : applyInsnClass(Resources, State)) {
328 if (SeenStates.emplace(args&: NewState).second)
329 Worklist.emplace_back(args&: NewState);
330 Emitter.addTransition(From: State, To: NewState, A: ResourcesID);
331 }
332 }
333 }
334
335 std::string TargetAndDFAName = TargetName + DFAName;
336 Emitter.emit(Name: 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
357static TableGen::Emitter::OptClass<DFAPacketizerEmitter>
358 X("gen-dfa-packetizer", "Generate DFA Packetizer for VLIW targets");
359