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/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/StatisticReporter.h"
  17 #include "llvm/Assembly/Writer.h"
  18 #include <algorithm>
  19 using std::string;
  20
  21 namespace {
  22   Statistic<>NumHoisted("licm\t\t- Number of instructions hoisted out of loop");
  23   Statistic<> NumHoistedLoads("licm\t\t- 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.preservesCFG();
  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
 113 Pass *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 ///
 118 bool 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 ///
 138 void 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 ///
 169 void 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 ///
 189 void 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
 206 void 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 ///
 217 bool 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 }