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