LoopDeletion.cpp revision d0a90b987673e22985c3407f413c76eb104777c4
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// 10a8a118b68fa3ca1632e7280cd6994aa0f8f1eec1Gordon Henriksen// This file implements the Dead Loop Deletion Pass. This pass is responsible 11a8a118b68fa3ca1632e7280cd6994aa0f8f1eec1Gordon Henriksen// for eliminating loops with non-infinite computable trip counts that have no 12a8a118b68fa3ca1632e7280cd6994aa0f8f1eec1Gordon Henriksen// side effects or volatile instructions, and do not contribute to the 13a8a118b68fa3ca1632e7280cd6994aa0f8f1eec1Gordon Henriksen// 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" 210db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson#include "llvm/Analysis/ScalarEvolution.h" 220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/ADT/Statistic.h" 230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/ADT/SmallVector.h" 240ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 250ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Andersonusing namespace llvm; 260ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 270ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen AndersonSTATISTIC(NumDeleted, "Number of loops deleted"); 280ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 290ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Andersonnamespace { 300396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson class VISIBILITY_HIDDEN LoopDeletion : public LoopPass { 310ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson public: 320ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson static char ID; // Pass ID, replacement for typeid 33ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman LoopDeletion() : LoopPass(&ID) {} 340ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Possibly eliminate loop L if it is dead. 360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson bool runOnLoop(Loop* L, LPPassManager& LPM); 370ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 389862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson bool SingleDominatingExit(Loop* L, 399862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitingBlocks); 409862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson bool IsLoopDead(Loop* L, SmallVector<BasicBlock*, 4>& exitingBlocks, 419862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitBlocks); 420ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson bool IsLoopInvariantInst(Instruction *I, Loop* L); 430ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson virtual void getAnalysisUsage(AnalysisUsage& AU) const { 450db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson AU.addRequired<ScalarEvolution>(); 460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequired<DominatorTree>(); 470ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequired<LoopInfo>(); 480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequiredID(LoopSimplifyID); 490ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequiredID(LCSSAID); 500ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 510db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson AU.addPreserved<ScalarEvolution>(); 520ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreserved<DominatorTree>(); 530ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreserved<LoopInfo>(); 540ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreservedID(LoopSimplifyID); 550ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreservedID(LCSSAID); 56d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman AU.addPreserved<DominanceFrontier>(); 570ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 580ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson }; 590ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 60844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 61844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopDeletion::ID = 0; 62844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LoopDeletion> X("loop-deletion", "Delete dead loops"); 630ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 64394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass* llvm::createLoopDeletionPass() { 650396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson return new LoopDeletion(); 660ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 670ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 689862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// SingleDominatingExit - Checks that there is only a single blocks that 690db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson/// branches out of the loop, and that it also g the latch block. Loops 709862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// with multiple or non-latch-dominating exiting blocks could be dead, but we'd 719862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// have to do more extensive analysis to make sure, for instance, that the 720db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson/// control flow logic involved was or could be made loop-invariant. 739862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Andersonbool LoopDeletion::SingleDominatingExit(Loop* L, 749862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitingBlocks) { 750ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 760ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (exitingBlocks.size() != 1) 779862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 780ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 790ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* latch = L->getLoopLatch(); 800ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!latch) 819862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 820ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 830ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DominatorTree& DT = getAnalysis<DominatorTree>(); 840db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson return DT.dominates(exitingBlocks[0], latch); 850ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 860ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 879862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// IsLoopInvariantInst - Checks if an instruction is invariant with respect to 889862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// a loop, which is defined as being true if all of its operands are defined 899862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// outside of the loop. These instructions can be hoisted out of the loop 909862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// if their results are needed. This could be made more aggressive by 919862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// recursively checking the operands for invariance, but it's not clear that 929862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// it's worth it. 930396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Andersonbool LoopDeletion::IsLoopInvariantInst(Instruction *I, Loop* L) { 940ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // PHI nodes are not loop invariant if defined in the loop. 950ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (isa<PHINode>(I) && L->contains(I->getParent())) 960ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 970ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 980ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // The instruction is loop invariant if all of its operands are loop-invariant 990ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 1000ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!L->isLoopInvariant(I->getOperand(i))) 1010ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1020db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 1030ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // If we got this far, the instruction is loop invariant! 1040ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 1050ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 1060ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1079862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// IsLoopDead - Determined if a loop is dead. This assumes that we've already 1089862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// checked for unique exit and exiting blocks, and that the code is in LCSSA 1099862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// form. 1109862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Andersonbool LoopDeletion::IsLoopDead(Loop* L, 1119862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitingBlocks, 1129862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitBlocks) { 1130ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitingBlock = exitingBlocks[0]; 1140ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitBlock = exitBlocks[0]; 1150ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1160ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Make sure that all PHI entries coming from the loop are loop invariant. 1179862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Because the code is in LCSSA form, any values used outside of the loop 1189862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // must pass through a PHI in the exit block, meaning that this check is 1199862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // sufficient to guarantee that no loop-variant values are used outside 1209862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // of the loop. 1210ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock::iterator BI = exitBlock->begin(); 1220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson while (PHINode* P = dyn_cast<PHINode>(BI)) { 1230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson Value* incoming = P->getIncomingValueForBlock(exitingBlock); 1240ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (Instruction* I = dyn_cast<Instruction>(incoming)) 1250ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!IsLoopInvariantInst(I, L)) 1260ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1270ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1280ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI++; 1290ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1300ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1310ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Make sure that no instructions in the block have potential side-effects. 1329862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // This includes instructions that could write to memory, and loads that are 1339862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // marked volatile. This could be made more aggressive by using aliasing 1349862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // information to identify readonly and readnone calls. 1350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 1360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) { 1370ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 1380ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ++BI) { 1390ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (BI->mayWriteToMemory()) 1400ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1419862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson else if (LoadInst* L = dyn_cast<LoadInst>(BI)) 1429862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson if (L->isVolatile()) 1439862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 1440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1450ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1470ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 1480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 1490ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1505f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the 1515f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// observable behavior of the program other than finite running time. Note 1525f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// we do ensure that this never remove a loop that might be infinite, as doing 1535f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// so could change the halting/non-halting nature of a program. 1549862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA 1559862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// in order to make various safety checks work. 1560396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Andersonbool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { 1570ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // We can only remove the loop if there is a preheader that we can 1580ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // branch from after removing it. 1590ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* preheader = L->getLoopPreheader(); 1600ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!preheader) 1610ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1620ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1630ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // We can't remove loops that contain subloops. If the subloops were dead, 1640ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // they would already have been removed in earlier executions of this pass. 1650ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (L->begin() != L->end()) 1660ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1670ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1680db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson SmallVector<BasicBlock*, 4> exitingBlocks; 1690db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson L->getExitingBlocks(exitingBlocks); 1700db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 1710db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson SmallVector<BasicBlock*, 4> exitBlocks; 1720db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson L->getUniqueExitBlocks(exitBlocks); 1730db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 1740db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // We require that the loop only have a single exit block. Otherwise, we'd 1750db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // be in the situation of needing to be able to solve statically which exit 1760db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // block will be branched to, or trying to preserve the branching logic in 1770db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // a loop invariant manner. 1780db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson if (exitBlocks.size() != 1) 1799862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 1809862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson 1810ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Loops with multiple exits or exits that don't dominate the latch 1820ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // are too complicated to handle correctly. 1839862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson if (!SingleDominatingExit(L, exitingBlocks)) 1840ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1850ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1860ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Finally, we have to check that the loop really is dead. 1879862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson if (!IsLoopDead(L, exitingBlocks, exitBlocks)) 1880ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1890ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1900db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // Don't remove loops for which we can't solve the trip count. 1910db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // They could be infinite, in which case we'd be changing program behavior. 1920db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson ScalarEvolution& SE = getAnalysis<ScalarEvolution>(); 1930db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson SCEVHandle S = SE.getIterationCount(L); 1940db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson if (isa<SCEVCouldNotCompute>(S)) 1950db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson return false; 1960db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 1979862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Now that we know the removal is safe, remove the loop by changing the 1988b23bb792e539197fc4c913c0fcbdc8f39b74ab4Owen Anderson // branch from the preheader to go to the single exit block. 1990ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitBlock = exitBlocks[0]; 2008b23bb792e539197fc4c913c0fcbdc8f39b74ab4Owen Anderson BasicBlock* exitingBlock = exitingBlocks[0]; 2010ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 202e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Because we're deleting a large chunk of code at once, the sequence in which 203e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // we remove things is very important to avoid invalidation issues. Don't 204e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // mess with this unless you have good reason and know what you're doing. 205e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson 206e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Move simple loop-invariant expressions out of the loop, since they 207e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // might be needed by the exit phis. 2080ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 2090ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) 2100ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 2110ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ) { 2120ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson Instruction* I = BI++; 213cb41e6bf52e51b2cbf6871f63785af1c12a5fe70Dan Gohman if (!I->use_empty() && IsLoopInvariantInst(I, L)) 2140ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson I->moveBefore(preheader->getTerminator()); 2150ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2160ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 217e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Connect the preheader directly to the exit block. 2180ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson TerminatorInst* TI = preheader->getTerminator(); 2199862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson TI->replaceUsesOfWith(L->getHeader(), exitBlock); 2209862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson 221e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Rewrite phis in the exit block to get their inputs from 222e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // the preheader instead of the exiting block. 2230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock::iterator BI = exitBlock->begin(); 2240ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson while (PHINode* P = dyn_cast<PHINode>(BI)) { 2258b23bb792e539197fc4c913c0fcbdc8f39b74ab4Owen Anderson P->replaceUsesOfWith(exitingBlock, preheader); 2260ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI++; 2270ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2280ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2299862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Update the dominator tree and remove the instructions and blocks that will 2309862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // be deleted from the reference counting scheme. 2310ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DominatorTree& DT = getAnalysis<DominatorTree>(); 232d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman DominanceFrontier* DF = getAnalysisIfAvailable<DominanceFrontier>(); 2339862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallPtrSet<DomTreeNode*, 8> ChildNodes; 2340ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 2350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) { 236e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Move all of the block's children to be children of the preheader, which 237e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // allows us to remove the domtree entry for the block. 2389862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson ChildNodes.insert(DT[*LI]->begin(), DT[*LI]->end()); 2399862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson for (SmallPtrSet<DomTreeNode*, 8>::iterator DI = ChildNodes.begin(), 240d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman DE = ChildNodes.end(); DI != DE; ++DI) { 2410ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DT.changeImmediateDominator(*DI, DT[preheader]); 242d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman if (DF) DF->changeImmediateDominator((*DI)->getBlock(), preheader, &DT); 243d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman } 2440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2459862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson ChildNodes.clear(); 2460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DT.eraseNode(*LI); 247d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman if (DF) DF->removeBlock(*LI); 248d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman 2490db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // Remove instructions that we're deleting from ScalarEvolution. 2500ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 2510db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson BI != BE; ++BI) 2520db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson SE.deleteValueFromRecords(BI); 2530db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 2540db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson SE.deleteValueFromRecords(*LI); 2550ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2560db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // Remove the block from the reference counting scheme, so that we can 2570db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // delete it freely later. 2580ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson (*LI)->dropAllReferences(); 2590ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2600ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 261e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Erase the instructions and the blocks without having to worry 262e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // about ordering because we already dropped the references. 2639862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // NOTE: This iteration is safe because erasing the block does not remove its 2649862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // entry from the loop's block list. We do that in the next section. 2650ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 266cd5e6dda7e91af662f378e43842e6d2d55ec3057Owen Anderson LI != LE; ++LI) 2670ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson (*LI)->eraseFromParent(); 268e2abdd3ff0dd54a59edbd114ebb1d7728040a2d9Dan Gohman 269e2abdd3ff0dd54a59edbd114ebb1d7728040a2d9Dan Gohman // Tell ScalarEvolution that the loop is deleted. 270e2abdd3ff0dd54a59edbd114ebb1d7728040a2d9Dan Gohman SE.forgetLoopIterationCount(L); 271e2abdd3ff0dd54a59edbd114ebb1d7728040a2d9Dan Gohman 272e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Finally, the blocks from loopinfo. This has to happen late because 273e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // otherwise our loop iterators won't work. 2740ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 2750ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallPtrSet<BasicBlock*, 8> blocks; 2760ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson blocks.insert(L->block_begin(), L->block_end()); 2770ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (SmallPtrSet<BasicBlock*,8>::iterator I = blocks.begin(), 2780ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson E = blocks.end(); I != E; ++I) 2790ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson loopInfo.removeBlock(*I); 2800ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 281e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // The last step is to inform the loop pass manager that we've 282e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // eliminated this loop. 2830ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LPM.deleteLoopFromQueue(L); 2840ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2850ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson NumDeleted++; 2860ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2870ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 2880ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 289