1 //===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===//
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
7 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
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"
29 #define DEBUG_TYPE "loop-delete"
31 STATISTIC(NumDeleted, "Number of loops deleted");
33 enum class LoopDeletionResult {
39 /// Determines if a loop is dead.
41 /// This assumes that we've already checked for unique exit and exiting blocks,
42 /// and that the code is in LCSSA form.
43 static 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
52 bool AllEntriesInvariant = true;
53 bool AllOutgoingValuesSame = true;
54 for (PHINode &P : ExitBlock->phis()) {
55 Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);
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
61 AllOutgoingValuesSame =
62 all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
63 return incoming == P.getIncomingValueForBlock(BB);
66 if (!AllOutgoingValuesSame)
69 if (Instruction *I = dyn_cast<Instruction>(incoming))
70 if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
71 AllEntriesInvariant = false;
77 SE.forgetLoopDispositions(L);
79 if (!AllEntriesInvariant || !AllOutgoingValuesSame)
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
85 for (auto &I : L->blocks())
86 if (any_of(*I, [](Instruction &I) { return I.mayHaveSideEffects(); }))
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.
94 static bool isLoopNeverExecuted(Loop *L) {
95 using namespace PatternMatch;
97 auto *Preheader = L->getLoopPreheader();
98 // TODO: We can relax this constraint, since we just need a loop
100 assert(Preheader && "Needs preheader!");
102 if (Preheader == &Preheader->getParent()->getEntryBlock())
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;
109 if (!match(Pred->getTerminator(),
110 m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
112 if (!Cond->getZExtValue())
113 std::swap(Taken, NotTaken);
114 if (Taken == Preheader)
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.
123 /// Remove a loop if it is dead.
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.
130 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
131 /// order to make various safety checks work.
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.
136 static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
137 ScalarEvolution &SE, LoopInfo &LI) {
138 assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
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
143 BasicBlock *Preheader = L->getLoopPreheader();
144 if (!Preheader || !L->hasDedicatedExits()) {
147 << "Deletion requires Loop with preheader and dedicated exits.\n");
148 return LoopDeletionResult::Unmodified;
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;
158 BasicBlock *ExitBlock = L->getUniqueExitBlock();
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()));
167 deleteDeadLoop(L, &DT, &SE, &LI);
169 return LoopDeletionResult::Deleted;
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);
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.
182 LLVM_DEBUG(dbgs() << "Deletion requires single exit block\n");
183 return LoopDeletionResult::Unmodified;
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;
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;
202 LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
203 deleteDeadLoop(L, &DT, &SE, &LI);
206 return LoopDeletionResult::Deleted;
209 PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
210 LoopStandardAnalysisResults &AR,
211 LPMUpdater &Updater) {
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();
220 if (Result == LoopDeletionResult::Deleted)
221 Updater.markLoopAsDeleted(L, LoopName);
223 return getLoopPassPreservedAnalyses();
227 class LoopDeletionLegacyPass : public LoopPass {
229 static char ID; // Pass ID, replacement for typeid
230 LoopDeletionLegacyPass() : LoopPass(ID) {
231 initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry());
234 // Possibly eliminate loop L if it is dead.
235 bool runOnLoop(Loop *L, LPPassManager &) override;
237 void getAnalysisUsage(AnalysisUsage &AU) const override {
238 getLoopAnalysisUsage(AU);
243 char LoopDeletionLegacyPass::ID = 0;
244 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
245 "Delete dead loops", false, false)
246 INITIALIZE_PASS_DEPENDENCY(LoopPass)
247 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
248 "Delete dead loops", false, false)
250 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
252 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
255 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
256 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
257 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
259 LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
260 LLVM_DEBUG(L->dump());
262 LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI);
264 if (Result == LoopDeletionResult::Deleted)
265 LPM.markLoopAsDeleted(*L);
267 return Result != LoopDeletionResult::Unmodified;