]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine-----===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This class parses the Schedule.td file and produces an API that can be used | |
11 | // to reason about whether an instruction can be added to a packet on a VLIW | |
12 | // architecture. The class internally generates a deterministic finite | |
13 | // automaton (DFA) that models all possible mappings of machine instructions | |
14 | // to functional units as instructions are added to a packet. | |
15 | // | |
16 | //===----------------------------------------------------------------------===// | |
17 | ||
18 | #include "CodeGenTarget.h" | |
19 | #include "llvm/ADT/DenseSet.h" | |
20 | #include "llvm/ADT/STLExtras.h" | |
21 | #include "llvm/TableGen/Record.h" | |
22 | #include "llvm/TableGen/TableGenBackend.h" | |
23 | #include <list> | |
24 | #include <map> | |
25 | #include <string> | |
26 | using namespace llvm; | |
27 | ||
28 | // | |
29 | // class DFAPacketizerEmitter: class that generates and prints out the DFA | |
30 | // for resource tracking. | |
31 | // | |
32 | namespace { | |
33 | class DFAPacketizerEmitter { | |
34 | private: | |
35 | std::string TargetName; | |
36 | // | |
37 | // allInsnClasses is the set of all possible resources consumed by an | |
38 | // InstrStage. | |
39 | // | |
40 | DenseSet<unsigned> allInsnClasses; | |
41 | RecordKeeper &Records; | |
42 | ||
43 | public: | |
44 | DFAPacketizerEmitter(RecordKeeper &R); | |
45 | ||
46 | // | |
47 | // collectAllInsnClasses: Populate allInsnClasses which is a set of units | |
48 | // used in each stage. | |
49 | // | |
50 | void collectAllInsnClasses(const std::string &Name, | |
51 | Record *ItinData, | |
52 | unsigned &NStages, | |
53 | raw_ostream &OS); | |
54 | ||
55 | void run(raw_ostream &OS); | |
56 | }; | |
57 | } // End anonymous namespace. | |
58 | ||
59 | // | |
60 | // | |
61 | // State represents the usage of machine resources if the packet contains | |
62 | // a set of instruction classes. | |
63 | // | |
64 | // Specifically, currentState is a set of bit-masks. | |
65 | // The nth bit in a bit-mask indicates whether the nth resource is being used | |
66 | // by this state. The set of bit-masks in a state represent the different | |
67 | // possible outcomes of transitioning to this state. | |
68 | // For example: consider a two resource architecture: resource L and resource M | |
69 | // with three instruction classes: L, M, and L_or_M. | |
70 | // From the initial state (currentState = 0x00), if we add instruction class | |
71 | // L_or_M we will transition to a state with currentState = [0x01, 0x10]. This | |
72 | // represents the possible resource states that can result from adding a L_or_M | |
73 | // instruction | |
74 | // | |
75 | // Another way of thinking about this transition is we are mapping a NDFA with | |
76 | // two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10]. | |
77 | // | |
78 | // A State instance also contains a collection of transitions from that state: | |
79 | // a map from inputs to new states. | |
80 | // | |
81 | namespace { | |
82 | class State { | |
83 | public: | |
84 | static int currentStateNum; | |
85 | int stateNum; | |
86 | bool isInitial; | |
87 | std::set<unsigned> stateInfo; | |
88 | typedef std::map<unsigned, State *> TransitionMap; | |
89 | TransitionMap Transitions; | |
90 | ||
91 | State(); | |
92 | State(const State &S); | |
93 | ||
94 | bool operator<(const State &s) const { | |
95 | return stateNum < s.stateNum; | |
96 | } | |
97 | ||
98 | // | |
99 | // canAddInsnClass - Returns true if an instruction of type InsnClass is a | |
100 | // valid transition from this state, i.e., can an instruction of type InsnClass | |
101 | // be added to the packet represented by this state. | |
102 | // | |
103 | // PossibleStates is the set of valid resource states that ensue from valid | |
104 | // transitions. | |
105 | // | |
106 | bool canAddInsnClass(unsigned InsnClass) const; | |
107 | // | |
108 | // AddInsnClass - Return all combinations of resource reservation | |
109 | // which are possible from this state (PossibleStates). | |
110 | // | |
111 | void AddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates); | |
112 | // | |
113 | // addTransition - Add a transition from this state given the input InsnClass | |
114 | // | |
115 | void addTransition(unsigned InsnClass, State *To); | |
116 | // | |
117 | // hasTransition - Returns true if there is a transition from this state | |
118 | // given the input InsnClass | |
119 | // | |
120 | bool hasTransition(unsigned InsnClass); | |
121 | }; | |
122 | } // End anonymous namespace. | |
123 | ||
124 | // | |
125 | // class DFA: deterministic finite automaton for processor resource tracking. | |
126 | // | |
127 | namespace { | |
128 | class DFA { | |
129 | public: | |
130 | DFA(); | |
131 | ~DFA(); | |
132 | ||
133 | // Set of states. Need to keep this sorted to emit the transition table. | |
134 | typedef std::set<State *, less_ptr<State> > StateSet; | |
135 | StateSet states; | |
136 | ||
137 | State *currentState; | |
138 | ||
139 | // | |
140 | // Modify the DFA. | |
141 | // | |
142 | void initialize(); | |
143 | void addState(State *); | |
144 | ||
145 | // | |
146 | // writeTable: Print out a table representing the DFA. | |
147 | // | |
148 | void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName); | |
149 | }; | |
150 | } // End anonymous namespace. | |
151 | ||
152 | ||
153 | // | |
154 | // Constructors and destructors for State and DFA | |
155 | // | |
156 | State::State() : | |
157 | stateNum(currentStateNum++), isInitial(false) {} | |
158 | ||
159 | ||
160 | State::State(const State &S) : | |
161 | stateNum(currentStateNum++), isInitial(S.isInitial), | |
162 | stateInfo(S.stateInfo) {} | |
163 | ||
164 | DFA::DFA(): currentState(NULL) {} | |
165 | ||
166 | DFA::~DFA() { | |
167 | DeleteContainerPointers(states); | |
168 | } | |
169 | ||
170 | // | |
171 | // addTransition - Add a transition from this state given the input InsnClass | |
172 | // | |
173 | void State::addTransition(unsigned InsnClass, State *To) { | |
174 | assert(!Transitions.count(InsnClass) && | |
175 | "Cannot have multiple transitions for the same input"); | |
176 | Transitions[InsnClass] = To; | |
177 | } | |
178 | ||
179 | // | |
180 | // hasTransition - Returns true if there is a transition from this state | |
181 | // given the input InsnClass | |
182 | // | |
183 | bool State::hasTransition(unsigned InsnClass) { | |
184 | return Transitions.count(InsnClass) > 0; | |
185 | } | |
186 | ||
187 | // | |
188 | // AddInsnClass - Return all combinations of resource reservation | |
189 | // which are possible from this state (PossibleStates). | |
190 | // | |
191 | void State::AddInsnClass(unsigned InsnClass, | |
192 | std::set<unsigned> &PossibleStates) { | |
193 | // | |
194 | // Iterate over all resource states in currentState. | |
195 | // | |
196 | ||
197 | for (std::set<unsigned>::iterator SI = stateInfo.begin(); | |
198 | SI != stateInfo.end(); ++SI) { | |
199 | unsigned thisState = *SI; | |
200 | ||
201 | // | |
202 | // Iterate over all possible resources used in InsnClass. | |
203 | // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}. | |
204 | // | |
205 | ||
206 | DenseSet<unsigned> VisitedResourceStates; | |
207 | for (unsigned int j = 0; j < sizeof(InsnClass) * 8; ++j) { | |
208 | if ((0x1 << j) & InsnClass) { | |
209 | // | |
210 | // For each possible resource used in InsnClass, generate the | |
211 | // resource state if that resource was used. | |
212 | // | |
213 | unsigned ResultingResourceState = thisState | (0x1 << j); | |
214 | // | |
215 | // Check if the resulting resource state can be accommodated in this | |
216 | // packet. | |
217 | // We compute ResultingResourceState OR thisState. | |
218 | // If the result of the OR is different than thisState, it implies | |
219 | // that there is at least one resource that can be used to schedule | |
220 | // InsnClass in the current packet. | |
221 | // Insert ResultingResourceState into PossibleStates only if we haven't | |
222 | // processed ResultingResourceState before. | |
223 | // | |
224 | if ((ResultingResourceState != thisState) && | |
225 | (VisitedResourceStates.count(ResultingResourceState) == 0)) { | |
226 | VisitedResourceStates.insert(ResultingResourceState); | |
227 | PossibleStates.insert(ResultingResourceState); | |
228 | } | |
229 | } | |
230 | } | |
231 | } | |
232 | ||
233 | } | |
234 | ||
235 | ||
236 | // | |
237 | // canAddInsnClass - Quickly verifies if an instruction of type InsnClass is a | |
238 | // valid transition from this state i.e., can an instruction of type InsnClass | |
239 | // be added to the packet represented by this state. | |
240 | // | |
241 | bool State::canAddInsnClass(unsigned InsnClass) const { | |
242 | for (std::set<unsigned>::const_iterator SI = stateInfo.begin(); | |
243 | SI != stateInfo.end(); ++SI) { | |
244 | if (~*SI & InsnClass) | |
245 | return true; | |
246 | } | |
247 | return false; | |
248 | } | |
249 | ||
250 | ||
251 | void DFA::initialize() { | |
252 | assert(currentState && "Missing current state"); | |
253 | currentState->isInitial = true; | |
254 | } | |
255 | ||
256 | ||
257 | void DFA::addState(State *S) { | |
258 | assert(!states.count(S) && "State already exists"); | |
259 | states.insert(S); | |
260 | } | |
261 | ||
262 | ||
263 | int State::currentStateNum = 0; | |
264 | ||
265 | DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): | |
266 | TargetName(CodeGenTarget(R).getName()), | |
267 | allInsnClasses(), Records(R) {} | |
268 | ||
269 | ||
270 | // | |
271 | // writeTableAndAPI - Print out a table representing the DFA and the | |
272 | // associated API to create a DFA packetizer. | |
273 | // | |
274 | // Format: | |
275 | // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid | |
276 | // transitions. | |
277 | // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for | |
278 | // the ith state. | |
279 | // | |
280 | // | |
281 | void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { | |
970d7e83 | 282 | static const std::string SentinelEntry = "{-1, -1}"; |
223e47cc LB |
283 | DFA::StateSet::iterator SI = states.begin(); |
284 | // This table provides a map to the beginning of the transitions for State s | |
285 | // in DFAStateInputTable. | |
286 | std::vector<int> StateEntry(states.size()); | |
287 | ||
288 | OS << "namespace llvm {\n\n"; | |
289 | OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n"; | |
290 | ||
291 | // Tracks the total valid transitions encountered so far. It is used | |
292 | // to construct the StateEntry table. | |
293 | int ValidTransitions = 0; | |
294 | for (unsigned i = 0; i < states.size(); ++i, ++SI) { | |
295 | assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers"); | |
296 | StateEntry[i] = ValidTransitions; | |
297 | for (State::TransitionMap::iterator | |
298 | II = (*SI)->Transitions.begin(), IE = (*SI)->Transitions.end(); | |
299 | II != IE; ++II) { | |
300 | OS << "{" << II->first << ", " | |
301 | << II->second->stateNum | |
302 | << "}, "; | |
303 | } | |
304 | ValidTransitions += (*SI)->Transitions.size(); | |
305 | ||
306 | // If there are no valid transitions from this stage, we need a sentinel | |
307 | // transition. | |
308 | if (ValidTransitions == StateEntry[i]) { | |
970d7e83 | 309 | OS << SentinelEntry << ","; |
223e47cc LB |
310 | ++ValidTransitions; |
311 | } | |
312 | ||
313 | OS << "\n"; | |
314 | } | |
970d7e83 LB |
315 | |
316 | // Print out a sentinel entry at the end of the StateInputTable. This is | |
317 | // needed to iterate over StateInputTable in DFAPacketizer::ReadTable() | |
318 | OS << SentinelEntry << "\n"; | |
319 | ||
223e47cc LB |
320 | OS << "};\n\n"; |
321 | OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; | |
322 | ||
323 | // Multiply i by 2 since each entry in DFAStateInputTable is a set of | |
324 | // two numbers. | |
325 | for (unsigned i = 0; i < states.size(); ++i) | |
326 | OS << StateEntry[i] << ", "; | |
327 | ||
970d7e83 LB |
328 | // Print out the index to the sentinel entry in StateInputTable |
329 | OS << ValidTransitions << ", "; | |
330 | ||
223e47cc LB |
331 | OS << "\n};\n"; |
332 | OS << "} // namespace\n"; | |
333 | ||
334 | ||
335 | // | |
336 | // Emit DFA Packetizer tables if the target is a VLIW machine. | |
337 | // | |
338 | std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; | |
339 | OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; | |
340 | OS << "namespace llvm {\n"; | |
341 | OS << "DFAPacketizer *" << SubTargetClassName << "::" | |
342 | << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" | |
343 | << " return new DFAPacketizer(IID, " << TargetName | |
344 | << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; | |
345 | OS << "} // End llvm namespace \n"; | |
346 | } | |
347 | ||
348 | ||
349 | // | |
350 | // collectAllInsnClasses - Populate allInsnClasses which is a set of units | |
351 | // used in each stage. | |
352 | // | |
353 | void DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name, | |
354 | Record *ItinData, | |
355 | unsigned &NStages, | |
356 | raw_ostream &OS) { | |
357 | // Collect processor itineraries. | |
358 | std::vector<Record*> ProcItinList = | |
359 | Records.getAllDerivedDefinitions("ProcessorItineraries"); | |
360 | ||
361 | // If just no itinerary then don't bother. | |
362 | if (ProcItinList.size() < 2) | |
363 | return; | |
364 | std::map<std::string, unsigned> NameToBitsMap; | |
365 | ||
366 | // Parse functional units for all the itineraries. | |
367 | for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { | |
368 | Record *Proc = ProcItinList[i]; | |
369 | std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); | |
370 | ||
371 | // Convert macros to bits for each stage. | |
372 | for (unsigned i = 0, N = FUs.size(); i < N; ++i) | |
373 | NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); | |
374 | } | |
375 | ||
376 | const std::vector<Record*> &StageList = | |
377 | ItinData->getValueAsListOfDefs("Stages"); | |
378 | ||
379 | // The number of stages. | |
380 | NStages = StageList.size(); | |
381 | ||
382 | // For each unit. | |
383 | unsigned UnitBitValue = 0; | |
384 | ||
385 | // Compute the bitwise or of each unit used in this stage. | |
386 | for (unsigned i = 0; i < NStages; ++i) { | |
387 | const Record *Stage = StageList[i]; | |
388 | ||
389 | // Get unit list. | |
390 | const std::vector<Record*> &UnitList = | |
391 | Stage->getValueAsListOfDefs("Units"); | |
392 | ||
393 | for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { | |
394 | // Conduct bitwise or. | |
395 | std::string UnitName = UnitList[j]->getName(); | |
396 | assert(NameToBitsMap.count(UnitName)); | |
397 | UnitBitValue |= NameToBitsMap[UnitName]; | |
398 | } | |
399 | ||
400 | if (UnitBitValue != 0) | |
401 | allInsnClasses.insert(UnitBitValue); | |
402 | } | |
403 | } | |
404 | ||
405 | ||
406 | // | |
407 | // Run the worklist algorithm to generate the DFA. | |
408 | // | |
409 | void DFAPacketizerEmitter::run(raw_ostream &OS) { | |
410 | ||
411 | // Collect processor iteraries. | |
412 | std::vector<Record*> ProcItinList = | |
413 | Records.getAllDerivedDefinitions("ProcessorItineraries"); | |
414 | ||
415 | // | |
416 | // Collect the instruction classes. | |
417 | // | |
418 | for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { | |
419 | Record *Proc = ProcItinList[i]; | |
420 | ||
421 | // Get processor itinerary name. | |
422 | const std::string &Name = Proc->getName(); | |
423 | ||
424 | // Skip default. | |
425 | if (Name == "NoItineraries") | |
426 | continue; | |
427 | ||
428 | // Sanity check for at least one instruction itinerary class. | |
429 | unsigned NItinClasses = | |
430 | Records.getAllDerivedDefinitions("InstrItinClass").size(); | |
431 | if (NItinClasses == 0) | |
432 | return; | |
433 | ||
434 | // Get itinerary data list. | |
435 | std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); | |
436 | ||
437 | // Collect instruction classes for all itinerary data. | |
438 | for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { | |
439 | Record *ItinData = ItinDataList[j]; | |
440 | unsigned NStages; | |
441 | collectAllInsnClasses(Name, ItinData, NStages, OS); | |
442 | } | |
443 | } | |
444 | ||
445 | ||
446 | // | |
447 | // Run a worklist algorithm to generate the DFA. | |
448 | // | |
449 | DFA D; | |
450 | State *Initial = new State; | |
451 | Initial->isInitial = true; | |
452 | Initial->stateInfo.insert(0x0); | |
453 | D.addState(Initial); | |
454 | SmallVector<State*, 32> WorkList; | |
455 | std::map<std::set<unsigned>, State*> Visited; | |
456 | ||
457 | WorkList.push_back(Initial); | |
458 | ||
459 | // | |
460 | // Worklist algorithm to create a DFA for processor resource tracking. | |
461 | // C = {set of InsnClasses} | |
462 | // Begin with initial node in worklist. Initial node does not have | |
463 | // any consumed resources, | |
464 | // ResourceState = 0x0 | |
465 | // Visited = {} | |
466 | // While worklist != empty | |
467 | // S = first element of worklist | |
468 | // For every instruction class C | |
469 | // if we can accommodate C in S: | |
470 | // S' = state with resource states = {S Union C} | |
471 | // Add a new transition: S x C -> S' | |
472 | // If S' is not in Visited: | |
473 | // Add S' to worklist | |
474 | // Add S' to Visited | |
475 | // | |
476 | while (!WorkList.empty()) { | |
477 | State *current = WorkList.pop_back_val(); | |
478 | for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(), | |
479 | CE = allInsnClasses.end(); CI != CE; ++CI) { | |
480 | unsigned InsnClass = *CI; | |
481 | ||
482 | std::set<unsigned> NewStateResources; | |
483 | // | |
484 | // If we haven't already created a transition for this input | |
485 | // and the state can accommodate this InsnClass, create a transition. | |
486 | // | |
487 | if (!current->hasTransition(InsnClass) && | |
488 | current->canAddInsnClass(InsnClass)) { | |
489 | State *NewState = NULL; | |
490 | current->AddInsnClass(InsnClass, NewStateResources); | |
491 | assert(NewStateResources.size() && "New states must be generated"); | |
492 | ||
493 | // | |
494 | // If we have seen this state before, then do not create a new state. | |
495 | // | |
496 | // | |
497 | std::map<std::set<unsigned>, State*>::iterator VI; | |
498 | if ((VI = Visited.find(NewStateResources)) != Visited.end()) | |
499 | NewState = VI->second; | |
500 | else { | |
501 | NewState = new State; | |
502 | NewState->stateInfo = NewStateResources; | |
503 | D.addState(NewState); | |
504 | Visited[NewStateResources] = NewState; | |
505 | WorkList.push_back(NewState); | |
506 | } | |
507 | ||
508 | current->addTransition(InsnClass, NewState); | |
509 | } | |
510 | } | |
511 | } | |
512 | ||
513 | // Print out the table. | |
514 | D.writeTableAndAPI(OS, TargetName); | |
515 | } | |
516 | ||
517 | namespace llvm { | |
518 | ||
519 | void EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { | |
520 | emitSourceFileHeader("Target DFA Packetizer Tables", OS); | |
521 | DFAPacketizerEmitter(RK).run(OS); | |
522 | } | |
523 | ||
524 | } // End llvm namespace |