1 //===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the Dead Loop Deletion Pass. This pass is responsible 11 // for eliminating loops with non-infinite computable trip counts that have no 12 // side effects or volatile instructions, and do not contribute to the 13 // computation of the function's return value. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "llvm/Transforms/Scalar.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/LoopPass.h" 21 #include "llvm/Analysis/ScalarEvolution.h" 22 #include "llvm/IR/Dominators.h" 23 using namespace llvm; 24 25 #define DEBUG_TYPE "loop-delete" 26 27 STATISTIC(NumDeleted, "Number of loops deleted"); 28 29 namespace { 30 class LoopDeletion : public LoopPass { 31 public: 32 static char ID; // Pass ID, replacement for typeid 33 LoopDeletion() : LoopPass(ID) { 34 initializeLoopDeletionPass(*PassRegistry::getPassRegistry()); 35 } 36 37 // Possibly eliminate loop L if it is dead. 38 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 39 40 void getAnalysisUsage(AnalysisUsage &AU) const override { 41 AU.addRequired<DominatorTreeWrapperPass>(); 42 AU.addRequired<LoopInfo>(); 43 AU.addRequired<ScalarEvolution>(); 44 AU.addRequiredID(LoopSimplifyID); 45 AU.addRequiredID(LCSSAID); 46 47 AU.addPreserved<ScalarEvolution>(); 48 AU.addPreserved<DominatorTreeWrapperPass>(); 49 AU.addPreserved<LoopInfo>(); 50 AU.addPreservedID(LoopSimplifyID); 51 AU.addPreservedID(LCSSAID); 52 } 53 54 private: 55 bool isLoopDead(Loop *L, SmallVectorImpl<BasicBlock *> &exitingBlocks, 56 SmallVectorImpl<BasicBlock *> &exitBlocks, 57 bool &Changed, BasicBlock *Preheader); 58 59 }; 60 } 61 62 char LoopDeletion::ID = 0; 63 INITIALIZE_PASS_BEGIN(LoopDeletion, "loop-deletion", 64 "Delete dead loops", false, false) 65 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 66 INITIALIZE_PASS_DEPENDENCY(LoopInfo) 67 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 68 INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 69 INITIALIZE_PASS_DEPENDENCY(LCSSA) 70 INITIALIZE_PASS_END(LoopDeletion, "loop-deletion", 71 "Delete dead loops", false, false) 72 73 Pass *llvm::createLoopDeletionPass() { 74 return new LoopDeletion(); 75 } 76 77 /// isLoopDead - Determined if a loop is dead. This assumes that we've already 78 /// checked for unique exit and exiting blocks, and that the code is in LCSSA 79 /// form. 80 bool LoopDeletion::isLoopDead(Loop *L, 81 SmallVectorImpl<BasicBlock *> &exitingBlocks, 82 SmallVectorImpl<BasicBlock *> &exitBlocks, 83 bool &Changed, BasicBlock *Preheader) { 84 BasicBlock *exitBlock = exitBlocks[0]; 85 86 // Make sure that all PHI entries coming from the loop are loop invariant. 87 // Because the code is in LCSSA form, any values used outside of the loop 88 // must pass through a PHI in the exit block, meaning that this check is 89 // sufficient to guarantee that no loop-variant values are used outside 90 // of the loop. 91 BasicBlock::iterator BI = exitBlock->begin(); 92 while (PHINode *P = dyn_cast<PHINode>(BI)) { 93 Value *incoming = P->getIncomingValueForBlock(exitingBlocks[0]); 94 95 // Make sure all exiting blocks produce the same incoming value for the exit 96 // block. If there are different incoming values for different exiting 97 // blocks, then it is impossible to statically determine which value should 98 // be used. 99 for (unsigned i = 1, e = exitingBlocks.size(); i < e; ++i) { 100 if (incoming != P->getIncomingValueForBlock(exitingBlocks[i])) 101 return false; 102 } 103 104 if (Instruction *I = dyn_cast<Instruction>(incoming)) 105 if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) 106 return false; 107 108 ++BI; 109 } 110 111 // Make sure that no instructions in the block have potential side-effects. 112 // This includes instructions that could write to memory, and loads that are 113 // marked volatile. This could be made more aggressive by using aliasing 114 // information to identify readonly and readnone calls. 115 for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 116 LI != LE; ++LI) { 117 for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); 118 BI != BE; ++BI) { 119 if (BI->mayHaveSideEffects()) 120 return false; 121 } 122 } 123 124 return true; 125 } 126 127 /// runOnLoop - Remove dead loops, by which we mean loops that do not impact the 128 /// observable behavior of the program other than finite running time. Note 129 /// we do ensure that this never remove a loop that might be infinite, as doing 130 /// so could change the halting/non-halting nature of a program. 131 /// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA 132 /// in order to make various safety checks work. 133 bool LoopDeletion::runOnLoop(Loop *L, LPPassManager &LPM) { 134 if (skipOptnoneFunction(L)) 135 return false; 136 137 // We can only remove the loop if there is a preheader that we can 138 // branch from after removing it. 139 BasicBlock *preheader = L->getLoopPreheader(); 140 if (!preheader) 141 return false; 142 143 // If LoopSimplify form is not available, stay out of trouble. 144 if (!L->hasDedicatedExits()) 145 return false; 146 147 // We can't remove loops that contain subloops. If the subloops were dead, 148 // they would already have been removed in earlier executions of this pass. 149 if (L->begin() != L->end()) 150 return false; 151 152 SmallVector<BasicBlock*, 4> exitingBlocks; 153 L->getExitingBlocks(exitingBlocks); 154 155 SmallVector<BasicBlock*, 4> exitBlocks; 156 L->getUniqueExitBlocks(exitBlocks); 157 158 // We require that the loop only have a single exit block. Otherwise, we'd 159 // be in the situation of needing to be able to solve statically which exit 160 // block will be branched to, or trying to preserve the branching logic in 161 // a loop invariant manner. 162 if (exitBlocks.size() != 1) 163 return false; 164 165 // Finally, we have to check that the loop really is dead. 166 bool Changed = false; 167 if (!isLoopDead(L, exitingBlocks, exitBlocks, Changed, preheader)) 168 return Changed; 169 170 // Don't remove loops for which we can't solve the trip count. 171 // They could be infinite, in which case we'd be changing program behavior. 172 ScalarEvolution &SE = getAnalysis<ScalarEvolution>(); 173 const SCEV *S = SE.getMaxBackedgeTakenCount(L); 174 if (isa<SCEVCouldNotCompute>(S)) 175 return Changed; 176 177 // Now that we know the removal is safe, remove the loop by changing the 178 // branch from the preheader to go to the single exit block. 179 BasicBlock *exitBlock = exitBlocks[0]; 180 181 // Because we're deleting a large chunk of code at once, the sequence in which 182 // we remove things is very important to avoid invalidation issues. Don't 183 // mess with this unless you have good reason and know what you're doing. 184 185 // Tell ScalarEvolution that the loop is deleted. Do this before 186 // deleting the loop so that ScalarEvolution can look at the loop 187 // to determine what it needs to clean up. 188 SE.forgetLoop(L); 189 190 // Connect the preheader directly to the exit block. 191 TerminatorInst *TI = preheader->getTerminator(); 192 TI->replaceUsesOfWith(L->getHeader(), exitBlock); 193 194 // Rewrite phis in the exit block to get their inputs from 195 // the preheader instead of the exiting block. 196 BasicBlock *exitingBlock = exitingBlocks[0]; 197 BasicBlock::iterator BI = exitBlock->begin(); 198 while (PHINode *P = dyn_cast<PHINode>(BI)) { 199 int j = P->getBasicBlockIndex(exitingBlock); 200 assert(j >= 0 && "Can't find exiting block in exit block's phi node!"); 201 P->setIncomingBlock(j, preheader); 202 for (unsigned i = 1; i < exitingBlocks.size(); ++i) 203 P->removeIncomingValue(exitingBlocks[i]); 204 ++BI; 205 } 206 207 // Update the dominator tree and remove the instructions and blocks that will 208 // be deleted from the reference counting scheme. 209 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 210 SmallVector<DomTreeNode*, 8> ChildNodes; 211 for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 212 LI != LE; ++LI) { 213 // Move all of the block's children to be children of the preheader, which 214 // allows us to remove the domtree entry for the block. 215 ChildNodes.insert(ChildNodes.begin(), DT[*LI]->begin(), DT[*LI]->end()); 216 for (SmallVectorImpl<DomTreeNode *>::iterator DI = ChildNodes.begin(), 217 DE = ChildNodes.end(); DI != DE; ++DI) { 218 DT.changeImmediateDominator(*DI, DT[preheader]); 219 } 220 221 ChildNodes.clear(); 222 DT.eraseNode(*LI); 223 224 // Remove the block from the reference counting scheme, so that we can 225 // delete it freely later. 226 (*LI)->dropAllReferences(); 227 } 228 229 // Erase the instructions and the blocks without having to worry 230 // about ordering because we already dropped the references. 231 // NOTE: This iteration is safe because erasing the block does not remove its 232 // entry from the loop's block list. We do that in the next section. 233 for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); 234 LI != LE; ++LI) 235 (*LI)->eraseFromParent(); 236 237 // Finally, the blocks from loopinfo. This has to happen late because 238 // otherwise our loop iterators won't work. 239 LoopInfo &loopInfo = getAnalysis<LoopInfo>(); 240 SmallPtrSet<BasicBlock*, 8> blocks; 241 blocks.insert(L->block_begin(), L->block_end()); 242 for (SmallPtrSet<BasicBlock*,8>::iterator I = blocks.begin(), 243 E = blocks.end(); I != E; ++I) 244 loopInfo.removeBlock(*I); 245 246 // The last step is to inform the loop pass manager that we've 247 // eliminated this loop. 248 LPM.deleteLoopFromQueue(L); 249 Changed = true; 250 251 ++NumDeleted; 252 253 return Changed; 254 } 255