1 //===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
3 // This pass is a simple loop invariant code motion pass.
5 // Note that this pass does NOT require pre-headers to exist on loops in the
6 // CFG, but if there is not distinct preheader for a loop, the hoisted code will
7 // be *DUPLICATED* in every basic block, outside of the loop, that preceeds the
8 // loop header. Additionally, any use of one of these hoisted expressions
9 // cannot be loop invariant itself, because the expression hoisted gets a PHI
10 // node that is loop variant.
12 // For these reasons, and many more, it makes sense to run a pass before this
13 // that ensures that there are preheaders on all loops. That said, we don't
16 //===----------------------------------------------------------------------===//
18 #include "llvm/Transforms/Scalar.h"
19 #include "llvm/Transforms/Utils/Local.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/AliasAnalysis.h"
22 #include "llvm/iOperators.h"
23 #include "llvm/iPHINode.h"
24 #include "llvm/iMemory.h"
25 #include "llvm/Support/InstVisitor.h"
26 #include "llvm/Support/CFG.h"
27 #include "Support/STLExtras.h"
28 #include "Support/StatisticReporter.h"
32 static Statistic<> NumHoistedNPH("licm\t\t- Number of insts hoisted to multiple"
33 " loop preds (bad, no loop pre-header)");
34 static Statistic<> NumHoistedPH("licm\t\t- Number of insts hoisted to a loop "
36 static Statistic<> NumHoistedLoads("licm\t\t- Number of load insts hoisted");
39 struct LICM : public FunctionPass, public InstVisitor<LICM> {
40 virtual bool runOnFunction(Function &F);
42 // This transformation requires natural loop information...
43 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
45 AU.addRequired<LoopInfo>();
46 AU.addRequired<AliasAnalysis>();
50 // List of predecessor blocks for the current loop - These blocks are where
51 // we hoist loop invariants to for the current loop.
53 std::vector<BasicBlock*> LoopPreds, LoopBackEdges;
55 Loop *CurLoop; // The current loop we are working on...
56 bool Changed; // Set to true when we change anything.
57 AliasAnalysis *AA; // Currently AliasAnalysis information
59 // visitLoop - Hoist expressions out of the specified loop...
60 void visitLoop(Loop *L);
62 // notInCurrentLoop - Little predicate that returns true if the specified
63 // basic block is in a subloop of the current one, not the current one
66 bool notInCurrentLoop(BasicBlock *BB) {
67 for (unsigned i = 0, e = CurLoop->getSubLoops().size(); i != e; ++i)
68 if (CurLoop->getSubLoops()[i]->contains(BB))
69 return true; // A subloop actually contains this block!
73 // hoist - When an instruction is found to only use loop invariant operands
74 // that is safe to hoist, this instruction is called to do the dirty work.
76 void hoist(Instruction &I);
78 // pointerInvalidatedByLoop - Return true if the body of this loop may store
79 // into the memory location pointed to by V.
81 bool pointerInvalidatedByLoop(Value *V);
83 // isLoopInvariant - Return true if the specified value is loop invariant
84 inline bool isLoopInvariant(Value *V) {
85 if (Instruction *I = dyn_cast<Instruction>(V))
86 return !CurLoop->contains(I->getParent());
87 return true; // All non-instructions are loop invariant
90 // visitBasicBlock - Run LICM on a particular block.
91 void visitBasicBlock(BasicBlock *BB);
93 // Instruction visitation handlers... these basically control whether or not
94 // the specified instruction types are hoisted.
96 friend class InstVisitor<LICM>;
97 void visitBinaryOperator(Instruction &I) {
98 if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1)))
101 void visitCastInst(CastInst &CI) {
102 Instruction &I = (Instruction&)CI;
103 if (isLoopInvariant(I.getOperand(0))) hoist(I);
105 void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); }
107 void visitLoadInst(LoadInst &LI) {
108 assert(!LI.hasIndices());
109 if (isLoopInvariant(LI.getOperand(0)) &&
110 !pointerInvalidatedByLoop(LI.getOperand(0)))
114 void visitGetElementPtrInst(GetElementPtrInst &GEPI) {
115 Instruction &I = (Instruction&)GEPI;
116 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
117 if (!isLoopInvariant(I.getOperand(i))) return;
122 RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion");
125 Pass *createLICMPass() { return new LICM(); }
127 bool LICM::runOnFunction(Function &) {
128 // get our loop information...
129 const std::vector<Loop*> &TopLevelLoops =
130 getAnalysis<LoopInfo>().getTopLevelLoops();
132 // Get our alias analysis information...
133 AA = &getAnalysis<AliasAnalysis>();
135 // Traverse loops in postorder, hoisting expressions out of the deepest loops
139 std::for_each(TopLevelLoops.begin(), TopLevelLoops.end(),
140 bind_obj(this, &LICM::visitLoop));
144 void LICM::visitLoop(Loop *L) {
145 // Recurse through all subloops before we process this loop...
146 std::for_each(L->getSubLoops().begin(), L->getSubLoops().end(),
147 bind_obj(this, &LICM::visitLoop));
150 // Calculate the set of predecessors for this loop. The predecessors for this
151 // loop are equal to the predecessors for the header node of the loop that are
152 // not themselves in the loop.
154 BasicBlock *Header = L->getHeader();
156 // Calculate the sets of predecessors and backedges of the loop...
157 LoopBackEdges.insert(LoopBackEdges.end(),pred_begin(Header),pred_end(Header));
159 std::vector<BasicBlock*>::iterator LPI =
160 std::partition(LoopBackEdges.begin(), LoopBackEdges.end(),
161 bind_obj(CurLoop, &Loop::contains));
163 // Move all predecessors to the LoopPreds vector...
164 LoopPreds.insert(LoopPreds.end(), LPI, LoopBackEdges.end());
166 // Remove predecessors from backedges list...
167 LoopBackEdges.erase(LPI, LoopBackEdges.end());
170 // The only way that there could be no predecessors to a loop is if the loop
171 // is not reachable. Since we don't care about optimizing dead loops,
172 // summarily ignore them.
174 if (LoopPreds.empty()) return;
176 // We want to visit all of the instructions in this loop... that are not parts
177 // of our subloops (they have already had their invariants hoisted out of
178 // their loop, into this loop, so there is no need to process the BODIES of
181 std::vector<BasicBlock*> BBs(L->getBlocks().begin(), L->getBlocks().end());
183 // Remove blocks that are actually in subloops...
184 BBs.erase(std::remove_if(BBs.begin(), BBs.end(),
185 bind_obj(this, &LICM::notInCurrentLoop)), BBs.end());
187 // Visit all of the basic blocks we have chosen, hoisting out the instructions
188 // as neccesary. This leaves dead copies of the instruction in the loop
191 for_each(BBs.begin(), BBs.end(), bind_obj(this, &LICM::visitBasicBlock));
193 // Clear out loops state information for the next iteration
196 LoopBackEdges.clear();
199 void LICM::visitBasicBlock(BasicBlock *BB) {
200 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
203 if (dceInstruction(I))
211 void LICM::hoist(Instruction &Inst) {
212 if (Inst.use_empty()) return; // Don't (re) hoist dead instructions!
213 //cerr << "Hoisting " << Inst;
215 BasicBlock *Header = CurLoop->getHeader();
217 // Old instruction will be removed, so take it's name...
218 string InstName = Inst.getName();
221 if (isa<LoadInst>(Inst))
224 // The common case is that we have a pre-header. Generate special case code
225 // that is faster if that is the case.
227 if (LoopPreds.size() == 1) {
228 BasicBlock *Pred = LoopPreds[0];
230 // Create a new copy of the instruction, for insertion into Pred.
231 Instruction *New = Inst.clone();
232 New->setName(InstName);
234 // Insert the new node in Pred, before the terminator.
235 Pred->getInstList().insert(--Pred->end(), New);
237 // Kill the old instruction...
238 Inst.replaceAllUsesWith(New);
242 // No loop pre-header, insert a PHI node into header to capture all of the
243 // incoming versions of the value.
245 PHINode *LoopVal = new PHINode(Inst.getType(), InstName+".phi");
247 // Insert the new PHI node into the loop header...
248 Header->getInstList().push_front(LoopVal);
250 // Insert cloned versions of the instruction into all of the loop preds.
251 for (unsigned i = 0, e = LoopPreds.size(); i != e; ++i) {
252 BasicBlock *Pred = LoopPreds[i];
254 // Create a new copy of the instruction, for insertion into Pred.
255 Instruction *New = Inst.clone();
256 New->setName(InstName);
258 // Insert the new node in Pred, before the terminator.
259 Pred->getInstList().insert(--Pred->end(), New);
261 // Add the incoming value to the PHI node.
262 LoopVal->addIncoming(New, Pred);
265 // Add incoming values to the PHI node for all backedges in the loop...
266 for (unsigned i = 0, e = LoopBackEdges.size(); i != e; ++i)
267 LoopVal->addIncoming(LoopVal, LoopBackEdges[i]);
269 // Replace all uses of the old version of the instruction in the loop with
270 // the new version that is out of the loop. We know that this is ok,
271 // because the new definition is in the loop header, which dominates the
272 // entire loop body. The old definition was defined _inside_ of the loop,
273 // so the scope cannot extend outside of the loop, so we're ok.
275 Inst.replaceAllUsesWith(LoopVal);
282 // pointerInvalidatedByLoop - Return true if the body of this loop may store
283 // into the memory location pointed to by V.
285 bool LICM::pointerInvalidatedByLoop(Value *V) {
286 // Check to see if any of the basic blocks in CurLoop invalidate V.
287 for (unsigned i = 0, e = CurLoop->getBlocks().size(); i != e; ++i)
288 if (AA->canBasicBlockModify(*CurLoop->getBlocks()[i], V))