LoopDeletion.cpp revision 256281
1188413Sthompsa//===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===// 2188413Sthompsa// 3188413Sthompsa// The LLVM Compiler Infrastructure 4188413Sthompsa// 5188413Sthompsa// This file is distributed under the University of Illinois Open Source 6188413Sthompsa// License. See LICENSE.TXT for details. 7188413Sthompsa// 8188413Sthompsa//===----------------------------------------------------------------------===// 9188413Sthompsa// 10188413Sthompsa// This file implements the Dead Loop Deletion Pass. This pass is responsible 11188413Sthompsa// for eliminating loops with non-infinite computable trip counts that have no 12188413Sthompsa// side effects or volatile instructions, and do not contribute to the 13188413Sthompsa// computation of the function's return value. 14188413Sthompsa// 15188413Sthompsa//===----------------------------------------------------------------------===// 16188413Sthompsa 17188413Sthompsa#define DEBUG_TYPE "loop-delete" 18188413Sthompsa#include "llvm/Transforms/Scalar.h" 19188413Sthompsa#include "llvm/ADT/SmallVector.h" 20188413Sthompsa#include "llvm/ADT/Statistic.h" 21188413Sthompsa#include "llvm/Analysis/Dominators.h" 22188746Sthompsa#include "llvm/Analysis/LoopPass.h" 23188942Sthompsa#include "llvm/Analysis/ScalarEvolution.h" 24188942Sthompsausing namespace llvm; 25188942Sthompsa 26188413SthompsaSTATISTIC(NumDeleted, "Number of loops deleted"); 27188413Sthompsa 28188413Sthompsanamespace { 29188942Sthompsa class LoopDeletion : public LoopPass { 30188942Sthompsa public: 31188942Sthompsa static char ID; // Pass ID, replacement for typeid 32188942Sthompsa LoopDeletion() : LoopPass(ID) { 33188942Sthompsa initializeLoopDeletionPass(*PassRegistry::getPassRegistry()); 34188942Sthompsa } 35188942Sthompsa 36188413Sthompsa // Possibly eliminate loop L if it is dead. 37188942Sthompsa bool runOnLoop(Loop *L, LPPassManager &LPM); 38188413Sthompsa 39188413Sthompsa virtual void getAnalysisUsage(AnalysisUsage &AU) const { 40188413Sthompsa AU.addRequired<DominatorTree>(); 41188413Sthompsa AU.addRequired<LoopInfo>(); 42188664Sthompsa AU.addRequired<ScalarEvolution>(); 43188664Sthompsa AU.addRequiredID(LoopSimplifyID); 44188413Sthompsa AU.addRequiredID(LCSSAID); 45188413Sthompsa 46188413Sthompsa AU.addPreserved<ScalarEvolution>(); 47188413Sthompsa AU.addPreserved<DominatorTree>(); 48188413Sthompsa AU.addPreserved<LoopInfo>(); 49188413Sthompsa AU.addPreservedID(LoopSimplifyID); 50188413Sthompsa AU.addPreservedID(LCSSAID); 51188413Sthompsa } 52188413Sthompsa 53188413Sthompsa private: 54188413Sthompsa bool isLoopDead(Loop *L, SmallVector<BasicBlock*, 4> &exitingBlocks, 55188413Sthompsa SmallVector<BasicBlock*, 4> &exitBlocks, 56188413Sthompsa bool &Changed, BasicBlock *Preheader); 57188413Sthompsa 58188413Sthompsa }; 59188413Sthompsa} 60188413Sthompsa 61188413Sthompsachar LoopDeletion::ID = 0; 62188413SthompsaINITIALIZE_PASS_BEGIN(LoopDeletion, "loop-deletion", 63188413Sthompsa "Delete dead loops", false, false) 64188413SthompsaINITIALIZE_PASS_DEPENDENCY(DominatorTree) 65188413SthompsaINITIALIZE_PASS_DEPENDENCY(LoopInfo) 66188413SthompsaINITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 67188413SthompsaINITIALIZE_PASS_DEPENDENCY(LoopSimplify) 68188413SthompsaINITIALIZE_PASS_DEPENDENCY(LCSSA) 69188413SthompsaINITIALIZE_PASS_END(LoopDeletion, "loop-deletion", 70188413Sthompsa "Delete dead loops", false, false) 71188413Sthompsa 72188413SthompsaPass *llvm::createLoopDeletionPass() { 73188413Sthompsa return new LoopDeletion(); 74188413Sthompsa} 75188413Sthompsa 76188413Sthompsa/// isLoopDead - Determined if a loop is dead. This assumes that we've already 77188413Sthompsa/// checked for unique exit and exiting blocks, and that the code is in LCSSA 78188413Sthompsa/// form. 79188413Sthompsabool LoopDeletion::isLoopDead(Loop *L, 80188413Sthompsa SmallVector<BasicBlock*, 4> &exitingBlocks, 81188413Sthompsa SmallVector<BasicBlock*, 4> &exitBlocks, 82188413Sthompsa bool &Changed, BasicBlock *Preheader) { 83188413Sthompsa BasicBlock *exitBlock = exitBlocks[0]; 84188413Sthompsa 85188413Sthompsa // Make sure that all PHI entries coming from the loop are loop invariant. 86188413Sthompsa // Because the code is in LCSSA form, any values used outside of the loop 87188413Sthompsa // must pass through a PHI in the exit block, meaning that this check is 88188413Sthompsa // sufficient to guarantee that no loop-variant values are used outside 89188413Sthompsa // of the loop. 90188413Sthompsa BasicBlock::iterator BI = exitBlock->begin(); 91188413Sthompsa while (PHINode *P = dyn_cast<PHINode>(BI)) { 92188413Sthompsa Value *incoming = P->getIncomingValueForBlock(exitingBlocks[0]); 93188413Sthompsa 94188413Sthompsa // Make sure all exiting blocks produce the same incoming value for the exit 95188413Sthompsa // block. If there are different incoming values for different exiting 96188413Sthompsa // blocks, then it is impossible to statically determine which value should 97188413Sthompsa // be used. 98188413Sthompsa for (unsigned i = 1, e = exitingBlocks.size(); i < e; ++i) { 99189265Sthompsa if (incoming != P->getIncomingValueForBlock(exitingBlocks[i])) 100188413Sthompsa return false; 101188413Sthompsa } 102188413Sthompsa 103188413Sthompsa if (Instruction *I = dyn_cast<Instruction>(incoming)) 104188413Sthompsa if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) 105188413Sthompsa return false; 106188413Sthompsa 107188413Sthompsa ++BI; 108188413Sthompsa } 109188413Sthompsa 110188413Sthompsa // Make sure that no instructions in the block have potential side-effects. 111188413Sthompsa // This includes instructions that could write to memory, and loads that are 112188413Sthompsa // marked volatile. This could be made more aggressive by using aliasing 113188413Sthompsa // information to identify readonly and readnone calls. 114188413Sthompsa for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 115188413Sthompsa LI != LE; ++LI) { 116188413Sthompsa for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 117188413Sthompsa BI != BE; ++BI) { 118188413Sthompsa if (BI->mayHaveSideEffects()) 119188413Sthompsa return false; 120188413Sthompsa } 121188413Sthompsa } 122188413Sthompsa 123188413Sthompsa return true; 124188413Sthompsa} 125188413Sthompsa 126188413Sthompsa/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the 127188413Sthompsa/// observable behavior of the program other than finite running time. Note 128188413Sthompsa/// we do ensure that this never remove a loop that might be infinite, as doing 129188413Sthompsa/// so could change the halting/non-halting nature of a program. 130188413Sthompsa/// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA 131190734Sthompsa/// in order to make various safety checks work. 132190734Sthompsabool LoopDeletion::runOnLoop(Loop *L, LPPassManager &LPM) { 133190734Sthompsa // We can only remove the loop if there is a preheader that we can 134188413Sthompsa // branch from after removing it. 135188413Sthompsa BasicBlock *preheader = L->getLoopPreheader(); 136188413Sthompsa if (!preheader) 137188413Sthompsa return false; 138188413Sthompsa 139188413Sthompsa // If LoopSimplify form is not available, stay out of trouble. 140190734Sthompsa if (!L->hasDedicatedExits()) 141190734Sthompsa return false; 142190734Sthompsa 143188413Sthompsa // We can't remove loops that contain subloops. If the subloops were dead, 144188413Sthompsa // they would already have been removed in earlier executions of this pass. 145188413Sthompsa if (L->begin() != L->end()) 146188413Sthompsa return false; 147188413Sthompsa 148188413Sthompsa SmallVector<BasicBlock*, 4> exitingBlocks; 149188413Sthompsa L->getExitingBlocks(exitingBlocks); 150188413Sthompsa 151188413Sthompsa SmallVector<BasicBlock*, 4> exitBlocks; 152188413Sthompsa L->getUniqueExitBlocks(exitBlocks); 153188413Sthompsa 154188413Sthompsa // We require that the loop only have a single exit block. Otherwise, we'd 155188413Sthompsa // be in the situation of needing to be able to solve statically which exit 156188413Sthompsa // block will be branched to, or trying to preserve the branching logic in 157188413Sthompsa // a loop invariant manner. 158188413Sthompsa if (exitBlocks.size() != 1) 159188413Sthompsa return false; 160188413Sthompsa 161188413Sthompsa // Finally, we have to check that the loop really is dead. 162188413Sthompsa bool Changed = false; 163188413Sthompsa if (!isLoopDead(L, exitingBlocks, exitBlocks, Changed, preheader)) 164188413Sthompsa return Changed; 165188413Sthompsa 166188413Sthompsa // Don't remove loops for which we can't solve the trip count. 167188413Sthompsa // They could be infinite, in which case we'd be changing program behavior. 168188413Sthompsa ScalarEvolution &SE = getAnalysis<ScalarEvolution>(); 169188413Sthompsa const SCEV *S = SE.getMaxBackedgeTakenCount(L); 170188413Sthompsa if (isa<SCEVCouldNotCompute>(S)) 171188413Sthompsa return Changed; 172188413Sthompsa 173188413Sthompsa // Now that we know the removal is safe, remove the loop by changing the 174188413Sthompsa // branch from the preheader to go to the single exit block. 175188413Sthompsa BasicBlock *exitBlock = exitBlocks[0]; 176188413Sthompsa 177188413Sthompsa // Because we're deleting a large chunk of code at once, the sequence in which 178188413Sthompsa // we remove things is very important to avoid invalidation issues. Don't 179188413Sthompsa // mess with this unless you have good reason and know what you're doing. 180188413Sthompsa 181188413Sthompsa // Tell ScalarEvolution that the loop is deleted. Do this before 182188413Sthompsa // deleting the loop so that ScalarEvolution can look at the loop 183188413Sthompsa // to determine what it needs to clean up. 184188413Sthompsa SE.forgetLoop(L); 185188413Sthompsa 186188413Sthompsa // Connect the preheader directly to the exit block. 187188413Sthompsa TerminatorInst *TI = preheader->getTerminator(); 188188413Sthompsa TI->replaceUsesOfWith(L->getHeader(), exitBlock); 189188413Sthompsa 190188413Sthompsa // Rewrite phis in the exit block to get their inputs from 191188413Sthompsa // the preheader instead of the exiting block. 192188664Sthompsa BasicBlock *exitingBlock = exitingBlocks[0]; 193188413Sthompsa BasicBlock::iterator BI = exitBlock->begin(); 194188413Sthompsa while (PHINode *P = dyn_cast<PHINode>(BI)) { 195188413Sthompsa int j = P->getBasicBlockIndex(exitingBlock); 196188413Sthompsa assert(j >= 0 && "Can't find exiting block in exit block's phi node!"); 197189275Sthompsa P->setIncomingBlock(j, preheader); 198188942Sthompsa for (unsigned i = 1; i < exitingBlocks.size(); ++i) 199188942Sthompsa P->removeIncomingValue(exitingBlocks[i]); 200188664Sthompsa ++BI; 201188413Sthompsa } 202188413Sthompsa 203188413Sthompsa // Update the dominator tree and remove the instructions and blocks that will 204188413Sthompsa // be deleted from the reference counting scheme. 205188413Sthompsa DominatorTree &DT = getAnalysis<DominatorTree>(); 206188413Sthompsa SmallVector<DomTreeNode*, 8> ChildNodes; 207188413Sthompsa for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 208188413Sthompsa LI != LE; ++LI) { 209188413Sthompsa // Move all of the block's children to be children of the preheader, which 210188413Sthompsa // allows us to remove the domtree entry for the block. 211188413Sthompsa ChildNodes.insert(ChildNodes.begin(), DT[*LI]->begin(), DT[*LI]->end()); 212188413Sthompsa for (SmallVector<DomTreeNode*, 8>::iterator DI = ChildNodes.begin(), 213188413Sthompsa DE = ChildNodes.end(); DI != DE; ++DI) { 214188413Sthompsa DT.changeImmediateDominator(*DI, DT[preheader]); 215188413Sthompsa } 216188413Sthompsa 217188413Sthompsa ChildNodes.clear(); 218188413Sthompsa DT.eraseNode(*LI); 219188413Sthompsa 220188413Sthompsa // Remove the block from the reference counting scheme, so that we can 221188413Sthompsa // delete it freely later. 222188413Sthompsa (*LI)->dropAllReferences(); 223188413Sthompsa } 224188413Sthompsa 225188413Sthompsa // Erase the instructions and the blocks without having to worry 226188413Sthompsa // about ordering because we already dropped the references. 227188413Sthompsa // NOTE: This iteration is safe because erasing the block does not remove its 228188413Sthompsa // entry from the loop's block list. We do that in the next section. 229188413Sthompsa for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 230188413Sthompsa LI != LE; ++LI) 231189265Sthompsa (*LI)->eraseFromParent(); 232188413Sthompsa 233188413Sthompsa // Finally, the blocks from loopinfo. This has to happen late because 234188413Sthompsa // otherwise our loop iterators won't work. 235188413Sthompsa LoopInfo &loopInfo = getAnalysis<LoopInfo>(); 236188413Sthompsa SmallPtrSet<BasicBlock*, 8> blocks; 237189265Sthompsa blocks.insert(L->block_begin(), L->block_end()); 238188413Sthompsa for (SmallPtrSet<BasicBlock*,8>::iterator I = blocks.begin(), 239188413Sthompsa E = blocks.end(); I != E; ++I) 240188413Sthompsa loopInfo.removeBlock(*I); 241188413Sthompsa 242188413Sthompsa // The last step is to inform the loop pass manager that we've 243188413Sthompsa // eliminated this loop. 244189265Sthompsa LPM.deleteLoopFromQueue(L); 245188413Sthompsa Changed = true; 246188413Sthompsa 247189265Sthompsa ++NumDeleted; 248188413Sthompsa 249188413Sthompsa return Changed; 250189265Sthompsa} 251188413Sthompsa