LLVM  10.0.0svn
Go to the documentation of this file.
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 //===----------------------------------------------------------------------===//
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/LoopPass.h"
21 #include "llvm/IR/Dominators.h"
22 #include "llvm/IR/PatternMatch.h"
23 #include "llvm/Transforms/Scalar.h"
26 using namespace llvm;
28 #define DEBUG_TYPE "loop-delete"
30 STATISTIC(NumDeleted, "Number of loops deleted");
32 enum class LoopDeletionResult {
33  Unmodified,
34  Modified,
35  Deleted,
36 };
38 /// Determines if a loop is dead.
39 ///
40 /// This assumes that we've already checked for unique exit and exiting blocks,
41 /// and that the code is in LCSSA form.
42 static bool isLoopDead(Loop *L, ScalarEvolution &SE,
43  SmallVectorImpl<BasicBlock *> &ExitingBlocks,
44  BasicBlock *ExitBlock, bool &Changed,
45  BasicBlock *Preheader) {
46  // Make sure that all PHI entries coming from the loop are loop invariant.
47  // Because the code is in LCSSA form, any values used outside of the loop
48  // must pass through a PHI in the exit block, meaning that this check is
49  // sufficient to guarantee that no loop-variant values are used outside
50  // of the loop.
51  bool AllEntriesInvariant = true;
52  bool AllOutgoingValuesSame = true;
53  for (PHINode &P : ExitBlock->phis()) {
54  Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);
56  // Make sure all exiting blocks produce the same incoming value for the exit
57  // block. If there are different incoming values for different exiting
58  // blocks, then it is impossible to statically determine which value should
59  // be used.
60  AllOutgoingValuesSame =
61  all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
62  return incoming == P.getIncomingValueForBlock(BB);
63  });
65  if (!AllOutgoingValuesSame)
66  break;
68  if (Instruction *I = dyn_cast<Instruction>(incoming))
69  if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
70  AllEntriesInvariant = false;
71  break;
72  }
73  }
75  if (Changed)
78  if (!AllEntriesInvariant || !AllOutgoingValuesSame)
79  return false;
81  // Make sure that no instructions in the block have potential side-effects.
82  // This includes instructions that could write to memory, and loads that are
83  // marked volatile.
84  for (auto &I : L->blocks())
85  if (any_of(*I, [](Instruction &I) { return I.mayHaveSideEffects(); }))
86  return false;
87  return true;
88 }
90 /// This function returns true if there is no viable path from the
91 /// entry block to the header of \p L. Right now, it only does
92 /// a local search to save compile time.
93 static bool isLoopNeverExecuted(Loop *L) {
94  using namespace PatternMatch;
96  auto *Preheader = L->getLoopPreheader();
97  // TODO: We can relax this constraint, since we just need a loop
98  // predecessor.
99  assert(Preheader && "Needs preheader!");
101  if (Preheader == &Preheader->getParent()->getEntryBlock())
102  return false;
103  // All predecessors of the preheader should have a constant conditional
104  // branch, with the loop's preheader as not-taken.
105  for (auto *Pred: predecessors(Preheader)) {
106  BasicBlock *Taken, *NotTaken;
107  ConstantInt *Cond;
108  if (!match(Pred->getTerminator(),
109  m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
110  return false;
111  if (!Cond->getZExtValue())
112  std::swap(Taken, NotTaken);
113  if (Taken == Preheader)
114  return false;
115  }
116  assert(!pred_empty(Preheader) &&
117  "Preheader should have predecessors at this point!");
118  // All the predecessors have the loop preheader as not-taken target.
119  return true;
120 }
122 /// Remove a loop if it is dead.
123 ///
124 /// A loop is considered dead if it does not impact the observable behavior of
125 /// the program other than finite running time. This never removes a loop that
126 /// might be infinite (unless it is never executed), as doing so could change
127 /// the halting/non-halting nature of a program.
128 ///
129 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
130 /// order to make various safety checks work.
131 ///
132 /// \returns true if any changes were made. This may mutate the loop even if it
133 /// is unable to delete it due to hoisting trivially loop invariant
134 /// instructions out of the loop.
136  ScalarEvolution &SE, LoopInfo &LI) {
137  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
139  // We can only remove the loop if there is a preheader that we can branch from
140  // after removing it. Also, if LoopSimplify form is not available, stay out
141  // of trouble.
142  BasicBlock *Preheader = L->getLoopPreheader();
143  if (!Preheader || !L->hasDedicatedExits()) {
145  dbgs()
146  << "Deletion requires Loop with preheader and dedicated exits.\n");
148  }
149  // We can't remove loops that contain subloops. If the subloops were dead,
150  // they would already have been removed in earlier executions of this pass.
151  if (L->begin() != L->end()) {
152  LLVM_DEBUG(dbgs() << "Loop contains subloops.\n");
154  }
157  BasicBlock *ExitBlock = L->getUniqueExitBlock();
159  if (ExitBlock && isLoopNeverExecuted(L)) {
160  LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
161  // Set incoming value to undef for phi nodes in the exit block.
162  for (PHINode &P : ExitBlock->phis()) {
163  std::fill(P.incoming_values().begin(), P.incoming_values().end(),
164  UndefValue::get(P.getType()));
165  }
166  deleteDeadLoop(L, &DT, &SE, &LI);
167  ++NumDeleted;
169  }
171  // The remaining checks below are for a loop being dead because all statements
172  // in the loop are invariant.
173  SmallVector<BasicBlock *, 4> ExitingBlocks;
174  L->getExitingBlocks(ExitingBlocks);
176  // We require that the loop only have a single exit block. Otherwise, we'd
177  // be in the situation of needing to be able to solve statically which exit
178  // block will be branched to, or trying to preserve the branching logic in
179  // a loop invariant manner.
180  if (!ExitBlock) {
181  LLVM_DEBUG(dbgs() << "Deletion requires single exit block\n");
183  }
184  // Finally, we have to check that the loop really is dead.
185  bool Changed = false;
186  if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) {
187  LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
188  return Changed ? LoopDeletionResult::Modified
190  }
192  // Don't remove loops for which we can't solve the trip count.
193  // They could be infinite, in which case we'd be changing program behavior.
194  const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L);
195  if (isa<SCEVCouldNotCompute>(S)) {
196  LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
197  return Changed ? LoopDeletionResult::Modified
199  }
201  LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
202  deleteDeadLoop(L, &DT, &SE, &LI);
203  ++NumDeleted;
206 }
210  LPMUpdater &Updater) {
212  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
213  LLVM_DEBUG(L.dump());
214  std::string LoopName = L.getName();
215  auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI);
216  if (Result == LoopDeletionResult::Unmodified)
217  return PreservedAnalyses::all();
219  if (Result == LoopDeletionResult::Deleted)
220  Updater.markLoopAsDeleted(L, LoopName);
223 }
225 namespace {
226 class LoopDeletionLegacyPass : public LoopPass {
227 public:
228  static char ID; // Pass ID, replacement for typeid
229  LoopDeletionLegacyPass() : LoopPass(ID) {
231  }
233  // Possibly eliminate loop L if it is dead.
234  bool runOnLoop(Loop *L, LPPassManager &) override;
236  void getAnalysisUsage(AnalysisUsage &AU) const override {
238  }
239 };
240 }
243 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
244  "Delete dead loops", false, false)
246 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
247  "Delete dead loops", false, false)
249 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
251 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
252  if (skipLoop(L))
253  return false;
254  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
255  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
256  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
258  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
259  LLVM_DEBUG(L->dump());
261  LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI);
263  if (Result == LoopDeletionResult::Deleted)
264  LPM.markLoopAsDeleted(*L);
266  return Result != LoopDeletionResult::Unmodified;
267 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This header provides classes for managing a pipeline of passes over loops in LLVM IR...
This is the interface for a simple mod/ref and alias analysis over globals.
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:85
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:448
void initializeLoopDeletionLegacyPassPass(PassRegistry &)
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:160
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1165
STATISTIC(NumFunctions, "Total number of functions")
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:144
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
Definition: PassSupport.h:50
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:450
loop Delete dead loops
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI)
This function deletes dead loops.
Definition: LoopUtils.cpp:506
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:81
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
#define P(N)
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:148
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
void dump() const
Definition: LoopInfo.cpp:647
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:582
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1172
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI)
Remove a loop if it is dead.
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:116
void getExitingBlocks(SmallVectorImpl< BlockT *> &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1446
loop deletion
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:131
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
static bool isLoopNeverExecuted(Loop *L)
This function returns true if there is no viable path from the entry block to the header of L...
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
iterator begin() const
Definition: LoopInfo.h:147
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:143
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
Pass * createLoopDeletionPass()
INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion", "Delete dead loops", false, false) INITIALIZE_PASS_END(LoopDeletionLegacyPass
static bool isLoopDead(Loop *L, ScalarEvolution &SE, SmallVectorImpl< BasicBlock *> &ExitingBlocks, BasicBlock *ExitBlock, bool &Changed, BasicBlock *Preheader)
Determines if a loop is dead.
This class represents an analyzed expression in the program.
StringRef getName() const
Definition: LoopInfo.h:827
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
#define I(x, y, z)
Definition: MD5.cpp:58
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:138
iterator end() const
Definition: LoopInfo.h:148
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:329
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:74
The loop was not modified.
A container for analyses that lazily runs them and caches their results.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:161
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr) const
If the given value is an instruction inside of the loop and it can be hoisted, do so to make it trivi...
Definition: LoopInfo.cpp:71