xref: /openbsd-src/gnu/llvm/llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
109467b48Spatrick //===--------- LoopSimplifyCFG.cpp - Loop CFG Simplification Pass ---------===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick //
909467b48Spatrick // This file implements the Loop SimplifyCFG Pass. This pass is responsible for
1009467b48Spatrick // basic loop CFG cleanup, primarily to assist other loop passes. If you
1109467b48Spatrick // encounter a noncanonical CFG construct that causes another loop pass to
1209467b48Spatrick // perform suboptimally, this is the place to fix it up.
1309467b48Spatrick //
1409467b48Spatrick //===----------------------------------------------------------------------===//
1509467b48Spatrick 
1609467b48Spatrick #include "llvm/Transforms/Scalar/LoopSimplifyCFG.h"
1709467b48Spatrick #include "llvm/ADT/SmallVector.h"
1809467b48Spatrick #include "llvm/ADT/Statistic.h"
1909467b48Spatrick #include "llvm/Analysis/DependenceAnalysis.h"
2009467b48Spatrick #include "llvm/Analysis/DomTreeUpdater.h"
2109467b48Spatrick #include "llvm/Analysis/LoopInfo.h"
22097a140dSpatrick #include "llvm/Analysis/LoopIterator.h"
2309467b48Spatrick #include "llvm/Analysis/LoopPass.h"
2409467b48Spatrick #include "llvm/Analysis/MemorySSA.h"
2509467b48Spatrick #include "llvm/Analysis/MemorySSAUpdater.h"
2609467b48Spatrick #include "llvm/Analysis/ScalarEvolution.h"
2709467b48Spatrick #include "llvm/IR/Dominators.h"
28097a140dSpatrick #include "llvm/IR/IRBuilder.h"
2909467b48Spatrick #include "llvm/InitializePasses.h"
3009467b48Spatrick #include "llvm/Support/CommandLine.h"
3109467b48Spatrick #include "llvm/Transforms/Scalar.h"
3209467b48Spatrick #include "llvm/Transforms/Scalar/LoopPassManager.h"
3309467b48Spatrick #include "llvm/Transforms/Utils/BasicBlockUtils.h"
3409467b48Spatrick #include "llvm/Transforms/Utils/LoopUtils.h"
35*d415bd75Srobert #include <optional>
3609467b48Spatrick using namespace llvm;
3709467b48Spatrick 
3809467b48Spatrick #define DEBUG_TYPE "loop-simplifycfg"
3909467b48Spatrick 
4009467b48Spatrick static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
4109467b48Spatrick                                        cl::init(true));
4209467b48Spatrick 
4309467b48Spatrick STATISTIC(NumTerminatorsFolded,
4409467b48Spatrick           "Number of terminators folded to unconditional branches");
4509467b48Spatrick STATISTIC(NumLoopBlocksDeleted,
4609467b48Spatrick           "Number of loop blocks deleted");
4709467b48Spatrick STATISTIC(NumLoopExitsDeleted,
4809467b48Spatrick           "Number of loop exiting edges deleted");
4909467b48Spatrick 
5009467b48Spatrick /// If \p BB is a switch or a conditional branch, but only one of its successors
5109467b48Spatrick /// can be reached from this block in runtime, return this successor. Otherwise,
5209467b48Spatrick /// return nullptr.
getOnlyLiveSuccessor(BasicBlock * BB)5309467b48Spatrick static BasicBlock *getOnlyLiveSuccessor(BasicBlock *BB) {
5409467b48Spatrick   Instruction *TI = BB->getTerminator();
5509467b48Spatrick   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
5609467b48Spatrick     if (BI->isUnconditional())
5709467b48Spatrick       return nullptr;
5809467b48Spatrick     if (BI->getSuccessor(0) == BI->getSuccessor(1))
5909467b48Spatrick       return BI->getSuccessor(0);
6009467b48Spatrick     ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
6109467b48Spatrick     if (!Cond)
6209467b48Spatrick       return nullptr;
6309467b48Spatrick     return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);
6409467b48Spatrick   }
6509467b48Spatrick 
6609467b48Spatrick   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
6709467b48Spatrick     auto *CI = dyn_cast<ConstantInt>(SI->getCondition());
6809467b48Spatrick     if (!CI)
6909467b48Spatrick       return nullptr;
7009467b48Spatrick     for (auto Case : SI->cases())
7109467b48Spatrick       if (Case.getCaseValue() == CI)
7209467b48Spatrick         return Case.getCaseSuccessor();
7309467b48Spatrick     return SI->getDefaultDest();
7409467b48Spatrick   }
7509467b48Spatrick 
7609467b48Spatrick   return nullptr;
7709467b48Spatrick }
7809467b48Spatrick 
7909467b48Spatrick /// Removes \p BB from all loops from [FirstLoop, LastLoop) in parent chain.
removeBlockFromLoops(BasicBlock * BB,Loop * FirstLoop,Loop * LastLoop=nullptr)8009467b48Spatrick static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop,
8109467b48Spatrick                                  Loop *LastLoop = nullptr) {
8209467b48Spatrick   assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&
8309467b48Spatrick          "First loop is supposed to be inside of last loop!");
8409467b48Spatrick   assert(FirstLoop->contains(BB) && "Must be a loop block!");
8509467b48Spatrick   for (Loop *Current = FirstLoop; Current != LastLoop;
8609467b48Spatrick        Current = Current->getParentLoop())
8709467b48Spatrick     Current->removeBlockFromLoop(BB);
8809467b48Spatrick }
8909467b48Spatrick 
9009467b48Spatrick /// Find innermost loop that contains at least one block from \p BBs and
9109467b48Spatrick /// contains the header of loop \p L.
getInnermostLoopFor(SmallPtrSetImpl<BasicBlock * > & BBs,Loop & L,LoopInfo & LI)9209467b48Spatrick static Loop *getInnermostLoopFor(SmallPtrSetImpl<BasicBlock *> &BBs,
9309467b48Spatrick                                  Loop &L, LoopInfo &LI) {
9409467b48Spatrick   Loop *Innermost = nullptr;
9509467b48Spatrick   for (BasicBlock *BB : BBs) {
9609467b48Spatrick     Loop *BBL = LI.getLoopFor(BB);
9709467b48Spatrick     while (BBL && !BBL->contains(L.getHeader()))
9809467b48Spatrick       BBL = BBL->getParentLoop();
9909467b48Spatrick     if (BBL == &L)
10009467b48Spatrick       BBL = BBL->getParentLoop();
10109467b48Spatrick     if (!BBL)
10209467b48Spatrick       continue;
10309467b48Spatrick     if (!Innermost || BBL->getLoopDepth() > Innermost->getLoopDepth())
10409467b48Spatrick       Innermost = BBL;
10509467b48Spatrick   }
10609467b48Spatrick   return Innermost;
10709467b48Spatrick }
10809467b48Spatrick 
10909467b48Spatrick namespace {
11009467b48Spatrick /// Helper class that can turn branches and switches with constant conditions
11109467b48Spatrick /// into unconditional branches.
11209467b48Spatrick class ConstantTerminatorFoldingImpl {
11309467b48Spatrick private:
11409467b48Spatrick   Loop &L;
11509467b48Spatrick   LoopInfo &LI;
11609467b48Spatrick   DominatorTree &DT;
11709467b48Spatrick   ScalarEvolution &SE;
11809467b48Spatrick   MemorySSAUpdater *MSSAU;
11909467b48Spatrick   LoopBlocksDFS DFS;
12009467b48Spatrick   DomTreeUpdater DTU;
12109467b48Spatrick   SmallVector<DominatorTree::UpdateType, 16> DTUpdates;
12209467b48Spatrick 
12309467b48Spatrick   // Whether or not the current loop has irreducible CFG.
12409467b48Spatrick   bool HasIrreducibleCFG = false;
12509467b48Spatrick   // Whether or not the current loop will still exist after terminator constant
12609467b48Spatrick   // folding will be done. In theory, there are two ways how it can happen:
12709467b48Spatrick   // 1. Loop's latch(es) become unreachable from loop header;
12809467b48Spatrick   // 2. Loop's header becomes unreachable from method entry.
12909467b48Spatrick   // In practice, the second situation is impossible because we only modify the
13009467b48Spatrick   // current loop and its preheader and do not affect preheader's reachibility
13109467b48Spatrick   // from any other block. So this variable set to true means that loop's latch
13209467b48Spatrick   // has become unreachable from loop header.
13309467b48Spatrick   bool DeleteCurrentLoop = false;
13409467b48Spatrick 
13509467b48Spatrick   // The blocks of the original loop that will still be reachable from entry
13609467b48Spatrick   // after the constant folding.
13709467b48Spatrick   SmallPtrSet<BasicBlock *, 8> LiveLoopBlocks;
13809467b48Spatrick   // The blocks of the original loop that will become unreachable from entry
13909467b48Spatrick   // after the constant folding.
14009467b48Spatrick   SmallVector<BasicBlock *, 8> DeadLoopBlocks;
14109467b48Spatrick   // The exits of the original loop that will still be reachable from entry
14209467b48Spatrick   // after the constant folding.
14309467b48Spatrick   SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
14409467b48Spatrick   // The exits of the original loop that will become unreachable from entry
14509467b48Spatrick   // after the constant folding.
14609467b48Spatrick   SmallVector<BasicBlock *, 8> DeadExitBlocks;
14709467b48Spatrick   // The blocks that will still be a part of the current loop after folding.
14809467b48Spatrick   SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
14909467b48Spatrick   // The blocks that have terminators with constant condition that can be
15009467b48Spatrick   // folded. Note: fold candidates should be in L but not in any of its
15109467b48Spatrick   // subloops to avoid complex LI updates.
15209467b48Spatrick   SmallVector<BasicBlock *, 8> FoldCandidates;
15309467b48Spatrick 
dump() const15409467b48Spatrick   void dump() const {
15509467b48Spatrick     dbgs() << "Constant terminator folding for loop " << L << "\n";
15609467b48Spatrick     dbgs() << "After terminator constant-folding, the loop will";
15709467b48Spatrick     if (!DeleteCurrentLoop)
15809467b48Spatrick       dbgs() << " not";
15909467b48Spatrick     dbgs() << " be destroyed\n";
16009467b48Spatrick     auto PrintOutVector = [&](const char *Message,
16109467b48Spatrick                            const SmallVectorImpl<BasicBlock *> &S) {
16209467b48Spatrick       dbgs() << Message << "\n";
16309467b48Spatrick       for (const BasicBlock *BB : S)
16409467b48Spatrick         dbgs() << "\t" << BB->getName() << "\n";
16509467b48Spatrick     };
16609467b48Spatrick     auto PrintOutSet = [&](const char *Message,
16709467b48Spatrick                            const SmallPtrSetImpl<BasicBlock *> &S) {
16809467b48Spatrick       dbgs() << Message << "\n";
16909467b48Spatrick       for (const BasicBlock *BB : S)
17009467b48Spatrick         dbgs() << "\t" << BB->getName() << "\n";
17109467b48Spatrick     };
17209467b48Spatrick     PrintOutVector("Blocks in which we can constant-fold terminator:",
17309467b48Spatrick                    FoldCandidates);
17409467b48Spatrick     PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);
17509467b48Spatrick     PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);
17609467b48Spatrick     PrintOutSet("Live exit blocks:", LiveExitBlocks);
17709467b48Spatrick     PrintOutVector("Dead exit blocks:", DeadExitBlocks);
17809467b48Spatrick     if (!DeleteCurrentLoop)
17909467b48Spatrick       PrintOutSet("The following blocks will still be part of the loop:",
18009467b48Spatrick                   BlocksInLoopAfterFolding);
18109467b48Spatrick   }
18209467b48Spatrick 
18309467b48Spatrick   /// Whether or not the current loop has irreducible CFG.
hasIrreducibleCFG(LoopBlocksDFS & DFS)18409467b48Spatrick   bool hasIrreducibleCFG(LoopBlocksDFS &DFS) {
18509467b48Spatrick     assert(DFS.isComplete() && "DFS is expected to be finished");
18609467b48Spatrick     // Index of a basic block in RPO traversal.
18709467b48Spatrick     DenseMap<const BasicBlock *, unsigned> RPO;
18809467b48Spatrick     unsigned Current = 0;
18909467b48Spatrick     for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I)
19009467b48Spatrick       RPO[*I] = Current++;
19109467b48Spatrick 
19209467b48Spatrick     for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
19309467b48Spatrick       BasicBlock *BB = *I;
19409467b48Spatrick       for (auto *Succ : successors(BB))
19509467b48Spatrick         if (L.contains(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])
19609467b48Spatrick           // If an edge goes from a block with greater order number into a block
19709467b48Spatrick           // with lesses number, and it is not a loop backedge, then it can only
19809467b48Spatrick           // be a part of irreducible non-loop cycle.
19909467b48Spatrick           return true;
20009467b48Spatrick     }
20109467b48Spatrick     return false;
20209467b48Spatrick   }
20309467b48Spatrick 
20409467b48Spatrick   /// Fill all information about status of blocks and exits of the current loop
20509467b48Spatrick   /// if constant folding of all branches will be done.
analyze()20609467b48Spatrick   void analyze() {
20709467b48Spatrick     DFS.perform(&LI);
20809467b48Spatrick     assert(DFS.isComplete() && "DFS is expected to be finished");
20909467b48Spatrick 
21009467b48Spatrick     // TODO: The algorithm below relies on both RPO and Postorder traversals.
21109467b48Spatrick     // When the loop has only reducible CFG inside, then the invariant "all
21209467b48Spatrick     // predecessors of X are processed before X in RPO" is preserved. However
21309467b48Spatrick     // an irreducible loop can break this invariant (e.g. latch does not have to
21409467b48Spatrick     // be the last block in the traversal in this case, and the algorithm relies
21509467b48Spatrick     // on this). We can later decide to support such cases by altering the
21609467b48Spatrick     // algorithms, but so far we just give up analyzing them.
21709467b48Spatrick     if (hasIrreducibleCFG(DFS)) {
21809467b48Spatrick       HasIrreducibleCFG = true;
21909467b48Spatrick       return;
22009467b48Spatrick     }
22109467b48Spatrick 
22209467b48Spatrick     // Collect live and dead loop blocks and exits.
22309467b48Spatrick     LiveLoopBlocks.insert(L.getHeader());
22409467b48Spatrick     for (auto I = DFS.beginRPO(), E = DFS.endRPO(); I != E; ++I) {
22509467b48Spatrick       BasicBlock *BB = *I;
22609467b48Spatrick 
22709467b48Spatrick       // If a loop block wasn't marked as live so far, then it's dead.
22809467b48Spatrick       if (!LiveLoopBlocks.count(BB)) {
22909467b48Spatrick         DeadLoopBlocks.push_back(BB);
23009467b48Spatrick         continue;
23109467b48Spatrick       }
23209467b48Spatrick 
23309467b48Spatrick       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
23409467b48Spatrick 
23509467b48Spatrick       // If a block has only one live successor, it's a candidate on constant
23609467b48Spatrick       // folding. Only handle blocks from current loop: branches in child loops
23709467b48Spatrick       // are skipped because if they can be folded, they should be folded during
23809467b48Spatrick       // the processing of child loops.
23909467b48Spatrick       bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;
24009467b48Spatrick       if (TakeFoldCandidate)
24109467b48Spatrick         FoldCandidates.push_back(BB);
24209467b48Spatrick 
24309467b48Spatrick       // Handle successors.
24409467b48Spatrick       for (BasicBlock *Succ : successors(BB))
24509467b48Spatrick         if (!TakeFoldCandidate || TheOnlySucc == Succ) {
24609467b48Spatrick           if (L.contains(Succ))
24709467b48Spatrick             LiveLoopBlocks.insert(Succ);
24809467b48Spatrick           else
24909467b48Spatrick             LiveExitBlocks.insert(Succ);
25009467b48Spatrick         }
25109467b48Spatrick     }
25209467b48Spatrick 
253*d415bd75Srobert     // Amount of dead and live loop blocks should match the total number of
254*d415bd75Srobert     // blocks in loop.
25509467b48Spatrick     assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
25609467b48Spatrick            "Malformed block sets?");
25709467b48Spatrick 
258*d415bd75Srobert     // Now, all exit blocks that are not marked as live are dead, if all their
259*d415bd75Srobert     // predecessors are in the loop. This may not be the case, as the input loop
260*d415bd75Srobert     // may not by in loop-simplify/canonical form.
26109467b48Spatrick     SmallVector<BasicBlock *, 8> ExitBlocks;
26209467b48Spatrick     L.getExitBlocks(ExitBlocks);
26309467b48Spatrick     SmallPtrSet<BasicBlock *, 8> UniqueDeadExits;
26409467b48Spatrick     for (auto *ExitBlock : ExitBlocks)
26509467b48Spatrick       if (!LiveExitBlocks.count(ExitBlock) &&
266*d415bd75Srobert           UniqueDeadExits.insert(ExitBlock).second &&
267*d415bd75Srobert           all_of(predecessors(ExitBlock),
268*d415bd75Srobert                  [this](BasicBlock *Pred) { return L.contains(Pred); }))
26909467b48Spatrick         DeadExitBlocks.push_back(ExitBlock);
27009467b48Spatrick 
27109467b48Spatrick     // Whether or not the edge From->To will still be present in graph after the
27209467b48Spatrick     // folding.
27309467b48Spatrick     auto IsEdgeLive = [&](BasicBlock *From, BasicBlock *To) {
27409467b48Spatrick       if (!LiveLoopBlocks.count(From))
27509467b48Spatrick         return false;
27609467b48Spatrick       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(From);
27709467b48Spatrick       return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(From) != &L;
27809467b48Spatrick     };
27909467b48Spatrick 
28009467b48Spatrick     // The loop will not be destroyed if its latch is live.
28109467b48Spatrick     DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());
28209467b48Spatrick 
28309467b48Spatrick     // If we are going to delete the current loop completely, no extra analysis
28409467b48Spatrick     // is needed.
28509467b48Spatrick     if (DeleteCurrentLoop)
28609467b48Spatrick       return;
28709467b48Spatrick 
28809467b48Spatrick     // Otherwise, we should check which blocks will still be a part of the
28909467b48Spatrick     // current loop after the transform.
29009467b48Spatrick     BlocksInLoopAfterFolding.insert(L.getLoopLatch());
29109467b48Spatrick     // If the loop is live, then we should compute what blocks are still in
29209467b48Spatrick     // loop after all branch folding has been done. A block is in loop if
29309467b48Spatrick     // it has a live edge to another block that is in the loop; by definition,
29409467b48Spatrick     // latch is in the loop.
29509467b48Spatrick     auto BlockIsInLoop = [&](BasicBlock *BB) {
29609467b48Spatrick       return any_of(successors(BB), [&](BasicBlock *Succ) {
29709467b48Spatrick         return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);
29809467b48Spatrick       });
29909467b48Spatrick     };
30009467b48Spatrick     for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
30109467b48Spatrick       BasicBlock *BB = *I;
30209467b48Spatrick       if (BlockIsInLoop(BB))
30309467b48Spatrick         BlocksInLoopAfterFolding.insert(BB);
30409467b48Spatrick     }
30509467b48Spatrick 
30609467b48Spatrick     assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
30709467b48Spatrick            "Header not in loop?");
30809467b48Spatrick     assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
30909467b48Spatrick            "All blocks that stay in loop should be live!");
31009467b48Spatrick   }
31109467b48Spatrick 
31209467b48Spatrick   /// We need to preserve static reachibility of all loop exit blocks (this is)
31309467b48Spatrick   /// required by loop pass manager. In order to do it, we make the following
31409467b48Spatrick   /// trick:
31509467b48Spatrick   ///
31609467b48Spatrick   ///  preheader:
31709467b48Spatrick   ///    <preheader code>
31809467b48Spatrick   ///    br label %loop_header
31909467b48Spatrick   ///
32009467b48Spatrick   ///  loop_header:
32109467b48Spatrick   ///    ...
32209467b48Spatrick   ///    br i1 false, label %dead_exit, label %loop_block
32309467b48Spatrick   ///    ...
32409467b48Spatrick   ///
32509467b48Spatrick   /// We cannot simply remove edge from the loop to dead exit because in this
32609467b48Spatrick   /// case dead_exit (and its successors) may become unreachable. To avoid that,
32709467b48Spatrick   /// we insert the following fictive preheader:
32809467b48Spatrick   ///
32909467b48Spatrick   ///  preheader:
33009467b48Spatrick   ///    <preheader code>
33109467b48Spatrick   ///    switch i32 0, label %preheader-split,
33209467b48Spatrick   ///                  [i32 1, label %dead_exit_1],
33309467b48Spatrick   ///                  [i32 2, label %dead_exit_2],
33409467b48Spatrick   ///                  ...
33509467b48Spatrick   ///                  [i32 N, label %dead_exit_N],
33609467b48Spatrick   ///
33709467b48Spatrick   ///  preheader-split:
33809467b48Spatrick   ///    br label %loop_header
33909467b48Spatrick   ///
34009467b48Spatrick   ///  loop_header:
34109467b48Spatrick   ///    ...
34209467b48Spatrick   ///    br i1 false, label %dead_exit_N, label %loop_block
34309467b48Spatrick   ///    ...
34409467b48Spatrick   ///
34509467b48Spatrick   /// Doing so, we preserve static reachibility of all dead exits and can later
34609467b48Spatrick   /// remove edges from the loop to these blocks.
handleDeadExits()34709467b48Spatrick   void handleDeadExits() {
34809467b48Spatrick     // If no dead exits, nothing to do.
34909467b48Spatrick     if (DeadExitBlocks.empty())
35009467b48Spatrick       return;
35109467b48Spatrick 
35209467b48Spatrick     // Construct split preheader and the dummy switch to thread edges from it to
35309467b48Spatrick     // dead exits.
35409467b48Spatrick     BasicBlock *Preheader = L.getLoopPreheader();
35509467b48Spatrick     BasicBlock *NewPreheader = llvm::SplitBlock(
35609467b48Spatrick         Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);
35709467b48Spatrick 
35809467b48Spatrick     IRBuilder<> Builder(Preheader->getTerminator());
35909467b48Spatrick     SwitchInst *DummySwitch =
36009467b48Spatrick         Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
36109467b48Spatrick     Preheader->getTerminator()->eraseFromParent();
36209467b48Spatrick 
36309467b48Spatrick     unsigned DummyIdx = 1;
36409467b48Spatrick     for (BasicBlock *BB : DeadExitBlocks) {
36573471bf0Spatrick       // Eliminate all Phis and LandingPads from dead exits.
36673471bf0Spatrick       // TODO: Consider removing all instructions in this dead block.
36773471bf0Spatrick       SmallVector<Instruction *, 4> DeadInstructions;
36809467b48Spatrick       for (auto &PN : BB->phis())
36973471bf0Spatrick         DeadInstructions.push_back(&PN);
37009467b48Spatrick 
37173471bf0Spatrick       if (auto *LandingPad = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()))
37273471bf0Spatrick         DeadInstructions.emplace_back(LandingPad);
37373471bf0Spatrick 
37473471bf0Spatrick       for (Instruction *I : DeadInstructions) {
375*d415bd75Srobert         SE.forgetBlockAndLoopDispositions(I);
376*d415bd75Srobert         I->replaceAllUsesWith(PoisonValue::get(I->getType()));
37773471bf0Spatrick         I->eraseFromParent();
37809467b48Spatrick       }
37973471bf0Spatrick 
38009467b48Spatrick       assert(DummyIdx != 0 && "Too many dead exits!");
38109467b48Spatrick       DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
38209467b48Spatrick       DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});
38309467b48Spatrick       ++NumLoopExitsDeleted;
38409467b48Spatrick     }
38509467b48Spatrick 
38609467b48Spatrick     assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
38709467b48Spatrick     if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
38809467b48Spatrick       // When we break dead edges, the outer loop may become unreachable from
38909467b48Spatrick       // the current loop. We need to fix loop info accordingly. For this, we
39009467b48Spatrick       // find the most nested loop that still contains L and remove L from all
39109467b48Spatrick       // loops that are inside of it.
39209467b48Spatrick       Loop *StillReachable = getInnermostLoopFor(LiveExitBlocks, L, LI);
39309467b48Spatrick 
39409467b48Spatrick       // Okay, our loop is no longer in the outer loop (and maybe not in some of
39509467b48Spatrick       // its parents as well). Make the fixup.
39609467b48Spatrick       if (StillReachable != OuterLoop) {
39709467b48Spatrick         LI.changeLoopFor(NewPreheader, StillReachable);
39809467b48Spatrick         removeBlockFromLoops(NewPreheader, OuterLoop, StillReachable);
39909467b48Spatrick         for (auto *BB : L.blocks())
40009467b48Spatrick           removeBlockFromLoops(BB, OuterLoop, StillReachable);
40109467b48Spatrick         OuterLoop->removeChildLoop(&L);
40209467b48Spatrick         if (StillReachable)
40309467b48Spatrick           StillReachable->addChildLoop(&L);
40409467b48Spatrick         else
40509467b48Spatrick           LI.addTopLevelLoop(&L);
40609467b48Spatrick 
40709467b48Spatrick         // Some values from loops in [OuterLoop, StillReachable) could be used
40809467b48Spatrick         // in the current loop. Now it is not their child anymore, so such uses
40909467b48Spatrick         // require LCSSA Phis.
41009467b48Spatrick         Loop *FixLCSSALoop = OuterLoop;
41109467b48Spatrick         while (FixLCSSALoop->getParentLoop() != StillReachable)
41209467b48Spatrick           FixLCSSALoop = FixLCSSALoop->getParentLoop();
41309467b48Spatrick         assert(FixLCSSALoop && "Should be a loop!");
41409467b48Spatrick         // We need all DT updates to be done before forming LCSSA.
41509467b48Spatrick         if (MSSAU)
41673471bf0Spatrick           MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
41773471bf0Spatrick         else
41873471bf0Spatrick           DTU.applyUpdates(DTUpdates);
41909467b48Spatrick         DTUpdates.clear();
42009467b48Spatrick         formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
421*d415bd75Srobert         SE.forgetBlockAndLoopDispositions();
42209467b48Spatrick       }
42309467b48Spatrick     }
42409467b48Spatrick 
42509467b48Spatrick     if (MSSAU) {
42609467b48Spatrick       // Clear all updates now. Facilitates deletes that follow.
42773471bf0Spatrick       MSSAU->applyUpdates(DTUpdates, DT, /*UpdateDT=*/true);
42809467b48Spatrick       DTUpdates.clear();
42909467b48Spatrick       if (VerifyMemorySSA)
43009467b48Spatrick         MSSAU->getMemorySSA()->verifyMemorySSA();
43109467b48Spatrick     }
43209467b48Spatrick   }
43309467b48Spatrick 
43409467b48Spatrick   /// Delete loop blocks that have become unreachable after folding. Make all
43509467b48Spatrick   /// relevant updates to DT and LI.
deleteDeadLoopBlocks()43609467b48Spatrick   void deleteDeadLoopBlocks() {
43709467b48Spatrick     if (MSSAU) {
43809467b48Spatrick       SmallSetVector<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
43909467b48Spatrick                                                         DeadLoopBlocks.end());
44009467b48Spatrick       MSSAU->removeBlocks(DeadLoopBlocksSet);
44109467b48Spatrick     }
44209467b48Spatrick 
44309467b48Spatrick     // The function LI.erase has some invariants that need to be preserved when
44409467b48Spatrick     // it tries to remove a loop which is not the top-level loop. In particular,
44509467b48Spatrick     // it requires loop's preheader to be strictly in loop's parent. We cannot
44609467b48Spatrick     // just remove blocks one by one, because after removal of preheader we may
44709467b48Spatrick     // break this invariant for the dead loop. So we detatch and erase all dead
44809467b48Spatrick     // loops beforehand.
44909467b48Spatrick     for (auto *BB : DeadLoopBlocks)
45009467b48Spatrick       if (LI.isLoopHeader(BB)) {
45109467b48Spatrick         assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
45209467b48Spatrick         Loop *DL = LI.getLoopFor(BB);
45373471bf0Spatrick         if (!DL->isOutermost()) {
45409467b48Spatrick           for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
45509467b48Spatrick             for (auto *BB : DL->getBlocks())
45609467b48Spatrick               PL->removeBlockFromLoop(BB);
45709467b48Spatrick           DL->getParentLoop()->removeChildLoop(DL);
45809467b48Spatrick           LI.addTopLevelLoop(DL);
45909467b48Spatrick         }
46009467b48Spatrick         LI.erase(DL);
46109467b48Spatrick       }
46209467b48Spatrick 
46309467b48Spatrick     for (auto *BB : DeadLoopBlocks) {
46409467b48Spatrick       assert(BB != L.getHeader() &&
46509467b48Spatrick              "Header of the current loop cannot be dead!");
46609467b48Spatrick       LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
46709467b48Spatrick                         << "\n");
46809467b48Spatrick       LI.removeBlock(BB);
46909467b48Spatrick     }
47009467b48Spatrick 
471*d415bd75Srobert     detachDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
47209467b48Spatrick     DTU.applyUpdates(DTUpdates);
47309467b48Spatrick     DTUpdates.clear();
47409467b48Spatrick     for (auto *BB : DeadLoopBlocks)
47509467b48Spatrick       DTU.deleteBB(BB);
47609467b48Spatrick 
47709467b48Spatrick     NumLoopBlocksDeleted += DeadLoopBlocks.size();
47809467b48Spatrick   }
47909467b48Spatrick 
480*d415bd75Srobert   /// Constant-fold terminators of blocks accumulated in FoldCandidates into the
48109467b48Spatrick   /// unconditional branches.
foldTerminators()48209467b48Spatrick   void foldTerminators() {
48309467b48Spatrick     for (BasicBlock *BB : FoldCandidates) {
48409467b48Spatrick       assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
48509467b48Spatrick       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);
48609467b48Spatrick       assert(TheOnlySucc && "Should have one live successor!");
48709467b48Spatrick 
48809467b48Spatrick       LLVM_DEBUG(dbgs() << "Replacing terminator of " << BB->getName()
48909467b48Spatrick                         << " with an unconditional branch to the block "
49009467b48Spatrick                         << TheOnlySucc->getName() << "\n");
49109467b48Spatrick 
49209467b48Spatrick       SmallPtrSet<BasicBlock *, 2> DeadSuccessors;
49309467b48Spatrick       // Remove all BB's successors except for the live one.
49409467b48Spatrick       unsigned TheOnlySuccDuplicates = 0;
49509467b48Spatrick       for (auto *Succ : successors(BB))
49609467b48Spatrick         if (Succ != TheOnlySucc) {
49709467b48Spatrick           DeadSuccessors.insert(Succ);
49809467b48Spatrick           // If our successor lies in a different loop, we don't want to remove
49909467b48Spatrick           // the one-input Phi because it is a LCSSA Phi.
50009467b48Spatrick           bool PreserveLCSSAPhi = !L.contains(Succ);
50109467b48Spatrick           Succ->removePredecessor(BB, PreserveLCSSAPhi);
50209467b48Spatrick           if (MSSAU)
50309467b48Spatrick             MSSAU->removeEdge(BB, Succ);
50409467b48Spatrick         } else
50509467b48Spatrick           ++TheOnlySuccDuplicates;
50609467b48Spatrick 
50709467b48Spatrick       assert(TheOnlySuccDuplicates > 0 && "Should be!");
50809467b48Spatrick       // If TheOnlySucc was BB's successor more than once, after transform it
50909467b48Spatrick       // will be its successor only once. Remove redundant inputs from
51009467b48Spatrick       // TheOnlySucc's Phis.
51109467b48Spatrick       bool PreserveLCSSAPhi = !L.contains(TheOnlySucc);
51209467b48Spatrick       for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)
51309467b48Spatrick         TheOnlySucc->removePredecessor(BB, PreserveLCSSAPhi);
51409467b48Spatrick       if (MSSAU && TheOnlySuccDuplicates > 1)
51509467b48Spatrick         MSSAU->removeDuplicatePhiEdgesBetween(BB, TheOnlySucc);
51609467b48Spatrick 
51709467b48Spatrick       IRBuilder<> Builder(BB->getContext());
51809467b48Spatrick       Instruction *Term = BB->getTerminator();
51909467b48Spatrick       Builder.SetInsertPoint(Term);
52009467b48Spatrick       Builder.CreateBr(TheOnlySucc);
52109467b48Spatrick       Term->eraseFromParent();
52209467b48Spatrick 
52309467b48Spatrick       for (auto *DeadSucc : DeadSuccessors)
52409467b48Spatrick         DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});
52509467b48Spatrick 
52609467b48Spatrick       ++NumTerminatorsFolded;
52709467b48Spatrick     }
52809467b48Spatrick   }
52909467b48Spatrick 
53009467b48Spatrick public:
ConstantTerminatorFoldingImpl(Loop & L,LoopInfo & LI,DominatorTree & DT,ScalarEvolution & SE,MemorySSAUpdater * MSSAU)53109467b48Spatrick   ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
53209467b48Spatrick                                 ScalarEvolution &SE,
53309467b48Spatrick                                 MemorySSAUpdater *MSSAU)
53409467b48Spatrick       : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),
53509467b48Spatrick         DTU(DT, DomTreeUpdater::UpdateStrategy::Eager) {}
run()53609467b48Spatrick   bool run() {
53709467b48Spatrick     assert(L.getLoopLatch() && "Should be single latch!");
53809467b48Spatrick 
53909467b48Spatrick     // Collect all available information about status of blocks after constant
54009467b48Spatrick     // folding.
54109467b48Spatrick     analyze();
54209467b48Spatrick     BasicBlock *Header = L.getHeader();
54309467b48Spatrick     (void)Header;
54409467b48Spatrick 
54509467b48Spatrick     LLVM_DEBUG(dbgs() << "In function " << Header->getParent()->getName()
54609467b48Spatrick                       << ": ");
54709467b48Spatrick 
54809467b48Spatrick     if (HasIrreducibleCFG) {
54909467b48Spatrick       LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");
55009467b48Spatrick       return false;
55109467b48Spatrick     }
55209467b48Spatrick 
55309467b48Spatrick     // Nothing to constant-fold.
55409467b48Spatrick     if (FoldCandidates.empty()) {
55509467b48Spatrick       LLVM_DEBUG(
55609467b48Spatrick           dbgs() << "No constant terminator folding candidates found in loop "
55709467b48Spatrick                  << Header->getName() << "\n");
55809467b48Spatrick       return false;
55909467b48Spatrick     }
56009467b48Spatrick 
56109467b48Spatrick     // TODO: Support deletion of the current loop.
56209467b48Spatrick     if (DeleteCurrentLoop) {
56309467b48Spatrick       LLVM_DEBUG(
56409467b48Spatrick           dbgs()
56509467b48Spatrick           << "Give up constant terminator folding in loop " << Header->getName()
56609467b48Spatrick           << ": we don't currently support deletion of the current loop.\n");
56709467b48Spatrick       return false;
56809467b48Spatrick     }
56909467b48Spatrick 
57009467b48Spatrick     // TODO: Support blocks that are not dead, but also not in loop after the
57109467b48Spatrick     // folding.
57209467b48Spatrick     if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
57309467b48Spatrick         L.getNumBlocks()) {
57409467b48Spatrick       LLVM_DEBUG(
57509467b48Spatrick           dbgs() << "Give up constant terminator folding in loop "
57609467b48Spatrick                  << Header->getName() << ": we don't currently"
57709467b48Spatrick                     " support blocks that are not dead, but will stop "
57809467b48Spatrick                     "being a part of the loop after constant-folding.\n");
57909467b48Spatrick       return false;
58009467b48Spatrick     }
58109467b48Spatrick 
582*d415bd75Srobert     // TODO: Tokens may breach LCSSA form by default. However, the transform for
583*d415bd75Srobert     // dead exit blocks requires LCSSA form to be maintained for all values,
584*d415bd75Srobert     // tokens included, otherwise it may break use-def dominance (see PR56243).
585*d415bd75Srobert     if (!DeadExitBlocks.empty() && !L.isLCSSAForm(DT, /*IgnoreTokens*/ false)) {
586*d415bd75Srobert       assert(L.isLCSSAForm(DT, /*IgnoreTokens*/ true) &&
587*d415bd75Srobert              "LCSSA broken not by tokens?");
588*d415bd75Srobert       LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop "
589*d415bd75Srobert                         << Header->getName()
590*d415bd75Srobert                         << ": tokens uses potentially break LCSSA form.\n");
591*d415bd75Srobert       return false;
592*d415bd75Srobert     }
593*d415bd75Srobert 
59409467b48Spatrick     SE.forgetTopmostLoop(&L);
59509467b48Spatrick     // Dump analysis results.
59609467b48Spatrick     LLVM_DEBUG(dump());
59709467b48Spatrick 
59809467b48Spatrick     LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
59909467b48Spatrick                       << " terminators in loop " << Header->getName() << "\n");
60009467b48Spatrick 
601*d415bd75Srobert     if (!DeadLoopBlocks.empty())
602*d415bd75Srobert       SE.forgetBlockAndLoopDispositions();
603*d415bd75Srobert 
60409467b48Spatrick     // Make the actual transforms.
60509467b48Spatrick     handleDeadExits();
60609467b48Spatrick     foldTerminators();
60709467b48Spatrick 
60809467b48Spatrick     if (!DeadLoopBlocks.empty()) {
60909467b48Spatrick       LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
61009467b48Spatrick                     << " dead blocks in loop " << Header->getName() << "\n");
61109467b48Spatrick       deleteDeadLoopBlocks();
61209467b48Spatrick     } else {
61309467b48Spatrick       // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
61409467b48Spatrick       DTU.applyUpdates(DTUpdates);
61509467b48Spatrick       DTUpdates.clear();
61609467b48Spatrick     }
61709467b48Spatrick 
61809467b48Spatrick     if (MSSAU && VerifyMemorySSA)
61909467b48Spatrick       MSSAU->getMemorySSA()->verifyMemorySSA();
62009467b48Spatrick 
62109467b48Spatrick #ifndef NDEBUG
62209467b48Spatrick     // Make sure that we have preserved all data structures after the transform.
62309467b48Spatrick #if defined(EXPENSIVE_CHECKS)
62409467b48Spatrick     assert(DT.verify(DominatorTree::VerificationLevel::Full) &&
62509467b48Spatrick            "DT broken after transform!");
62609467b48Spatrick #else
62709467b48Spatrick     assert(DT.verify(DominatorTree::VerificationLevel::Fast) &&
62809467b48Spatrick            "DT broken after transform!");
62909467b48Spatrick #endif
63009467b48Spatrick     assert(DT.isReachableFromEntry(Header));
63109467b48Spatrick     LI.verify(DT);
63209467b48Spatrick #endif
63309467b48Spatrick 
63409467b48Spatrick     return true;
63509467b48Spatrick   }
63609467b48Spatrick 
foldingBreaksCurrentLoop() const63709467b48Spatrick   bool foldingBreaksCurrentLoop() const {
63809467b48Spatrick     return DeleteCurrentLoop;
63909467b48Spatrick   }
64009467b48Spatrick };
64109467b48Spatrick } // namespace
64209467b48Spatrick 
64309467b48Spatrick /// Turn branches and switches with known constant conditions into unconditional
64409467b48Spatrick /// branches.
constantFoldTerminators(Loop & L,DominatorTree & DT,LoopInfo & LI,ScalarEvolution & SE,MemorySSAUpdater * MSSAU,bool & IsLoopDeleted)64509467b48Spatrick static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI,
64609467b48Spatrick                                     ScalarEvolution &SE,
64709467b48Spatrick                                     MemorySSAUpdater *MSSAU,
64809467b48Spatrick                                     bool &IsLoopDeleted) {
64909467b48Spatrick   if (!EnableTermFolding)
65009467b48Spatrick     return false;
65109467b48Spatrick 
65209467b48Spatrick   // To keep things simple, only process loops with single latch. We
65309467b48Spatrick   // canonicalize most loops to this form. We can support multi-latch if needed.
65409467b48Spatrick   if (!L.getLoopLatch())
65509467b48Spatrick     return false;
65609467b48Spatrick 
65709467b48Spatrick   ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);
65809467b48Spatrick   bool Changed = BranchFolder.run();
65909467b48Spatrick   IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();
66009467b48Spatrick   return Changed;
66109467b48Spatrick }
66209467b48Spatrick 
mergeBlocksIntoPredecessors(Loop & L,DominatorTree & DT,LoopInfo & LI,MemorySSAUpdater * MSSAU,ScalarEvolution & SE)66309467b48Spatrick static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT,
664*d415bd75Srobert                                         LoopInfo &LI, MemorySSAUpdater *MSSAU,
665*d415bd75Srobert                                         ScalarEvolution &SE) {
66609467b48Spatrick   bool Changed = false;
66709467b48Spatrick   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
66809467b48Spatrick   // Copy blocks into a temporary array to avoid iterator invalidation issues
66909467b48Spatrick   // as we remove them.
67009467b48Spatrick   SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
67109467b48Spatrick 
67209467b48Spatrick   for (auto &Block : Blocks) {
67309467b48Spatrick     // Attempt to merge blocks in the trivial case. Don't modify blocks which
67409467b48Spatrick     // belong to other loops.
67509467b48Spatrick     BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
67609467b48Spatrick     if (!Succ)
67709467b48Spatrick       continue;
67809467b48Spatrick 
67909467b48Spatrick     BasicBlock *Pred = Succ->getSinglePredecessor();
68009467b48Spatrick     if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
68109467b48Spatrick       continue;
68209467b48Spatrick 
68309467b48Spatrick     // Merge Succ into Pred and delete it.
68409467b48Spatrick     MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
68509467b48Spatrick 
68609467b48Spatrick     if (MSSAU && VerifyMemorySSA)
68709467b48Spatrick       MSSAU->getMemorySSA()->verifyMemorySSA();
68809467b48Spatrick 
68909467b48Spatrick     Changed = true;
69009467b48Spatrick   }
69109467b48Spatrick 
692*d415bd75Srobert   if (Changed)
693*d415bd75Srobert     SE.forgetBlockAndLoopDispositions();
694*d415bd75Srobert 
69509467b48Spatrick   return Changed;
69609467b48Spatrick }
69709467b48Spatrick 
simplifyLoopCFG(Loop & L,DominatorTree & DT,LoopInfo & LI,ScalarEvolution & SE,MemorySSAUpdater * MSSAU,bool & IsLoopDeleted)69809467b48Spatrick static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
69909467b48Spatrick                             ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
700097a140dSpatrick                             bool &IsLoopDeleted) {
70109467b48Spatrick   bool Changed = false;
70209467b48Spatrick 
70309467b48Spatrick   // Constant-fold terminators with known constant conditions.
704097a140dSpatrick   Changed |= constantFoldTerminators(L, DT, LI, SE, MSSAU, IsLoopDeleted);
70509467b48Spatrick 
706097a140dSpatrick   if (IsLoopDeleted)
70709467b48Spatrick     return true;
70809467b48Spatrick 
70909467b48Spatrick   // Eliminate unconditional branches by merging blocks into their predecessors.
710*d415bd75Srobert   Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU, SE);
71109467b48Spatrick 
71209467b48Spatrick   if (Changed)
71309467b48Spatrick     SE.forgetTopmostLoop(&L);
71409467b48Spatrick 
71509467b48Spatrick   return Changed;
71609467b48Spatrick }
71709467b48Spatrick 
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater & LPMU)71809467b48Spatrick PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
71909467b48Spatrick                                            LoopStandardAnalysisResults &AR,
72009467b48Spatrick                                            LPMUpdater &LPMU) {
721*d415bd75Srobert   std::optional<MemorySSAUpdater> MSSAU;
72209467b48Spatrick   if (AR.MSSA)
72309467b48Spatrick     MSSAU = MemorySSAUpdater(AR.MSSA);
72409467b48Spatrick   bool DeleteCurrentLoop = false;
725*d415bd75Srobert   if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE, MSSAU ? &*MSSAU : nullptr,
72609467b48Spatrick                        DeleteCurrentLoop))
72709467b48Spatrick     return PreservedAnalyses::all();
72809467b48Spatrick 
72909467b48Spatrick   if (DeleteCurrentLoop)
73009467b48Spatrick     LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
73109467b48Spatrick 
73209467b48Spatrick   auto PA = getLoopPassPreservedAnalyses();
73309467b48Spatrick   if (AR.MSSA)
73409467b48Spatrick     PA.preserve<MemorySSAAnalysis>();
73509467b48Spatrick   return PA;
73609467b48Spatrick }
73709467b48Spatrick 
73809467b48Spatrick namespace {
73909467b48Spatrick class LoopSimplifyCFGLegacyPass : public LoopPass {
74009467b48Spatrick public:
74109467b48Spatrick   static char ID; // Pass ID, replacement for typeid
LoopSimplifyCFGLegacyPass()74209467b48Spatrick   LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
74309467b48Spatrick     initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
74409467b48Spatrick   }
74509467b48Spatrick 
runOnLoop(Loop * L,LPPassManager & LPM)74609467b48Spatrick   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
74709467b48Spatrick     if (skipLoop(L))
74809467b48Spatrick       return false;
74909467b48Spatrick 
75009467b48Spatrick     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
75109467b48Spatrick     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
75209467b48Spatrick     ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
753*d415bd75Srobert     auto *MSSAA = getAnalysisIfAvailable<MemorySSAWrapperPass>();
754*d415bd75Srobert     std::optional<MemorySSAUpdater> MSSAU;
755*d415bd75Srobert     if (MSSAA)
756*d415bd75Srobert       MSSAU = MemorySSAUpdater(&MSSAA->getMSSA());
757*d415bd75Srobert     if (MSSAA && VerifyMemorySSA)
758*d415bd75Srobert       MSSAU->getMemorySSA()->verifyMemorySSA();
75909467b48Spatrick     bool DeleteCurrentLoop = false;
760*d415bd75Srobert     bool Changed = simplifyLoopCFG(*L, DT, LI, SE, MSSAU ? &*MSSAU : nullptr,
76109467b48Spatrick                                    DeleteCurrentLoop);
76209467b48Spatrick     if (DeleteCurrentLoop)
76309467b48Spatrick       LPM.markLoopAsDeleted(*L);
76409467b48Spatrick     return Changed;
76509467b48Spatrick   }
76609467b48Spatrick 
getAnalysisUsage(AnalysisUsage & AU) const76709467b48Spatrick   void getAnalysisUsage(AnalysisUsage &AU) const override {
76809467b48Spatrick     AU.addPreserved<MemorySSAWrapperPass>();
76909467b48Spatrick     AU.addPreserved<DependenceAnalysisWrapperPass>();
77009467b48Spatrick     getLoopAnalysisUsage(AU);
77109467b48Spatrick   }
77209467b48Spatrick };
773097a140dSpatrick } // end namespace
77409467b48Spatrick 
77509467b48Spatrick char LoopSimplifyCFGLegacyPass::ID = 0;
77609467b48Spatrick INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
77709467b48Spatrick                       "Simplify loop CFG", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopPass)77809467b48Spatrick INITIALIZE_PASS_DEPENDENCY(LoopPass)
77909467b48Spatrick INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
78009467b48Spatrick INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
78109467b48Spatrick                     "Simplify loop CFG", false, false)
78209467b48Spatrick 
78309467b48Spatrick Pass *llvm::createLoopSimplifyCFGPass() {
78409467b48Spatrick   return new LoopSimplifyCFGLegacyPass();
78509467b48Spatrick }
786