LLVM API Documentation
00001 //===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the Dead Loop Deletion Pass. This pass is responsible 00011 // for eliminating loops with non-infinite computable trip counts that have no 00012 // side effects or volatile instructions, and do not contribute to the 00013 // computation of the function's return value. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #define DEBUG_TYPE "loop-delete" 00018 00019 #include "llvm/Transforms/Scalar.h" 00020 #include "llvm/Analysis/LoopPass.h" 00021 #include "llvm/Analysis/ScalarEvolution.h" 00022 #include "llvm/ADT/Statistic.h" 00023 #include "llvm/ADT/SmallVector.h" 00024 00025 using namespace llvm; 00026 00027 STATISTIC(NumDeleted, "Number of loops deleted"); 00028 00029 namespace { 00030 class VISIBILITY_HIDDEN LoopDeletion : public LoopPass { 00031 public: 00032 static char ID; // Pass ID, replacement for typeid 00033 LoopDeletion() : LoopPass(&ID) {} 00034 00035 // Possibly eliminate loop L if it is dead. 00036 bool runOnLoop(Loop* L, LPPassManager& LPM); 00037 00038 bool SingleDominatingExit(Loop* L, 00039 SmallVector<BasicBlock*, 4>& exitingBlocks); 00040 bool IsLoopDead(Loop* L, SmallVector<BasicBlock*, 4>& exitingBlocks, 00041 SmallVector<BasicBlock*, 4>& exitBlocks, 00042 bool &Changed, BasicBlock *Preheader); 00043 00044 virtual void getAnalysisUsage(AnalysisUsage& AU) const { 00045 AU.addRequired<ScalarEvolution>(); 00046 AU.addRequired<DominatorTree>(); 00047 AU.addRequired<LoopInfo>(); 00048 AU.addRequiredID(LoopSimplifyID); 00049 AU.addRequiredID(LCSSAID); 00050 00051 AU.addPreserved<ScalarEvolution>(); 00052 AU.addPreserved<DominatorTree>(); 00053 AU.addPreserved<LoopInfo>(); 00054 AU.addPreservedID(LoopSimplifyID); 00055 AU.addPreservedID(LCSSAID); 00056 AU.addPreserved<DominanceFrontier>(); 00057 } 00058 }; 00059 } 00060 00061 char LoopDeletion::ID = 0; 00062 static RegisterPass<LoopDeletion> X("loop-deletion", "Delete dead loops"); 00063 00064 Pass* llvm::createLoopDeletionPass() { 00065 return new LoopDeletion(); 00066 } 00067 00068 /// SingleDominatingExit - Checks that there is only a single blocks that 00069 /// branches out of the loop, and that it also g the latch block. Loops 00070 /// with multiple or non-latch-dominating exiting blocks could be dead, but we'd 00071 /// have to do more extensive analysis to make sure, for instance, that the 00072 /// control flow logic involved was or could be made loop-invariant. 00073 bool LoopDeletion::SingleDominatingExit(Loop* L, 00074 SmallVector<BasicBlock*, 4>& exitingBlocks) { 00075 00076 if (exitingBlocks.size() != 1) 00077 return false; 00078 00079 BasicBlock* latch = L->getLoopLatch(); 00080 if (!latch) 00081 return false; 00082 00083 DominatorTree& DT = getAnalysis<DominatorTree>(); 00084 return DT.dominates(exitingBlocks[0], latch); 00085 } 00086 00087 /// IsLoopDead - Determined if a loop is dead. This assumes that we've already 00088 /// checked for unique exit and exiting blocks, and that the code is in LCSSA 00089 /// form. 00090 bool LoopDeletion::IsLoopDead(Loop* L, 00091 SmallVector<BasicBlock*, 4>& exitingBlocks, 00092 SmallVector<BasicBlock*, 4>& exitBlocks, 00093 bool &Changed, BasicBlock *Preheader) { 00094 BasicBlock* exitingBlock = exitingBlocks[0]; 00095 BasicBlock* exitBlock = exitBlocks[0]; 00096 00097 // Make sure that all PHI entries coming from the loop are loop invariant. 00098 // Because the code is in LCSSA form, any values used outside of the loop 00099 // must pass through a PHI in the exit block, meaning that this check is 00100 // sufficient to guarantee that no loop-variant values are used outside 00101 // of the loop. 00102 BasicBlock::iterator BI = exitBlock->begin(); 00103 while (PHINode* P = dyn_cast<PHINode>(BI)) { 00104 Value* incoming = P->getIncomingValueForBlock(exitingBlock); 00105 if (Instruction* I = dyn_cast<Instruction>(incoming)) 00106 if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) 00107 return false; 00108 00109 BI++; 00110 } 00111 00112 // Make sure that no instructions in the block have potential side-effects. 00113 // This includes instructions that could write to memory, and loads that are 00114 // marked volatile. This could be made more aggressive by using aliasing 00115 // information to identify readonly and readnone calls. 00116 for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 00117 LI != LE; ++LI) { 00118 for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 00119 BI != BE; ++BI) { 00120 if (BI->mayHaveSideEffects()) 00121 return false; 00122 } 00123 } 00124 00125 return true; 00126 } 00127 00128 /// runOnLoop - Remove dead loops, by which we mean loops that do not impact the 00129 /// observable behavior of the program other than finite running time. Note 00130 /// we do ensure that this never remove a loop that might be infinite, as doing 00131 /// so could change the halting/non-halting nature of a program. 00132 /// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA 00133 /// in order to make various safety checks work. 00134 bool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { 00135 // We can only remove the loop if there is a preheader that we can 00136 // branch from after removing it. 00137 BasicBlock* preheader = L->getLoopPreheader(); 00138 if (!preheader) 00139 return false; 00140 00141 // We can't remove loops that contain subloops. If the subloops were dead, 00142 // they would already have been removed in earlier executions of this pass. 00143 if (L->begin() != L->end()) 00144 return false; 00145 00146 SmallVector<BasicBlock*, 4> exitingBlocks; 00147 L->getExitingBlocks(exitingBlocks); 00148 00149 SmallVector<BasicBlock*, 4> exitBlocks; 00150 L->getUniqueExitBlocks(exitBlocks); 00151 00152 // We require that the loop only have a single exit block. Otherwise, we'd 00153 // be in the situation of needing to be able to solve statically which exit 00154 // block will be branched to, or trying to preserve the branching logic in 00155 // a loop invariant manner. 00156 if (exitBlocks.size() != 1) 00157 return false; 00158 00159 // Loops with multiple exits or exits that don't dominate the latch 00160 // are too complicated to handle correctly. 00161 if (!SingleDominatingExit(L, exitingBlocks)) 00162 return false; 00163 00164 // Finally, we have to check that the loop really is dead. 00165 bool Changed = false; 00166 if (!IsLoopDead(L, exitingBlocks, exitBlocks, Changed, preheader)) 00167 return Changed; 00168 00169 // Don't remove loops for which we can't solve the trip count. 00170 // They could be infinite, in which case we'd be changing program behavior. 00171 ScalarEvolution& SE = getAnalysis<ScalarEvolution>(); 00172 const SCEV *S = SE.getBackedgeTakenCount(L); 00173 if (isa<SCEVCouldNotCompute>(S)) 00174 return Changed; 00175 00176 // Now that we know the removal is safe, remove the loop by changing the 00177 // branch from the preheader to go to the single exit block. 00178 BasicBlock* exitBlock = exitBlocks[0]; 00179 BasicBlock* exitingBlock = exitingBlocks[0]; 00180 00181 // Because we're deleting a large chunk of code at once, the sequence in which 00182 // we remove things is very important to avoid invalidation issues. Don't 00183 // mess with this unless you have good reason and know what you're doing. 00184 00185 // Tell ScalarEvolution that the loop is deleted. Do this before 00186 // deleting the loop so that ScalarEvolution can look at the loop 00187 // to determine what it needs to clean up. 00188 SE.forgetLoopBackedgeTakenCount(L); 00189 00190 // Connect the preheader directly to the exit block. 00191 TerminatorInst* TI = preheader->getTerminator(); 00192 TI->replaceUsesOfWith(L->getHeader(), exitBlock); 00193 00194 // Rewrite phis in the exit block to get their inputs from 00195 // the preheader instead of the exiting block. 00196 BasicBlock::iterator BI = exitBlock->begin(); 00197 while (PHINode* P = dyn_cast<PHINode>(BI)) { 00198 P->replaceUsesOfWith(exitingBlock, preheader); 00199 BI++; 00200 } 00201 00202 // Update the dominator tree and remove the instructions and blocks that will 00203 // be deleted from the reference counting scheme. 00204 DominatorTree& DT = getAnalysis<DominatorTree>(); 00205 DominanceFrontier* DF = getAnalysisIfAvailable<DominanceFrontier>(); 00206 SmallPtrSet<DomTreeNode*, 8> ChildNodes; 00207 for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 00208 LI != LE; ++LI) { 00209 // Move all of the block's children to be children of the preheader, which 00210 // allows us to remove the domtree entry for the block. 00211 ChildNodes.insert(DT[*LI]->begin(), DT[*LI]->end()); 00212 for (SmallPtrSet<DomTreeNode*, 8>::iterator DI = ChildNodes.begin(), 00213 DE = ChildNodes.end(); DI != DE; ++DI) { 00214 DT.changeImmediateDominator(*DI, DT[preheader]); 00215 if (DF) DF->changeImmediateDominator((*DI)->getBlock(), preheader, &DT); 00216 } 00217 00218 ChildNodes.clear(); 00219 DT.eraseNode(*LI); 00220 if (DF) DF->removeBlock(*LI); 00221 00222 // Remove the block from the reference counting scheme, so that we can 00223 // delete it freely later. 00224 (*LI)->dropAllReferences(); 00225 } 00226 00227 // Erase the instructions and the blocks without having to worry 00228 // about ordering because we already dropped the references. 00229 // NOTE: This iteration is safe because erasing the block does not remove its 00230 // entry from the loop's block list. We do that in the next section. 00231 for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 00232 LI != LE; ++LI) 00233 (*LI)->eraseFromParent(); 00234 00235 // Finally, the blocks from loopinfo. This has to happen late because 00236 // otherwise our loop iterators won't work. 00237 LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 00238 SmallPtrSet<BasicBlock*, 8> blocks; 00239 blocks.insert(L->block_begin(), L->block_end()); 00240 for (SmallPtrSet<BasicBlock*,8>::iterator I = blocks.begin(), 00241 E = blocks.end(); I != E; ++I) 00242 loopInfo.removeBlock(*I); 00243 00244 // The last step is to inform the loop pass manager that we've 00245 // eliminated this loop. 00246 LPM.deleteLoopFromQueue(L); 00247 Changed = true; 00248 00249 NumDeleted++; 00250 00251 return Changed; 00252 }