text: //===- BasicBlockUtils.cpp - Unit tests for BasicBlockUtils ---------------===//
  //
  // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  // See https://llvm.org/LICENSE.txt for license information.
  // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  //
  //===----------------------------------------------------------------------===//
  
  #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  #include "llvm/Analysis/AssumptionCache.h"
  #include "llvm/Analysis/BasicAliasAnalysis.h"
  #include "llvm/Analysis/BlockFrequencyInfo.h"
  #include "llvm/Analysis/BranchProbabilityInfo.h"
  #include "llvm/Analysis/CFG.h"
  #include "llvm/Analysis/LoopInfo.h"
  #include "llvm/Analysis/MemorySSA.h"
  #include "llvm/Analysis/MemorySSAUpdater.h"
  #include "llvm/Analysis/PostDominators.h"
  #include "llvm/Analysis/TargetLibraryInfo.h"
  #include "llvm/AsmParser/Parser.h"
  #include "llvm/IR/BasicBlock.h"
  #include "llvm/IR/Dominators.h"
  #include "llvm/IR/LLVMContext.h"
  #include "llvm/Support/SourceMgr.h"
  #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
  #include "gtest/gtest.h"
  
  using namespace llvm;
  
  static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
    SMDiagnostic Err;
    std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
    if (!Mod)
      Err.print("BasicBlockUtilsTests", errs());
    return Mod;
  }
  
  static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) {
    for (BasicBlock &BB : F)
      if (BB.getName() == Name)
        return &BB;
    llvm_unreachable("Expected to find basic block!");
  }
  
  TEST(BasicBlockUtils, EliminateUnreachableBlocks) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define i32 @has_unreachable(i1 %cond) {
  entry:
    br i1 %cond, label %bb0, label %bb1
  bb0:
    br label %bb1
  bb1:
    %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]
    ret i32 %phi
  bb2:
    ret i32 42
  }
  )IR");
    Function *F = M->getFunction("has_unreachable");
    DominatorTree DT(*F);
    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
  
    EXPECT_EQ(F->size(), (size_t)4);
    bool Result = EliminateUnreachableBlocks(*F, &DTU);
    EXPECT_TRUE(Result);
    EXPECT_EQ(F->size(), (size_t)3);
    EXPECT_TRUE(DT.verify());
  }
  
  TEST(BasicBlockUtils, SplitEdge_ex1) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define void @foo(i1 %cond0) {
  entry:
    br i1 %cond0, label %bb0, label %bb1
  bb0:
   %0 = mul i32 1, 2
    br label %bb1
  bb1:
    br label %bb2
  bb2:
    ret void
  }
  )IR");
    Function *F = M->getFunction("foo");
    DominatorTree DT(*F);
    BasicBlock *SrcBlock;
    BasicBlock *DestBlock;
    BasicBlock *NewBB;
  
    SrcBlock = getBasicBlockByName(*F, "entry");
    DestBlock = getBasicBlockByName(*F, "bb0");
    NewBB = SplitEdge(SrcBlock, DestBlock, &DT, nullptr, nullptr);
  
    EXPECT_TRUE(DT.verify());
    EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
    EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
    EXPECT_EQ(NewBB->getParent(), F);
  
    bool BBFlag = false;
    for (BasicBlock &BB : *F) {
      if (BB.getName() == NewBB->getName()) {
        BBFlag = true;
      }
    }
    EXPECT_TRUE(BBFlag);
  }
  
  TEST(BasicBlockUtils, SplitEdge_ex2) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define void @foo() {
  bb0:
    br label %bb2
  bb1:
    br label %bb2
  bb2:
    ret void
  }
  )IR");
    Function *F = M->getFunction("foo");
    DominatorTree DT(*F);
  
    BasicBlock *SrcBlock;
    BasicBlock *DestBlock;
    BasicBlock *NewBB;
  
    SrcBlock = getBasicBlockByName(*F, "bb0");
    DestBlock = getBasicBlockByName(*F, "bb2");
    NewBB = SplitEdge(SrcBlock, DestBlock, &DT, nullptr, nullptr);
  
    EXPECT_TRUE(DT.verify());
    EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
    EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
    EXPECT_EQ(NewBB->getParent(), F);
  
    bool BBFlag = false;
    for (BasicBlock &BB : *F) {
      if (BB.getName() == NewBB->getName()) {
        BBFlag = true;
      }
    }
    EXPECT_TRUE(BBFlag);
  }
  
  TEST(BasicBlockUtils, SplitEdge_ex3) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define i32 @foo(i32 %n) {
  entry:
   br label %header
  header:
   %sum.02 = phi i32 [ 0, %entry ], [ %sum.1, %bb3 ]
   %0 = phi i32 [ 0, %entry ], [ %4, %bb3 ]
   %1 = icmp slt i32 %0, %n
   br i1 %1, label %bb0, label %bb1
  bb0:
    %2 = add nsw i32 %sum.02, 2
    br label %bb2
  bb1:
    %3 = add nsw i32 %sum.02, 1
    br label %bb2
  bb2:
    %sum.1 = phi i32 [ %2, %bb0 ], [ %3, %bb1 ]
    br label %bb3
  bb3:
    %4 = add nsw i32 %0, 1
    %5 = icmp slt i32 %4, 100
    br i1 %5, label %header, label %bb4
  bb4:
   %sum.0.lcssa = phi i32 [ %sum.1, %bb3 ]
   ret i32 %sum.0.lcssa
  }
  )IR");
    Function *F = M->getFunction("foo");
    DominatorTree DT(*F);
  
    LoopInfo LI(DT);
  
    DataLayout DL("e-i64:64-f80:128-n8:16:32:64-S128");
    TargetLibraryInfoImpl TLII;
    TargetLibraryInfo TLI(TLII);
    AssumptionCache AC(*F);
    AAResults AA(TLI);
  
    BasicAAResult BAA(DL, *F, TLI, AC, &DT);
    AA.addAAResult(BAA);
  
    MemorySSA MSSA(*F, &AA, &DT);
    MemorySSAUpdater Updater(&MSSA);
  
    BasicBlock *SrcBlock;
    BasicBlock *DestBlock;
    BasicBlock *NewBB;
  
    SrcBlock = getBasicBlockByName(*F, "header");
    DestBlock = getBasicBlockByName(*F, "bb0");
    NewBB = SplitEdge(SrcBlock, DestBlock, &DT, &LI, &Updater);
  
    Updater.getMemorySSA()->verifyMemorySSA();
    EXPECT_TRUE(DT.verify());
    EXPECT_NE(LI.getLoopFor(SrcBlock), nullptr);
    EXPECT_NE(LI.getLoopFor(DestBlock), nullptr);
    EXPECT_NE(LI.getLoopFor(NewBB), nullptr);
    EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
    EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
    EXPECT_EQ(NewBB->getParent(), F);
  
    bool BBFlag = false;
    for (BasicBlock &BB : *F) {
      if (BB.getName() == NewBB->getName()) {
        BBFlag = true;
      }
    }
    EXPECT_TRUE(BBFlag);
  }
  
  TEST(BasicBlockUtils, SplitEdge_ex4) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define void @bar(i32 %cond) personality i8 0 {
  entry:
    switch i32 %cond, label %exit [
      i32 -1, label %continue
      i32 0, label %continue
      i32 1, label %continue_alt
      i32 2, label %continue_alt
    ]
  exit:
    ret void
  continue:
    invoke void @sink() to label %normal unwind label %exception
  continue_alt:
    invoke void @sink_alt() to label %normal unwind label %exception
  exception:
    %cleanup = landingpad i8 cleanup
    br label %trivial-eh-handler
  trivial-eh-handler:
    call void @sideeffect(i32 1)
    br label %normal
  normal:
    call void @sideeffect(i32 0)
    ret void
  }
  
  declare void @sideeffect(i32)
  declare void @sink() cold
  declare void @sink_alt() cold
  )IR");
    Function *F = M->getFunction("bar");
  
    DominatorTree DT(*F);
  
    LoopInfo LI(DT);
  
    TargetLibraryInfoImpl TLII;
    TargetLibraryInfo TLI(TLII);
  
    AAResults AA(TLI);
  
    MemorySSA MSSA(*F, &AA, &DT);
    MemorySSAUpdater MSSAU(&MSSA);
  
    BasicBlock *SrcBlock;
    BasicBlock *DestBlock;
  
    SrcBlock = getBasicBlockByName(*F, "continue");
    DestBlock = getBasicBlockByName(*F, "exception");
  
    unsigned SuccNum = GetSuccessorNumber(SrcBlock, DestBlock);
    Instruction *LatchTerm = SrcBlock->getTerminator();
  
    const CriticalEdgeSplittingOptions Options =
        CriticalEdgeSplittingOptions(&DT, &LI, &MSSAU);
  
    // Check that the following edge is both critical and the destination block is
    // an exception block. These must be handled differently by SplitEdge
    bool CriticalEdge =
        isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges);
    EXPECT_TRUE(CriticalEdge);
  
    bool Ehpad = DestBlock->isEHPad();
    EXPECT_TRUE(Ehpad);
  
    BasicBlock *NewBB = SplitEdge(SrcBlock, DestBlock, &DT, &LI, &MSSAU, "");
  
    MSSA.verifyMemorySSA();
    EXPECT_TRUE(DT.verify());
    EXPECT_NE(NewBB, nullptr);
    EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
    EXPECT_EQ(NewBB, SrcBlock->getTerminator()->getSuccessor(SuccNum));
    EXPECT_EQ(NewBB->getParent(), F);
  
    bool BBFlag = false;
    for (BasicBlock &BB : *F) {
      if (BB.getName() == NewBB->getName()) {
        BBFlag = true;
        break;
      }
    }
    EXPECT_TRUE(BBFlag);
  }
  
  TEST(BasicBlockUtils, splitBasicBlockBefore_ex1) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define void @foo() {
  bb0:
   %0 = mul i32 1, 2
    br label %bb2
  bb1:
    br label %bb3
  bb2:
    %1 = phi  i32 [ %0, %bb0 ]
    br label %bb3
  bb3:
    ret void
  }
  )IR");
    Function *F = M->getFunction("foo");
    DominatorTree DT(*F);
  
    BasicBlock *DestBlock;
    BasicBlock *NewBB;
  
    DestBlock = getBasicBlockByName(*F, "bb2");
  
    NewBB = DestBlock->splitBasicBlockBefore(DestBlock->front().getIterator(),
                                             "test");
  
    PHINode *PN = dyn_cast<PHINode>(&(DestBlock->front()));
    EXPECT_EQ(PN->getIncomingBlock(0), NewBB);
    EXPECT_EQ(NewBB->getName(), "test");
    EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
    EXPECT_EQ(DestBlock->getSinglePredecessor(), NewBB);
  }
  
  #ifndef NDEBUG
  TEST(BasicBlockUtils, splitBasicBlockBefore_ex2) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define void @foo() {
  bb0:
   %0 = mul i32 1, 2
    br label %bb2
  bb1:
    br label %bb2
  bb2:
    %1 = phi  i32 [ %0, %bb0 ], [ 1, %bb1 ]
    br label %bb3
  bb3:
    ret void
  }
  )IR");
    Function *F = M->getFunction("foo");
    DominatorTree DT(*F);
  
    BasicBlock *DestBlock = getBasicBlockByName(*F, "bb2");
  
    ASSERT_DEATH(
        {
          DestBlock->splitBasicBlockBefore(DestBlock->front().getIterator(),
                                           "test");
        },
        "cannot split on multi incoming phis");
  }
  #endif
  
  TEST(BasicBlockUtils, NoUnreachableBlocksToEliminate) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define i32 @no_unreachable(i1 %cond) {
  entry:
    br i1 %cond, label %bb0, label %bb1
  bb0:
    br label %bb1
  bb1:
    %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]
    ret i32 %phi
  }
  )IR");
    Function *F = M->getFunction("no_unreachable");
    DominatorTree DT(*F);
    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
  
    EXPECT_EQ(F->size(), (size_t)3);
    bool Result = EliminateUnreachableBlocks(*F, &DTU);
    EXPECT_FALSE(Result);
    EXPECT_EQ(F->size(), (size_t)3);
    EXPECT_TRUE(DT.verify());
  }
  
  TEST(BasicBlockUtils, SplitBlockPredecessors) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define i32 @basic_func(i1 %cond) {
  entry:
    br i1 %cond, label %bb0, label %bb1
  bb0:
    br label %bb1
  bb1:
    %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]
    ret i32 %phi
  }
  )IR");
    Function *F = M->getFunction("basic_func");
    DominatorTree DT(*F);
  
    // Make sure the dominator tree is properly updated if calling this on the
    // entry block.
    SplitBlockPredecessors(&F->getEntryBlock(), {}, "split.entry", &DT);
    EXPECT_TRUE(DT.verify());
  }
  
  TEST(BasicBlockUtils, SplitCriticalEdge) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define void @crit_edge(i1 %cond0, i1 %cond1) {
  entry:
    br i1 %cond0, label %bb0, label %bb1
  bb0:
    br label %bb1
  bb1:
    br label %bb2
  bb2:
    ret void
  }
  )IR");
    Function *F = M->getFunction("crit_edge");
    DominatorTree DT(*F);
    PostDominatorTree PDT(*F);
  
    CriticalEdgeSplittingOptions CESO(&DT, nullptr, nullptr, &PDT);
    EXPECT_EQ(1u, SplitAllCriticalEdges(*F, CESO));
    EXPECT_TRUE(DT.verify());
    EXPECT_TRUE(PDT.verify());
  }
  
  TEST(BasicBlockUtils, SplitIndirectBrCriticalEdgesIgnorePHIs) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define void @crit_edge(i8* %tgt, i1 %cond0, i1 %cond1) {
  entry:
    indirectbr i8* %tgt, [label %bb0, label %bb1, label %bb2]
  bb0:
    br i1 %cond0, label %bb1, label %bb2
  bb1:
    %p = phi i32 [0, %bb0], [0, %entry]
    br i1 %cond1, label %bb3, label %bb4
  bb2:
    ret void
  bb3:
    ret void
  bb4:
    ret void
  }
  )IR");
    Function *F = M->getFunction("crit_edge");
    DominatorTree DT(*F);
    LoopInfo LI(DT);
    BranchProbabilityInfo BPI(*F, LI);
    BlockFrequencyInfo BFI(*F, BPI, LI);
  
    ASSERT_TRUE(SplitIndirectBrCriticalEdges(*F, /*IgnoreBlocksWithoutPHI=*/true,
                                             &BPI, &BFI));
  
    // Check that successors of the split block get their probability correct.
    BasicBlock *BB1 = getBasicBlockByName(*F, "bb1");
    BasicBlock *SplitBB = BB1->getTerminator()->getSuccessor(0);
    ASSERT_EQ(2u, SplitBB->getTerminator()->getNumSuccessors());
    EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 0u));
    EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 1u));
  
    // bb2 has no PHI, so we shouldn't split bb0 -> bb2
    BasicBlock *BB0 = getBasicBlockByName(*F, "bb0");
    ASSERT_EQ(2u, BB0->getTerminator()->getNumSuccessors());
    EXPECT_EQ(BB0->getTerminator()->getSuccessor(1),
              getBasicBlockByName(*F, "bb2"));
  }
  
  TEST(BasicBlockUtils, SplitIndirectBrCriticalEdges) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define void @crit_edge(i8* %tgt, i1 %cond0, i1 %cond1) {
  entry:
    indirectbr i8* %tgt, [label %bb0, label %bb1, label %bb2]
  bb0:
    br i1 %cond0, label %bb1, label %bb2
  bb1:
    %p = phi i32 [0, %bb0], [0, %entry]
    br i1 %cond1, label %bb3, label %bb4
  bb2:
    ret void
  bb3:
    ret void
  bb4:
    ret void
  }
  )IR");
    Function *F = M->getFunction("crit_edge");
    DominatorTree DT(*F);
    LoopInfo LI(DT);
    BranchProbabilityInfo BPI(*F, LI);
    BlockFrequencyInfo BFI(*F, BPI, LI);
  
    ASSERT_TRUE(SplitIndirectBrCriticalEdges(*F, /*IgnoreBlocksWithoutPHI=*/false,
                                             &BPI, &BFI));
  
    // Check that successors of the split block get their probability correct.
    BasicBlock *BB1 = getBasicBlockByName(*F, "bb1");
    BasicBlock *SplitBB = BB1->getTerminator()->getSuccessor(0);
    ASSERT_EQ(2u, SplitBB->getTerminator()->getNumSuccessors());
    EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 0u));
    EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 1u));
  
    // Should split, resulting in:
    //   bb0 -> bb2.clone; bb2 -> split1; bb2.clone -> split,
    BasicBlock *BB0 = getBasicBlockByName(*F, "bb0");
    ASSERT_EQ(2u, BB0->getTerminator()->getNumSuccessors());
    BasicBlock *BB2Clone = BB0->getTerminator()->getSuccessor(1);
    BasicBlock *BB2 = getBasicBlockByName(*F, "bb2");
    EXPECT_NE(BB2Clone, BB2);
    ASSERT_EQ(1u, BB2->getTerminator()->getNumSuccessors());
    ASSERT_EQ(1u, BB2Clone->getTerminator()->getNumSuccessors());
    EXPECT_EQ(BB2->getTerminator()->getSuccessor(0),
              BB2Clone->getTerminator()->getSuccessor(0));
  }
  
  TEST(BasicBlockUtils, SetEdgeProbability) {
    LLVMContext C;
    std::unique_ptr<Module> M = parseIR(C, R"IR(
  define void @edge_probability(i32 %0) {
  entry:
  switch i32 %0, label %LD [
    i32 700, label %L0
    i32 701, label %L1
    i32 702, label %L2
    i32 703, label %L3
    i32 704, label %L4
    i32 705, label %L5
    i32 706, label %L6
    i32 707, label %L7
    i32 708, label %L8
    i32 709, label %L9
    i32 710, label %L10
    i32 711, label %L11
    i32 712, label %L12
    i32 713, label %L13
    i32 714, label %L14
    i32 715, label %L15
    i32 716, label %L16
    i32 717, label %L17
    i32 718, label %L18
    i32 719, label %L19
  ], !prof !{!"branch_weights", i32 1, i32 1, i32 1, i32 1, i32 1, i32 451, i32 1,
             i32 12, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1,
             i32 1, i32 1, i32 1, i32 1, i32 1}
  LD:
    unreachable
  L0:
    ret void
  L1:
    ret void
  L2:
    ret void
  L3:
    ret void
  L4:
    ret void
  L5:
    ret void
  L6:
    ret void
  L7:
    ret void
  L8:
    ret void
  L9:
    ret void
  L10:
    ret void
  L11:
    ret void
  L12:
    ret void
  L13:
    ret void
  L14:
    ret void
  L15:
    ret void
  L16:
    ret void
  L17:
    ret void
  L18:
    ret void
  L19:
    ret void
  }
  )IR");
    Function *F = M->getFunction("edge_probability");
    DominatorTree DT(*F);
    LoopInfo LI(DT);
    BranchProbabilityInfo BPI(*F, LI);
  
    // Check that the unreachable block has the minimal probability.
    const BasicBlock *EntryBB = getBasicBlockByName(*F, "entry");
    const BasicBlock *UnreachableBB = getBasicBlockByName(*F, "LD");
    EXPECT_EQ(BranchProbability::getRaw(1),
              BPI.getEdgeProbability(EntryBB, UnreachableBB));
  }
  