LLVM  14.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"
19 #include "llvm/Analysis/CFG.h"
23 #include "llvm/Analysis/LoopPass.h"
26 #include "llvm/IR/Dominators.h"
27 
28 #include "llvm/IR/PatternMatch.h"
29 #include "llvm/InitializePasses.h"
30 #include "llvm/Transforms/Scalar.h"
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "loop-delete"
37 
38 STATISTIC(NumDeleted, "Number of loops deleted");
39 
41  "loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true),
42  cl::desc("Break backedge through symbolic execution of 1st iteration "
43  "attempting to prove that the backedge is never taken"));
44 
45 enum class LoopDeletionResult {
46  Unmodified,
47  Modified,
48  Deleted,
49 };
50 
57 }
58 
59 /// Determines if a loop is dead.
60 ///
61 /// This assumes that we've already checked for unique exit and exiting blocks,
62 /// and that the code is in LCSSA form.
63 static bool isLoopDead(Loop *L, ScalarEvolution &SE,
64  SmallVectorImpl<BasicBlock *> &ExitingBlocks,
65  BasicBlock *ExitBlock, bool &Changed,
66  BasicBlock *Preheader, LoopInfo &LI) {
67  // Make sure that all PHI entries coming from the loop are loop invariant.
68  // Because the code is in LCSSA form, any values used outside of the loop
69  // must pass through a PHI in the exit block, meaning that this check is
70  // sufficient to guarantee that no loop-variant values are used outside
71  // of the loop.
72  bool AllEntriesInvariant = true;
73  bool AllOutgoingValuesSame = true;
74  if (!L->hasNoExitBlocks()) {
75  for (PHINode &P : ExitBlock->phis()) {
76  Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);
77 
78  // Make sure all exiting blocks produce the same incoming value for the
79  // block. If there are different incoming values for different exiting
80  // blocks, then it is impossible to statically determine which value
81  // should be used.
82  AllOutgoingValuesSame =
83  all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
84  return incoming == P.getIncomingValueForBlock(BB);
85  });
86 
87  if (!AllOutgoingValuesSame)
88  break;
89 
90  if (Instruction *I = dyn_cast<Instruction>(incoming))
91  if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) {
92  AllEntriesInvariant = false;
93  break;
94  }
95  }
96  }
97 
98  if (Changed)
100 
101  if (!AllEntriesInvariant || !AllOutgoingValuesSame)
102  return false;
103 
104  // Make sure that no instructions in the block have potential side-effects.
105  // This includes instructions that could write to memory, and loads that are
106  // marked volatile.
107  for (auto &I : L->blocks())
108  if (any_of(*I, [](Instruction &I) {
109  return I.mayHaveSideEffects() && !I.isDroppable();
110  }))
111  return false;
112 
113  // The loop or any of its sub-loops looping infinitely is legal. The loop can
114  // only be considered dead if either
115  // a. the function is mustprogress.
116  // b. all (sub-)loops are mustprogress or have a known trip-count.
117  if (L->getHeader()->getParent()->mustProgress())
118  return true;
119 
120  LoopBlocksRPO RPOT(L);
121  RPOT.perform(&LI);
122  // If the loop contains an irreducible cycle, it may loop infinitely.
123  if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
124  return false;
125 
126  SmallVector<Loop *, 8> WorkList;
127  WorkList.push_back(L);
128  while (!WorkList.empty()) {
129  Loop *Current = WorkList.pop_back_val();
130  if (hasMustProgress(Current))
131  continue;
132 
133  const SCEV *S = SE.getConstantMaxBackedgeTakenCount(Current);
134  if (isa<SCEVCouldNotCompute>(S)) {
135  LLVM_DEBUG(
136  dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
137  "not required to make progress.\n");
138  return false;
139  }
140  WorkList.append(Current->begin(), Current->end());
141  }
142  return true;
143 }
144 
145 /// This function returns true if there is no viable path from the
146 /// entry block to the header of \p L. Right now, it only does
147 /// a local search to save compile time.
148 static bool isLoopNeverExecuted(Loop *L) {
149  using namespace PatternMatch;
150 
151  auto *Preheader = L->getLoopPreheader();
152  // TODO: We can relax this constraint, since we just need a loop
153  // predecessor.
154  assert(Preheader && "Needs preheader!");
155 
156  if (Preheader->isEntryBlock())
157  return false;
158  // All predecessors of the preheader should have a constant conditional
159  // branch, with the loop's preheader as not-taken.
160  for (auto *Pred: predecessors(Preheader)) {
161  BasicBlock *Taken, *NotTaken;
162  ConstantInt *Cond;
163  if (!match(Pred->getTerminator(),
164  m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
165  return false;
166  if (!Cond->getZExtValue())
167  std::swap(Taken, NotTaken);
168  if (Taken == Preheader)
169  return false;
170  }
171  assert(!pred_empty(Preheader) &&
172  "Preheader should have predecessors at this point!");
173  // All the predecessors have the loop preheader as not-taken target.
174  return true;
175 }
176 
177 static Value *
179  const SimplifyQuery &SQ) {
180  // Quick hack: do not flood cache with non-instruction values.
181  if (!isa<Instruction>(V))
182  return V;
183  // Do we already know cached result?
184  auto Existing = FirstIterValue.find(V);
185  if (Existing != FirstIterValue.end())
186  return Existing->second;
187  Value *FirstIterV = nullptr;
188  if (auto *BO = dyn_cast<BinaryOperator>(V)) {
189  Value *LHS =
190  getValueOnFirstIteration(BO->getOperand(0), FirstIterValue, SQ);
191  Value *RHS =
192  getValueOnFirstIteration(BO->getOperand(1), FirstIterValue, SQ);
193  FirstIterV = SimplifyBinOp(BO->getOpcode(), LHS, RHS, SQ);
194  } else if (auto *Cmp = dyn_cast<ICmpInst>(V)) {
195  Value *LHS =
196  getValueOnFirstIteration(Cmp->getOperand(0), FirstIterValue, SQ);
197  Value *RHS =
198  getValueOnFirstIteration(Cmp->getOperand(1), FirstIterValue, SQ);
199  FirstIterV = SimplifyICmpInst(Cmp->getPredicate(), LHS, RHS, SQ);
200  }
201  if (!FirstIterV)
202  FirstIterV = V;
203  FirstIterValue[V] = FirstIterV;
204  return FirstIterV;
205 }
206 
207 // Try to prove that one of conditions that dominates the latch must exit on 1st
208 // iteration.
210  LoopInfo &LI) {
211  // Disabled by option.
213  return false;
214 
215  BasicBlock *Predecessor = L->getLoopPredecessor();
216  BasicBlock *Latch = L->getLoopLatch();
217 
218  if (!Predecessor || !Latch)
219  return false;
220 
221  LoopBlocksRPO RPOT(L);
222  RPOT.perform(&LI);
223 
224  // For the optimization to be correct, we need RPOT to have a property that
225  // each block is processed after all its predecessors, which may only be
226  // violated for headers of the current loop and all nested loops. Irreducible
227  // CFG provides multiple ways to break this assumption, so we do not want to
228  // deal with it.
229  if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
230  return false;
231 
232  BasicBlock *Header = L->getHeader();
233  // Blocks that are reachable on the 1st iteration.
234  SmallPtrSet<BasicBlock *, 4> LiveBlocks;
235  // Edges that are reachable on the 1st iteration.
236  DenseSet<BasicBlockEdge> LiveEdges;
237  LiveBlocks.insert(Header);
238 
240  auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) {
241  assert(LiveBlocks.count(From) && "Must be live!");
242  assert((LI.isLoopHeader(To) || !Visited.count(To)) &&
243  "Only canonical backedges are allowed. Irreducible CFG?");
244  assert((LiveBlocks.count(To) || !Visited.count(To)) &&
245  "We already discarded this block as dead!");
246  LiveBlocks.insert(To);
247  LiveEdges.insert({ From, To });
248  };
249 
250  auto MarkAllSuccessorsLive = [&](BasicBlock *BB) {
251  for (auto *Succ : successors(BB))
252  MarkLiveEdge(BB, Succ);
253  };
254 
255  // Check if there is only one value coming from all live predecessor blocks.
256  // Note that because we iterate in RPOT, we have already visited all its
257  // (non-latch) predecessors.
258  auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
259  BasicBlock *BB = PN.getParent();
260  bool HasLivePreds = false;
261  (void)HasLivePreds;
262  if (BB == Header)
263  return PN.getIncomingValueForBlock(Predecessor);
264  Value *OnlyInput = nullptr;
265  for (auto *Pred : predecessors(BB))
266  if (LiveEdges.count({ Pred, BB })) {
267  HasLivePreds = true;
268  Value *Incoming = PN.getIncomingValueForBlock(Pred);
269  // Skip undefs. If they are present, we can assume they are equal to
270  // the non-undef input.
271  if (isa<UndefValue>(Incoming))
272  continue;
273  // Two inputs.
274  if (OnlyInput && OnlyInput != Incoming)
275  return nullptr;
276  OnlyInput = Incoming;
277  }
278 
279  assert(HasLivePreds && "No live predecessors?");
280  // If all incoming live value were undefs, return undef.
281  return OnlyInput ? OnlyInput : UndefValue::get(PN.getType());
282  };
283  DenseMap<Value *, Value *> FirstIterValue;
284 
285  // Use the following algorithm to prove we never take the latch on the 1st
286  // iteration:
287  // 1. Traverse in topological order, so that whenever we visit a block, all
288  // its predecessors are already visited.
289  // 2. If we can prove that the block may have only 1 predecessor on the 1st
290  // iteration, map all its phis onto input from this predecessor.
291  // 3a. If we can prove which successor of out block is taken on the 1st
292  // iteration, mark this successor live.
293  // 3b. If we cannot prove it, conservatively assume that all successors are
294  // live.
295  auto &DL = Header->getModule()->getDataLayout();
296  const SimplifyQuery SQ(DL);
297  for (auto *BB : RPOT) {
298  Visited.insert(BB);
299 
300  // This block is not reachable on the 1st iterations.
301  if (!LiveBlocks.count(BB))
302  continue;
303 
304  // Skip inner loops.
305  if (LI.getLoopFor(BB) != L) {
306  MarkAllSuccessorsLive(BB);
307  continue;
308  }
309 
310  // If Phi has only one input from all live input blocks, use it.
311  for (auto &PN : BB->phis()) {
312  if (!PN.getType()->isIntegerTy())
313  continue;
314  auto *Incoming = GetSoleInputOnFirstIteration(PN);
315  if (Incoming && DT.dominates(Incoming, BB->getTerminator())) {
316  Value *FirstIterV =
317  getValueOnFirstIteration(Incoming, FirstIterValue, SQ);
318  FirstIterValue[&PN] = FirstIterV;
319  }
320  }
321 
322  using namespace PatternMatch;
323  Value *Cond;
324  BasicBlock *IfTrue, *IfFalse;
325  auto *Term = BB->getTerminator();
326  if (match(Term, m_Br(m_Value(Cond),
327  m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) {
328  auto *ICmp = dyn_cast<ICmpInst>(Cond);
329  if (!ICmp || !ICmp->getType()->isIntegerTy()) {
330  MarkAllSuccessorsLive(BB);
331  continue;
332  }
333 
334  // Can we prove constant true or false for this condition?
335  auto *KnownCondition = getValueOnFirstIteration(ICmp, FirstIterValue, SQ);
336  if (KnownCondition == ICmp) {
337  // Failed to simplify.
338  MarkAllSuccessorsLive(BB);
339  continue;
340  }
341  if (isa<UndefValue>(KnownCondition)) {
342  // TODO: According to langref, branching by undef is undefined behavior.
343  // It means that, theoretically, we should be able to just continue
344  // without marking any successors as live. However, we are not certain
345  // how correct our compiler is at handling such cases. So we are being
346  // very conservative here.
347  //
348  // If there is a non-loop successor, always assume this branch leaves the
349  // loop. Otherwise, arbitrarily take IfTrue.
350  //
351  // Once we are certain that branching by undef is handled correctly by
352  // other transforms, we should not mark any successors live here.
353  if (L->contains(IfTrue) && L->contains(IfFalse))
354  MarkLiveEdge(BB, IfTrue);
355  continue;
356  }
357  auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition);
358  if (!ConstCondition) {
359  // Non-constant condition, cannot analyze any further.
360  MarkAllSuccessorsLive(BB);
361  continue;
362  }
363  if (ConstCondition->isAllOnesValue())
364  MarkLiveEdge(BB, IfTrue);
365  else
366  MarkLiveEdge(BB, IfFalse);
367  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Term)) {
368  auto *SwitchValue = SI->getCondition();
369  auto *SwitchValueOnFirstIter =
370  getValueOnFirstIteration(SwitchValue, FirstIterValue, SQ);
371  auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter);
372  if (!ConstSwitchValue) {
373  MarkAllSuccessorsLive(BB);
374  continue;
375  }
376  auto CaseIterator = SI->findCaseValue(ConstSwitchValue);
377  MarkLiveEdge(BB, CaseIterator->getCaseSuccessor());
378  } else {
379  MarkAllSuccessorsLive(BB);
380  continue;
381  }
382  }
383 
384  // We can break the latch if it wasn't live.
385  return !LiveEdges.count({ Latch, Header });
386 }
387 
388 /// If we can prove the backedge is untaken, remove it. This destroys the
389 /// loop, but leaves the (now trivially loop invariant) control flow and
390 /// side effects (if any) in place.
391 static LoopDeletionResult
393  LoopInfo &LI, MemorySSA *MSSA,
395  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
396 
397  if (!L->getLoopLatch())
399 
400  auto *BTC = SE.getSymbolicMaxBackedgeTakenCount(L);
401  if (BTC->isZero()) {
402  // SCEV knows this backedge isn't taken!
403  breakLoopBackedge(L, DT, SE, LI, MSSA);
405  }
406 
407  // If SCEV leaves open the possibility of a zero trip count, see if
408  // symbolically evaluating the first iteration lets us prove the backedge
409  // unreachable.
410  if (isa<SCEVCouldNotCompute>(BTC) || !SE.isKnownNonZero(BTC))
411  if (canProveExitOnFirstIteration(L, DT, LI)) {
412  breakLoopBackedge(L, DT, SE, LI, MSSA);
414  }
415 
417 }
418 
419 /// Remove a loop if it is dead.
420 ///
421 /// A loop is considered dead either if it does not impact the observable
422 /// behavior of the program other than finite running time, or if it is
423 /// required to make progress by an attribute such as 'mustprogress' or
424 /// 'llvm.loop.mustprogress' and does not make any. This may remove
425 /// infinite loops that have been required to make progress.
426 ///
427 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
428 /// order to make various safety checks work.
429 ///
430 /// \returns true if any changes were made. This may mutate the loop even if it
431 /// is unable to delete it due to hoisting trivially loop invariant
432 /// instructions out of the loop.
434  ScalarEvolution &SE, LoopInfo &LI,
435  MemorySSA *MSSA,
437  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
438 
439  // We can only remove the loop if there is a preheader that we can branch from
440  // after removing it. Also, if LoopSimplify form is not available, stay out
441  // of trouble.
442  BasicBlock *Preheader = L->getLoopPreheader();
443  if (!Preheader || !L->hasDedicatedExits()) {
444  LLVM_DEBUG(
445  dbgs()
446  << "Deletion requires Loop with preheader and dedicated exits.\n");
448  }
449 
450  BasicBlock *ExitBlock = L->getUniqueExitBlock();
451 
452  if (ExitBlock && isLoopNeverExecuted(L)) {
453  LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
454  // We need to forget the loop before setting the incoming values of the exit
455  // phis to undef, so we properly invalidate the SCEV expressions for those
456  // phis.
457  SE.forgetLoop(L);
458  // Set incoming value to undef for phi nodes in the exit block.
459  for (PHINode &P : ExitBlock->phis()) {
460  std::fill(P.incoming_values().begin(), P.incoming_values().end(),
461  UndefValue::get(P.getType()));
462  }
463  ORE.emit([&]() {
464  return OptimizationRemark(DEBUG_TYPE, "NeverExecutes", L->getStartLoc(),
465  L->getHeader())
466  << "Loop deleted because it never executes";
467  });
468  deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
469  ++NumDeleted;
471  }
472 
473  // The remaining checks below are for a loop being dead because all statements
474  // in the loop are invariant.
475  SmallVector<BasicBlock *, 4> ExitingBlocks;
476  L->getExitingBlocks(ExitingBlocks);
477 
478  // We require that the loop has at most one exit block. Otherwise, we'd be in
479  // the situation of needing to be able to solve statically which exit block
480  // will be branched to, or trying to preserve the branching logic in a loop
481  // invariant manner.
482  if (!ExitBlock && !L->hasNoExitBlocks()) {
483  LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n");
485  }
486  // Finally, we have to check that the loop really is dead.
487  bool Changed = false;
488  if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {
489  LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
490  return Changed ? LoopDeletionResult::Modified
492  }
493 
494  LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!");
495  ORE.emit([&]() {
496  return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
497  L->getHeader())
498  << "Loop deleted because it is invariant";
499  });
500  deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
501  ++NumDeleted;
502 
504 }
505 
508  LPMUpdater &Updater) {
509 
510  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
511  LLVM_DEBUG(L.dump());
512  std::string LoopName = std::string(L.getName());
513  // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
514  // pass. Function analyses need to be preserved across loop transformations
515  // but ORE cannot be preserved (see comment before the pass definition).
517  auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE);
518 
519  // If we can prove the backedge isn't taken, just break it and be done. This
520  // leaves the loop structure in place which means it can handle dispatching
521  // to the right exit based on whatever loop invariant structure remains.
522  if (Result != LoopDeletionResult::Deleted)
523  Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI,
524  AR.MSSA, ORE));
525 
526  if (Result == LoopDeletionResult::Unmodified)
527  return PreservedAnalyses::all();
528 
529  if (Result == LoopDeletionResult::Deleted)
530  Updater.markLoopAsDeleted(L, LoopName);
531 
532  auto PA = getLoopPassPreservedAnalyses();
533  if (AR.MSSA)
534  PA.preserve<MemorySSAAnalysis>();
535  return PA;
536 }
537 
538 namespace {
539 class LoopDeletionLegacyPass : public LoopPass {
540 public:
541  static char ID; // Pass ID, replacement for typeid
542  LoopDeletionLegacyPass() : LoopPass(ID) {
544  }
545 
546  // Possibly eliminate loop L if it is dead.
547  bool runOnLoop(Loop *L, LPPassManager &) override;
548 
549  void getAnalysisUsage(AnalysisUsage &AU) const override {
552  }
553 };
554 }
555 
557 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
558  "Delete dead loops", false, false)
560 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
561  "Delete dead loops", false, false)
562 
563 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
564 
565 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
566  if (skipLoop(L))
567  return false;
568  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
569  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
570  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
571  auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
572  MemorySSA *MSSA = nullptr;
573  if (MSSAAnalysis)
574  MSSA = &MSSAAnalysis->getMSSA();
575  // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
576  // pass. Function analyses need to be preserved across loop transformations
577  // but ORE cannot be preserved (see comment before the pass definition).
579 
580  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
581  LLVM_DEBUG(L->dump());
582 
583  LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE);
584 
585  // If we can prove the backedge isn't taken, just break it and be done. This
586  // leaves the loop structure in place which means it can handle dispatching
587  // to the right exit based on whatever loop invariant structure remains.
588  if (Result != LoopDeletionResult::Deleted)
589  Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE));
590 
591  if (Result == LoopDeletionResult::Deleted)
592  LPM.markLoopAsDeleted(*L);
593 
594  return Result != LoopDeletionResult::Unmodified;
595 }
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
---------------------— PointerInfo ------------------------------------—
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
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
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:7542
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:433
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
canProveExitOnFirstIteration
static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT, LoopInfo &LI)
Definition: LoopDeletion.cpp:209
llvm::deleteDeadLoop
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
Definition: LoopUtils.cpp:477
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:858
llvm::SmallVector< Loop *, 8 >
Statistic.h
llvm::ScalarEvolution::isKnownNonZero
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
Definition: ScalarEvolution.cpp:9838
llvm::LoopBase::getLoopPredecessor
BlockT * getLoopPredecessor() const
If the given loop's header has exactly one unique predecessor outside the loop, return it.
Definition: LoopInfoImpl.h:195
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:461
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:149
GlobalsModRef.h
deletion
loop deletion
Definition: LoopDeletion.cpp:560
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
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:45
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:392
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::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:55
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
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::LoopBlocksRPO
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
llvm::LoopDeletionPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopDeletion.cpp:506
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
LoopDeletionResult::Deleted
@ Deleted
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
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:1551
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:981
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:648
llvm::SimplifyICmpInst
Value * SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an ICmpInst, fold the result or return null.
Definition: InstructionSimplify.cpp:3699
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:51
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:1771
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:148
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:866
LoopIterator.h
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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:704
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:140
llvm::cl::opt< bool >
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:249
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::SimplifyBinOp
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
Definition: InstructionSimplify.cpp:5316
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:705
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::ScalarEvolution::getSymbolicMaxBackedgeTakenCount
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
Definition: ScalarEvolution.h:866
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
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::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
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
SI
StandardInstrumentations SI(Debug, VerifyEach)
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:269
LoopPassManager.h
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:931
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
CFG.h
llvm::LoopInfo
Definition: LoopInfo.h:1083
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:1558
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
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 &)
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
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::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:980
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:7452
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::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
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:626
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:561
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: LoopInfo.cpp:1112
SmallVector.h
LoopDeletionResult::Unmodified
@ Unmodified
Dominators.h
InstructionSimplify.h
LoopDeletion.h
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:61
llvm::PHINode
Definition: Instructions.h:2633
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
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3212
llvm::PatternMatch::m_BasicBlock
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:160
llvm::cl::desc
Definition: CommandLine.h:414
getValueOnFirstIteration
static Value * getValueOnFirstIteration(Value *V, DenseMap< Value *, Value * > &FirstIterValue, const SimplifyQuery &SQ)
Definition: LoopDeletion.cpp:178
llvm::LoopUnrollResult::Unmodified
@ Unmodified
The loop was not modified.
llvm::LoopBlocksRPO::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:180
isLoopDead
static bool isLoopDead(Loop *L, ScalarEvolution &SE, SmallVectorImpl< BasicBlock * > &ExitingBlocks, BasicBlock *ExitBlock, bool &Changed, BasicBlock *Preheader, LoopInfo &LI)
Determines if a loop is dead.
Definition: LoopDeletion.cpp:63
llvm::createLoopDeletionPass
Pass * createLoopDeletionPass()
Definition: LoopDeletion.cpp:563
DEBUG_TYPE
#define DEBUG_TYPE
Definition: LoopDeletion.cpp:36
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
EnableSymbolicExecution
static cl::opt< bool > EnableSymbolicExecution("loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true), cl::desc("Break backedge through symbolic execution of 1st iteration " "attempting to prove that the backedge is never taken"))