1 //===-- MachineLICM.cpp - Machine Loop Invariant Code Motion Pass ---------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Bill Wendling and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass performs loop invariant code motion on machine instructions. We
11 // attempt to remove as much code from the body of a loop as possible.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "machine-licm"
16 #include "llvm/ADT/IndexedMap.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/CodeGen/MachineBasicBlock.h"
20 #include "llvm/CodeGen/MachineDominators.h"
21 #include "llvm/CodeGen/MachineInstr.h"
22 #include "llvm/CodeGen/MachineLoopInfo.h"
23 #include "llvm/CodeGen/Passes.h"
24 #include "llvm/Support/CFG.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/Compiler.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Target/MRegisterInfo.h"
29 #include "llvm/Target/TargetInstrInfo.h"
30 #include "llvm/Target/TargetMachine.h"
35 // Hidden options to help debugging
37 PerformLICM("machine-licm",
38 cl::init(false), cl::Hidden,
39 cl::desc("Perform loop-invariant code motion on machine code"));
42 STATISTIC(NumHoisted, "Number of machine instructions hoisted out of loops");
45 class VISIBILITY_HIDDEN MachineLICM : public MachineFunctionPass {
46 const TargetInstrInfo *TII;
47 MachineFunction *CurMF; // Current MachineFunction
49 // Various analyses that we use...
50 MachineLoopInfo *LI; // Current MachineLoopInfo
51 MachineDominatorTree *DT; // Machine dominator tree for the current Loop
53 // State that is updated as we process loops
54 bool Changed; // True if a loop is changed.
55 MachineLoop *CurLoop; // The current loop we are working on.
57 // Map the def of a virtual register to the machine instruction.
58 IndexedMap<const MachineInstr*, VirtReg2IndexFunctor> VRegDefs;
60 static char ID; // Pass identification, replacement for typeid
61 MachineLICM() : MachineFunctionPass((intptr_t)&ID) {}
63 virtual bool runOnMachineFunction(MachineFunction &MF);
65 /// FIXME: Loop preheaders?
67 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
69 AU.addRequired<MachineLoopInfo>();
70 AU.addRequired<MachineDominatorTree>();
73 /// VisitAllLoops - Visit all of the loops in depth first order and try to
74 /// hoist invariant instructions from them.
76 void VisitAllLoops(MachineLoop *L) {
77 const std::vector<MachineLoop*> &SubLoops = L->getSubLoops();
79 for (MachineLoop::iterator
80 I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I) {
83 // Traverse the body of the loop in depth first order on the dominator
84 // tree so that we are guaranteed to see definitions before we see uses.
86 HoistRegion(DT->getNode(ML->getHeader()));
89 HoistRegion(DT->getNode(L->getHeader()));
92 /// MapVirtualRegisterDefs - Create a map of which machine instruction
93 /// defines a virtual register.
95 void MapVirtualRegisterDefs();
97 /// IsInSubLoop - A little predicate that returns true if the specified
98 /// basic block is in a subloop of the current one, not the current one
101 bool IsInSubLoop(MachineBasicBlock *BB) {
102 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
103 return LI->getLoopFor(BB) != CurLoop;
106 /// IsLoopInvariantInst - Returns true if the instruction is loop
107 /// invariant. I.e., all virtual register operands are defined outside of
108 /// the loop, physical registers aren't accessed (explicitly or implicitly),
109 /// and the instruction is hoistable.
111 bool IsLoopInvariantInst(MachineInstr &I);
113 /// FindPredecessors - Get all of the predecessors of the loop that are not
116 void FindPredecessors(std::vector<MachineBasicBlock*> &Preds) {
117 const MachineBasicBlock *Header = CurLoop->getHeader();
119 for (MachineBasicBlock::const_pred_iterator
120 I = Header->pred_begin(), E = Header->pred_end(); I != E; ++I)
121 if (!CurLoop->contains(*I))
125 /// MoveInstToEndOfBlock - Moves the machine instruction to the bottom of
126 /// the predecessor basic block (but before the terminator instructions).
128 void MoveInstToEndOfBlock(MachineBasicBlock *MBB, MachineInstr *MI) {
130 DOUT << "Hoisting " << *MI;
131 if (MBB->getBasicBlock())
132 DOUT << " to MachineBasicBlock "
133 << MBB->getBasicBlock()->getName();
136 MachineBasicBlock::iterator Iter = MBB->getFirstTerminator();
137 MBB->insert(Iter, MI);
141 /// HoistRegion - Walk the specified region of the CFG (defined by all
142 /// blocks dominated by the specified block, and that are in the current
143 /// loop) in depth first order w.r.t the DominatorTree. This allows us to
144 /// visit definitions before uses, allowing us to hoist a loop body in one
145 /// pass without iteration.
147 void HoistRegion(MachineDomTreeNode *N);
149 /// Hoist - When an instruction is found to only use loop invariant operands
150 /// that is safe to hoist, this instruction is called to do the dirty work.
152 void Hoist(MachineInstr &MI);
155 char MachineLICM::ID = 0;
156 RegisterPass<MachineLICM> X("machine-licm",
157 "Machine Loop Invariant Code Motion");
158 } // end anonymous namespace
160 FunctionPass *llvm::createMachineLICMPass() { return new MachineLICM(); }
162 /// Hoist expressions out of the specified loop. Note, alias info for inner loop
163 /// is not preserved so it is not a good idea to run LICM multiple times on one
166 bool MachineLICM::runOnMachineFunction(MachineFunction &MF) {
167 if (!PerformLICM) return false; // For debugging.
169 DOUT << "******** Machine LICM ********\n";
173 TII = CurMF->getTarget().getInstrInfo();
175 // Get our Loop information...
176 LI = &getAnalysis<MachineLoopInfo>();
177 DT = &getAnalysis<MachineDominatorTree>();
179 MapVirtualRegisterDefs();
181 for (MachineLoopInfo::iterator
182 I = LI->begin(), E = LI->end(); I != E; ++I) {
185 // Visit all of the instructions of the loop. We want to visit the subloops
186 // first, though, so that we can hoist their invariants first into their
187 // containing loop before we process that loop.
188 VisitAllLoops(CurLoop);
194 /// MapVirtualRegisterDefs - Create a map of which machine instruction defines a
195 /// virtual register.
197 void MachineLICM::MapVirtualRegisterDefs() {
198 for (MachineFunction::const_iterator
199 I = CurMF->begin(), E = CurMF->end(); I != E; ++I) {
200 const MachineBasicBlock &MBB = *I;
202 for (MachineBasicBlock::const_iterator
203 II = MBB.begin(), IE = MBB.end(); II != IE; ++II) {
204 const MachineInstr &MI = *II;
206 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
207 const MachineOperand &MO = MI.getOperand(i);
209 if (MO.isRegister() && MO.isDef() &&
210 MRegisterInfo::isVirtualRegister(MO.getReg())) {
211 VRegDefs.grow(MO.getReg());
212 VRegDefs[MO.getReg()] = &MI;
219 /// HoistRegion - Walk the specified region of the CFG (defined by all blocks
220 /// dominated by the specified block, and that are in the current loop) in depth
221 /// first order w.r.t the DominatorTree. This allows us to visit definitions
222 /// before uses, allowing us to hoist a loop body in one pass without iteration.
224 void MachineLICM::HoistRegion(MachineDomTreeNode *N) {
225 assert(N != 0 && "Null dominator tree node?");
226 MachineBasicBlock *BB = N->getBlock();
228 // If this subregion is not in the top level loop at all, exit.
229 if (!CurLoop->contains(BB)) return;
231 // Only need to process the contents of this block if it is not part of a
232 // subloop (which would already have been processed).
233 if (!IsInSubLoop(BB))
234 for (MachineBasicBlock::iterator
235 I = BB->begin(), E = BB->end(); I != E; ) {
236 MachineInstr &MI = *I++;
238 // Try hoisting the instruction out of the loop. We can only do this if
239 // all of the operands of the instruction are loop invariant and if it is
240 // safe to hoist the instruction.
244 const std::vector<MachineDomTreeNode*> &Children = N->getChildren();
246 for (unsigned I = 0, E = Children.size(); I != E; ++I)
247 HoistRegion(Children[I]);
250 /// IsLoopInvariantInst - Returns true if the instruction is loop
251 /// invariant. I.e., all virtual register operands are defined outside of the
252 /// loop, physical registers aren't accessed (explicitly or implicitly), and the
253 /// instruction is hoistable.
255 bool MachineLICM::IsLoopInvariantInst(MachineInstr &I) {
257 DOUT << "--- Checking if we can hoist " << I;
258 if (I.getInstrDescriptor()->ImplicitUses) {
259 DOUT << " * Instruction has implicit uses:\n";
261 const TargetMachine &TM = CurMF->getTarget();
262 const MRegisterInfo *MRI = TM.getRegisterInfo();
263 const unsigned *ImpUses = I.getInstrDescriptor()->ImplicitUses;
265 for (; *ImpUses; ++ImpUses)
266 DOUT << " -> " << MRI->getName(*ImpUses) << "\n";
269 if (I.getInstrDescriptor()->ImplicitDefs) {
270 DOUT << " * Instruction has implicit defines:\n";
272 const TargetMachine &TM = CurMF->getTarget();
273 const MRegisterInfo *MRI = TM.getRegisterInfo();
274 const unsigned *ImpDefs = I.getInstrDescriptor()->ImplicitDefs;
276 for (; *ImpDefs; ++ImpDefs)
277 DOUT << " -> " << MRI->getName(*ImpDefs) << "\n";
280 if (TII->hasUnmodelledSideEffects(&I))
281 DOUT << " * Instruction has side effects.\n";
285 // FIXME: Don't hoist if this instruction implicitly reads physical registers.
286 if (I.getInstrDescriptor()->ImplicitUses ||
287 I.getInstrDescriptor()->ImplicitDefs)
291 // The instruction is loop invariant if all of its operands are loop-invariant
292 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
293 const MachineOperand &MO = I.getOperand(i);
295 if (!(MO.isRegister() && MO.getReg() && MO.isUse()))
298 unsigned Reg = MO.getReg();
300 // Don't hoist instructions that access physical registers.
301 if (!MRegisterInfo::isVirtualRegister(Reg))
304 assert(VRegDefs[Reg] && "Machine instr not mapped for this vreg?");
306 // If the loop contains the definition of an operand, then the instruction
307 // isn't loop invariant.
308 if (CurLoop->contains(VRegDefs[Reg]->getParent()))
312 // Don't hoist something that has side effects.
313 if (TII->hasUnmodelledSideEffects(&I)) return false;
315 // If we got this far, the instruction is loop invariant!
319 /// Hoist - When an instruction is found to only use loop invariant operands
320 /// that is safe to hoist, this instruction is called to do the dirty work.
322 void MachineLICM::Hoist(MachineInstr &MI) {
323 if (!IsLoopInvariantInst(MI)) return;
325 std::vector<MachineBasicBlock*> Preds;
327 // Non-back-edge predecessors.
328 FindPredecessors(Preds);
330 // Either we don't have any predecessors(?!) or we have more than one, which
332 if (Preds.empty() || Preds.size() != 1) return;
334 // Check that the predecessor is qualified to take the hoisted
335 // instruction. I.e., there is only one edge from the predecessor, and it's to
337 MachineBasicBlock *MBB = Preds.front();
339 // FIXME: We are assuming at first that the basic block coming into this loop
340 // has only one successor. This isn't the case in general because we haven't
341 // broken critical edges or added preheaders.
342 if (MBB->succ_size() != 1) return;
343 assert(*MBB->succ_begin() == CurLoop->getHeader() &&
344 "The predecessor doesn't feed directly into the loop header!");
346 // Now move the instructions to the predecessor.
347 MachineInstr *NewMI = MI.clone();
348 MoveInstToEndOfBlock(MBB, NewMI);
351 for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {
352 const MachineOperand &MO = NewMI->getOperand(i);
354 if (MO.isRegister() && MO.isDef() &&
355 MRegisterInfo::isVirtualRegister(MO.getReg())) {
356 VRegDefs.grow(MO.getReg());
357 VRegDefs[MO.getReg()] = NewMI;
361 // Hoisting was successful! Remove bothersome instruction now.
362 MI.getParent()->remove(&MI);