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/InstructionSimplify.h" 21 #include "llvm/Analysis/LoopIterator.h" 22 #include "llvm/Analysis/LoopPass.h" 23 #include "llvm/Analysis/MemorySSA.h" 24 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 25 #include "llvm/Analysis/ScalarEvolution.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 STATISTIC(NumBackedgesBroken, 40 "Number of loops for which we managed to break the backedge"); 41 42 static cl::opt<bool> EnableSymbolicExecution( 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 53 static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B) { 54 if (A == LoopDeletionResult::Deleted || B == LoopDeletionResult::Deleted) 55 return LoopDeletionResult::Deleted; 56 if (A == LoopDeletionResult::Modified || B == LoopDeletionResult::Modified) 57 return LoopDeletionResult::Modified; 58 return LoopDeletionResult::Unmodified; 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(ArrayRef(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 * 179 getValueOnFirstIteration(Value *V, DenseMap<Value *, Value *> &FirstIterValue, 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. 218 static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT, 219 LoopInfo &LI) { 220 // Disabled by option. 221 if (!EnableSymbolicExecution) 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 248 SmallPtrSet<BasicBlock *, 4> Visited; 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 401 breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE, 402 LoopInfo &LI, MemorySSA *MSSA, 403 OptimizationRemarkEmitter &ORE) { 404 assert(L->isLCSSAForm(DT) && "Expected LCSSA!"); 405 406 if (!L->getLoopLatch()) 407 return LoopDeletionResult::Unmodified; 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)) 414 return LoopDeletionResult::Unmodified; 415 if (!canProveExitOnFirstIteration(L, DT, LI)) 416 return LoopDeletionResult::Unmodified; 417 } 418 } 419 ++NumBackedgesBroken; 420 breakLoopBackedge(L, DT, SE, LI, MSSA); 421 return LoopDeletionResult::Deleted; 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. 438 static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, 439 ScalarEvolution &SE, LoopInfo &LI, 440 MemorySSA *MSSA, 441 OptimizationRemarkEmitter &ORE) { 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"); 452 return LoopDeletionResult::Unmodified; 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; 475 return LoopDeletionResult::Deleted; 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"); 489 return LoopDeletionResult::Unmodified; 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 496 : LoopDeletionResult::Unmodified; 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 508 return LoopDeletionResult::Deleted; 509 } 510 511 PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM, 512 LoopStandardAnalysisResults &AR, 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). 521 OptimizationRemarkEmitter ORE(L.getHeader()->getParent()); 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) { 548 initializeLoopDeletionLegacyPassPass(*PassRegistry::getPassRegistry()); 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 { 555 AU.addPreserved<MemorySSAWrapperPass>(); 556 getLoopAnalysisUsage(AU); 557 } 558 }; 559 } 560 561 char LoopDeletionLegacyPass::ID = 0; 562 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion", 563 "Delete dead loops", false, false) 564 INITIALIZE_PASS_DEPENDENCY(LoopPass) 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). 583 OptimizationRemarkEmitter ORE(L->getHeader()->getParent()); 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 } 601