LoopDeletion.cpp revision 0396cd33ca2d879d1cf0e9b252ce43a760449fff
10396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson//===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===// 20ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson// 30ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson// The LLVM Compiler Infrastructure 40ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson// 50ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson// This file is distributed under the University of Illinois Open Source 60ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson// License. See LICENSE.TXT for details. 70ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson// 80ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson//===----------------------------------------------------------------------===// 90ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson// 100ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson// This file implements the Dead Loop Elimination Pass. 110ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson// 120ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson//===----------------------------------------------------------------------===// 130ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 140396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson#define DEBUG_TYPE "loop-delete" 150ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 160ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/Transforms/Scalar.h" 170ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/Analysis/LoopPass.h" 180ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/ADT/Statistic.h" 190ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/ADT/SmallVector.h" 200ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 210ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Andersonusing namespace llvm; 220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen AndersonSTATISTIC(NumDeleted, "Number of loops deleted"); 240ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 250ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Andersonnamespace { 260396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson class VISIBILITY_HIDDEN LoopDeletion : public LoopPass { 270ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson public: 280ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson static char ID; // Pass ID, replacement for typeid 290396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson LoopDeletion() : LoopPass((intptr_t)&ID) { } 300ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 310ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Possibly eliminate loop L if it is dead. 320ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson bool runOnLoop(Loop* L, LPPassManager& LPM); 330ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 340ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson bool SingleDominatingExit(Loop* L); 350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson bool IsLoopDead(Loop* L); 360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson bool IsLoopInvariantInst(Instruction *I, Loop* L); 370ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 380ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson virtual void getAnalysisUsage(AnalysisUsage& AU) const { 390ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequired<DominatorTree>(); 400ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequired<LoopInfo>(); 410ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequiredID(LoopSimplifyID); 420ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequiredID(LCSSAID); 430ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreserved<DominatorTree>(); 450ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreserved<LoopInfo>(); 460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreservedID(LoopSimplifyID); 470ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreservedID(LCSSAID); 480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 490ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson }; 500ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 510396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson char LoopDeletion::ID = 0; 520396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson RegisterPass<LoopDeletion> X ("loop-deletion", "Delete dead loops"); 530ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 540ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 550396cd33ca2d879d1cf0e9b252ce43a760449fffOwen AndersonLoopPass* llvm::createLoopDeletionPass() { 560396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson return new LoopDeletion(); 570ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 580ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 590396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Andersonbool LoopDeletion::SingleDominatingExit(Loop* L) { 600ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallVector<BasicBlock*, 4> exitingBlocks; 610ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson L->getExitingBlocks(exitingBlocks); 620ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 630ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (exitingBlocks.size() != 1) 640ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return 0; 650ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 660ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* latch = L->getLoopLatch(); 670ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!latch) 680ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return 0; 690ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 700ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DominatorTree& DT = getAnalysis<DominatorTree>(); 710ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (DT.dominates(exitingBlocks[0], latch)) 720ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return exitingBlocks[0]; 730ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson else 740ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return 0; 750ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 760ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 770396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Andersonbool LoopDeletion::IsLoopInvariantInst(Instruction *I, Loop* L) { 780ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // PHI nodes are not loop invariant if defined in the loop. 790ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (isa<PHINode>(I) && L->contains(I->getParent())) 800ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 810ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 820ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // The instruction is loop invariant if all of its operands are loop-invariant 830ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 840ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!L->isLoopInvariant(I->getOperand(i))) 850ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 860ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 870ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // If we got this far, the instruction is loop invariant! 880ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 890ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 900ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 910396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Andersonbool LoopDeletion::IsLoopDead(Loop* L) { 920ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallVector<BasicBlock*, 1> exitingBlocks; 930ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson L->getExitingBlocks(exitingBlocks); 940ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitingBlock = exitingBlocks[0]; 950ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 960ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Get the set of out-of-loop blocks that the exiting block branches to. 970ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallVector<BasicBlock*, 8> exitBlocks; 980ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson L->getUniqueExitBlocks(exitBlocks); 990ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (exitBlocks.size() > 1) 1000ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1010ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitBlock = exitBlocks[0]; 1020ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1030ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Make sure that all PHI entries coming from the loop are loop invariant. 1040ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock::iterator BI = exitBlock->begin(); 1050ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson while (PHINode* P = dyn_cast<PHINode>(BI)) { 1060ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson Value* incoming = P->getIncomingValueForBlock(exitingBlock); 1070ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (Instruction* I = dyn_cast<Instruction>(incoming)) 1080ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!IsLoopInvariantInst(I, L)) 1090ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1100ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1110ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI++; 1120ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1130ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1140ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Make sure that no instructions in the block have potential side-effects. 1150ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 1160ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) { 1170ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 1180ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ++BI) { 1190ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (BI->mayWriteToMemory()) 1200ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1210ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1240ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 1250ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 1260ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1275f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the 1285f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// observable behavior of the program other than finite running time. Note 1295f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// we do ensure that this never remove a loop that might be infinite, as doing 1305f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// so could change the halting/non-halting nature of a program. 1310396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Andersonbool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { 1320ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Don't remove loops for which we can't solve the trip count. 1330ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // They could be infinite, in which case we'd be changing program behavior. 1340ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (L->getTripCount()) 1350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1370ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // We can only remove the loop if there is a preheader that we can 1380ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // branch from after removing it. 1390ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* preheader = L->getLoopPreheader(); 1400ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!preheader) 1410ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1420ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1430ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // We can't remove loops that contain subloops. If the subloops were dead, 1440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // they would already have been removed in earlier executions of this pass. 1450ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (L->begin() != L->end()) 1460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1470ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Loops with multiple exits or exits that don't dominate the latch 1490ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // are too complicated to handle correctly. 1500ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!SingleDominatingExit(L)) 1510ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1520ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1530ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Finally, we have to check that the loop really is dead. 1540ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!IsLoopDead(L)) 1550ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1560ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1570ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Now that we know the removal is safe, change the branch from the preheader 1580ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // to go to the single exiting block. 1590ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallVector<BasicBlock*, 1> exitingBlocks; 1600ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson L->getExitingBlocks(exitingBlocks); 1610ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitingBlock = exitingBlocks[0]; 1620ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1630ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallVector<BasicBlock*, 1> exitBlocks; 1640ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson L->getUniqueExitBlocks(exitBlocks); 1650ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitBlock = exitBlocks[0]; 1660ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 167e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Because we're deleting a large chunk of code at once, the sequence in which 168e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // we remove things is very important to avoid invalidation issues. Don't 169e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // mess with this unless you have good reason and know what you're doing. 170e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson 171e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Move simple loop-invariant expressions out of the loop, since they 172e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // might be needed by the exit phis. 1730ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 1740ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) 1750ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 1760ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ) { 1770ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson Instruction* I = BI++; 1780ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (I->getNumUses() > 0 && IsLoopInvariantInst(I, L)) 1790ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson I->moveBefore(preheader->getTerminator()); 1800ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1810ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 182e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Connect the preheader directly to the exit block. 1830ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson TerminatorInst* TI = preheader->getTerminator(); 1840ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (BranchInst* BI = dyn_cast<BranchInst>(TI)) { 1850ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (BI->isUnconditional()) 1860ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI->setSuccessor(0, exitBlock); 1870ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson else if (L->contains(BI->getSuccessor(0))) 1880ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI->setSuccessor(0, exitBlock); 1890ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson else 1900ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI->setSuccessor(1, exitBlock); 1910ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } else { 192e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // FIXME: Support switches 1930ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1940ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1950ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 196e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Rewrite phis in the exit block to get their inputs from 197e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // the preheader instead of the exiting block. 1980ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock::iterator BI = exitBlock->begin(); 1990ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson while (PHINode* P = dyn_cast<PHINode>(BI)) { 2000ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson unsigned i = P->getBasicBlockIndex(exitingBlock); 2010ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson P->setIncomingBlock(i, preheader); 2020ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI++; 2030ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2040ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 205e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Update lots of internal structures... 2060ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DominatorTree& DT = getAnalysis<DominatorTree>(); 2070ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 2080ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) { 209e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Move all of the block's children to be children of the preheader, which 210e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // allows us to remove the domtree entry for the block. 2110ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallPtrSet<DomTreeNode*, 8> childNodes; 2120ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson childNodes.insert(DT[*LI]->begin(), DT[*LI]->end()); 2130ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (SmallPtrSet<DomTreeNode*, 8>::iterator DI = childNodes.begin(), 2140ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DE = childNodes.end(); DI != DE; ++DI) 2150ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DT.changeImmediateDominator(*DI, DT[preheader]); 2160ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2170ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DT.eraseNode(*LI); 2180ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 219e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Drop all references between the instructions and the block so 220e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // that we don't have reference counting problems later. 2210ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 2220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ++BI) { 2230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI->dropAllReferences(); 2240ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2250ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2260ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson (*LI)->dropAllReferences(); 2270ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2280ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 229e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Erase the instructions and the blocks without having to worry 230e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // about ordering because we already dropped the references. 2310ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 2320ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) { 2330ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 2340ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ) { 2350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson Instruction* I = BI++; 2360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson I->eraseFromParent(); 2370ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2380ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2390ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson (*LI)->eraseFromParent(); 2400ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2410ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 242e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Finally, the blocks from loopinfo. This has to happen late because 243e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // otherwise our loop iterators won't work. 2440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 2450ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallPtrSet<BasicBlock*, 8> blocks; 2460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson blocks.insert(L->block_begin(), L->block_end()); 2470ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (SmallPtrSet<BasicBlock*,8>::iterator I = blocks.begin(), 2480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson E = blocks.end(); I != E; ++I) 2490ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson loopInfo.removeBlock(*I); 2500ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 251e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // The last step is to inform the loop pass manager that we've 252e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // eliminated this loop. 2530ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LPM.deleteLoopFromQueue(L); 2540ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2550ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson NumDeleted++; 2560ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2570ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 2580ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 259