832 lines · cpp
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-exception6//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 21using namespace llvm;22 23static 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 31TEST(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 *%p37 switch i32 %i, label %bb1 [38 i32 1, label %bb239 i32 2, label %bb340 ]41 bb1:42 ret i32 143 bb2:44 ret i32 245 bb3:46 ret i32 347 })";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 duplicate79 // 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 the101 // contained Instructions and change the Terminator to "unreachable" when102 // 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() test127 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::ConstantFoldTerminator133 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 } else140 ++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 149TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) {150 StringRef FuncName = "f";151 StringRef ModuleString = R"(152 define i32 @f() {153 bb0:154 br label %bb1155 bb1:156 ret i32 1157 }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 a200 // 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 214TEST(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 *%p220 switch i32 %i, label %bb1 [221 i32 0, label %bb2222 i32 1, label %bb2223 i32 2, label %bb3224 ]225 bb1:226 ret i32 1227 bb2:228 ret i32 2229 bb3:230 ret i32 3231 }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 duplicate259 // 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 CFG277 // (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 the282 // contained Instructions and change the Terminator to "unreachable" when283 // queued for deletion. Its parent is still F until all the pending updates284 // are applied to all trees held by the DomTreeUpdater (DomTree/PostDomTree).285 // We don't defer this action because it can cause problems for other286 // transforms or analysis as it's part of the actual CFG. We only defer287 // updates to the DominatorTrees. This code will crash if it is placed before288 // the BranchInst::Create() call above. After a deletion of a BasicBlock. Only289 // an explicit flush event can trigger the flushing of deleteBBs. Because some290 // 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 304TEST(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 *%p310 switch i32 %i, label %bb1 [311 i32 2, label %bb2312 i32 3, label %bb3313 ]314 bb1:315 br label %bb3316 bb2:317 br label %bb3318 bb3:319 ret i32 3320 }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..predN346 // | |347 // +> curr <+ converted into: pred1..predN curr348 // | | |349 // v +> succ <+350 // succ351 //352 // There is a specific shape of this we have to be careful of:353 //354 // pred1..predN355 // || |356 // |+> curr <+ converted into: pred1..predN curr357 // | | | |358 // | v +> succ <+359 // +-> succ360 //361 // While the final CFG form is functionally identical the updates to362 // DTU are not. In the first case we must have363 // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in364 // the latter case we must *NOT* have365 // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}).366 367 // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to368 // 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) { llvm::erase(BasicBlocks, BB); };379 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));380 // Remove bb2 from F. This has to happen before the call to381 // applyUpdates() for DTU to detect there is no longer an edge between382 // bb2 -> bb3. The deleteBB() method converts bb2's TI into "unreachable".383 ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));384 EXPECT_FALSE(DTU.isBBPendingDeletion(BB2));385 DTU.callbackDeleteBB(BB2, Eraser);386 EXPECT_TRUE(DTU.isBBPendingDeletion(BB2));387 ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator()));388 EXPECT_EQ(BB2->getParent(), F);389 390 // Queue up the DTU updates.391 std::vector<DominatorTree::UpdateType> Updates;392 Updates.reserve(4);393 Updates.push_back({DominatorTree::Delete, BB0, BB2});394 Updates.push_back({DominatorTree::Delete, BB2, BB3});395 396 // Handle the specific shape case next.397 // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1.398 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);399 BB0->getTerminator()->eraseFromParent();400 BranchInst::Create(BB3, BB0);401 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);402 403 // Remove bb1 from F. This has to happen before the call to404 // applyUpdates() for DTU to detect there is no longer an edge between405 // bb1 -> bb3. The deleteBB() method converts bb1's TI into "unreachable".406 ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));407 EXPECT_FALSE(DTU.isBBPendingDeletion(BB1));408 DTU.callbackDeleteBB(BB1, Eraser);409 EXPECT_TRUE(DTU.isBBPendingDeletion(BB1));410 ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));411 EXPECT_EQ(BB1->getParent(), F);412 413 // Update the DTU. In this case we don't submit {DominatorTree::Insert, BB0,414 // BB3} because the edge previously existed at the start of this test when DT415 // was first created.416 Updates.push_back({DominatorTree::Delete, BB0, BB1});417 Updates.push_back({DominatorTree::Delete, BB1, BB3});418 419 // Verify everything.420 DTU.applyUpdatesPermissive(Updates);421 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));422 DTU.flush();423 ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0));424 ASSERT_TRUE(DT.verify());425}426 427TEST(DomTreeUpdater, LazyUpdateBasicOperations) {428 StringRef FuncName = "f";429 StringRef ModuleString = R"(430 define i32 @f(i32 %i, i32 *%p) {431 bb0:432 store i32 %i, i32 *%p433 switch i32 %i, label %bb1 [434 i32 0, label %bb2435 i32 1, label %bb2436 i32 2, label %bb3437 ]438 bb1:439 ret i32 1440 bb2:441 ret i32 2442 bb3:443 ret i32 3444 }445 )";446 // Make the module.447 LLVMContext Context;448 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);449 Function *F = M->getFunction(FuncName);450 451 // Make the DTU.452 DominatorTree DT(*F);453 PostDominatorTree PDT(*F);454 DomTreeUpdater DTU(&DT, &PDT, DomTreeUpdater::UpdateStrategy::Lazy);455 ASSERT_TRUE(DTU.hasDomTree());456 ASSERT_TRUE(DTU.hasPostDomTree());457 ASSERT_FALSE(DTU.isEager());458 ASSERT_TRUE(DTU.isLazy());459 ASSERT_TRUE(DTU.getDomTree().verify());460 ASSERT_TRUE(DTU.getPostDomTree().verify());461 462 Function::iterator FI = F->begin();463 BasicBlock *BB0 = &*FI++;464 BasicBlock *BB1 = &*FI++;465 BasicBlock *BB2 = &*FI++;466 BasicBlock *BB3 = &*FI++;467 // Test discards of self-domination update.468 DTU.applyUpdates({{DominatorTree::Delete, BB0, BB0}});469 470 // Delete edge bb0 -> bb3 and push the update twice to verify duplicate471 // entries are discarded.472 std::vector<DominatorTree::UpdateType> Updates;473 Updates.reserve(4);474 Updates.push_back({DominatorTree::Delete, BB0, BB3});475 Updates.push_back({DominatorTree::Delete, BB0, BB3});476 477 // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0.478 Updates.push_back({DominatorTree::Insert, BB1, BB2});479 // Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0.480 Updates.push_back({DominatorTree::Delete, BB0, BB1});481 482 // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.483 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);484 BB0->getTerminator()->eraseFromParent();485 BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);486 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);487 488 // Deletion of a BasicBlock is an immediate event. We remove all uses to the489 // contained Instructions and change the Terminator to "unreachable" when490 // queued for deletion. Its parent is still F until DTU.flushDomTree is491 // called. We don't defer this action because it can cause problems for other492 // transforms or analysis as it's part of the actual CFG. We only defer493 // updates to the DominatorTree. This code will crash if it is placed before494 // the BranchInst::Create() call above.495 bool CallbackFlag = false;496 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));497 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));498 DTU.callbackDeleteBB(BB3, [&](BasicBlock *) { CallbackFlag = true; });499 EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));500 ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));501 EXPECT_EQ(BB3->getParent(), F);502 503 // Verify. Updates to DTU must be applied *after* all changes to the CFG504 // (including block deletion).505 DTU.applyUpdatesPermissive(Updates);506 ASSERT_TRUE(DTU.getDomTree().verify());507 ASSERT_TRUE(DTU.hasPendingUpdates());508 ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());509 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());510 ASSERT_TRUE(DTU.hasPendingDeletedBB());511 ASSERT_TRUE(DTU.getPostDomTree().verify());512 ASSERT_FALSE(DTU.hasPendingUpdates());513 ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());514 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());515 ASSERT_FALSE(DTU.hasPendingDeletedBB());516 ASSERT_EQ(CallbackFlag, true);517}518 519TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) {520 StringRef FuncName = "f";521 StringRef ModuleString = R"(522 define i32 @f() {523 bb0:524 br label %bb1525 bb1:526 ret i32 1527 }528 )";529 // Make the module.530 LLVMContext Context;531 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);532 Function *F = M->getFunction(FuncName);533 534 // Make the DTU.535 DominatorTree DT(*F);536 PostDominatorTree PDT(*F);537 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);538 ASSERT_TRUE(DTU.hasDomTree());539 ASSERT_TRUE(DTU.hasPostDomTree());540 ASSERT_FALSE(DTU.isEager());541 ASSERT_TRUE(DTU.isLazy());542 ASSERT_TRUE(DTU.getDomTree().verify());543 ASSERT_TRUE(DTU.getPostDomTree().verify());544 545 Function::iterator FI = F->begin();546 BasicBlock *BB0 = &*FI++;547 BasicBlock *BB1 = &*FI++;548 549 // Add a block as the new function entry BB. We also link it to BB0.550 BasicBlock *NewEntry =551 BasicBlock::Create(F->getContext(), "new_entry", F, BB0);552 BranchInst::Create(BB0, NewEntry);553 EXPECT_EQ(F->begin()->getName(), NewEntry->getName());554 EXPECT_TRUE(&F->getEntryBlock() == NewEntry);555 556 // Insert the new edge between new_entry -> bb0. Without this the557 // recalculate() call below will not actually recalculate the DT as there558 // are no changes pending and no blocks deleted.559 DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}});560 561 // Changing the Entry BB requires a full recalculation.562 DTU.recalculate(*F);563 ASSERT_TRUE(DTU.getDomTree().verify());564 ASSERT_TRUE(DTU.getPostDomTree().verify());565 566 // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.567 EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);568 NewEntry->getTerminator()->eraseFromParent();569 BranchInst::Create(BB1, NewEntry);570 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);571 572 // Update the DTU. At this point bb0 now has no predecessors but is still a573 // Child of F.574 DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},575 {DominatorTree::Insert, NewEntry, BB1}});576 DTU.flush();577 ASSERT_TRUE(DT.verify());578 ASSERT_TRUE(PDT.verify());579 580 // Now remove bb0 from F.581 ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));582 EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));583 DTU.deleteBB(BB0);584 EXPECT_TRUE(DTU.isBBPendingDeletion(BB0));585 ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));586 EXPECT_EQ(BB0->getParent(), F);587 588 // Perform a full recalculation of the DTU. It is not necessary here but we589 // do this to test the case when there are no pending DT updates but there are590 // pending deleted BBs.591 ASSERT_TRUE(DTU.hasPendingDeletedBB());592 DTU.recalculate(*F);593 ASSERT_FALSE(DTU.hasPendingDeletedBB());594}595 596TEST(DomTreeUpdater, LazyUpdateStepTest) {597 // This test focus on testing a DTU holding both trees applying multiple598 // updates and DT/PDT not flushed together.599 StringRef FuncName = "f";600 StringRef ModuleString = R"(601 define i32 @f(i32 %i, i32 *%p) {602 bb0:603 store i32 %i, i32 *%p604 switch i32 %i, label %bb1 [605 i32 0, label %bb1606 i32 1, label %bb2607 i32 2, label %bb3608 i32 3, label %bb1609 ]610 bb1:611 ret i32 1612 bb2:613 ret i32 2614 bb3:615 ret i32 3616 }617 )";618 // Make the module.619 LLVMContext Context;620 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);621 Function *F = M->getFunction(FuncName);622 623 // Make the DomTreeUpdater.624 DominatorTree DT(*F);625 PostDominatorTree PDT(*F);626 DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);627 628 ASSERT_TRUE(DTU.hasDomTree());629 ASSERT_TRUE(DTU.hasPostDomTree());630 ASSERT_FALSE(DTU.isEager());631 ASSERT_TRUE(DTU.isLazy());632 ASSERT_TRUE(DTU.getDomTree().verify());633 ASSERT_TRUE(DTU.getPostDomTree().verify());634 ASSERT_FALSE(DTU.hasPendingUpdates());635 636 Function::iterator FI = F->begin();637 BasicBlock *BB0 = &*FI++;638 FI++;639 BasicBlock *BB2 = &*FI++;640 BasicBlock *BB3 = &*FI++;641 SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());642 ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";643 644 // Delete edge bb0 -> bb3.645 std::vector<DominatorTree::UpdateType> Updates;646 Updates.reserve(1);647 Updates.push_back({DominatorTree::Delete, BB0, BB3});648 649 // CFG Change: remove edge bb0 -> bb3.650 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 5u);651 BB3->removePredecessor(BB0);652 for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {653 if (i->getCaseIndex() == 2) {654 SI->removeCase(i);655 break;656 }657 }658 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);659 // Deletion of a BasicBlock is an immediate event. We remove all uses to the660 // contained Instructions and change the Terminator to "unreachable" when661 // queued for deletion.662 ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));663 EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));664 DTU.applyUpdates(Updates);665 666 // Only flush DomTree.667 ASSERT_TRUE(DTU.getDomTree().verify());668 ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());669 ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());670 671 ASSERT_EQ(BB3->getParent(), F);672 DTU.deleteBB(BB3);673 674 Updates.clear();675 676 // Remove all case branch to BB2 to test Eager recalculation.677 // Code section from llvm::ConstantFoldTerminator678 for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {679 if (i->getCaseSuccessor() == BB2) {680 // Remove this entry.681 BB2->removePredecessor(BB0);682 i = SI->removeCase(i);683 e = SI->case_end();684 Updates.push_back({DominatorTree::Delete, BB0, BB2});685 } else686 ++i;687 }688 689 DTU.applyUpdatesPermissive(Updates);690 // flush PostDomTree691 ASSERT_TRUE(DTU.getPostDomTree().verify());692 ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());693 ASSERT_TRUE(DTU.hasPendingDomTreeUpdates());694 // flush both trees695 DTU.flush();696 ASSERT_TRUE(DT.verify());697}698 699TEST(DomTreeUpdater, NoTreeTest) {700 StringRef FuncName = "f";701 StringRef ModuleString = R"(702 define i32 @f() {703 bb0:704 ret i32 0705 }706 )";707 // Make the module.708 LLVMContext Context;709 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);710 Function *F = M->getFunction(FuncName);711 712 // Make the DTU.713 DomTreeUpdater DTU(nullptr, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);714 ASSERT_FALSE(DTU.hasDomTree());715 ASSERT_FALSE(DTU.hasPostDomTree());716 Function::iterator FI = F->begin();717 BasicBlock *BB0 = &*FI++;718 // Test whether PendingDeletedBB is flushed after the recalculation.719 DTU.deleteBB(BB0);720 ASSERT_TRUE(DTU.hasPendingDeletedBB());721 DTU.recalculate(*F);722 ASSERT_FALSE(DTU.hasPendingDeletedBB());723}724 725TEST(DomTreeUpdater, LazyUpdateDeduplicationTest) {726 StringRef FuncName = "f";727 StringRef ModuleString = R"(728 define i32 @f() {729 bb0:730 br label %bb1731 bb1:732 ret i32 1733 bb2:734 ret i32 1735 }736 )";737 // Make the module.738 LLVMContext Context;739 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);740 Function *F = M->getFunction(FuncName);741 742 // Make the DTU.743 DominatorTree DT(*F);744 DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);745 ASSERT_TRUE(DTU.getDomTree().verify());746 747 Function::iterator FI = F->begin();748 BasicBlock *BB0 = &*FI++;749 BasicBlock *BB1 = &*FI++;750 BasicBlock *BB2 = &*FI++;751 752 // CFG Change: remove bb0 -> bb1 and add back bb0 -> bb1.753 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);754 BB0->getTerminator()->eraseFromParent();755 BranchInst::Create(BB1, BB0);756 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);757 758 // Update the DTU and simulate duplicates.759 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1},760 {DominatorTree::Delete, BB0, BB1},761 {DominatorTree::Insert, BB0, BB1},762 {DominatorTree::Insert, BB0, BB1},763 {DominatorTree::Insert, BB0, BB1}});764 765 // The above operations result in a no-op.766 ASSERT_FALSE(DTU.hasPendingUpdates());767 768 // Update the DTU. Simulate an invalid update.769 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}});770 ASSERT_FALSE(DTU.hasPendingUpdates());771 772 // CFG Change: remove bb0 -> bb1.773 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);774 BB0->getTerminator()->eraseFromParent();775 776 // Update the DTU and simulate invalid updates.777 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1},778 {DominatorTree::Insert, BB0, BB1},779 {DominatorTree::Delete, BB0, BB1},780 {DominatorTree::Insert, BB0, BB1},781 {DominatorTree::Insert, BB0, BB1}});782 ASSERT_TRUE(DTU.hasPendingUpdates());783 784 // CFG Change: add bb0 -> bb2.785 BranchInst::Create(BB2, BB0);786 EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);787 DTU.applyUpdates({{DominatorTree::Insert, BB0, BB2}});788 ASSERT_TRUE(DTU.getDomTree().verify());789}790 791TEST(DomTreeUpdater, CriticalEdgeSplitTest) {792 StringRef FuncName = "f";793 StringRef ModuleString = R"(794declare void @use1(i32)795 796define void @f(i32 %i, i1 %c) {797entry:798 %A = icmp eq i32 %i, 0 ; <i1> [#uses=1]799 br i1 %A, label %brtrue, label %brfalse800 801brtrue: ; preds = %entry802 call void @use1( i32 %i )803 br label %brfalse804 805brfalse: ; preds = %brtrue, %entry806 call void @use1( i32 %i )807 ret void808}809 )";810 // Make the module.811 LLVMContext Context;812 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);813 Function *F = M->getFunction(FuncName);814 815 // Make the DTU.816 DominatorTree DT(*F);817 DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);818 ASSERT_TRUE(DTU.getDomTree().verify());819 820 CriticalEdgeSplittingOptions Opts;821 SplitAllCriticalEdges(*F, Opts);822 823 Function::iterator FI = F->begin();824 BasicBlock *BBEntry = &*FI++;825 BasicBlock *SplitB = &*FI++;826 [[maybe_unused]] BasicBlock *BBTrue = &*FI++;827 BasicBlock *BBFalse = &*FI++;828 DTU.splitCriticalEdge(BBEntry, BBFalse, SplitB);829 DominatorTree NewDT(*F);830 ASSERT_FALSE(NewDT.compare(DTU.getDomTree()));831}832