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