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#include "llvm/Transforms/Scalar.h" 190ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/Analysis/LoopPass.h" 20301278719b67dcdd1159d9f91b4db5ef57f025c6Cameron Zwarich#include "llvm/Analysis/Dominators.h" 210db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson#include "llvm/Analysis/ScalarEvolution.h" 220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/ADT/Statistic.h" 230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson#include "llvm/ADT/SmallVector.h" 240ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Andersonusing namespace llvm; 250ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 260ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen AndersonSTATISTIC(NumDeleted, "Number of loops deleted"); 270ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 280ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Andersonnamespace { 293e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner class LoopDeletion : public LoopPass { 300ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson public: 310ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson static char ID; // Pass ID, replacement for typeid 32081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson LoopDeletion() : LoopPass(ID) { 33081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLoopDeletionPass(*PassRegistry::getPassRegistry()); 34081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Possibly eliminate loop L if it is dead. 370ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson bool runOnLoop(Loop* L, LPPassManager& LPM); 380ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 399862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson bool IsLoopDead(Loop* L, SmallVector<BasicBlock*, 4>& exitingBlocks, 40bdc017edacb713119b24ab269d250a82d62fffebDan Gohman SmallVector<BasicBlock*, 4>& exitBlocks, 41bdc017edacb713119b24ab269d250a82d62fffebDan Gohman bool &Changed, BasicBlock *Preheader); 42bdc017edacb713119b24ab269d250a82d62fffebDan Gohman 430ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson virtual void getAnalysisUsage(AnalysisUsage& AU) const { 440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequired<DominatorTree>(); 450ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequired<LoopInfo>(); 46052f0001588a1613f845c84c04b38ced28ad6711Dan Gohman AU.addRequired<ScalarEvolution>(); 470ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequiredID(LoopSimplifyID); 480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addRequiredID(LCSSAID); 490ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 500db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson AU.addPreserved<ScalarEvolution>(); 510ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreserved<DominatorTree>(); 520ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreserved<LoopInfo>(); 530ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreservedID(LoopSimplifyID); 540ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson AU.addPreservedID(LCSSAID); 550ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 560ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson }; 570ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 58844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 59844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar LoopDeletion::ID = 0; 602ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LoopDeletion, "loop-deletion", 612ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Delete dead loops", false, false) 622ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 632ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 642ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 652ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 662ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LCSSA) 672ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LoopDeletion, "loop-deletion", 68ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Delete dead loops", false, false) 690ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 70394f0441e06dafca29f0752cf400990a5b8fe4b1Daniel DunbarPass* llvm::createLoopDeletionPass() { 710396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Anderson return new LoopDeletion(); 720ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 730ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 749862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// IsLoopDead - Determined if a loop is dead. This assumes that we've already 759862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// checked for unique exit and exiting blocks, and that the code is in LCSSA 769862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// form. 779862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Andersonbool LoopDeletion::IsLoopDead(Loop* L, 789862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson SmallVector<BasicBlock*, 4>& exitingBlocks, 79bdc017edacb713119b24ab269d250a82d62fffebDan Gohman SmallVector<BasicBlock*, 4>& exitBlocks, 80bdc017edacb713119b24ab269d250a82d62fffebDan Gohman bool &Changed, BasicBlock *Preheader) { 810ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitBlock = exitBlocks[0]; 820ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 830ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Make sure that all PHI entries coming from the loop are loop invariant. 849862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Because the code is in LCSSA form, any values used outside of the loop 859862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // must pass through a PHI in the exit block, meaning that this check is 869862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // sufficient to guarantee that no loop-variant values are used outside 879862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // of the loop. 880ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock::iterator BI = exitBlock->begin(); 890ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson while (PHINode* P = dyn_cast<PHINode>(BI)) { 90c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich Value* incoming = P->getIncomingValueForBlock(exitingBlocks[0]); 91c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich 92c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich // Make sure all exiting blocks produce the same incoming value for the exit 93c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich // block. If there are different incoming values for different exiting 94c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich // blocks, then it is impossible to statically determine which value should 95c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich // be used. 96c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich for (unsigned i = 1; i < exitingBlocks.size(); ++i) { 97c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich if (incoming != P->getIncomingValueForBlock(exitingBlocks[i])) 98c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich return false; 99c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich } 100c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich 1010ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (Instruction* I = dyn_cast<Instruction>(incoming)) 102bdc017edacb713119b24ab269d250a82d62fffebDan Gohman if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) 1030ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 104c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich 105fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++BI; 1060ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1070ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1080ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Make sure that no instructions in the block have potential side-effects. 1099862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // This includes instructions that could write to memory, and loads that are 1109862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // marked volatile. This could be made more aggressive by using aliasing 1119862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // information to identify readonly and readnone calls. 1120ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 1130ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) { 1140ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 1150ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BI != BE; ++BI) { 1167af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands if (BI->mayHaveSideEffects()) 1170ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1180ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1190ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 1200ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1210ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return true; 1220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 1230ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1245f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the 1255f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// observable behavior of the program other than finite running time. Note 1265f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// we do ensure that this never remove a loop that might be infinite, as doing 1275f8b344255d1909d327df9a8322c2ad3733c328dOwen Anderson/// so could change the halting/non-halting nature of a program. 1289862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA 1299862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson/// in order to make various safety checks work. 1300396cd33ca2d879d1cf0e9b252ce43a760449fffOwen Andersonbool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { 1310ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // We can only remove the loop if there is a preheader that we can 1320ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // branch from after removing it. 1330ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* preheader = L->getLoopPreheader(); 1340ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (!preheader) 1350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 13732cc5f47fa6a544bb77afcdc92c37ba32bfc0c4fDan Gohman // If LoopSimplify form is not available, stay out of trouble. 13832cc5f47fa6a544bb77afcdc92c37ba32bfc0c4fDan Gohman if (!L->hasDedicatedExits()) 13932cc5f47fa6a544bb77afcdc92c37ba32bfc0c4fDan Gohman return false; 14032cc5f47fa6a544bb77afcdc92c37ba32bfc0c4fDan Gohman 1410ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // We can't remove loops that contain subloops. If the subloops were dead, 1420ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // they would already have been removed in earlier executions of this pass. 1430ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson if (L->begin() != L->end()) 1440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson return false; 1450ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1460db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson SmallVector<BasicBlock*, 4> exitingBlocks; 1470db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson L->getExitingBlocks(exitingBlocks); 1480db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 1490db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson SmallVector<BasicBlock*, 4> exitBlocks; 1500db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson L->getUniqueExitBlocks(exitBlocks); 1510db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 1520db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // We require that the loop only have a single exit block. Otherwise, we'd 1530db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // be in the situation of needing to be able to solve statically which exit 1540db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // block will be branched to, or trying to preserve the branching logic in 1550db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // a loop invariant manner. 1560db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson if (exitBlocks.size() != 1) 1579862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson return false; 1589862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson 1590ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson // Finally, we have to check that the loop really is dead. 160bdc017edacb713119b24ab269d250a82d62fffebDan Gohman bool Changed = false; 161bdc017edacb713119b24ab269d250a82d62fffebDan Gohman if (!IsLoopDead(L, exitingBlocks, exitBlocks, Changed, preheader)) 162bdc017edacb713119b24ab269d250a82d62fffebDan Gohman return Changed; 1630ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 1640db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // Don't remove loops for which we can't solve the trip count. 1650db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // They could be infinite, in which case we'd be changing program behavior. 1660db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson ScalarEvolution& SE = getAnalysis<ScalarEvolution>(); 167934af9cfe08ba402882b061364aa693d47855547Dan Gohman const SCEV *S = SE.getMaxBackedgeTakenCount(L); 1680db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson if (isa<SCEVCouldNotCompute>(S)) 169bdc017edacb713119b24ab269d250a82d62fffebDan Gohman return Changed; 1700db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson 1719862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Now that we know the removal is safe, remove the loop by changing the 1728b23bb792e539197fc4c913c0fcbdc8f39b74ab4Owen Anderson // branch from the preheader to go to the single exit block. 1730ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock* exitBlock = exitBlocks[0]; 1740ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 175e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Because we're deleting a large chunk of code at once, the sequence in which 176e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // we remove things is very important to avoid invalidation issues. Don't 177e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // mess with this unless you have good reason and know what you're doing. 17885ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman 17985ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman // Tell ScalarEvolution that the loop is deleted. Do this before 18085ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman // deleting the loop so that ScalarEvolution can look at the loop 18185ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman // to determine what it needs to clean up. 1824c7279ac726e338400626fca5a09b5533426eb6aDan Gohman SE.forgetLoop(L); 18385ebb0f66cf07ff071323ff314d58449decd4316Dan Gohman 184e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Connect the preheader directly to the exit block. 1850ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson TerminatorInst* TI = preheader->getTerminator(); 1869862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson TI->replaceUsesOfWith(L->getHeader(), exitBlock); 1879862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson 188e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Rewrite phis in the exit block to get their inputs from 189e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // the preheader instead of the exiting block. 190c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich BasicBlock* exitingBlock = exitingBlocks[0]; 1910ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson BasicBlock::iterator BI = exitBlock->begin(); 1920ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson while (PHINode* P = dyn_cast<PHINode>(BI)) { 19369254f67a54656ebf88fe854d0e8bf7fc58abda6Jay Foad int j = P->getBasicBlockIndex(exitingBlock); 19469254f67a54656ebf88fe854d0e8bf7fc58abda6Jay Foad assert(j >= 0 && "Can't find exiting block in exit block's phi node!"); 19569254f67a54656ebf88fe854d0e8bf7fc58abda6Jay Foad P->setIncomingBlock(j, preheader); 196c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich for (unsigned i = 1; i < exitingBlocks.size(); ++i) 197c4f3d51e12390f39f314451d868350e2a11a52b6Cameron Zwarich P->removeIncomingValue(exitingBlocks[i]); 198fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++BI; 1990ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2000ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2019862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // Update the dominator tree and remove the instructions and blocks that will 2029862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // be deleted from the reference counting scheme. 2030ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DominatorTree& DT = getAnalysis<DominatorTree>(); 20485bbd576ea3078a7cd9d8a17228f4c2dce35be2cDevang Patel SmallVector<DomTreeNode*, 8> ChildNodes; 2050ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 2060ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LI != LE; ++LI) { 207e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Move all of the block's children to be children of the preheader, which 208e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // allows us to remove the domtree entry for the block. 20985bbd576ea3078a7cd9d8a17228f4c2dce35be2cDevang Patel ChildNodes.insert(ChildNodes.begin(), DT[*LI]->begin(), DT[*LI]->end()); 21085bbd576ea3078a7cd9d8a17228f4c2dce35be2cDevang Patel for (SmallVector<DomTreeNode*, 8>::iterator DI = ChildNodes.begin(), 211d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman DE = ChildNodes.end(); DI != DE; ++DI) { 2120ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DT.changeImmediateDominator(*DI, DT[preheader]); 213d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman } 2140ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 2159862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson ChildNodes.clear(); 2160ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson DT.eraseNode(*LI); 217d0a90b987673e22985c3407f413c76eb104777c4Dan Gohman 2180db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // Remove the block from the reference counting scheme, so that we can 2190db198d7587951f47e9cc93db1fd5e6175ceb695Owen Anderson // delete it freely later. 2200ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson (*LI)->dropAllReferences(); 2210ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson } 2220ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 223e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Erase the instructions and the blocks without having to worry 224e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // about ordering because we already dropped the references. 2259862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // NOTE: This iteration is safe because erasing the block does not remove its 2269862f31533d09709c0c60b6c943e5ef8a3a5429fOwen Anderson // entry from the loop's block list. We do that in the next section. 2270ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 228cd5e6dda7e91af662f378e43842e6d2d55ec3057Owen Anderson LI != LE; ++LI) 2290ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson (*LI)->eraseFromParent(); 230e2abdd3ff0dd54a59edbd114ebb1d7728040a2d9Dan Gohman 231e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // Finally, the blocks from loopinfo. This has to happen late because 232e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // otherwise our loop iterators won't work. 2330ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 2340ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson SmallPtrSet<BasicBlock*, 8> blocks; 2350ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson blocks.insert(L->block_begin(), L->block_end()); 2360ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson for (SmallPtrSet<BasicBlock*,8>::iterator I = blocks.begin(), 2370ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson E = blocks.end(); I != E; ++I) 2380ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson loopInfo.removeBlock(*I); 2390ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 240e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // The last step is to inform the loop pass manager that we've 241e54cfdb32a0b8343b3fa1839d1284da9ef211792Owen Anderson // eliminated this loop. 2420ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson LPM.deleteLoopFromQueue(L); 243bdc017edacb713119b24ab269d250a82d62fffebDan Gohman Changed = true; 2440ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 245fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumDeleted; 2460ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson 247bdc017edacb713119b24ab269d250a82d62fffebDan Gohman return Changed; 2480ff7708a5bbde331f9f54fb955bf7a2e96af710eOwen Anderson} 249