1//===- BranchProbabilityInfoTest.cpp - BranchProbabilityInfo unit tests ---===//
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#include "llvm/Analysis/BranchProbabilityInfo.h"
10#include "llvm/Analysis/LoopInfo.h"
11#include "llvm/AsmParser/Parser.h"
12#include "llvm/IR/BasicBlock.h"
13#include "llvm/IR/Constants.h"
14#include "llvm/IR/Dominators.h"
15#include "llvm/IR/Function.h"
16#include "llvm/IR/Instructions.h"
17#include "llvm/IR/LLVMContext.h"
18#include "llvm/IR/Module.h"
19#include "llvm/Support/DataTypes.h"
20#include "llvm/Support/SourceMgr.h"
21#include "llvm/Support/raw_ostream.h"
22#include "gtest/gtest.h"
23
24namespace llvm {
25namespace {
26
27struct BranchProbabilityInfoTest : public testing::Test {
28 std::unique_ptr<BranchProbabilityInfo> BPI;
29 std::unique_ptr<DominatorTree> DT;
30 std::unique_ptr<LoopInfo> LI;
31 LLVMContext C;
32
33 BranchProbabilityInfo &buildBPI(Function &F) {
34 DT.reset(p: new DominatorTree(F));
35 LI.reset(p: new LoopInfo(*DT));
36 BPI.reset(p: new BranchProbabilityInfo(F, *LI));
37 return *BPI;
38 }
39
40 std::unique_ptr<Module> makeLLVMModule() {
41 const char *ModuleString = "define void @f() { exit: ret void }\n";
42 SMDiagnostic Err;
43 return parseAssemblyString(AsmString: ModuleString, Err, Context&: C);
44 }
45};
46
47TEST_F(BranchProbabilityInfoTest, StressUnreachableHeuristic) {
48 auto M = makeLLVMModule();
49 Function *F = M->getFunction(Name: "f");
50
51 // define void @f() {
52 // entry:
53 // switch i32 undef, label %exit, [
54 // i32 0, label %preexit
55 // ... ;;< Add lots of cases to stress the heuristic.
56 // ]
57 // preexit:
58 // unreachable
59 // exit:
60 // ret void
61 // }
62
63 auto *ExitBB = &F->back();
64 auto *EntryBB = BasicBlock::Create(Context&: C, Name: "entry", Parent: F, /*insertBefore=*/InsertBefore: ExitBB);
65
66 auto *PreExitBB =
67 BasicBlock::Create(Context&: C, Name: "preexit", Parent: F, /*insertBefore=*/InsertBefore: ExitBB);
68 new UnreachableInst(C, PreExitBB);
69
70 unsigned NumCases = 4096;
71 auto *I32 = IntegerType::get(C, NumBits: 32);
72 auto *Undef = UndefValue::get(T: I32);
73 auto *Switch = SwitchInst::Create(Value: Undef, Default: ExitBB, NumCases, InsertAtEnd: EntryBB);
74 for (unsigned I = 0; I < NumCases; ++I)
75 Switch->addCase(OnVal: ConstantInt::get(Ty: I32, V: I), Dest: PreExitBB);
76
77 BranchProbabilityInfo &BPI = buildBPI(F&: *F);
78
79 // FIXME: This doesn't seem optimal. Since all of the cases handled by the
80 // switch have the *same* destination block ("preexit"), shouldn't it be the
81 // hot one? I'd expect the results to be reversed here...
82 EXPECT_FALSE(BPI.isEdgeHot(EntryBB, PreExitBB));
83 EXPECT_TRUE(BPI.isEdgeHot(EntryBB, ExitBB));
84}
85
86TEST_F(BranchProbabilityInfoTest, SwapProbabilities) {
87 StringRef Assembly = R"(
88 define void @f() {
89 entry:
90 br label %loop
91
92 loop:
93 %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
94 %iv.next = add i32 %iv, 1
95 %cond = icmp slt i32 %iv.next, 10
96 br i1 %cond, label %exit, label %loop
97
98 exit:
99 ret void
100 }
101 )";
102 LLVMContext Context;
103 SMDiagnostic Error;
104 auto M = parseAssemblyString(AsmString: Assembly, Err&: Error, Context);
105 ASSERT_TRUE(M) << "Bad assembly?";
106
107 Function *F = M->getFunction(Name: "f");
108 auto *LoopHeaderBB = F->front().getSingleSuccessor();
109 ASSERT_TRUE(LoopHeaderBB != nullptr);
110 BranchInst *Branch = dyn_cast<BranchInst>(Val: LoopHeaderBB->getTerminator());
111 ASSERT_TRUE(Branch != nullptr);
112 // Save the probabilities before successors swapping
113 BranchProbabilityInfo *BPI = &buildBPI(F&: *F);
114 auto ProbEdge0 = BPI->getEdgeProbability(Src: LoopHeaderBB, IndexInSuccessors: 0U);
115 auto ProbEdge1 = BPI->getEdgeProbability(Src: LoopHeaderBB, IndexInSuccessors: 1U);
116 EXPECT_LT(ProbEdge0, ProbEdge1);
117
118 Branch->swapSuccessors();
119 BPI->swapSuccEdgesProbabilities(Src: LoopHeaderBB);
120 // TODO: Check the probabilities are swapped as well as the edges
121 EXPECT_EQ(ProbEdge0, BPI->getEdgeProbability(LoopHeaderBB, 1U));
122 EXPECT_EQ(ProbEdge1, BPI->getEdgeProbability(LoopHeaderBB, 0U));
123}
124
125} // end anonymous namespace
126} // end namespace llvm
127

source code of llvm/unittests/Analysis/BranchProbabilityInfoTest.cpp