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