1144 lines · cpp
1//===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants 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 <random>10#include "llvm/Analysis/PostDominators.h"11#include "llvm/Analysis/IteratedDominanceFrontier.h"12#include "llvm/AsmParser/Parser.h"13#include "llvm/IR/Constants.h"14#include "llvm/IR/Dominators.h"15#include "llvm/IR/Instructions.h"16#include "llvm/IR/LLVMContext.h"17#include "llvm/IR/Module.h"18#include "llvm/Support/SourceMgr.h"19#include "CFGBuilder.h"20#include "gtest/gtest.h"21 22using namespace llvm;23 24 25/// Build the dominator tree for the function and run the Test.26static void runWithDomTree(27 Module &M, StringRef FuncName,28 function_ref<void(Function &F, DominatorTree *DT, PostDominatorTree *PDT)>29 Test) {30 auto *F = M.getFunction(FuncName);31 ASSERT_NE(F, nullptr) << "Could not find " << FuncName;32 // Compute the dominator tree for the function.33 DominatorTree DT(*F);34 PostDominatorTree PDT(*F);35 Test(*F, &DT, &PDT);36}37 38static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,39 StringRef ModuleStr) {40 SMDiagnostic Err;41 std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);42 assert(M && "Bad assembly?");43 return M;44}45 46TEST(DominatorTree, PHIs) {47 StringRef ModuleString = R"(48 define void @f() {49 bb1:50 br label %bb151 bb2:52 %a = phi i32 [0, %bb1], [1, %bb2]53 %b = phi i32 [2, %bb1], [%a, %bb2]54 br label %bb255 };56 )";57 58 // Parse the module.59 LLVMContext Context;60 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);61 62 runWithDomTree(*M, "f",63 [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {64 auto FI = F.begin();65 ++FI;66 BasicBlock *BB2 = &*FI;67 auto BI = BB2->begin();68 Instruction *PhiA = &*BI++;69 Instruction *PhiB = &*BI;70 71 // Phis are thought to execute "instantly, together".72 EXPECT_TRUE(DT->dominates(PhiA, PhiB));73 EXPECT_TRUE(DT->dominates(PhiB, PhiA));74 });75}76 77TEST(DominatorTree, Unreachable) {78 StringRef ModuleString =79 "declare i32 @g()\n"80 "define void @f(i32 %x) personality i32 ()* @g {\n"81 "bb0:\n"82 " %y1 = add i32 %x, 1\n"83 " %y2 = add i32 %x, 1\n"84 " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n"85 "bb1:\n"86 " %y4 = add i32 %x, 1\n"87 " br label %bb4\n"88 "bb2:\n"89 " %y5 = landingpad i32\n"90 " cleanup\n"91 " br label %bb4\n"92 "bb3:\n"93 " %y6 = add i32 %x, 1\n"94 " %y7 = add i32 %x, 1\n"95 " ret void\n"96 "bb4:\n"97 " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n"98 " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n"99 " ret void\n"100 "}\n";101 102 // Parse the module.103 LLVMContext Context;104 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);105 106 runWithDomTree(107 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {108 Function::iterator FI = F.begin();109 110 BasicBlock *BB0 = &*FI++;111 BasicBlock::iterator BBI = BB0->begin();112 Instruction *Y1 = &*BBI++;113 Instruction *Y2 = &*BBI++;114 Instruction *Y3 = &*BBI++;115 116 BasicBlock *BB1 = &*FI++;117 BBI = BB1->begin();118 Instruction *Y4 = &*BBI++;119 120 BasicBlock *BB2 = &*FI++;121 BBI = BB2->begin();122 Instruction *Y5 = &*BBI++;123 124 BasicBlock *BB3 = &*FI++;125 BBI = BB3->begin();126 Instruction *Y6 = &*BBI++;127 Instruction *Y7 = &*BBI++;128 129 BasicBlock *BB4 = &*FI++;130 BBI = BB4->begin();131 Instruction *Y8 = &*BBI++;132 Instruction *Y9 = &*BBI++;133 134 // Reachability135 EXPECT_TRUE(DT->isReachableFromEntry(BB0));136 EXPECT_TRUE(DT->isReachableFromEntry(BB1));137 EXPECT_TRUE(DT->isReachableFromEntry(BB2));138 EXPECT_FALSE(DT->isReachableFromEntry(BB3));139 EXPECT_TRUE(DT->isReachableFromEntry(BB4));140 141 // BB dominance142 EXPECT_TRUE(DT->dominates(BB0, BB0));143 EXPECT_TRUE(DT->dominates(BB0, BB1));144 EXPECT_TRUE(DT->dominates(BB0, BB2));145 EXPECT_TRUE(DT->dominates(BB0, BB3));146 EXPECT_TRUE(DT->dominates(BB0, BB4));147 148 EXPECT_FALSE(DT->dominates(BB1, BB0));149 EXPECT_TRUE(DT->dominates(BB1, BB1));150 EXPECT_FALSE(DT->dominates(BB1, BB2));151 EXPECT_TRUE(DT->dominates(BB1, BB3));152 EXPECT_FALSE(DT->dominates(BB1, BB4));153 154 EXPECT_FALSE(DT->dominates(BB2, BB0));155 EXPECT_FALSE(DT->dominates(BB2, BB1));156 EXPECT_TRUE(DT->dominates(BB2, BB2));157 EXPECT_TRUE(DT->dominates(BB2, BB3));158 EXPECT_FALSE(DT->dominates(BB2, BB4));159 160 EXPECT_FALSE(DT->dominates(BB3, BB0));161 EXPECT_FALSE(DT->dominates(BB3, BB1));162 EXPECT_FALSE(DT->dominates(BB3, BB2));163 EXPECT_TRUE(DT->dominates(BB3, BB3));164 EXPECT_FALSE(DT->dominates(BB3, BB4));165 166 // BB proper dominance167 EXPECT_FALSE(DT->properlyDominates(BB0, BB0));168 EXPECT_TRUE(DT->properlyDominates(BB0, BB1));169 EXPECT_TRUE(DT->properlyDominates(BB0, BB2));170 EXPECT_TRUE(DT->properlyDominates(BB0, BB3));171 172 EXPECT_FALSE(DT->properlyDominates(BB1, BB0));173 EXPECT_FALSE(DT->properlyDominates(BB1, BB1));174 EXPECT_FALSE(DT->properlyDominates(BB1, BB2));175 EXPECT_TRUE(DT->properlyDominates(BB1, BB3));176 177 EXPECT_FALSE(DT->properlyDominates(BB2, BB0));178 EXPECT_FALSE(DT->properlyDominates(BB2, BB1));179 EXPECT_FALSE(DT->properlyDominates(BB2, BB2));180 EXPECT_TRUE(DT->properlyDominates(BB2, BB3));181 182 EXPECT_FALSE(DT->properlyDominates(BB3, BB0));183 EXPECT_FALSE(DT->properlyDominates(BB3, BB1));184 EXPECT_FALSE(DT->properlyDominates(BB3, BB2));185 EXPECT_FALSE(DT->properlyDominates(BB3, BB3));186 187 // Instruction dominance in the same reachable BB188 EXPECT_FALSE(DT->dominates(Y1, Y1));189 EXPECT_TRUE(DT->dominates(Y1, Y2));190 EXPECT_FALSE(DT->dominates(Y2, Y1));191 EXPECT_FALSE(DT->dominates(Y2, Y2));192 193 // Instruction dominance in the same unreachable BB194 EXPECT_TRUE(DT->dominates(Y6, Y6));195 EXPECT_TRUE(DT->dominates(Y6, Y7));196 EXPECT_TRUE(DT->dominates(Y7, Y6));197 EXPECT_TRUE(DT->dominates(Y7, Y7));198 199 // Invoke200 EXPECT_TRUE(DT->dominates(Y3, Y4));201 EXPECT_FALSE(DT->dominates(Y3, Y5));202 203 // Phi204 EXPECT_TRUE(DT->dominates(Y2, Y9));205 EXPECT_FALSE(DT->dominates(Y3, Y9));206 EXPECT_FALSE(DT->dominates(Y8, Y9));207 208 // Anything dominates unreachable209 EXPECT_TRUE(DT->dominates(Y1, Y6));210 EXPECT_TRUE(DT->dominates(Y3, Y6));211 212 // Unreachable doesn't dominate reachable213 EXPECT_FALSE(DT->dominates(Y6, Y1));214 215 // Instruction, BB dominance216 EXPECT_FALSE(DT->dominates(Y1, BB0));217 EXPECT_TRUE(DT->dominates(Y1, BB1));218 EXPECT_TRUE(DT->dominates(Y1, BB2));219 EXPECT_TRUE(DT->dominates(Y1, BB3));220 EXPECT_TRUE(DT->dominates(Y1, BB4));221 222 EXPECT_FALSE(DT->dominates(Y3, BB0));223 EXPECT_TRUE(DT->dominates(Y3, BB1));224 EXPECT_FALSE(DT->dominates(Y3, BB2));225 EXPECT_TRUE(DT->dominates(Y3, BB3));226 EXPECT_FALSE(DT->dominates(Y3, BB4));227 228 EXPECT_TRUE(DT->dominates(Y6, BB3));229 230 // Post dominance.231 EXPECT_TRUE(PDT->dominates(BB0, BB0));232 EXPECT_FALSE(PDT->dominates(BB1, BB0));233 EXPECT_FALSE(PDT->dominates(BB2, BB0));234 EXPECT_FALSE(PDT->dominates(BB3, BB0));235 EXPECT_TRUE(PDT->dominates(BB4, BB1));236 237 // Dominance descendants.238 SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs;239 240 DT->getDescendants(BB0, DominatedBBs);241 PDT->getDescendants(BB0, PostDominatedBBs);242 EXPECT_EQ(DominatedBBs.size(), 4UL);243 EXPECT_EQ(PostDominatedBBs.size(), 1UL);244 245 // BB3 is unreachable. It should have no dominators nor postdominators.246 DominatedBBs.clear();247 PostDominatedBBs.clear();248 DT->getDescendants(BB3, DominatedBBs);249 DT->getDescendants(BB3, PostDominatedBBs);250 EXPECT_EQ(DominatedBBs.size(), 0UL);251 EXPECT_EQ(PostDominatedBBs.size(), 0UL);252 253 // Check DFS Numbers before254 DT->updateDFSNumbers();255 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL);256 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL);257 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL);258 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL);259 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL);260 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL);261 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL);262 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL);263 264 // Check levels before265 EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U);266 EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U);267 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U);268 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U);269 270 // Reattach block 3 to block 1 and recalculate271 BB1->getTerminator()->eraseFromParent();272 BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1);273 DT->recalculate(F);274 275 // Check DFS Numbers after276 DT->updateDFSNumbers();277 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL);278 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL);279 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL);280 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL);281 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL);282 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL);283 EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL);284 EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL);285 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL);286 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL);287 288 // Check levels after289 EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U);290 EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U);291 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U);292 EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U);293 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U);294 295 // Change root node296 EXPECT_TRUE(DT->verify());297 BasicBlock *NewEntry =298 BasicBlock::Create(F.getContext(), "new_entry", &F, BB0);299 BranchInst::Create(BB0, NewEntry);300 EXPECT_EQ(F.begin()->getName(), NewEntry->getName());301 EXPECT_TRUE(&F.getEntryBlock() == NewEntry);302 DT->setNewRoot(NewEntry);303 EXPECT_TRUE(DT->verify());304 });305}306 307TEST(DominatorTree, NonUniqueEdges) {308 StringRef ModuleString =309 "define i32 @f(i32 %i, i32 *%p) {\n"310 "bb0:\n"311 " store i32 %i, i32 *%p\n"312 " switch i32 %i, label %bb2 [\n"313 " i32 0, label %bb1\n"314 " i32 1, label %bb1\n"315 " ]\n"316 " bb1:\n"317 " ret i32 1\n"318 " bb2:\n"319 " ret i32 4\n"320 "}\n";321 322 // Parse the module.323 LLVMContext Context;324 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);325 326 runWithDomTree(327 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {328 Function::iterator FI = F.begin();329 330 BasicBlock *BB0 = &*FI++;331 BasicBlock *BB1 = &*FI++;332 BasicBlock *BB2 = &*FI++;333 334 const Instruction *TI = BB0->getTerminator();335 assert(TI->getNumSuccessors() == 3 && "Switch has three successors");336 337 BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0));338 assert(Edge_BB0_BB2.getEnd() == BB2 &&339 "Default label is the 1st successor");340 341 BasicBlockEdge Edge_BB0_BB1_a(BB0, TI->getSuccessor(1));342 assert(Edge_BB0_BB1_a.getEnd() == BB1 && "BB1 is the 2nd successor");343 344 BasicBlockEdge Edge_BB0_BB1_b(BB0, TI->getSuccessor(2));345 assert(Edge_BB0_BB1_b.getEnd() == BB1 && "BB1 is the 3rd successor");346 347 EXPECT_TRUE(DT->dominates(Edge_BB0_BB2, BB2));348 EXPECT_FALSE(DT->dominates(Edge_BB0_BB2, BB1));349 350 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB1));351 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB1));352 353 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB2));354 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2));355 });356}357 358// Verify that the PDT is correctly updated in case an edge removal results359// in a new unreachable CFG node. Also make sure that the updated PDT is the360// same as a freshly recalculated one.361//362// For the following input code and initial PDT:363//364// CFG PDT365//366// A Exit367// | |368// _B D369// / | \ |370// ^ v \ B371// \ / D / \372// C \ C A373// v374// Exit375//376// we verify that CFG' and PDT-updated is obtained after removal of edge C -> B.377//378// CFG' PDT-updated379//380// A Exit381// | / | \382// B C B D383// | \ |384// v \ A385// / D386// C \387// | \388// unreachable Exit389//390// Both the blocks that end with ret and with unreachable become trivial391// PostDominatorTree roots, as they have no successors.392//393TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) {394 StringRef ModuleString =395 "define void @f() {\n"396 "A:\n"397 " br label %B\n"398 "B:\n"399 " br i1 undef, label %D, label %C\n"400 "C:\n"401 " br label %B\n"402 "D:\n"403 " ret void\n"404 "}\n";405 406 // Parse the module.407 LLVMContext Context;408 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);409 410 runWithDomTree(411 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {412 Function::iterator FI = F.begin();413 414 FI++;415 BasicBlock *B = &*FI++;416 BasicBlock *C = &*FI++;417 BasicBlock *D = &*FI++;418 419 ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));420 EXPECT_TRUE(DT->verify());421 EXPECT_TRUE(PDT->verify());422 423 C->getTerminator()->eraseFromParent();424 new UnreachableInst(C->getContext(), C);425 426 DT->deleteEdge(C, B);427 PDT->deleteEdge(C, B);428 429 EXPECT_TRUE(DT->verify());430 EXPECT_TRUE(PDT->verify());431 432 EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));433 EXPECT_NE(PDT->getNode(C), nullptr);434 435 DominatorTree NDT(F);436 EXPECT_EQ(DT->compare(NDT), 0);437 438 PostDominatorTree NPDT(F);439 EXPECT_EQ(PDT->compare(NPDT), 0);440 });441}442 443// Verify that the PDT is correctly updated in case an edge removal results444// in an infinite loop. Also make sure that the updated PDT is the445// same as a freshly recalculated one.446//447// Test case:448//449// CFG PDT450//451// A Exit452// | |453// _B D454// / | \ |455// ^ v \ B456// \ / D / \457// C \ C A458// / \ v459// ^ v Exit460// \_/461//462// After deleting the edge C->B, C is part of an infinite reverse-unreachable463// loop:464//465// CFG' PDT'466//467// A Exit468// | / | \469// B C B D470// | \ |471// v \ A472// / D473// C \474// / \ v475// ^ v Exit476// \_/477//478// As C now becomes reverse-unreachable, it forms a new non-trivial root and479// gets connected to the virtual exit.480// D does not postdominate B anymore, because there are two forward paths from481// B to the virtual exit:482// - B -> C -> VirtualExit483// - B -> D -> VirtualExit.484//485TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) {486 StringRef ModuleString =487 "define void @f() {\n"488 "A:\n"489 " br label %B\n"490 "B:\n"491 " br i1 undef, label %D, label %C\n"492 "C:\n"493 " switch i32 undef, label %C [\n"494 " i32 0, label %B\n"495 " ]\n"496 "D:\n"497 " ret void\n"498 "}\n";499 500 // Parse the module.501 LLVMContext Context;502 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);503 504 runWithDomTree(505 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {506 Function::iterator FI = F.begin();507 508 FI++;509 BasicBlock *B = &*FI++;510 BasicBlock *C = &*FI++;511 BasicBlock *D = &*FI++;512 513 ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));514 EXPECT_TRUE(DT->verify());515 EXPECT_TRUE(PDT->verify());516 517 auto SwitchC = cast<SwitchInst>(C->getTerminator());518 SwitchC->removeCase(SwitchC->case_begin());519 DT->deleteEdge(C, B);520 EXPECT_TRUE(DT->verify());521 PDT->deleteEdge(C, B);522 EXPECT_TRUE(PDT->verify());523 524 EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));525 EXPECT_NE(PDT->getNode(C), nullptr);526 527 DominatorTree NDT(F);528 EXPECT_EQ(DT->compare(NDT), 0);529 530 PostDominatorTree NPDT(F);531 EXPECT_EQ(PDT->compare(NPDT), 0);532 });533}534 535// Verify that the PDT is correctly updated in case an edge removal results536// in an infinite loop.537//538// Test case:539//540// CFG PDT541//542// A Exit543// | / | \544// B-- C2 B D545// | \ / |546// v \ C A547// / D548// C--C2 \549// / \ \ v550// ^ v --Exit551// \_/552//553// After deleting the edge C->E, C is part of an infinite reverse-unreachable554// loop:555//556// CFG' PDT'557//558// A Exit559// | / | \560// B C B D561// | \ |562// v \ A563// / D564// C \565// / \ v566// ^ v Exit567// \_/568//569// In PDT, D does not post-dominate B. After the edge C -> C2 is removed,570// C becomes a new nontrivial PDT root.571//572TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) {573 StringRef ModuleString =574 "define void @f() {\n"575 "A:\n"576 " br label %B\n"577 "B:\n"578 " br i1 undef, label %D, label %C\n"579 "C:\n"580 " switch i32 undef, label %C [\n"581 " i32 0, label %C2\n"582 " ]\n"583 "C2:\n"584 " ret void\n"585 "D:\n"586 " ret void\n"587 "}\n";588 589 // Parse the module.590 LLVMContext Context;591 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);592 593 runWithDomTree(594 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {595 Function::iterator FI = F.begin();596 597 FI++;598 BasicBlock *B = &*FI++;599 BasicBlock *C = &*FI++;600 BasicBlock *C2 = &*FI++;601 BasicBlock *D = &*FI++;602 603 EXPECT_TRUE(DT->verify());604 EXPECT_TRUE(PDT->verify());605 606 auto SwitchC = cast<SwitchInst>(C->getTerminator());607 SwitchC->removeCase(SwitchC->case_begin());608 DT->deleteEdge(C, C2);609 PDT->deleteEdge(C, C2);610 611 EXPECT_EQ(DT->getNode(C2), nullptr);612 PDT->eraseNode(C2);613 C2->eraseFromParent();614 615 EXPECT_TRUE(DT->verify());616 EXPECT_TRUE(PDT->verify());617 618 EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));619 EXPECT_NE(PDT->getNode(C), nullptr);620 621 DominatorTree NDT(F);622 EXPECT_EQ(DT->compare(NDT), 0);623 624 PostDominatorTree NPDT(F);625 EXPECT_EQ(PDT->compare(NPDT), 0);626 });627}628 629// Verify that the IDF returns blocks in a deterministic way.630//631// Test case:632//633// CFG634//635// (A)636// / \637// / \638// (B) (C)639// |\ /|640// | X |641// |/ \|642// (D) (E)643//644// IDF for block B is {D, E}, and the order of blocks in this list is defined by645// their 1) level in dom-tree and 2) DFSIn number if the level is the same.646//647TEST(DominatorTree, IDFDeterminismTest) {648 StringRef ModuleString =649 "define void @f() {\n"650 "A:\n"651 " br i1 undef, label %B, label %C\n"652 "B:\n"653 " br i1 undef, label %D, label %E\n"654 "C:\n"655 " br i1 undef, label %D, label %E\n"656 "D:\n"657 " ret void\n"658 "E:\n"659 " ret void\n"660 "}\n";661 662 // Parse the module.663 LLVMContext Context;664 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);665 666 runWithDomTree(667 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {668 Function::iterator FI = F.begin();669 670 BasicBlock *A = &*FI++;671 BasicBlock *B = &*FI++;672 BasicBlock *C = &*FI++;673 BasicBlock *D = &*FI++;674 BasicBlock *E = &*FI++;675 (void)C;676 677 DT->updateDFSNumbers();678 ForwardIDFCalculator IDF(*DT);679 SmallPtrSet<BasicBlock *, 1> DefBlocks;680 DefBlocks.insert(B);681 IDF.setDefiningBlocks(DefBlocks);682 683 SmallVector<BasicBlock *, 32> IDFBlocks;684 IDF.resetLiveInBlocks();685 IDF.calculate(IDFBlocks);686 687 688 EXPECT_EQ(IDFBlocks.size(), 2UL);689 EXPECT_EQ(DT->getNode(A)->getDFSNumIn(), 0UL);690 EXPECT_EQ(IDFBlocks[0], D);691 EXPECT_EQ(IDFBlocks[1], E);692 EXPECT_TRUE(DT->getNode(IDFBlocks[0])->getDFSNumIn() <693 DT->getNode(IDFBlocks[1])->getDFSNumIn());694 });695}696 697namespace {698const auto Insert = CFGBuilder::ActionKind::Insert;699const auto Delete = CFGBuilder::ActionKind::Delete;700 701bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) {702 return std::tie(A.Action, A.Edge.From, A.Edge.To) <703 std::tie(B.Action, B.Edge.From, B.Edge.To);704}705} // namespace706 707TEST(DominatorTree, InsertReachable) {708 CFGHolder Holder;709 std::vector<CFGBuilder::Arc> Arcs = {710 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},711 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};712 713 std::vector<CFGBuilder::Update> Updates = {{Insert, {"12", "10"}},714 {Insert, {"10", "9"}},715 {Insert, {"7", "6"}},716 {Insert, {"7", "5"}}};717 CFGBuilder B(Holder.F, Arcs, Updates);718 DominatorTree DT(*Holder.F);719 EXPECT_TRUE(DT.verify());720 PostDominatorTree PDT(*Holder.F);721 EXPECT_TRUE(PDT.verify());722 723 std::optional<CFGBuilder::Update> LastUpdate;724 while ((LastUpdate = B.applyUpdate())) {725 EXPECT_EQ(LastUpdate->Action, Insert);726 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);727 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);728 DT.insertEdge(From, To);729 EXPECT_TRUE(DT.verify());730 PDT.insertEdge(From, To);731 EXPECT_TRUE(PDT.verify());732 }733}734 735TEST(DominatorTree, InsertReachable2) {736 CFGHolder Holder;737 std::vector<CFGBuilder::Arc> Arcs = {738 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},739 {"7", "5"}, {"2", "8"}, {"8", "11"}, {"11", "12"}, {"12", "10"},740 {"10", "9"}, {"9", "10"}};741 742 std::vector<CFGBuilder::Update> Updates = {{Insert, {"10", "7"}}};743 CFGBuilder B(Holder.F, Arcs, Updates);744 DominatorTree DT(*Holder.F);745 EXPECT_TRUE(DT.verify());746 PostDominatorTree PDT(*Holder.F);747 EXPECT_TRUE(PDT.verify());748 749 std::optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();750 EXPECT_TRUE(LastUpdate);751 752 EXPECT_EQ(LastUpdate->Action, Insert);753 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);754 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);755 DT.insertEdge(From, To);756 EXPECT_TRUE(DT.verify());757 PDT.insertEdge(From, To);758 EXPECT_TRUE(PDT.verify());759}760 761TEST(DominatorTree, InsertUnreachable) {762 CFGHolder Holder;763 std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"},764 {"5", "6"}, {"5", "7"}, {"3", "8"},765 {"9", "10"}, {"11", "12"}};766 767 std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}},768 {Insert, {"8", "9"}},769 {Insert, {"10", "12"}},770 {Insert, {"10", "11"}}};771 CFGBuilder B(Holder.F, Arcs, Updates);772 DominatorTree DT(*Holder.F);773 EXPECT_TRUE(DT.verify());774 PostDominatorTree PDT(*Holder.F);775 EXPECT_TRUE(PDT.verify());776 777 std::optional<CFGBuilder::Update> LastUpdate;778 while ((LastUpdate = B.applyUpdate())) {779 EXPECT_EQ(LastUpdate->Action, Insert);780 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);781 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);782 DT.insertEdge(From, To);783 EXPECT_TRUE(DT.verify());784 PDT.insertEdge(From, To);785 EXPECT_TRUE(PDT.verify());786 }787}788 789TEST(DominatorTree, InsertFromUnreachable) {790 CFGHolder Holder;791 std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}};792 793 std::vector<CFGBuilder::Update> Updates = {{Insert, {"3", "5"}}};794 CFGBuilder B(Holder.F, Arcs, Updates);795 PostDominatorTree PDT(*Holder.F);796 EXPECT_TRUE(PDT.verify());797 798 std::optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();799 EXPECT_TRUE(LastUpdate);800 801 EXPECT_EQ(LastUpdate->Action, Insert);802 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);803 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);804 PDT.insertEdge(From, To);805 EXPECT_TRUE(PDT.verify());806 EXPECT_EQ(PDT.root_size(), 2UL);807 // Make sure we can use a const pointer with getNode.808 const BasicBlock *BB5 = B.getOrAddBlock("5");809 EXPECT_NE(PDT.getNode(BB5), nullptr);810}811 812TEST(DominatorTree, InsertMixed) {813 CFGHolder Holder;814 std::vector<CFGBuilder::Arc> Arcs = {815 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"},816 {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}};817 818 std::vector<CFGBuilder::Update> Updates = {819 {Insert, {"4", "5"}}, {Insert, {"2", "5"}}, {Insert, {"10", "9"}},820 {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}},821 {Insert, {"7", "5"}}};822 CFGBuilder B(Holder.F, Arcs, Updates);823 DominatorTree DT(*Holder.F);824 EXPECT_TRUE(DT.verify());825 PostDominatorTree PDT(*Holder.F);826 EXPECT_TRUE(PDT.verify());827 828 std::optional<CFGBuilder::Update> LastUpdate;829 while ((LastUpdate = B.applyUpdate())) {830 EXPECT_EQ(LastUpdate->Action, Insert);831 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);832 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);833 DT.insertEdge(From, To);834 EXPECT_TRUE(DT.verify());835 PDT.insertEdge(From, To);836 EXPECT_TRUE(PDT.verify());837 }838}839 840TEST(DominatorTree, InsertPermut) {841 std::vector<CFGBuilder::Arc> Arcs = {842 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"},843 {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}};844 845 std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}},846 {Insert, {"2", "5"}},847 {Insert, {"10", "9"}},848 {Insert, {"12", "10"}}};849 850 while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) {851 CFGHolder Holder;852 CFGBuilder B(Holder.F, Arcs, Updates);853 DominatorTree DT(*Holder.F);854 EXPECT_TRUE(DT.verify());855 PostDominatorTree PDT(*Holder.F);856 EXPECT_TRUE(PDT.verify());857 858 std::optional<CFGBuilder::Update> LastUpdate;859 while ((LastUpdate = B.applyUpdate())) {860 EXPECT_EQ(LastUpdate->Action, Insert);861 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);862 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);863 DT.insertEdge(From, To);864 EXPECT_TRUE(DT.verify());865 PDT.insertEdge(From, To);866 EXPECT_TRUE(PDT.verify());867 }868 }869}870 871TEST(DominatorTree, DeleteReachable) {872 CFGHolder Holder;873 std::vector<CFGBuilder::Arc> Arcs = {874 {"1", "2"}, {"2", "3"}, {"2", "4"}, {"3", "4"}, {"4", "5"}, {"5", "6"},875 {"5", "7"}, {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}};876 877 std::vector<CFGBuilder::Update> Updates = {878 {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}};879 CFGBuilder B(Holder.F, Arcs, Updates);880 DominatorTree DT(*Holder.F);881 EXPECT_TRUE(DT.verify());882 PostDominatorTree PDT(*Holder.F);883 EXPECT_TRUE(PDT.verify());884 885 std::optional<CFGBuilder::Update> LastUpdate;886 while ((LastUpdate = B.applyUpdate())) {887 EXPECT_EQ(LastUpdate->Action, Delete);888 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);889 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);890 DT.deleteEdge(From, To);891 EXPECT_TRUE(DT.verify());892 PDT.deleteEdge(From, To);893 EXPECT_TRUE(PDT.verify());894 }895}896 897TEST(DominatorTree, DeleteUnreachable) {898 CFGHolder Holder;899 std::vector<CFGBuilder::Arc> Arcs = {900 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},901 {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}};902 903 std::vector<CFGBuilder::Update> Updates = {904 {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}};905 CFGBuilder B(Holder.F, Arcs, Updates);906 DominatorTree DT(*Holder.F);907 EXPECT_TRUE(DT.verify());908 PostDominatorTree PDT(*Holder.F);909 EXPECT_TRUE(PDT.verify());910 911 std::optional<CFGBuilder::Update> LastUpdate;912 while ((LastUpdate = B.applyUpdate())) {913 EXPECT_EQ(LastUpdate->Action, Delete);914 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);915 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);916 DT.deleteEdge(From, To);917 EXPECT_TRUE(DT.verify());918 PDT.deleteEdge(From, To);919 EXPECT_TRUE(PDT.verify());920 }921}922 923TEST(DominatorTree, InsertDelete) {924 std::vector<CFGBuilder::Arc> Arcs = {925 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},926 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};927 928 std::vector<CFGBuilder::Update> Updates = {929 {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}},930 {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}},931 {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}},932 {Delete, {"8", "9"}}, {Delete, {"11", "12"}}};933 934 CFGHolder Holder;935 CFGBuilder B(Holder.F, Arcs, Updates);936 DominatorTree DT(*Holder.F);937 EXPECT_TRUE(DT.verify());938 PostDominatorTree PDT(*Holder.F);939 EXPECT_TRUE(PDT.verify());940 941 std::optional<CFGBuilder::Update> LastUpdate;942 while ((LastUpdate = B.applyUpdate())) {943 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);944 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);945 if (LastUpdate->Action == Insert) {946 DT.insertEdge(From, To);947 PDT.insertEdge(From, To);948 } else {949 DT.deleteEdge(From, To);950 PDT.deleteEdge(From, To);951 }952 953 EXPECT_TRUE(DT.verify());954 EXPECT_TRUE(PDT.verify());955 }956}957 958TEST(DominatorTree, InsertDeleteExhaustive) {959 std::vector<CFGBuilder::Arc> Arcs = {960 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},961 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};962 963 std::vector<CFGBuilder::Update> Updates = {964 {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}},965 {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}},966 {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}},967 {Delete, {"8", "9"}}, {Delete, {"11", "12"}}};968 969 std::mt19937 Generator(0);970 for (unsigned i = 0; i < 16; ++i) {971 std::shuffle(Updates.begin(), Updates.end(), Generator);972 CFGHolder Holder;973 CFGBuilder B(Holder.F, Arcs, Updates);974 DominatorTree DT(*Holder.F);975 EXPECT_TRUE(DT.verify());976 PostDominatorTree PDT(*Holder.F);977 EXPECT_TRUE(PDT.verify());978 979 std::optional<CFGBuilder::Update> LastUpdate;980 while ((LastUpdate = B.applyUpdate())) {981 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);982 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);983 if (LastUpdate->Action == Insert) {984 DT.insertEdge(From, To);985 PDT.insertEdge(From, To);986 } else {987 DT.deleteEdge(From, To);988 PDT.deleteEdge(From, To);989 }990 991 EXPECT_TRUE(DT.verify());992 EXPECT_TRUE(PDT.verify());993 }994 }995}996 997TEST(DominatorTree, InsertIntoIrreducible) {998 std::vector<CFGBuilder::Arc> Arcs = {999 {"0", "1"},1000 {"1", "27"}, {"1", "7"},1001 {"10", "18"},1002 {"13", "10"},1003 {"18", "13"}, {"18", "23"},1004 {"23", "13"}, {"23", "24"},1005 {"24", "1"}, {"24", "18"},1006 {"27", "24"}};1007 1008 CFGHolder Holder;1009 CFGBuilder B(Holder.F, Arcs, {{Insert, {"7", "23"}}});1010 DominatorTree DT(*Holder.F);1011 EXPECT_TRUE(DT.verify());1012 1013 B.applyUpdate();1014 BasicBlock *From = B.getOrAddBlock("7");1015 BasicBlock *To = B.getOrAddBlock("23");1016 DT.insertEdge(From, To);1017 1018 EXPECT_TRUE(DT.verify());1019}1020 1021TEST(DominatorTree, EdgeDomination) {1022 StringRef ModuleString = "define i32 @f(i1 %cond) {\n"1023 " bb0:\n"1024 " br i1 %cond, label %bb1, label %bb2\n"1025 " bb1:\n"1026 " br label %bb3\n"1027 " bb2:\n"1028 " br label %bb3\n"1029 " bb3:\n"1030 " ret i32 4"1031 "}\n";1032 1033 // Parse the module.1034 LLVMContext Context;1035 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1036 1037 runWithDomTree(*M, "f",1038 [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {1039 Function::iterator FI = F.begin();1040 1041 BasicBlock *BB0 = &*FI++;1042 BasicBlock *BB1 = &*FI++;1043 BasicBlock *BB2 = &*FI++;1044 BasicBlock *BB3 = &*FI++;1045 1046 BasicBlockEdge E01(BB0, BB1);1047 BasicBlockEdge E02(BB0, BB2);1048 BasicBlockEdge E13(BB1, BB3);1049 BasicBlockEdge E23(BB2, BB3);1050 1051 EXPECT_TRUE(DT->dominates(E01, E01));1052 EXPECT_FALSE(DT->dominates(E01, E02));1053 EXPECT_TRUE(DT->dominates(E01, E13));1054 EXPECT_FALSE(DT->dominates(E01, E23));1055 1056 EXPECT_FALSE(DT->dominates(E02, E01));1057 EXPECT_TRUE(DT->dominates(E02, E02));1058 EXPECT_FALSE(DT->dominates(E02, E13));1059 EXPECT_TRUE(DT->dominates(E02, E23));1060 1061 EXPECT_FALSE(DT->dominates(E13, E01));1062 EXPECT_FALSE(DT->dominates(E13, E02));1063 EXPECT_TRUE(DT->dominates(E13, E13));1064 EXPECT_FALSE(DT->dominates(E13, E23));1065 1066 EXPECT_FALSE(DT->dominates(E23, E01));1067 EXPECT_FALSE(DT->dominates(E23, E02));1068 EXPECT_FALSE(DT->dominates(E23, E13));1069 EXPECT_TRUE(DT->dominates(E23, E23));1070 });1071}1072 1073TEST(DominatorTree, ValueDomination) {1074 StringRef ModuleString = R"(1075 @foo = global i8 01076 define i8 @f(i8 %arg) {1077 ret i8 %arg1078 }1079 )";1080 1081 LLVMContext Context;1082 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1083 1084 runWithDomTree(*M, "f",1085 [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {1086 Argument *A = F.getArg(0);1087 GlobalValue *G = M->getNamedValue("foo");1088 Constant *C = ConstantInt::getNullValue(Type::getInt8Ty(Context));1089 1090 Instruction *I = F.getEntryBlock().getTerminator();1091 EXPECT_TRUE(DT->dominates(A, I));1092 EXPECT_TRUE(DT->dominates(G, I));1093 EXPECT_TRUE(DT->dominates(C, I));1094 1095 const Use &U = I->getOperandUse(0);1096 EXPECT_TRUE(DT->dominates(A, U));1097 EXPECT_TRUE(DT->dominates(G, U));1098 EXPECT_TRUE(DT->dominates(C, U));1099 });1100}1101TEST(DominatorTree, CallBrDomination) {1102 StringRef ModuleString = R"(1103define void @x() {1104 %y = alloca i321105 %w = callbr i32 asm "", "=r,!i"()1106 to label %asm.fallthrough [label %z]1107 1108asm.fallthrough:1109 br label %cleanup1110 1111z:1112 store i32 %w, ptr %y1113 br label %cleanup1114 1115cleanup:1116 ret void1117})";1118 1119 LLVMContext Context;1120 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1121 1122 runWithDomTree(1123 *M, "x", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {1124 Function::iterator FI = F.begin();1125 1126 BasicBlock *Entry = &*FI++;1127 BasicBlock *ASMFallthrough = &*FI++;1128 BasicBlock *Z = &*FI++;1129 1130 EXPECT_TRUE(DT->dominates(Entry, ASMFallthrough));1131 EXPECT_TRUE(DT->dominates(Entry, Z));1132 1133 BasicBlock::iterator BBI = Entry->begin();1134 ++BBI;1135 Instruction &I = *BBI;1136 EXPECT_TRUE(isa<CallBrInst>(I));1137 EXPECT_TRUE(isa<Value>(I));1138 for (const User *U : I.users()) {1139 EXPECT_TRUE(isa<Instruction>(U));1140 EXPECT_TRUE(DT->dominates(cast<Value>(&I), cast<Instruction>(U)));1141 }1142 });1143}1144