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