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
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(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
getResourcesForItinerary(Record * Itinerary)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
createScheduleClasses(unsigned ItineraryIdx,const RecVec & Itineraries)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 //
run(raw_ostream & OS)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
emitForItineraries(raw_ostream & OS,std::vector<const CodeGenProcModel * > & ProcModels,std::string DFAName)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
EmitDFAPacketizer(RecordKeeper & RK,raw_ostream & OS)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