LICM.cpp revision cb2610ea037a17115ef3a01a6bdaab4e3cfdca27
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/Analysis/Dominators.h" 12#include "llvm/iOperators.h" 13#include "llvm/iMemory.h" 14#include "llvm/Support/InstVisitor.h" 15#include "Support/STLExtras.h" 16#include "Support/Statistic.h" 17#include "llvm/Assembly/Writer.h" 18#include <algorithm> 19using std::string; 20 21namespace { 22 Statistic<> NumHoisted("licm", "Number of instructions hoisted out of loop"); 23 Statistic<> NumHoistedLoads("licm", "Number of load insts hoisted"); 24 25 struct LICM : public FunctionPass, public InstVisitor<LICM> { 26 virtual bool runOnFunction(Function &F); 27 28 /// This transformation requires natural loop information & requires that 29 /// loop preheaders be inserted into the CFG... 30 /// 31 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 32 AU.setPreservesCFG(); 33 AU.addRequiredID(LoopPreheadersID); 34 AU.addRequired<LoopInfo>(); 35 AU.addRequired<DominatorTree>(); 36 AU.addRequired<AliasAnalysis>(); 37 } 38 39 private: 40 Loop *CurLoop; // The current loop we are working on... 41 BasicBlock *Preheader; // The preheader block of the current loop... 42 bool Changed; // Set to true when we change anything. 43 AliasAnalysis *AA; // Currently AliasAnalysis information 44 45 /// visitLoop - Hoist expressions out of the specified loop... 46 /// 47 void visitLoop(Loop *L); 48 49 /// HoistRegion - Walk the specified region of the CFG (defined by all 50 /// blocks dominated by the specified block, and that are in the current 51 /// loop) in depth first order w.r.t the DominatorTree. This allows us to 52 /// visit defintions before uses, allowing us to hoist a loop body in one 53 /// pass without iteration. 54 /// 55 void HoistRegion(DominatorTree::Node *N); 56 57 /// inSubLoop - Little predicate that returns true if the specified basic 58 /// block is in a subloop of the current one, not the current one itself. 59 /// 60 bool inSubLoop(BasicBlock *BB) { 61 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); 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 /// pointerInvalidatedByLoop - Return true if the body of this loop may 74 /// store into the memory location pointed to by V. 75 /// 76 bool pointerInvalidatedByLoop(Value *V); 77 78 /// isLoopInvariant - Return true if the specified value is loop invariant 79 /// 80 inline bool isLoopInvariant(Value *V) { 81 if (Instruction *I = dyn_cast<Instruction>(V)) 82 return !CurLoop->contains(I->getParent()); 83 return true; // All non-instructions are loop invariant 84 } 85 86 /// Instruction visitation handlers... these basically control whether or 87 /// not the specified instruction types are hoisted. 88 /// 89 friend class InstVisitor<LICM>; 90 void visitBinaryOperator(Instruction &I) { 91 if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1))) 92 hoist(I); 93 } 94 void visitCastInst(CastInst &CI) { 95 Instruction &I = (Instruction&)CI; 96 if (isLoopInvariant(I.getOperand(0))) hoist(I); 97 } 98 void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); } 99 100 void visitLoadInst(LoadInst &LI); 101 102 void visitGetElementPtrInst(GetElementPtrInst &GEPI) { 103 Instruction &I = (Instruction&)GEPI; 104 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 105 if (!isLoopInvariant(I.getOperand(i))) return; 106 hoist(I); 107 } 108 }; 109 110 RegisterOpt<LICM> X("licm", "Loop Invariant Code Motion"); 111} 112 113Pass *createLICMPass() { return new LICM(); } 114 115/// runOnFunction - For LICM, this simply traverses the loop structure of the 116/// function, hoisting expressions out of loops if possible. 117/// 118bool LICM::runOnFunction(Function &) { 119 // Get information about the top level loops in the function... 120 const std::vector<Loop*> &TopLevelLoops = 121 getAnalysis<LoopInfo>().getTopLevelLoops(); 122 123 // Get our alias analysis information... 124 AA = &getAnalysis<AliasAnalysis>(); 125 126 // Traverse loops in postorder, hoisting expressions out of the deepest loops 127 // first. 128 // 129 Changed = false; 130 std::for_each(TopLevelLoops.begin(), TopLevelLoops.end(), 131 bind_obj(this, &LICM::visitLoop)); 132 return Changed; 133} 134 135 136/// visitLoop - Hoist expressions out of the specified loop... 137/// 138void LICM::visitLoop(Loop *L) { 139 // Recurse through all subloops before we process this loop... 140 std::for_each(L->getSubLoops().begin(), L->getSubLoops().end(), 141 bind_obj(this, &LICM::visitLoop)); 142 CurLoop = L; 143 144 // Get the preheader block to move instructions into... 145 Preheader = L->getLoopPreheader(); 146 assert(Preheader&&"Preheader insertion pass guarantees we have a preheader!"); 147 148 // We want to visit all of the instructions in this loop... that are not parts 149 // of our subloops (they have already had their invariants hoisted out of 150 // their loop, into this loop, so there is no need to process the BODIES of 151 // the subloops). 152 // 153 // Traverse the body of the loop in depth first order on the dominator tree so 154 // that we are guaranteed to see definitions before we see uses. This allows 155 // us to perform the LICM transformation in one pass, without iteration. 156 // 157 HoistRegion(getAnalysis<DominatorTree>()[L->getHeader()]); 158 159 // Clear out loops state information for the next iteration 160 CurLoop = 0; 161 Preheader = 0; 162} 163 164/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 165/// dominated by the specified block, and that are in the current loop) in depth 166/// first order w.r.t the DominatorTree. This allows us to visit defintions 167/// before uses, allowing us to hoist a loop body in one pass without iteration. 168/// 169void LICM::HoistRegion(DominatorTree::Node *N) { 170 assert(N != 0 && "Null dominator tree node?"); 171 172 // If this subregion is not in the top level loop at all, exit. 173 if (!CurLoop->contains(N->getNode())) return; 174 175 // Only need to hoist the contents of this block if it is not part of a 176 // subloop (which would already have been hoisted) 177 if (!inSubLoop(N->getNode())) 178 visit(*N->getNode()); 179 180 const std::vector<DominatorTree::Node*> &Children = N->getChildren(); 181 for (unsigned i = 0, e = Children.size(); i != e; ++i) 182 HoistRegion(Children[i]); 183} 184 185 186/// hoist - When an instruction is found to only use loop invariant operands 187/// that is safe to hoist, this instruction is called to do the dirty work. 188/// 189void LICM::hoist(Instruction &Inst) { 190 DEBUG(std::cerr << "LICM hoisting to"; 191 WriteAsOperand(std::cerr, Preheader, false); 192 std::cerr << ": " << Inst); 193 194 // Remove the instruction from its current basic block... but don't delete the 195 // instruction. 196 Inst.getParent()->getInstList().remove(&Inst); 197 198 // Insert the new node in Preheader, before the terminator. 199 Preheader->getInstList().insert(Preheader->getTerminator(), &Inst); 200 201 ++NumHoisted; 202 Changed = true; 203} 204 205 206void LICM::visitLoadInst(LoadInst &LI) { 207 if (isLoopInvariant(LI.getOperand(0)) && 208 !pointerInvalidatedByLoop(LI.getOperand(0))) { 209 hoist(LI); 210 ++NumHoistedLoads; 211 } 212} 213 214/// pointerInvalidatedByLoop - Return true if the body of this loop may store 215/// into the memory location pointed to by V. 216/// 217bool LICM::pointerInvalidatedByLoop(Value *V) { 218 // Check to see if any of the basic blocks in CurLoop invalidate V. 219 for (unsigned i = 0, e = CurLoop->getBlocks().size(); i != e; ++i) 220 if (AA->canBasicBlockModify(*CurLoop->getBlocks()[i], V)) 221 return true; 222 return false; 223} 224