lib/Transforms/Scalar/LoopDeletion.cpp

   1 //===- DeadLoopElimination.cpp - Dead Loop Elimination Pass ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the Dead Loop Elimination Pass.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "dead-loop"
  15
  16 #include "llvm/Transforms/Scalar.h"
  17 #include "llvm/Instruction.h"
  18 #include "llvm/Analysis/LoopInfo.h"
  19 #include "llvm/Analysis/LoopPass.h"
  20 #include "llvm/ADT/Statistic.h"
  21 #include "llvm/ADT/SmallVector.h"
  22
  23 using namespace llvm;
  24
  25 STATISTIC(NumDeleted, "Number of loops deleted");
  26
  27 namespace {
  28   class VISIBILITY_HIDDEN DeadLoopElimination : public LoopPass {
  29   public:
  30     static char ID; // Pass ID, replacement for typeid
  31     DeadLoopElimination() : LoopPass((intptr_t)&ID) { }
  32
  33     // Possibly eliminate loop L if it is dead.
  34     bool runOnLoop(Loop* L, LPPassManager& LPM);
  35
  36     bool SingleDominatingExit(Loop* L);
  37     bool IsLoopDead(Loop* L);
  38     bool IsLoopInvariantInst(Instruction *I, Loop* L);
  39
  40     virtual void getAnalysisUsage(AnalysisUsage& AU) const {
  41       AU.addRequired<DominatorTree>();
  42       AU.addRequired<LoopInfo>();
  43       AU.addRequiredID(LoopSimplifyID);
  44       AU.addRequiredID(LCSSAID);
  45
  46       AU.addPreserved<DominatorTree>();
  47       AU.addPreserved<LoopInfo>();
  48       AU.addPreservedID(LoopSimplifyID);
  49       AU.addPreservedID(LCSSAID);
  50     }
  51   };
  52
  53   char DeadLoopElimination::ID = 0;
  54   RegisterPass<DeadLoopElimination> X ("dead-loop", "Eliminate dead loops");
  55 }
  56
  57 LoopPass* llvm::createDeadLoopEliminationPass() {
  58   return new DeadLoopElimination();
  59 }
  60
  61 bool DeadLoopElimination::SingleDominatingExit(Loop* L) {
  62   SmallVector<BasicBlock*, 4> exitingBlocks;
  63   L->getExitingBlocks(exitingBlocks);
  64
  65   if (exitingBlocks.size() != 1)
  66     return 0;
  67
  68   BasicBlock* latch = L->getLoopLatch();
  69   if (!latch)
  70     return 0;
  71
  72   DominatorTree& DT = getAnalysis<DominatorTree>();
  73   if (DT.dominates(exitingBlocks[0], latch))
  74     return exitingBlocks[0];
  75   else
  76     return 0;
  77 }
  78
  79 bool DeadLoopElimination::IsLoopInvariantInst(Instruction *I, Loop* L)  {
  80   // PHI nodes are not loop invariant if defined in  the loop.
  81   if (isa<PHINode>(I) && L->contains(I->getParent()))
  82     return false;
  83
  84   // The instruction is loop invariant if all of its operands are loop-invariant
  85   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
  86     if (!L->isLoopInvariant(I->getOperand(i)))
  87       return false;
  88
  89   // If we got this far, the instruction is loop invariant!
  90   return true;
  91 }
  92
  93 bool DeadLoopElimination::IsLoopDead(Loop* L) {
  94   SmallVector<BasicBlock*, 1> exitingBlocks;
  95   L->getExitingBlocks(exitingBlocks);
  96   BasicBlock* exitingBlock = exitingBlocks[0];
  97
  98   // Get the set of out-of-loop blocks that the exiting block branches to.
  99   SmallVector<BasicBlock*, 8> exitBlocks;
 100   L->getUniqueExitBlocks(exitBlocks);
 101   if (exitBlocks.size() > 1)
 102     return false;
 103   BasicBlock* exitBlock = exitBlocks[0];
 104
 105   // Make sure that all PHI entries coming from the loop are loop invariant.
 106   BasicBlock::iterator BI = exitBlock->begin();
 107   while (PHINode* P = dyn_cast<PHINode>(BI)) {
 108     Value* incoming = P->getIncomingValueForBlock(exitingBlock);
 109     if (Instruction* I = dyn_cast<Instruction>(incoming))
 110       if (!IsLoopInvariantInst(I, L))
 111         return false;
 112
 113     BI++;
 114   }
 115
 116   // Make sure that no instructions in the block have potential side-effects.
 117   for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
 118        LI != LE; ++LI) {
 119     for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end();
 120          BI != BE; ++BI) {
 121       if (BI->mayWriteToMemory())
 122         return false;
 123     }
 124   }
 125
 126   return true;
 127 }
 128
 129 /// runOnLoop - Remove dead loops, by which we mean loops that do not impact the
 130 /// observable behavior of the program other than finite running time.  Note
 131 /// we do ensure that this never remove a loop that might be infinite, as doing
 132 /// so could change the halting/non-halting nature of a program.
 133 bool DeadLoopElimination::runOnLoop(Loop* L, LPPassManager& LPM) {
 134   // Don't remove loops for which we can't solve the trip count.
 135   // They could be infinite, in which case we'd be changing program behavior.
 136   if (L->getTripCount())
 137     return false;
 138
 139   // We can only remove the loop if there is a preheader that we can
 140   // branch from after removing it.
 141   BasicBlock* preheader = L->getLoopPreheader();
 142   if (!preheader)
 143     return false;
 144
 145   // We can't remove loops that contain subloops.  If the subloops were dead,
 146   // they would already have been removed in earlier executions of this pass.
 147   if (L->begin() != L->end())
 148     return false;
 149
 150   // Loops with multiple exits or exits that don't dominate the latch
 151   // are too complicated to handle correctly.
 152   if (!SingleDominatingExit(L))
 153     return false;
 154
 155   // Finally, we have to check that the loop really is dead.
 156   if (!IsLoopDead(L))
 157     return false;
 158
 159   // Now that we know the removal is safe, change the branch from the preheader
 160   // to go to the single exiting block.
 161   SmallVector<BasicBlock*, 1> exitingBlocks;
 162   L->getExitingBlocks(exitingBlocks);
 163   BasicBlock* exitingBlock = exitingBlocks[0];
 164
 165   SmallVector<BasicBlock*, 1> exitBlocks;
 166   L->getUniqueExitBlocks(exitBlocks);
 167   BasicBlock* exitBlock = exitBlocks[0];
 168
 169   // Because we're deleting a large chunk of code at once, the sequence in which
 170   // we remove things is very important to avoid invalidation issues.  Don't
 171   // mess with this unless you have good reason and know what you're doing.
 172
 173   // Move simple loop-invariant expressions out of the loop, since they
 174   // might be needed by the exit phis.
 175   for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
 176        LI != LE; ++LI)
 177     for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end();
 178          BI != BE; ) {
 179       Instruction* I = BI++;
 180       if (I->getNumUses() > 0 && IsLoopInvariantInst(I, L))
 181         I->moveBefore(preheader->getTerminator());
 182     }
 183
 184   // Connect the preheader directly to the exit block.
 185   TerminatorInst* TI = preheader->getTerminator();
 186   if (BranchInst* BI = dyn_cast<BranchInst>(TI)) {
 187     if (BI->isUnconditional())
 188       BI->setSuccessor(0, exitBlock);
 189     else if (L->contains(BI->getSuccessor(0)))
 190       BI->setSuccessor(0, exitBlock);
 191     else
 192       BI->setSuccessor(1, exitBlock);
 193   } else {
 194     // FIXME: Support switches
 195     return false;
 196   }
 197
 198   // Rewrite phis in the exit block to get their inputs from
 199   // the preheader instead of the exiting block.
 200   BasicBlock::iterator BI = exitBlock->begin();
 201   while (PHINode* P = dyn_cast<PHINode>(BI)) {
 202     unsigned i = P->getBasicBlockIndex(exitingBlock);
 203     P->setIncomingBlock(i, preheader);
 204     BI++;
 205   }
 206
 207   // Update lots of internal structures...
 208   DominatorTree& DT = getAnalysis<DominatorTree>();
 209   for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
 210        LI != LE; ++LI) {
 211     // Move all of the block's children to be children of the preheader, which
 212     // allows us to remove the domtree entry for the block.
 213     SmallPtrSet<DomTreeNode*, 8> childNodes;
 214     childNodes.insert(DT[*LI]->begin(), DT[*LI]->end());
 215     for (SmallPtrSet<DomTreeNode*, 8>::iterator DI = childNodes.begin(),
 216          DE = childNodes.end(); DI != DE; ++DI)
 217       DT.changeImmediateDominator(*DI, DT[preheader]);
 218
 219     DT.eraseNode(*LI);
 220
 221     // Drop all references between the instructions and the block so
 222     // that we don't have reference counting problems later.
 223     for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end();
 224          BI != BE; ++BI) {
 225       BI->dropAllReferences();
 226     }
 227
 228     (*LI)->dropAllReferences();
 229   }
 230
 231   // Erase the instructions and the blocks without having to worry
 232   // about ordering because we already dropped the references.
 233   for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
 234        LI != LE; ++LI) {
 235     for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end();
 236          BI != BE; ) {
 237       Instruction* I = BI++;
 238       I->eraseFromParent();
 239     }
 240
 241     (*LI)->eraseFromParent();
 242   }
 243
 244   // Finally, the blocks from loopinfo.  This has to happen late because
 245   // otherwise our loop iterators won't work.
 246   LoopInfo& loopInfo = getAnalysis<LoopInfo>();
 247   SmallPtrSet<BasicBlock*, 8> blocks;
 248   blocks.insert(L->block_begin(), L->block_end());
 249   for (SmallPtrSet<BasicBlock*,8>::iterator I = blocks.begin(),
 250        E = blocks.end(); I != E; ++I)
 251     loopInfo.removeBlock(*I);
 252
 253   // The last step is to inform the loop pass manager that we've
 254   // eliminated this loop.
 255   LPM.deleteLoopFromQueue(L);
 256
 257   NumDeleted++;
 258
 259   return true;
 260 }