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/AssumptionCache.h"
11 #include "llvm/Analysis/BasicAliasAnalysis.h"
12 #include "llvm/Analysis/BlockFrequencyInfo.h"
13 #include "llvm/Analysis/BranchProbabilityInfo.h"
14 #include "llvm/Analysis/LoopInfo.h"
15 #include "llvm/Analysis/MemorySSA.h"
16 #include "llvm/Analysis/MemorySSAUpdater.h"
17 #include "llvm/Analysis/PostDominators.h"
18 #include "llvm/Analysis/TargetLibraryInfo.h"
19 #include "llvm/AsmParser/Parser.h"
20 #include "llvm/IR/BasicBlock.h"
21 #include "llvm/IR/Dominators.h"
22 #include "llvm/IR/LLVMContext.h"
23 #include "llvm/Support/SourceMgr.h"
24 #include "gtest/gtest.h"
25 
26 using namespace llvm;
27 
28 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
29   SMDiagnostic Err;
30   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
31   if (!Mod)
32     Err.print("BasicBlockUtilsTests", errs());
33   return Mod;
34 }
35 
36 static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) {
37   for (BasicBlock &BB : F)
38     if (BB.getName() == Name)
39       return &BB;
40   llvm_unreachable("Expected to find basic block!");
41 }
42 
43 TEST(BasicBlockUtils, EliminateUnreachableBlocks) {
44   LLVMContext C;
45 
46   std::unique_ptr<Module> M = parseIR(
47     C,
48     "define i32 @has_unreachable(i1 %cond) {\n"
49     "entry:\n"
50     "  br i1 %cond, label %bb0, label %bb1\n"
51     "bb0:\n"
52     "  br label %bb1\n"
53     "bb1:\n"
54     "  %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
55     "  ret i32 %phi\n"
56     "bb2:\n"
57     "  ret i32 42\n"
58     "}\n"
59     "\n"
60     );
61 
62   auto *F = M->getFunction("has_unreachable");
63   DominatorTree DT(*F);
64   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
65 
66   EXPECT_EQ(F->size(), (size_t)4);
67   bool Result = EliminateUnreachableBlocks(*F, &DTU);
68   EXPECT_TRUE(Result);
69   EXPECT_EQ(F->size(), (size_t)3);
70   EXPECT_TRUE(DT.verify());
71 }
72 
73 TEST(BasicBlockUtils, SplitEdge_ex1) {
74   LLVMContext C;
75   std::unique_ptr<Module> M =
76       parseIR(C, "define void @foo(i1 %cond0) {\n"
77                  "entry:\n"
78                  "  br i1 %cond0, label %bb0, label %bb1\n"
79                  "bb0:\n"
80                  " %0 = mul i32 1, 2\n"
81                  "  br label %bb1\n"
82                  "bb1:\n"
83                  "  br label %bb2\n"
84                  "bb2:\n"
85                  "  ret void\n"
86                  "}\n"
87                  "\n");
88 
89   Function *F = M->getFunction("foo");
90   DominatorTree DT(*F);
91   BasicBlock *SrcBlock;
92   BasicBlock *DestBlock;
93   BasicBlock *NewBB;
94 
95   SrcBlock = getBasicBlockByName(*F, "entry");
96   DestBlock = getBasicBlockByName(*F, "bb0");
97   NewBB = SplitEdge(SrcBlock, DestBlock, &DT, nullptr, nullptr);
98 
99   EXPECT_TRUE(DT.verify());
100   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
101   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
102   EXPECT_EQ(NewBB->getParent(), F);
103 
104   bool BBFlag = false;
105   for (BasicBlock &BB : *F) {
106     if (BB.getName() == NewBB->getName()) {
107       BBFlag = true;
108     }
109   }
110   EXPECT_TRUE(BBFlag);
111 }
112 
113 TEST(BasicBlockUtils, SplitEdge_ex2) {
114   LLVMContext C;
115   std::unique_ptr<Module> M = parseIR(C, "define void @foo() {\n"
116                                          "bb0:\n"
117                                          "  br label %bb2\n"
118                                          "bb1:\n"
119                                          "  br label %bb2\n"
120                                          "bb2:\n"
121                                          "  ret void\n"
122                                          "}\n"
123                                          "\n");
124 
125   Function *F = M->getFunction("foo");
126   DominatorTree DT(*F);
127 
128   BasicBlock *SrcBlock;
129   BasicBlock *DestBlock;
130   BasicBlock *NewBB;
131 
132   SrcBlock = getBasicBlockByName(*F, "bb0");
133   DestBlock = getBasicBlockByName(*F, "bb2");
134   NewBB = SplitEdge(SrcBlock, DestBlock, &DT, nullptr, nullptr);
135 
136   EXPECT_TRUE(DT.verify());
137   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
138   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
139   EXPECT_EQ(NewBB->getParent(), F);
140 
141   bool BBFlag = false;
142   for (BasicBlock &BB : *F) {
143     if (BB.getName() == NewBB->getName()) {
144       BBFlag = true;
145     }
146   }
147   EXPECT_TRUE(BBFlag);
148 }
149 
150 TEST(BasicBlockUtils, SplitEdge_ex3) {
151   LLVMContext C;
152   std::unique_ptr<Module> M =
153       parseIR(C, "define i32 @foo(i32 %n) {\n"
154                  "entry:\n"
155                  " br label %header\n"
156                  "header:\n"
157                  " %sum.02 = phi i32 [ 0, %entry ], [ %sum.1, %bb3 ]\n"
158                  " %0 = phi i32 [ 0, %entry ], [ %4, %bb3 ] \n"
159                  " %1 = icmp slt i32 %0, %n \n"
160                  " br i1 %1, label %bb0, label %bb1\n"
161                  "bb0:\n"
162                  "  %2 = add nsw i32 %sum.02, 2\n"
163                  "  br label %bb2\n"
164                  "bb1:\n"
165                  "  %3 = add nsw i32 %sum.02, 1\n"
166                  "  br label %bb2\n"
167                  "bb2:\n"
168                  "  %sum.1 = phi i32 [ %2, %bb0 ], [ %3, %bb1 ]\n"
169                  "  br label %bb3\n"
170                  "bb3:\n"
171                  "  %4 = add nsw i32 %0, 1 \n"
172                  "  %5 = icmp slt i32 %4, 100\n"
173                  "  br i1 %5, label %header, label %bb4\n"
174                  "bb4:\n"
175                  " %sum.0.lcssa = phi i32 [ %sum.1, %bb3 ]\n"
176                  " ret i32 %sum.0.lcssa\n"
177                  "}\n"
178                  "\n");
179 
180   Function *F = M->getFunction("foo");
181   DominatorTree DT(*F);
182 
183   LoopInfo LI(DT);
184 
185   DataLayout DL("e-i64:64-f80:128-n8:16:32:64-S128");
186   TargetLibraryInfoImpl TLII;
187   TargetLibraryInfo TLI(TLII);
188   AssumptionCache AC(*F);
189   AAResults AA(TLI);
190 
191   BasicAAResult BAA(DL, *F, TLI, AC, &DT);
192   AA.addAAResult(BAA);
193 
194   MemorySSA MSSA(*F, &AA, &DT);
195   MemorySSAUpdater Updater(&MSSA);
196 
197   BasicBlock *SrcBlock;
198   BasicBlock *DestBlock;
199   BasicBlock *NewBB;
200 
201   SrcBlock = getBasicBlockByName(*F, "header");
202   DestBlock = getBasicBlockByName(*F, "bb0");
203   NewBB = SplitEdge(SrcBlock, DestBlock, &DT, &LI, &Updater);
204 
205   Updater.getMemorySSA()->verifyMemorySSA();
206   EXPECT_TRUE(DT.verify());
207   EXPECT_NE(LI.getLoopFor(SrcBlock), nullptr);
208   EXPECT_NE(LI.getLoopFor(DestBlock), nullptr);
209   EXPECT_NE(LI.getLoopFor(NewBB), nullptr);
210   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
211   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
212   EXPECT_EQ(NewBB->getParent(), F);
213 
214   bool BBFlag = false;
215   for (BasicBlock &BB : *F) {
216     if (BB.getName() == NewBB->getName()) {
217       BBFlag = true;
218     }
219   }
220   EXPECT_TRUE(BBFlag);
221 }
222 
223 TEST(BasicBlockUtils, splitBasicBlockBefore_ex1) {
224   LLVMContext C;
225   std::unique_ptr<Module> M = parseIR(C, "define void @foo() {\n"
226                                          "bb0:\n"
227                                          " %0 = mul i32 1, 2\n"
228                                          "  br label %bb2\n"
229                                          "bb1:\n"
230                                          "  br label %bb3\n"
231                                          "bb2:\n"
232                                          "  %1 = phi  i32 [ %0, %bb0 ]\n"
233                                          "  br label %bb3\n"
234                                          "bb3:\n"
235                                          "  ret void\n"
236                                          "}\n"
237                                          "\n");
238 
239   Function *F = M->getFunction("foo");
240   DominatorTree DT(*F);
241 
242   BasicBlock *DestBlock;
243   BasicBlock *NewBB;
244 
245   DestBlock = getBasicBlockByName(*F, "bb2");
246 
247   NewBB = DestBlock->splitBasicBlockBefore(DestBlock->front().getIterator(),
248                                            "test");
249 
250   PHINode *PN = dyn_cast<PHINode>(&(DestBlock->front()));
251   EXPECT_EQ(PN->getIncomingBlock(0), NewBB);
252   EXPECT_EQ(NewBB->getName(), "test");
253   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
254   EXPECT_EQ(DestBlock->getSinglePredecessor(), NewBB);
255 }
256 
257 #ifndef NDEBUG
258 TEST(BasicBlockUtils, splitBasicBlockBefore_ex2) {
259   LLVMContext C;
260   std::unique_ptr<Module> M =
261       parseIR(C, "define void @foo() {\n"
262                  "bb0:\n"
263                  " %0 = mul i32 1, 2\n"
264                  "  br label %bb2\n"
265                  "bb1:\n"
266                  "  br label %bb2\n"
267                  "bb2:\n"
268                  "  %1 = phi  i32 [ %0, %bb0 ], [ 1, %bb1 ]\n"
269                  "  br label %bb3\n"
270                  "bb3:\n"
271                  "  ret void\n"
272                  "}\n"
273                  "\n");
274 
275   Function *F = M->getFunction("foo");
276   DominatorTree DT(*F);
277 
278   BasicBlock *DestBlock;
279 
280   DestBlock = getBasicBlockByName(*F, "bb2");
281 
282   ASSERT_DEATH(
283       {
284         DestBlock->splitBasicBlockBefore(DestBlock->front().getIterator(),
285                                          "test");
286       },
287       "cannot split on multi incoming phis");
288 }
289 #endif
290 
291 TEST(BasicBlockUtils, NoUnreachableBlocksToEliminate) {
292   LLVMContext C;
293 
294   std::unique_ptr<Module> M = parseIR(
295     C,
296     "define i32 @no_unreachable(i1 %cond) {\n"
297     "entry:\n"
298     "  br i1 %cond, label %bb0, label %bb1\n"
299     "bb0:\n"
300     "  br label %bb1\n"
301     "bb1:\n"
302     "  %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
303     "  ret i32 %phi\n"
304     "}\n"
305     "\n"
306     );
307 
308   auto *F = M->getFunction("no_unreachable");
309   DominatorTree DT(*F);
310   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
311 
312   EXPECT_EQ(F->size(), (size_t)3);
313   bool Result = EliminateUnreachableBlocks(*F, &DTU);
314   EXPECT_FALSE(Result);
315   EXPECT_EQ(F->size(), (size_t)3);
316   EXPECT_TRUE(DT.verify());
317 }
318 
319 TEST(BasicBlockUtils, SplitBlockPredecessors) {
320   LLVMContext C;
321 
322   std::unique_ptr<Module> M = parseIR(
323     C,
324     "define i32 @basic_func(i1 %cond) {\n"
325     "entry:\n"
326     "  br i1 %cond, label %bb0, label %bb1\n"
327     "bb0:\n"
328     "  br label %bb1\n"
329     "bb1:\n"
330     "  %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]"
331     "  ret i32 %phi\n"
332     "}\n"
333     "\n"
334     );
335 
336   auto *F = M->getFunction("basic_func");
337   DominatorTree DT(*F);
338 
339   // Make sure the dominator tree is properly updated if calling this on the
340   // entry block.
341   SplitBlockPredecessors(&F->getEntryBlock(), {}, "split.entry", &DT);
342   EXPECT_TRUE(DT.verify());
343 }
344 
345 TEST(BasicBlockUtils, SplitCriticalEdge) {
346   LLVMContext C;
347 
348   std::unique_ptr<Module> M = parseIR(
349     C,
350     "define void @crit_edge(i1 %cond0, i1 %cond1) {\n"
351     "entry:\n"
352     "  br i1 %cond0, label %bb0, label %bb1\n"
353     "bb0:\n"
354     "  br label %bb1\n"
355     "bb1:\n"
356     "  br label %bb2\n"
357     "bb2:\n"
358     "  ret void\n"
359     "}\n"
360     "\n"
361     );
362 
363   auto *F = M->getFunction("crit_edge");
364   DominatorTree DT(*F);
365   PostDominatorTree PDT(*F);
366 
367   CriticalEdgeSplittingOptions CESO(&DT, nullptr, nullptr, &PDT);
368   EXPECT_EQ(1u, SplitAllCriticalEdges(*F, CESO));
369   EXPECT_TRUE(DT.verify());
370   EXPECT_TRUE(PDT.verify());
371 }
372 
373 TEST(BasicBlockUtils, SplitIndirectBrCriticalEdge) {
374   LLVMContext C;
375 
376   std::unique_ptr<Module> M =
377       parseIR(C, "define void @crit_edge(i8* %cond0, i1 %cond1) {\n"
378                  "entry:\n"
379                  "  indirectbr i8* %cond0, [label %bb0, label %bb1]\n"
380                  "bb0:\n"
381                  "  br label %bb1\n"
382                  "bb1:\n"
383                  "  %p = phi i32 [0, %bb0], [0, %entry]\n"
384                  "  br i1 %cond1, label %bb2, label %bb3\n"
385                  "bb2:\n"
386                  "  ret void\n"
387                  "bb3:\n"
388                  "  ret void\n"
389                  "}\n");
390 
391   auto *F = M->getFunction("crit_edge");
392   DominatorTree DT(*F);
393   LoopInfo LI(DT);
394   BranchProbabilityInfo BPI(*F, LI);
395   BlockFrequencyInfo BFI(*F, BPI, LI);
396 
397   auto Block = [&F](StringRef BBName) -> const BasicBlock & {
398     for (auto &BB : *F)
399       if (BB.getName() == BBName)
400         return BB;
401     llvm_unreachable("Block not found");
402   };
403 
404   bool Split = SplitIndirectBrCriticalEdges(*F, &BPI, &BFI);
405 
406   EXPECT_TRUE(Split);
407 
408   // Check that successors of the split block get their probability correct.
409   BasicBlock *SplitBB = Block("bb1").getTerminator()->getSuccessor(0);
410   EXPECT_EQ(2u, SplitBB->getTerminator()->getNumSuccessors());
411   EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 0u));
412   EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 1u));
413 }
414 
415 TEST(BasicBlockUtils, SetEdgeProbability) {
416   LLVMContext C;
417 
418   std::unique_ptr<Module> M = parseIR(
419       C, "define void @edge_probability(i32 %0) {\n"
420          "entry:\n"
421          "switch i32 %0, label %LD [\n"
422          "  i32 700, label %L0\n"
423          "  i32 701, label %L1\n"
424          "  i32 702, label %L2\n"
425          "  i32 703, label %L3\n"
426          "  i32 704, label %L4\n"
427          "  i32 705, label %L5\n"
428          "  i32 706, label %L6\n"
429          "  i32 707, label %L7\n"
430          "  i32 708, label %L8\n"
431          "  i32 709, label %L9\n"
432          "  i32 710, label %L10\n"
433          "  i32 711, label %L11\n"
434          "  i32 712, label %L12\n"
435          "  i32 713, label %L13\n"
436          "  i32 714, label %L14\n"
437          "  i32 715, label %L15\n"
438          "  i32 716, label %L16\n"
439          "  i32 717, label %L17\n"
440          "  i32 718, label %L18\n"
441          "  i32 719, label %L19\n"
442          "], !prof !{!\"branch_weights\", i32 1, i32 1, i32 1, i32 1, i32 1, "
443          "i32 451, i32 1, i32 12, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, "
444          "i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1}\n"
445          "LD:\n"
446          "  unreachable\n"
447          "L0:\n"
448          "  ret void\n"
449          "L1:\n"
450          "  ret void\n"
451          "L2:\n"
452          "  ret void\n"
453          "L3:\n"
454          "  ret void\n"
455          "L4:\n"
456          "  ret void\n"
457          "L5:\n"
458          "  ret void\n"
459          "L6:\n"
460          "  ret void\n"
461          "L7:\n"
462          "  ret void\n"
463          "L8:\n"
464          "  ret void\n"
465          "L9:\n"
466          "  ret void\n"
467          "L10:\n"
468          "  ret void\n"
469          "L11:\n"
470          "  ret void\n"
471          "L12:\n"
472          "  ret void\n"
473          "L13:\n"
474          "  ret void\n"
475          "L14:\n"
476          "  ret void\n"
477          "L15:\n"
478          "  ret void\n"
479          "L16:\n"
480          "  ret void\n"
481          "L17:\n"
482          "  ret void\n"
483          "L18:\n"
484          "  ret void\n"
485          "L19:\n"
486          "  ret void\n"
487          "}\n");
488 
489   auto *F = M->getFunction("edge_probability");
490   DominatorTree DT(*F);
491   LoopInfo LI(DT);
492   BranchProbabilityInfo BPI(*F, LI);
493 
494   auto Block = [&F](StringRef BBName) -> const BasicBlock & {
495     for (auto &BB : *F)
496       if (BB.getName() == BBName)
497         return BB;
498     llvm_unreachable("Block not found");
499   };
500 
501   // Check that the unreachable block has the minimal probability.
502   const BasicBlock &EntryBB = Block("entry");
503   const BasicBlock &UnreachableBB = Block("LD");
504   EXPECT_EQ(BranchProbability::getRaw(1),
505             BPI.getEdgeProbability(&EntryBB, &UnreachableBB));
506 }
507