1 //===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the Dead Loop Deletion Pass. This pass is responsible 10 // for eliminating loops with non-infinite computable trip counts that have no 11 // side effects or volatile instructions, and do not contribute to the 12 // computation of the function's return value. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/Transforms/Scalar/LoopDeletion.h" 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/Analysis/GlobalsModRef.h" 20 #include "llvm/Analysis/LoopPass.h" 21 #include "llvm/IR/Dominators.h" 22 #include "llvm/IR/PatternMatch.h" 23 #include "llvm/Transforms/Scalar.h" 24 #include "llvm/Transforms/Scalar/LoopPassManager.h" 25 #include "llvm/Transforms/Utils/LoopUtils.h" 26 using namespace llvm; 27 28 #define DEBUG_TYPE "loop-delete" 29 30 STATISTIC(NumDeleted, "Number of loops deleted"); 31 32 enum class LoopDeletionResult { 33 Unmodified, 34 Modified, 35 Deleted, 36 }; 37 38 /// Determines if a loop is dead. 39 /// 40 /// This assumes that we've already checked for unique exit and exiting blocks, 41 /// and that the code is in LCSSA form. 42 static bool isLoopDead(Loop *L, ScalarEvolution &SE, 43 SmallVectorImpl<BasicBlock *> &ExitingBlocks, 44 BasicBlock *ExitBlock, bool &Changed, 45 BasicBlock *Preheader) { 46 // Make sure that all PHI entries coming from the loop are loop invariant. 47 // Because the code is in LCSSA form, any values used outside of the loop 48 // must pass through a PHI in the exit block, meaning that this check is 49 // sufficient to guarantee that no loop-variant values are used outside 50 // of the loop. 51 bool AllEntriesInvariant = true; 52 bool AllOutgoingValuesSame = true; 53 for (PHINode &P : ExitBlock->phis()) { 54 Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]); 55 56 // Make sure all exiting blocks produce the same incoming value for the exit 57 // block. If there are different incoming values for different exiting 58 // blocks, then it is impossible to statically determine which value should 59 // be used. 60 AllOutgoingValuesSame = 61 all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) { 62 return incoming == P.getIncomingValueForBlock(BB); 63 }); 64 65 if (!AllOutgoingValuesSame) 66 break; 67 68 if (Instruction *I = dyn_cast<Instruction>(incoming)) 69 if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) { 70 AllEntriesInvariant = false; 71 break; 72 } 73 } 74 75 if (Changed) 76 SE.forgetLoopDispositions(L); 77 78 if (!AllEntriesInvariant || !AllOutgoingValuesSame) 79 return false; 80 81 // Make sure that no instructions in the block have potential side-effects. 82 // This includes instructions that could write to memory, and loads that are 83 // marked volatile. 84 for (auto &I : L->blocks()) 85 if (any_of(*I, [](Instruction &I) { return I.mayHaveSideEffects(); })) 86 return false; 87 return true; 88 } 89 90 /// This function returns true if there is no viable path from the 91 /// entry block to the header of \p L. Right now, it only does 92 /// a local search to save compile time. 93 static bool isLoopNeverExecuted(Loop *L) { 94 using namespace PatternMatch; 95 96 auto *Preheader = L->getLoopPreheader(); 97 // TODO: We can relax this constraint, since we just need a loop 98 // predecessor. 99 assert(Preheader && "Needs preheader!"); 100 101 if (Preheader == &Preheader->getParent()->getEntryBlock()) 102 return false; 103 // All predecessors of the preheader should have a constant conditional 104 // branch, with the loop's preheader as not-taken. 105 for (auto *Pred: predecessors(Preheader)) { 106 BasicBlock *Taken, *NotTaken; 107 ConstantInt *Cond; 108 if (!match(Pred->getTerminator(), 109 m_Br(m_ConstantInt(Cond), Taken, NotTaken))) 110 return false; 111 if (!Cond->getZExtValue()) 112 std::swap(Taken, NotTaken); 113 if (Taken == Preheader) 114 return false; 115 } 116 assert(!pred_empty(Preheader) && 117 "Preheader should have predecessors at this point!"); 118 // All the predecessors have the loop preheader as not-taken target. 119 return true; 120 } 121 122 /// Remove a loop if it is dead. 123 /// 124 /// A loop is considered dead if it does not impact the observable behavior of 125 /// the program other than finite running time. This never removes a loop that 126 /// might be infinite (unless it is never executed), as doing so could change 127 /// the halting/non-halting nature of a program. 128 /// 129 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in 130 /// order to make various safety checks work. 131 /// 132 /// \returns true if any changes were made. This may mutate the loop even if it 133 /// is unable to delete it due to hoisting trivially loop invariant 134 /// instructions out of the loop. 135 static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, 136 ScalarEvolution &SE, LoopInfo &LI) { 137 assert(L->isLCSSAForm(DT) && "Expected LCSSA!"); 138 139 // We can only remove the loop if there is a preheader that we can branch from 140 // after removing it. Also, if LoopSimplify form is not available, stay out 141 // of trouble. 142 BasicBlock *Preheader = L->getLoopPreheader(); 143 if (!Preheader || !L->hasDedicatedExits()) { 144 LLVM_DEBUG( 145 dbgs() 146 << "Deletion requires Loop with preheader and dedicated exits.\n"); 147 return LoopDeletionResult::Unmodified; 148 } 149 // We can't remove loops that contain subloops. If the subloops were dead, 150 // they would already have been removed in earlier executions of this pass. 151 if (L->begin() != L->end()) { 152 LLVM_DEBUG(dbgs() << "Loop contains subloops.\n"); 153 return LoopDeletionResult::Unmodified; 154 } 155 156 157 BasicBlock *ExitBlock = L->getUniqueExitBlock(); 158 159 if (ExitBlock && isLoopNeverExecuted(L)) { 160 LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!"); 161 // Set incoming value to undef for phi nodes in the exit block. 162 for (PHINode &P : ExitBlock->phis()) { 163 std::fill(P.incoming_values().begin(), P.incoming_values().end(), 164 UndefValue::get(P.getType())); 165 } 166 deleteDeadLoop(L, &DT, &SE, &LI); 167 ++NumDeleted; 168 return LoopDeletionResult::Deleted; 169 } 170 171 // The remaining checks below are for a loop being dead because all statements 172 // in the loop are invariant. 173 SmallVector<BasicBlock *, 4> ExitingBlocks; 174 L->getExitingBlocks(ExitingBlocks); 175 176 // We require that the loop only have a single exit block. Otherwise, we'd 177 // be in the situation of needing to be able to solve statically which exit 178 // block will be branched to, or trying to preserve the branching logic in 179 // a loop invariant manner. 180 if (!ExitBlock) { 181 LLVM_DEBUG(dbgs() << "Deletion requires single exit block\n"); 182 return LoopDeletionResult::Unmodified; 183 } 184 // Finally, we have to check that the loop really is dead. 185 bool Changed = false; 186 if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) { 187 LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n"); 188 return Changed ? LoopDeletionResult::Modified 189 : LoopDeletionResult::Unmodified; 190 } 191 192 // Don't remove loops for which we can't solve the trip count. 193 // They could be infinite, in which case we'd be changing program behavior. 194 const SCEV *S = SE.getMaxBackedgeTakenCount(L); 195 if (isa<SCEVCouldNotCompute>(S)) { 196 LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n"); 197 return Changed ? LoopDeletionResult::Modified 198 : LoopDeletionResult::Unmodified; 199 } 200 201 LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!"); 202 deleteDeadLoop(L, &DT, &SE, &LI); 203 ++NumDeleted; 204 205 return LoopDeletionResult::Deleted; 206 } 207 208 PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM, 209 LoopStandardAnalysisResults &AR, 210 LPMUpdater &Updater) { 211 212 LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: "); 213 LLVM_DEBUG(L.dump()); 214 std::string LoopName = L.getName(); 215 auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI); 216 if (Result == LoopDeletionResult::Unmodified) 217 return PreservedAnalyses::all(); 218 219 if (Result == LoopDeletionResult::Deleted) 220 Updater.markLoopAsDeleted(L, LoopName); 221 222 return getLoopPassPreservedAnalyses(); 223 } 224 225 namespace { 226 class LoopDeletionLegacyPass : public LoopPass { 227 public: 228 static char ID; // Pass ID, replacement for typeid 229 LoopDeletionLegacyPass() : LoopPass(ID) { 230 initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry()); 231 } 232 233 // Possibly eliminate loop L if it is dead. 234 bool runOnLoop(Loop *L, LPPassManager &) override; 235 236 void getAnalysisUsage(AnalysisUsage &AU) const override { 237 getLoopAnalysisUsage(AU); 238 } 239 }; 240 } 241 242 char LoopDeletionLegacyPass::ID = 0; 243 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion", 244 "Delete dead loops", false, false) 245 INITIALIZE_PASS_DEPENDENCY(LoopPass) 246 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion", 247 "Delete dead loops", false, false) 248 249 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); } 250 251 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) { 252 if (skipLoop(L)) 253 return false; 254 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 255 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 256 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 257 258 LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: "); 259 LLVM_DEBUG(L->dump()); 260 261 LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI); 262 263 if (Result == LoopDeletionResult::Deleted) 264 LPM.markLoopAsDeleted(*L); 265 266 return Result != LoopDeletionResult::Unmodified; 267 } 268