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 = llvm::SplitBlock(
 356         Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);
 357
 358     IRBuilder<> Builder(Preheader->getTerminator());
 359     SwitchInst *DummySwitch =
 360         Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
 361     Preheader->getTerminator()->eraseFromParent();
 362
 363     unsigned DummyIdx = 1;
 364     for (BasicBlock *BB : DeadExitBlocks) {
 365       SmallVector<Instruction *, 4> DeadPhis;
 366       for (auto &PN : BB->phis())
 367         DeadPhis.push_back(&PN);
 368
 369       // Eliminate all Phis from dead exits.
 370       for (Instruction *PN : DeadPhis) {
 371         PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 372         PN->eraseFromParent();
 373       }
 374       assert(DummyIdx != 0 && "Too many dead exits!");
 375       DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
 376       DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
 377       ++NumLoopExitsDeleted;
 378     }
 379
 380     assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
 381     if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
 382       // When we break dead edges, the outer loop may become unreachable from
 383       // the current loop. We need to fix loop info accordingly. For this, we
 384       // find the most nested loop that still contains L and remove L from all
 385       // loops that are inside of it.
 386       Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI);
 387
 388       // Okay, our loop is no longer in the outer loop (and maybe not in some of
 389       // its parents as well). Make the fixup.
 390       if (StillReachable != OuterLoop) {
 391         LI.changeLoopFor(NewPreheader, StillReachable);
 392         removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);
 393         for (auto *BB : L.blocks())
 394           removeBlockFromLoops(BB, OuterLoop, StillReachable);
 395         OuterLoop->removeChildLoop(&L);
 396         if (StillReachable)
 397           StillReachable->addChildLoop(&L);
 398         else
 399           LI.addTopLevelLoop(&L);
 400
 401         // Some values from loops in [OuterLoop, StillReachable) could be used
 402         // in the current loop. Now it is not their child anymore, so such uses
 403         // require LCSSA Phis.
 404         Loop *FixLCSSALoop = OuterLoop;
 405         while (FixLCSSALoop->getParentLoop() != StillReachable)
 406           FixLCSSALoop = FixLCSSALoop->getParentLoop();
 407         assert(FixLCSSALoop && "Should be a loop!");
 408         // We need all DT updates to be done before forming LCSSA.
 409         DTU.applyUpdates(DTUpdates);
 410         if (MSSAU)
 411           MSSAU->applyUpdates(DTUpdates, DT);
 412         DTUpdates.clear();
 413         formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
 414       }
 415     }
 416
 417     if (MSSAU) {
 418       // Clear all updates now. Facilitates deletes that follow.
 419       DTU.applyUpdates(DTUpdates);
 420       MSSAU->applyUpdates(DTUpdates, DT);
 421       DTUpdates.clear();
 422       if (VerifyMemorySSA)
 423         MSSAU->getMemorySSA()->verifyMemorySSA();
 424     }
 425   }
 426
 427   /// Delete loop blocks that have become unreachable after folding. Make all
 428   /// relevant updates to DT and LI.
 429   void deleteDeadLoopBlocks() {
 430     if (MSSAU) {
 431       SmallSetVector<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
 432                                                         DeadLoopBlocks.end());
 433       MSSAU->removeBlocks(DeadLoopBlocksSet);
 434     }
 435
 436     // The function LI.erase has some invariants that need to be preserved when
 437     // it tries to remove a loop which is not the top-level loop. In particular,
 438     // it requires loop's preheader to be strictly in loop's parent. We cannot
 439     // just remove blocks one by one, because after removal of preheader we may
 440     // break this invariant for the dead loop. So we detatch and erase all dead
 441     // loops beforehand.
 442     for (auto *BB : DeadLoopBlocks)
 443       if (LI.isLoopHeader(BB)) {
 444         assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
 445         Loop *DL = LI.getLoopFor(BB);
 446         if (DL->getParentLoop()) {
 447           for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
 448             for (auto *BB : DL->getBlocks())
 449               PL->removeBlockFromLoop(BB);
 450           DL->getParentLoop()->removeChildLoop(DL);
 451           LI.addTopLevelLoop(DL);
 452         }
 453         LI.erase(DL);
 454       }
 455
 456     for (auto *BB : DeadLoopBlocks) {
 457       assert(BB != L.getHeader() &&
 458              "Header of the current loop cannot be dead!");
 459       LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
 460                         << "\n");
 461       LI.removeBlock(BB);
 462     }
 463
 464     DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
 465     DTU.applyUpdates(DTUpdates);
 466     DTUpdates.clear();
 467     for (auto *BB : DeadLoopBlocks)
 468       DTU.deleteBB(BB);
 469
 470     NumLoopBlocksDeleted += DeadLoopBlocks.size();
 471   }
 472
 473   /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
 474   /// unconditional branches.
 475   void foldTerminators() {
 476     for (BasicBlock *BB : FoldCandidates) {
 477       assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
 478       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
 479       assert(TheOnlySucc && "Should have one live successor!");
 480
 481       LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
 482                         << " with an unconditional branch to the block "
 483                         << TheOnlySucc->getName() << "\n");
 484
 485       SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
 486       // Remove all BB's successors except for the live one.
 487       unsigned TheOnlySuccDuplicates = 0;
 488       for (auto *Succ : successors(BB))
 489         if (Succ != TheOnlySucc) {
 490           DeadSuccessors.insert(Succ);
 491           // If our successor lies in a different loop, we don't want to remove
 492           // the one-input Phi because it is a LCSSA Phi.
 493           bool PreserveLCSSAPhi = !L.contains(Succ);
 494           Succ->removePredecessor(BB, PreserveLCSSAPhi);
 495           if (MSSAU)
 496             MSSAU->removeEdge(BB, Succ);
 497         } else
 498           ++TheOnlySuccDuplicates;
 499
 500       assert(TheOnlySuccDuplicates > 0 && "Should be!");
 501       // If TheOnlySucc was BB's successor more than once, after transform it
 502       // will be its successor only once. Remove redundant inputs from
 503       // TheOnlySucc's Phis.
 504       bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
 505       for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
 506         TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);
 507       if (MSSAU && TheOnlySuccDuplicates > 1)
 508         MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);
 509
 510       IRBuilder<> Builder(BB->getContext());
 511       Instruction *Term = BB->getTerminator();
 512       Builder.SetInsertPoint(Term);
 513       Builder.CreateBr(TheOnlySucc);
 514       Term->eraseFromParent();
 515
 516       for (auto *DeadSucc : DeadSuccessors)
 517         DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});
 518
 519       ++NumTerminatorsFolded;
 520     }
 521   }
 522
 523 public:
 524   ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
 525                                 ScalarEvolution &SE,
 526                                 MemorySSAUpdater *MSSAU)
 527       : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),
 528         DTU(DT, DomTreeUpdater::UpdateStrategy::Eager) {}
 529   bool run() {
 530     assert(L.getLoopLatch() && "Should be single latch!");
 531
 532     // Collect all available information about status of blocks after constant
 533     // folding.
 534     analyze();
 535     BasicBlock *Header = L.getHeader();
 536     (void)Header;
 537
 538     LLVM_DEBUG(dbgs() << "In function " << Header->getParent()->getName()
 539                       << ": ");
 540
 541     if (HasIrreducibleCFG) {
 542       LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");
 543       return false;
 544     }
 545
 546     // Nothing to constant-fold.
 547     if (FoldCandidates.empty()) {
 548       LLVM_DEBUG(
 549           dbgs() << "No constant terminator folding candidates found in loop "
 550                  << Header->getName() << "\n");
 551       return false;
 552     }
 553
 554     // TODO: Support deletion of the current loop.
 555     if (DeleteCurrentLoop) {
 556       LLVM_DEBUG(
 557           dbgs()
 558           << "Give up constant terminator folding in loop " << Header->getName()
 559           << ": we don't currently support deletion of the current loop.\n");
 560       return false;
 561     }
 562
 563     // TODO: Support blocks that are not dead, but also not in loop after the
 564     // folding.
 565     if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
 566         L.getNumBlocks()) {
 567       LLVM_DEBUG(
 568           dbgs() << "Give up constant terminator folding in loop "
 569                  << Header->getName() << ": we don't currently"
 570                     " support blocks that are not dead, but will stop "
 571                     "being a part of the loop after constant-folding.\n");
 572       return false;
 573     }
 574
 575     SE.forgetTopmostLoop(&L);
 576     // Dump analysis results.
 577     LLVM_DEBUG(dump());
 578
 579     LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
 580                       << " terminators in loop " << Header->getName() << "\n");
 581
 582     // Make the actual transforms.
 583     handleDeadExits();
 584     foldTerminators();
 585
 586     if (!DeadLoopBlocks.empty()) {
 587       LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
 588                     << " dead blocks in loop " << Header->getName() << "\n");
 589       deleteDeadLoopBlocks();
 590     } else {
 591       // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
 592       DTU.applyUpdates(DTUpdates);
 593       DTUpdates.clear();
 594     }
 595
 596     if (MSSAU && VerifyMemorySSA)
 597       MSSAU->getMemorySSA()->verifyMemorySSA();
 598
 599 #ifndef NDEBUG
 600     // Make sure that we have preserved all data structures after the transform.
 601 #if defined(EXPENSIVE_CHECKS)
 602     assert(DT.verify(DominatorTree::VerificationLevel::Full) &&
 603            "DT broken after transform!");
 604 #else
 605     assert(DT.verify(DominatorTree::VerificationLevel::Fast) &&
 606            "DT broken after transform!");
 607 #endif
 608     assert(DT.isReachableFromEntry(Header));
 609     LI.verify(DT);
 610 #endif
 611
 612     return true;
 613   }
 614
 615   bool foldingBreaksCurrentLoop() const {
 616     return DeleteCurrentLoop;
 617   }
 618 };
 619 } // namespace
 620
 621 /// Turn branches and switches with known constant conditions into unconditional
 622 /// branches.
 623 static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI,
 624                                     ScalarEvolution &SE,
 625                                     MemorySSAUpdater *MSSAU,
 626                                     bool &IsLoopDeleted) {
 627   if (!EnableTermFolding)
 628     return false;
 629
 630   // To keep things simple, only process loops with single latch. We
 631   // canonicalize most loops to this form. We can support multi-latch if needed.
 632   if (!L.getLoopLatch())
 633     return false;
 634
 635   ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
 636   bool Changed = BranchFolder.run();
 637   IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
 638   return Changed;
 639 }
 640
 641 static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT,
 642                                         LoopInfo &LI, MemorySSAUpdater *MSSAU) {
 643   bool Changed = false;
 644   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 645   // Copy blocks into a temporary array to avoid iterator invalidation issues
 646   // as we remove them.
 647   SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
 648
 649   for (auto &Block : Blocks) {
 650     // Attempt to merge blocks in the trivial case. Don't modify blocks which
 651     // belong to other loops.
 652     BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
 653     if (!Succ)
 654       continue;
 655
 656     BasicBlock *Pred = Succ->getSinglePredecessor();
 657     if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
 658       continue;
 659
 660     // Merge Succ into Pred and delete it.
 661     MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
 662
 663     Changed = true;
 664   }
 665
 666   return Changed;
 667 }
 668
 669 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
 670                             ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
 671                             bool &isLoopDeleted) {
 672   bool Changed = false;
 673
 674   // Constant-fold terminators with known constant conditions.
 675   Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, isLoopDeleted);
 676
 677   if (isLoopDeleted)
 678     return true;
 679
 680   // Eliminate unconditional branches by merging blocks into their predecessors.
 681   Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
 682
 683   if (Changed)
 684     SE.forgetTopmostLoop(&L);
 685
 686   return Changed;
 687 }
 688
 689 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
 690                                            LoopStandardAnalysisResults &AR,
 691                                            LPMUpdater &LPMU) {
 692   Optional<MemorySSAUpdater> MSSAU;
 693   if (AR.MSSA)
 694     MSSAU = MemorySSAUpdater(AR.MSSA);
 695   bool DeleteCurrentLoop = false;
 696   if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
 697                        MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
 698                        DeleteCurrentLoop))
 699     return PreservedAnalyses::all();
 700
 701   if (DeleteCurrentLoop)
 702     LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
 703
 704   auto PA = getLoopPassPreservedAnalyses();
 705   if (AR.MSSA)
 706     PA.preserve<MemorySSAAnalysis>();
 707   return PA;
 708 }
 709
 710 namespace {
 711 class LoopSimplifyCFGLegacyPass : public LoopPass {
 712 public:
 713   static char ID; // Pass ID, replacement for typeid
 714   LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
 715     initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
 716   }
 717
 718   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
 719     if (skipLoop(L))
 720       return false;
 721
 722     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 723     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 724     ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 725     Optional<MemorySSAUpdater> MSSAU;
 726     if (EnableMSSALoopDependency) {
 727       MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
 728       MSSAU = MemorySSAUpdater(MSSA);
 729       if (VerifyMemorySSA)
 730         MSSA->verifyMemorySSA();
 731     }
 732     bool DeleteCurrentLoop = false;
 733     bool Changed = simplifyLoopCFG(
 734         *L, DT, LI, SE, MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
 735         DeleteCurrentLoop);
 736     if (DeleteCurrentLoop)
 737       LPM.markLoopAsDeleted(*L);
 738     return Changed;
 739   }
 740
 741   void getAnalysisUsage(AnalysisUsage &AU) const override {
 742     if (EnableMSSALoopDependency) {
 743       AU.addRequired<MemorySSAWrapperPass>();
 744       AU.addPreserved<MemorySSAWrapperPass>();
 745     }
 746     AU.addPreserved<DependenceAnalysisWrapperPass>();
 747     getLoopAnalysisUsage(AU);
 748   }
 749 };
 750 }
 751
 752 char LoopSimplifyCFGLegacyPass::ID = 0;
 753 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
 754                       "Simplify loop CFG", false, false)
 755 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 756 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 757 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
 758                     "Simplify loop CFG", false, false)
 759
 760 Pass *llvm::createLoopSimplifyCFGPass() {
 761   return new LoopSimplifyCFGLegacyPass();
 762 }