blob: 0d3c6fdc933c41e9f87b32fd02461610a1fc51be [file] [log] [blame]
Eugene Zelenko6ac3f732016-01-26 18:48:36 +00001//===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine ----===//
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +00002//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +00006//
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
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +000017#define DEBUG_TYPE "dfa-emitter"
18
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +000019#include "CodeGenTarget.h"
James Molloy12092a92019-10-17 08:34:29 +000020#include "DFAEmitter.h"
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +000021#include "llvm/ADT/DenseSet.h"
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +000022#include "llvm/ADT/SmallVector.h"
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +000023#include "llvm/ADT/StringExtras.h"
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +000024#include "llvm/TableGen/Record.h"
25#include "llvm/TableGen/TableGenBackend.h"
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +000026#include "llvm/Support/Debug.h"
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +000027#include "llvm/Support/raw_ostream.h"
28#include <cassert>
29#include <cstdint>
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +000030#include <map>
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +000031#include <set>
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +000032#include <string>
James Molloy6ccd6732019-08-30 19:50:49 +000033#include <unordered_map>
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +000034#include <vector>
Eugene Zelenko6ac3f732016-01-26 18:48:36 +000035
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +000036using namespace llvm;
37
Krzysztof Parzyszek6753f332015-11-22 15:20:19 +000038// --------------------------------------------------------------------
39// Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
40
41// DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
42// This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
43//
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
48//
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
57//
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.
60
61typedef uint64_t DFAInput;
62typedef int64_t DFAStateInput;
63#define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable.
64
65namespace {
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +000066
Krzysztof Parzyszek6753f332015-11-22 15:20:19 +000067 DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
68 return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
69 }
70
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;
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +000076 assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
77 "Exceeded maximum number of DFA terms");
Krzysztof Parzyszek6753f332015-11-22 15:20:19 +000078 for (auto U : InsnClass)
79 InsnInput = addDFAFuncUnits(InsnInput, U);
80 return InsnInput;
81 }
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +000082
Eugene Zelenko6ac3f732016-01-26 18:48:36 +000083} // end anonymous namespace
84
Krzysztof Parzyszek6753f332015-11-22 15:20:19 +000085// --------------------------------------------------------------------
86
Krzysztof Parzyszekdd135242015-11-21 22:46:52 +000087#ifndef NDEBUG
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +000088// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
89//
90// dbgsInsnClass - When debugging, print instruction class stages.
91//
92void dbgsInsnClass(const std::vector<unsigned> &InsnClass);
93//
94// dbgsStateInfo - When debugging, print the set of state info.
95//
96void dbgsStateInfo(const std::set<unsigned> &stateInfo);
97//
98// dbgsIndent - When debugging, indent by the specified amount.
99//
100void dbgsIndent(unsigned indent);
Krzysztof Parzyszekdd135242015-11-21 22:46:52 +0000101#endif
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000102
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000103//
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +0000104// class DFAPacketizerEmitter: class that generates and prints out the DFA
105// for resource tracking.
106//
107namespace {
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +0000108
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +0000109class DFAPacketizerEmitter {
110private:
111 std::string TargetName;
112 //
113 // allInsnClasses is the set of all possible resources consumed by an
114 // InstrStage.
115 //
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000116 std::vector<std::vector<unsigned>> allInsnClasses;
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +0000117 RecordKeeper &Records;
118
119public:
120 DFAPacketizerEmitter(RecordKeeper &R);
121
122 //
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000123 // collectAllFuncUnits - Construct a map of function unit names to bits.
124 //
125 int collectAllFuncUnits(std::vector<Record*> &ProcItinList,
126 std::map<std::string, unsigned> &FUNameToBitsMap,
127 int &maxResources,
128 raw_ostream &OS);
129
130 //
131 // collectAllComboFuncs - Construct a map from a combo function unit bit to
132 // the bits of all included functional units.
133 //
134 int collectAllComboFuncs(std::vector<Record*> &ComboFuncList,
135 std::map<std::string, unsigned> &FUNameToBitsMap,
136 std::map<unsigned, unsigned> &ComboBitToBitsMap,
137 raw_ostream &OS);
138
139 //
140 // collectOneInsnClass - Populate allInsnClasses with one instruction class.
141 //
142 int collectOneInsnClass(const std::string &ProcName,
143 std::vector<Record*> &ProcItinList,
144 std::map<std::string, unsigned> &FUNameToBitsMap,
145 Record *ItinData,
146 raw_ostream &OS);
147
148 //
149 // collectAllInsnClasses - Populate allInsnClasses which is a set of units
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +0000150 // used in each stage.
151 //
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000152 int collectAllInsnClasses(const std::string &ProcName,
153 std::vector<Record*> &ProcItinList,
154 std::map<std::string, unsigned> &FUNameToBitsMap,
155 std::vector<Record*> &ItinDataList,
156 int &maxStages,
157 raw_ostream &OS);
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +0000158
James Molloy6ccd6732019-08-30 19:50:49 +0000159 // Emit code for a subset of itineraries.
160 void emitForItineraries(raw_ostream &OS,
161 std::vector<Record *> &ProcItinList,
162 std::string DFAName);
163
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +0000164 void run(raw_ostream &OS);
165};
Eugene Zelenko6ac3f732016-01-26 18:48:36 +0000166} // end anonymous namespace
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000167
Krzysztof Parzyszek8dd552d2015-11-21 22:19:50 +0000168#ifndef NDEBUG
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000169// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
170//
171// dbgsInsnClass - When debugging, print instruction class stages.
172//
173void dbgsInsnClass(const std::vector<unsigned> &InsnClass) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000174 LLVM_DEBUG(dbgs() << "InsnClass: ");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000175 for (unsigned i = 0; i < InsnClass.size(); ++i) {
176 if (i > 0) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000177 LLVM_DEBUG(dbgs() << ", ");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000178 }
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000179 LLVM_DEBUG(dbgs() << "0x" << Twine::utohexstr(InsnClass[i]));
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000180 }
181 DFAInput InsnInput = getDFAInsnInput(InsnClass);
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000182 LLVM_DEBUG(dbgs() << " (input: 0x" << Twine::utohexstr(InsnInput) << ")");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000183}
184
185//
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000186// dbgsIndent - When debugging, indent by the specified amount.
187//
188void dbgsIndent(unsigned indent) {
189 for (unsigned i = 0; i < indent; ++i) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000190 LLVM_DEBUG(dbgs() << " ");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000191 }
192}
Eugene Zelenko6ac3f732016-01-26 18:48:36 +0000193#endif // NDEBUG
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000194
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +0000195DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R):
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +0000196 TargetName(CodeGenTarget(R).getName()), Records(R) {}
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000197
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000198//
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000199// collectAllFuncUnits - Construct a map of function unit names to bits.
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000200//
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000201int DFAPacketizerEmitter::collectAllFuncUnits(
202 std::vector<Record*> &ProcItinList,
203 std::map<std::string, unsigned> &FUNameToBitsMap,
204 int &maxFUs,
205 raw_ostream &OS) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000206 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
207 "----------------------\n");
208 LLVM_DEBUG(dbgs() << "collectAllFuncUnits");
209 LLVM_DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n");
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000210
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000211 int totalFUs = 0;
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000212 // 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");
216
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000217 LLVM_DEBUG(dbgs() << " FU:" << i << " (" << FUs.size() << " FUs) "
218 << Proc->getName());
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000219
Sebastian Pop9aa61372011-12-06 17:34:11 +0000220 // Convert macros to bits for each stage.
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000221 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;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000227 LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"
228 << Twine::utohexstr(FuncResources));
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000229 }
230 if (((int) numFUs) > maxFUs) {
231 maxFUs = numFUs;
232 }
233 totalFUs += numFUs;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000234 LLVM_DEBUG(dbgs() << "\n");
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000235 }
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000236 return totalFUs;
237}
238
239//
240// collectAllComboFuncs - Construct a map from a combo function unit bit to
241// the bits of all included functional units.
242//
243int DFAPacketizerEmitter::collectAllComboFuncs(
244 std::vector<Record*> &ComboFuncList,
245 std::map<std::string, unsigned> &FUNameToBitsMap,
246 std::map<unsigned, unsigned> &ComboBitToBitsMap,
247 raw_ostream &OS) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000248 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
249 "----------------------\n");
250 LLVM_DEBUG(dbgs() << "collectAllComboFuncs");
251 LLVM_DEBUG(dbgs() << " (" << ComboFuncList.size() << " sets)\n");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000252
253 int numCombos = 0;
254 for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
255 Record *Func = ComboFuncList[i];
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000256 std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD");
257
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000258 LLVM_DEBUG(dbgs() << " CFD:" << i << " (" << FUs.size() << " combo FUs) "
259 << Func->getName() << "\n");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000260
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");
Benjamin Kramer4ca41fd2016-06-12 17:30:47 +0000269 const std::string &ComboFuncName = ComboFunc->getName();
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000270 unsigned ComboBit = FUNameToBitsMap[ComboFuncName];
271 unsigned ComboResources = ComboBit;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000272 LLVM_DEBUG(dbgs() << " combo: " << ComboFuncName << ":0x"
273 << Twine::utohexstr(ComboResources) << "\n");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000274 for (unsigned k = 0, M = FuncList.size(); k < M; ++k) {
275 std::string FuncName = FuncList[k]->getName();
276 unsigned FuncResources = FUNameToBitsMap[FuncName];
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000277 LLVM_DEBUG(dbgs() << " " << FuncName << ":0x"
278 << Twine::utohexstr(FuncResources) << "\n");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000279 ComboResources |= FuncResources;
280 }
281 ComboBitToBitsMap[ComboBit] = ComboResources;
282 numCombos++;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000283 LLVM_DEBUG(dbgs() << " => combo bits: " << ComboFuncName << ":0x"
284 << Twine::utohexstr(ComboBit) << " = 0x"
285 << Twine::utohexstr(ComboResources) << "\n");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000286 }
287 }
288 return numCombos;
289}
290
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000291//
292// collectOneInsnClass - Populate allInsnClasses with one instruction class
293//
294int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName,
295 std::vector<Record*> &ProcItinList,
296 std::map<std::string, unsigned> &FUNameToBitsMap,
297 Record *ItinData,
298 raw_ostream &OS) {
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000299 const std::vector<Record*> &StageList =
300 ItinData->getValueAsListOfDefs("Stages");
301
Sebastian Pop9aa61372011-12-06 17:34:11 +0000302 // The number of stages.
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000303 unsigned NStages = StageList.size();
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000304
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000305 LLVM_DEBUG(dbgs() << " " << ItinData->getValueAsDef("TheClass")->getName()
306 << "\n");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000307
308 std::vector<unsigned> UnitBits;
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000309
Sebastian Pop9aa61372011-12-06 17:34:11 +0000310 // Compute the bitwise or of each unit used in this stage.
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000311 for (unsigned i = 0; i < NStages; ++i) {
312 const Record *Stage = StageList[i];
313
Sebastian Pop9aa61372011-12-06 17:34:11 +0000314 // Get unit list.
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000315 const std::vector<Record*> &UnitList =
316 Stage->getValueAsListOfDefs("Units");
317
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000318 LLVM_DEBUG(dbgs() << " stage:" << i << " [" << UnitList.size()
319 << " units]:");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000320 unsigned dbglen = 26; // cursor after stage dbgs
321
322 // Compute the bitwise or of each unit used in this stage.
323 unsigned UnitBitValue = 0;
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000324 for (unsigned j = 0, M = UnitList.size(); j < M; ++j) {
Sebastian Pop9aa61372011-12-06 17:34:11 +0000325 // Conduct bitwise or.
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000326 std::string UnitName = UnitList[j]->getName();
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000327 LLVM_DEBUG(dbgs() << " " << j << ":" << UnitName);
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000328 dbglen += 3 + UnitName.length();
329 assert(FUNameToBitsMap.count(UnitName));
330 UnitBitValue |= FUNameToBitsMap[UnitName];
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000331 }
332
333 if (UnitBitValue != 0)
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000334 UnitBits.push_back(UnitBitValue);
335
336 while (dbglen <= 64) { // line up bits dbgs
337 dbglen += 8;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000338 LLVM_DEBUG(dbgs() << "\t");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000339 }
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000340 LLVM_DEBUG(dbgs() << " (bits: 0x" << Twine::utohexstr(UnitBitValue)
341 << ")\n");
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000342 }
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000343
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +0000344 if (!UnitBits.empty())
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000345 allInsnClasses.push_back(UnitBits);
346
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000347 LLVM_DEBUG({
Krzysztof Parzyszekdd135242015-11-21 22:46:52 +0000348 dbgs() << " ";
349 dbgsInsnClass(UnitBits);
350 dbgs() << "\n";
351 });
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000352
353 return NStages;
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000354}
355
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000356//
357// collectAllInsnClasses - Populate allInsnClasses which is a set of units
358// used in each stage.
359//
360int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName,
361 std::vector<Record*> &ProcItinList,
362 std::map<std::string, unsigned> &FUNameToBitsMap,
363 std::vector<Record*> &ItinDataList,
364 int &maxStages,
365 raw_ostream &OS) {
366 // Collect all instruction classes.
367 unsigned M = ItinDataList.size();
368
369 int numInsnClasses = 0;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000370 LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
371 "----------------------\n"
372 << "collectAllInsnClasses " << ProcName << " (" << M
373 << " classes)\n");
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000374
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) {
381 maxStages = NStages;
382 }
383 numInsnClasses++;
384 }
385 return numInsnClasses;
386}
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000387
388//
Sebastian Pop9aa61372011-12-06 17:34:11 +0000389// Run the worklist algorithm to generate the DFA.
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000390//
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +0000391void DFAPacketizerEmitter::run(raw_ostream &OS) {
James Molloy6ccd6732019-08-30 19:50:49 +0000392 OS << "\n"
393 << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
394 OS << "namespace llvm {\n";
395
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";
401
Sebastian Pop9aa61372011-12-06 17:34:11 +0000402 // Collect processor iteraries.
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000403 std::vector<Record*> ProcItinList =
404 Records.getAllDerivedDefinitions("ProcessorItineraries");
405
James Molloy6ccd6732019-08-30 19:50:49 +0000406 std::unordered_map<std::string, std::vector<Record*>> ItinsByNamespace;
407 for (Record *R : ProcItinList)
408 ItinsByNamespace[R->getValueAsString("PacketizerNamespace")].push_back(R);
409
410 for (auto &KV : ItinsByNamespace)
411 emitForItineraries(OS, KV.second, KV.first);
412 OS << "} // end namespace llvm\n";
413}
414
415void DFAPacketizerEmitter::emitForItineraries(
416 raw_ostream &OS, std::vector<Record *> &ProcItinList,
417 std::string DFAName) {
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000418 //
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000419 // Collect the Functional units.
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000420 //
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000421 std::map<std::string, unsigned> FUNameToBitsMap;
422 int maxResources = 0;
423 collectAllFuncUnits(ProcItinList,
424 FUNameToBitsMap, maxResources, OS);
425
426 //
427 // Collect the Combo Functional units.
428 //
429 std::map<unsigned, unsigned> ComboBitToBitsMap;
430 std::vector<Record*> ComboFuncList =
431 Records.getAllDerivedDefinitions("ComboFuncUnits");
James Molloy12092a92019-10-17 08:34:29 +0000432 collectAllComboFuncs(ComboFuncList, FUNameToBitsMap, ComboBitToBitsMap, OS);
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000433
434 //
435 // Collect the itineraries.
436 //
437 int maxStages = 0;
438 int numInsnClasses = 0;
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000439 for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) {
440 Record *Proc = ProcItinList[i];
441
Sebastian Pop9aa61372011-12-06 17:34:11 +0000442 // Get processor itinerary name.
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000443 const std::string &ProcName = Proc->getName();
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000444
Sebastian Pop9aa61372011-12-06 17:34:11 +0000445 // Skip default.
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000446 if (ProcName == "NoItineraries")
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000447 continue;
448
Sebastian Pop9aa61372011-12-06 17:34:11 +0000449 // Sanity check for at least one instruction itinerary class.
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000450 unsigned NItinClasses =
451 Records.getAllDerivedDefinitions("InstrItinClass").size();
452 if (NItinClasses == 0)
453 return;
454
Sebastian Pop9aa61372011-12-06 17:34:11 +0000455 // Get itinerary data list.
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000456 std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID");
457
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000458 // Collect all instruction classes
459 numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList,
460 FUNameToBitsMap, ItinDataList, maxStages, OS);
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000461 }
462
James Molloy12092a92019-10-17 08:34:29 +0000463 // The type of a state in the nondeterministic automaton we're defining.
464 using NfaStateTy = unsigned;
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000465
James Molloy12092a92019-10-17 08:34:29 +0000466 // Given a resource state, return all resource states by applying
467 // InsnClass.
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();
477 V.pop_front();
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000478
James Molloy12092a92019-10-17 08:34:29 +0000479 // 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.
484 continue;
485 unsigned Combo = ComboBitToBitsMap[ResourceMask];
486 if (Combo && ((~S & Combo) != Combo))
487 // This combo units bits are not available.
488 continue;
489 unsigned ResultingResourceState = S | ResourceMask | Combo;
490 if (ResultingResourceState == S)
491 continue;
492 V.push_back(ResultingResourceState);
493 }
494 }
495 }
496 return V;
497 };
498
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
501 // applyInsnClass.
502 auto canApplyInsnClass = [](ArrayRef<unsigned> InsnClass,
503 NfaStateTy State) -> bool {
504 for (unsigned Resources : InsnClass) {
505 if ((State | Resources) == State)
506 return false;
507 }
508 return true;
509 };
510
511 DfaEmitter Emitter;
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();
Krzysztof Parzyszekb4655722015-11-21 20:00:45 +0000518 for (unsigned i = 0; i < allInsnClasses.size(); i++) {
James Molloy12092a92019-10-17 08:34:29 +0000519 const std::vector<unsigned> &InsnClass = allInsnClasses[i];
520 if (!canApplyInsnClass(InsnClass, State))
521 continue;
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));
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000526 }
527 }
528 }
529
James Molloy12092a92019-10-17 08:34:29 +0000530 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";
James Molloy6ccd6732019-08-30 19:50:49 +0000535
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"
James Molloy12092a92019-10-17 08:34:29 +0000541 << " Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName
542 << "Transition>(" << TargetAndDFAName << "Transitions), "
543 << TargetAndDFAName << "TransitionInfo);\n"
544 << " return new DFAPacketizer(IID, std::move(A));\n"
545 << "\n}\n\n";
Anshuman Dasgupta08ebdc12011-12-01 21:10:21 +0000546}
Jakob Stoklund Olesene6aed132012-06-11 15:37:55 +0000547
548namespace llvm {
549
550void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) {
551 emitSourceFileHeader("Target DFA Packetizer Tables", OS);
552 DFAPacketizerEmitter(RK).run(OS);
553}
554
Eugene Zelenkoa3fe70d2016-11-30 17:48:10 +0000555} // end namespace llvm