1 //===---- ScheduleDAGInstrs.cpp - MachineInstr Rescheduling ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the ScheduleDAGInstrs class, which implements re-scheduling
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "sched-instrs"
16 #include "llvm/CodeGen/MachineDominators.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
20 #include "llvm/CodeGen/PseudoSourceValue.h"
21 #include "llvm/Target/TargetMachine.h"
22 #include "llvm/Target/TargetInstrInfo.h"
23 #include "llvm/Target/TargetRegisterInfo.h"
24 #include "llvm/Target/TargetSubtarget.h"
25 #include "llvm/Support/Compiler.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/ADT/SmallSet.h"
32 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineBasicBlock *bb,
33 const TargetMachine &tm,
34 const MachineLoopInfo &mli,
35 const MachineDominatorTree &mdt)
36 : ScheduleDAG(0, bb, tm), MLI(mli), MDT(mdt) {}
38 void ScheduleDAGInstrs::BuildSchedUnits() {
40 SUnits.reserve(BB->size());
42 // We build scheduling units by walking a block's instruction list from bottom
45 // Remember where defs and uses of each physical register are as we procede.
46 std::vector<SUnit *> Defs[TargetRegisterInfo::FirstVirtualRegister] = {};
47 std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister] = {};
49 // Remember where unknown loads are after the most recent unknown store
51 std::vector<SUnit *> PendingLoads;
53 // Remember where a generic side-effecting instruction is as we procede. If
54 // ChainMMO is null, this is assumed to have arbitrary side-effects. If
55 // ChainMMO is non-null, then Chain makes only a single memory reference.
57 MachineMemOperand *ChainMMO = 0;
59 // Memory references to specific known memory locations are tracked so that
60 // they can be given more precise dependencies.
61 std::map<const Value *, SUnit *> MemDefs;
62 std::map<const Value *, std::vector<SUnit *> > MemUses;
64 // Terminators can perform control transfers, we we need to make sure that
65 // all the work of the block is done before the terminator.
66 SUnit *Terminator = 0;
68 // Check to see if the scheduler cares about latencies.
69 bool UnitLatencies = ForceUnitLatencies();
71 for (MachineBasicBlock::iterator MII = BB->end(), MIE = BB->begin();
73 MachineInstr *MI = prior(MII);
74 const TargetInstrDesc &TID = MI->getDesc();
75 SUnit *SU = NewSUnit(MI);
77 // Assign the Latency field of SU using target-provided information.
83 // Add register-based dependencies (data, anti, and output).
84 for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
85 const MachineOperand &MO = MI->getOperand(j);
86 if (!MO.isReg()) continue;
87 unsigned Reg = MO.getReg();
88 if (Reg == 0) continue;
90 assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
91 std::vector<SUnit *> &UseList = Uses[Reg];
92 std::vector<SUnit *> &DefList = Defs[Reg];
93 // Optionally add output and anti dependencies.
94 // TODO: Using a latency of 1 here assumes there's no cost for
96 SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
97 for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
98 SUnit *DefSU = DefList[i];
100 (Kind != SDep::Output || !MO.isDead() ||
101 !DefSU->getInstr()->registerDefIsDead(Reg)))
102 DefSU->addPred(SDep(SU, Kind, /*Latency=*/1, /*Reg=*/Reg));
104 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
105 std::vector<SUnit *> &DefList = Defs[*Alias];
106 for (unsigned i = 0, e = DefList.size(); i != e; ++i) {
107 SUnit *DefSU = DefList[i];
109 (Kind != SDep::Output || !MO.isDead() ||
110 !DefSU->getInstr()->registerDefIsDead(Reg)))
111 DefSU->addPred(SDep(SU, Kind, /*Latency=*/1, /*Reg=*/ *Alias));
116 // Add any data dependencies.
117 unsigned DataLatency = SU->Latency;
118 for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
119 SUnit *UseSU = UseList[i];
121 UseSU->addPred(SDep(SU, SDep::Data, DataLatency, Reg));
124 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
125 std::vector<SUnit *> &UseList = Uses[*Alias];
126 for (unsigned i = 0, e = UseList.size(); i != e; ++i) {
127 SUnit *UseSU = UseList[i];
129 UseSU->addPred(SDep(SU, SDep::Data, DataLatency, *Alias));
136 DefList.push_back(SU);
138 UseList.push_back(SU);
142 // Add chain dependencies.
143 // Note that isStoreToStackSlot and isLoadFromStackSLot are not usable
144 // after stack slots are lowered to actual addresses.
145 // TODO: Use an AliasAnalysis and do real alias-analysis queries, and
146 // produce more precise dependence information.
147 if (TID.isCall() || TID.isReturn() || TID.isBranch() ||
148 TID.hasUnmodeledSideEffects()) {
150 // This is the conservative case. Add dependencies on all memory
153 Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
155 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
156 PendingLoads[k]->addPred(SDep(SU, SDep::Order, SU->Latency));
157 PendingLoads.clear();
158 for (std::map<const Value *, SUnit *>::iterator I = MemDefs.begin(),
159 E = MemDefs.end(); I != E; ++I) {
160 I->second->addPred(SDep(SU, SDep::Order, SU->Latency));
163 for (std::map<const Value *, std::vector<SUnit *> >::iterator I =
164 MemUses.begin(), E = MemUses.end(); I != E; ++I) {
165 for (unsigned i = 0, e = I->second.size(); i != e; ++i)
166 I->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency));
169 // See if it is known to just have a single memory reference.
170 MachineInstr *ChainMI = Chain->getInstr();
171 const TargetInstrDesc &ChainTID = ChainMI->getDesc();
172 if (!ChainTID.isCall() && !ChainTID.isReturn() && !ChainTID.isBranch() &&
173 !ChainTID.hasUnmodeledSideEffects() &&
174 ChainMI->hasOneMemOperand() &&
175 !ChainMI->memoperands_begin()->isVolatile() &&
176 ChainMI->memoperands_begin()->getValue())
177 // We know that the Chain accesses one specific memory location.
178 ChainMMO = &*ChainMI->memoperands_begin();
180 // Unknown memory accesses. Assume the worst.
182 } else if (TID.mayStore()) {
183 if (MI->hasOneMemOperand() &&
184 MI->memoperands_begin()->getValue() &&
185 !MI->memoperands_begin()->isVolatile() &&
186 isa<PseudoSourceValue>(MI->memoperands_begin()->getValue())) {
187 // A store to a specific PseudoSourceValue. Add precise dependencies.
188 const Value *V = MI->memoperands_begin()->getValue();
189 // Handle the def in MemDefs, if there is one.
190 std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
191 if (I != MemDefs.end()) {
192 I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
193 /*isNormalMemory=*/true));
198 // Handle the uses in MemUses, if there are any.
199 std::map<const Value *, std::vector<SUnit *> >::iterator J =
201 if (J != MemUses.end()) {
202 for (unsigned i = 0, e = J->second.size(); i != e; ++i)
203 J->second[i]->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
204 /*isNormalMemory=*/true));
207 // Add a general dependence too, if needed.
209 Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
211 // Treat all other stores conservatively.
213 } else if (TID.mayLoad()) {
214 if (TII->isInvariantLoad(MI)) {
215 // Invariant load, no chain dependencies needed!
216 } else if (MI->hasOneMemOperand() &&
217 MI->memoperands_begin()->getValue() &&
218 !MI->memoperands_begin()->isVolatile() &&
219 isa<PseudoSourceValue>(MI->memoperands_begin()->getValue())) {
220 // A load from a specific PseudoSourceValue. Add precise dependencies.
221 const Value *V = MI->memoperands_begin()->getValue();
222 std::map<const Value *, SUnit *>::iterator I = MemDefs.find(V);
223 if (I != MemDefs.end())
224 I->second->addPred(SDep(SU, SDep::Order, SU->Latency, /*Reg=*/0,
225 /*isNormalMemory=*/true));
226 MemUses[V].push_back(SU);
228 // Add a general dependence too, if needed.
229 if (Chain && (!ChainMMO ||
230 (ChainMMO->isStore() || ChainMMO->isVolatile())))
231 Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
232 } else if (MI->hasVolatileMemoryRef()) {
233 // Treat volatile loads conservatively. Note that this includes
234 // cases where memoperand information is unavailable.
237 // A normal load. Just depend on the general chain.
239 Chain->addPred(SDep(SU, SDep::Order, SU->Latency));
240 PendingLoads.push_back(SU);
244 // Add chain edges from the terminator to ensure that all the work of the
245 // block is completed before any control transfers.
246 if (Terminator && SU->Succs.empty())
247 Terminator->addPred(SDep(SU, SDep::Order, SU->Latency));
248 if (TID.isTerminator() || MI->isLabel())
253 void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) {
254 const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
256 // Compute the latency for the node. We use the sum of the latencies for
257 // all nodes flagged together into this SUnit.
259 InstrItins.getLatency(SU->getInstr()->getDesc().getSchedClass());
261 // Simplistic target-independent heuristic: assume that loads take
263 if (InstrItins.isEmpty())
264 if (SU->getInstr()->getDesc().mayLoad())
268 void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
269 SU->getInstr()->dump();
272 std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
274 raw_string_ostream oss(s);
275 SU->getInstr()->print(oss);
279 // EmitSchedule - Emit the machine code in scheduled order.
280 MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() {
281 // For MachineInstr-based scheduling, we're rescheduling the instructions in
282 // the block, so start by removing them from the block.
284 BB->remove(BB->begin());
286 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
287 SUnit *SU = Sequence[i];
289 // Null SUnit* is a noop.
294 BB->push_back(SU->getInstr());