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