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  AllEntriesInvariant = false;
95  break;
96  }
97  if (Changed) {
98  // Moving I to a different location may change its block disposition,
99  // so invalidate its SCEV.
100  SE.forgetValue(I);
101  }
102  }
103  }
104  }
105 
106  if (Changed)
108 
109  if (!AllEntriesInvariant || !AllOutgoingValuesSame)
110  return false;
111 
112  // Make sure that no instructions in the block have potential side-effects.
113  // This includes instructions that could write to memory, and loads that are
114  // marked volatile.
115  for (const auto &I : L->blocks())
116  if (any_of(*I, [](Instruction &I) {
117  return I.mayHaveSideEffects() && !I.isDroppable();
118  }))
119  return false;
120 
121  // The loop or any of its sub-loops looping infinitely is legal. The loop can
122  // only be considered dead if either
123  // a. the function is mustprogress.
124  // b. all (sub-)loops are mustprogress or have a known trip-count.
125  if (L->getHeader()->getParent()->mustProgress())
126  return true;
127 
128  LoopBlocksRPO RPOT(L);
129  RPOT.perform(&LI);
130  // If the loop contains an irreducible cycle, it may loop infinitely.
131  if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
132  return false;
133 
134  SmallVector<Loop *, 8> WorkList;
135  WorkList.push_back(L);
136  while (!WorkList.empty()) {
137  Loop *Current = WorkList.pop_back_val();
138  if (hasMustProgress(Current))
139  continue;
140 
141  const SCEV *S = SE.getConstantMaxBackedgeTakenCount(Current);
142  if (isa<SCEVCouldNotCompute>(S)) {
143  LLVM_DEBUG(
144  dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "
145  "not required to make progress.\n");
146  return false;
147  }
148  WorkList.append(Current->begin(), Current->end());
149  }
150  return true;
151 }
152 
153 /// This function returns true if there is no viable path from the
154 /// entry block to the header of \p L. Right now, it only does
155 /// a local search to save compile time.
156 static bool isLoopNeverExecuted(Loop *L) {
157  using namespace PatternMatch;
158 
159  auto *Preheader = L->getLoopPreheader();
160  // TODO: We can relax this constraint, since we just need a loop
161  // predecessor.
162  assert(Preheader && "Needs preheader!");
163 
164  if (Preheader->isEntryBlock())
165  return false;
166  // All predecessors of the preheader should have a constant conditional
167  // branch, with the loop's preheader as not-taken.
168  for (auto *Pred: predecessors(Preheader)) {
169  BasicBlock *Taken, *NotTaken;
170  ConstantInt *Cond;
171  if (!match(Pred->getTerminator(),
172  m_Br(m_ConstantInt(Cond), Taken, NotTaken)))
173  return false;
174  if (!Cond->getZExtValue())
175  std::swap(Taken, NotTaken);
176  if (Taken == Preheader)
177  return false;
178  }
179  assert(!pred_empty(Preheader) &&
180  "Preheader should have predecessors at this point!");
181  // All the predecessors have the loop preheader as not-taken target.
182  return true;
183 }
184 
185 static Value *
187  const SimplifyQuery &SQ) {
188  // Quick hack: do not flood cache with non-instruction values.
189  if (!isa<Instruction>(V))
190  return V;
191  // Do we already know cached result?
192  auto Existing = FirstIterValue.find(V);
193  if (Existing != FirstIterValue.end())
194  return Existing->second;
195  Value *FirstIterV = nullptr;
196  if (auto *BO = dyn_cast<BinaryOperator>(V)) {
197  Value *LHS =
198  getValueOnFirstIteration(BO->getOperand(0), FirstIterValue, SQ);
199  Value *RHS =
200  getValueOnFirstIteration(BO->getOperand(1), FirstIterValue, SQ);
201  FirstIterV = simplifyBinOp(BO->getOpcode(), LHS, RHS, SQ);
202  } else if (auto *Cmp = dyn_cast<ICmpInst>(V)) {
203  Value *LHS =
204  getValueOnFirstIteration(Cmp->getOperand(0), FirstIterValue, SQ);
205  Value *RHS =
206  getValueOnFirstIteration(Cmp->getOperand(1), FirstIterValue, SQ);
207  FirstIterV = simplifyICmpInst(Cmp->getPredicate(), LHS, RHS, SQ);
208  } else if (auto *Select = dyn_cast<SelectInst>(V)) {
209  Value *Cond =
210  getValueOnFirstIteration(Select->getCondition(), FirstIterValue, SQ);
211  if (auto *C = dyn_cast<ConstantInt>(Cond)) {
212  auto *Selected = C->isAllOnesValue() ? Select->getTrueValue()
213  : Select->getFalseValue();
214  FirstIterV = getValueOnFirstIteration(Selected, FirstIterValue, SQ);
215  }
216  }
217  if (!FirstIterV)
218  FirstIterV = V;
219  FirstIterValue[V] = FirstIterV;
220  return FirstIterV;
221 }
222 
223 // Try to prove that one of conditions that dominates the latch must exit on 1st
224 // iteration.
226  LoopInfo &LI) {
227  // Disabled by option.
229  return false;
230 
231  BasicBlock *Predecessor = L->getLoopPredecessor();
232  BasicBlock *Latch = L->getLoopLatch();
233 
234  if (!Predecessor || !Latch)
235  return false;
236 
237  LoopBlocksRPO RPOT(L);
238  RPOT.perform(&LI);
239 
240  // For the optimization to be correct, we need RPOT to have a property that
241  // each block is processed after all its predecessors, which may only be
242  // violated for headers of the current loop and all nested loops. Irreducible
243  // CFG provides multiple ways to break this assumption, so we do not want to
244  // deal with it.
245  if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))
246  return false;
247 
248  BasicBlock *Header = L->getHeader();
249  // Blocks that are reachable on the 1st iteration.
250  SmallPtrSet<BasicBlock *, 4> LiveBlocks;
251  // Edges that are reachable on the 1st iteration.
252  DenseSet<BasicBlockEdge> LiveEdges;
253  LiveBlocks.insert(Header);
254 
256  auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) {
257  assert(LiveBlocks.count(From) && "Must be live!");
258  assert((LI.isLoopHeader(To) || !Visited.count(To)) &&
259  "Only canonical backedges are allowed. Irreducible CFG?");
260  assert((LiveBlocks.count(To) || !Visited.count(To)) &&
261  "We already discarded this block as dead!");
262  LiveBlocks.insert(To);
263  LiveEdges.insert({ From, To });
264  };
265 
266  auto MarkAllSuccessorsLive = [&](BasicBlock *BB) {
267  for (auto *Succ : successors(BB))
268  MarkLiveEdge(BB, Succ);
269  };
270 
271  // Check if there is only one value coming from all live predecessor blocks.
272  // Note that because we iterate in RPOT, we have already visited all its
273  // (non-latch) predecessors.
274  auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
275  BasicBlock *BB = PN.getParent();
276  bool HasLivePreds = false;
277  (void)HasLivePreds;
278  if (BB == Header)
279  return PN.getIncomingValueForBlock(Predecessor);
280  Value *OnlyInput = nullptr;
281  for (auto *Pred : predecessors(BB))
282  if (LiveEdges.count({ Pred, BB })) {
283  HasLivePreds = true;
284  Value *Incoming = PN.getIncomingValueForBlock(Pred);
285  // Skip undefs. If they are present, we can assume they are equal to
286  // the non-undef input.
287  if (isa<UndefValue>(Incoming))
288  continue;
289  // Two inputs.
290  if (OnlyInput && OnlyInput != Incoming)
291  return nullptr;
292  OnlyInput = Incoming;
293  }
294 
295  assert(HasLivePreds && "No live predecessors?");
296  // If all incoming live value were undefs, return undef.
297  return OnlyInput ? OnlyInput : UndefValue::get(PN.getType());
298  };
299  DenseMap<Value *, Value *> FirstIterValue;
300 
301  // Use the following algorithm to prove we never take the latch on the 1st
302  // iteration:
303  // 1. Traverse in topological order, so that whenever we visit a block, all
304  // its predecessors are already visited.
305  // 2. If we can prove that the block may have only 1 predecessor on the 1st
306  // iteration, map all its phis onto input from this predecessor.
307  // 3a. If we can prove which successor of out block is taken on the 1st
308  // iteration, mark this successor live.
309  // 3b. If we cannot prove it, conservatively assume that all successors are
310  // live.
311  auto &DL = Header->getModule()->getDataLayout();
312  const SimplifyQuery SQ(DL);
313  for (auto *BB : RPOT) {
314  Visited.insert(BB);
315 
316  // This block is not reachable on the 1st iterations.
317  if (!LiveBlocks.count(BB))
318  continue;
319 
320  // Skip inner loops.
321  if (LI.getLoopFor(BB) != L) {
322  MarkAllSuccessorsLive(BB);
323  continue;
324  }
325 
326  // If Phi has only one input from all live input blocks, use it.
327  for (auto &PN : BB->phis()) {
328  if (!PN.getType()->isIntegerTy())
329  continue;
330  auto *Incoming = GetSoleInputOnFirstIteration(PN);
331  if (Incoming && DT.dominates(Incoming, BB->getTerminator())) {
332  Value *FirstIterV =
333  getValueOnFirstIteration(Incoming, FirstIterValue, SQ);
334  FirstIterValue[&PN] = FirstIterV;
335  }
336  }
337 
338  using namespace PatternMatch;
339  Value *Cond;
340  BasicBlock *IfTrue, *IfFalse;
341  auto *Term = BB->getTerminator();
342  if (match(Term, m_Br(m_Value(Cond),
343  m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) {
344  auto *ICmp = dyn_cast<ICmpInst>(Cond);
345  if (!ICmp || !ICmp->getType()->isIntegerTy()) {
346  MarkAllSuccessorsLive(BB);
347  continue;
348  }
349 
350  // Can we prove constant true or false for this condition?
351  auto *KnownCondition = getValueOnFirstIteration(ICmp, FirstIterValue, SQ);
352  if (KnownCondition == ICmp) {
353  // Failed to simplify.
354  MarkAllSuccessorsLive(BB);
355  continue;
356  }
357  if (isa<UndefValue>(KnownCondition)) {
358  // TODO: According to langref, branching by undef is undefined behavior.
359  // It means that, theoretically, we should be able to just continue
360  // without marking any successors as live. However, we are not certain
361  // how correct our compiler is at handling such cases. So we are being
362  // very conservative here.
363  //
364  // If there is a non-loop successor, always assume this branch leaves the
365  // loop. Otherwise, arbitrarily take IfTrue.
366  //
367  // Once we are certain that branching by undef is handled correctly by
368  // other transforms, we should not mark any successors live here.
369  if (L->contains(IfTrue) && L->contains(IfFalse))
370  MarkLiveEdge(BB, IfTrue);
371  continue;
372  }
373  auto *ConstCondition = dyn_cast<ConstantInt>(KnownCondition);
374  if (!ConstCondition) {
375  // Non-constant condition, cannot analyze any further.
376  MarkAllSuccessorsLive(BB);
377  continue;
378  }
379  if (ConstCondition->isAllOnesValue())
380  MarkLiveEdge(BB, IfTrue);
381  else
382  MarkLiveEdge(BB, IfFalse);
383  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Term)) {
384  auto *SwitchValue = SI->getCondition();
385  auto *SwitchValueOnFirstIter =
386  getValueOnFirstIteration(SwitchValue, FirstIterValue, SQ);
387  auto *ConstSwitchValue = dyn_cast<ConstantInt>(SwitchValueOnFirstIter);
388  if (!ConstSwitchValue) {
389  MarkAllSuccessorsLive(BB);
390  continue;
391  }
392  auto CaseIterator = SI->findCaseValue(ConstSwitchValue);
393  MarkLiveEdge(BB, CaseIterator->getCaseSuccessor());
394  } else {
395  MarkAllSuccessorsLive(BB);
396  continue;
397  }
398  }
399 
400  // We can break the latch if it wasn't live.
401  return !LiveEdges.count({ Latch, Header });
402 }
403 
404 /// If we can prove the backedge is untaken, remove it. This destroys the
405 /// loop, but leaves the (now trivially loop invariant) control flow and
406 /// side effects (if any) in place.
407 static LoopDeletionResult
409  LoopInfo &LI, MemorySSA *MSSA,
411  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
412 
413  if (!L->getLoopLatch())
415 
416  auto *BTCMax = SE.getConstantMaxBackedgeTakenCount(L);
417  if (!BTCMax->isZero()) {
418  auto *BTC = SE.getBackedgeTakenCount(L);
419  if (!BTC->isZero()) {
420  if (!isa<SCEVCouldNotCompute>(BTC) && SE.isKnownNonZero(BTC))
422  if (!canProveExitOnFirstIteration(L, DT, LI))
424  }
425  }
426  ++NumBackedgesBroken;
427  breakLoopBackedge(L, DT, SE, LI, MSSA);
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 poison, so we properly invalidate the SCEV expressions for those
468  // phis.
469  SE.forgetLoop(L);
470  // Set incoming value to poison 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  PoisonValue::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:152
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:137
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:445
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
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:225
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:10569
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:194
llvm::Loop::getStartLoc
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
Definition: LoopInfo.cpp:627
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:572
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:408
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:170
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: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
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:1590
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
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:5575
llvm::LoopBase::end
iterator end() const
Definition: LoopInfo.h:171
llvm::LoopBase::blocks
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:194
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:669
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:156
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:888
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:691
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:3860
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:440
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:166
llvm::ScalarEvolution::forgetValue
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
Definition: ScalarEvolution.cpp:8358
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:215
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:91
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
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: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::ScalarEvolution::forgetLoopDispositions
void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
Definition: ScalarEvolution.cpp:8385
llvm::LoopInfo
Definition: LoopInfo.h:1105
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:1597
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
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:70
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::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:1002
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:8298
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:104
llvm::Loop::dump
void dump() const
Definition: LoopInfo.cpp:663
llvm::Function::mustProgress
bool mustProgress() const
Determine if the function is required to make forward progress.
Definition: Function.h:615
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:573
llvm::LoopBase::hasNoExitBlocks
bool hasNoExitBlocks() const
Return true if this loop does not have any exit blocks.
Definition: LoopInfoImpl.h:72
llvm::OptimizationRemark
Diagnostic information for applied optimization remarks.
Definition: DiagnosticInfo.h:690
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:1110
SmallVector.h
LoopDeletionResult::Unmodified
@ Unmodified
Dominators.h
InstructionSimplify.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:659
LoopDeletion.h
llvm::LoopStandardAnalysisResults::MSSA
MemorySSA * MSSA
Definition: LoopAnalysisManager.h:61
llvm::PHINode
Definition: Instructions.h:2699
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:458
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:3278
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:186
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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:8168
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:365
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"))
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1732