LLVM  7.0.0svn
LoopDeletion.cpp
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 //===----------------------------------------------------------------------===//
16 
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;
28 
29 #define DEBUG_TYPE "loop-delete"
30 
31 STATISTIC(NumDeleted, "Number of loops deleted");
32 
33 enum class LoopDeletionResult {
34  Unmodified,
35  Modified,
36  Deleted,
37 };
38 
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]);
56 
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  });
65 
66  if (!AllOutgoingValuesSame)
67  break;
68 
69  if (Instruction *I = dyn_cast<Instruction>(incoming))
70  if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
71  AllEntriesInvariant = false;
72  break;
73  }
74  }
75 
76  if (Changed)
78 
79  if (!AllEntriesInvariant || !AllOutgoingValuesSame)
80  return false;
81 
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 }
90 
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;
96 
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!");
101 
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 }
122 
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!");
139 
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()) {
145  LLVM_DEBUG(
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  }
156 
157 
158  BasicBlock *ExitBlock = L->getUniqueExitBlock();
159 
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  }
171 
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);
176 
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  }
192 
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  }
201 
202  LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
203  deleteDeadLoop(L, &DT, &SE, &LI);
204  ++NumDeleted;
205 
207 }
208 
211  LPMUpdater &Updater) {
212 
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();
219 
220  if (Result == LoopDeletionResult::Deleted)
221  Updater.markLoopAsDeleted(L, LoopName);
222 
224 }
225 
226 namespace {
227 class LoopDeletionLegacyPass : public LoopPass {
228 public:
229  static char ID; // Pass ID, replacement for typeid
230  LoopDeletionLegacyPass() : LoopPass(ID) {
232  }
233 
234  // Possibly eliminate loop L if it is dead.
235  bool runOnLoop(Loop *L, LPPassManager &) override;
236 
237  void getAnalysisUsage(AnalysisUsage &AU) const override {
239  }
240 };
241 }
242 
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)
249 
250 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
251 
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();
258 
259  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
260  LLVM_DEBUG(L->dump());
261 
262  LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI);
263 
264  if (Result == LoopDeletionResult::Deleted)
265  LPM.markLoopAsDeleted(*L);
266 
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:176
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:67
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:908
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...
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
#define INITIALIZE_PASS_DEPENDENCY(depName)
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:1343
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:142
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:153
void dump() const
Definition: LoopInfo.cpp:382
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:541
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:915
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:107
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:159
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:861
iterator begin() const
Definition: LoopInfo.h:142
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:113
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:142
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:924
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:1226
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:320
LoopDeletionResult
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.
const TerminatorInst * 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
#define LLVM_DEBUG(X)
Definition: Debug.h:119
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156