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 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 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 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 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 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 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