1 //===- DomTreeUpdaterTest.cpp - DomTreeUpdater unit tests -----------------===// 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/Analysis/DomTreeUpdater.h" 10 #include "llvm/Analysis/PostDominators.h" 11 #include "llvm/AsmParser/Parser.h" 12 #include "llvm/IR/Constants.h" 13 #include "llvm/IR/Dominators.h" 14 #include "llvm/IR/Instructions.h" 15 #include "llvm/IR/LLVMContext.h" 16 #include "llvm/IR/Module.h" 17 #include "llvm/Support/SourceMgr.h" 18 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 19 #include "gtest/gtest.h" 20 #include <algorithm> 21 22 using namespace llvm; 23 24 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 25 StringRef ModuleStr) { 26 SMDiagnostic Err; 27 std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context); 28 assert(M && "Bad LLVM IR?"); 29 return M; 30 } 31 32 TEST(DomTreeUpdater, EagerUpdateBasicOperations) { 33 StringRef FuncName = "f"; 34 StringRef ModuleString = R"( 35 define i32 @f(i32 %i, i32 *%p) { 36 bb0: 37 store i32 %i, i32 *%p 38 switch i32 %i, label %bb1 [ 39 i32 1, label %bb2 40 i32 2, label %bb3 41 ] 42 bb1: 43 ret i32 1 44 bb2: 45 ret i32 2 46 bb3: 47 ret i32 3 48 })"; 49 // Make the module. 50 LLVMContext Context; 51 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 52 Function *F = M->getFunction(FuncName); 53 54 // Make the DomTreeUpdater. 55 DominatorTree DT(*F); 56 PostDominatorTree PDT(*F); 57 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager); 58 59 ASSERT_TRUE(DTU.hasDomTree()); 60 ASSERT_TRUE(DTU.hasPostDomTree()); 61 ASSERT_TRUE(DTU.isEager()); 62 ASSERT_FALSE(DTU.isLazy()); 63 ASSERT_TRUE(DTU.getDomTree().verify()); 64 ASSERT_TRUE(DTU.getPostDomTree().verify()); 65 ASSERT_FALSE(DTU.hasPendingUpdates()); 66 67 Function::iterator FI = F->begin(); 68 BasicBlock *BB0 = &*FI++; 69 BasicBlock *BB1 = &*FI++; 70 BasicBlock *BB2 = &*FI++; 71 BasicBlock *BB3 = &*FI++; 72 SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator()); 73 ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst."; 74 75 DTU.applyUpdatesPermissive( 76 {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}}); 77 ASSERT_FALSE(DTU.hasPendingUpdates()); 78 79 // Delete edge bb0 -> bb3 and push the update twice to verify duplicate 80 // entries are discarded. 81 std::vector<DominatorTree::UpdateType> Updates; 82 Updates.reserve(4); 83 Updates.push_back({DominatorTree::Delete, BB0, BB3}); 84 Updates.push_back({DominatorTree::Delete, BB0, BB3}); 85 86 // Invalid Insert: no edge bb1 -> bb2 after change to bb0. 87 Updates.push_back({DominatorTree::Insert, BB1, BB2}); 88 // Invalid Delete: edge exists bb0 -> bb1 after change to bb0. 89 Updates.push_back({DominatorTree::Delete, BB0, BB1}); 90 91 // CFG Change: remove edge bb0 -> bb3. 92 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u); 93 BB3->removePredecessor(BB0); 94 for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) { 95 if (i->getCaseSuccessor() == BB3) { 96 SI->removeCase(i); 97 break; 98 } 99 } 100 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u); 101 // Deletion of a BasicBlock is an immediate event. We remove all uses to the 102 // contained Instructions and change the Terminator to "unreachable" when 103 // queued for deletion. 104 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator())); 105 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3)); 106 DTU.applyUpdatesPermissive(Updates); 107 ASSERT_FALSE(DTU.hasPendingUpdates()); 108 109 // Invalid Insert: no edge bb1 -> bb2 after change to bb0. 110 // Invalid Delete: edge exists bb0 -> bb1 after change to bb0. 111 DTU.applyUpdatesPermissive( 112 {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}}); 113 114 // DTU working with Eager UpdateStrategy does not need to flush. 115 ASSERT_TRUE(DT.verify()); 116 ASSERT_TRUE(PDT.verify()); 117 118 // Test callback utils. 119 ASSERT_EQ(BB3->getParent(), F); 120 DTU.callbackDeleteBB(BB3, 121 [&F](BasicBlock *BB) { ASSERT_NE(BB->getParent(), F); }); 122 123 ASSERT_TRUE(DT.verify()); 124 ASSERT_TRUE(PDT.verify()); 125 ASSERT_FALSE(DTU.hasPendingUpdates()); 126 127 // Unnecessary flush() test 128 DTU.flush(); 129 EXPECT_TRUE(DT.verify()); 130 EXPECT_TRUE(PDT.verify()); 131 132 // Remove all case branch to BB2 to test Eager recalculation. 133 // Code section from llvm::ConstantFoldTerminator 134 for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) { 135 if (i->getCaseSuccessor() == BB2) { 136 // Remove this entry. 137 BB2->removePredecessor(BB0); 138 i = SI->removeCase(i); 139 e = SI->case_end(); 140 } else 141 ++i; 142 } 143 ASSERT_FALSE(DT.verify()); 144 ASSERT_FALSE(PDT.verify()); 145 DTU.recalculate(*F); 146 ASSERT_TRUE(DT.verify()); 147 ASSERT_TRUE(PDT.verify()); 148 } 149 150 TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) { 151 StringRef FuncName = "f"; 152 StringRef ModuleString = R"( 153 define i32 @f() { 154 bb0: 155 br label %bb1 156 bb1: 157 ret i32 1 158 } 159 )"; 160 // Make the module. 161 LLVMContext Context; 162 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 163 Function *F = M->getFunction(FuncName); 164 165 // Make the DTU. 166 DominatorTree DT(*F); 167 PostDominatorTree PDT(*F); 168 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager); 169 ASSERT_TRUE(DTU.hasDomTree()); 170 ASSERT_TRUE(DTU.hasPostDomTree()); 171 ASSERT_TRUE(DTU.isEager()); 172 ASSERT_FALSE(DTU.isLazy()); 173 ASSERT_TRUE(DT.verify()); 174 ASSERT_TRUE(PDT.verify()); 175 176 Function::iterator FI = F->begin(); 177 BasicBlock *BB0 = &*FI++; 178 BasicBlock *BB1 = &*FI++; 179 180 // Add a block as the new function entry BB. We also link it to BB0. 181 BasicBlock *NewEntry = 182 BasicBlock::Create(F->getContext(), "new_entry", F, BB0); 183 BranchInst::Create(BB0, NewEntry); 184 EXPECT_EQ(F->begin()->getName(), NewEntry->getName()); 185 EXPECT_TRUE(&F->getEntryBlock() == NewEntry); 186 187 DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}}); 188 189 // Changing the Entry BB requires a full recalculation of DomTree. 190 DTU.recalculate(*F); 191 ASSERT_TRUE(DT.verify()); 192 ASSERT_TRUE(PDT.verify()); 193 194 // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1. 195 EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u); 196 NewEntry->getTerminator()->eraseFromParent(); 197 BranchInst::Create(BB1, NewEntry); 198 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); 199 200 // Update the DTU. At this point bb0 now has no predecessors but is still a 201 // Child of F. 202 DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0}, 203 {DominatorTree::Insert, NewEntry, BB1}}); 204 ASSERT_TRUE(DT.verify()); 205 ASSERT_TRUE(PDT.verify()); 206 207 // Now remove bb0 from F. 208 ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator())); 209 EXPECT_FALSE(DTU.isBBPendingDeletion(BB0)); 210 DTU.deleteBB(BB0); 211 ASSERT_TRUE(DT.verify()); 212 ASSERT_TRUE(PDT.verify()); 213 } 214 215 TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) { 216 StringRef FuncName = "f"; 217 StringRef ModuleString = R"( 218 define i32 @f(i32 %i, i32 *%p) { 219 bb0: 220 store i32 %i, i32 *%p 221 switch i32 %i, label %bb1 [ 222 i32 0, label %bb2 223 i32 1, label %bb2 224 i32 2, label %bb3 225 ] 226 bb1: 227 ret i32 1 228 bb2: 229 ret i32 2 230 bb3: 231 ret i32 3 232 } 233 )"; 234 // Make the module. 235 LLVMContext Context; 236 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 237 Function *F = M->getFunction(FuncName); 238 239 // Make the DTU. 240 DominatorTree DT(*F); 241 PostDominatorTree *PDT = nullptr; 242 DomTreeUpdater DTU(&DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); 243 ASSERT_TRUE(DTU.hasDomTree()); 244 ASSERT_FALSE(DTU.hasPostDomTree()); 245 ASSERT_FALSE(DTU.isEager()); 246 ASSERT_TRUE(DTU.isLazy()); 247 ASSERT_TRUE(DTU.getDomTree().verify()); 248 249 Function::iterator FI = F->begin(); 250 BasicBlock *BB0 = &*FI++; 251 BasicBlock *BB1 = &*FI++; 252 BasicBlock *BB2 = &*FI++; 253 BasicBlock *BB3 = &*FI++; 254 255 // Test discards of self-domination update. 256 DTU.applyUpdatesPermissive({{DominatorTree::Insert, BB0, BB0}}); 257 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); 258 259 // Delete edge bb0 -> bb3 and push the update twice to verify duplicate 260 // entries are discarded. 261 std::vector<DominatorTree::UpdateType> Updates; 262 Updates.reserve(4); 263 Updates.push_back({DominatorTree::Delete, BB0, BB3}); 264 Updates.push_back({DominatorTree::Delete, BB0, BB3}); 265 266 // Invalid Insert: no edge bb1 -> bb2 after change to bb0. 267 Updates.push_back({DominatorTree::Insert, BB1, BB2}); 268 // Invalid Delete: edge exists bb0 -> bb1 after change to bb0. 269 Updates.push_back({DominatorTree::Delete, BB0, BB1}); 270 271 // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2. 272 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u); 273 BB0->getTerminator()->eraseFromParent(); 274 BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0); 275 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u); 276 277 // Verify. Updates to DTU must be applied *after* all changes to the CFG 278 // (including block deletion). 279 DTU.applyUpdatesPermissive(Updates); 280 ASSERT_TRUE(DTU.getDomTree().verify()); 281 282 // Deletion of a BasicBlock is an immediate event. We remove all uses to the 283 // contained Instructions and change the Terminator to "unreachable" when 284 // queued for deletion. Its parent is still F until all the pending updates 285 // are applied to all trees held by the DomTreeUpdater (DomTree/PostDomTree). 286 // We don't defer this action because it can cause problems for other 287 // transforms or analysis as it's part of the actual CFG. We only defer 288 // updates to the DominatorTrees. This code will crash if it is placed before 289 // the BranchInst::Create() call above. After a deletion of a BasicBlock. Only 290 // an explicit flush event can trigger the flushing of deleteBBs. Because some 291 // passes using Lazy UpdateStrategy rely on this behavior. 292 293 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator())); 294 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3)); 295 EXPECT_FALSE(DTU.hasPendingDeletedBB()); 296 DTU.deleteBB(BB3); 297 EXPECT_TRUE(DTU.isBBPendingDeletion(BB3)); 298 EXPECT_TRUE(DTU.hasPendingDeletedBB()); 299 ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator())); 300 EXPECT_EQ(BB3->getParent(), F); 301 DTU.recalculate(*F); 302 EXPECT_FALSE(DTU.hasPendingDeletedBB()); 303 } 304 305 TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) { 306 StringRef FuncName = "f"; 307 StringRef ModuleString = R"( 308 define i32 @f(i32 %i, i32 *%p) { 309 bb0: 310 store i32 %i, i32 *%p 311 switch i32 %i, label %bb1 [ 312 i32 2, label %bb2 313 i32 3, label %bb3 314 ] 315 bb1: 316 br label %bb3 317 bb2: 318 br label %bb3 319 bb3: 320 ret i32 3 321 } 322 )"; 323 // Make the module. 324 LLVMContext Context; 325 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 326 Function *F = M->getFunction(FuncName); 327 328 // Make the DTU. 329 DominatorTree DT(*F); 330 PostDominatorTree *PDT = nullptr; 331 DomTreeUpdater DTU(&DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); 332 ASSERT_TRUE(DTU.hasDomTree()); 333 ASSERT_FALSE(DTU.hasPostDomTree()); 334 ASSERT_FALSE(DTU.isEager()); 335 ASSERT_TRUE(DTU.isLazy()); 336 ASSERT_TRUE(DTU.getDomTree().verify()); 337 338 Function::iterator FI = F->begin(); 339 BasicBlock *BB0 = &*FI++; 340 BasicBlock *BB1 = &*FI++; 341 BasicBlock *BB2 = &*FI++; 342 BasicBlock *BB3 = &*FI++; 343 344 // There are several CFG locations where we have: 345 // 346 // pred1..predN 347 // | | 348 // +> curr <+ converted into: pred1..predN curr 349 // | | | 350 // v +> succ <+ 351 // succ 352 // 353 // There is a specific shape of this we have to be careful of: 354 // 355 // pred1..predN 356 // || | 357 // |+> curr <+ converted into: pred1..predN curr 358 // | | | | 359 // | v +> succ <+ 360 // +-> succ 361 // 362 // While the final CFG form is functionally identical the updates to 363 // DTU are not. In the first case we must have 364 // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in 365 // the latter case we must *NOT* have 366 // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}). 367 368 // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to 369 // remove bb2. 370 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u); 371 BB0->getTerminator()->eraseFromParent(); 372 BranchInst::Create(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0); 373 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u); 374 375 // Test callback utils. 376 std::vector<BasicBlock *> BasicBlocks; 377 BasicBlocks.push_back(BB1); 378 BasicBlocks.push_back(BB2); 379 auto Eraser = [&](BasicBlock *BB) { llvm::erase(BasicBlocks, BB); }; 380 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2)); 381 // Remove bb2 from F. This has to happen before the call to 382 // applyUpdates() for DTU to detect there is no longer an edge between 383 // bb2 -> bb3. The deleteBB() method converts bb2's TI into "unreachable". 384 ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator())); 385 EXPECT_FALSE(DTU.isBBPendingDeletion(BB2)); 386 DTU.callbackDeleteBB(BB2, Eraser); 387 EXPECT_TRUE(DTU.isBBPendingDeletion(BB2)); 388 ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator())); 389 EXPECT_EQ(BB2->getParent(), F); 390 391 // Queue up the DTU updates. 392 std::vector<DominatorTree::UpdateType> Updates; 393 Updates.reserve(4); 394 Updates.push_back({DominatorTree::Delete, BB0, BB2}); 395 Updates.push_back({DominatorTree::Delete, BB2, BB3}); 396 397 // Handle the specific shape case next. 398 // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1. 399 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u); 400 BB0->getTerminator()->eraseFromParent(); 401 BranchInst::Create(BB3, BB0); 402 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); 403 404 // Remove bb1 from F. This has to happen before the call to 405 // applyUpdates() for DTU to detect there is no longer an edge between 406 // bb1 -> bb3. The deleteBB() method converts bb1's TI into "unreachable". 407 ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator())); 408 EXPECT_FALSE(DTU.isBBPendingDeletion(BB1)); 409 DTU.callbackDeleteBB(BB1, Eraser); 410 EXPECT_TRUE(DTU.isBBPendingDeletion(BB1)); 411 ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator())); 412 EXPECT_EQ(BB1->getParent(), F); 413 414 // Update the DTU. In this case we don't submit {DominatorTree::Insert, BB0, 415 // BB3} because the edge previously existed at the start of this test when DT 416 // was first created. 417 Updates.push_back({DominatorTree::Delete, BB0, BB1}); 418 Updates.push_back({DominatorTree::Delete, BB1, BB3}); 419 420 // Verify everything. 421 DTU.applyUpdatesPermissive(Updates); 422 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2)); 423 DTU.flush(); 424 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0)); 425 ASSERT_TRUE(DT.verify()); 426 } 427 428 TEST(DomTreeUpdater, LazyUpdateBasicOperations) { 429 StringRef FuncName = "f"; 430 StringRef ModuleString = R"( 431 define i32 @f(i32 %i, i32 *%p) { 432 bb0: 433 store i32 %i, i32 *%p 434 switch i32 %i, label %bb1 [ 435 i32 0, label %bb2 436 i32 1, label %bb2 437 i32 2, label %bb3 438 ] 439 bb1: 440 ret i32 1 441 bb2: 442 ret i32 2 443 bb3: 444 ret i32 3 445 } 446 )"; 447 // Make the module. 448 LLVMContext Context; 449 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 450 Function *F = M->getFunction(FuncName); 451 452 // Make the DTU. 453 DominatorTree DT(*F); 454 PostDominatorTree PDT(*F); 455 DomTreeUpdater DTU(&DT, &PDT, DomTreeUpdater::UpdateStrategy::Lazy); 456 ASSERT_TRUE(DTU.hasDomTree()); 457 ASSERT_TRUE(DTU.hasPostDomTree()); 458 ASSERT_FALSE(DTU.isEager()); 459 ASSERT_TRUE(DTU.isLazy()); 460 ASSERT_TRUE(DTU.getDomTree().verify()); 461 ASSERT_TRUE(DTU.getPostDomTree().verify()); 462 463 Function::iterator FI = F->begin(); 464 BasicBlock *BB0 = &*FI++; 465 BasicBlock *BB1 = &*FI++; 466 BasicBlock *BB2 = &*FI++; 467 BasicBlock *BB3 = &*FI++; 468 // Test discards of self-domination update. 469 DTU.applyUpdates({{DominatorTree::Delete, BB0, BB0}}); 470 471 // Delete edge bb0 -> bb3 and push the update twice to verify duplicate 472 // entries are discarded. 473 std::vector<DominatorTree::UpdateType> Updates; 474 Updates.reserve(4); 475 Updates.push_back({DominatorTree::Delete, BB0, BB3}); 476 Updates.push_back({DominatorTree::Delete, BB0, BB3}); 477 478 // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0. 479 Updates.push_back({DominatorTree::Insert, BB1, BB2}); 480 // Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0. 481 Updates.push_back({DominatorTree::Delete, BB0, BB1}); 482 483 // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2. 484 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u); 485 BB0->getTerminator()->eraseFromParent(); 486 BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0); 487 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u); 488 489 // Deletion of a BasicBlock is an immediate event. We remove all uses to the 490 // contained Instructions and change the Terminator to "unreachable" when 491 // queued for deletion. Its parent is still F until DTU.flushDomTree is 492 // called. We don't defer this action because it can cause problems for other 493 // transforms or analysis as it's part of the actual CFG. We only defer 494 // updates to the DominatorTree. This code will crash if it is placed before 495 // the BranchInst::Create() call above. 496 bool CallbackFlag = false; 497 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator())); 498 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3)); 499 DTU.callbackDeleteBB(BB3, [&](BasicBlock *) { CallbackFlag = true; }); 500 EXPECT_TRUE(DTU.isBBPendingDeletion(BB3)); 501 ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator())); 502 EXPECT_EQ(BB3->getParent(), F); 503 504 // Verify. Updates to DTU must be applied *after* all changes to the CFG 505 // (including block deletion). 506 DTU.applyUpdatesPermissive(Updates); 507 ASSERT_TRUE(DTU.getDomTree().verify()); 508 ASSERT_TRUE(DTU.hasPendingUpdates()); 509 ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates()); 510 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); 511 ASSERT_TRUE(DTU.hasPendingDeletedBB()); 512 ASSERT_TRUE(DTU.getPostDomTree().verify()); 513 ASSERT_FALSE(DTU.hasPendingUpdates()); 514 ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates()); 515 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); 516 ASSERT_FALSE(DTU.hasPendingDeletedBB()); 517 ASSERT_EQ(CallbackFlag, true); 518 } 519 520 TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) { 521 StringRef FuncName = "f"; 522 StringRef ModuleString = R"( 523 define i32 @f() { 524 bb0: 525 br label %bb1 526 bb1: 527 ret i32 1 528 } 529 )"; 530 // Make the module. 531 LLVMContext Context; 532 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 533 Function *F = M->getFunction(FuncName); 534 535 // Make the DTU. 536 DominatorTree DT(*F); 537 PostDominatorTree PDT(*F); 538 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); 539 ASSERT_TRUE(DTU.hasDomTree()); 540 ASSERT_TRUE(DTU.hasPostDomTree()); 541 ASSERT_FALSE(DTU.isEager()); 542 ASSERT_TRUE(DTU.isLazy()); 543 ASSERT_TRUE(DTU.getDomTree().verify()); 544 ASSERT_TRUE(DTU.getPostDomTree().verify()); 545 546 Function::iterator FI = F->begin(); 547 BasicBlock *BB0 = &*FI++; 548 BasicBlock *BB1 = &*FI++; 549 550 // Add a block as the new function entry BB. We also link it to BB0. 551 BasicBlock *NewEntry = 552 BasicBlock::Create(F->getContext(), "new_entry", F, BB0); 553 BranchInst::Create(BB0, NewEntry); 554 EXPECT_EQ(F->begin()->getName(), NewEntry->getName()); 555 EXPECT_TRUE(&F->getEntryBlock() == NewEntry); 556 557 // Insert the new edge between new_entry -> bb0. Without this the 558 // recalculate() call below will not actually recalculate the DT as there 559 // are no changes pending and no blocks deleted. 560 DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}}); 561 562 // Changing the Entry BB requires a full recalculation. 563 DTU.recalculate(*F); 564 ASSERT_TRUE(DTU.getDomTree().verify()); 565 ASSERT_TRUE(DTU.getPostDomTree().verify()); 566 567 // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1. 568 EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u); 569 NewEntry->getTerminator()->eraseFromParent(); 570 BranchInst::Create(BB1, NewEntry); 571 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); 572 573 // Update the DTU. At this point bb0 now has no predecessors but is still a 574 // Child of F. 575 DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0}, 576 {DominatorTree::Insert, NewEntry, BB1}}); 577 DTU.flush(); 578 ASSERT_TRUE(DT.verify()); 579 ASSERT_TRUE(PDT.verify()); 580 581 // Now remove bb0 from F. 582 ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator())); 583 EXPECT_FALSE(DTU.isBBPendingDeletion(BB0)); 584 DTU.deleteBB(BB0); 585 EXPECT_TRUE(DTU.isBBPendingDeletion(BB0)); 586 ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator())); 587 EXPECT_EQ(BB0->getParent(), F); 588 589 // Perform a full recalculation of the DTU. It is not necessary here but we 590 // do this to test the case when there are no pending DT updates but there are 591 // pending deleted BBs. 592 ASSERT_TRUE(DTU.hasPendingDeletedBB()); 593 DTU.recalculate(*F); 594 ASSERT_FALSE(DTU.hasPendingDeletedBB()); 595 } 596 597 TEST(DomTreeUpdater, LazyUpdateStepTest) { 598 // This test focus on testing a DTU holding both trees applying multiple 599 // updates and DT/PDT not flushed together. 600 StringRef FuncName = "f"; 601 StringRef ModuleString = R"( 602 define i32 @f(i32 %i, i32 *%p) { 603 bb0: 604 store i32 %i, i32 *%p 605 switch i32 %i, label %bb1 [ 606 i32 0, label %bb1 607 i32 1, label %bb2 608 i32 2, label %bb3 609 i32 3, label %bb1 610 ] 611 bb1: 612 ret i32 1 613 bb2: 614 ret i32 2 615 bb3: 616 ret i32 3 617 } 618 )"; 619 // Make the module. 620 LLVMContext Context; 621 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 622 Function *F = M->getFunction(FuncName); 623 624 // Make the DomTreeUpdater. 625 DominatorTree DT(*F); 626 PostDominatorTree PDT(*F); 627 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); 628 629 ASSERT_TRUE(DTU.hasDomTree()); 630 ASSERT_TRUE(DTU.hasPostDomTree()); 631 ASSERT_FALSE(DTU.isEager()); 632 ASSERT_TRUE(DTU.isLazy()); 633 ASSERT_TRUE(DTU.getDomTree().verify()); 634 ASSERT_TRUE(DTU.getPostDomTree().verify()); 635 ASSERT_FALSE(DTU.hasPendingUpdates()); 636 637 Function::iterator FI = F->begin(); 638 BasicBlock *BB0 = &*FI++; 639 FI++; 640 BasicBlock *BB2 = &*FI++; 641 BasicBlock *BB3 = &*FI++; 642 SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator()); 643 ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst."; 644 645 // Delete edge bb0 -> bb3. 646 std::vector<DominatorTree::UpdateType> Updates; 647 Updates.reserve(1); 648 Updates.push_back({DominatorTree::Delete, BB0, BB3}); 649 650 // CFG Change: remove edge bb0 -> bb3. 651 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 5u); 652 BB3->removePredecessor(BB0); 653 for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) { 654 if (i->getCaseIndex() == 2) { 655 SI->removeCase(i); 656 break; 657 } 658 } 659 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u); 660 // Deletion of a BasicBlock is an immediate event. We remove all uses to the 661 // contained Instructions and change the Terminator to "unreachable" when 662 // queued for deletion. 663 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator())); 664 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3)); 665 DTU.applyUpdates(Updates); 666 667 // Only flush DomTree. 668 ASSERT_TRUE(DTU.getDomTree().verify()); 669 ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates()); 670 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); 671 672 ASSERT_EQ(BB3->getParent(), F); 673 DTU.deleteBB(BB3); 674 675 Updates.clear(); 676 677 // Remove all case branch to BB2 to test Eager recalculation. 678 // Code section from llvm::ConstantFoldTerminator 679 for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) { 680 if (i->getCaseSuccessor() == BB2) { 681 // Remove this entry. 682 BB2->removePredecessor(BB0); 683 i = SI->removeCase(i); 684 e = SI->case_end(); 685 Updates.push_back({DominatorTree::Delete, BB0, BB2}); 686 } else 687 ++i; 688 } 689 690 DTU.applyUpdatesPermissive(Updates); 691 // flush PostDomTree 692 ASSERT_TRUE(DTU.getPostDomTree().verify()); 693 ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates()); 694 ASSERT_TRUE(DTU.hasPendingDomTreeUpdates()); 695 // flush both trees 696 DTU.flush(); 697 ASSERT_TRUE(DT.verify()); 698 } 699 700 TEST(DomTreeUpdater, NoTreeTest) { 701 StringRef FuncName = "f"; 702 StringRef ModuleString = R"( 703 define i32 @f() { 704 bb0: 705 ret i32 0 706 } 707 )"; 708 // Make the module. 709 LLVMContext Context; 710 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 711 Function *F = M->getFunction(FuncName); 712 713 // Make the DTU. 714 DomTreeUpdater DTU(nullptr, nullptr, DomTreeUpdater::UpdateStrategy::Lazy); 715 ASSERT_FALSE(DTU.hasDomTree()); 716 ASSERT_FALSE(DTU.hasPostDomTree()); 717 Function::iterator FI = F->begin(); 718 BasicBlock *BB0 = &*FI++; 719 // Test whether PendingDeletedBB is flushed after the recalculation. 720 DTU.deleteBB(BB0); 721 ASSERT_TRUE(DTU.hasPendingDeletedBB()); 722 DTU.recalculate(*F); 723 ASSERT_FALSE(DTU.hasPendingDeletedBB()); 724 } 725 726 TEST(DomTreeUpdater, LazyUpdateDeduplicationTest) { 727 StringRef FuncName = "f"; 728 StringRef ModuleString = R"( 729 define i32 @f() { 730 bb0: 731 br label %bb1 732 bb1: 733 ret i32 1 734 bb2: 735 ret i32 1 736 } 737 )"; 738 // Make the module. 739 LLVMContext Context; 740 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 741 Function *F = M->getFunction(FuncName); 742 743 // Make the DTU. 744 DominatorTree DT(*F); 745 DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy); 746 ASSERT_TRUE(DTU.getDomTree().verify()); 747 748 Function::iterator FI = F->begin(); 749 BasicBlock *BB0 = &*FI++; 750 BasicBlock *BB1 = &*FI++; 751 BasicBlock *BB2 = &*FI++; 752 753 // CFG Change: remove bb0 -> bb1 and add back bb0 -> bb1. 754 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); 755 BB0->getTerminator()->eraseFromParent(); 756 BranchInst::Create(BB1, BB0); 757 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); 758 759 // Update the DTU and simulate duplicates. 760 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}, 761 {DominatorTree::Delete, BB0, BB1}, 762 {DominatorTree::Insert, BB0, BB1}, 763 {DominatorTree::Insert, BB0, BB1}, 764 {DominatorTree::Insert, BB0, BB1}}); 765 766 // The above operations result in a no-op. 767 ASSERT_FALSE(DTU.hasPendingUpdates()); 768 769 // Update the DTU. Simulate an invalid update. 770 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}}); 771 ASSERT_FALSE(DTU.hasPendingUpdates()); 772 773 // CFG Change: remove bb0 -> bb1. 774 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); 775 BB0->getTerminator()->eraseFromParent(); 776 777 // Update the DTU and simulate invalid updates. 778 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}, 779 {DominatorTree::Insert, BB0, BB1}, 780 {DominatorTree::Delete, BB0, BB1}, 781 {DominatorTree::Insert, BB0, BB1}, 782 {DominatorTree::Insert, BB0, BB1}}); 783 ASSERT_TRUE(DTU.hasPendingUpdates()); 784 785 // CFG Change: add bb0 -> bb2. 786 BranchInst::Create(BB2, BB0); 787 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); 788 DTU.applyUpdates({{DominatorTree::Insert, BB0, BB2}}); 789 ASSERT_TRUE(DTU.getDomTree().verify()); 790 } 791 792 TEST(DomTreeUpdater, CriticalEdgeSplitTest) { 793 StringRef FuncName = "f"; 794 StringRef ModuleString = R"( 795 declare void @use1(i32) 796 797 define void @f(i32 %i, i1 %c) { 798 entry: 799 %A = icmp eq i32 %i, 0 ; <i1> [#uses=1] 800 br i1 %A, label %brtrue, label %brfalse 801 802 brtrue: ; preds = %entry 803 call void @use1( i32 %i ) 804 br label %brfalse 805 806 brfalse: ; preds = %brtrue, %entry 807 call void @use1( i32 %i ) 808 ret void 809 } 810 )"; 811 // Make the module. 812 LLVMContext Context; 813 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 814 Function *F = M->getFunction(FuncName); 815 816 // Make the DTU. 817 DominatorTree DT(*F); 818 DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy); 819 ASSERT_TRUE(DTU.getDomTree().verify()); 820 821 CriticalEdgeSplittingOptions Opts; 822 SplitAllCriticalEdges(*F, Opts); 823 824 Function::iterator FI = F->begin(); 825 BasicBlock *BBEntry = &*FI++; 826 BasicBlock *SplitB = &*FI++; 827 [[maybe_unused]] BasicBlock *BBTrue = &*FI++; 828 BasicBlock *BBFalse = &*FI++; 829 DTU.splitCriticalEdge(BBEntry, BBFalse, SplitB); 830 DominatorTree NewDT(*F); 831 ASSERT_FALSE(NewDT.compare(DTU.getDomTree())); 832 } 833