/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/DFAPacketizer.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //=- llvm/CodeGen/DFAPacketizer.cpp - DFA Packetizer for VLIW -*- C++ -*-=====// |
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 | | // This class implements a deterministic finite automaton (DFA) based |
10 | | // packetizing mechanism for VLIW architectures. It provides APIs to |
11 | | // determine whether there exists a legal mapping of instructions to |
12 | | // functional unit assignments in a packet. The DFA is auto-generated from |
13 | | // the target's Schedule.td file. |
14 | | // |
15 | | // A DFA consists of 3 major elements: states, inputs, and transitions. For |
16 | | // the packetizing mechanism, the input is the set of instruction classes for |
17 | | // a target. The state models all possible combinations of functional unit |
18 | | // consumption for a given set of instructions in a packet. A transition |
19 | | // models the addition of an instruction to a packet. In the DFA constructed |
20 | | // by this class, if an instruction can be added to a packet, then a valid |
21 | | // transition exists from the corresponding state. Invalid transitions |
22 | | // indicate that the instruction cannot be added to the current packet. |
23 | | // |
24 | | //===----------------------------------------------------------------------===// |
25 | | |
26 | | #include "llvm/CodeGen/DFAPacketizer.h" |
27 | | #include "llvm/CodeGen/MachineFunction.h" |
28 | | #include "llvm/CodeGen/MachineInstr.h" |
29 | | #include "llvm/CodeGen/MachineInstrBundle.h" |
30 | | #include "llvm/CodeGen/ScheduleDAG.h" |
31 | | #include "llvm/CodeGen/ScheduleDAGInstrs.h" |
32 | | #include "llvm/MC/MCInstrDesc.h" |
33 | | #include "llvm/MC/MCInstrItineraries.h" |
34 | | #include "llvm/Support/CommandLine.h" |
35 | | #include "llvm/Support/Debug.h" |
36 | | #include "llvm/Support/raw_ostream.h" |
37 | | #include "llvm/Target/TargetInstrInfo.h" |
38 | | #include "llvm/Target/TargetSubtargetInfo.h" |
39 | | #include <algorithm> |
40 | | #include <cassert> |
41 | | #include <iterator> |
42 | | #include <memory> |
43 | | #include <vector> |
44 | | |
45 | | using namespace llvm; |
46 | | |
47 | | #define DEBUG_TYPE "packets" |
48 | | |
49 | | static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden, |
50 | | cl::init(0), cl::desc("If present, stops packetizing after N instructions")); |
51 | | |
52 | | static unsigned InstrCount = 0; |
53 | | |
54 | | // -------------------------------------------------------------------- |
55 | | // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp |
56 | | |
57 | 311k | static DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) { |
58 | 311k | return (Inp << DFA_MAX_RESOURCES) | FuncUnits; |
59 | 311k | } |
60 | | |
61 | | /// Return the DFAInput for an instruction class input vector. |
62 | | /// This function is used in both DFAPacketizer.cpp and in |
63 | | /// DFAPacketizerEmitter.cpp. |
64 | 0 | static DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) { |
65 | 0 | DFAInput InsnInput = 0; |
66 | 0 | assert((InsnClass.size() <= DFA_MAX_RESTERMS) && |
67 | 0 | "Exceeded maximum number of DFA terms"); |
68 | 0 | for (auto U : InsnClass) |
69 | 0 | InsnInput = addDFAFuncUnits(InsnInput, U); |
70 | 0 | return InsnInput; |
71 | 0 | } |
72 | | |
73 | | // -------------------------------------------------------------------- |
74 | | |
75 | | DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, |
76 | | const DFAStateInput (*SIT)[2], |
77 | | const unsigned *SET): |
78 | 7.52k | InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET) { |
79 | 7.52k | // Make sure DFA types are large enough for the number of terms & resources. |
80 | 7.52k | static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= |
81 | 7.52k | (8 * sizeof(DFAInput)), |
82 | 7.52k | "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput"); |
83 | 7.52k | static_assert( |
84 | 7.52k | (DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)), |
85 | 7.52k | "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput"); |
86 | 7.52k | } |
87 | | |
88 | | // Read the DFA transition table and update CachedTable. |
89 | | // |
90 | | // Format of the transition tables: |
91 | | // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid |
92 | | // transitions |
93 | | // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable |
94 | | // for the ith state |
95 | | // |
96 | 283k | void DFAPacketizer::ReadTable(unsigned int state) { |
97 | 283k | unsigned ThisState = DFAStateEntryTable[state]; |
98 | 283k | unsigned NextStateInTable = DFAStateEntryTable[state+1]; |
99 | 283k | // Early exit in case CachedTable has already contains this |
100 | 283k | // state's transitions. |
101 | 283k | if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0]))) |
102 | 263k | return; |
103 | 19.7k | |
104 | 328k | for (unsigned i = ThisState; 19.7k i < NextStateInTable328k ; i++308k ) |
105 | 308k | CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] = |
106 | 308k | DFAStateInputTable[i][1]; |
107 | 283k | } |
108 | | |
109 | | // Return the DFAInput for an instruction class. |
110 | 283k | DFAInput DFAPacketizer::getInsnInput(unsigned InsnClass) { |
111 | 283k | // Note: this logic must match that in DFAPacketizerDefs.h for input vectors. |
112 | 283k | DFAInput InsnInput = 0; |
113 | 283k | unsigned i = 0; |
114 | 283k | (void)i; |
115 | 283k | for (const InstrStage *IS = InstrItins->beginStage(InsnClass), |
116 | 594k | *IE = InstrItins->endStage(InsnClass); IS != IE594k ; ++IS311k ) { |
117 | 311k | InsnInput = addDFAFuncUnits(InsnInput, IS->getUnits()); |
118 | 311k | assert((i++ < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs"); |
119 | 311k | } |
120 | 283k | return InsnInput; |
121 | 283k | } |
122 | | |
123 | | // Return the DFAInput for an instruction class input vector. |
124 | 0 | DFAInput DFAPacketizer::getInsnInput(const std::vector<unsigned> &InsnClass) { |
125 | 0 | return getDFAInsnInput(InsnClass); |
126 | 0 | } |
127 | | |
128 | | // Check if the resources occupied by a MCInstrDesc are available in the |
129 | | // current state. |
130 | 206k | bool DFAPacketizer::canReserveResources(const MCInstrDesc *MID) { |
131 | 206k | unsigned InsnClass = MID->getSchedClass(); |
132 | 206k | DFAInput InsnInput = getInsnInput(InsnClass); |
133 | 206k | UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); |
134 | 206k | ReadTable(CurrentState); |
135 | 206k | return CachedTable.count(StateTrans) != 0; |
136 | 206k | } |
137 | | |
138 | | // Reserve the resources occupied by a MCInstrDesc and change the current |
139 | | // state to reflect that change. |
140 | 76.6k | void DFAPacketizer::reserveResources(const MCInstrDesc *MID) { |
141 | 76.6k | unsigned InsnClass = MID->getSchedClass(); |
142 | 76.6k | DFAInput InsnInput = getInsnInput(InsnClass); |
143 | 76.6k | UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); |
144 | 76.6k | ReadTable(CurrentState); |
145 | 76.6k | assert(CachedTable.count(StateTrans) != 0); |
146 | 76.6k | CurrentState = CachedTable[StateTrans]; |
147 | 76.6k | } |
148 | | |
149 | | // Check if the resources occupied by a machine instruction are available |
150 | | // in the current state. |
151 | 206k | bool DFAPacketizer::canReserveResources(MachineInstr &MI) { |
152 | 206k | const MCInstrDesc &MID = MI.getDesc(); |
153 | 206k | return canReserveResources(&MID); |
154 | 206k | } |
155 | | |
156 | | // Reserve the resources occupied by a machine instruction and change the |
157 | | // current state to reflect that change. |
158 | 76.6k | void DFAPacketizer::reserveResources(MachineInstr &MI) { |
159 | 76.6k | const MCInstrDesc &MID = MI.getDesc(); |
160 | 76.6k | reserveResources(&MID); |
161 | 76.6k | } |
162 | | |
163 | | namespace llvm { |
164 | | |
165 | | // This class extends ScheduleDAGInstrs and overrides the schedule method |
166 | | // to build the dependence graph. |
167 | | class DefaultVLIWScheduler : public ScheduleDAGInstrs { |
168 | | private: |
169 | | AliasAnalysis *AA; |
170 | | /// Ordered list of DAG postprocessing steps. |
171 | | std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; |
172 | | |
173 | | public: |
174 | | DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, |
175 | | AliasAnalysis *AA); |
176 | | |
177 | | // Actual scheduling work. |
178 | | void schedule() override; |
179 | | |
180 | | /// DefaultVLIWScheduler takes ownership of the Mutation object. |
181 | 2.59k | void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) { |
182 | 2.59k | Mutations.push_back(std::move(Mutation)); |
183 | 2.59k | } |
184 | | |
185 | | protected: |
186 | | void postprocessDAG(); |
187 | | }; |
188 | | |
189 | | } // end namespace llvm |
190 | | |
191 | | DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF, |
192 | | MachineLoopInfo &MLI, |
193 | | AliasAnalysis *AA) |
194 | 2.92k | : ScheduleDAGInstrs(MF, &MLI), AA(AA) { |
195 | 2.92k | CanHandleTerminators = true; |
196 | 2.92k | } |
197 | | |
198 | | /// Apply each ScheduleDAGMutation step in order. |
199 | 3.59k | void DefaultVLIWScheduler::postprocessDAG() { |
200 | 3.59k | for (auto &M : Mutations) |
201 | 4.65k | M->apply(this); |
202 | 3.59k | } |
203 | | |
204 | 3.59k | void DefaultVLIWScheduler::schedule() { |
205 | 3.59k | // Build the scheduling graph. |
206 | 3.59k | buildSchedGraph(AA); |
207 | 3.59k | postprocessDAG(); |
208 | 3.59k | } |
209 | | |
210 | | VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf, |
211 | | MachineLoopInfo &mli, AliasAnalysis *aa) |
212 | 2.92k | : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) { |
213 | 2.92k | ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget()); |
214 | 2.92k | VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA); |
215 | 2.92k | } |
216 | | |
217 | 2.92k | VLIWPacketizerList::~VLIWPacketizerList() { |
218 | 2.92k | delete VLIWScheduler; |
219 | 2.92k | delete ResourceTracker; |
220 | 2.92k | } |
221 | | |
222 | | // End the current packet, bundle packet instructions and reset DFA state. |
223 | | void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB, |
224 | 39.3k | MachineBasicBlock::iterator MI) { |
225 | 39.3k | DEBUG({ |
226 | 39.3k | if (!CurrentPacketMIs.empty()) { |
227 | 39.3k | dbgs() << "Finalizing packet:\n"; |
228 | 39.3k | for (MachineInstr *MI : CurrentPacketMIs) |
229 | 39.3k | dbgs() << " * " << *MI; |
230 | 39.3k | } |
231 | 39.3k | }); |
232 | 39.3k | if (CurrentPacketMIs.size() > 139.3k ) { |
233 | 16.9k | MachineInstr &MIFirst = *CurrentPacketMIs.front(); |
234 | 16.9k | finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator()); |
235 | 16.9k | } |
236 | 39.3k | CurrentPacketMIs.clear(); |
237 | 39.3k | ResourceTracker->clearResources(); |
238 | 39.3k | DEBUG(dbgs() << "End packet\n"); |
239 | 39.3k | } |
240 | | |
241 | | // Bundle machine instructions into packets. |
242 | | void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB, |
243 | | MachineBasicBlock::iterator BeginItr, |
244 | 3.59k | MachineBasicBlock::iterator EndItr) { |
245 | 3.59k | assert(VLIWScheduler && "VLIW Scheduler is not initialized!"); |
246 | 3.59k | VLIWScheduler->startBlock(MBB); |
247 | 3.59k | VLIWScheduler->enterRegion(MBB, BeginItr, EndItr, |
248 | 3.59k | std::distance(BeginItr, EndItr)); |
249 | 3.59k | VLIWScheduler->schedule(); |
250 | 3.59k | |
251 | 3.59k | DEBUG({ |
252 | 3.59k | dbgs() << "Scheduling DAG of the packetize region\n"; |
253 | 3.59k | for (SUnit &SU : VLIWScheduler->SUnits) |
254 | 3.59k | SU.dumpAll(VLIWScheduler); |
255 | 3.59k | }); |
256 | 3.59k | |
257 | 3.59k | // Generate MI -> SU map. |
258 | 3.59k | MIToSUnit.clear(); |
259 | 3.59k | for (SUnit &SU : VLIWScheduler->SUnits) |
260 | 69.4k | MIToSUnit[SU.getInstr()] = &SU; |
261 | 3.59k | |
262 | 3.59k | bool LimitPresent = InstrLimit.getPosition(); |
263 | 3.59k | |
264 | 3.59k | // The main packetizer loop. |
265 | 73.0k | for (; BeginItr != EndItr73.0k ; ++BeginItr69.4k ) { |
266 | 69.4k | if (LimitPresent69.4k ) { |
267 | 0 | if (InstrCount >= InstrLimit0 ) { |
268 | 0 | EndItr = BeginItr; |
269 | 0 | break; |
270 | 0 | } |
271 | 0 | InstrCount++; |
272 | 0 | } |
273 | 69.4k | MachineInstr &MI = *BeginItr; |
274 | 69.4k | initPacketizerState(); |
275 | 69.4k | |
276 | 69.4k | // End the current packet if needed. |
277 | 69.4k | if (isSoloInstruction(MI)69.4k ) { |
278 | 13.9k | endPacket(MBB, MI); |
279 | 13.9k | continue; |
280 | 13.9k | } |
281 | 55.4k | |
282 | 55.4k | // Ignore pseudo instructions. |
283 | 55.4k | if (55.4k ignorePseudoInstruction(MI, MBB)55.4k ) |
284 | 12 | continue; |
285 | 55.4k | |
286 | 55.4k | SUnit *SUI = MIToSUnit[&MI]; |
287 | 55.4k | assert(SUI && "Missing SUnit Info!"); |
288 | 55.4k | |
289 | 55.4k | // Ask DFA if machine resource is available for MI. |
290 | 55.4k | DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI); |
291 | 55.4k | |
292 | 55.4k | bool ResourceAvail = ResourceTracker->canReserveResources(MI); |
293 | 55.4k | DEBUG({ |
294 | 55.4k | if (ResourceAvail) |
295 | 55.4k | dbgs() << " Resources are available for adding MI to packet\n"; |
296 | 55.4k | else |
297 | 55.4k | dbgs() << " Resources NOT available\n"; |
298 | 55.4k | }); |
299 | 55.4k | if (ResourceAvail && 55.4k shouldAddToPacket(MI)53.1k ) { |
300 | 53.0k | // Dependency check for MI with instructions in CurrentPacketMIs. |
301 | 61.6k | for (auto MJ : CurrentPacketMIs) { |
302 | 61.6k | SUnit *SUJ = MIToSUnit[MJ]; |
303 | 61.6k | assert(SUJ && "Missing SUnit Info!"); |
304 | 61.6k | |
305 | 61.6k | DEBUG(dbgs() << " Checking against MJ " << *MJ); |
306 | 61.6k | // Is it legal to packetize SUI and SUJ together. |
307 | 61.6k | if (!isLegalToPacketizeTogether(SUI, SUJ)61.6k ) { |
308 | 6.89k | DEBUG(dbgs() << " Not legal to add MI, try to prune\n"); |
309 | 6.89k | // Allow packetization if dependency can be pruned. |
310 | 6.89k | if (!isLegalToPruneDependencies(SUI, SUJ)6.89k ) { |
311 | 6.89k | // End the packet if dependency cannot be pruned. |
312 | 6.89k | DEBUG(dbgs() << " Could not prune dependencies for adding MI\n"); |
313 | 6.89k | endPacket(MBB, MI); |
314 | 6.89k | break; |
315 | 6.89k | } |
316 | 0 | DEBUG0 (dbgs() << " Pruned dependence for adding MI\n"); |
317 | 0 | } |
318 | 61.6k | } |
319 | 55.4k | } else { |
320 | 2.37k | DEBUG(if (ResourceAvail) |
321 | 2.37k | dbgs() << "Resources are available, but instruction should not be " |
322 | 2.37k | "added to packet\n " << MI); |
323 | 2.37k | // End the packet if resource is not available, or if the instruction |
324 | 2.37k | // shoud not be added to the current packet. |
325 | 2.37k | endPacket(MBB, MI); |
326 | 2.37k | } |
327 | 55.4k | |
328 | 55.4k | // Add MI to the current packet. |
329 | 55.4k | DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n'); |
330 | 69.4k | BeginItr = addToPacket(MI); |
331 | 69.4k | } // For all instructions in the packetization range. |
332 | 3.59k | |
333 | 3.59k | // End any packet left behind. |
334 | 3.59k | endPacket(MBB, EndItr); |
335 | 3.59k | VLIWScheduler->exitRegion(); |
336 | 3.59k | VLIWScheduler->finishBlock(); |
337 | 3.59k | } |
338 | | |
339 | | // Add a DAG mutation object to the ordered list. |
340 | | void VLIWPacketizerList::addMutation( |
341 | 2.59k | std::unique_ptr<ScheduleDAGMutation> Mutation) { |
342 | 2.59k | VLIWScheduler->addMutation(std::move(Mutation)); |
343 | 2.59k | } |