1 //===- BasicBlockUtils.cpp - Unit tests for BasicBlockUtils ---------------===//
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/Transforms/Utils/BasicBlockUtils.h"
10 #include "llvm/Analysis/BlockFrequencyInfo.h"
11 #include "llvm/Analysis/BranchProbabilityInfo.h"
12 #include "llvm/Analysis/LoopInfo.h"
13 #include "llvm/Analysis/PostDominators.h"
14 #include "llvm/AsmParser/Parser.h"
15 #include "llvm/IR/BasicBlock.h"
16 #include "llvm/IR/Dominators.h"
17 #include "llvm/IR/LLVMContext.h"
18 #include "llvm/Support/SourceMgr.h"
19 #include "gtest/gtest.h"
20
21 using namespace llvm;
22
parseIR(LLVMContext & C,const char * IR)23 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
24 SMDiagnostic Err;
25 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
26 if (!Mod)
27 Err.print("BasicBlockUtilsTests", errs());
28 return Mod;
29 }
30
TEST(BasicBlockUtils,EliminateUnreachableBlocks)31 TEST(BasicBlockUtils, EliminateUnreachableBlocks) {
32 LLVMContext C;
33
34 std::unique_ptr<Module> M = parseIR(
35 C,
36 "define i32 @has_unreachable(i1 %cond) {\n"
37 "entry:\n"
38 " br i1 %cond, label %bb0, label %bb1\n"
39 "bb0:\n"
40 " br label %bb1\n"
41 "bb1:\n"
42 " %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
43 " ret i32 %phi\n"
44 "bb2:\n"
45 " ret i32 42\n"
46 "}\n"
47 "\n"
48 );
49
50 auto *F = M->getFunction("has_unreachable");
51 DominatorTree DT(*F);
52 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
53
54 EXPECT_EQ(F->size(), (size_t)4);
55 bool Result = EliminateUnreachableBlocks(*F, &DTU);
56 EXPECT_TRUE(Result);
57 EXPECT_EQ(F->size(), (size_t)3);
58 EXPECT_TRUE(DT.verify());
59 }
60
TEST(BasicBlockUtils,NoUnreachableBlocksToEliminate)61 TEST(BasicBlockUtils, NoUnreachableBlocksToEliminate) {
62 LLVMContext C;
63
64 std::unique_ptr<Module> M = parseIR(
65 C,
66 "define i32 @no_unreachable(i1 %cond) {\n"
67 "entry:\n"
68 " br i1 %cond, label %bb0, label %bb1\n"
69 "bb0:\n"
70 " br label %bb1\n"
71 "bb1:\n"
72 " %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
73 " ret i32 %phi\n"
74 "}\n"
75 "\n"
76 );
77
78 auto *F = M->getFunction("no_unreachable");
79 DominatorTree DT(*F);
80 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
81
82 EXPECT_EQ(F->size(), (size_t)3);
83 bool Result = EliminateUnreachableBlocks(*F, &DTU);
84 EXPECT_FALSE(Result);
85 EXPECT_EQ(F->size(), (size_t)3);
86 EXPECT_TRUE(DT.verify());
87 }
88
TEST(BasicBlockUtils,SplitBlockPredecessors)89 TEST(BasicBlockUtils, SplitBlockPredecessors) {
90 LLVMContext C;
91
92 std::unique_ptr<Module> M = parseIR(
93 C,
94 "define i32 @basic_func(i1 %cond) {\n"
95 "entry:\n"
96 " br i1 %cond, label %bb0, label %bb1\n"
97 "bb0:\n"
98 " br label %bb1\n"
99 "bb1:\n"
100 " %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
101 " ret i32 %phi\n"
102 "}\n"
103 "\n"
104 );
105
106 auto *F = M->getFunction("basic_func");
107 DominatorTree DT(*F);
108
109 // Make sure the dominator tree is properly updated if calling this on the
110 // entry block.
111 SplitBlockPredecessors(&F->getEntryBlock(), {}, "split.entry", &DT);
112 EXPECT_TRUE(DT.verify());
113 }
114
TEST(BasicBlockUtils,SplitCriticalEdge)115 TEST(BasicBlockUtils, SplitCriticalEdge) {
116 LLVMContext C;
117
118 std::unique_ptr<Module> M = parseIR(
119 C,
120 "define void @crit_edge(i1 %cond0, i1 %cond1) {\n"
121 "entry:\n"
122 " br i1 %cond0, label %bb0, label %bb1\n"
123 "bb0:\n"
124 " br label %bb1\n"
125 "bb1:\n"
126 " br label %bb2\n"
127 "bb2:\n"
128 " ret void\n"
129 "}\n"
130 "\n"
131 );
132
133 auto *F = M->getFunction("crit_edge");
134 DominatorTree DT(*F);
135 PostDominatorTree PDT(*F);
136
137 CriticalEdgeSplittingOptions CESO(&DT, nullptr, nullptr, &PDT);
138 EXPECT_EQ(1u, SplitAllCriticalEdges(*F, CESO));
139 EXPECT_TRUE(DT.verify());
140 EXPECT_TRUE(PDT.verify());
141 }
142
TEST(BasicBlockUtils,SplitIndirectBrCriticalEdge)143 TEST(BasicBlockUtils, SplitIndirectBrCriticalEdge) {
144 LLVMContext C;
145
146 std::unique_ptr<Module> M =
147 parseIR(C, "define void @crit_edge(i8* %cond0, i1 %cond1) {\n"
148 "entry:\n"
149 " indirectbr i8* %cond0, [label %bb0, label %bb1]\n"
150 "bb0:\n"
151 " br label %bb1\n"
152 "bb1:\n"
153 " %p = phi i32 [0, %bb0], [0, %entry]\n"
154 " br i1 %cond1, label %bb2, label %bb3\n"
155 "bb2:\n"
156 " ret void\n"
157 "bb3:\n"
158 " ret void\n"
159 "}\n");
160
161 auto *F = M->getFunction("crit_edge");
162 DominatorTree DT(*F);
163 LoopInfo LI(DT);
164 BranchProbabilityInfo BPI(*F, LI);
165 BlockFrequencyInfo BFI(*F, BPI, LI);
166
167 auto Block = [&F](StringRef BBName) -> const BasicBlock & {
168 for (auto &BB : *F)
169 if (BB.getName() == BBName)
170 return BB;
171 llvm_unreachable("Block not found");
172 };
173
174 bool Split = SplitIndirectBrCriticalEdges(*F, &BPI, &BFI);
175
176 EXPECT_TRUE(Split);
177
178 // Check that successors of the split block get their probability correct.
179 BasicBlock *SplitBB = Block("bb1").getTerminator()->getSuccessor(0);
180 EXPECT_EQ(2u, SplitBB->getTerminator()->getNumSuccessors());
181 EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 0u));
182 EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 1u));
183 }
184
TEST(BasicBlockUtils,SetEdgeProbability)185 TEST(BasicBlockUtils, SetEdgeProbability) {
186 LLVMContext C;
187
188 std::unique_ptr<Module> M = parseIR(
189 C, "define void @edge_probability(i32 %0) {\n"
190 "entry:\n"
191 "switch i32 %0, label %LD [\n"
192 " i32 700, label %L0\n"
193 " i32 701, label %L1\n"
194 " i32 702, label %L2\n"
195 " i32 703, label %L3\n"
196 " i32 704, label %L4\n"
197 " i32 705, label %L5\n"
198 " i32 706, label %L6\n"
199 " i32 707, label %L7\n"
200 " i32 708, label %L8\n"
201 " i32 709, label %L9\n"
202 " i32 710, label %L10\n"
203 " i32 711, label %L11\n"
204 " i32 712, label %L12\n"
205 " i32 713, label %L13\n"
206 " i32 714, label %L14\n"
207 " i32 715, label %L15\n"
208 " i32 716, label %L16\n"
209 " i32 717, label %L17\n"
210 " i32 718, label %L18\n"
211 " i32 719, label %L19\n"
212 "], !prof !{!\"branch_weights\", i32 1, i32 1, i32 1, i32 1, i32 1, "
213 "i32 451, i32 1, i32 12, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, "
214 "i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1}\n"
215 "LD:\n"
216 " unreachable\n"
217 "L0:\n"
218 " ret void\n"
219 "L1:\n"
220 " ret void\n"
221 "L2:\n"
222 " ret void\n"
223 "L3:\n"
224 " ret void\n"
225 "L4:\n"
226 " ret void\n"
227 "L5:\n"
228 " ret void\n"
229 "L6:\n"
230 " ret void\n"
231 "L7:\n"
232 " ret void\n"
233 "L8:\n"
234 " ret void\n"
235 "L9:\n"
236 " ret void\n"
237 "L10:\n"
238 " ret void\n"
239 "L11:\n"
240 " ret void\n"
241 "L12:\n"
242 " ret void\n"
243 "L13:\n"
244 " ret void\n"
245 "L14:\n"
246 " ret void\n"
247 "L15:\n"
248 " ret void\n"
249 "L16:\n"
250 " ret void\n"
251 "L17:\n"
252 " ret void\n"
253 "L18:\n"
254 " ret void\n"
255 "L19:\n"
256 " ret void\n"
257 "}\n");
258
259 auto *F = M->getFunction("edge_probability");
260 DominatorTree DT(*F);
261 LoopInfo LI(DT);
262 BranchProbabilityInfo BPI(*F, LI);
263
264 auto Block = [&F](StringRef BBName) -> const BasicBlock & {
265 for (auto &BB : *F)
266 if (BB.getName() == BBName)
267 return BB;
268 llvm_unreachable("Block not found");
269 };
270
271 // Check that the unreachable block has the minimal probability.
272 const BasicBlock &EntryBB = Block("entry");
273 const BasicBlock &UnreachableBB = Block("LD");
274 EXPECT_EQ(BranchProbability::getRaw(1),
275 BPI.getEdgeProbability(&EntryBB, &UnreachableBB));
276 }
277