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