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