1 //===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include <random> 11 #include "llvm/Analysis/PostDominators.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 22 using namespace llvm; 23 24 struct PostDomTree : PostDomTreeBase<BasicBlock> { 25 PostDomTree(Function &F) { recalculate(F); } 26 }; 27 28 /// Build the dominator tree for the function and run the Test. 29 static void runWithDomTree( 30 Module &M, StringRef FuncName, 31 function_ref<void(Function &F, DominatorTree *DT, PostDomTree *PDT)> Test) { 32 auto *F = M.getFunction(FuncName); 33 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 34 // Compute the dominator tree for the function. 35 DominatorTree DT(*F); 36 PostDomTree PDT(*F); 37 Test(*F, &DT, &PDT); 38 } 39 40 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 41 StringRef ModuleStr) { 42 SMDiagnostic Err; 43 std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context); 44 assert(M && "Bad assembly?"); 45 return M; 46 } 47 48 TEST(DominatorTree, Unreachable) { 49 StringRef ModuleString = 50 "declare i32 @g()\n" 51 "define void @f(i32 %x) personality i32 ()* @g {\n" 52 "bb0:\n" 53 " %y1 = add i32 %x, 1\n" 54 " %y2 = add i32 %x, 1\n" 55 " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" 56 "bb1:\n" 57 " %y4 = add i32 %x, 1\n" 58 " br label %bb4\n" 59 "bb2:\n" 60 " %y5 = landingpad i32\n" 61 " cleanup\n" 62 " br label %bb4\n" 63 "bb3:\n" 64 " %y6 = add i32 %x, 1\n" 65 " %y7 = add i32 %x, 1\n" 66 " ret void\n" 67 "bb4:\n" 68 " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n" 69 " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n" 70 " ret void\n" 71 "}\n"; 72 73 // Parse the module. 74 LLVMContext Context; 75 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 76 77 runWithDomTree( 78 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 79 Function::iterator FI = F.begin(); 80 81 BasicBlock *BB0 = &*FI++; 82 BasicBlock::iterator BBI = BB0->begin(); 83 Instruction *Y1 = &*BBI++; 84 Instruction *Y2 = &*BBI++; 85 Instruction *Y3 = &*BBI++; 86 87 BasicBlock *BB1 = &*FI++; 88 BBI = BB1->begin(); 89 Instruction *Y4 = &*BBI++; 90 91 BasicBlock *BB2 = &*FI++; 92 BBI = BB2->begin(); 93 Instruction *Y5 = &*BBI++; 94 95 BasicBlock *BB3 = &*FI++; 96 BBI = BB3->begin(); 97 Instruction *Y6 = &*BBI++; 98 Instruction *Y7 = &*BBI++; 99 100 BasicBlock *BB4 = &*FI++; 101 BBI = BB4->begin(); 102 Instruction *Y8 = &*BBI++; 103 Instruction *Y9 = &*BBI++; 104 105 // Reachability 106 EXPECT_TRUE(DT->isReachableFromEntry(BB0)); 107 EXPECT_TRUE(DT->isReachableFromEntry(BB1)); 108 EXPECT_TRUE(DT->isReachableFromEntry(BB2)); 109 EXPECT_FALSE(DT->isReachableFromEntry(BB3)); 110 EXPECT_TRUE(DT->isReachableFromEntry(BB4)); 111 112 // BB dominance 113 EXPECT_TRUE(DT->dominates(BB0, BB0)); 114 EXPECT_TRUE(DT->dominates(BB0, BB1)); 115 EXPECT_TRUE(DT->dominates(BB0, BB2)); 116 EXPECT_TRUE(DT->dominates(BB0, BB3)); 117 EXPECT_TRUE(DT->dominates(BB0, BB4)); 118 119 EXPECT_FALSE(DT->dominates(BB1, BB0)); 120 EXPECT_TRUE(DT->dominates(BB1, BB1)); 121 EXPECT_FALSE(DT->dominates(BB1, BB2)); 122 EXPECT_TRUE(DT->dominates(BB1, BB3)); 123 EXPECT_FALSE(DT->dominates(BB1, BB4)); 124 125 EXPECT_FALSE(DT->dominates(BB2, BB0)); 126 EXPECT_FALSE(DT->dominates(BB2, BB1)); 127 EXPECT_TRUE(DT->dominates(BB2, BB2)); 128 EXPECT_TRUE(DT->dominates(BB2, BB3)); 129 EXPECT_FALSE(DT->dominates(BB2, BB4)); 130 131 EXPECT_FALSE(DT->dominates(BB3, BB0)); 132 EXPECT_FALSE(DT->dominates(BB3, BB1)); 133 EXPECT_FALSE(DT->dominates(BB3, BB2)); 134 EXPECT_TRUE(DT->dominates(BB3, BB3)); 135 EXPECT_FALSE(DT->dominates(BB3, BB4)); 136 137 // BB proper dominance 138 EXPECT_FALSE(DT->properlyDominates(BB0, BB0)); 139 EXPECT_TRUE(DT->properlyDominates(BB0, BB1)); 140 EXPECT_TRUE(DT->properlyDominates(BB0, BB2)); 141 EXPECT_TRUE(DT->properlyDominates(BB0, BB3)); 142 143 EXPECT_FALSE(DT->properlyDominates(BB1, BB0)); 144 EXPECT_FALSE(DT->properlyDominates(BB1, BB1)); 145 EXPECT_FALSE(DT->properlyDominates(BB1, BB2)); 146 EXPECT_TRUE(DT->properlyDominates(BB1, BB3)); 147 148 EXPECT_FALSE(DT->properlyDominates(BB2, BB0)); 149 EXPECT_FALSE(DT->properlyDominates(BB2, BB1)); 150 EXPECT_FALSE(DT->properlyDominates(BB2, BB2)); 151 EXPECT_TRUE(DT->properlyDominates(BB2, BB3)); 152 153 EXPECT_FALSE(DT->properlyDominates(BB3, BB0)); 154 EXPECT_FALSE(DT->properlyDominates(BB3, BB1)); 155 EXPECT_FALSE(DT->properlyDominates(BB3, BB2)); 156 EXPECT_FALSE(DT->properlyDominates(BB3, BB3)); 157 158 // Instruction dominance in the same reachable BB 159 EXPECT_FALSE(DT->dominates(Y1, Y1)); 160 EXPECT_TRUE(DT->dominates(Y1, Y2)); 161 EXPECT_FALSE(DT->dominates(Y2, Y1)); 162 EXPECT_FALSE(DT->dominates(Y2, Y2)); 163 164 // Instruction dominance in the same unreachable BB 165 EXPECT_TRUE(DT->dominates(Y6, Y6)); 166 EXPECT_TRUE(DT->dominates(Y6, Y7)); 167 EXPECT_TRUE(DT->dominates(Y7, Y6)); 168 EXPECT_TRUE(DT->dominates(Y7, Y7)); 169 170 // Invoke 171 EXPECT_TRUE(DT->dominates(Y3, Y4)); 172 EXPECT_FALSE(DT->dominates(Y3, Y5)); 173 174 // Phi 175 EXPECT_TRUE(DT->dominates(Y2, Y9)); 176 EXPECT_FALSE(DT->dominates(Y3, Y9)); 177 EXPECT_FALSE(DT->dominates(Y8, Y9)); 178 179 // Anything dominates unreachable 180 EXPECT_TRUE(DT->dominates(Y1, Y6)); 181 EXPECT_TRUE(DT->dominates(Y3, Y6)); 182 183 // Unreachable doesn't dominate reachable 184 EXPECT_FALSE(DT->dominates(Y6, Y1)); 185 186 // Instruction, BB dominance 187 EXPECT_FALSE(DT->dominates(Y1, BB0)); 188 EXPECT_TRUE(DT->dominates(Y1, BB1)); 189 EXPECT_TRUE(DT->dominates(Y1, BB2)); 190 EXPECT_TRUE(DT->dominates(Y1, BB3)); 191 EXPECT_TRUE(DT->dominates(Y1, BB4)); 192 193 EXPECT_FALSE(DT->dominates(Y3, BB0)); 194 EXPECT_TRUE(DT->dominates(Y3, BB1)); 195 EXPECT_FALSE(DT->dominates(Y3, BB2)); 196 EXPECT_TRUE(DT->dominates(Y3, BB3)); 197 EXPECT_FALSE(DT->dominates(Y3, BB4)); 198 199 EXPECT_TRUE(DT->dominates(Y6, BB3)); 200 201 // Post dominance. 202 EXPECT_TRUE(PDT->dominates(BB0, BB0)); 203 EXPECT_FALSE(PDT->dominates(BB1, BB0)); 204 EXPECT_FALSE(PDT->dominates(BB2, BB0)); 205 EXPECT_FALSE(PDT->dominates(BB3, BB0)); 206 EXPECT_TRUE(PDT->dominates(BB4, BB1)); 207 208 // Dominance descendants. 209 SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs; 210 211 DT->getDescendants(BB0, DominatedBBs); 212 PDT->getDescendants(BB0, PostDominatedBBs); 213 EXPECT_EQ(DominatedBBs.size(), 4UL); 214 EXPECT_EQ(PostDominatedBBs.size(), 1UL); 215 216 // BB3 is unreachable. It should have no dominators nor postdominators. 217 DominatedBBs.clear(); 218 PostDominatedBBs.clear(); 219 DT->getDescendants(BB3, DominatedBBs); 220 DT->getDescendants(BB3, PostDominatedBBs); 221 EXPECT_EQ(DominatedBBs.size(), 0UL); 222 EXPECT_EQ(PostDominatedBBs.size(), 0UL); 223 224 // Check DFS Numbers before 225 DT->updateDFSNumbers(); 226 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); 227 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL); 228 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); 229 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL); 230 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL); 231 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL); 232 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL); 233 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL); 234 235 // Check levels before 236 EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); 237 EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); 238 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); 239 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); 240 241 // Reattach block 3 to block 1 and recalculate 242 BB1->getTerminator()->eraseFromParent(); 243 BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1); 244 DT->recalculate(F); 245 246 // Check DFS Numbers after 247 DT->updateDFSNumbers(); 248 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); 249 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL); 250 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); 251 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL); 252 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL); 253 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL); 254 EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL); 255 EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL); 256 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL); 257 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL); 258 259 // Check levels after 260 EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); 261 EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); 262 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); 263 EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U); 264 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); 265 266 // Change root node 267 DT->verifyDomTree(); 268 BasicBlock *NewEntry = 269 BasicBlock::Create(F.getContext(), "new_entry", &F, BB0); 270 BranchInst::Create(BB0, NewEntry); 271 EXPECT_EQ(F.begin()->getName(), NewEntry->getName()); 272 EXPECT_TRUE(&F.getEntryBlock() == NewEntry); 273 DT->setNewRoot(NewEntry); 274 DT->verifyDomTree(); 275 }); 276 } 277 278 TEST(DominatorTree, NonUniqueEdges) { 279 StringRef ModuleString = 280 "define i32 @f(i32 %i, i32 *%p) {\n" 281 "bb0:\n" 282 " store i32 %i, i32 *%p\n" 283 " switch i32 %i, label %bb2 [\n" 284 " i32 0, label %bb1\n" 285 " i32 1, label %bb1\n" 286 " ]\n" 287 " bb1:\n" 288 " ret i32 1\n" 289 " bb2:\n" 290 " ret i32 4\n" 291 "}\n"; 292 293 // Parse the module. 294 LLVMContext Context; 295 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 296 297 runWithDomTree( 298 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 299 Function::iterator FI = F.begin(); 300 301 BasicBlock *BB0 = &*FI++; 302 BasicBlock *BB1 = &*FI++; 303 BasicBlock *BB2 = &*FI++; 304 305 const TerminatorInst *TI = BB0->getTerminator(); 306 assert(TI->getNumSuccessors() == 3 && "Switch has three successors"); 307 308 BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0)); 309 assert(Edge_BB0_BB2.getEnd() == BB2 && 310 "Default label is the 1st successor"); 311 312 BasicBlockEdge Edge_BB0_BB1_a(BB0, TI->getSuccessor(1)); 313 assert(Edge_BB0_BB1_a.getEnd() == BB1 && "BB1 is the 2nd successor"); 314 315 BasicBlockEdge Edge_BB0_BB1_b(BB0, TI->getSuccessor(2)); 316 assert(Edge_BB0_BB1_b.getEnd() == BB1 && "BB1 is the 3rd successor"); 317 318 EXPECT_TRUE(DT->dominates(Edge_BB0_BB2, BB2)); 319 EXPECT_FALSE(DT->dominates(Edge_BB0_BB2, BB1)); 320 321 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB1)); 322 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB1)); 323 324 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB2)); 325 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2)); 326 }); 327 } 328 329 namespace { 330 const auto Insert = CFGBuilder::ActionKind::Insert; 331 const auto Delete = CFGBuilder::ActionKind::Delete; 332 333 bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) { 334 return std::tie(A.Action, A.Edge.From, A.Edge.To) < 335 std::tie(B.Action, B.Edge.From, B.Edge.To); 336 } 337 } // namespace 338 339 TEST(DominatorTree, InsertReachable) { 340 CFGHolder Holder; 341 std::vector<CFGBuilder::Arc> Arcs = { 342 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 343 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 344 345 std::vector<CFGBuilder::Update> Updates = {{Insert, {"12", "10"}}, 346 {Insert, {"10", "9"}}, 347 {Insert, {"7", "6"}}, 348 {Insert, {"7", "5"}}}; 349 CFGBuilder B(Holder.F, Arcs, Updates); 350 DominatorTree DT(*Holder.F); 351 EXPECT_TRUE(DT.verify()); 352 PostDomTree PDT(*Holder.F); 353 EXPECT_TRUE(PDT.verify()); 354 355 Optional<CFGBuilder::Update> LastUpdate; 356 while ((LastUpdate = B.applyUpdate())) { 357 EXPECT_EQ(LastUpdate->Action, Insert); 358 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 359 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 360 DT.insertEdge(From, To); 361 EXPECT_TRUE(DT.verify()); 362 PDT.insertEdge(From, To); 363 EXPECT_TRUE(PDT.verify()); 364 } 365 } 366 367 TEST(DominatorTree, InsertReachable2) { 368 CFGHolder Holder; 369 std::vector<CFGBuilder::Arc> Arcs = { 370 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 371 {"7", "5"}, {"2", "8"}, {"8", "11"}, {"11", "12"}, {"12", "10"}, 372 {"10", "9"}, {"9", "10"}}; 373 374 std::vector<CFGBuilder::Update> Updates = {{Insert, {"10", "7"}}}; 375 CFGBuilder B(Holder.F, Arcs, Updates); 376 DominatorTree DT(*Holder.F); 377 EXPECT_TRUE(DT.verify()); 378 PostDomTree PDT(*Holder.F); 379 EXPECT_TRUE(PDT.verify()); 380 381 Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); 382 EXPECT_TRUE(LastUpdate); 383 384 EXPECT_EQ(LastUpdate->Action, Insert); 385 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 386 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 387 DT.insertEdge(From, To); 388 EXPECT_TRUE(DT.verify()); 389 PDT.insertEdge(From, To); 390 EXPECT_TRUE(PDT.verify()); 391 } 392 393 TEST(DominatorTree, InsertUnreachable) { 394 CFGHolder Holder; 395 std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}, 396 {"5", "6"}, {"5", "7"}, {"3", "8"}, 397 {"9", "10"}, {"11", "12"}}; 398 399 std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}}, 400 {Insert, {"8", "9"}}, 401 {Insert, {"10", "12"}}, 402 {Insert, {"10", "11"}}}; 403 CFGBuilder B(Holder.F, Arcs, Updates); 404 DominatorTree DT(*Holder.F); 405 EXPECT_TRUE(DT.verify()); 406 PostDomTree PDT(*Holder.F); 407 EXPECT_TRUE(PDT.verify()); 408 409 Optional<CFGBuilder::Update> LastUpdate; 410 while ((LastUpdate = B.applyUpdate())) { 411 EXPECT_EQ(LastUpdate->Action, Insert); 412 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 413 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 414 DT.insertEdge(From, To); 415 EXPECT_TRUE(DT.verify()); 416 PDT.insertEdge(From, To); 417 EXPECT_TRUE(PDT.verify()); 418 } 419 } 420 421 TEST(DominatorTree, InsertMixed) { 422 CFGHolder Holder; 423 std::vector<CFGBuilder::Arc> Arcs = { 424 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, 425 {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; 426 427 std::vector<CFGBuilder::Update> Updates = { 428 {Insert, {"4", "5"}}, {Insert, {"2", "5"}}, {Insert, {"10", "9"}}, 429 {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}}, 430 {Insert, {"7", "5"}}}; 431 CFGBuilder B(Holder.F, Arcs, Updates); 432 DominatorTree DT(*Holder.F); 433 EXPECT_TRUE(DT.verify()); 434 PostDomTree PDT(*Holder.F); 435 EXPECT_TRUE(PDT.verify()); 436 437 Optional<CFGBuilder::Update> LastUpdate; 438 while ((LastUpdate = B.applyUpdate())) { 439 EXPECT_EQ(LastUpdate->Action, Insert); 440 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 441 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 442 DT.insertEdge(From, To); 443 EXPECT_TRUE(DT.verify()); 444 PDT.insertEdge(From, To); 445 EXPECT_TRUE(PDT.verify()); 446 } 447 } 448 449 TEST(DominatorTree, InsertPermut) { 450 std::vector<CFGBuilder::Arc> Arcs = { 451 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, 452 {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; 453 454 std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}}, 455 {Insert, {"2", "5"}}, 456 {Insert, {"10", "9"}}, 457 {Insert, {"12", "10"}}}; 458 459 while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) { 460 CFGHolder Holder; 461 CFGBuilder B(Holder.F, Arcs, Updates); 462 DominatorTree DT(*Holder.F); 463 EXPECT_TRUE(DT.verify()); 464 PostDomTree PDT(*Holder.F); 465 EXPECT_TRUE(PDT.verify()); 466 467 Optional<CFGBuilder::Update> LastUpdate; 468 while ((LastUpdate = B.applyUpdate())) { 469 EXPECT_EQ(LastUpdate->Action, Insert); 470 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 471 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 472 DT.insertEdge(From, To); 473 EXPECT_TRUE(DT.verify()); 474 PDT.insertEdge(From, To); 475 EXPECT_TRUE(PDT.verify()); 476 } 477 } 478 } 479 480 TEST(DominatorTree, DeleteReachable) { 481 CFGHolder Holder; 482 std::vector<CFGBuilder::Arc> Arcs = { 483 {"1", "2"}, {"2", "3"}, {"2", "4"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, 484 {"5", "7"}, {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}}; 485 486 std::vector<CFGBuilder::Update> Updates = { 487 {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}}; 488 CFGBuilder B(Holder.F, Arcs, Updates); 489 DominatorTree DT(*Holder.F); 490 EXPECT_TRUE(DT.verify()); 491 PostDomTree PDT(*Holder.F); 492 EXPECT_TRUE(PDT.verify()); 493 494 Optional<CFGBuilder::Update> LastUpdate; 495 while ((LastUpdate = B.applyUpdate())) { 496 EXPECT_EQ(LastUpdate->Action, Delete); 497 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 498 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 499 DT.deleteEdge(From, To); 500 EXPECT_TRUE(DT.verify()); 501 PDT.deleteEdge(From, To); 502 EXPECT_TRUE(PDT.verify()); 503 } 504 } 505 506 TEST(DominatorTree, DeleteUnreachable) { 507 CFGHolder Holder; 508 std::vector<CFGBuilder::Arc> Arcs = { 509 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 510 {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}}; 511 512 std::vector<CFGBuilder::Update> Updates = { 513 {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}}; 514 CFGBuilder B(Holder.F, Arcs, Updates); 515 DominatorTree DT(*Holder.F); 516 EXPECT_TRUE(DT.verify()); 517 PostDomTree PDT(*Holder.F); 518 EXPECT_TRUE(PDT.verify()); 519 520 Optional<CFGBuilder::Update> LastUpdate; 521 while ((LastUpdate = B.applyUpdate())) { 522 EXPECT_EQ(LastUpdate->Action, Delete); 523 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 524 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 525 DT.deleteEdge(From, To); 526 EXPECT_TRUE(DT.verify()); 527 PDT.deleteEdge(From, To); 528 EXPECT_TRUE(PDT.verify()); 529 } 530 } 531 532 TEST(DominatorTree, InsertDelete) { 533 std::vector<CFGBuilder::Arc> Arcs = { 534 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 535 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 536 537 std::vector<CFGBuilder::Update> Updates = { 538 {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}}, 539 {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}}, 540 {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}}, 541 {Delete, {"8", "9"}}, {Delete, {"11", "12"}}}; 542 543 CFGHolder Holder; 544 CFGBuilder B(Holder.F, Arcs, Updates); 545 DominatorTree DT(*Holder.F); 546 EXPECT_TRUE(DT.verify()); 547 PostDomTree PDT(*Holder.F); 548 EXPECT_TRUE(PDT.verify()); 549 550 Optional<CFGBuilder::Update> LastUpdate; 551 while ((LastUpdate = B.applyUpdate())) { 552 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 553 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 554 if (LastUpdate->Action == Insert) { 555 DT.insertEdge(From, To); 556 PDT.insertEdge(From, To); 557 } else { 558 DT.deleteEdge(From, To); 559 PDT.deleteEdge(From, To); 560 } 561 562 EXPECT_TRUE(DT.verify()); 563 EXPECT_TRUE(PDT.verify()); 564 } 565 } 566 567 TEST(DominatorTree, InsertDeleteExhaustive) { 568 std::vector<CFGBuilder::Arc> Arcs = { 569 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 570 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 571 572 std::vector<CFGBuilder::Update> Updates = { 573 {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}}, 574 {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}}, 575 {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}}, 576 {Delete, {"8", "9"}}, {Delete, {"11", "12"}}}; 577 578 std::mt19937 Generator(0); 579 for (unsigned i = 0; i < 16; ++i) { 580 std::shuffle(Updates.begin(), Updates.end(), Generator); 581 CFGHolder Holder; 582 CFGBuilder B(Holder.F, Arcs, Updates); 583 DominatorTree DT(*Holder.F); 584 EXPECT_TRUE(DT.verify()); 585 PostDomTree PDT(*Holder.F); 586 EXPECT_TRUE(PDT.verify()); 587 588 Optional<CFGBuilder::Update> LastUpdate; 589 while ((LastUpdate = B.applyUpdate())) { 590 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 591 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 592 if (LastUpdate->Action == Insert) { 593 DT.insertEdge(From, To); 594 PDT.insertEdge(From, To); 595 } else { 596 DT.deleteEdge(From, To); 597 PDT.deleteEdge(From, To); 598 } 599 600 EXPECT_TRUE(DT.verify()); 601 EXPECT_TRUE(PDT.verify()); 602 } 603 } 604 } 605