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"
29using namespace llvm;
30
31#define DEBUG_TYPE "loop-delete"
32
33STATISTIC(NumDeleted, "Number of loops deleted");
34
35enum 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.
45static 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.
96static 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.
138static 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
223PreservedAnalyses 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
247namespace {
248class LoopDeletionLegacyPass : public LoopPass {
249public:
250  static char ID; // Pass ID, replacement for typeid
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
258  void getAnalysisUsage(AnalysisUsage &AU) const override {
259    AU.addPreserved<MemorySSAWrapperPass>();
260    getLoopAnalysisUsage(AU);
261  }
262};
263}
264
265char LoopDeletionLegacyPass::ID = 0;
266INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
267                      "Delete dead loops", false, false)
268INITIALIZE_PASS_DEPENDENCY(LoopPass)
269INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
270                    "Delete dead loops", false, false)
271
272Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
273
274bool 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