xref: /llvm-project/llvm/unittests/Transforms/Utils/BasicBlockUtilsTest.cpp (revision a494ae43bef09c8d0f6a6a98e92f3a89758247d5) 
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/CFG.h"
15 #include "llvm/Analysis/DomTreeUpdater.h"
16 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/Analysis/MemorySSA.h"
18 #include "llvm/Analysis/MemorySSAUpdater.h"
19 #include "llvm/Analysis/PostDominators.h"
20 #include "llvm/Analysis/TargetLibraryInfo.h"
21 #include "llvm/AsmParser/Parser.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/Dominators.h"
24 #include "llvm/IR/LLVMContext.h"
25 #include "llvm/Support/SourceMgr.h"
26 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
27 #include "gtest/gtest.h"
28 
29 using namespace llvm;
30 
31 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
32   SMDiagnostic Err;
33   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
34   if (!Mod)
35     Err.print("BasicBlockUtilsTests", errs());
36   return Mod;
37 }
38 
39 static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) {
40   for (BasicBlock &BB : F)
41     if (BB.getName() == Name)
42       return &BB;
43   llvm_unreachable("Expected to find basic block!");
44 }
45 
46 TEST(BasicBlockUtils, EliminateUnreachableBlocks) {
47   LLVMContext C;
48   std::unique_ptr<Module> M = parseIR(C, R"IR(
49 define i32 @has_unreachable(i1 %cond) {
50 entry:
51   br i1 %cond, label %bb0, label %bb1
52 bb0:
53   br label %bb1
54 bb1:
55   %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]
56   ret i32 %phi
57 bb2:
58   ret i32 42
59 }
60 )IR");
61   Function *F = M->getFunction("has_unreachable");
62   DominatorTree DT(*F);
63   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
64 
65   EXPECT_EQ(F->size(), (size_t)4);
66   bool Result = EliminateUnreachableBlocks(*F, &DTU);
67   EXPECT_TRUE(Result);
68   EXPECT_EQ(F->size(), (size_t)3);
69   EXPECT_TRUE(DT.verify());
70 }
71 
72 TEST(BasicBlockUtils, SplitEdge_ex1) {
73   LLVMContext C;
74   std::unique_ptr<Module> M = parseIR(C, R"IR(
75 define void @foo(i1 %cond0) {
76 entry:
77   br i1 %cond0, label %bb0, label %bb1
78 bb0:
79  %0 = mul i32 1, 2
80   br label %bb1
81 bb1:
82   br label %bb2
83 bb2:
84   ret void
85 }
86 )IR");
87   Function *F = M->getFunction("foo");
88   DominatorTree DT(*F);
89   BasicBlock *SrcBlock;
90   BasicBlock *DestBlock;
91   BasicBlock *NewBB;
92 
93   SrcBlock = getBasicBlockByName(*F, "entry");
94   DestBlock = getBasicBlockByName(*F, "bb0");
95   NewBB = SplitEdge(SrcBlock, DestBlock, &DT, nullptr, nullptr);
96 
97   EXPECT_TRUE(DT.verify());
98   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
99   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
100   EXPECT_EQ(NewBB->getParent(), F);
101 
102   bool BBFlag = false;
103   for (BasicBlock &BB : *F) {
104     if (BB.getName() == NewBB->getName()) {
105       BBFlag = true;
106     }
107   }
108   EXPECT_TRUE(BBFlag);
109 }
110 
111 TEST(BasicBlockUtils, SplitEdge_ex2) {
112   LLVMContext C;
113   std::unique_ptr<Module> M = parseIR(C, R"IR(
114 define void @foo() {
115 bb0:
116   br label %bb2
117 bb1:
118   br label %bb2
119 bb2:
120   ret void
121 }
122 )IR");
123   Function *F = M->getFunction("foo");
124   DominatorTree DT(*F);
125 
126   BasicBlock *SrcBlock;
127   BasicBlock *DestBlock;
128   BasicBlock *NewBB;
129 
130   SrcBlock = getBasicBlockByName(*F, "bb0");
131   DestBlock = getBasicBlockByName(*F, "bb2");
132   NewBB = SplitEdge(SrcBlock, DestBlock, &DT, nullptr, nullptr);
133 
134   EXPECT_TRUE(DT.verify());
135   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
136   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
137   EXPECT_EQ(NewBB->getParent(), F);
138 
139   bool BBFlag = false;
140   for (BasicBlock &BB : *F) {
141     if (BB.getName() == NewBB->getName()) {
142       BBFlag = true;
143     }
144   }
145   EXPECT_TRUE(BBFlag);
146 }
147 
148 TEST(BasicBlockUtils, SplitEdge_ex3) {
149   LLVMContext C;
150   std::unique_ptr<Module> M = parseIR(C, R"IR(
151 define i32 @foo(i32 %n) {
152 entry:
153  br label %header
154 header:
155  %sum.02 = phi i32 [ 0, %entry ], [ %sum.1, %bb3 ]
156  %0 = phi i32 [ 0, %entry ], [ %4, %bb3 ]
157  %1 = icmp slt i32 %0, %n
158  br i1 %1, label %bb0, label %bb1
159 bb0:
160   %2 = add nsw i32 %sum.02, 2
161   br label %bb2
162 bb1:
163   %3 = add nsw i32 %sum.02, 1
164   br label %bb2
165 bb2:
166   %sum.1 = phi i32 [ %2, %bb0 ], [ %3, %bb1 ]
167   br label %bb3
168 bb3:
169   %4 = add nsw i32 %0, 1
170   %5 = icmp slt i32 %4, 100
171   br i1 %5, label %header, label %bb4
172 bb4:
173  %sum.0.lcssa = phi i32 [ %sum.1, %bb3 ]
174  ret i32 %sum.0.lcssa
175 }
176 )IR");
177   Function *F = M->getFunction("foo");
178   DominatorTree DT(*F);
179 
180   LoopInfo LI(DT);
181 
182   DataLayout DL("e-i64:64-f80:128-n8:16:32:64-S128");
183   TargetLibraryInfoImpl TLII;
184   TargetLibraryInfo TLI(TLII);
185   AssumptionCache AC(*F);
186   AAResults AA(TLI);
187 
188   BasicAAResult BAA(DL, *F, TLI, AC, &DT);
189   AA.addAAResult(BAA);
190 
191   MemorySSA MSSA(*F, &AA, &DT);
192   MemorySSAUpdater Updater(&MSSA);
193 
194   BasicBlock *SrcBlock;
195   BasicBlock *DestBlock;
196   BasicBlock *NewBB;
197 
198   SrcBlock = getBasicBlockByName(*F, "header");
199   DestBlock = getBasicBlockByName(*F, "bb0");
200   NewBB = SplitEdge(SrcBlock, DestBlock, &DT, &LI, &Updater);
201 
202   Updater.getMemorySSA()->verifyMemorySSA();
203   EXPECT_TRUE(DT.verify());
204   EXPECT_NE(LI.getLoopFor(SrcBlock), nullptr);
205   EXPECT_NE(LI.getLoopFor(DestBlock), nullptr);
206   EXPECT_NE(LI.getLoopFor(NewBB), nullptr);
207   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
208   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
209   EXPECT_EQ(NewBB->getParent(), F);
210 
211   bool BBFlag = false;
212   for (BasicBlock &BB : *F) {
213     if (BB.getName() == NewBB->getName()) {
214       BBFlag = true;
215     }
216   }
217   EXPECT_TRUE(BBFlag);
218 }
219 
220 TEST(BasicBlockUtils, SplitEdge_ex4) {
221   LLVMContext C;
222   std::unique_ptr<Module> M = parseIR(C, R"IR(
223 define void @bar(i32 %cond) personality i8 0 {
224 entry:
225   switch i32 %cond, label %exit [
226     i32 -1, label %continue
227     i32 0, label %continue
228     i32 1, label %continue_alt
229     i32 2, label %continue_alt
230   ]
231 exit:
232   ret void
233 continue:
234   invoke void @sink() to label %normal unwind label %exception
235 continue_alt:
236   invoke void @sink_alt() to label %normal unwind label %exception
237 exception:
238   %cleanup = landingpad i8 cleanup
239   br label %trivial-eh-handler
240 trivial-eh-handler:
241   call void @sideeffect(i32 1)
242   br label %normal
243 normal:
244   call void @sideeffect(i32 0)
245   ret void
246 }
247 
248 declare void @sideeffect(i32)
249 declare void @sink() cold
250 declare void @sink_alt() cold
251 )IR");
252   Function *F = M->getFunction("bar");
253 
254   DominatorTree DT(*F);
255 
256   LoopInfo LI(DT);
257 
258   TargetLibraryInfoImpl TLII;
259   TargetLibraryInfo TLI(TLII);
260 
261   AAResults AA(TLI);
262 
263   MemorySSA MSSA(*F, &AA, &DT);
264   MemorySSAUpdater MSSAU(&MSSA);
265 
266   BasicBlock *SrcBlock;
267   BasicBlock *DestBlock;
268 
269   SrcBlock = getBasicBlockByName(*F, "continue");
270   DestBlock = getBasicBlockByName(*F, "exception");
271 
272   unsigned SuccNum = GetSuccessorNumber(SrcBlock, DestBlock);
273   Instruction *LatchTerm = SrcBlock->getTerminator();
274 
275   const CriticalEdgeSplittingOptions Options =
276       CriticalEdgeSplittingOptions(&DT, &LI, &MSSAU);
277 
278   // Check that the following edge is both critical and the destination block is
279   // an exception block. These must be handled differently by SplitEdge
280   bool CriticalEdge =
281       isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges);
282   EXPECT_TRUE(CriticalEdge);
283 
284   bool Ehpad = DestBlock->isEHPad();
285   EXPECT_TRUE(Ehpad);
286 
287   BasicBlock *NewBB = SplitEdge(SrcBlock, DestBlock, &DT, &LI, &MSSAU, "");
288 
289   MSSA.verifyMemorySSA();
290   EXPECT_TRUE(DT.verify());
291   EXPECT_NE(NewBB, nullptr);
292   EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock);
293   EXPECT_EQ(NewBB, SrcBlock->getTerminator()->getSuccessor(SuccNum));
294   EXPECT_EQ(NewBB->getParent(), F);
295 
296   bool BBFlag = false;
297   for (BasicBlock &BB : *F) {
298     if (BB.getName() == NewBB->getName()) {
299       BBFlag = true;
300       break;
301     }
302   }
303   EXPECT_TRUE(BBFlag);
304 }
305 
306 TEST(BasicBlockUtils, splitBasicBlockBefore_ex1) {
307   LLVMContext C;
308   std::unique_ptr<Module> M = parseIR(C, R"IR(
309 define void @foo() {
310 bb0:
311  %0 = mul i32 1, 2
312   br label %bb2
313 bb1:
314   br label %bb3
315 bb2:
316   %1 = phi  i32 [ %0, %bb0 ]
317   br label %bb3
318 bb3:
319   ret void
320 }
321 )IR");
322   Function *F = M->getFunction("foo");
323   DominatorTree DT(*F);
324 
325   BasicBlock *DestBlock;
326   BasicBlock *NewBB;
327 
328   DestBlock = getBasicBlockByName(*F, "bb2");
329 
330   NewBB = DestBlock->splitBasicBlockBefore(DestBlock->front().getIterator(),
331                                            "test");
332 
333   PHINode *PN = dyn_cast<PHINode>(&(DestBlock->front()));
334   EXPECT_EQ(PN->getIncomingBlock(0), NewBB);
335   EXPECT_EQ(NewBB->getName(), "test");
336   EXPECT_EQ(NewBB->getSingleSuccessor(), DestBlock);
337   EXPECT_EQ(DestBlock->getSinglePredecessor(), NewBB);
338 }
339 
340 #ifndef NDEBUG
341 TEST(BasicBlockUtils, splitBasicBlockBefore_ex2) {
342   LLVMContext C;
343   std::unique_ptr<Module> M = parseIR(C, R"IR(
344 define void @foo() {
345 bb0:
346  %0 = mul i32 1, 2
347   br label %bb2
348 bb1:
349   br label %bb2
350 bb2:
351   %1 = phi  i32 [ %0, %bb0 ], [ 1, %bb1 ]
352   br label %bb3
353 bb3:
354   ret void
355 }
356 )IR");
357   Function *F = M->getFunction("foo");
358   DominatorTree DT(*F);
359 
360   BasicBlock *DestBlock = getBasicBlockByName(*F, "bb2");
361 
362   ASSERT_DEATH(
363       {
364         DestBlock->splitBasicBlockBefore(DestBlock->front().getIterator(),
365                                          "test");
366       },
367       "cannot split on multi incoming phis");
368 }
369 #endif
370 
371 TEST(BasicBlockUtils, NoUnreachableBlocksToEliminate) {
372   LLVMContext C;
373   std::unique_ptr<Module> M = parseIR(C, R"IR(
374 define i32 @no_unreachable(i1 %cond) {
375 entry:
376   br i1 %cond, label %bb0, label %bb1
377 bb0:
378   br label %bb1
379 bb1:
380   %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]
381   ret i32 %phi
382 }
383 )IR");
384   Function *F = M->getFunction("no_unreachable");
385   DominatorTree DT(*F);
386   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
387 
388   EXPECT_EQ(F->size(), (size_t)3);
389   bool Result = EliminateUnreachableBlocks(*F, &DTU);
390   EXPECT_FALSE(Result);
391   EXPECT_EQ(F->size(), (size_t)3);
392   EXPECT_TRUE(DT.verify());
393 }
394 
395 TEST(BasicBlockUtils, SplitBlockPredecessors) {
396   LLVMContext C;
397   std::unique_ptr<Module> M = parseIR(C, R"IR(
398 define i32 @basic_func(i1 %cond) {
399 entry:
400   br i1 %cond, label %bb0, label %bb1
401 bb0:
402   br label %bb1
403 bb1:
404   %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]
405   ret i32 %phi
406 }
407 )IR");
408   Function *F = M->getFunction("basic_func");
409   DominatorTree DT(*F);
410 
411   // Make sure the dominator tree is properly updated if calling this on the
412   // entry block.
413   SplitBlockPredecessors(&F->getEntryBlock(), {}, "split.entry", &DT);
414   EXPECT_TRUE(DT.verify());
415 }
416 
417 TEST(BasicBlockUtils, SplitCriticalEdge) {
418   LLVMContext C;
419   std::unique_ptr<Module> M = parseIR(C, R"IR(
420 define void @crit_edge(i1 %cond0, i1 %cond1) {
421 entry:
422   br i1 %cond0, label %bb0, label %bb1
423 bb0:
424   br label %bb1
425 bb1:
426   br label %bb2
427 bb2:
428   ret void
429 }
430 )IR");
431   Function *F = M->getFunction("crit_edge");
432   DominatorTree DT(*F);
433   PostDominatorTree PDT(*F);
434 
435   CriticalEdgeSplittingOptions CESO(&DT, nullptr, nullptr, &PDT);
436   EXPECT_EQ(1u, SplitAllCriticalEdges(*F, CESO));
437   EXPECT_TRUE(DT.verify());
438   EXPECT_TRUE(PDT.verify());
439 }
440 
441 TEST(BasicBlockUtils, SplitIndirectBrCriticalEdgesIgnorePHIs) {
442   LLVMContext C;
443   std::unique_ptr<Module> M = parseIR(C, R"IR(
444 define void @crit_edge(i8* %tgt, i1 %cond0, i1 %cond1) {
445 entry:
446   indirectbr i8* %tgt, [label %bb0, label %bb1, label %bb2]
447 bb0:
448   br i1 %cond0, label %bb1, label %bb2
449 bb1:
450   %p = phi i32 [0, %bb0], [0, %entry]
451   br i1 %cond1, label %bb3, label %bb4
452 bb2:
453   ret void
454 bb3:
455   ret void
456 bb4:
457   ret void
458 }
459 )IR");
460   Function *F = M->getFunction("crit_edge");
461   DominatorTree DT(*F);
462   LoopInfo LI(DT);
463   BranchProbabilityInfo BPI(*F, LI);
464   BlockFrequencyInfo BFI(*F, BPI, LI);
465 
466   ASSERT_TRUE(SplitIndirectBrCriticalEdges(*F, /*IgnoreBlocksWithoutPHI=*/true,
467                                            &BPI, &BFI));
468 
469   // Check that successors of the split block get their probability correct.
470   BasicBlock *BB1 = getBasicBlockByName(*F, "bb1");
471   BasicBlock *SplitBB = BB1->getTerminator()->getSuccessor(0);
472   ASSERT_EQ(2u, SplitBB->getTerminator()->getNumSuccessors());
473   EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 0u));
474   EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 1u));
475 
476   // bb2 has no PHI, so we shouldn't split bb0 -> bb2
477   BasicBlock *BB0 = getBasicBlockByName(*F, "bb0");
478   ASSERT_EQ(2u, BB0->getTerminator()->getNumSuccessors());
479   EXPECT_EQ(BB0->getTerminator()->getSuccessor(1),
480             getBasicBlockByName(*F, "bb2"));
481 }
482 
483 TEST(BasicBlockUtils, SplitIndirectBrCriticalEdges) {
484   LLVMContext C;
485   std::unique_ptr<Module> M = parseIR(C, R"IR(
486 define void @crit_edge(i8* %tgt, i1 %cond0, i1 %cond1) {
487 entry:
488   indirectbr i8* %tgt, [label %bb0, label %bb1, label %bb2]
489 bb0:
490   br i1 %cond0, label %bb1, label %bb2
491 bb1:
492   %p = phi i32 [0, %bb0], [0, %entry]
493   br i1 %cond1, label %bb3, label %bb4
494 bb2:
495   ret void
496 bb3:
497   ret void
498 bb4:
499   ret void
500 }
501 )IR");
502   Function *F = M->getFunction("crit_edge");
503   DominatorTree DT(*F);
504   LoopInfo LI(DT);
505   BranchProbabilityInfo BPI(*F, LI);
506   BlockFrequencyInfo BFI(*F, BPI, LI);
507 
508   ASSERT_TRUE(SplitIndirectBrCriticalEdges(*F, /*IgnoreBlocksWithoutPHI=*/false,
509                                            &BPI, &BFI));
510 
511   // Check that successors of the split block get their probability correct.
512   BasicBlock *BB1 = getBasicBlockByName(*F, "bb1");
513   BasicBlock *SplitBB = BB1->getTerminator()->getSuccessor(0);
514   ASSERT_EQ(2u, SplitBB->getTerminator()->getNumSuccessors());
515   EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 0u));
516   EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 1u));
517 
518   // Should split, resulting in:
519   //   bb0 -> bb2.clone; bb2 -> split1; bb2.clone -> split,
520   BasicBlock *BB0 = getBasicBlockByName(*F, "bb0");
521   ASSERT_EQ(2u, BB0->getTerminator()->getNumSuccessors());
522   BasicBlock *BB2Clone = BB0->getTerminator()->getSuccessor(1);
523   BasicBlock *BB2 = getBasicBlockByName(*F, "bb2");
524   EXPECT_NE(BB2Clone, BB2);
525   ASSERT_EQ(1u, BB2->getTerminator()->getNumSuccessors());
526   ASSERT_EQ(1u, BB2Clone->getTerminator()->getNumSuccessors());
527   EXPECT_EQ(BB2->getTerminator()->getSuccessor(0),
528             BB2Clone->getTerminator()->getSuccessor(0));
529 }
530 
531 TEST(BasicBlockUtils, SetEdgeProbability) {
532   LLVMContext C;
533   std::unique_ptr<Module> M = parseIR(C, R"IR(
534 define void @edge_probability(i32 %0) {
535 entry:
536 switch i32 %0, label %LD [
537   i32 700, label %L0
538   i32 701, label %L1
539   i32 702, label %L2
540   i32 703, label %L3
541   i32 704, label %L4
542   i32 705, label %L5
543   i32 706, label %L6
544   i32 707, label %L7
545   i32 708, label %L8
546   i32 709, label %L9
547   i32 710, label %L10
548   i32 711, label %L11
549   i32 712, label %L12
550   i32 713, label %L13
551   i32 714, label %L14
552   i32 715, label %L15
553   i32 716, label %L16
554   i32 717, label %L17
555   i32 718, label %L18
556   i32 719, label %L19
557 ], !prof !{!"branch_weights", i32 1, i32 1, i32 1, i32 1, i32 1, i32 451, i32 1,
558            i32 12, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1,
559            i32 1, i32 1, i32 1, i32 1, i32 1}
560 LD:
561   unreachable
562 L0:
563   ret void
564 L1:
565   ret void
566 L2:
567   ret void
568 L3:
569   ret void
570 L4:
571   ret void
572 L5:
573   ret void
574 L6:
575   ret void
576 L7:
577   ret void
578 L8:
579   ret void
580 L9:
581   ret void
582 L10:
583   ret void
584 L11:
585   ret void
586 L12:
587   ret void
588 L13:
589   ret void
590 L14:
591   ret void
592 L15:
593   ret void
594 L16:
595   ret void
596 L17:
597   ret void
598 L18:
599   ret void
600 L19:
601   ret void
602 }
603 )IR");
604   Function *F = M->getFunction("edge_probability");
605   DominatorTree DT(*F);
606   LoopInfo LI(DT);
607   BranchProbabilityInfo BPI(*F, LI);
608 
609   // Check that the unreachable block has the minimal probability.
610   const BasicBlock *EntryBB = getBasicBlockByName(*F, "entry");
611   const BasicBlock *UnreachableBB = getBasicBlockByName(*F, "LD");
612   EXPECT_EQ(BranchProbability::getRaw(1),
613             BPI.getEdgeProbability(EntryBB, UnreachableBB));
614 }
615