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