nils.hoelscher
/
llvm-for-llvmta
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
llvm-for-llvmta/unittests/Transforms/Utils/BasicBlockUtilsTest.cpp

507 lines
15 KiB
C++
Raw Permalink Blame History

//===- 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/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 "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,
"define i32 @has_unreachable(i1 %cond) {\n"
"entry:\n"
" br i1 %cond, label %bb0, label %bb1\n"
"bb0:\n"
" br label %bb1\n"
"bb1:\n"
" %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
" ret i32 %phi\n"
"bb2:\n"
" ret i32 42\n"
"}\n"
"\n"
);
auto *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, "define void @foo(i1 %cond0) {\n"
"entry:\n"
" br i1 %cond0, label %bb0, label %bb1\n"
"bb0:\n"
" %0 = mul i32 1, 2\n"
" br label %bb1\n"
"bb1:\n"
" br label %bb2\n"
"bb2:\n"
" ret void\n"
"}\n"
"\n");
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, "define void @foo() {\n"
"bb0:\n"
" br label %bb2\n"
"bb1:\n"
" br label %bb2\n"
"bb2:\n"
" ret void\n"
"}\n"
"\n");
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, "define i32 @foo(i32 %n) {\n"
"entry:\n"
" br label %header\n"
"header:\n"
" %sum.02 = phi i32 [ 0, %entry ], [ %sum.1, %bb3 ]\n"
" %0 = phi i32 [ 0, %entry ], [ %4, %bb3 ] \n"
" %1 = icmp slt i32 %0, %n \n"
" br i1 %1, label %bb0, label %bb1\n"
"bb0:\n"
" %2 = add nsw i32 %sum.02, 2\n"
" br label %bb2\n"
"bb1:\n"
" %3 = add nsw i32 %sum.02, 1\n"
" br label %bb2\n"
"bb2:\n"
" %sum.1 = phi i32 [ %2, %bb0 ], [ %3, %bb1 ]\n"
" br label %bb3\n"
"bb3:\n"
" %4 = add nsw i32 %0, 1 \n"
" %5 = icmp slt i32 %4, 100\n"
" br i1 %5, label %header, label %bb4\n"
"bb4:\n"
" %sum.0.lcssa = phi i32 [ %sum.1, %bb3 ]\n"
" ret i32 %sum.0.lcssa\n"
"}\n"
"\n");
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, splitBasicBlockBefore_ex1) {
LLVMContext C;
std::unique_ptr<Module> M = parseIR(C, "define void @foo() {\n"
"bb0:\n"
" %0 = mul i32 1, 2\n"
" br label %bb2\n"
"bb1:\n"
" br label %bb3\n"
"bb2:\n"
" %1 = phi i32 [ %0, %bb0 ]\n"
" br label %bb3\n"
"bb3:\n"
" ret void\n"
"}\n"
"\n");
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, "define void @foo() {\n"
"bb0:\n"
" %0 = mul i32 1, 2\n"
" br label %bb2\n"
"bb1:\n"
" br label %bb2\n"
"bb2:\n"
" %1 = phi i32 [ %0, %bb0 ], [ 1, %bb1 ]\n"
" br label %bb3\n"
"bb3:\n"
" ret void\n"
"}\n"
"\n");
Function *F = M->getFunction("foo");
DominatorTree DT(*F);
BasicBlock *DestBlock;
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,
"define i32 @no_unreachable(i1 %cond) {\n"
"entry:\n"
" br i1 %cond, label %bb0, label %bb1\n"
"bb0:\n"
" br label %bb1\n"
"bb1:\n"
" %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
" ret i32 %phi\n"
"}\n"
"\n"
);
auto *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,
"define i32 @basic_func(i1 %cond) {\n"
"entry:\n"
" br i1 %cond, label %bb0, label %bb1\n"
"bb0:\n"
" br label %bb1\n"
"bb1:\n"
" %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
" ret i32 %phi\n"
"}\n"
"\n"
);
auto *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,
"define void @crit_edge(i1 %cond0, i1 %cond1) {\n"
"entry:\n"
" br i1 %cond0, label %bb0, label %bb1\n"
"bb0:\n"
" br label %bb1\n"
"bb1:\n"
" br label %bb2\n"
"bb2:\n"
" ret void\n"
"}\n"
"\n"
);
auto *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, SplitIndirectBrCriticalEdge) {
LLVMContext C;
std::unique_ptr<Module> M =
parseIR(C, "define void @crit_edge(i8* %cond0, i1 %cond1) {\n"
"entry:\n"
" indirectbr i8* %cond0, [label %bb0, label %bb1]\n"
"bb0:\n"
" br label %bb1\n"
"bb1:\n"
" %p = phi i32 [0, %bb0], [0, %entry]\n"
" br i1 %cond1, label %bb2, label %bb3\n"
"bb2:\n"
" ret void\n"
"bb3:\n"
" ret void\n"
"}\n");
auto *F = M->getFunction("crit_edge");
DominatorTree DT(*F);
LoopInfo LI(DT);
BranchProbabilityInfo BPI(*F, LI);
BlockFrequencyInfo BFI(*F, BPI, LI);
auto Block = [&F](StringRef BBName) -> const BasicBlock & {
for (auto &BB : *F)
if (BB.getName() == BBName)
return BB;
llvm_unreachable("Block not found");
};
bool Split = SplitIndirectBrCriticalEdges(*F, &BPI, &BFI);
EXPECT_TRUE(Split);
// Check that successors of the split block get their probability correct.
BasicBlock *SplitBB = Block("bb1").getTerminator()->getSuccessor(0);
EXPECT_EQ(2u, SplitBB->getTerminator()->getNumSuccessors());
EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 0u));
EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 1u));
}
TEST(BasicBlockUtils, SetEdgeProbability) {
LLVMContext C;
std::unique_ptr<Module> M = parseIR(
C, "define void @edge_probability(i32 %0) {\n"
"entry:\n"
"switch i32 %0, label %LD [\n"
" i32 700, label %L0\n"
" i32 701, label %L1\n"
" i32 702, label %L2\n"
" i32 703, label %L3\n"
" i32 704, label %L4\n"
" i32 705, label %L5\n"
" i32 706, label %L6\n"
" i32 707, label %L7\n"
" i32 708, label %L8\n"
" i32 709, label %L9\n"
" i32 710, label %L10\n"
" i32 711, label %L11\n"
" i32 712, label %L12\n"
" i32 713, label %L13\n"
" i32 714, label %L14\n"
" i32 715, label %L15\n"
" i32 716, label %L16\n"
" i32 717, label %L17\n"
" i32 718, label %L18\n"
" i32 719, label %L19\n"
"], !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}\n"
"LD:\n"
" unreachable\n"
"L0:\n"
" ret void\n"
"L1:\n"
" ret void\n"
"L2:\n"
" ret void\n"
"L3:\n"
" ret void\n"
"L4:\n"
" ret void\n"
"L5:\n"
" ret void\n"
"L6:\n"
" ret void\n"
"L7:\n"
" ret void\n"
"L8:\n"
" ret void\n"
"L9:\n"
" ret void\n"
"L10:\n"
" ret void\n"
"L11:\n"
" ret void\n"
"L12:\n"
" ret void\n"
"L13:\n"
" ret void\n"
"L14:\n"
" ret void\n"
"L15:\n"
" ret void\n"
"L16:\n"
" ret void\n"
"L17:\n"
" ret void\n"
"L18:\n"
" ret void\n"
"L19:\n"
" ret void\n"
"}\n");
auto *F = M->getFunction("edge_probability");
DominatorTree DT(*F);
LoopInfo LI(DT);
BranchProbabilityInfo BPI(*F, LI);
auto Block = [&F](StringRef BBName) -> const BasicBlock & {
for (auto &BB : *F)
if (BB.getName() == BBName)
return BB;
llvm_unreachable("Block not found");
};
// Check that the unreachable block has the minimal probability.
const BasicBlock &EntryBB = Block("entry");
const BasicBlock &UnreachableBB = Block("LD");
EXPECT_EQ(BranchProbability::getRaw(1),
BPI.getEdgeProbability(&EntryBB, &UnreachableBB));
}
Reference in New Issue View Git Blame Copy Permalink