LoopDeletion.cpp revision 9862f31533d09709c0c60b6c943e5ef8a3a5429f
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// 109862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson// This file implements the Dead Loop Elimination Pass. This pass is 119862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson// responsible for eliminating loops with non-infinite computable trip counts 129862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson// that have no side effects or volatile instructions, and do not contribute 139862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson// to the computation of the function's return value. 140ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson// 150ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson//===----------------------------------------------------------------------===// 160ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 170396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson#define DEBUG_TYPE "loop-delete" 180ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 190ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/Transforms/Scalar.h" 200ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/Analysis/LoopPass.h" 210ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/ADT/Statistic.h" 220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/ADT/SmallVector.h" 230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 240ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Andersonusing namespace llvm; 250ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 260ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen AndersonSTATISTIC(NumDeleted, "Number of loops deleted"); 270ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 280ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Andersonnamespace { 290396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson class VISIBILITY_HIDDEN LoopDeletion : public LoopPass { 300ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson public: 310ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson static char ID; // Pass ID, replacement for typeid 320396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson LoopDeletion() : LoopPass((intptr_t)&ID) { } 330ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 340ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Possibly eliminate loop L if it is dead. 350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson bool runOnLoop(Loop* L, LPPassManager& LPM); 360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 379862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson bool SingleDominatingExit(Loop* L, 389862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitingBlocks); 399862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson bool IsLoopDead(Loop* L, SmallVector<BasicBlock*, 4>& exitingBlocks, 409862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitBlocks); 410ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson bool IsLoopInvariantInst(Instruction *I, Loop* L); 420ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 430ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson virtual void getAnalysisUsage(AnalysisUsage& AU) const { 440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequired<DominatorTree>(); 450ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequired<LoopInfo>(); 460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequiredID(LoopSimplifyID); 470ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequiredID(LCSSAID); 480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 490ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreserved<DominatorTree>(); 500ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreserved<LoopInfo>(); 510ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreservedID(LoopSimplifyID); 520ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreservedID(LCSSAID); 530ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 540ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson }; 550ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 560396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson char LoopDeletion::ID = 0; 570396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson RegisterPass<LoopDeletion> X ("loop-deletion", "Delete dead loops"); 580ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 590ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 600396cd33ca2d879d1cf0e9b252ce43a760449fffOwen AndersonLoopPass* llvm::createLoopDeletionPass() { 610396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson return new LoopDeletion(); 620ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 630ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 649862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// SingleDominatingExit - Checks that there is only a single blocks that 659862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// branches out of the loop, and that it also dominates the latch block. Loops 669862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// with multiple or non-latch-dominating exiting blocks could be dead, but we'd 679862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// have to do more extensive analysis to make sure, for instance, that the 689862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// control flow logic involves was or could be made loop-invariant. 699862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Andersonbool LoopDeletion::SingleDominatingExit(Loop* L, 709862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitingBlocks) { 710ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 720ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (exitingBlocks.size() != 1) 739862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 740ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 750ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* latch = L->getLoopLatch(); 760ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!latch) 779862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 780ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 790ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DominatorTree& DT = getAnalysis<DominatorTree>(); 800ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (DT.dominates(exitingBlocks[0], latch)) 819862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return true; 820ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson else 839862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 840ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 850ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 869862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// IsLoopInvariantInst - Checks if an instruction is invariant with respect to 879862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// a loop, which is defined as being true if all of its operands are defined 889862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// outside of the loop. These instructions can be hoisted out of the loop 899862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// if their results are needed. This could be made more aggressive by 909862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// recursively checking the operands for invariance, but it's not clear that 919862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// it's worth it. 920396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Andersonbool LoopDeletion::IsLoopInvariantInst(Instruction *I, Loop* L) { 930ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // PHI nodes are not loop invariant if defined in the loop. 940ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (isa<PHINode>(I) && L->contains(I->getParent())) 950ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 960ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 970ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // The instruction is loop invariant if all of its operands are loop-invariant 980ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 990ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!L->isLoopInvariant(I->getOperand(i))) 1000ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1010ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1020ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // If we got this far, the instruction is loop invariant! 1030ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 1040ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 1050ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1069862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// IsLoopDead - Determined if a loop is dead. This assumes that we've already 1079862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// checked for unique exit and exiting blocks, and that the code is in LCSSA 1089862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// form. 1099862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Andersonbool LoopDeletion::IsLoopDead(Loop* L, 1109862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitingBlocks, 1119862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitBlocks) { 1120ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitingBlock = exitingBlocks[0]; 1130ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitBlock = exitBlocks[0]; 1140ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1150ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Make sure that all PHI entries coming from the loop are loop invariant. 1169862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Because the code is in LCSSA form, any values used outside of the loop 1179862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // must pass through a PHI in the exit block, meaning that this check is 1189862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // sufficient to guarantee that no loop-variant values are used outside 1199862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // of the loop. 1200ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock::iterator BI = exitBlock->begin(); 1210ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson while (PHINode* P = dyn_cast<PHINode>(BI)) { 1220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson Value* incoming = P->getIncomingValueForBlock(exitingBlock); 1230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (Instruction* I = dyn_cast<Instruction>(incoming)) 1240ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!IsLoopInvariantInst(I, L)) 1250ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1260ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1270ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI++; 1280ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1290ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1300ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Make sure that no instructions in the block have potential side-effects. 1319862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // This includes instructions that could write to memory, and loads that are 1329862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // marked volatile. This could be made more aggressive by using aliasing 1339862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // information to identify readonly and readnone calls. 1340ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 1350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) { 1360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 1370ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ++BI) { 1380ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (BI->mayWriteToMemory()) 1390ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1409862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson else if (LoadInst* L = dyn_cast<LoadInst>(BI)) 1419862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson if (L->isVolatile()) 1429862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 1430ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1450ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 1470ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 1480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1495f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the 1505f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// observable behavior of the program other than finite running time. Note 1515f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// we do ensure that this never remove a loop that might be infinite, as doing 1525f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// so could change the halting/non-halting nature of a program. 1539862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA 1549862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// in order to make various safety checks work. 1550396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Andersonbool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { 1569862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4> exitingBlocks; 1579862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson L->getExitingBlocks(exitingBlocks); 1589862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson 1599862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4> exitBlocks; 1609862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson L->getUniqueExitBlocks(exitBlocks); 1619862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson 1629862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // We require that the loop only have a single exit block. Otherwise, we'd 1639862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // be in the situation of needing to be able to solve statically which exit 1649862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // block will be branced to, or trying to preserve the branching logic in 1659862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // a loop invariant manner. 1669862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson if (exitBlocks.size() != 1) 1670ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1680ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1690ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // We can only remove the loop if there is a preheader that we can 1700ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // branch from after removing it. 1710ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* preheader = L->getLoopPreheader(); 1720ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!preheader) 1730ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1740ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1750ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // We can't remove loops that contain subloops. If the subloops were dead, 1760ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // they would already have been removed in earlier executions of this pass. 1770ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (L->begin() != L->end()) 1780ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1790ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1809862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Don't remove loops for which we can't solve the trip count. 1819862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // They could be infinite, in which case we'd be changing program behavior. 1829862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson if (L->getTripCount()) 1839862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 1849862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson 1850ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Loops with multiple exits or exits that don't dominate the latch 1860ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // are too complicated to handle correctly. 1879862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson if (!SingleDominatingExit(L, exitingBlocks)) 1880ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1890ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1900ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Finally, we have to check that the loop really is dead. 1919862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson if (!IsLoopDead(L, exitingBlocks, exitBlocks)) 1920ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1930ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1949862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Now that we know the removal is safe, remove the loop by changing the 1959862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // branch from the preheader to go to the single exiting block. 1960ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitBlock = exitBlocks[0]; 1970ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 198e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Because we're deleting a large chunk of code at once, the sequence in which 199e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // we remove things is very important to avoid invalidation issues. Don't 200e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // mess with this unless you have good reason and know what you're doing. 201e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson 202e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Move simple loop-invariant expressions out of the loop, since they 203e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // might be needed by the exit phis. 2040ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 2050ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) 2060ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 2070ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ) { 2080ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson Instruction* I = BI++; 2090ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (I->getNumUses() > 0 && IsLoopInvariantInst(I, L)) 2100ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson I->moveBefore(preheader->getTerminator()); 2110ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2120ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 213e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Connect the preheader directly to the exit block. 2140ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson TerminatorInst* TI = preheader->getTerminator(); 2159862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson TI->replaceUsesOfWith(L->getHeader(), exitBlock); 2169862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson 217e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Rewrite phis in the exit block to get their inputs from 218e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // the preheader instead of the exiting block. 2190ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock::iterator BI = exitBlock->begin(); 2200ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson while (PHINode* P = dyn_cast<PHINode>(BI)) { 2219862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson P->replaceUsesOfWith(exitBlock, preheader); 2220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI++; 2230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2240ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2259862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Update the dominator tree and remove the instructions and blocks that will 2269862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // be deleted from the reference counting scheme. 2270ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DominatorTree& DT = getAnalysis<DominatorTree>(); 2289862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallPtrSet<DomTreeNode*, 8> ChildNodes; 2290ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 2300ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) { 231e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Move all of the block's children to be children of the preheader, which 232e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // allows us to remove the domtree entry for the block. 2339862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson ChildNodes.insert(DT[*LI]->begin(), DT[*LI]->end()); 2349862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson for (SmallPtrSet<DomTreeNode*, 8>::iterator DI = ChildNodes.begin(), 2359862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson DE = ChildNodes.end(); DI != DE; ++DI) 2360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DT.changeImmediateDominator(*DI, DT[preheader]); 2370ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2389862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson ChildNodes.clear(); 2390ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DT.eraseNode(*LI); 2400ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 241e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Drop all references between the instructions and the block so 242e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // that we don't have reference counting problems later. 2430ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 2440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ++BI) { 2450ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI->dropAllReferences(); 2460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2470ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson (*LI)->dropAllReferences(); 2490ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2500ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 251e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Erase the instructions and the blocks without having to worry 252e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // about ordering because we already dropped the references. 2539862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // NOTE: This iteration is safe because erasing the block does not remove its 2549862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // entry from the loop's block list. We do that in the next section. 2550ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 2569862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson LI != LE; ++LI) 2570ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson (*LI)->eraseFromParent(); 2580ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 259e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Finally, the blocks from loopinfo. This has to happen late because 260e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // otherwise our loop iterators won't work. 2610ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 2620ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallPtrSet<BasicBlock*, 8> blocks; 2630ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson blocks.insert(L->block_begin(), L->block_end()); 2640ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (SmallPtrSet<BasicBlock*,8>::iterator I = blocks.begin(), 2650ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson E = blocks.end(); I != E; ++I) 2660ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson loopInfo.removeBlock(*I); 2670ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 268e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // The last step is to inform the loop pass manager that we've 269e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // eliminated this loop. 2700ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LPM.deleteLoopFromQueue(L); 2710ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2720ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson NumDeleted++; 2730ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2740ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 2750ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 276