LLVM  16.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"
22 #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  /*MSSAU=*/nullptr, &SE)) {
95  AllEntriesInvariant = false;
96  break;
97  }
98  }
99  }
100  }
101 
102  if (!AllEntriesInvariant || !AllOutgoingValuesSame)
103  return false;
104 
105  // Make sure that no instructions in the block have potential side-effects.
106  // This includes instructions that could write to memory, and loads that are
107  // marked volatile.
108  for (const auto &I : L->blocks())
109  if (any_of(*I, [](Instruction &I) {
110  return I.mayHaveSideEffects() && !I.isDroppable();
111  }))
112  return false;
113 
114  // The loop or any of its sub-loops looping infinitely is legal. The loop can
115  // only be considered dead if either
116  // a. the function is mustprogress.
117  // b. all (sub-)loops are mustprogress or have a known trip-count.
118  if (L->getHeader()->getParent()->mustProgress())
119  return true;
120 
121  LoopBlocksRPO RPOT(L);
122  RPOT.perform(&LI);
123  // If the loop contains an irreducible cycle, it may loop infinitely.
124  if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
125  return false;
126 
127  SmallVector<Loop *, 8> WorkList;
128  WorkList.push_back(L);
129  while (!WorkList.empty()) {
130  Loop *Current = WorkList.pop_back_val();
131  if (hasMustProgress(Current))
132  continue;
133 
134  const SCEV *S = SE.getConstantMaxBackedgeTakenCount(Current);
135  if (isa<SCEVCouldNotCompute>(S)) {
136  LLVM_DEBUG(
137  dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
138  "not required to make progress.\n");
139  return false;
140  }
141  WorkList.append(Current->begin(), Current->end());
142  }
143  return true;
144 }
145 
146 /// This function returns true if there is no viable path from the
147 /// entry block to the header of \p L. Right now, it only does
148 /// a local search to save compile time.
149 static bool isLoopNeverExecuted(Loop *L) {
150  using namespace PatternMatch;
151 
152  auto *Preheader = L->getLoopPreheader();
153  // TODO: We can relax this constraint, since we just need a loop
154  // predecessor.
155  assert(Preheader && "Needs preheader!");
156 
157  if (Preheader->isEntryBlock())
158  return false;
159  // All predecessors of the preheader should have a constant conditional
160  // branch, with the loop's preheader as not-taken.
161  for (auto *Pred: predecessors(Preheader)) {
162  BasicBlock *Taken, *NotTaken;
163  ConstantInt *Cond;
164  if (!match(Pred->getTerminator(),
165  m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
166  return false;
167  if (!Cond->getZExtValue())
168  std::swap(Taken, NotTaken);
169  if (Taken == Preheader)
170  return false;
171  }
172  assert(!pred_empty(Preheader) &&
173  "Preheader should have predecessors at this point!");
174  // All the predecessors have the loop preheader as not-taken target.
175  return true;
176 }
177 
178 static Value *
180  const SimplifyQuery &SQ) {
181  // Quick hack: do not flood cache with non-instruction values.
182  if (!isa<Instruction>(V))
183  return V;
184  // Do we already know cached result?
185  auto Existing = FirstIterValue.find(V);
186  if (Existing != FirstIterValue.end())
187  return Existing->second;
188  Value *FirstIterV = nullptr;
189  if (auto *BO = dyn_cast<BinaryOperator>(V)) {
190  Value *LHS =
191  getValueOnFirstIteration(BO->getOperand(0), FirstIterValue, SQ);
192  Value *RHS =
193  getValueOnFirstIteration(BO->getOperand(1), FirstIterValue, SQ);
194  FirstIterV = simplifyBinOp(BO->getOpcode(), LHS, RHS, SQ);
195  } else if (auto *Cmp = dyn_cast<ICmpInst>(V)) {
196  Value *LHS =
197  getValueOnFirstIteration(Cmp->getOperand(0), FirstIterValue, SQ);
198  Value *RHS =
199  getValueOnFirstIteration(Cmp->getOperand(1), FirstIterValue, SQ);
200  FirstIterV = simplifyICmpInst(Cmp->getPredicate(), LHS, RHS, SQ);
201  } else if (auto *Select = dyn_cast<SelectInst>(V)) {
202  Value *Cond =
203  getValueOnFirstIteration(Select->getCondition(), FirstIterValue, SQ);
204  if (auto *C = dyn_cast<ConstantInt>(Cond)) {
205  auto *Selected = C->isAllOnesValue() ? Select->getTrueValue()
206  : Select->getFalseValue();
207  FirstIterV = getValueOnFirstIteration(Selected, FirstIterValue, SQ);
208  }
209  }
210  if (!FirstIterV)
211  FirstIterV = V;
212  FirstIterValue[V] = FirstIterV;
213  return FirstIterV;
214 }
215 
216 // Try to prove that one of conditions that dominates the latch must exit on 1st
217 // iteration.
219  LoopInfo &LI) {
220  // Disabled by option.
222  return false;
223 
224  BasicBlock *Predecessor = L->getLoopPredecessor();
225  BasicBlock *Latch = L->getLoopLatch();
226 
227  if (!Predecessor || !Latch)
228  return false;
229 
230  LoopBlocksRPO RPOT(L);
231  RPOT.perform(&LI);
232 
233  // For the optimization to be correct, we need RPOT to have a property that
234  // each block is processed after all its predecessors, which may only be
235  // violated for headers of the current loop and all nested loops. Irreducible
236  // CFG provides multiple ways to break this assumption, so we do not want to
237  // deal with it.
238  if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
239  return false;
240 
241  BasicBlock *Header = L->getHeader();
242  // Blocks that are reachable on the 1st iteration.
243  SmallPtrSet<BasicBlock *, 4> LiveBlocks;
244  // Edges that are reachable on the 1st iteration.
245  DenseSet<BasicBlockEdge> LiveEdges;
246  LiveBlocks.insert(Header);
247 
249  auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) {
250  assert(LiveBlocks.count(From) && "Must be live!");
251  assert((LI.isLoopHeader(To) || !Visited.count(To)) &&
252  "Only canonical backedges are allowed. Irreducible CFG?");
253  assert((LiveBlocks.count(To) || !Visited.count(To)) &&
254  "We already discarded this block as dead!");
255  LiveBlocks.insert(To);
256  LiveEdges.insert({ From, To });
257  };
258 
259  auto MarkAllSuccessorsLive = [&](BasicBlock *BB) {
260  for (auto *Succ : successors(BB))
261  MarkLiveEdge(BB, Succ);
262  };
263 
264  // Check if there is only one value coming from all live predecessor blocks.
265  // Note that because we iterate in RPOT, we have already visited all its
266  // (non-latch) predecessors.
267  auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
268  BasicBlock *BB = PN.getParent();
269  bool HasLivePreds = false;
270  (void)HasLivePreds;
271  if (BB == Header)
272  return PN.getIncomingValueForBlock(Predecessor);
273  Value *OnlyInput = nullptr;
274  for (auto *Pred : predecessors(BB))
275  if (LiveEdges.count({ Pred, BB })) {
276  HasLivePreds = true;
277  Value *Incoming = PN.getIncomingValueForBlock(Pred);
278  // Skip undefs. If they are present, we can assume they are equal to
279  // the non-undef input.
280  if (isa<UndefValue>(Incoming))
281  continue;
282  // Two inputs.
283  if (OnlyInput && OnlyInput != Incoming)
284  return nullptr;
285  OnlyInput = Incoming;
286  }
287 
288  assert(HasLivePreds && "No live predecessors?");
289  // If all incoming live value were undefs, return undef.
290  return OnlyInput ? OnlyInput : UndefValue::get(PN.getType());
291  };
292  DenseMap<Value *, Value *> FirstIterValue;
293 
294  // Use the following algorithm to prove we never take the latch on the 1st
295  // iteration:
296  // 1. Traverse in topological order, so that whenever we visit a block, all
297  // its predecessors are already visited.
298  // 2. If we can prove that the block may have only 1 predecessor on the 1st
299  // iteration, map all its phis onto input from this predecessor.
300  // 3a. If we can prove which successor of out block is taken on the 1st
301  // iteration, mark this successor live.
302  // 3b. If we cannot prove it, conservatively assume that all successors are
303  // live.
304  auto &DL = Header->getModule()->getDataLayout();
305  const SimplifyQuery SQ(DL);
306  for (auto *BB : RPOT) {
307  Visited.insert(BB);
308 
309  // This block is not reachable on the 1st iterations.
310  if (!LiveBlocks.count(BB))
311  continue;
312 
313  // Skip inner loops.
314  if (LI.getLoopFor(BB) != L) {
315  MarkAllSuccessorsLive(BB);
316  continue;
317  }
318 
319  // If Phi has only one input from all live input blocks, use it.
320  for (auto &PN : BB->phis()) {
321  if (!PN.getType()->isIntegerTy())
322  continue;
323  auto *Incoming = GetSoleInputOnFirstIteration(PN);
324  if (Incoming && DT.dominates(Incoming, BB->getTerminator())) {
325  Value *FirstIterV =
326  getValueOnFirstIteration(Incoming, FirstIterValue, SQ);
327  FirstIterValue[&PN] = FirstIterV;
328  }
329  }
330 
331  using namespace PatternMatch;
332  Value *Cond;
333  BasicBlock *IfTrue, *IfFalse;
334  auto *Term = BB->getTerminator();
335  if (match(Term, m_Br(m_Value(Cond),
336  m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) {
337  auto *ICmp = dyn_cast<ICmpInst>(Cond);
338  if (!ICmp || !ICmp->getType()->isIntegerTy()) {
339  MarkAllSuccessorsLive(BB);
340  continue;
341  }
342 
343  // Can we prove constant true or false for this condition?
344  auto *KnownCondition = getValueOnFirstIteration(ICmp, FirstIterValue, SQ);
345  if (KnownCondition == ICmp) {
346  // Failed to simplify.
347  MarkAllSuccessorsLive(BB);
348  continue;
349  }
350  if (isa<UndefValue>(KnownCondition)) {
351  // TODO: According to langref, branching by undef is undefined behavior.
352  // It means that, theoretically, we should be able to just continue
353  // without marking any successors as live. However, we are not certain
354  // how correct our compiler is at handling such cases. So we are being
355  // very conservative here.
356  //
357  // If there is a non-loop successor, always assume this branch leaves the
358  // loop. Otherwise, arbitrarily take IfTrue.
359  //
360  // Once we are certain that branching by undef is handled correctly by
361  // other transforms, we should not mark any successors live here.
362  if (L->contains(IfTrue) && L->contains(IfFalse))
363  MarkLiveEdge(BB, IfTrue);
364  continue;
365  }
366  auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition);
367  if (!ConstCondition) {
368  // Non-constant condition, cannot analyze any further.
369  MarkAllSuccessorsLive(BB);
370  continue;
371  }
372  if (ConstCondition->isAllOnesValue())
373  MarkLiveEdge(BB, IfTrue);
374  else
375  MarkLiveEdge(BB, IfFalse);
376  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Term)) {
377  auto *SwitchValue = SI->getCondition();
378  auto *SwitchValueOnFirstIter =
379  getValueOnFirstIteration(SwitchValue, FirstIterValue, SQ);
380  auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter);
381  if (!ConstSwitchValue) {
382  MarkAllSuccessorsLive(BB);
383  continue;
384  }
385  auto CaseIterator = SI->findCaseValue(ConstSwitchValue);
386  MarkLiveEdge(BB, CaseIterator->getCaseSuccessor());
387  } else {
388  MarkAllSuccessorsLive(BB);
389  continue;
390  }
391  }
392 
393  // We can break the latch if it wasn't live.
394  return !LiveEdges.count({ Latch, Header });
395 }
396 
397 /// If we can prove the backedge is untaken, remove it. This destroys the
398 /// loop, but leaves the (now trivially loop invariant) control flow and
399 /// side effects (if any) in place.
400 static LoopDeletionResult
402  LoopInfo &LI, MemorySSA *MSSA,
404  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
405 
406  if (!L->getLoopLatch())
408 
409  auto *BTCMax = SE.getConstantMaxBackedgeTakenCount(L);
410  if (!BTCMax->isZero()) {
411  auto *BTC = SE.getBackedgeTakenCount(L);
412  if (!BTC->isZero()) {
413  if (!isa<SCEVCouldNotCompute>(BTC) && SE.isKnownNonZero(BTC))
415  if (!canProveExitOnFirstIteration(L, DT, LI))
417  }
418  }
419  ++NumBackedgesBroken;
420  breakLoopBackedge(L, DT, SE, LI, MSSA);
422 }
423 
424 /// Remove a loop if it is dead.
425 ///
426 /// A loop is considered dead either if it does not impact the observable
427 /// behavior of the program other than finite running time, or if it is
428 /// required to make progress by an attribute such as 'mustprogress' or
429 /// 'llvm.loop.mustprogress' and does not make any. This may remove
430 /// infinite loops that have been required to make progress.
431 ///
432 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
433 /// order to make various safety checks work.
434 ///
435 /// \returns true if any changes were made. This may mutate the loop even if it
436 /// is unable to delete it due to hoisting trivially loop invariant
437 /// instructions out of the loop.
439  ScalarEvolution &SE, LoopInfo &LI,
440  MemorySSA *MSSA,
442  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
443 
444  // We can only remove the loop if there is a preheader that we can branch from
445  // after removing it. Also, if LoopSimplify form is not available, stay out
446  // of trouble.
447  BasicBlock *Preheader = L->getLoopPreheader();
448  if (!Preheader || !L->hasDedicatedExits()) {
449  LLVM_DEBUG(
450  dbgs()
451  << "Deletion requires Loop with preheader and dedicated exits.\n");
453  }
454 
455  BasicBlock *ExitBlock = L->getUniqueExitBlock();
456 
457  if (ExitBlock && isLoopNeverExecuted(L)) {
458  LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!\n");
459  // We need to forget the loop before setting the incoming values of the exit
460  // phis to poison, so we properly invalidate the SCEV expressions for those
461  // phis.
462  SE.forgetLoop(L);
463  // Set incoming value to poison for phi nodes in the exit block.
464  for (PHINode &P : ExitBlock->phis()) {
465  std::fill(P.incoming_values().begin(), P.incoming_values().end(),
466  PoisonValue::get(P.getType()));
467  }
468  ORE.emit([&]() {
469  return OptimizationRemark(DEBUG_TYPE, "NeverExecutes", L->getStartLoc(),
470  L->getHeader())
471  << "Loop deleted because it never executes";
472  });
473  deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
474  ++NumDeleted;
476  }
477 
478  // The remaining checks below are for a loop being dead because all statements
479  // in the loop are invariant.
480  SmallVector<BasicBlock *, 4> ExitingBlocks;
481  L->getExitingBlocks(ExitingBlocks);
482 
483  // We require that the loop has at most one exit block. Otherwise, we'd be in
484  // the situation of needing to be able to solve statically which exit block
485  // will be branched to, or trying to preserve the branching logic in a loop
486  // invariant manner.
487  if (!ExitBlock && !L->hasNoExitBlocks()) {
488  LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n");
490  }
491  // Finally, we have to check that the loop really is dead.
492  bool Changed = false;
493  if (!isLoopDead(L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {
494  LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");
495  return Changed ? LoopDeletionResult::Modified
497  }
498 
499  LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!\n");
500  ORE.emit([&]() {
501  return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
502  L->getHeader())
503  << "Loop deleted because it is invariant";
504  });
505  deleteDeadLoop(L, &DT, &SE, &LI, MSSA);
506  ++NumDeleted;
507 
509 }
510 
513  LPMUpdater &Updater) {
514 
515  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
516  LLVM_DEBUG(L.dump());
517  std::string LoopName = std::string(L.getName());
518  // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
519  // pass. Function analyses need to be preserved across loop transformations
520  // but ORE cannot be preserved (see comment before the pass definition).
522  auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE);
523 
524  // If we can prove the backedge isn't taken, just break it and be done. This
525  // leaves the loop structure in place which means it can handle dispatching
526  // to the right exit based on whatever loop invariant structure remains.
527  if (Result != LoopDeletionResult::Deleted)
528  Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI,
529  AR.MSSA, ORE));
530 
531  if (Result == LoopDeletionResult::Unmodified)
532  return PreservedAnalyses::all();
533 
534  if (Result == LoopDeletionResult::Deleted)
535  Updater.markLoopAsDeleted(L, LoopName);
536 
537  auto PA = getLoopPassPreservedAnalyses();
538  if (AR.MSSA)
539  PA.preserve<MemorySSAAnalysis>();
540  return PA;
541 }
542 
543 namespace {
544 class LoopDeletionLegacyPass : public LoopPass {
545 public:
546  static char ID; // Pass ID, replacement for typeid
547  LoopDeletionLegacyPass() : LoopPass(ID) {
549  }
550 
551  // Possibly eliminate loop L if it is dead.
552  bool runOnLoop(Loop *L, LPPassManager &) override;
553 
554  void getAnalysisUsage(AnalysisUsage &AU) const override {
557  }
558 };
559 }
560 
562 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
563  "Delete dead loops", false, false)
565 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
566  "Delete dead loops", false, false)
567 
568 Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); }
569 
570 bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
571  if (skipLoop(L))
572  return false;
573  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
574  ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
575  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
576  auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
577  MemorySSA *MSSA = nullptr;
578  if (MSSAAnalysis)
579  MSSA = &MSSAAnalysis->getMSSA();
580  // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
581  // pass. Function analyses need to be preserved across loop transformations
582  // but ORE cannot be preserved (see comment before the pass definition).
584 
585  LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
586  LLVM_DEBUG(L->dump());
587 
588  LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE);
589 
590  // If we can prove the backedge isn't taken, just break it and be done. This
591  // leaves the loop structure in place which means it can handle dispatching
592  // to the right exit based on whatever loop invariant structure remains.
593  if (Result != LoopDeletionResult::Deleted)
594  Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE));
595 
596  if (Result == LoopDeletionResult::Deleted)
597  LPM.markLoopAsDeleted(*L);
598 
599  return Result != LoopDeletionResult::Unmodified;
600 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LoopBase::getUniqueExitBlock
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:158
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
Scalar.h
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:438
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
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:218
llvm::deleteDeadLoop
void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)
This function deletes dead loops.
Definition: LoopUtils.cpp:470
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:891
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:10678
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:211
llvm::Loop::getStartLoc
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:631
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::getLoopAnalysisUsage
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
Definition: LoopUtils.cpp:142
deletion
loop deletion
Definition: LoopDeletion.cpp:565
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
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:1731
LoopDeletionResult
LoopDeletionResult
Definition: LoopDeletion.cpp:47
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion", "Delete dead loops", false, false) INITIALIZE_PASS_END(LoopDeletionLegacyPass
ScalarEvolution.h
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:401
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::LoopBase::begin
iterator begin() const
Definition: LoopInfo.h:171
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::LoopStandardAnalysisResults::DT
DominatorTree & DT
Definition: LoopAnalysisManager.h:54
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:55
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:511
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
LoopDeletionResult::Deleted
@ Deleted
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:1709
llvm::MemorySSAWrapperPass
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:984
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
SI
@ SI
Definition: SIInstrInfo.cpp:7882
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
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:5636
llvm::LoopBase::end
iterator end() const
Definition: LoopInfo.h:172
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:195
false
Definition: StackSlotColoring.cpp:141
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:147
llvm::Instruction
Definition: Instruction.h:42
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:364
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
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:33
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1713
LoopUtils.h
llvm::LPPassManager
Definition: LoopPass.h:76
llvm::SmallVectorImpl::append
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
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:149
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:891
LoopIterator.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:687
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:137
llvm::cl::opt< bool >
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
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:3869
llvm::LoopPass
Definition: LoopPass.h:28
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:183
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:232
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:112
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:853
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:282
LoopPassManager.h
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:934
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:383
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:1108
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:1716
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
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:55
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:118
llvm::Loop::makeLoopInvariant
bool makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt=nullptr, MemorySSAUpdater *MSSAU=nullptr, ScalarEvolution *SE=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:70
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:1005
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:8371
llvm::LPPassManager::markLoopAsDeleted
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:110
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:84
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:667
llvm::Function::mustProgress
bool mustProgress() const
Determine if the function is required to make forward progress.
Definition: Function.h:596
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:56
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
loops
loop Delete dead loops
Definition: LoopDeletion.cpp:566
llvm::LoopBase::hasNoExitBlocks
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
Definition: LoopInfoImpl.h:95
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:689
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:1114
SmallVector.h
LoopDeletionResult::Unmodified
@ Unmodified
Dominators.h
InstructionSimplify.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
LoopDeletion.h
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:61
llvm::PHINode
Definition: Instructions.h:2698
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.h:119
llvm::SmallVectorImpl< BasicBlock * >
llvm::Loop::isLCSSAForm
bool isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens=true) const
Return true if the Loop is in LCSSA form.
Definition: LoopInfo.cpp:462
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
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:3277
llvm::PatternMatch::m_BasicBlock
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:168
llvm::cl::desc
Definition: CommandLine.h:413
getValueOnFirstIteration
static Value * getValueOnFirstIteration(Value *V, DenseMap< Value *, Value * > &FirstIterValue, const SimplifyQuery &SQ)
Definition: LoopDeletion.cpp:179
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
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:8241
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:568
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:365
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"))
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1732