LICM.cpp revision 99a57216a935a512c418032f590a4660bad9d846
1//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// 2// 3// This pass is a simple loop invariant code motion pass. 4// 5//===----------------------------------------------------------------------===// 6 7#include "llvm/Transforms/Scalar.h" 8#include "llvm/Transforms/Utils/Local.h" 9#include "llvm/Analysis/LoopInfo.h" 10#include "llvm/Analysis/AliasAnalysis.h" 11#include "llvm/iOperators.h" 12#include "llvm/iMemory.h" 13#include "llvm/Support/InstVisitor.h" 14#include "Support/STLExtras.h" 15#include "Support/StatisticReporter.h" 16#include <algorithm> 17using std::string; 18 19namespace { 20 Statistic<>NumHoisted("licm\t\t- Number of instructions hoisted out of loop"); 21 Statistic<> NumHoistedLoads("licm\t\t- Number of load insts hoisted"); 22 23 struct LICM : public FunctionPass, public InstVisitor<LICM> { 24 virtual bool runOnFunction(Function &F); 25 26 /// This transformation requires natural loop information & requires that 27 /// loop preheaders be inserted into the CFG... 28 /// 29 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 30 AU.preservesCFG(); 31 AU.addRequiredID(LoopPreheadersID); 32 AU.addRequired<LoopInfo>(); 33 AU.addRequired<AliasAnalysis>(); 34 } 35 36 private: 37 Loop *CurLoop; // The current loop we are working on... 38 BasicBlock *Preheader; // The preheader block of the current loop... 39 bool Changed; // Set to true when we change anything. 40 AliasAnalysis *AA; // Currently AliasAnalysis information 41 42 /// visitLoop - Hoist expressions out of the specified loop... 43 /// 44 void visitLoop(Loop *L); 45 46 /// inCurrentLoop - Little predicate that returns false if the specified 47 /// basic block is in a subloop of the current one, not the current one 48 /// itself. 49 /// 50 bool inCurrentLoop(BasicBlock *BB) { 51 for (unsigned i = 0, e = CurLoop->getSubLoops().size(); i != e; ++i) 52 if (CurLoop->getSubLoops()[i]->contains(BB)) 53 return false; // A subloop actually contains this block! 54 return true; 55 } 56 57 /// hoist - When an instruction is found to only use loop invariant operands 58 /// that is safe to hoist, this instruction is called to do the dirty work. 59 /// 60 void hoist(Instruction &I); 61 62 /// pointerInvalidatedByLoop - Return true if the body of this loop may 63 /// store into the memory location pointed to by V. 64 /// 65 bool pointerInvalidatedByLoop(Value *V); 66 67 /// isLoopInvariant - Return true if the specified value is loop invariant 68 /// 69 inline bool isLoopInvariant(Value *V) { 70 if (Instruction *I = dyn_cast<Instruction>(V)) 71 return !CurLoop->contains(I->getParent()); 72 return true; // All non-instructions are loop invariant 73 } 74 75 /// Instruction visitation handlers... these basically control whether or 76 /// not the specified instruction types are hoisted. 77 /// 78 friend class InstVisitor<LICM>; 79 void visitBinaryOperator(Instruction &I) { 80 if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1))) 81 hoist(I); 82 } 83 void visitCastInst(CastInst &CI) { 84 Instruction &I = (Instruction&)CI; 85 if (isLoopInvariant(I.getOperand(0))) hoist(I); 86 } 87 void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); } 88 89 void visitLoadInst(LoadInst &LI); 90 91 void visitGetElementPtrInst(GetElementPtrInst &GEPI) { 92 Instruction &I = (Instruction&)GEPI; 93 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 94 if (!isLoopInvariant(I.getOperand(i))) return; 95 hoist(I); 96 } 97 }; 98 99 RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion"); 100} 101 102Pass *createLICMPass() { return new LICM(); } 103 104/// runOnFunction - For LICM, this simply traverses the loop structure of the 105/// function, hoisting expressions out of loops if possible. 106/// 107bool LICM::runOnFunction(Function &) { 108 // Get information about the top level loops in the function... 109 const std::vector<Loop*> &TopLevelLoops = 110 getAnalysis<LoopInfo>().getTopLevelLoops(); 111 112 // Get our alias analysis information... 113 AA = &getAnalysis<AliasAnalysis>(); 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 124 125/// visitLoop - Hoist expressions out of the specified loop... 126/// 127void LICM::visitLoop(Loop *L) { 128 // Recurse through all subloops before we process this loop... 129 std::for_each(L->getSubLoops().begin(), L->getSubLoops().end(), 130 bind_obj(this, &LICM::visitLoop)); 131 CurLoop = L; 132 133 // Get the preheader block to move instructions into... 134 Preheader = L->getLoopPreheader(); 135 assert(Preheader&&"Preheader insertion pass guarantees we have a preheader!"); 136 137 // We want to visit all of the instructions in this loop... that are not parts 138 // of our subloops (they have already had their invariants hoisted out of 139 // their loop, into this loop, so there is no need to process the BODIES of 140 // the subloops). 141 // 142 for (std::vector<BasicBlock*>::const_iterator 143 I = L->getBlocks().begin(), E = L->getBlocks().end(); I != E; ++I) 144 if (inCurrentLoop(*I)) 145 visit(**I); 146 147 // Clear out loops state information for the next iteration 148 CurLoop = 0; 149 Preheader = 0; 150} 151 152/// hoist - When an instruction is found to only use loop invariant operands 153/// that is safe to hoist, this instruction is called to do the dirty work. 154/// 155void LICM::hoist(Instruction &Inst) { 156 if (Inst.use_empty()) return; // Don't (re) hoist dead instructions! 157 //cerr << "Hoisting " << Inst; 158 159 BasicBlock *Header = CurLoop->getHeader(); 160 161 // Remove the instruction from its current basic block... but don't delete the 162 // instruction. 163 Inst.getParent()->getInstList().remove(&Inst); 164 165 // Insert the new node in Preheader, before the terminator. 166 Preheader->getInstList().insert(Preheader->getTerminator(), &Inst); 167 168 ++NumHoisted; 169 Changed = true; 170} 171 172 173void LICM::visitLoadInst(LoadInst &LI) { 174 if (isLoopInvariant(LI.getOperand(0)) && 175 !pointerInvalidatedByLoop(LI.getOperand(0))) { 176 hoist(LI); 177 ++NumHoistedLoads; 178 } 179} 180 181/// pointerInvalidatedByLoop - Return true if the body of this loop may store 182/// into the memory location pointed to by V. 183/// 184bool LICM::pointerInvalidatedByLoop(Value *V) { 185 // Check to see if any of the basic blocks in CurLoop invalidate V. 186 for (unsigned i = 0, e = CurLoop->getBlocks().size(); i != e; ++i) 187 if (AA->canBasicBlockModify(*CurLoop->getBlocks()[i], V)) 188 return true; 189 return false; 190} 191