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 "ScalarOptions.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/Analysis/CFG.h"
21#include "llvm/Analysis/InstructionSimplify.h"
22#include "llvm/Analysis/LoopInfo.h"
23#include "llvm/Analysis/LoopIterator.h"
24#include "llvm/Analysis/LoopPass.h"
25#include "llvm/Analysis/MemorySSA.h"
26#include "llvm/Analysis/OptimizationRemarkEmitter.h"
27#include "llvm/Analysis/ScalarEvolution.h"
28#include "llvm/IR/Dominators.h"
29
30#include "llvm/IR/PatternMatch.h"
31#include "llvm/Transforms/Scalar/LoopPassManager.h"
32#include "llvm/Transforms/Utils/LoopUtils.h"
33
34using namespace llvm;
35
36#define DEBUG_TYPE "loop-delete"
37
38STATISTIC(NumDeleted, "Number of loops deleted");
39STATISTIC(NumBackedgesBroken,
40 "Number of loops for which we managed to break the backedge");
41
42enum class LoopDeletionResult {
43 Unmodified,
44 Modified,
45 Deleted,
46};
47
48static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B) {
49 if (A == LoopDeletionResult::Deleted || B == LoopDeletionResult::Deleted)
50 return LoopDeletionResult::Deleted;
51 if (A == LoopDeletionResult::Modified || B == LoopDeletionResult::Modified)
52 return LoopDeletionResult::Modified;
53 return LoopDeletionResult::Unmodified;
54}
55
56/// Determines if a loop is dead.
57///
58/// This assumes that we've already checked for unique exit and exiting blocks,
59/// and that the code is in LCSSA form.
60static bool isLoopDead(Loop *L, ScalarEvolution &SE,
61 SmallVectorImpl<BasicBlock *> &ExitingBlocks,
62 BasicBlock *ExitBlock, bool &Changed,
63 BasicBlock *Preheader, LoopInfo &LI) {
64 // Make sure that all PHI entries coming from the loop are loop invariant.
65 // Because the code is in LCSSA form, any values used outside of the loop
66 // must pass through a PHI in the exit block, meaning that this check is
67 // sufficient to guarantee that no loop-variant values are used outside
68 // of the loop.
69 bool AllEntriesInvariant = true;
70 bool AllOutgoingValuesSame = true;
71 if (ExitBlock) {
72 for (PHINode &P : ExitBlock->phis()) {
73 Value *incoming = P.getIncomingValueForBlock(BB: ExitingBlocks[0]);
74
75 // Make sure all exiting blocks produce the same incoming value for the
76 // block. If there are different incoming values for different exiting
77 // blocks, then it is impossible to statically determine which value
78 // should be used.
79 AllOutgoingValuesSame =
80 all_of(Range: ArrayRef(ExitingBlocks).slice(N: 1), P: [&](BasicBlock *BB) {
81 return incoming == P.getIncomingValueForBlock(BB);
82 });
83
84 if (!AllOutgoingValuesSame)
85 break;
86
87 if (Instruction *I = dyn_cast<Instruction>(Val: incoming)) {
88 if (!L->makeLoopInvariant(I, Changed, InsertPt: Preheader->getTerminator(),
89 /*MSSAU=*/nullptr, SE: &SE)) {
90 AllEntriesInvariant = false;
91 break;
92 }
93 }
94 }
95 }
96
97 if (!AllEntriesInvariant || !AllOutgoingValuesSame)
98 return false;
99
100 // Make sure that no instructions in the block have potential side-effects.
101 // This includes instructions that could write to memory, and loads that are
102 // marked volatile.
103 for (const auto &I : L->blocks())
104 if (any_of(Range&: *I, P: [](Instruction &I) {
105 return I.mayHaveSideEffects() && !I.isDroppable();
106 }))
107 return false;
108
109 // Calls that may not return were rejected above.
110 return isLoopNestFinite(L, SE, LI);
111}
112
113/// This function returns true if there is no viable path from the
114/// entry block to the header of \p L. Right now, it only does
115/// a local search to save compile time.
116static bool isLoopNeverExecuted(Loop *L) {
117 using namespace PatternMatch;
118
119 auto *Preheader = L->getLoopPreheader();
120 // TODO: We can relax this constraint, since we just need a loop
121 // predecessor.
122 assert(Preheader && "Needs preheader!");
123
124 if (Preheader->isEntryBlock())
125 return false;
126 // All predecessors of the preheader should have a constant conditional
127 // branch, with the loop's preheader as not-taken.
128 for (auto *Pred: predecessors(BB: Preheader)) {
129 BasicBlock *Taken, *NotTaken;
130 ConstantInt *Cond;
131 if (!match(V: Pred->getTerminator(),
132 P: m_Br(C: m_ConstantInt(CI&: Cond), T&: Taken, F&: NotTaken)))
133 return false;
134 if (!Cond->getZExtValue())
135 std::swap(a&: Taken, b&: NotTaken);
136 if (Taken == Preheader)
137 return false;
138 }
139 assert(!pred_empty(Preheader) &&
140 "Preheader should have predecessors at this point!");
141 // All the predecessors have the loop preheader as not-taken target.
142 return true;
143}
144
145static Value *
146getValueOnFirstIteration(Value *V, DenseMap<Value *, Value *> &FirstIterValue,
147 const SimplifyQuery &SQ) {
148 // Quick hack: do not flood cache with non-instruction values.
149 if (!isa<Instruction>(Val: V))
150 return V;
151 // Do we already know cached result?
152 auto Existing = FirstIterValue.find(Val: V);
153 if (Existing != FirstIterValue.end())
154 return Existing->second;
155 Value *FirstIterV = nullptr;
156 if (auto *BO = dyn_cast<BinaryOperator>(Val: V)) {
157 Value *LHS =
158 getValueOnFirstIteration(V: BO->getOperand(i_nocapture: 0), FirstIterValue, SQ);
159 Value *RHS =
160 getValueOnFirstIteration(V: BO->getOperand(i_nocapture: 1), FirstIterValue, SQ);
161 FirstIterV = simplifyBinOp(Opcode: BO->getOpcode(), LHS, RHS, Q: SQ);
162 } else if (auto *Cmp = dyn_cast<ICmpInst>(Val: V)) {
163 Value *LHS =
164 getValueOnFirstIteration(V: Cmp->getOperand(i_nocapture: 0), FirstIterValue, SQ);
165 Value *RHS =
166 getValueOnFirstIteration(V: Cmp->getOperand(i_nocapture: 1), FirstIterValue, SQ);
167 FirstIterV = simplifyICmpInst(Pred: Cmp->getPredicate(), LHS, RHS, Q: SQ);
168 } else if (auto *Select = dyn_cast<SelectInst>(Val: V)) {
169 Value *Cond =
170 getValueOnFirstIteration(V: Select->getCondition(), FirstIterValue, SQ);
171 if (auto *C = dyn_cast<ConstantInt>(Val: Cond)) {
172 auto *Selected = C->isAllOnesValue() ? Select->getTrueValue()
173 : Select->getFalseValue();
174 FirstIterV = getValueOnFirstIteration(V: Selected, FirstIterValue, SQ);
175 }
176 }
177 if (!FirstIterV)
178 FirstIterV = V;
179 FirstIterValue[V] = FirstIterV;
180 return FirstIterV;
181}
182
183// Try to prove that one of conditions that dominates the latch must exit on 1st
184// iteration.
185static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT,
186 LoopInfo &LI) {
187 // Disabled by option.
188 if (!getScalarOptions(L: *L).loop_deletion_enable_symbolic_execution)
189 return false;
190
191 BasicBlock *Predecessor = L->getLoopPredecessor();
192 BasicBlock *Latch = L->getLoopLatch();
193
194 if (!Predecessor || !Latch)
195 return false;
196
197 LoopBlocksRPO RPOT(L);
198 RPOT.perform(LI: &LI);
199
200 // For the optimization to be correct, we need RPOT to have a property that
201 // each block is processed after all its predecessors, which may only be
202 // violated for headers of the current loop and all nested loops. Irreducible
203 // CFG provides multiple ways to break this assumption, so we do not want to
204 // deal with it.
205 if (containsIrreducibleCFG<const BasicBlock *>(RPOTraversal&: RPOT, LI))
206 return false;
207
208 BasicBlock *Header = L->getHeader();
209 // Blocks that are reachable on the 1st iteration.
210 SmallPtrSet<BasicBlock *, 4> LiveBlocks;
211 // Edges that are reachable on the 1st iteration.
212 DenseSet<BasicBlockEdge> LiveEdges;
213 LiveBlocks.insert(Ptr: Header);
214
215 SmallPtrSet<BasicBlock *, 4> Visited;
216 auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) {
217 assert(LiveBlocks.count(From) && "Must be live!");
218 assert((LI.isLoopHeader(To) || !Visited.count(To)) &&
219 "Only canonical backedges are allowed. Irreducible CFG?");
220 assert((LiveBlocks.count(To) || !Visited.count(To)) &&
221 "We already discarded this block as dead!");
222 LiveBlocks.insert(Ptr: To);
223 LiveEdges.insert(V: { From, To });
224 };
225
226 auto MarkAllSuccessorsLive = [&](BasicBlock *BB) {
227 for (auto *Succ : successors(BB))
228 MarkLiveEdge(BB, Succ);
229 };
230
231 // Check if there is only one value coming from all live predecessor blocks.
232 // Note that because we iterate in RPOT, we have already visited all its
233 // (non-latch) predecessors.
234 auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
235 BasicBlock *BB = PN.getParent();
236 bool HasLivePreds = false;
237 (void)HasLivePreds;
238 if (BB == Header)
239 return PN.getIncomingValueForBlock(BB: Predecessor);
240 Value *OnlyInput = nullptr;
241 for (auto *Pred : predecessors(BB))
242 if (LiveEdges.count(V: { Pred, BB })) {
243 HasLivePreds = true;
244 Value *Incoming = PN.getIncomingValueForBlock(BB: Pred);
245 // Skip poison. If they are present, we can assume they are equal to
246 // the non-poison input.
247 if (isa<PoisonValue>(Val: Incoming))
248 continue;
249 // Two inputs.
250 if (OnlyInput && OnlyInput != Incoming)
251 return nullptr;
252 OnlyInput = Incoming;
253 }
254
255 assert(HasLivePreds && "No live predecessors?");
256 // If all incoming live value were poison, return poison.
257 return OnlyInput ? OnlyInput : PoisonValue::get(T: PN.getType());
258 };
259 DenseMap<Value *, Value *> FirstIterValue;
260
261 // Use the following algorithm to prove we never take the latch on the 1st
262 // iteration:
263 // 1. Traverse in topological order, so that whenever we visit a block, all
264 // its predecessors are already visited.
265 // 2. If we can prove that the block may have only 1 predecessor on the 1st
266 // iteration, map all its phis onto input from this predecessor.
267 // 3a. If we can prove which successor of out block is taken on the 1st
268 // iteration, mark this successor live.
269 // 3b. If we cannot prove it, conservatively assume that all successors are
270 // live.
271 auto &DL = Header->getDataLayout();
272 const SimplifyQuery SQ(DL);
273 for (auto *BB : RPOT) {
274 Visited.insert(Ptr: BB);
275
276 // This block is not reachable on the 1st iterations.
277 if (!LiveBlocks.count(Ptr: BB))
278 continue;
279
280 // Skip inner loops.
281 if (LI.getLoopFor(BB) != L) {
282 MarkAllSuccessorsLive(BB);
283 continue;
284 }
285
286 // If Phi has only one input from all live input blocks, use it.
287 for (auto &PN : BB->phis()) {
288 if (!PN.getType()->isIntegerTy())
289 continue;
290 auto *Incoming = GetSoleInputOnFirstIteration(PN);
291 if (Incoming && DT.dominates(Def: Incoming, User: BB->getTerminator())) {
292 Value *FirstIterV =
293 getValueOnFirstIteration(V: Incoming, FirstIterValue, SQ);
294 FirstIterValue[&PN] = FirstIterV;
295 }
296 }
297
298 using namespace PatternMatch;
299 Value *Cond;
300 BasicBlock *IfTrue, *IfFalse;
301 auto *Term = BB->getTerminator();
302 if (match(V: Term, P: m_Br(C: m_Value(V&: Cond),
303 T: m_BasicBlock(V&: IfTrue), F: m_BasicBlock(V&: IfFalse)))) {
304 auto *ICmp = dyn_cast<ICmpInst>(Val: Cond);
305 if (!ICmp || !ICmp->getType()->isIntegerTy()) {
306 MarkAllSuccessorsLive(BB);
307 continue;
308 }
309
310 // Can we prove constant true or false for this condition?
311 auto *KnownCondition = getValueOnFirstIteration(V: ICmp, FirstIterValue, SQ);
312 if (KnownCondition == ICmp) {
313 // Failed to simplify.
314 MarkAllSuccessorsLive(BB);
315 continue;
316 }
317 if (isa<UndefValue>(Val: KnownCondition)) {
318 // TODO: According to langref, branching by undef is undefined behavior.
319 // It means that, theoretically, we should be able to just continue
320 // without marking any successors as live. However, we are not certain
321 // how correct our compiler is at handling such cases. So we are being
322 // very conservative here.
323 //
324 // If there is a non-loop successor, always assume this branch leaves the
325 // loop. Otherwise, arbitrarily take IfTrue.
326 //
327 // Once we are certain that branching by undef is handled correctly by
328 // other transforms, we should not mark any successors live here.
329 if (L->contains(BB: IfTrue) && L->contains(BB: IfFalse))
330 MarkLiveEdge(BB, IfTrue);
331 continue;
332 }
333 auto *ConstCondition = dyn_cast<ConstantInt>(Val: KnownCondition);
334 if (!ConstCondition) {
335 // Non-constant condition, cannot analyze any further.
336 MarkAllSuccessorsLive(BB);
337 continue;
338 }
339 if (ConstCondition->isAllOnesValue())
340 MarkLiveEdge(BB, IfTrue);
341 else
342 MarkLiveEdge(BB, IfFalse);
343 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: Term)) {
344 auto *SwitchValue = SI->getCondition();
345 auto *SwitchValueOnFirstIter =
346 getValueOnFirstIteration(V: SwitchValue, FirstIterValue, SQ);
347 auto *ConstSwitchValue = dyn_cast<ConstantInt>(Val: SwitchValueOnFirstIter);
348 if (!ConstSwitchValue) {
349 MarkAllSuccessorsLive(BB);
350 continue;
351 }
352 auto CaseIterator = SI->findCaseValue(C: ConstSwitchValue);
353 MarkLiveEdge(BB, CaseIterator->getCaseSuccessor());
354 } else {
355 MarkAllSuccessorsLive(BB);
356 continue;
357 }
358 }
359
360 // We can break the latch if it wasn't live.
361 return !LiveEdges.count(V: { Latch, Header });
362}
363
364/// If we can prove the backedge is untaken, remove it. This destroys the
365/// loop, but leaves the (now trivially loop invariant) control flow and
366/// side effects (if any) in place.
367static LoopDeletionResult
368breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
369 LoopInfo &LI, MemorySSA *MSSA,
370 OptimizationRemarkEmitter &ORE) {
371 assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
372
373 if (!L->getLoopLatch())
374 return LoopDeletionResult::Unmodified;
375
376 const SCEV *BTCMax = SE.getConstantMaxBackedgeTakenCount(L);
377 if (!BTCMax->isZero()) {
378 const SCEV *BTC = SE.getBackedgeTakenCount(L);
379 if (!BTC->isZero()) {
380 if (!isa<SCEVCouldNotCompute>(Val: BTC) && SE.isKnownNonZero(S: BTC))
381 return LoopDeletionResult::Unmodified;
382 if (!canProveExitOnFirstIteration(L, DT, LI))
383 return LoopDeletionResult::Unmodified;
384 }
385 }
386 ++NumBackedgesBroken;
387 breakLoopBackedge(L, DT, SE, LI, MSSA);
388 return LoopDeletionResult::Deleted;
389}
390
391/// Remove a loop if it is dead.
392///
393/// A loop is considered dead either if it does not impact the observable
394/// behavior of the program other than finite running time, or if it is
395/// required to make progress by an attribute such as 'mustprogress' or
396/// 'llvm.loop.mustprogress' and does not make any. This may remove
397/// infinite loops that have been required to make progress.
398///
399/// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
400/// order to make various safety checks work.
401///
402/// \returns true if any changes were made. This may mutate the loop even if it
403/// is unable to delete it due to hoisting trivially loop invariant
404/// instructions out of the loop.
405static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
406 ScalarEvolution &SE, LoopInfo &LI,
407 MemorySSA *MSSA,
408 OptimizationRemarkEmitter &ORE) {
409 assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
410
411 // We can only remove the loop if there is a preheader that we can branch from
412 // after removing it. Also, if LoopSimplify form is not available, stay out
413 // of trouble.
414 BasicBlock *Preheader = L->getLoopPreheader();
415 if (!Preheader || !L->hasDedicatedExits()) {
416 LLVM_DEBUG(
417 dbgs()
418 << "Deletion requires Loop with preheader and dedicated exits.\n");
419 return LoopDeletionResult::Unmodified;
420 }
421
422 BasicBlock *ExitBlock = L->getUniqueExitBlock();
423
424 // We can't directly branch to an EH pad. Don't bother handling this edge
425 // case.
426 if (ExitBlock && ExitBlock->isEHPad()) {
427 LLVM_DEBUG(dbgs() << "Cannot delete loop exiting to EH pad.\n");
428 return LoopDeletionResult::Unmodified;
429 }
430
431 if (ExitBlock && isLoopNeverExecuted(L)) {
432 LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!\n");
433 // We need to forget the loop before setting the incoming values of the exit
434 // phis to poison, so we properly invalidate the SCEV expressions for those
435 // phis.
436 SE.forgetLoop(L);
437 // Set incoming value to poison for phi nodes in the exit block.
438 for (PHINode &P : ExitBlock->phis()) {
439 llvm::fill(Range: P.incoming_values(), Value: PoisonValue::get(T: P.getType()));
440 }
441 ORE.emit(RemarkBuilder: [&]() {
442 return OptimizationRemark(DEBUG_TYPE, "NeverExecutes", L->getStartLoc(),
443 L->getHeader())
444 << "Loop deleted because it never executes";
445 });
446 deleteDeadLoop(L, DT: &DT, SE: &SE, LI: &LI, MSSA);
447 ++NumDeleted;
448 return LoopDeletionResult::Deleted;
449 }
450
451 // The remaining checks below are for a loop being dead because all statements
452 // in the loop are invariant.
453 SmallVector<BasicBlock *, 4> ExitingBlocks;
454 L->getExitingBlocks(ExitingBlocks);
455
456 // We require that the loop has at most one exit block. Otherwise, we'd be in
457 // the situation of needing to be able to solve statically which exit block
458 // will be branched to, or trying to preserve the branching logic in a loop
459 // invariant manner.
460 if (!ExitBlock && !LI.hasNoExitBlocks(L: *L)) {
461 LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n");
462 return LoopDeletionResult::Unmodified;
463 }
464
465 // Finally, we have to check that the loop really is dead.
466 bool Changed = false;
467 if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {
468 LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
469 return Changed ? LoopDeletionResult::Modified
470 : LoopDeletionResult::Unmodified;
471 }
472
473 LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!\n");
474 ORE.emit(RemarkBuilder: [&]() {
475 return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
476 L->getHeader())
477 << "Loop deleted because it is invariant";
478 });
479 deleteDeadLoop(L, DT: &DT, SE: &SE, LI: &LI, MSSA);
480 ++NumDeleted;
481
482 return LoopDeletionResult::Deleted;
483}
484
485PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
486 LoopStandardAnalysisResults &AR,
487 LPMUpdater &Updater) {
488
489 LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
490 LLVM_DEBUG(L.dump());
491 std::string LoopName = std::string(L.getName());
492 // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
493 // pass. Function analyses need to be preserved across loop transformations
494 // but ORE cannot be preserved (see comment before the pass definition).
495 OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
496 auto Result = deleteLoopIfDead(L: &L, DT&: AR.DT, SE&: AR.SE, LI&: AR.LI, MSSA: AR.MSSA, ORE);
497
498 // If we can prove the backedge isn't taken, just break it and be done. This
499 // leaves the loop structure in place which means it can handle dispatching
500 // to the right exit based on whatever loop invariant structure remains.
501 if (Result != LoopDeletionResult::Deleted)
502 Result = merge(A: Result, B: breakBackedgeIfNotTaken(L: &L, DT&: AR.DT, SE&: AR.SE, LI&: AR.LI,
503 MSSA: AR.MSSA, ORE));
504
505 if (Result == LoopDeletionResult::Unmodified)
506 return PreservedAnalyses::all();
507
508 if (Result == LoopDeletionResult::Deleted)
509 Updater.markLoopAsDeleted(L, Name: LoopName);
510
511 auto PA = getLoopPassPreservedAnalyses();
512 if (AR.MSSA)
513 PA.preserve<MemorySSAAnalysis>();
514 return PA;
515}
516