1 //===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===//
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
7 //===----------------------------------------------------------------------===//
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.
15 //===----------------------------------------------------------------------===//
17 #define DEBUG_TYPE "dfa-emitter"
19 #include "CodeGenSchedule.h"
20 #include "CodeGenTarget.h"
21 #include "DFAEmitter.h"
22 #include "llvm/ADT/DenseSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/StringExtras.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include "llvm/TableGen/Record.h"
28 #include "llvm/TableGen/TableGenBackend.h"
34 #include <unordered_map>
39 // We use a uint64_t to represent a resource bitmask.
40 #define DFA_MAX_RESOURCES 64
43 using ResourceVector = SmallVector<uint64_t, 4>;
45 struct ScheduleClass {
46 /// The parent itinerary index (processor model ID).
49 /// Index within this itinerary of the schedule class.
52 /// The index within the uniqued set of required resources of Resources.
53 unsigned ResourcesIdx;
55 /// Conjunctive list of resource requirements:
56 /// {a|b, b|c} => (a OR b) AND (b or c).
57 /// Resources are unique across all itineraries.
58 ResourceVector Resources;
61 // Generates and prints out the DFA for resource tracking.
62 class DFAPacketizerEmitter {
64 std::string TargetName;
65 RecordKeeper &Records;
67 UniqueVector<ResourceVector> UniqueResources;
68 std::vector<ScheduleClass> ScheduleClasses;
69 std::map<std::string, uint64_t> FUNameToBitsMap;
70 std::map<unsigned, uint64_t> ComboBitToBitsMap;
73 DFAPacketizerEmitter(RecordKeeper &R);
75 // Construct a map of function unit names to bits.
76 int collectAllFuncUnits(
77 ArrayRef<const CodeGenProcModel *> ProcModels);
79 // Construct a map from a combo function unit bit to the bits of all included
81 int collectAllComboFuncs(ArrayRef<Record *> ComboFuncList);
83 ResourceVector getResourcesForItinerary(Record *Itinerary);
84 void createScheduleClasses(unsigned ItineraryIdx, const RecVec &Itineraries);
86 // Emit code for a subset of itineraries.
87 void emitForItineraries(raw_ostream &OS,
88 std::vector<const CodeGenProcModel *> &ProcItinList,
91 void run(raw_ostream &OS);
93 } // end anonymous namespace
95 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R)
96 : TargetName(CodeGenTarget(R).getName()), Records(R) {}
98 int DFAPacketizerEmitter::collectAllFuncUnits(
99 ArrayRef<const CodeGenProcModel *> ProcModels) {
100 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
101 "----------------------\n");
102 LLVM_DEBUG(dbgs() << "collectAllFuncUnits");
103 LLVM_DEBUG(dbgs() << " (" << ProcModels.size() << " itineraries)\n");
105 std::set<Record *> ProcItinList;
106 for (const CodeGenProcModel *Model : ProcModels)
107 ProcItinList.insert(Model->ItinsDef);
110 // Parse functional units for all the itineraries.
111 for (Record *Proc : ProcItinList) {
112 std::vector<Record *> FUs = Proc->getValueAsListOfDefs("FU");
114 LLVM_DEBUG(dbgs() << " FU:"
115 << " (" << FUs.size() << " FUs) " << Proc->getName());
117 // Convert macros to bits for each stage.
118 unsigned numFUs = FUs.size();
119 for (unsigned j = 0; j < numFUs; ++j) {
120 assert((j < DFA_MAX_RESOURCES) &&
121 "Exceeded maximum number of representable resources");
122 uint64_t FuncResources = 1ULL << j;
123 FUNameToBitsMap[FUs[j]->getName()] = FuncResources;
124 LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"
125 << Twine::utohexstr(FuncResources));
128 LLVM_DEBUG(dbgs() << "\n");
133 int DFAPacketizerEmitter::collectAllComboFuncs(ArrayRef<Record *> ComboFuncList) {
134 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
135 "----------------------\n");
136 LLVM_DEBUG(dbgs() << "collectAllComboFuncs");
137 LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");
140 for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
141 Record *Func = ComboFuncList[i];
142 std::vector<Record *> FUs = Func->getValueAsListOfDefs("CFD");
144 LLVM_DEBUG(dbgs() << " CFD:" << i << " (" << FUs.size() << " combo FUs) "
145 << Func->getName() << "\n");
147 // Convert macros to bits for each stage.
148 for (unsigned j = 0, N = FUs.size(); j < N; ++j) {
149 assert((j < DFA_MAX_RESOURCES) &&
150 "Exceeded maximum number of DFA resources");
151 Record *FuncData = FUs[j];
152 Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");
153 const std::vector<Record *> &FuncList =
154 FuncData->getValueAsListOfDefs("FuncList");
155 const std::string &ComboFuncName = ComboFunc->getName();
156 uint64_t ComboBit = FUNameToBitsMap[ComboFuncName];
157 uint64_t ComboResources = ComboBit;
158 LLVM_DEBUG(dbgs() << " combo: " << ComboFuncName << ":0x"
159 << Twine::utohexstr(ComboResources) << "\n");
160 for (unsigned k = 0, M = FuncList.size(); k < M; ++k) {
161 std::string FuncName = FuncList[k]->getName();
162 uint64_t FuncResources = FUNameToBitsMap[FuncName];
163 LLVM_DEBUG(dbgs() << " " << FuncName << ":0x"
164 << Twine::utohexstr(FuncResources) << "\n");
165 ComboResources |= FuncResources;
167 ComboBitToBitsMap[ComboBit] = ComboResources;
169 LLVM_DEBUG(dbgs() << " => combo bits: " << ComboFuncName << ":0x"
170 << Twine::utohexstr(ComboBit) << " = 0x"
171 << Twine::utohexstr(ComboResources) << "\n");
178 DFAPacketizerEmitter::getResourcesForItinerary(Record *Itinerary) {
179 ResourceVector Resources;
181 for (Record *StageDef : Itinerary->getValueAsListOfDefs("Stages")) {
182 uint64_t StageResources = 0;
183 for (Record *Unit : StageDef->getValueAsListOfDefs("Units")) {
184 StageResources |= FUNameToBitsMap[Unit->getName()];
186 if (StageResources != 0)
187 Resources.push_back(StageResources);
192 void DFAPacketizerEmitter::createScheduleClasses(unsigned ItineraryIdx,
193 const RecVec &Itineraries) {
195 for (Record *Itinerary : Itineraries) {
197 ScheduleClasses.push_back({ItineraryIdx, Idx++, 0, ResourceVector{}});
200 ResourceVector Resources = getResourcesForItinerary(Itinerary);
201 ScheduleClasses.push_back(
202 {ItineraryIdx, Idx++, UniqueResources.insert(Resources), Resources});
207 // Run the worklist algorithm to generate the DFA.
209 void DFAPacketizerEmitter::run(raw_ostream &OS) {
211 << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
212 OS << "namespace llvm {\n";
214 CodeGenTarget CGT(Records);
215 CodeGenSchedModels CGS(Records, CGT);
217 std::unordered_map<std::string, std::vector<const CodeGenProcModel *>>
219 for (const CodeGenProcModel &ProcModel : CGS.procModels()) {
220 if (ProcModel.hasItineraries()) {
221 auto NS = ProcModel.ItinsDef->getValueAsString("PacketizerNamespace");
222 ItinsByNamespace[NS].push_back(&ProcModel);
226 for (auto &KV : ItinsByNamespace)
227 emitForItineraries(OS, KV.second, KV.first);
228 OS << "} // end namespace llvm\n";
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"));
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);
247 // Output the mapping from ScheduleClass to ResourcesIdx.
249 OS << "unsigned " << TargetName << DFAName << "ResourceIndices[] = {";
250 for (const ScheduleClass &SC : ScheduleClasses) {
253 OS << SC.ResourcesIdx << ", ";
257 // And the mapping from Itinerary index into the previous table.
258 OS << "unsigned " << TargetName << DFAName
259 << "ProcResourceIndexStart[] = {\n";
260 OS << " 0, // NoSchedModel\n";
261 for (const CodeGenProcModel *Model : ProcModels) {
262 OS << " " << ProcModelStartIdx[Model] << ", // " << Model->ModelName
265 OS << ScheduleClasses.size() << "\n};\n\n";
267 // The type of a state in the nondeterministic automaton we're defining.
268 using NfaStateTy = uint64_t;
270 // Given a resource state, return all resource states by applying
272 auto applyInsnClass = [&](const ResourceVector &InsnClass,
273 NfaStateTy State) -> std::deque<NfaStateTy> {
274 std::deque<NfaStateTy> V(1, State);
275 // Apply every stage in the class individually.
276 for (NfaStateTy Stage : InsnClass) {
277 // Apply this stage to every existing member of V in turn.
278 size_t Sz = V.size();
279 for (unsigned I = 0; I < Sz; ++I) {
280 NfaStateTy S = V.front();
283 // For this stage, state combination, try all possible resources.
284 for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) {
285 NfaStateTy ResourceMask = 1ULL << J;
286 if ((ResourceMask & Stage) == 0)
287 // This resource isn't required by this stage.
289 NfaStateTy Combo = ComboBitToBitsMap[ResourceMask];
290 if (Combo && ((~S & Combo) != Combo))
291 // This combo units bits are not available.
293 NfaStateTy ResultingResourceState = S | ResourceMask | Combo;
294 if (ResultingResourceState == S)
296 V.push_back(ResultingResourceState);
303 // Given a resource state, return a quick (conservative) guess as to whether
304 // InsnClass can be applied. This is a filter for the more heavyweight
306 auto canApplyInsnClass = [](const ResourceVector &InsnClass,
307 NfaStateTy State) -> bool {
308 for (NfaStateTy Resources : InsnClass) {
309 if ((State | Resources) == State)
316 std::deque<NfaStateTy> Worklist(1, 0);
317 std::set<NfaStateTy> SeenStates;
318 SeenStates.insert(Worklist.front());
319 while (!Worklist.empty()) {
320 NfaStateTy State = Worklist.front();
321 Worklist.pop_front();
322 for (const ResourceVector &Resources : UniqueResources) {
323 if (!canApplyInsnClass(Resources, State))
325 unsigned ResourcesID = UniqueResources.idFor(Resources);
326 for (uint64_t NewState : applyInsnClass(Resources, State)) {
327 if (SeenStates.emplace(NewState).second)
328 Worklist.emplace_back(NewState);
329 Emitter.addTransition(State, NewState, ResourcesID);
334 std::string TargetAndDFAName = TargetName + DFAName;
335 Emitter.emit(TargetAndDFAName, OS);
336 OS << "} // end anonymous namespace\n\n";
338 std::string SubTargetClassName = TargetName + "GenSubtargetInfo";
339 OS << "namespace llvm {\n";
340 OS << "DFAPacketizer *" << SubTargetClassName << "::"
341 << "create" << DFAName
342 << "DFAPacketizer(const InstrItineraryData *IID) const {\n"
343 << " static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName
344 << "Transition>(" << TargetAndDFAName << "Transitions), "
345 << TargetAndDFAName << "TransitionInfo);\n"
346 << " unsigned ProcResIdxStart = " << TargetAndDFAName
347 << "ProcResourceIndexStart[IID->SchedModel.ProcID];\n"
348 << " unsigned ProcResIdxNum = " << TargetAndDFAName
349 << "ProcResourceIndexStart[IID->SchedModel.ProcID + 1] - "
351 << " return new DFAPacketizer(IID, A, {&" << TargetAndDFAName
352 << "ResourceIndices[ProcResIdxStart], ProcResIdxNum});\n"
358 void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
359 emitSourceFileHeader("Target DFA Packetizer Tables", OS);
360 DFAPacketizerEmitter(RK).run(OS);
363 } // end namespace llvm