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 | |
24 | namespace llvm { |
25 | namespace { |
26 | |
27 | struct 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 | |
47 | TEST_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 | |
86 | TEST_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 * = 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 | |