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 "CodeGenTarget.h"
20 #include "DFAEmitter.h"
21 #include "llvm/ADT/DenseSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/StringExtras.h"
24 #include "llvm/TableGen/Record.h"
25 #include "llvm/TableGen/TableGenBackend.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
33 #include <unordered_map>
38 // --------------------------------------------------------------------
39 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
41 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
42 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
44 // e.g. terms x resource bit combinations that fit in uint32_t:
45 // 4 terms x 8 bits = 32 bits
46 // 3 terms x 10 bits = 30 bits
47 // 2 terms x 16 bits = 32 bits
49 // e.g. terms x resource bit combinations that fit in uint64_t:
50 // 8 terms x 8 bits = 64 bits
51 // 7 terms x 9 bits = 63 bits
52 // 6 terms x 10 bits = 60 bits
53 // 5 terms x 12 bits = 60 bits
54 // 4 terms x 16 bits = 64 bits <--- current
55 // 3 terms x 21 bits = 63 bits
56 // 2 terms x 32 bits = 64 bits
58 #define DFA_MAX_RESTERMS 4 // The max # of AND'ed resource terms.
59 #define DFA_MAX_RESOURCES 16 // The max # of resource bits in one term.
61 typedef uint64_t DFAInput
;
62 typedef int64_t DFAStateInput
;
63 #define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable.
67 DFAInput
addDFAFuncUnits(DFAInput Inp
, unsigned FuncUnits
) {
68 return (Inp
<< DFA_MAX_RESOURCES
) | FuncUnits
;
71 /// Return the DFAInput for an instruction class input vector.
72 /// This function is used in both DFAPacketizer.cpp and in
73 /// DFAPacketizerEmitter.cpp.
74 DFAInput
getDFAInsnInput(const std::vector
<unsigned> &InsnClass
) {
75 DFAInput InsnInput
= 0;
76 assert((InsnClass
.size() <= DFA_MAX_RESTERMS
) &&
77 "Exceeded maximum number of DFA terms");
78 for (auto U
: InsnClass
)
79 InsnInput
= addDFAFuncUnits(InsnInput
, U
);
83 } // end anonymous namespace
85 // --------------------------------------------------------------------
88 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
90 // dbgsInsnClass - When debugging, print instruction class stages.
92 void dbgsInsnClass(const std::vector
<unsigned> &InsnClass
);
94 // dbgsStateInfo - When debugging, print the set of state info.
96 void dbgsStateInfo(const std::set
<unsigned> &stateInfo
);
98 // dbgsIndent - When debugging, indent by the specified amount.
100 void dbgsIndent(unsigned indent
);
104 // class DFAPacketizerEmitter: class that generates and prints out the DFA
105 // for resource tracking.
109 class DFAPacketizerEmitter
{
111 std::string TargetName
;
113 // allInsnClasses is the set of all possible resources consumed by an
116 std::vector
<std::vector
<unsigned>> allInsnClasses
;
117 RecordKeeper
&Records
;
120 DFAPacketizerEmitter(RecordKeeper
&R
);
123 // collectAllFuncUnits - Construct a map of function unit names to bits.
125 int collectAllFuncUnits(std::vector
<Record
*> &ProcItinList
,
126 std::map
<std::string
, unsigned> &FUNameToBitsMap
,
131 // collectAllComboFuncs - Construct a map from a combo function unit bit to
132 // the bits of all included functional units.
134 int collectAllComboFuncs(std::vector
<Record
*> &ComboFuncList
,
135 std::map
<std::string
, unsigned> &FUNameToBitsMap
,
136 std::map
<unsigned, unsigned> &ComboBitToBitsMap
,
140 // collectOneInsnClass - Populate allInsnClasses with one instruction class.
142 int collectOneInsnClass(const std::string
&ProcName
,
143 std::vector
<Record
*> &ProcItinList
,
144 std::map
<std::string
, unsigned> &FUNameToBitsMap
,
149 // collectAllInsnClasses - Populate allInsnClasses which is a set of units
150 // used in each stage.
152 int collectAllInsnClasses(const std::string
&ProcName
,
153 std::vector
<Record
*> &ProcItinList
,
154 std::map
<std::string
, unsigned> &FUNameToBitsMap
,
155 std::vector
<Record
*> &ItinDataList
,
159 // Emit code for a subset of itineraries.
160 void emitForItineraries(raw_ostream
&OS
,
161 std::vector
<Record
*> &ProcItinList
,
162 std::string DFAName
);
164 void run(raw_ostream
&OS
);
166 } // end anonymous namespace
169 // To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
171 // dbgsInsnClass - When debugging, print instruction class stages.
173 void dbgsInsnClass(const std::vector
<unsigned> &InsnClass
) {
174 LLVM_DEBUG(dbgs() << "InsnClass: ");
175 for (unsigned i
= 0; i
< InsnClass
.size(); ++i
) {
177 LLVM_DEBUG(dbgs() << ", ");
179 LLVM_DEBUG(dbgs() << "0x" << Twine::utohexstr(InsnClass
[i
]));
181 DFAInput InsnInput
= getDFAInsnInput(InsnClass
);
182 LLVM_DEBUG(dbgs() << " (input: 0x" << Twine::utohexstr(InsnInput
) << ")");
186 // dbgsIndent - When debugging, indent by the specified amount.
188 void dbgsIndent(unsigned indent
) {
189 for (unsigned i
= 0; i
< indent
; ++i
) {
190 LLVM_DEBUG(dbgs() << " ");
195 DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper
&R
):
196 TargetName(CodeGenTarget(R
).getName()), Records(R
) {}
199 // collectAllFuncUnits - Construct a map of function unit names to bits.
201 int DFAPacketizerEmitter::collectAllFuncUnits(
202 std::vector
<Record
*> &ProcItinList
,
203 std::map
<std::string
, unsigned> &FUNameToBitsMap
,
206 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
207 "----------------------\n");
208 LLVM_DEBUG(dbgs() << "collectAllFuncUnits");
209 LLVM_DEBUG(dbgs() << " (" << ProcItinList
.size() << " itineraries)\n");
212 // Parse functional units for all the itineraries.
213 for (unsigned i
= 0, N
= ProcItinList
.size(); i
< N
; ++i
) {
214 Record
*Proc
= ProcItinList
[i
];
215 std::vector
<Record
*> FUs
= Proc
->getValueAsListOfDefs("FU");
217 LLVM_DEBUG(dbgs() << " FU:" << i
<< " (" << FUs
.size() << " FUs) "
220 // Convert macros to bits for each stage.
221 unsigned numFUs
= FUs
.size();
222 for (unsigned j
= 0; j
< numFUs
; ++j
) {
223 assert ((j
< DFA_MAX_RESOURCES
) &&
224 "Exceeded maximum number of representable resources");
225 unsigned FuncResources
= (unsigned) (1U << j
);
226 FUNameToBitsMap
[FUs
[j
]->getName()] = FuncResources
;
227 LLVM_DEBUG(dbgs() << " " << FUs
[j
]->getName() << ":0x"
228 << Twine::utohexstr(FuncResources
));
230 if (((int) numFUs
) > maxFUs
) {
234 LLVM_DEBUG(dbgs() << "\n");
240 // collectAllComboFuncs - Construct a map from a combo function unit bit to
241 // the bits of all included functional units.
243 int DFAPacketizerEmitter::collectAllComboFuncs(
244 std::vector
<Record
*> &ComboFuncList
,
245 std::map
<std::string
, unsigned> &FUNameToBitsMap
,
246 std::map
<unsigned, unsigned> &ComboBitToBitsMap
,
248 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
249 "----------------------\n");
250 LLVM_DEBUG(dbgs() << "collectAllComboFuncs");
251 LLVM_DEBUG(dbgs() << " (" << ComboFuncList
.size() << " sets)\n");
254 for (unsigned i
= 0, N
= ComboFuncList
.size(); i
< N
; ++i
) {
255 Record
*Func
= ComboFuncList
[i
];
256 std::vector
<Record
*> FUs
= Func
->getValueAsListOfDefs("CFD");
258 LLVM_DEBUG(dbgs() << " CFD:" << i
<< " (" << FUs
.size() << " combo FUs) "
259 << Func
->getName() << "\n");
261 // Convert macros to bits for each stage.
262 for (unsigned j
= 0, N
= FUs
.size(); j
< N
; ++j
) {
263 assert ((j
< DFA_MAX_RESOURCES
) &&
264 "Exceeded maximum number of DFA resources");
265 Record
*FuncData
= FUs
[j
];
266 Record
*ComboFunc
= FuncData
->getValueAsDef("TheComboFunc");
267 const std::vector
<Record
*> &FuncList
=
268 FuncData
->getValueAsListOfDefs("FuncList");
269 const std::string
&ComboFuncName
= ComboFunc
->getName();
270 unsigned ComboBit
= FUNameToBitsMap
[ComboFuncName
];
271 unsigned ComboResources
= ComboBit
;
272 LLVM_DEBUG(dbgs() << " combo: " << ComboFuncName
<< ":0x"
273 << Twine::utohexstr(ComboResources
) << "\n");
274 for (unsigned k
= 0, M
= FuncList
.size(); k
< M
; ++k
) {
275 std::string FuncName
= FuncList
[k
]->getName();
276 unsigned FuncResources
= FUNameToBitsMap
[FuncName
];
277 LLVM_DEBUG(dbgs() << " " << FuncName
<< ":0x"
278 << Twine::utohexstr(FuncResources
) << "\n");
279 ComboResources
|= FuncResources
;
281 ComboBitToBitsMap
[ComboBit
] = ComboResources
;
283 LLVM_DEBUG(dbgs() << " => combo bits: " << ComboFuncName
<< ":0x"
284 << Twine::utohexstr(ComboBit
) << " = 0x"
285 << Twine::utohexstr(ComboResources
) << "\n");
292 // collectOneInsnClass - Populate allInsnClasses with one instruction class
294 int DFAPacketizerEmitter::collectOneInsnClass(const std::string
&ProcName
,
295 std::vector
<Record
*> &ProcItinList
,
296 std::map
<std::string
, unsigned> &FUNameToBitsMap
,
299 const std::vector
<Record
*> &StageList
=
300 ItinData
->getValueAsListOfDefs("Stages");
302 // The number of stages.
303 unsigned NStages
= StageList
.size();
305 LLVM_DEBUG(dbgs() << " " << ItinData
->getValueAsDef("TheClass")->getName()
308 std::vector
<unsigned> UnitBits
;
310 // Compute the bitwise or of each unit used in this stage.
311 for (unsigned i
= 0; i
< NStages
; ++i
) {
312 const Record
*Stage
= StageList
[i
];
315 const std::vector
<Record
*> &UnitList
=
316 Stage
->getValueAsListOfDefs("Units");
318 LLVM_DEBUG(dbgs() << " stage:" << i
<< " [" << UnitList
.size()
320 unsigned dbglen
= 26; // cursor after stage dbgs
322 // Compute the bitwise or of each unit used in this stage.
323 unsigned UnitBitValue
= 0;
324 for (unsigned j
= 0, M
= UnitList
.size(); j
< M
; ++j
) {
325 // Conduct bitwise or.
326 std::string UnitName
= UnitList
[j
]->getName();
327 LLVM_DEBUG(dbgs() << " " << j
<< ":" << UnitName
);
328 dbglen
+= 3 + UnitName
.length();
329 assert(FUNameToBitsMap
.count(UnitName
));
330 UnitBitValue
|= FUNameToBitsMap
[UnitName
];
333 if (UnitBitValue
!= 0)
334 UnitBits
.push_back(UnitBitValue
);
336 while (dbglen
<= 64) { // line up bits dbgs
338 LLVM_DEBUG(dbgs() << "\t");
340 LLVM_DEBUG(dbgs() << " (bits: 0x" << Twine::utohexstr(UnitBitValue
)
344 if (!UnitBits
.empty())
345 allInsnClasses
.push_back(UnitBits
);
349 dbgsInsnClass(UnitBits
);
357 // collectAllInsnClasses - Populate allInsnClasses which is a set of units
358 // used in each stage.
360 int DFAPacketizerEmitter::collectAllInsnClasses(const std::string
&ProcName
,
361 std::vector
<Record
*> &ProcItinList
,
362 std::map
<std::string
, unsigned> &FUNameToBitsMap
,
363 std::vector
<Record
*> &ItinDataList
,
366 // Collect all instruction classes.
367 unsigned M
= ItinDataList
.size();
369 int numInsnClasses
= 0;
370 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
371 "----------------------\n"
372 << "collectAllInsnClasses " << ProcName
<< " (" << M
375 // Collect stages for each instruction class for all itinerary data
376 for (unsigned j
= 0; j
< M
; j
++) {
377 Record
*ItinData
= ItinDataList
[j
];
378 int NStages
= collectOneInsnClass(ProcName
, ProcItinList
,
379 FUNameToBitsMap
, ItinData
, OS
);
380 if (NStages
> maxStages
) {
385 return numInsnClasses
;
389 // Run the worklist algorithm to generate the DFA.
391 void DFAPacketizerEmitter::run(raw_ostream
&OS
) {
393 << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
394 OS
<< "namespace llvm {\n";
396 OS
<< "\n// Input format:\n";
397 OS
<< "#define DFA_MAX_RESTERMS " << DFA_MAX_RESTERMS
398 << "\t// maximum AND'ed resource terms\n";
399 OS
<< "#define DFA_MAX_RESOURCES " << DFA_MAX_RESOURCES
400 << "\t// maximum resource bits in one term\n";
402 // Collect processor iteraries.
403 std::vector
<Record
*> ProcItinList
=
404 Records
.getAllDerivedDefinitions("ProcessorItineraries");
406 std::unordered_map
<std::string
, std::vector
<Record
*>> ItinsByNamespace
;
407 for (Record
*R
: ProcItinList
)
408 ItinsByNamespace
[R
->getValueAsString("PacketizerNamespace")].push_back(R
);
410 for (auto &KV
: ItinsByNamespace
)
411 emitForItineraries(OS
, KV
.second
, KV
.first
);
412 OS
<< "} // end namespace llvm\n";
415 void DFAPacketizerEmitter::emitForItineraries(
416 raw_ostream
&OS
, std::vector
<Record
*> &ProcItinList
,
417 std::string DFAName
) {
419 // Collect the Functional units.
421 std::map
<std::string
, unsigned> FUNameToBitsMap
;
422 int maxResources
= 0;
423 collectAllFuncUnits(ProcItinList
,
424 FUNameToBitsMap
, maxResources
, OS
);
427 // Collect the Combo Functional units.
429 std::map
<unsigned, unsigned> ComboBitToBitsMap
;
430 std::vector
<Record
*> ComboFuncList
=
431 Records
.getAllDerivedDefinitions("ComboFuncUnits");
432 collectAllComboFuncs(ComboFuncList
, FUNameToBitsMap
, ComboBitToBitsMap
, OS
);
435 // Collect the itineraries.
438 int numInsnClasses
= 0;
439 for (unsigned i
= 0, N
= ProcItinList
.size(); i
< N
; i
++) {
440 Record
*Proc
= ProcItinList
[i
];
442 // Get processor itinerary name.
443 const std::string
&ProcName
= Proc
->getName();
446 if (ProcName
== "NoItineraries")
449 // Sanity check for at least one instruction itinerary class.
450 unsigned NItinClasses
=
451 Records
.getAllDerivedDefinitions("InstrItinClass").size();
452 if (NItinClasses
== 0)
455 // Get itinerary data list.
456 std::vector
<Record
*> ItinDataList
= Proc
->getValueAsListOfDefs("IID");
458 // Collect all instruction classes
459 numInsnClasses
+= collectAllInsnClasses(ProcName
, ProcItinList
,
460 FUNameToBitsMap
, ItinDataList
, maxStages
, OS
);
463 // The type of a state in the nondeterministic automaton we're defining.
464 using NfaStateTy
= unsigned;
466 // Given a resource state, return all resource states by applying
468 auto applyInsnClass
= [&](ArrayRef
<unsigned> InsnClass
,
469 NfaStateTy State
) -> std::deque
<unsigned> {
470 std::deque
<unsigned> V(1, State
);
471 // Apply every stage in the class individually.
472 for (unsigned Stage
: InsnClass
) {
473 // Apply this stage to every existing member of V in turn.
474 size_t Sz
= V
.size();
475 for (unsigned I
= 0; I
< Sz
; ++I
) {
476 unsigned S
= V
.front();
479 // For this stage, state combination, try all possible resources.
480 for (unsigned J
= 0; J
< DFA_MAX_RESOURCES
; ++J
) {
481 unsigned ResourceMask
= 1U << J
;
482 if ((ResourceMask
& Stage
) == 0)
483 // This resource isn't required by this stage.
485 unsigned Combo
= ComboBitToBitsMap
[ResourceMask
];
486 if (Combo
&& ((~S
& Combo
) != Combo
))
487 // This combo units bits are not available.
489 unsigned ResultingResourceState
= S
| ResourceMask
| Combo
;
490 if (ResultingResourceState
== S
)
492 V
.push_back(ResultingResourceState
);
499 // Given a resource state, return a quick (conservative) guess as to whether
500 // InsnClass can be applied. This is a filter for the more heavyweight
502 auto canApplyInsnClass
= [](ArrayRef
<unsigned> InsnClass
,
503 NfaStateTy State
) -> bool {
504 for (unsigned Resources
: InsnClass
) {
505 if ((State
| Resources
) == State
)
512 std::deque
<NfaStateTy
> Worklist(1, 0);
513 std::set
<NfaStateTy
> SeenStates
;
514 SeenStates
.insert(Worklist
.front());
515 while (!Worklist
.empty()) {
516 NfaStateTy State
= Worklist
.front();
517 Worklist
.pop_front();
518 for (unsigned i
= 0; i
< allInsnClasses
.size(); i
++) {
519 const std::vector
<unsigned> &InsnClass
= allInsnClasses
[i
];
520 if (!canApplyInsnClass(InsnClass
, State
))
522 for (unsigned NewState
: applyInsnClass(InsnClass
, State
)) {
523 if (SeenStates
.emplace(NewState
).second
)
524 Worklist
.emplace_back(NewState
);
525 Emitter
.addTransition(State
, NewState
, getDFAInsnInput(InsnClass
));
530 OS
<< "} // end namespace llvm\n\n";
531 OS
<< "namespace {\n";
532 std::string TargetAndDFAName
= TargetName
+ DFAName
;
533 Emitter
.emit(TargetAndDFAName
, OS
);
534 OS
<< "} // end anonymous namespace\n\n";
536 std::string SubTargetClassName
= TargetName
+ "GenSubtargetInfo";
537 OS
<< "namespace llvm {\n";
538 OS
<< "DFAPacketizer *" << SubTargetClassName
<< "::"
539 << "create" << DFAName
540 << "DFAPacketizer(const InstrItineraryData *IID) const {\n"
541 << " static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName
542 << "Transition>(" << TargetAndDFAName
<< "Transitions), "
543 << TargetAndDFAName
<< "TransitionInfo);\n"
544 << " return new DFAPacketizer(IID, A);\n"
550 void EmitDFAPacketizer(RecordKeeper
&RK
, raw_ostream
&OS
) {
551 emitSourceFileHeader("Target DFA Packetizer Tables", OS
);
552 DFAPacketizerEmitter(RK
).run(OS
);
555 } // end namespace llvm