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