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