LLVM  8.0.0svn
Go to the documentation of this file.
1 //===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the Dead Loop Deletion Pass. This pass is responsible
11 // for eliminating loops with non-infinite computable trip counts that have no
12 // side effects or volatile instructions, and do not contribute to the
13 // computation of the function's return value.
14 //
15 //===----------------------------------------------------------------------===//
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
21 #include "llvm/Analysis/LoopPass.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/PatternMatch.h"
24 #include "llvm/Transforms/Scalar.h"
27 using namespace llvm;
29 #define DEBUG_TYPE "loop-delete"
31 STATISTIC(NumDeleted, "Number of loops deleted");
33 enum class LoopDeletionResult {
34  Unmodified,
35  Modified,
36  Deleted,
37 };
39 /// Determines if a loop is dead.
40 ///
41 /// This assumes that we've already checked for unique exit and exiting blocks,
42 /// and that the code is in LCSSA form.
43 static bool isLoopDead(Loop *L, ScalarEvolution &SE,
44  SmallVectorImpl<BasicBlock *> &ExitingBlocks,
45  BasicBlock *ExitBlock, bool &Changed,
46  BasicBlock *Preheader) {
47  // Make sure that all PHI entries coming from the loop are loop invariant.
48  // Because the code is in LCSSA form, any values used outside of the loop
49  // must pass through a PHI in the exit block, meaning that this check is
50  // sufficient to guarantee that no loop-variant values are used outside
51  // of the loop.
52  bool AllEntriesInvariant = true;
53  bool AllOutgoingValuesSame = true;
54  for (PHINode &P : ExitBlock->phis()) {
55  Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);
57  // Make sure all exiting blocks produce the same incoming value for the exit
58  // block. If there are different incoming values for different exiting
59  // blocks, then it is impossible to statically determine which value should
60  // be used.
61  AllOutgoingValuesSame =
62  all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
63  return incoming == P.getIncomingValueForBlock(BB);
64  });
66  if (!AllOutgoingValuesSame)
67  break;
69  if (Instruction *I = dyn_cast<Instruction>(incoming))
70  if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
71  AllEntriesInvariant = false;
72  break;
73  }
74  }
76  if (Changed)
79  if (!AllEntriesInvariant || !AllOutgoingValuesSame)
80  return false;
82  // Make sure that no instructions in the block have potential side-effects.
83  // This includes instructions that could write to memory, and loads that are
84  // marked volatile.
85  for (auto &I : L->blocks())
86  if (any_of(*I, [](Instruction &I) { return I.mayHaveSideEffects(); }))
87  return false;
88  return true;
89 }
91 /// This function returns true if there is no viable path from the
92 /// entry block to the header of \p L. Right now, it only does
93 /// a local search to save compile time.
94 static bool isLoopNeverExecuted(Loop *L) {
95  using namespace PatternMatch;
97  auto *Preheader = L->getLoopPreheader();
98  // TODO: We can relax this constraint, since we just need a loop
99  // predecessor.
100  assert(Preheader && "Needs preheader!");
102  if (Preheader == &Preheader->getParent()->getEntryBlock())
103  return false;
104  // All predecessors of the preheader should have a constant conditional
105  // branch, with the loop's preheader as not-taken.
106  for (auto *Pred: predecessors(Preheader)) {
107  BasicBlock *Taken, *NotTaken;
108  ConstantInt *Cond;
109  if (!match(Pred->getTerminator(),
110  m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
111  return false;
112  if (!Cond->getZExtValue())
113  std::swap(Taken, NotTaken);
114  if (Taken == Preheader)
115  return false;
116  }
117  assert(!pred_empty(Preheader) &&
118  "Preheader should have predecessors at this point!");
119  // All the predecessors have the loop preheader as not-taken target.
120  return true;
121 }
123 /// Remove a loop if it is dead.
124 ///
125 /// A loop is considered dead if it does not impact the observable behavior of
126 /// the program other than finite running time. This never removes a loop that
127 /// might be infinite (unless it is never executed), as doing so could change
128 /// the halting/non-halting nature of a program.
129 ///
130 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
131 /// order to make various safety checks work.
132 ///
133 /// \returns true if any changes were made. This may mutate the loop even if it
134 /// is unable to delete it due to hoisting trivially loop invariant
135 /// instructions out of the loop.
137  ScalarEvolution &SE, LoopInfo &LI) {
138  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
140  // We can only remove the loop if there is a preheader that we can branch from
141  // after removing it. Also, if LoopSimplify form is not available, stay out
142  // of trouble.
143  BasicBlock *Preheader = L->getLoopPreheader();
144  if (!Preheader || !L->hasDedicatedExits()) {
146  dbgs()
147  << "Deletion requires Loop with preheader and dedicated exits.\n");
149  }
150  // We can't remove loops that contain subloops. If the subloops were dead,
151  // they would already have been removed in earlier executions of this pass.
152  if (L->begin() != L->end()) {
153  LLVM_DEBUG(dbgs() << "Loop contains subloops.\n");
155  }
158  BasicBlock *ExitBlock = L->getUniqueExitBlock();
160  if (ExitBlock && isLoopNeverExecuted(L)) {
161  LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
162  // Set incoming value to undef for phi nodes in the exit block.
163  for (PHINode &P : ExitBlock->phis()) {
164  std::fill(P.incoming_values().begin(), P.incoming_values().end(),
165  UndefValue::get(P.getType()));
166  }
167  deleteDeadLoop(L, &DT, &SE, &LI);
168  ++NumDeleted;
170  }
172  // The remaining checks below are for a loop being dead because all statements
173  // in the loop are invariant.
174  SmallVector<BasicBlock *, 4> ExitingBlocks;
175  L->getExitingBlocks(ExitingBlocks);
177  // We require that the loop only have a single exit block. Otherwise, we'd
178  // be in the situation of needing to be able to solve statically which exit
179  // block will be branched to, or trying to preserve the branching logic in
180  // a loop invariant manner.
181  if (!ExitBlock) {
182  LLVM_DEBUG(dbgs() << "Deletion requires single exit block\n");
184  }
185  // Finally, we have to check that the loop really is dead.
186  bool Changed = false;
187  if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) {
188  LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
189  return Changed ? LoopDeletionResult::Modified
191  }
193  // Don't remove loops for which we can't solve the trip count.
194  // They could be infinite, in which case we'd be changing program behavior.
195  const SCEV *S = SE.getMaxBackedgeTakenCount(L);
196  if (isa<SCEVCouldNotCompute>(S)) {
197  LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
198  return Changed ? LoopDeletionResult::Modified
200  }
202  LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
203  deleteDeadLoop(L, &DT, &SE, &LI);
204  ++NumDeleted;
207 }
211  LPMUpdater &Updater) {
213  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
214  LLVM_DEBUG(L.dump());
215  std::string LoopName = L.getName();
216  auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI);
217  if (Result == LoopDeletionResult::Unmodified)
218  return PreservedAnalyses::all();
220  if (Result == LoopDeletionResult::Deleted)
221  Updater.markLoopAsDeleted(L, LoopName);
224 }
226 namespace {
227 class LoopDeletionLegacyPass : public LoopPass {
228 public:
229  static char ID; // Pass ID, replacement for typeid
230  LoopDeletionLegacyPass() : LoopPass(ID) {
232  }
234  // Possibly eliminate loop L if it is dead.
235  bool runOnLoop(Loop *L, LPPassManager &) override;
237  void getAnalysisUsage(AnalysisUsage &AU) const override {
239  }
240 };
241 }
244 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
245  "Delete dead loops", false, false)
247 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
248  "Delete dead loops", false, false)
250 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
252 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
253  if (skipLoop(L))
254  return false;
255  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
256  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
257  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
259  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
260  LLVM_DEBUG(L->dump());
262  LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI);
264  if (Result == LoopDeletionResult::Deleted)
265  LPM.markLoopAsDeleted(*L);
267  return Result != LoopDeletionResult::Unmodified;
268 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
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.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:86
bool isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:177
void initializeLoopDeletionLegacyPassPass(PassRegistry &)
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:174
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=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:68
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:1048
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:138
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
Definition: PassSupport.h:51
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
loop Delete dead loops
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI)
This function deletes dead loops.
Definition: LoopUtils.cpp:245
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
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:149
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
void dump() const
Definition: LoopInfo.cpp:371
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:562
brc_match< Cond_t > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
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:1055
const SCEV * getMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
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:117
void getExitingBlocks(SmallVectorImpl< BlockT *> &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:35
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1392
loop deletion
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:145
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:84
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
iterator begin() const
Definition: LoopInfo.h:142
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:123
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:133
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
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:583
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
#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:128
iterator end() const
Definition: LoopInfo.h:143
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:319
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
The loop was not modified.
A container for analyses that lazily runs them and caches their results.
#define LLVM_DEBUG(X)
Definition: Debug.h:123
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156