LLVM  7.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()) {
145  DEBUG(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  DEBUG(dbgs() << "Loop contains subloops.\n");
154  }
157  BasicBlock *ExitBlock = L->getUniqueExitBlock();
159  if (ExitBlock && isLoopNeverExecuted(L)) {
160  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  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  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.getMaxBackedgeTakenCount(L);
195  if (isa<SCEVCouldNotCompute>(S)) {
196  DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount.\n");
197  return Changed ? LoopDeletionResult::Modified
199  }
201  DEBUG(dbgs() << "Loop is invariant, delete it!");
202  deleteDeadLoop(L, &DT, &SE, &LI);
203  ++NumDeleted;
206 }
210  LPMUpdater &Updater) {
212  DEBUG(dbgs() << "Analyzing Loop for deletion: ");
213  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  DEBUG(dbgs() << "Analyzing Loop for deletion: ");
259  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: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:814
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
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:1266
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:536
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:821
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:1319
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...
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:862
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:1149
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:308
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