lib/Transforms/Scalar/LICM.cpp

   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>
  17 using std::string;
  18
  19 namespace {
  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
 102 Pass *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 ///
 107 bool 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 ///
 127 void 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 ///
 155 void 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
 173 void 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 ///
 184 bool 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 }