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