//===- 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/DomTreeUpdater.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));
}