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