llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

   1 //===--------- LoopSimplifyCFG.cpp - Loop CFG Simplification 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 Loop SimplifyCFG Pass. This pass is responsible for
  10 // basic loop CFG cleanup, primarily to assist other loop passes. If you
  11 // encounter a noncanonical CFG construct that causes another loop pass to
  12 // perform suboptimally, this is the place to fix it up.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/Analysis/AssumptionCache.h"
  20 #include "llvm/Analysis/BasicAliasAnalysis.h"
  21 #include "llvm/Analysis/DependenceAnalysis.h"
  22 #include "llvm/Analysis/DomTreeUpdater.h"
  23 #include "llvm/Analysis/GlobalsModRef.h"
  24 #include "llvm/Analysis/LoopInfo.h"
  25 #include "llvm/Analysis/LoopIterator.h"
  26 #include "llvm/Analysis/LoopPass.h"
  27 #include "llvm/Analysis/MemorySSA.h"
  28 #include "llvm/Analysis/MemorySSAUpdater.h"
  29 #include "llvm/Analysis/ScalarEvolution.h"
  30 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  31 #include "llvm/Analysis/TargetTransformInfo.h"
  32 #include "llvm/IR/Dominators.h"
  33 #include "llvm/IR/IRBuilder.h"
  34 #include "llvm/InitializePasses.h"
  35 #include "llvm/Support/CommandLine.h"
  36 #include "llvm/Transforms/Scalar.h"
  37 #include "llvm/Transforms/Scalar/LoopPassManager.h"
  38 #include "llvm/Transforms/Utils.h"
  39 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  40 #include "llvm/Transforms/Utils/Local.h"
  41 #include "llvm/Transforms/Utils/LoopUtils.h"
  42 using namespace llvm;
  43
  44 #define DEBUG_TYPE "loop-simplifycfg"
  45
  46 static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
  47                                        cl::init(true));
  48
  49 STATISTIC(NumTerminatorsFolded,
  50           "Number of terminators folded to unconditional branches");
  51 STATISTIC(NumLoopBlocksDeleted,
  52           "Number of loop blocks deleted");
  53 STATISTIC(NumLoopExitsDeleted,
  54           "Number of loop exiting edges deleted");
  55
  56 /// If \p BB is a switch or a conditional branch, but only one of its successors
  57 /// can be reached from this block in runtime, return this successor. Otherwise,
  58 /// return nullptr.
  59 static BasicBlock *getOnlyLiveSuccessor(BasicBlock *BB) {
  60   Instruction *TI = BB->getTerminator();
  61   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
  62     if (BI->isUnconditional())
  63       return nullptr;
  64     if (BI->getSuccessor(0) == BI->getSuccessor(1))
  65       return BI->getSuccessor(0);
  66     ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
  67     if (!Cond)
  68       return nullptr;
  69     return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
  70   }
  71
  72   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
  73     auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
  74     if (!CI)
  75       return nullptr;
  76     for (auto Case : SI->cases())
  77       if (Case.getCaseValue() == CI)
  78         return Case.getCaseSuccessor();
  79     return SI->getDefaultDest();
  80   }
  81
  82   return nullptr;
  83 }
  84
  85 /// Removes \p BB from all loops from [FirstLoop, LastLoop) in parent chain.
  86 static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop,
  87                                  Loop *LastLoop = nullptr) {
  88   assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&
  89          "First loop is supposed to be inside of last loop!");
  90   assert(FirstLoop->contains(BB) && "Must be a loop block!");
  91   for (Loop *Current = FirstLoop; Current != LastLoop;
  92        Current = Current->getParentLoop())
  93     Current->removeBlockFromLoop(BB);
  94 }
  95
  96 /// Find innermost loop that contains at least one block from \p BBs and
  97 /// contains the header of loop \p L.
  98 static Loop *getInnermostLoopFor(SmallPtrSetImpl<BasicBlock *> &BBs,
  99                                  Loop &L, LoopInfo &LI) {
 100   Loop *Innermost = nullptr;
 101   for (BasicBlock *BB : BBs) {
 102     Loop *BBL = LI.getLoopFor(BB);
 103     while (BBL && !BBL->contains(L.getHeader()))
 104       BBL = BBL->getParentLoop();
 105     if (BBL == &L)
 106       BBL = BBL->getParentLoop();
 107     if (!BBL)
 108       continue;
 109     if (!Innermost || BBL->getLoopDepth() > Innermost->getLoopDepth())
 110       Innermost = BBL;
 111   }
 112   return Innermost;
 113 }
 114
 115 namespace {
 116 /// Helper class that can turn branches and switches with constant conditions
 117 /// into unconditional branches.
 118 class ConstantTerminatorFoldingImpl {
 119 private:
 120   Loop &L;
 121   LoopInfo &LI;
 122   DominatorTree &DT;
 123   ScalarEvolution &SE;
 124   MemorySSAUpdater *MSSAU;
 125   LoopBlocksDFS DFS;
 126   DomTreeUpdater DTU;
 127   SmallVector<DominatorTree::UpdateType, 16> DTUpdates;
 128
 129   // Whether or not the current loop has irreducible CFG.
 130   bool HasIrreducibleCFG = false;
 131   // Whether or not the current loop will still exist after terminator constant
 132   // folding will be done. In theory, there are two ways how it can happen:
 133   // 1. Loop's latch(es) become unreachable from loop header;
 134   // 2. Loop's header becomes unreachable from method entry.
 135   // In practice, the second situation is impossible because we only modify the
 136   // current loop and its preheader and do not affect preheader's reachibility
 137   // from any other block. So this variable set to true means that loop's latch
 138   // has become unreachable from loop header.
 139   bool DeleteCurrentLoop = false;
 140
 141   // The blocks of the original loop that will still be reachable from entry
 142   // after the constant folding.
 143   SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
 144   // The blocks of the original loop that will become unreachable from entry
 145   // after the constant folding.
 146   SmallVector<BasicBlock *, 8> DeadLoopBlocks;
 147   // The exits of the original loop that will still be reachable from entry
 148   // after the constant folding.
 149   SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
 150   // The exits of the original loop that will become unreachable from entry
 151   // after the constant folding.
 152   SmallVector<BasicBlock *, 8> DeadExitBlocks;
 153   // The blocks that will still be a part of the current loop after folding.
 154   SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
 155   // The blocks that have terminators with constant condition that can be
 156   // folded. Note: fold candidates should be in L but not in any of its
 157   // subloops to avoid complex LI updates.
 158   SmallVector<BasicBlock *, 8> FoldCandidates;
 159
 160   void dump() const {
 161     dbgs() << "Constant terminator folding for loop " << L << "\n";
 162     dbgs() << "After terminator constant-folding, the loop will";
 163     if (!DeleteCurrentLoop)
 164       dbgs() << " not";
 165     dbgs() << " be destroyed\n";
 166     auto PrintOutVector = [&](const char *Message,
 167                            const SmallVectorImpl<BasicBlock *> &S) {
 168       dbgs() << Message << "\n";
 169       for (const BasicBlock *BB : S)
 170         dbgs() << "\t" << BB->getName() << "\n";
 171     };
 172     auto PrintOutSet = [&](const char *Message,
 173                            const SmallPtrSetImpl<BasicBlock *> &S) {
 174       dbgs() << Message << "\n";
 175       for (const BasicBlock *BB : S)
 176         dbgs() << "\t" << BB->getName() << "\n";
 177     };
 178     PrintOutVector("Blocks in which we can constant-fold terminator:",
 179                    FoldCandidates);
 180     PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
 181     PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);
 182     PrintOutSet("Live exit blocks:", LiveExitBlocks);
 183     PrintOutVector("Dead exit blocks:", DeadExitBlocks);
 184     if (!DeleteCurrentLoop)
 185       PrintOutSet("The following blocks will still be part of the loop:",
 186                   BlocksInLoopAfterFolding);
 187   }
 188
 189   /// Whether or not the current loop has irreducible CFG.
 190   bool hasIrreducibleCFG(LoopBlocksDFS &DFS) {
 191     assert(DFS.isComplete() && "DFS is expected to be finished");
 192     // Index of a basic block in RPO traversal.
 193     DenseMap<const BasicBlock *, unsigned> RPO;
 194     unsigned Current = 0;
 195     for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I)
 196       RPO[*I] = Current++;
 197
 198     for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
 199       BasicBlock *BB = *I;
 200       for (auto *Succ : successors(BB))
 201         if (L.contains(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])
 202           // If an edge goes from a block with greater order number into a block
 203           // with lesses number, and it is not a loop backedge, then it can only
 204           // be a part of irreducible non-loop cycle.
 205           return true;
 206     }
 207     return false;
 208   }
 209
 210   /// Fill all information about status of blocks and exits of the current loop
 211   /// if constant folding of all branches will be done.
 212   void analyze() {
 213     DFS.perform(&LI);
 214     assert(DFS.isComplete() && "DFS is expected to be finished");
 215
 216     // TODO: The algorithm below relies on both RPO and Postorder traversals.
 217     // When the loop has only reducible CFG inside, then the invariant "all
 218     // predecessors of X are processed before X in RPO" is preserved. However
 219     // an irreducible loop can break this invariant (e.g. latch does not have to
 220     // be the last block in the traversal in this case, and the algorithm relies
 221     // on this). We can later decide to support such cases by altering the
 222     // algorithms, but so far we just give up analyzing them.
 223     if (hasIrreducibleCFG(DFS)) {
 224       HasIrreducibleCFG = true;
 225       return;
 226     }
 227
 228     // Collect live and dead loop blocks and exits.
 229     LiveLoopBlocks.insert(L.getHeader());
 230     for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
 231       BasicBlock *BB = *I;
 232
 233       // If a loop block wasn't marked as live so far, then it's dead.
 234       if (!LiveLoopBlocks.count(BB)) {
 235         DeadLoopBlocks.push_back(BB);
 236         continue;
 237       }
 238
 239       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
 240
 241       // If a block has only one live successor, it's a candidate on constant
 242       // folding. Only handle blocks from current loop: branches in child loops
 243       // are skipped because if they can be folded, they should be folded during
 244       // the processing of child loops.
 245       bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;
 246       if (TakeFoldCandidate)
 247         FoldCandidates.push_back(BB);
 248
 249       // Handle successors.
 250       for (BasicBlock *Succ : successors(BB))
 251         if (!TakeFoldCandidate || TheOnlySucc == Succ) {
 252           if (L.contains(Succ))
 253             LiveLoopBlocks.insert(Succ);
 254           else
 255             LiveExitBlocks.insert(Succ);
 256         }
 257     }
 258
 259     // Sanity check: amount of dead and live loop blocks should match the total
 260     // number of blocks in loop.
 261     assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
 262            "Malformed block sets?");
 263
 264     // Now, all exit blocks that are not marked as live are dead.
 265     SmallVector<BasicBlock *, 8> ExitBlocks;
 266     L.getExitBlocks(ExitBlocks);
 267     SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
 268     for (auto *ExitBlock : ExitBlocks)
 269       if (!LiveExitBlocks.count(ExitBlock) &&
 270           UniqueDeadExits.insert(ExitBlock).second)
 271         DeadExitBlocks.push_back(ExitBlock);
 272
 273     // Whether or not the edge From->To will still be present in graph after the
 274     // folding.
 275     auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
 276       if (!LiveLoopBlocks.count(From))
 277         return false;
 278       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);
 279       return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(From) != &L;
 280     };
 281
 282     // The loop will not be destroyed if its latch is live.
 283     DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
 284
 285     // If we are going to delete the current loop completely, no extra analysis
 286     // is needed.
 287     if (DeleteCurrentLoop)
 288       return;
 289
 290     // Otherwise, we should check which blocks will still be a part of the
 291     // current loop after the transform.
 292     BlocksInLoopAfterFolding.insert(L.getLoopLatch());
 293     // If the loop is live, then we should compute what blocks are still in
 294     // loop after all branch folding has been done. A block is in loop if
 295     // it has a live edge to another block that is in the loop; by definition,
 296     // latch is in the loop.
 297     auto BlockIsInLoop = [&](BasicBlock *BB) {
 298       return any_of(successors(BB), [&](BasicBlock *Succ) {
 299         return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);
 300       });
 301     };
 302     for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
 303       BasicBlock *BB = *I;
 304       if (BlockIsInLoop(BB))
 305         BlocksInLoopAfterFolding.insert(BB);
 306     }
 307
 308     // Sanity check: header must be in loop.
 309     assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
 310            "Header not in loop?");
 311     assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
 312            "All blocks that stay in loop should be live!");
 313   }
 314
 315   /// We need to preserve static reachibility of all loop exit blocks (this is)
 316   /// required by loop pass manager. In order to do it, we make the following
 317   /// trick:
 318   ///
 319   ///  preheader:
 320   ///    <preheader code>
 321   ///    br label %loop_header
 322   ///
 323   ///  loop_header:
 324   ///    ...
 325   ///    br i1 false, label %dead_exit, label %loop_block
 326   ///    ...
 327   ///
 328   /// We cannot simply remove edge from the loop to dead exit because in this
 329   /// case dead_exit (and its successors) may become unreachable. To avoid that,
 330   /// we insert the following fictive preheader:
 331   ///
 332   ///  preheader:
 333   ///    <preheader code>
 334   ///    switch i32 0, label %preheader-split,
 335   ///                  [i32 1, label %dead_exit_1],
 336   ///                  [i32 2, label %dead_exit_2],
 337   ///                  ...
 338   ///                  [i32 N, label %dead_exit_N],
 339   ///
 340   ///  preheader-split:
 341   ///    br label %loop_header
 342   ///
 343   ///  loop_header:
 344   ///    ...
 345   ///    br i1 false, label %dead_exit_N, label %loop_block
 346   ///    ...
 347   ///
 348   /// Doing so, we preserve static reachibility of all dead exits and can later
 349   /// remove edges from the loop to these blocks.
 350   void handleDeadExits() {
 351     // If no dead exits, nothing to do.
 352     if (DeadExitBlocks.empty())
 353       return;
 354
 355     // Construct split preheader and the dummy switch to thread edges from it to
 356     // dead exits.
 357     BasicBlock *Preheader = L.getLoopPreheader();
 358     BasicBlock *NewPreheader = llvm::SplitBlock(
 359         Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);
 360
 361     IRBuilder<> Builder(Preheader->getTerminator());
 362     SwitchInst *DummySwitch =
 363         Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
 364     Preheader->getTerminator()->eraseFromParent();
 365
 366     unsigned DummyIdx = 1;
 367     for (BasicBlock *BB : DeadExitBlocks) {
 368       // Eliminate all Phis and LandingPads from dead exits.
 369       // TODO: Consider removing all instructions in this dead block.
 370       SmallVector<Instruction *, 4> DeadInstructions;
 371       for (auto &PN : BB->phis())
 372         DeadInstructions.push_back(&PN);
 373
 374       if (auto *LandingPad = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()))
 375         DeadInstructions.emplace_back(LandingPad);
 376
 377       for (Instruction *I : DeadInstructions) {
 378         I->replaceAllUsesWith(UndefValue::get(I->getType()));
 379         I->eraseFromParent();
 380       }
 381
 382       assert(DummyIdx != 0 && "Too many dead exits!");
 383       DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
 384       DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
 385       ++NumLoopExitsDeleted;
 386     }
 387
 388     assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
 389     if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
 390       // When we break dead edges, the outer loop may become unreachable from
 391       // the current loop. We need to fix loop info accordingly. For this, we
 392       // find the most nested loop that still contains L and remove L from all
 393       // loops that are inside of it.
 394       Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI);
 395
 396       // Okay, our loop is no longer in the outer loop (and maybe not in some of
 397       // its parents as well). Make the fixup.
 398       if (StillReachable != OuterLoop) {
 399         LI.changeLoopFor(NewPreheader, StillReachable);
 400         removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);
 401         for (auto *BB : L.blocks())
 402           removeBlockFromLoops(BB, OuterLoop, StillReachable);
 403         OuterLoop->removeChildLoop(&L);
 404         if (StillReachable)
 405           StillReachable->addChildLoop(&L);
 406         else
 407           LI.addTopLevelLoop(&L);
 408
 409         // Some values from loops in [OuterLoop, StillReachable) could be used
 410         // in the current loop. Now it is not their child anymore, so such uses
 411         // require LCSSA Phis.
 412         Loop *FixLCSSALoop = OuterLoop;
 413         while (FixLCSSALoop->getParentLoop() != StillReachable)
 414           FixLCSSALoop = FixLCSSALoop->getParentLoop();
 415         assert(FixLCSSALoop && "Should be a loop!");
 416         // We need all DT updates to be done before forming LCSSA.
 417         if (MSSAU)
 418           MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
 419         else
 420           DTU.applyUpdates(DTUpdates);
 421         DTUpdates.clear();
 422         formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
 423       }
 424     }
 425
 426     if (MSSAU) {
 427       // Clear all updates now. Facilitates deletes that follow.
 428       MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
 429       DTUpdates.clear();
 430       if (VerifyMemorySSA)
 431         MSSAU->getMemorySSA()->verifyMemorySSA();
 432     }
 433   }
 434
 435   /// Delete loop blocks that have become unreachable after folding. Make all
 436   /// relevant updates to DT and LI.
 437   void deleteDeadLoopBlocks() {
 438     if (MSSAU) {
 439       SmallSetVector<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
 440                                                         DeadLoopBlocks.end());
 441       MSSAU->removeBlocks(DeadLoopBlocksSet);
 442     }
 443
 444     // The function LI.erase has some invariants that need to be preserved when
 445     // it tries to remove a loop which is not the top-level loop. In particular,
 446     // it requires loop's preheader to be strictly in loop's parent. We cannot
 447     // just remove blocks one by one, because after removal of preheader we may
 448     // break this invariant for the dead loop. So we detatch and erase all dead
 449     // loops beforehand.
 450     for (auto *BB : DeadLoopBlocks)
 451       if (LI.isLoopHeader(BB)) {
 452         assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
 453         Loop *DL = LI.getLoopFor(BB);
 454         if (!DL->isOutermost()) {
 455           for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
 456             for (auto *BB : DL->getBlocks())
 457               PL->removeBlockFromLoop(BB);
 458           DL->getParentLoop()->removeChildLoop(DL);
 459           LI.addTopLevelLoop(DL);
 460         }
 461         LI.erase(DL);
 462       }
 463
 464     for (auto *BB : DeadLoopBlocks) {
 465       assert(BB != L.getHeader() &&
 466              "Header of the current loop cannot be dead!");
 467       LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
 468                         << "\n");
 469       LI.removeBlock(BB);
 470     }
 471
 472     DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
 473     DTU.applyUpdates(DTUpdates);
 474     DTUpdates.clear();
 475     for (auto *BB : DeadLoopBlocks)
 476       DTU.deleteBB(BB);
 477
 478     NumLoopBlocksDeleted += DeadLoopBlocks.size();
 479   }
 480
 481   /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
 482   /// unconditional branches.
 483   void foldTerminators() {
 484     for (BasicBlock *BB : FoldCandidates) {
 485       assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
 486       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
 487       assert(TheOnlySucc && "Should have one live successor!");
 488
 489       LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
 490                         << " with an unconditional branch to the block "
 491                         << TheOnlySucc->getName() << "\n");
 492
 493       SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
 494       // Remove all BB's successors except for the live one.
 495       unsigned TheOnlySuccDuplicates = 0;
 496       for (auto *Succ : successors(BB))
 497         if (Succ != TheOnlySucc) {
 498           DeadSuccessors.insert(Succ);
 499           // If our successor lies in a different loop, we don't want to remove
 500           // the one-input Phi because it is a LCSSA Phi.
 501           bool PreserveLCSSAPhi = !L.contains(Succ);
 502           Succ->removePredecessor(BB, PreserveLCSSAPhi);
 503           if (MSSAU)
 504             MSSAU->removeEdge(BB, Succ);
 505         } else
 506           ++TheOnlySuccDuplicates;
 507
 508       assert(TheOnlySuccDuplicates > 0 && "Should be!");
 509       // If TheOnlySucc was BB's successor more than once, after transform it
 510       // will be its successor only once. Remove redundant inputs from
 511       // TheOnlySucc's Phis.
 512       bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
 513       for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
 514         TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);
 515       if (MSSAU && TheOnlySuccDuplicates > 1)
 516         MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);
 517
 518       IRBuilder<> Builder(BB->getContext());
 519       Instruction *Term = BB->getTerminator();
 520       Builder.SetInsertPoint(Term);
 521       Builder.CreateBr(TheOnlySucc);
 522       Term->eraseFromParent();
 523
 524       for (auto *DeadSucc : DeadSuccessors)
 525         DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});
 526
 527       ++NumTerminatorsFolded;
 528     }
 529   }
 530
 531 public:
 532   ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
 533                                 ScalarEvolution &SE,
 534                                 MemorySSAUpdater *MSSAU)
 535       : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),
 536         DTU(DT, DomTreeUpdater::UpdateStrategy::Eager) {}
 537   bool run() {
 538     assert(L.getLoopLatch() && "Should be single latch!");
 539
 540     // Collect all available information about status of blocks after constant
 541     // folding.
 542     analyze();
 543     BasicBlock *Header = L.getHeader();
 544     (void)Header;
 545
 546     LLVM_DEBUG(dbgs() << "In function " << Header->getParent()->getName()
 547                       << ": ");
 548
 549     if (HasIrreducibleCFG) {
 550       LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");
 551       return false;
 552     }
 553
 554     // Nothing to constant-fold.
 555     if (FoldCandidates.empty()) {
 556       LLVM_DEBUG(
 557           dbgs() << "No constant terminator folding candidates found in loop "
 558                  << Header->getName() << "\n");
 559       return false;
 560     }
 561
 562     // TODO: Support deletion of the current loop.
 563     if (DeleteCurrentLoop) {
 564       LLVM_DEBUG(
 565           dbgs()
 566           << "Give up constant terminator folding in loop " << Header->getName()
 567           << ": we don't currently support deletion of the current loop.\n");
 568       return false;
 569     }
 570
 571     // TODO: Support blocks that are not dead, but also not in loop after the
 572     // folding.
 573     if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
 574         L.getNumBlocks()) {
 575       LLVM_DEBUG(
 576           dbgs() << "Give up constant terminator folding in loop "
 577                  << Header->getName() << ": we don't currently"
 578                     " support blocks that are not dead, but will stop "
 579                     "being a part of the loop after constant-folding.\n");
 580       return false;
 581     }
 582
 583     SE.forgetTopmostLoop(&L);
 584     // Dump analysis results.
 585     LLVM_DEBUG(dump());
 586
 587     LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
 588                       << " terminators in loop " << Header->getName() << "\n");
 589
 590     // Make the actual transforms.
 591     handleDeadExits();
 592     foldTerminators();
 593
 594     if (!DeadLoopBlocks.empty()) {
 595       LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
 596                     << " dead blocks in loop " << Header->getName() << "\n");
 597       deleteDeadLoopBlocks();
 598     } else {
 599       // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
 600       DTU.applyUpdates(DTUpdates);
 601       DTUpdates.clear();
 602     }
 603
 604     if (MSSAU && VerifyMemorySSA)
 605       MSSAU->getMemorySSA()->verifyMemorySSA();
 606
 607 #ifndef NDEBUG
 608     // Make sure that we have preserved all data structures after the transform.
 609 #if defined(EXPENSIVE_CHECKS)
 610     assert(DT.verify(DominatorTree::VerificationLevel::Full) &&
 611            "DT broken after transform!");
 612 #else
 613     assert(DT.verify(DominatorTree::VerificationLevel::Fast) &&
 614            "DT broken after transform!");
 615 #endif
 616     assert(DT.isReachableFromEntry(Header));
 617     LI.verify(DT);
 618 #endif
 619
 620     return true;
 621   }
 622
 623   bool foldingBreaksCurrentLoop() const {
 624     return DeleteCurrentLoop;
 625   }
 626 };
 627 } // namespace
 628
 629 /// Turn branches and switches with known constant conditions into unconditional
 630 /// branches.
 631 static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI,
 632                                     ScalarEvolution &SE,
 633                                     MemorySSAUpdater *MSSAU,
 634                                     bool &IsLoopDeleted) {
 635   if (!EnableTermFolding)
 636     return false;
 637
 638   // To keep things simple, only process loops with single latch. We
 639   // canonicalize most loops to this form. We can support multi-latch if needed.
 640   if (!L.getLoopLatch())
 641     return false;
 642
 643   ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
 644   bool Changed = BranchFolder.run();
 645   IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
 646   return Changed;
 647 }
 648
 649 static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT,
 650                                         LoopInfo &LI, MemorySSAUpdater *MSSAU) {
 651   bool Changed = false;
 652   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 653   // Copy blocks into a temporary array to avoid iterator invalidation issues
 654   // as we remove them.
 655   SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
 656
 657   for (auto &Block : Blocks) {
 658     // Attempt to merge blocks in the trivial case. Don't modify blocks which
 659     // belong to other loops.
 660     BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
 661     if (!Succ)
 662       continue;
 663
 664     BasicBlock *Pred = Succ->getSinglePredecessor();
 665     if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
 666       continue;
 667
 668     // Merge Succ into Pred and delete it.
 669     MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
 670
 671     if (MSSAU && VerifyMemorySSA)
 672       MSSAU->getMemorySSA()->verifyMemorySSA();
 673
 674     Changed = true;
 675   }
 676
 677   return Changed;
 678 }
 679
 680 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
 681                             ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
 682                             bool &IsLoopDeleted) {
 683   bool Changed = false;
 684
 685   // Constant-fold terminators with known constant conditions.
 686   Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, IsLoopDeleted);
 687
 688   if (IsLoopDeleted)
 689     return true;
 690
 691   // Eliminate unconditional branches by merging blocks into their predecessors.
 692   Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
 693
 694   if (Changed)
 695     SE.forgetTopmostLoop(&L);
 696
 697   return Changed;
 698 }
 699
 700 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
 701                                            LoopStandardAnalysisResults &AR,
 702                                            LPMUpdater &LPMU) {
 703   Optional<MemorySSAUpdater> MSSAU;
 704   if (AR.MSSA)
 705     MSSAU = MemorySSAUpdater(AR.MSSA);
 706   bool DeleteCurrentLoop = false;
 707   if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
 708                        MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
 709                        DeleteCurrentLoop))
 710     return PreservedAnalyses::all();
 711
 712   if (DeleteCurrentLoop)
 713     LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
 714
 715   auto PA = getLoopPassPreservedAnalyses();
 716   if (AR.MSSA)
 717     PA.preserve<MemorySSAAnalysis>();
 718   return PA;
 719 }
 720
 721 namespace {
 722 class LoopSimplifyCFGLegacyPass : public LoopPass {
 723 public:
 724   static char ID; // Pass ID, replacement for typeid
 725   LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
 726     initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
 727   }
 728
 729   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
 730     if (skipLoop(L))
 731       return false;
 732
 733     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 734     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 735     ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 736     auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
 737     Optional<MemorySSAUpdater> MSSAU;
 738     if (MSSAA)
 739       MSSAU = MemorySSAUpdater(&MSSAA->getMSSA());
 740     if (MSSAA && VerifyMemorySSA)
 741       MSSAU->getMemorySSA()->verifyMemorySSA();
 742     bool DeleteCurrentLoop = false;
 743     bool Changed = simplifyLoopCFG(
 744         *L, DT, LI, SE, MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
 745         DeleteCurrentLoop);
 746     if (DeleteCurrentLoop)
 747       LPM.markLoopAsDeleted(*L);
 748     return Changed;
 749   }
 750
 751   void getAnalysisUsage(AnalysisUsage &AU) const override {
 752     AU.addPreserved<MemorySSAWrapperPass>();
 753     AU.addPreserved<DependenceAnalysisWrapperPass>();
 754     getLoopAnalysisUsage(AU);
 755   }
 756 };
 757 } // end namespace
 758
 759 char LoopSimplifyCFGLegacyPass::ID = 0;
 760 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
 761                       "Simplify loop CFG", false, false)
 762 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 763 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 764 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
 765                     "Simplify loop CFG", false, false)
 766
 767 Pass *llvm::createLoopSimplifyCFGPass() {
 768   return new LoopSimplifyCFGLegacyPass();
 769 }