LoopDeletion.cpp revision 85ebb0f66cf07ff071323ff314d58449decd4316
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) { 1397af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands if (BI->mayHaveSideEffects()) 1400ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1410ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1420ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1430ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 1450ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 1460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1475f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the 1485f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// observable behavior of the program other than finite running time. Note 1495f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// we do ensure that this never remove a loop that might be infinite, as doing 1505f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// so could change the halting/non-halting nature of a program. 1519862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA 1529862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// in order to make various safety checks work. 1530396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Andersonbool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { 1540ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // We can only remove the loop if there is a preheader that we can 1550ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // branch from after removing it. 1560ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* preheader = L->getLoopPreheader(); 1570ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!preheader) 1580ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1590ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1600ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // We can't remove loops that contain subloops. If the subloops were dead, 1610ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // they would already have been removed in earlier executions of this pass. 1620ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (L->begin() != L->end()) 1630ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1640ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1650db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson SmallVector<BasicBlock*, 4> exitingBlocks; 1660db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson L->getExitingBlocks(exitingBlocks); 1670db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 1680db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson SmallVector<BasicBlock*, 4> exitBlocks; 1690db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson L->getUniqueExitBlocks(exitBlocks); 1700db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 1710db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // We require that the loop only have a single exit block. Otherwise, we'd 1720db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // be in the situation of needing to be able to solve statically which exit 1730db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // block will be branched to, or trying to preserve the branching logic in 1740db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // a loop invariant manner. 1750db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson if (exitBlocks.size() != 1) 1769862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 1779862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson 1780ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Loops with multiple exits or exits that don't dominate the latch 1790ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // are too complicated to handle correctly. 1809862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson if (!SingleDominatingExit(L, exitingBlocks)) 1810ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1820ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1830ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Finally, we have to check that the loop really is dead. 1849862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson if (!IsLoopDead(L, exitingBlocks, exitBlocks)) 1850ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1860ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1870db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // Don't remove loops for which we can't solve the trip count. 1880db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // They could be infinite, in which case we'd be changing program behavior. 1890db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson ScalarEvolution& SE = getAnalysis<ScalarEvolution>(); 1900bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *S = SE.getBackedgeTakenCount(L); 1910db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson if (isa<SCEVCouldNotCompute>(S)) 1920db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson return false; 1930db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 1949862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Now that we know the removal is safe, remove the loop by changing the 1958b23bb792e539197fc4c913c0fcbdc8f39b74ab4Owen Anderson // branch from the preheader to go to the single exit block. 1960ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitBlock = exitBlocks[0]; 1978b23bb792e539197fc4c913c0fcbdc8f39b74ab4Owen Anderson BasicBlock* exitingBlock = exitingBlocks[0]; 1980ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 199e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Because we're deleting a large chunk of code at once, the sequence in which 200e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // we remove things is very important to avoid invalidation issues. Don't 201e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // mess with this unless you have good reason and know what you're doing. 20285ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman 20385ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman // Tell ScalarEvolution that the loop is deleted. Do this before 20485ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman // deleting the loop so that ScalarEvolution can look at the loop 20585ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman // to determine what it needs to clean up. 20685ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman SE.forgetLoopBackedgeTakenCount(L); 20785ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman 208e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Move simple loop-invariant expressions out of the loop, since they 209e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // might be needed by the exit phis. 2100ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 2110ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) 2120ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 2130ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ) { 2140ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson Instruction* I = BI++; 215cb41e6bf52e51b2cbf6871f63785af1c12a5fe70Dan Gohman if (!I->use_empty() && IsLoopInvariantInst(I, L)) 2160ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson I->moveBefore(preheader->getTerminator()); 2170ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2180ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 219e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Connect the preheader directly to the exit block. 2200ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson TerminatorInst* TI = preheader->getTerminator(); 2219862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson TI->replaceUsesOfWith(L->getHeader(), exitBlock); 2229862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson 223e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Rewrite phis in the exit block to get their inputs from 224e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // the preheader instead of the exiting block. 2250ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock::iterator BI = exitBlock->begin(); 2260ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson while (PHINode* P = dyn_cast<PHINode>(BI)) { 2278b23bb792e539197fc4c913c0fcbdc8f39b74ab4Owen Anderson P->replaceUsesOfWith(exitingBlock, preheader); 2280ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI++; 2290ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2300ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2319862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Update the dominator tree and remove the instructions and blocks that will 2329862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // be deleted from the reference counting scheme. 2330ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DominatorTree& DT = getAnalysis<DominatorTree>(); 234d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman DominanceFrontier* DF = getAnalysisIfAvailable<DominanceFrontier>(); 2359862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallPtrSet<DomTreeNode*, 8> ChildNodes; 2360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 2370ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) { 238e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Move all of the block's children to be children of the preheader, which 239e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // allows us to remove the domtree entry for the block. 2409862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson ChildNodes.insert(DT[*LI]->begin(), DT[*LI]->end()); 2419862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson for (SmallPtrSet<DomTreeNode*, 8>::iterator DI = ChildNodes.begin(), 242d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman DE = ChildNodes.end(); DI != DE; ++DI) { 2430ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DT.changeImmediateDominator(*DI, DT[preheader]); 244d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman if (DF) DF->changeImmediateDominator((*DI)->getBlock(), preheader, &DT); 245d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman } 2460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2479862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson ChildNodes.clear(); 2480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DT.eraseNode(*LI); 249d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman if (DF) DF->removeBlock(*LI); 250d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman 2510db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // Remove the block from the reference counting scheme, so that we can 2520db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // delete it freely later. 2530ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson (*LI)->dropAllReferences(); 2540ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2550ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 256e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Erase the instructions and the blocks without having to worry 257e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // about ordering because we already dropped the references. 2589862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // NOTE: This iteration is safe because erasing the block does not remove its 2599862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // entry from the loop's block list. We do that in the next section. 2600ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 261cd5e6dda7e91af662f378e43842e6d2d55ec3057Owen Anderson LI != LE; ++LI) 2620ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson (*LI)->eraseFromParent(); 263e2abdd3ff0dd54a59edbd114ebb1d7728040a2d9Dan Gohman 264e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Finally, the blocks from loopinfo. This has to happen late because 265e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // otherwise our loop iterators won't work. 2660ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 2670ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallPtrSet<BasicBlock*, 8> blocks; 2680ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson blocks.insert(L->block_begin(), L->block_end()); 2690ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (SmallPtrSet<BasicBlock*,8>::iterator I = blocks.begin(), 2700ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson E = blocks.end(); I != E; ++I) 2710ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson loopInfo.removeBlock(*I); 2720ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 273e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // The last step is to inform the loop pass manager that we've 274e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // eliminated this loop. 2750ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LPM.deleteLoopFromQueue(L); 2760ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2770ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson NumDeleted++; 2780ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2790ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 2800ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 281