llvm/lib/Transforms/Scalar/LoopDeletion.cpp

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