Line data Source code
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/CodeGen/TargetInstrInfo.h"
33 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
34 : #include "llvm/MC/MCInstrDesc.h"
35 : #include "llvm/MC/MCInstrItineraries.h"
36 : #include "llvm/Support/CommandLine.h"
37 : #include "llvm/Support/Debug.h"
38 : #include "llvm/Support/raw_ostream.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 : static DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
58 500064 : return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
59 : }
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 : static DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
65 : DFAInput InsnInput = 0;
66 : assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
67 : "Exceeded maximum number of DFA terms");
68 0 : for (auto U : InsnClass)
69 : InsnInput = addDFAFuncUnits(InsnInput, U);
70 : return InsnInput;
71 : }
72 :
73 : // --------------------------------------------------------------------
74 :
75 21176 : DFAPacketizer::DFAPacketizer(const InstrItineraryData *I,
76 : const DFAStateInput (*SIT)[2],
77 21176 : const unsigned *SET):
78 21176 : InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET) {
79 : // Make sure DFA types are large enough for the number of terms & resources.
80 : static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <=
81 : (8 * sizeof(DFAInput)),
82 : "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput");
83 : static_assert(
84 : (DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)),
85 : "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput");
86 21176 : }
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 396475 : void DFAPacketizer::ReadTable(unsigned int state) {
97 396475 : unsigned ThisState = DFAStateEntryTable[state];
98 396475 : unsigned NextStateInTable = DFAStateEntryTable[state+1];
99 : // Early exit in case CachedTable has already contains this
100 : // state's transitions.
101 450750 : if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0])))
102 342200 : return;
103 :
104 1303184 : for (unsigned i = ThisState; i < NextStateInTable; i++)
105 1248909 : CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] =
106 1248909 : DFAStateInputTable[i][1];
107 : }
108 :
109 : // Return the DFAInput for an instruction class.
110 396475 : DFAInput DFAPacketizer::getInsnInput(unsigned InsnClass) {
111 : // Note: this logic must match that in DFAPacketizerDefs.h for input vectors.
112 : DFAInput InsnInput = 0;
113 : unsigned i = 0;
114 : (void)i;
115 396475 : for (const InstrStage *IS = InstrItins->beginStage(InsnClass),
116 896539 : *IE = InstrItins->endStage(InsnClass); IS != IE; ++IS) {
117 500064 : InsnInput = addDFAFuncUnits(InsnInput, IS->getUnits());
118 : assert((i++ < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs");
119 : }
120 396475 : return InsnInput;
121 : }
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 : }
127 :
128 : // Check if the resources occupied by a MCInstrDesc are available in the
129 : // current state.
130 260578 : bool DFAPacketizer::canReserveResources(const MCInstrDesc *MID) {
131 260578 : unsigned InsnClass = MID->getSchedClass();
132 260578 : DFAInput InsnInput = getInsnInput(InsnClass);
133 : UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
134 260578 : ReadTable(CurrentState);
135 260578 : return CachedTable.count(StateTrans) != 0;
136 : }
137 :
138 : // Reserve the resources occupied by a MCInstrDesc and change the current
139 : // state to reflect that change.
140 135897 : void DFAPacketizer::reserveResources(const MCInstrDesc *MID) {
141 135897 : unsigned InsnClass = MID->getSchedClass();
142 135897 : DFAInput InsnInput = getInsnInput(InsnClass);
143 : UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
144 135897 : ReadTable(CurrentState);
145 : assert(CachedTable.count(StateTrans) != 0);
146 135897 : CurrentState = CachedTable[StateTrans];
147 135897 : }
148 :
149 : // Check if the resources occupied by a machine instruction are available
150 : // in the current state.
151 260578 : bool DFAPacketizer::canReserveResources(MachineInstr &MI) {
152 260578 : const MCInstrDesc &MID = MI.getDesc();
153 260578 : return canReserveResources(&MID);
154 : }
155 :
156 : // Reserve the resources occupied by a machine instruction and change the
157 : // current state to reflect that change.
158 135897 : void DFAPacketizer::reserveResources(MachineInstr &MI) {
159 135897 : const MCInstrDesc &MID = MI.getDesc();
160 135897 : reserveResources(&MID);
161 135897 : }
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 : void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
182 14754 : Mutations.push_back(std::move(Mutation));
183 : }
184 :
185 : protected:
186 : void postprocessDAG();
187 : };
188 :
189 : } // end namespace llvm
190 :
191 7215 : DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF,
192 : MachineLoopInfo &MLI,
193 7215 : AliasAnalysis *AA)
194 7215 : : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
195 7215 : CanHandleTerminators = true;
196 7215 : }
197 :
198 : /// Apply each ScheduleDAGMutation step in order.
199 8606 : void DefaultVLIWScheduler::postprocessDAG() {
200 27815 : for (auto &M : Mutations)
201 19209 : M->apply(this);
202 8606 : }
203 :
204 8606 : void DefaultVLIWScheduler::schedule() {
205 : // Build the scheduling graph.
206 8606 : buildSchedGraph(AA);
207 8606 : postprocessDAG();
208 8606 : }
209 :
210 7215 : VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf,
211 7215 : MachineLoopInfo &mli, AliasAnalysis *aa)
212 7215 : : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
213 7215 : ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget());
214 7215 : VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA);
215 7215 : }
216 :
217 14430 : VLIWPacketizerList::~VLIWPacketizerList() {
218 7215 : delete VLIWScheduler;
219 14430 : delete ResourceTracker;
220 7215 : }
221 0 :
222 : // End the current packet, bundle packet instructions and reset DFA state.
223 : void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB,
224 0 : MachineBasicBlock::iterator MI) {
225 14430 : LLVM_DEBUG({
226 7215 : if (!CurrentPacketMIs.empty()) {
227 14430 : dbgs() << "Finalizing packet:\n";
228 7215 : for (MachineInstr *MI : CurrentPacketMIs)
229 : dbgs() << " * " << *MI;
230 : }
231 36042 : });
232 : if (CurrentPacketMIs.size() > 1) {
233 : MachineInstr &MIFirst = *CurrentPacketMIs.front();
234 : finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());
235 : }
236 : CurrentPacketMIs.clear();
237 : ResourceTracker->clearResources();
238 : LLVM_DEBUG(dbgs() << "End packet\n");
239 : }
240 72084 :
241 13651 : // Bundle machine instructions into packets.
242 13651 : void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB,
243 : MachineBasicBlock::iterator BeginItr,
244 : MachineBasicBlock::iterator EndItr) {
245 36042 : assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
246 : VLIWScheduler->startBlock(MBB);
247 36042 : VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,
248 : std::distance(BeginItr, EndItr));
249 : VLIWScheduler->schedule();
250 8606 :
251 : LLVM_DEBUG({
252 : dbgs() << "Scheduling DAG of the packetize region\n";
253 : VLIWScheduler->dump();
254 8606 : });
255 8606 :
256 8606 : // Generate MI -> SU map.
257 8606 : MIToSUnit.clear();
258 : for (SUnit &SU : VLIWScheduler->SUnits)
259 : MIToSUnit[SU.getInstr()] = &SU;
260 :
261 : bool LimitPresent = InstrLimit.getPosition();
262 :
263 : // The main packetizer loop.
264 : for (; BeginItr != EndItr; ++BeginItr) {
265 8606 : if (LimitPresent) {
266 109980 : if (InstrCount >= InstrLimit) {
267 101374 : EndItr = BeginItr;
268 : break;
269 8606 : }
270 : InstrCount++;
271 : }
272 109989 : MachineInstr &MI = *BeginItr;
273 101383 : initPacketizerState();
274 0 :
275 : // End the current packet if needed.
276 : if (isSoloInstruction(MI)) {
277 : endPacket(MBB, MI);
278 0 : continue;
279 : }
280 :
281 101383 : // Ignore pseudo instructions.
282 : if (ignorePseudoInstruction(MI, MBB))
283 : continue;
284 101383 :
285 30366 : SUnit *SUI = MIToSUnit[&MI];
286 15183 : assert(SUI && "Missing SUnit Info!");
287 :
288 : // Ask DFA if machine resource is available for MI.
289 : LLVM_DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);
290 86200 :
291 : bool ResourceAvail = ResourceTracker->canReserveResources(MI);
292 : LLVM_DEBUG({
293 86179 : if (ResourceAvail)
294 : dbgs() << " Resources are available for adding MI to packet\n";
295 : else
296 : dbgs() << " Resources NOT available\n";
297 : });
298 : if (ResourceAvail && shouldAddToPacket(MI)) {
299 86179 : // Dependency check for MI with instructions in CurrentPacketMIs.
300 : for (auto MJ : CurrentPacketMIs) {
301 : SUnit *SUJ = MIToSUnit[MJ];
302 : assert(SUJ && "Missing SUnit Info!");
303 :
304 : LLVM_DEBUG(dbgs() << " Checking against MJ " << *MJ);
305 : // Is it legal to packetize SUI and SUJ together.
306 86179 : if (!isLegalToPacketizeTogether(SUI, SUJ)) {
307 : LLVM_DEBUG(dbgs() << " Not legal to add MI, try to prune\n");
308 136293 : // Allow packetization if dependency can be pruned.
309 78017 : if (!isLegalToPruneDependencies(SUI, SUJ)) {
310 : // End the packet if dependency cannot be pruned.
311 : LLVM_DEBUG(dbgs()
312 : << " Could not prune dependencies for adding MI\n");
313 : endPacket(MBB, MI);
314 78017 : break;
315 : }
316 : LLVM_DEBUG(dbgs() << " Pruned dependence for adding MI\n");
317 11235 : }
318 : }
319 : } else {
320 : LLVM_DEBUG(if (ResourceAvail) dbgs()
321 22466 : << "Resources are available, but instruction should not be "
322 11233 : "added to packet\n "
323 : << MI);
324 : // End the packet if resource is not available, or if the instruction
325 : // shoud not be added to the current packet.
326 : endPacket(MBB, MI);
327 : }
328 :
329 : // Add MI to the current packet.
330 : LLVM_DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');
331 : BeginItr = addToPacket(MI);
332 : } // For all instructions in the packetization range.
333 :
334 33340 : // End any packet left behind.
335 : endPacket(MBB, EndItr);
336 : VLIWScheduler->exitRegion();
337 : VLIWScheduler->finishBlock();
338 : }
339 86179 :
340 : bool VLIWPacketizerList::alias(const MachineMemOperand &Op1,
341 : const MachineMemOperand &Op2,
342 : bool UseTBAA) const {
343 8606 : if (!Op1.getValue() || !Op2.getValue())
344 8606 : return true;
345 8606 :
346 8606 : int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
347 : int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset;
348 156 : int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset;
349 :
350 : AliasResult AAResult =
351 267 : AA->alias(MemoryLocation(Op1.getValue(), Overlapa,
352 : UseTBAA ? Op1.getAAInfo() : AAMDNodes()),
353 : MemoryLocation(Op2.getValue(), Overlapb,
354 130 : UseTBAA ? Op2.getAAInfo() : AAMDNodes()));
355 130 :
356 130 : return AAResult != NoAlias;
357 : }
358 :
359 130 : bool VLIWPacketizerList::alias(const MachineInstr &MI1,
360 130 : const MachineInstr &MI2,
361 130 : bool UseTBAA) const {
362 130 : if (MI1.memoperands_empty() || MI2.memoperands_empty())
363 : return true;
364 130 :
365 : for (const MachineMemOperand *Op1 : MI1.memoperands())
366 : for (const MachineMemOperand *Op2 : MI2.memoperands())
367 178 : if (alias(*Op1, *Op2, UseTBAA))
368 : return true;
369 : return false;
370 349 : }
371 22 :
372 : // Add a DAG mutation object to the ordered list.
373 245 : void VLIWPacketizerList::addMutation(
374 245 : std::unique_ptr<ScheduleDAGMutation> Mutation) {
375 156 : VLIWScheduler->addMutation(std::move(Mutation));
376 : }
|
