LLVM  6.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  BasicBlock::iterator BI = ExitBlock->begin();
53  bool AllEntriesInvariant = true;
54  bool AllOutgoingValuesSame = true;
55  while (PHINode *P = dyn_cast<PHINode>(BI)) {
56  Value *incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
57 
58  // Make sure all exiting blocks produce the same incoming value for the exit
59  // block. If there are different incoming values for different exiting
60  // blocks, then it is impossible to statically determine which value should
61  // be used.
62  AllOutgoingValuesSame =
63  all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
64  return incoming == P->getIncomingValueForBlock(BB);
65  });
66 
67  if (!AllOutgoingValuesSame)
68  break;
69 
70  if (Instruction *I = dyn_cast<Instruction>(incoming))
71  if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
72  AllEntriesInvariant = false;
73  break;
74  }
75 
76  ++BI;
77  }
78 
79  if (Changed)
81 
82  if (!AllEntriesInvariant || !AllOutgoingValuesSame)
83  return false;
84 
85  // Make sure that no instructions in the block have potential side-effects.
86  // This includes instructions that could write to memory, and loads that are
87  // marked volatile.
88  for (auto &I : L->blocks())
89  if (any_of(*I, [](Instruction &I) { return I.mayHaveSideEffects(); }))
90  return false;
91  return true;
92 }
93 
94 /// This function returns true if there is no viable path from the
95 /// entry block to the header of \p L. Right now, it only does
96 /// a local search to save compile time.
97 static bool isLoopNeverExecuted(Loop *L) {
98  using namespace PatternMatch;
99 
100  auto *Preheader = L->getLoopPreheader();
101  // TODO: We can relax this constraint, since we just need a loop
102  // predecessor.
103  assert(Preheader && "Needs preheader!");
104 
105  if (Preheader == &Preheader->getParent()->getEntryBlock())
106  return false;
107  // All predecessors of the preheader should have a constant conditional
108  // branch, with the loop's preheader as not-taken.
109  for (auto *Pred: predecessors(Preheader)) {
110  BasicBlock *Taken, *NotTaken;
111  ConstantInt *Cond;
112  if (!match(Pred->getTerminator(),
113  m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
114  return false;
115  if (!Cond->getZExtValue())
116  std::swap(Taken, NotTaken);
117  if (Taken == Preheader)
118  return false;
119  }
120  assert(!pred_empty(Preheader) &&
121  "Preheader should have predecessors at this point!");
122  // All the predecessors have the loop preheader as not-taken target.
123  return true;
124 }
125 
126 /// Remove a loop if it is dead.
127 ///
128 /// A loop is considered dead if it does not impact the observable behavior of
129 /// the program other than finite running time. This never removes a loop that
130 /// might be infinite (unless it is never executed), as doing so could change
131 /// the halting/non-halting nature of a program.
132 ///
133 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
134 /// order to make various safety checks work.
135 ///
136 /// \returns true if any changes were made. This may mutate the loop even if it
137 /// is unable to delete it due to hoisting trivially loop invariant
138 /// instructions out of the loop.
140  ScalarEvolution &SE, LoopInfo &LI) {
141  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
142 
143  // We can only remove the loop if there is a preheader that we can branch from
144  // after removing it. Also, if LoopSimplify form is not available, stay out
145  // of trouble.
146  BasicBlock *Preheader = L->getLoopPreheader();
147  if (!Preheader || !L->hasDedicatedExits()) {
148  DEBUG(dbgs()
149  << "Deletion requires Loop with preheader and dedicated exits.\n");
151  }
152  // We can't remove loops that contain subloops. If the subloops were dead,
153  // they would already have been removed in earlier executions of this pass.
154  if (L->begin() != L->end()) {
155  DEBUG(dbgs() << "Loop contains subloops.\n");
157  }
158 
159 
160  BasicBlock *ExitBlock = L->getUniqueExitBlock();
161 
162  if (ExitBlock && isLoopNeverExecuted(L)) {
163  DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
164  // Set incoming value to undef for phi nodes in the exit block.
165  BasicBlock::iterator BI = ExitBlock->begin();
166  while (PHINode *P = dyn_cast<PHINode>(BI)) {
167  for (unsigned i = 0; i < P->getNumIncomingValues(); i++)
168  P->setIncomingValue(i, UndefValue::get(P->getType()));
169  BI++;
170  }
171  deleteDeadLoop(L, &DT, &SE, &LI);
172  ++NumDeleted;
174  }
175 
176  // The remaining checks below are for a loop being dead because all statements
177  // in the loop are invariant.
178  SmallVector<BasicBlock *, 4> ExitingBlocks;
179  L->getExitingBlocks(ExitingBlocks);
180 
181  // We require that the loop only have a single exit block. Otherwise, we'd
182  // be in the situation of needing to be able to solve statically which exit
183  // block will be branched to, or trying to preserve the branching logic in
184  // a loop invariant manner.
185  if (!ExitBlock) {
186  DEBUG(dbgs() << "Deletion requires single exit block\n");
188  }
189  // Finally, we have to check that the loop really is dead.
190  bool Changed = false;
191  if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) {
192  DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
193  return Changed ? LoopDeletionResult::Modified
195  }
196 
197  // Don't remove loops for which we can't solve the trip count.
198  // They could be infinite, in which case we'd be changing program behavior.
199  const SCEV *S = SE.getMaxBackedgeTakenCount(L);
200  if (isa<SCEVCouldNotCompute>(S)) {
201  DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
202  return Changed ? LoopDeletionResult::Modified
204  }
205 
206  DEBUG(dbgs() << "Loop is invariant, delete it!");
207  deleteDeadLoop(L, &DT, &SE, &LI);
208  ++NumDeleted;
209 
211 }
212 
215  LPMUpdater &Updater) {
216 
217  DEBUG(dbgs() << "Analyzing Loop for deletion: ");
218  DEBUG(L.dump());
219  std::string LoopName = L.getName();
220  auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI);
221  if (Result == LoopDeletionResult::Unmodified)
222  return PreservedAnalyses::all();
223 
224  if (Result == LoopDeletionResult::Deleted)
225  Updater.markLoopAsDeleted(L, LoopName);
226 
228 }
229 
230 namespace {
231 class LoopDeletionLegacyPass : public LoopPass {
232 public:
233  static char ID; // Pass ID, replacement for typeid
234  LoopDeletionLegacyPass() : LoopPass(ID) {
236  }
237 
238  // Possibly eliminate loop L if it is dead.
239  bool runOnLoop(Loop *L, LPPassManager &) override;
240 
241  void getAnalysisUsage(AnalysisUsage &AU) const override {
243  }
244 };
245 }
246 
248 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
249  "Delete dead loops", false, false)
251 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
252  "Delete dead loops", false, false)
253 
254 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
255 
256 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
257  if (skipLoop(L))
258  return false;
259  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
260  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
261  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
262 
263  DEBUG(dbgs() << "Analyzing Loop for deletion: ");
264  DEBUG(L->dump());
265 
266  LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI);
267 
268  if (Result == LoopDeletionResult::Deleted)
269  LPM.markLoopAsDeleted(*L);
270 
271  return Result != LoopDeletionResult::Unmodified;
272 }
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 isLCSSAForm(DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:175
void initializeLoopDeletionLegacyPassPass(PassRegistry &)
The main scalar evolution driver.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:106
BasicBlock * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfo.cpp:435
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:66
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:767
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)
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
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:1140
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfo.cpp:380
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:140
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:444
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:535
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:774
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:1320
loop deletion
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...
Iterator for intrusive lists based on ilist_node.
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:864
iterator begin() const
Definition: LoopInfo.h:142
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:110
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:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
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:577
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:439
#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:1023
iterator end() const
Definition: LoopInfo.h:143
LoopDeletionResult
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
The loop was not modified.
#define DEBUG(X)
Definition: Debug.h:118
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:120
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156