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