LLVM  13.0.0git
LoopDeletion.cpp
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 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/LoopPass.h"
23 #include "llvm/IR/Dominators.h"
24 #include "llvm/IR/PatternMatch.h"
25 #include "llvm/InitializePasses.h"
26 #include "llvm/Transforms/Scalar.h"
29 
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "loop-delete"
33 
34 STATISTIC(NumDeleted, "Number of loops deleted");
35 
36 enum class LoopDeletionResult {
37  Unmodified,
38  Modified,
39  Deleted,
40 };
41 
48 }
49 
50 /// Determines if a loop is dead.
51 ///
52 /// This assumes that we've already checked for unique exit and exiting blocks,
53 /// and that the code is in LCSSA form.
54 static bool isLoopDead(Loop *L, ScalarEvolution &SE,
55  SmallVectorImpl<BasicBlock *> &ExitingBlocks,
56  BasicBlock *ExitBlock, bool &Changed,
57  BasicBlock *Preheader) {
58  // Make sure that all PHI entries coming from the loop are loop invariant.
59  // Because the code is in LCSSA form, any values used outside of the loop
60  // must pass through a PHI in the exit block, meaning that this check is
61  // sufficient to guarantee that no loop-variant values are used outside
62  // of the loop.
63  bool AllEntriesInvariant = true;
64  bool AllOutgoingValuesSame = true;
65  if (!L->hasNoExitBlocks()) {
66  for (PHINode &P : ExitBlock->phis()) {
67  Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);
68 
69  // Make sure all exiting blocks produce the same incoming value for the
70  // block. If there are different incoming values for different exiting
71  // blocks, then it is impossible to statically determine which value
72  // should be used.
73  AllOutgoingValuesSame =
74  all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
75  return incoming == P.getIncomingValueForBlock(BB);
76  });
77 
78  if (!AllOutgoingValuesSame)
79  break;
80 
81  if (Instruction *I = dyn_cast<Instruction>(incoming))
82  if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
83  AllEntriesInvariant = false;
84  break;
85  }
86  }
87  }
88 
89  if (Changed)
91 
92  if (!AllEntriesInvariant || !AllOutgoingValuesSame)
93  return false;
94 
95  // Make sure that no instructions in the block have potential side-effects.
96  // This includes instructions that could write to memory, and loads that are
97  // marked volatile.
98  for (auto &I : L->blocks())
99  if (any_of(*I, [](Instruction &I) {
100  return I.mayHaveSideEffects() && !I.isDroppable();
101  }))
102  return false;
103 
104  // The loop or any of its sub-loops looping infinitely is legal. The loop can
105  // only be considered dead if either
106  // a. the function is mustprogress.
107  // b. all (sub-)loops are mustprogress or have a known trip-count.
108  if (L->getHeader()->getParent()->mustProgress())
109  return true;
110 
111  SmallVector<Loop *, 8> WorkList;
112  WorkList.push_back(L);
113  while (!WorkList.empty()) {
114  Loop *Current = WorkList.pop_back_val();
115  if (hasMustProgress(Current))
116  continue;
117 
118  const SCEV *S = SE.getConstantMaxBackedgeTakenCount(Current);
119  if (isa<SCEVCouldNotCompute>(S)) {
120  LLVM_DEBUG(
121  dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
122  "not required to make progress.\n");
123  return false;
124  }
125  WorkList.append(Current->begin(), Current->end());
126  }
127  return true;
128 }
129 
130 /// This function returns true if there is no viable path from the
131 /// entry block to the header of \p L. Right now, it only does
132 /// a local search to save compile time.
133 static bool isLoopNeverExecuted(Loop *L) {
134  using namespace PatternMatch;
135 
136  auto *Preheader = L->getLoopPreheader();
137  // TODO: We can relax this constraint, since we just need a loop
138  // predecessor.
139  assert(Preheader && "Needs preheader!");
140 
141  if (Preheader->isEntryBlock())
142  return false;
143  // All predecessors of the preheader should have a constant conditional
144  // branch, with the loop's preheader as not-taken.
145  for (auto *Pred: predecessors(Preheader)) {
146  BasicBlock *Taken, *NotTaken;
147  ConstantInt *Cond;
148  if (!match(Pred->getTerminator(),
149  m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
150  return false;
151  if (!Cond->getZExtValue())
152  std::swap(Taken, NotTaken);
153  if (Taken == Preheader)
154  return false;
155  }
156  assert(!pred_empty(Preheader) &&
157  "Preheader should have predecessors at this point!");
158  // All the predecessors have the loop preheader as not-taken target.
159  return true;
160 }
161 
162 /// If we can prove the backedge is untaken, remove it. This destroys the
163 /// loop, but leaves the (now trivially loop invariant) control flow and
164 /// side effects (if any) in place.
165 static LoopDeletionResult
167  LoopInfo &LI, MemorySSA *MSSA,
169  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
170 
171  if (!L->getLoopLatch())
173 
174  auto *BTC = SE.getBackedgeTakenCount(L);
175  if (!BTC->isZero())
177 
178  breakLoopBackedge(L, DT, SE, LI, MSSA);
180 }
181 
182 /// Remove a loop if it is dead.
183 ///
184 /// A loop is considered dead either if it does not impact the observable
185 /// behavior of the program other than finite running time, or if it is
186 /// required to make progress by an attribute such as 'mustprogress' or
187 /// 'llvm.loop.mustprogress' and does not make any. This may remove
188 /// infinite loops that have been required to make progress.
189 ///
190 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
191 /// order to make various safety checks work.
192 ///
193 /// \returns true if any changes were made. This may mutate the loop even if it
194 /// is unable to delete it due to hoisting trivially loop invariant
195 /// instructions out of the loop.
197  ScalarEvolution &SE, LoopInfo &LI,
198  MemorySSA *MSSA,
200  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
201 
202  // We can only remove the loop if there is a preheader that we can branch from
203  // after removing it. Also, if LoopSimplify form is not available, stay out
204  // of trouble.
205  BasicBlock *Preheader = L->getLoopPreheader();
206  if (!Preheader || !L->hasDedicatedExits()) {
207  LLVM_DEBUG(
208  dbgs()
209  << "Deletion requires Loop with preheader and dedicated exits.\n");
211  }
212 
213  BasicBlock *ExitBlock = L->getUniqueExitBlock();
214 
215  if (ExitBlock && isLoopNeverExecuted(L)) {
216  LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
217  // We need to forget the loop before setting the incoming values of the exit
218  // phis to undef, so we properly invalidate the SCEV expressions for those
219  // phis.
220  SE.forgetLoop(L);
221  // Set incoming value to undef for phi nodes in the exit block.
222  for (PHINode &P : ExitBlock->phis()) {
223  std::fill(P.incoming_values().begin(), P.incoming_values().end(),
224  UndefValue::get(P.getType()));
225  }
226  ORE.emit([&]() {
227  return OptimizationRemark(DEBUG_TYPE, "NeverExecutes", L->getStartLoc(),
228  L->getHeader())
229  << "Loop deleted because it never executes";
230  });
231  deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
232  ++NumDeleted;
234  }
235 
236  // The remaining checks below are for a loop being dead because all statements
237  // in the loop are invariant.
238  SmallVector<BasicBlock *, 4> ExitingBlocks;
239  L->getExitingBlocks(ExitingBlocks);
240 
241  // We require that the loop has at most one exit block. Otherwise, we'd be in
242  // the situation of needing to be able to solve statically which exit block
243  // will be branched to, or trying to preserve the branching logic in a loop
244  // invariant manner.
245  if (!ExitBlock && !L->hasNoExitBlocks()) {
246  LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n");
248  }
249  // Finally, we have to check that the loop really is dead.
250  bool Changed = false;
251  if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader)) {
252  LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
253  return Changed ? LoopDeletionResult::Modified
255  }
256 
257  LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
258  ORE.emit([&]() {
259  return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
260  L->getHeader())
261  << "Loop deleted because it is invariant";
262  });
263  deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
264  ++NumDeleted;
265 
267 }
268 
271  LPMUpdater &Updater) {
272 
273  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
274  LLVM_DEBUG(L.dump());
275  std::string LoopName = std::string(L.getName());
276  // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
277  // pass. Function analyses need to be preserved across loop transformations
278  // but ORE cannot be preserved (see comment before the pass definition).
280  auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE);
281 
282  // If we can prove the backedge isn't taken, just break it and be done. This
283  // leaves the loop structure in place which means it can handle dispatching
284  // to the right exit based on whatever loop invariant structure remains.
285  if (Result != LoopDeletionResult::Deleted)
286  Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI,
287  AR.MSSA, ORE));
288 
289  if (Result == LoopDeletionResult::Unmodified)
290  return PreservedAnalyses::all();
291 
292  if (Result == LoopDeletionResult::Deleted)
293  Updater.markLoopAsDeleted(L, LoopName);
294 
295  auto PA = getLoopPassPreservedAnalyses();
296  if (AR.MSSA)
297  PA.preserve<MemorySSAAnalysis>();
298  return PA;
299 }
300 
301 namespace {
302 class LoopDeletionLegacyPass : public LoopPass {
303 public:
304  static char ID; // Pass ID, replacement for typeid
305  LoopDeletionLegacyPass() : LoopPass(ID) {
307  }
308 
309  // Possibly eliminate loop L if it is dead.
310  bool runOnLoop(Loop *L, LPPassManager &) override;
311 
312  void getAnalysisUsage(AnalysisUsage &AU) const override {
315  }
316 };
317 }
318 
320 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
321  "Delete dead loops", false, false)
323 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
324  "Delete dead loops", false, false)
325 
326 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
327 
328 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
329  if (skipLoop(L))
330  return false;
331  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
332  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
333  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
334  auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
335  MemorySSA *MSSA = nullptr;
336  if (MSSAAnalysis)
337  MSSA = &MSSAAnalysis->getMSSA();
338  // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
339  // pass. Function analyses need to be preserved across loop transformations
340  // but ORE cannot be preserved (see comment before the pass definition).
342 
343  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
344  LLVM_DEBUG(L->dump());
345 
346  LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE);
347 
348  // If we can prove the backedge isn't taken, just break it and be done. This
349  // leaves the loop structure in place which means it can handle dispatching
350  // to the right exit based on whatever loop invariant structure remains.
351  if (Result != LoopDeletionResult::Deleted)
352  Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE));
353 
354  if (Result == LoopDeletionResult::Deleted)
355  LPM.markLoopAsDeleted(*L);
356 
357  return Result != LoopDeletionResult::Unmodified;
358 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm
Definition: AllocatorList.h:23
llvm::LoopBase::getUniqueExitBlock
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:138
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
Scalar.h
llvm::ScalarEvolution::forgetLoopDispositions
void forgetLoopDispositions(const Loop *L)
Called when the client has changed the disposition of values in this loop.
Definition: ScalarEvolution.cpp:7406
deleteLoopIfDead
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA, OptimizationRemarkEmitter &ORE)
Remove a loop if it is dead.
Definition: LoopDeletion.cpp:196
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::deleteDeadLoop
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
Definition: LoopUtils.cpp:538
llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
Definition: ScalarEvolution.h:817
llvm::SmallVector< Loop *, 8 >
Statistic.h
llvm::Loop::getStartLoc
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:633
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:150
GlobalsModRef.h
deletion
loop deletion
Definition: LoopDeletion.cpp:323
llvm::PatternMatch::m_Br
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
Definition: PatternMatch.h:1741
LoopDeletionResult
LoopDeletionResult
Definition: LoopDeletion.cpp:36
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion", "Delete dead loops", false, false) INITIALIZE_PASS_END(LoopDeletionLegacyPass
breakBackedgeIfNotTaken
static LoopDeletionResult breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA, OptimizationRemarkEmitter &ORE)
If we can prove the backedge is untaken, remove it.
Definition: LoopDeletion.cpp:166
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::LoopBase::begin
iterator begin() const
Definition: LoopInfo.h:154
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:634
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
loop
Analysis the ScalarEvolution expression for r is< loop > Outside the loop
Definition: README.txt:8
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::LoopDeletionPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopDeletion.cpp:269
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
LoopDeletionResult::Deleted
@ Deleted
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::all_of
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:1482
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:961
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:647
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopBase::end
iterator end() const
Definition: LoopInfo.h:155
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
false
Definition: StackSlotColoring.cpp:142
merge
static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)
Definition: LoopDeletion.cpp:42
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::PatternMatch::m_ConstantInt
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:145
llvm::Instruction
Definition: Instruction.h:45
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
LoopDeletionResult::Modified
@ Modified
llvm::LoopBase::getExitingBlocks
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
Definition: LoopInfoImpl.h:34
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1783
LoopUtils.h
llvm::LPPassManager
Definition: LoopPass.h:75
PatternMatch.h
isLoopNeverExecuted
static bool isLoopNeverExecuted(Loop *L)
This function returns true if there is no viable path from the entry block to the header of L.
Definition: LoopDeletion.cpp:133
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:863
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::breakLoopBackedge
void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)
Remove the backedge of the specified loop.
Definition: LoopUtils.cpp:765
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:140
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:78
llvm::LoopPass
Definition: LoopPass.h:27
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:240
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:704
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
llvm::LoopBase::hasDedicatedExits
bool hasDedicatedExits() const
Return true if no exit block for the loop has a predecessor that is outside the loop.
Definition: LoopInfoImpl.h:92
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::OptimizationRemarkEmitter::emit
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Definition: OptimizationRemarkEmitter.cpp:77
llvm::LPMUpdater::markLoopAsDeleted
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
Definition: LoopPassManager.h:260
LoopPassManager.h
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:922
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::any_of
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:1489
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
llvm::Loop::makeLoopInvariant
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:74
LoopPass.h
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::initializeLoopDeletionLegacyPassPass
void initializeLoopDeletionLegacyPassPass(PassRegistry &)
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:56
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:119
llvm::BasicBlock::getTerminator
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:148
llvm::ScalarEvolution::forgetLoop
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
Definition: ScalarEvolution.cpp:7316
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:461
llvm::LPPassManager::markLoopAsDeleted
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:113
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:669
llvm::Function::mustProgress
bool mustProgress() const
Determine if the function is required to make forward progress.
Definition: Function.h:668
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:476
loops
loop Delete dead loops
Definition: LoopDeletion.cpp:324
llvm::LoopBase::hasNoExitBlocks
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
Definition: LoopInfoImpl.h:73
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:684
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
MemorySSA.h
llvm::hasMustProgress
bool hasMustProgress(const Loop *L)
Look for the loop attribute that requires progress within the loop.
Definition: LoopUtils.cpp:417
SmallVector.h
LoopDeletionResult::Unmodified
@ Unmodified
Dominators.h
LoopDeletion.h
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:61
llvm::PHINode
Definition: Instructions.h:2600
llvm::SmallVectorImpl< BasicBlock * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::LoopUnrollResult::Unmodified
@ Unmodified
The loop was not modified.
llvm::ScalarEvolution::getBackedgeTakenCount
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
Definition: ScalarEvolution.cpp:7148
llvm::createLoopDeletionPass
Pass * createLoopDeletionPass()
Definition: LoopDeletion.cpp:326
DEBUG_TYPE
#define DEBUG_TYPE
Definition: LoopDeletion.cpp:32
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
isLoopDead
static bool isLoopDead(Loop *L, ScalarEvolution &SE, SmallVectorImpl< BasicBlock * > &ExitingBlocks, BasicBlock *ExitBlock, bool &Changed, BasicBlock *Preheader)
Determines if a loop is dead.
Definition: LoopDeletion.cpp:54
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38