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