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 = new MemorySSA(*F, &AA, &DT); 195 MemorySSAUpdater *Updater = new MemorySSAUpdater(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 TEST(BasicBlockUtils, splitBasicBlockBefore_ex2) { 258 LLVMContext C; 259 std::unique_ptr<Module> M = 260 parseIR(C, "define void @foo() {\n" 261 "bb0:\n" 262 " %0 = mul i32 1, 2\n" 263 " br label %bb2\n" 264 "bb1:\n" 265 " br label %bb2\n" 266 "bb2:\n" 267 " %1 = phi i32 [ %0, %bb0 ], [ 1, %bb1 ]\n" 268 " br label %bb3\n" 269 "bb3:\n" 270 " ret void\n" 271 "}\n" 272 "\n"); 273 274 Function *F = M->getFunction("foo"); 275 DominatorTree DT(*F); 276 277 BasicBlock *DestBlock; 278 279 DestBlock = getBasicBlockByName(*F, "bb2"); 280 281 ASSERT_DEATH( 282 { 283 DestBlock->splitBasicBlockBefore(DestBlock->front().getIterator(), 284 "test"); 285 }, 286 "cannot split on multi incoming phis"); 287 } 288 289 TEST(BasicBlockUtils, NoUnreachableBlocksToEliminate) { 290 LLVMContext C; 291 292 std::unique_ptr<Module> M = parseIR( 293 C, 294 "define i32 @no_unreachable(i1 %cond) {\n" 295 "entry:\n" 296 " br i1 %cond, label %bb0, label %bb1\n" 297 "bb0:\n" 298 " br label %bb1\n" 299 "bb1:\n" 300 " %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]" 301 " ret i32 %phi\n" 302 "}\n" 303 "\n" 304 ); 305 306 auto *F = M->getFunction("no_unreachable"); 307 DominatorTree DT(*F); 308 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager); 309 310 EXPECT_EQ(F->size(), (size_t)3); 311 bool Result = EliminateUnreachableBlocks(*F, &DTU); 312 EXPECT_FALSE(Result); 313 EXPECT_EQ(F->size(), (size_t)3); 314 EXPECT_TRUE(DT.verify()); 315 } 316 317 TEST(BasicBlockUtils, SplitBlockPredecessors) { 318 LLVMContext C; 319 320 std::unique_ptr<Module> M = parseIR( 321 C, 322 "define i32 @basic_func(i1 %cond) {\n" 323 "entry:\n" 324 " br i1 %cond, label %bb0, label %bb1\n" 325 "bb0:\n" 326 " br label %bb1\n" 327 "bb1:\n" 328 " %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]" 329 " ret i32 %phi\n" 330 "}\n" 331 "\n" 332 ); 333 334 auto *F = M->getFunction("basic_func"); 335 DominatorTree DT(*F); 336 337 // Make sure the dominator tree is properly updated if calling this on the 338 // entry block. 339 SplitBlockPredecessors(&F->getEntryBlock(), {}, "split.entry", &DT); 340 EXPECT_TRUE(DT.verify()); 341 } 342 343 TEST(BasicBlockUtils, SplitCriticalEdge) { 344 LLVMContext C; 345 346 std::unique_ptr<Module> M = parseIR( 347 C, 348 "define void @crit_edge(i1 %cond0, i1 %cond1) {\n" 349 "entry:\n" 350 " br i1 %cond0, label %bb0, label %bb1\n" 351 "bb0:\n" 352 " br label %bb1\n" 353 "bb1:\n" 354 " br label %bb2\n" 355 "bb2:\n" 356 " ret void\n" 357 "}\n" 358 "\n" 359 ); 360 361 auto *F = M->getFunction("crit_edge"); 362 DominatorTree DT(*F); 363 PostDominatorTree PDT(*F); 364 365 CriticalEdgeSplittingOptions CESO(&DT, nullptr, nullptr, &PDT); 366 EXPECT_EQ(1u, SplitAllCriticalEdges(*F, CESO)); 367 EXPECT_TRUE(DT.verify()); 368 EXPECT_TRUE(PDT.verify()); 369 } 370 371 TEST(BasicBlockUtils, SplitIndirectBrCriticalEdge) { 372 LLVMContext C; 373 374 std::unique_ptr<Module> M = 375 parseIR(C, "define void @crit_edge(i8* %cond0, i1 %cond1) {\n" 376 "entry:\n" 377 " indirectbr i8* %cond0, [label %bb0, label %bb1]\n" 378 "bb0:\n" 379 " br label %bb1\n" 380 "bb1:\n" 381 " %p = phi i32 [0, %bb0], [0, %entry]\n" 382 " br i1 %cond1, label %bb2, label %bb3\n" 383 "bb2:\n" 384 " ret void\n" 385 "bb3:\n" 386 " ret void\n" 387 "}\n"); 388 389 auto *F = M->getFunction("crit_edge"); 390 DominatorTree DT(*F); 391 LoopInfo LI(DT); 392 BranchProbabilityInfo BPI(*F, LI); 393 BlockFrequencyInfo BFI(*F, BPI, LI); 394 395 auto Block = [&F](StringRef BBName) -> const BasicBlock & { 396 for (auto &BB : *F) 397 if (BB.getName() == BBName) 398 return BB; 399 llvm_unreachable("Block not found"); 400 }; 401 402 bool Split = SplitIndirectBrCriticalEdges(*F, &BPI, &BFI); 403 404 EXPECT_TRUE(Split); 405 406 // Check that successors of the split block get their probability correct. 407 BasicBlock *SplitBB = Block("bb1").getTerminator()->getSuccessor(0); 408 EXPECT_EQ(2u, SplitBB->getTerminator()->getNumSuccessors()); 409 EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 0u)); 410 EXPECT_EQ(BranchProbability(1, 2), BPI.getEdgeProbability(SplitBB, 1u)); 411 } 412 413 TEST(BasicBlockUtils, SetEdgeProbability) { 414 LLVMContext C; 415 416 std::unique_ptr<Module> M = parseIR( 417 C, "define void @edge_probability(i32 %0) {\n" 418 "entry:\n" 419 "switch i32 %0, label %LD [\n" 420 " i32 700, label %L0\n" 421 " i32 701, label %L1\n" 422 " i32 702, label %L2\n" 423 " i32 703, label %L3\n" 424 " i32 704, label %L4\n" 425 " i32 705, label %L5\n" 426 " i32 706, label %L6\n" 427 " i32 707, label %L7\n" 428 " i32 708, label %L8\n" 429 " i32 709, label %L9\n" 430 " i32 710, label %L10\n" 431 " i32 711, label %L11\n" 432 " i32 712, label %L12\n" 433 " i32 713, label %L13\n" 434 " i32 714, label %L14\n" 435 " i32 715, label %L15\n" 436 " i32 716, label %L16\n" 437 " i32 717, label %L17\n" 438 " i32 718, label %L18\n" 439 " i32 719, label %L19\n" 440 "], !prof !{!\"branch_weights\", i32 1, i32 1, i32 1, i32 1, i32 1, " 441 "i32 451, i32 1, i32 12, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, " 442 "i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1}\n" 443 "LD:\n" 444 " unreachable\n" 445 "L0:\n" 446 " ret void\n" 447 "L1:\n" 448 " ret void\n" 449 "L2:\n" 450 " ret void\n" 451 "L3:\n" 452 " ret void\n" 453 "L4:\n" 454 " ret void\n" 455 "L5:\n" 456 " ret void\n" 457 "L6:\n" 458 " ret void\n" 459 "L7:\n" 460 " ret void\n" 461 "L8:\n" 462 " ret void\n" 463 "L9:\n" 464 " ret void\n" 465 "L10:\n" 466 " ret void\n" 467 "L11:\n" 468 " ret void\n" 469 "L12:\n" 470 " ret void\n" 471 "L13:\n" 472 " ret void\n" 473 "L14:\n" 474 " ret void\n" 475 "L15:\n" 476 " ret void\n" 477 "L16:\n" 478 " ret void\n" 479 "L17:\n" 480 " ret void\n" 481 "L18:\n" 482 " ret void\n" 483 "L19:\n" 484 " ret void\n" 485 "}\n"); 486 487 auto *F = M->getFunction("edge_probability"); 488 DominatorTree DT(*F); 489 LoopInfo LI(DT); 490 BranchProbabilityInfo BPI(*F, LI); 491 492 auto Block = [&F](StringRef BBName) -> const BasicBlock & { 493 for (auto &BB : *F) 494 if (BB.getName() == BBName) 495 return BB; 496 llvm_unreachable("Block not found"); 497 }; 498 499 // Check that the unreachable block has the minimal probability. 500 const BasicBlock &EntryBB = Block("entry"); 501 const BasicBlock &UnreachableBB = Block("LD"); 502 EXPECT_EQ(BranchProbability::getRaw(1), 503 BPI.getEdgeProbability(&EntryBB, &UnreachableBB)); 504 } 505