LICM.cpp revision a6275ccdf5e1aa208afde56c498e2b13e16442f0
1//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// 2// 3// This pass is a simple loop invariant code motion pass. 4// 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. 11// 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 14// REQUIRE it. :) 15// 16//===----------------------------------------------------------------------===// 17 18#include "llvm/Transforms/Scalar.h" 19#include "llvm/Transforms/Utils/Local.h" 20#include "llvm/Analysis/LoopInfo.h" 21#include "llvm/iOperators.h" 22#include "llvm/iPHINode.h" 23#include "llvm/Support/InstVisitor.h" 24#include "llvm/Support/CFG.h" 25#include "Support/STLExtras.h" 26#include "Support/StatisticReporter.h" 27#include <algorithm> 28using std::string; 29 30static Statistic<> NumHoistedNPH("licm\t\t- Number of insts hoisted to multiple" 31 " loop preds (bad, no loop pre-header)"); 32static Statistic<> NumHoistedPH("licm\t\t- Number of insts hoisted to a loop " 33 "pre-header"); 34 35namespace { 36 struct LICM : public FunctionPass, public InstVisitor<LICM> { 37 virtual bool runOnFunction(Function &F); 38 39 // This transformation requires natural loop information... 40 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 41 AU.preservesCFG(); 42 AU.addRequired(LoopInfo::ID); 43 } 44 45 private: 46 // List of predecessor blocks for the current loop - These blocks are where 47 // we hoist loop invariants to for the current loop. 48 // 49 std::vector<BasicBlock*> LoopPreds, LoopBackEdges; 50 51 Loop *CurLoop; // The current loop we are working on... 52 bool Changed; // Set to true when we change anything. 53 54 // visitLoop - Hoist expressions out of the specified loop... 55 void visitLoop(Loop *L); 56 57 // notInCurrentLoop - Little predicate that returns true if the specified 58 // basic block is in a subloop of the current one, not the current one 59 // itself. 60 // 61 bool notInCurrentLoop(BasicBlock *BB) { 62 for (unsigned i = 0, e = CurLoop->getSubLoops().size(); i != e; ++i) 63 if (CurLoop->getSubLoops()[i]->contains(BB)) 64 return true; // A subloop actually contains this block! 65 return false; 66 } 67 68 // hoist - When an instruction is found to only use loop invariant operands 69 // that is safe to hoist, this instruction is called to do the dirty work. 70 // 71 void hoist(Instruction &I); 72 73 // isLoopInvariant - Return true if the specified value is loop invariant 74 inline bool isLoopInvariant(Value *V) { 75 if (Instruction *I = dyn_cast<Instruction>(V)) 76 return !CurLoop->contains(I->getParent()); 77 return true; // All non-instructions are loop invariant 78 } 79 80 // visitBasicBlock - Run LICM on a particular block. 81 void visitBasicBlock(BasicBlock *BB); 82 83 // Instruction visitation handlers... these basically control whether or not 84 // the specified instruction types are hoisted. 85 // 86 friend class InstVisitor<LICM>; 87 void visitUnaryOperator(Instruction &I) { 88 if (isLoopInvariant(I.getOperand(0))) hoist(I); 89 } 90 void visitBinaryOperator(Instruction &I) { 91 if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1))) 92 hoist(I); 93 } 94 95 void visitCastInst(CastInst &I) { visitUnaryOperator((Instruction&)I); } 96 void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); } 97 98 void visitGetElementPtrInst(GetElementPtrInst &GEPI) { 99 Instruction &I = (Instruction&)GEPI; 100 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 101 if (!isLoopInvariant(I.getOperand(i))) return; 102 hoist(I); 103 } 104 }; 105 106 RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion"); 107} 108 109Pass *createLICMPass() { return new LICM(); } 110 111bool LICM::runOnFunction(Function &) { 112 // get our loop information... 113 const std::vector<Loop*> &TopLevelLoops = 114 getAnalysis<LoopInfo>().getTopLevelLoops(); 115 116 // Traverse loops in postorder, hoisting expressions out of the deepest loops 117 // first. 118 // 119 Changed = false; 120 std::for_each(TopLevelLoops.begin(), TopLevelLoops.end(), 121 bind_obj(this, &LICM::visitLoop)); 122 return Changed; 123} 124 125void LICM::visitLoop(Loop *L) { 126 // Recurse through all subloops before we process this loop... 127 std::for_each(L->getSubLoops().begin(), L->getSubLoops().end(), 128 bind_obj(this, &LICM::visitLoop)); 129 CurLoop = L; 130 131 // Calculate the set of predecessors for this loop. The predecessors for this 132 // loop are equal to the predecessors for the header node of the loop that are 133 // not themselves in the loop. 134 // 135 BasicBlock *Header = L->getHeader(); 136 137 // Calculate the sets of predecessors and backedges of the loop... 138 LoopBackEdges.insert(LoopBackEdges.end(),pred_begin(Header),pred_end(Header)); 139 140 std::vector<BasicBlock*>::iterator LPI = 141 std::partition(LoopBackEdges.begin(), LoopBackEdges.end(), 142 bind_obj(CurLoop, &Loop::contains)); 143 144 // Move all predecessors to the LoopPreds vector... 145 LoopPreds.insert(LoopPreds.end(), LPI, LoopBackEdges.end()); 146 147 // Remove predecessors from backedges list... 148 LoopBackEdges.erase(LPI, LoopBackEdges.end()); 149 150 151 // The only way that there could be no predecessors to a loop is if the loop 152 // is not reachable. Since we don't care about optimizing dead loops, 153 // summarily ignore them. 154 // 155 if (LoopPreds.empty()) return; 156 157 // We want to visit all of the instructions in this loop... that are not parts 158 // of our subloops (they have already had their invariants hoisted out of 159 // their loop, into this loop, so there is no need to process the BODIES of 160 // the subloops). 161 // 162 std::vector<BasicBlock*> BBs(L->getBlocks().begin(), L->getBlocks().end()); 163 164 // Remove blocks that are actually in subloops... 165 BBs.erase(std::remove_if(BBs.begin(), BBs.end(), 166 bind_obj(this, &LICM::notInCurrentLoop)), BBs.end()); 167 168 // Visit all of the basic blocks we have chosen, hoisting out the instructions 169 // as neccesary. This leaves dead copies of the instruction in the loop 170 // unfortunately... 171 // 172 for_each(BBs.begin(), BBs.end(), bind_obj(this, &LICM::visitBasicBlock)); 173 174 // Clear out loops state information for the next iteration 175 CurLoop = 0; 176 LoopPreds.clear(); 177 LoopBackEdges.clear(); 178} 179 180void LICM::visitBasicBlock(BasicBlock *BB) { 181 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 182 visit(*I); 183 184 if (dceInstruction(I)) 185 Changed = true; 186 else 187 ++I; 188 } 189} 190 191 192void LICM::hoist(Instruction &Inst) { 193 if (Inst.use_empty()) return; // Don't (re) hoist dead instructions! 194 //cerr << "Hoisting " << Inst; 195 196 BasicBlock *Header = CurLoop->getHeader(); 197 198 // Old instruction will be removed, so take it's name... 199 string InstName = Inst.getName(); 200 Inst.setName(""); 201 202 // The common case is that we have a pre-header. Generate special case code 203 // that is faster if that is the case. 204 // 205 if (LoopPreds.size() == 1) { 206 BasicBlock *Pred = LoopPreds[0]; 207 208 // Create a new copy of the instruction, for insertion into Pred. 209 Instruction *New = Inst.clone(); 210 New->setName(InstName); 211 212 // Insert the new node in Pred, before the terminator. 213 Pred->getInstList().insert(--Pred->end(), New); 214 215 // Kill the old instruction... 216 Inst.replaceAllUsesWith(New); 217 ++NumHoistedPH; 218 219 } else { 220 // No loop pre-header, insert a PHI node into header to capture all of the 221 // incoming versions of the value. 222 // 223 PHINode *LoopVal = new PHINode(Inst.getType(), InstName+".phi"); 224 225 // Insert the new PHI node into the loop header... 226 Header->getInstList().push_front(LoopVal); 227 228 // Insert cloned versions of the instruction into all of the loop preds. 229 for (unsigned i = 0, e = LoopPreds.size(); i != e; ++i) { 230 BasicBlock *Pred = LoopPreds[i]; 231 232 // Create a new copy of the instruction, for insertion into Pred. 233 Instruction *New = Inst.clone(); 234 New->setName(InstName); 235 236 // Insert the new node in Pred, before the terminator. 237 Pred->getInstList().insert(--Pred->end(), New); 238 239 // Add the incoming value to the PHI node. 240 LoopVal->addIncoming(New, Pred); 241 } 242 243 // Add incoming values to the PHI node for all backedges in the loop... 244 for (unsigned i = 0, e = LoopBackEdges.size(); i != e; ++i) 245 LoopVal->addIncoming(LoopVal, LoopBackEdges[i]); 246 247 // Replace all uses of the old version of the instruction in the loop with 248 // the new version that is out of the loop. We know that this is ok, 249 // because the new definition is in the loop header, which dominates the 250 // entire loop body. The old definition was defined _inside_ of the loop, 251 // so the scope cannot extend outside of the loop, so we're ok. 252 // 253 Inst.replaceAllUsesWith(LoopVal); 254 ++NumHoistedNPH; 255 } 256 257 Changed = true; 258} 259 260