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 <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(
76 ArrayRef<const CodeGenProcModel *> ProcModels);
77
78 // Construct a map from a combo function unit bit to the bits of all included
79 // functional units.
80 int collectAllComboFuncs(ArrayRef<Record *> ComboFuncList);
81
82 ResourceVector getResourcesForItinerary(Record *Itinerary);
83 void createScheduleClasses(unsigned ItineraryIdx, const RecVec &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
DFAPacketizerEmitter(RecordKeeper & R)94 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R)
95 : TargetName(std::string(CodeGenTarget(R).getName())), Records(R) {}
96
collectAllFuncUnits(ArrayRef<const CodeGenProcModel * > ProcModels)97 int 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 std::set<Record *> ProcItinList;
105 for (const CodeGenProcModel *Model : ProcModels)
106 ProcItinList.insert(Model->ItinsDef);
107
108 int totalFUs = 0;
109 // Parse functional units for all the itineraries.
110 for (Record *Proc : ProcItinList) {
111 std::vector<Record *> FUs = Proc->getValueAsListOfDefs("FU");
112
113 LLVM_DEBUG(dbgs() << " FU:"
114 << " (" << FUs.size() << " FUs) " << Proc->getName());
115
116 // Convert macros to bits for each stage.
117 unsigned numFUs = FUs.size();
118 for (unsigned j = 0; j < numFUs; ++j) {
119 assert((j < DFA_MAX_RESOURCES) &&
120 "Exceeded maximum number of representable resources");
121 uint64_t FuncResources = 1ULL << j;
122 FUNameToBitsMap[std::string(FUs[j]->getName())] = FuncResources;
123 LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"
124 << Twine::utohexstr(FuncResources));
125 }
126 totalFUs += numFUs;
127 LLVM_DEBUG(dbgs() << "\n");
128 }
129 return totalFUs;
130 }
131
collectAllComboFuncs(ArrayRef<Record * > ComboFuncList)132 int DFAPacketizerEmitter::collectAllComboFuncs(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