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