Mercurial > hg > CbC > CbC_llvm

comparison unittests/IR/DominatorTreeTest.cpp @ 148:63bd29f05246

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merged
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Wed, 14 Aug 2019 19:46:37 +0900
parents c2174574ed3a
children
comparison
equal deleted inserted replaced
146:3fc4d5c3e21e 148:63bd29f05246
1 //===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===// 1 //===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===//
2 // 2 //
3 // The LLVM Compiler Infrastructure 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // 4 // See https://llvm.org/LICENSE.txt for license information.
5 // This file is distributed under the University of Illinois Open Source 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 // License. See LICENSE.TXT for details.
7 // 6 //
8 //===----------------------------------------------------------------------===// 7 //===----------------------------------------------------------------------===//
9 8
10 #include <random> 9 #include <random>
11 #include "llvm/Analysis/PostDominators.h" 10 #include "llvm/Analysis/PostDominators.h"
11 #include "llvm/Analysis/IteratedDominanceFrontier.h"
12 #include "llvm/AsmParser/Parser.h" 12 #include "llvm/AsmParser/Parser.h"
13 #include "llvm/IR/Constants.h" 13 #include "llvm/IR/Constants.h"
14 #include "llvm/IR/Dominators.h" 14 #include "llvm/IR/Dominators.h"
15 #include "llvm/IR/Instructions.h" 15 #include "llvm/IR/Instructions.h"
16 #include "llvm/IR/LLVMContext.h" 16 #include "llvm/IR/LLVMContext.h"
19 #include "CFGBuilder.h" 19 #include "CFGBuilder.h"
20 #include "gtest/gtest.h" 20 #include "gtest/gtest.h"
21 21
22 using namespace llvm; 22 using namespace llvm;
23 23
24 struct PostDomTree : PostDomTreeBase<BasicBlock> {
25 PostDomTree(Function &F) { recalculate(F); }
26 };
27 24
28 /// Build the dominator tree for the function and run the Test. 25 /// Build the dominator tree for the function and run the Test.
29 static void runWithDomTree( 26 static void runWithDomTree(
30 Module &M, StringRef FuncName, 27 Module &M, StringRef FuncName,
31 function_ref<void(Function &F, DominatorTree *DT, PostDomTree *PDT)> Test) { 28 function_ref<void(Function &F, DominatorTree *DT, PostDominatorTree *PDT)>
29 Test) {
32 auto *F = M.getFunction(FuncName); 30 auto *F = M.getFunction(FuncName);
33 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 31 ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
34 // Compute the dominator tree for the function. 32 // Compute the dominator tree for the function.
35 DominatorTree DT(*F); 33 DominatorTree DT(*F);
36 PostDomTree PDT(*F); 34 PostDominatorTree PDT(*F);
37 Test(*F, &DT, &PDT); 35 Test(*F, &DT, &PDT);
38 } 36 }
39 37
40 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 38 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
41 StringRef ModuleStr) { 39 StringRef ModuleStr) {
73 // Parse the module. 71 // Parse the module.
74 LLVMContext Context; 72 LLVMContext Context;
75 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 73 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
76 74
77 runWithDomTree( 75 runWithDomTree(
78 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 76 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
79 Function::iterator FI = F.begin(); 77 Function::iterator FI = F.begin();
80 78
81 BasicBlock *BB0 = &*FI++; 79 BasicBlock *BB0 = &*FI++;
82 BasicBlock::iterator BBI = BB0->begin(); 80 BasicBlock::iterator BBI = BB0->begin();
83 Instruction *Y1 = &*BBI++; 81 Instruction *Y1 = &*BBI++;
262 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); 260 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U);
263 EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U); 261 EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U);
264 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); 262 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U);
265 263
266 // Change root node 264 // Change root node
267 DT->verifyDomTree(); 265 EXPECT_TRUE(DT->verify());
268 BasicBlock *NewEntry = 266 BasicBlock *NewEntry =
269 BasicBlock::Create(F.getContext(), "new_entry", &F, BB0); 267 BasicBlock::Create(F.getContext(), "new_entry", &F, BB0);
270 BranchInst::Create(BB0, NewEntry); 268 BranchInst::Create(BB0, NewEntry);
271 EXPECT_EQ(F.begin()->getName(), NewEntry->getName()); 269 EXPECT_EQ(F.begin()->getName(), NewEntry->getName());
272 EXPECT_TRUE(&F.getEntryBlock() == NewEntry); 270 EXPECT_TRUE(&F.getEntryBlock() == NewEntry);
273 DT->setNewRoot(NewEntry); 271 DT->setNewRoot(NewEntry);
274 DT->verifyDomTree(); 272 EXPECT_TRUE(DT->verify());
275 }); 273 });
276 } 274 }
277 275
278 TEST(DominatorTree, NonUniqueEdges) { 276 TEST(DominatorTree, NonUniqueEdges) {
279 StringRef ModuleString = 277 StringRef ModuleString =
293 // Parse the module. 291 // Parse the module.
294 LLVMContext Context; 292 LLVMContext Context;
295 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 293 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
296 294
297 runWithDomTree( 295 runWithDomTree(
298 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 296 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
299 Function::iterator FI = F.begin(); 297 Function::iterator FI = F.begin();
300 298
301 BasicBlock *BB0 = &*FI++; 299 BasicBlock *BB0 = &*FI++;
302 BasicBlock *BB1 = &*FI++; 300 BasicBlock *BB1 = &*FI++;
303 BasicBlock *BB2 = &*FI++; 301 BasicBlock *BB2 = &*FI++;
304 302
305 const TerminatorInst *TI = BB0->getTerminator(); 303 const Instruction *TI = BB0->getTerminator();
306 assert(TI->getNumSuccessors() == 3 && "Switch has three successors"); 304 assert(TI->getNumSuccessors() == 3 && "Switch has three successors");
307 305
308 BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0)); 306 BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0));
309 assert(Edge_BB0_BB2.getEnd() == BB2 && 307 assert(Edge_BB0_BB2.getEnd() == BB2 &&
310 "Default label is the 1st successor"); 308 "Default label is the 1st successor");
357 // C \ 355 // C \
358 // | \ 356 // | \
359 // unreachable Exit 357 // unreachable Exit
360 // 358 //
361 // Both the blocks that end with ret and with unreachable become trivial 359 // Both the blocks that end with ret and with unreachable become trivial
362 // PostDomTree roots, as they have no successors. 360 // PostDominatorTree roots, as they have no successors.
363 // 361 //
364 TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) { 362 TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) {
365 StringRef ModuleString = 363 StringRef ModuleString =
366 "define void @f() {\n" 364 "define void @f() {\n"
367 "A:\n" 365 "A:\n"
377 // Parse the module. 375 // Parse the module.
378 LLVMContext Context; 376 LLVMContext Context;
379 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 377 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
380 378
381 runWithDomTree( 379 runWithDomTree(
382 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 380 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
383 Function::iterator FI = F.begin(); 381 Function::iterator FI = F.begin();
384 382
385 FI++; 383 FI++;
386 BasicBlock *B = &*FI++; 384 BasicBlock *B = &*FI++;
387 BasicBlock *C = &*FI++; 385 BasicBlock *C = &*FI++;
404 EXPECT_NE(PDT->getNode(C), nullptr); 402 EXPECT_NE(PDT->getNode(C), nullptr);
405 403
406 DominatorTree NDT(F); 404 DominatorTree NDT(F);
407 EXPECT_EQ(DT->compare(NDT), 0); 405 EXPECT_EQ(DT->compare(NDT), 0);
408 406
409 PostDomTree NPDT(F); 407 PostDominatorTree NPDT(F);
410 EXPECT_EQ(PDT->compare(NPDT), 0); 408 EXPECT_EQ(PDT->compare(NPDT), 0);
411 }); 409 });
412 } 410 }
413 411
414 // Verify that the PDT is correctly updated in case an edge removal results 412 // Verify that the PDT is correctly updated in case an edge removal results
471 // Parse the module. 469 // Parse the module.
472 LLVMContext Context; 470 LLVMContext Context;
473 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 471 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
474 472
475 runWithDomTree( 473 runWithDomTree(
476 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 474 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
477 Function::iterator FI = F.begin(); 475 Function::iterator FI = F.begin();
478 476
479 FI++; 477 FI++;
480 BasicBlock *B = &*FI++; 478 BasicBlock *B = &*FI++;
481 BasicBlock *C = &*FI++; 479 BasicBlock *C = &*FI++;
496 EXPECT_NE(PDT->getNode(C), nullptr); 494 EXPECT_NE(PDT->getNode(C), nullptr);
497 495
498 DominatorTree NDT(F); 496 DominatorTree NDT(F);
499 EXPECT_EQ(DT->compare(NDT), 0); 497 EXPECT_EQ(DT->compare(NDT), 0);
500 498
501 PostDomTree NPDT(F); 499 PostDominatorTree NPDT(F);
502 EXPECT_EQ(PDT->compare(NPDT), 0); 500 EXPECT_EQ(PDT->compare(NPDT), 0);
503 }); 501 });
504 } 502 }
505 503
506 // Verify that the PDT is correctly updated in case an edge removal results 504 // Verify that the PDT is correctly updated in case an edge removal results
560 // Parse the module. 558 // Parse the module.
561 LLVMContext Context; 559 LLVMContext Context;
562 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 560 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
563 561
564 runWithDomTree( 562 runWithDomTree(
565 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 563 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
566 Function::iterator FI = F.begin(); 564 Function::iterator FI = F.begin();
567 565
568 FI++; 566 FI++;
569 BasicBlock *B = &*FI++; 567 BasicBlock *B = &*FI++;
570 BasicBlock *C = &*FI++; 568 BasicBlock *C = &*FI++;
591 EXPECT_NE(PDT->getNode(C), nullptr); 589 EXPECT_NE(PDT->getNode(C), nullptr);
592 590
593 DominatorTree NDT(F); 591 DominatorTree NDT(F);
594 EXPECT_EQ(DT->compare(NDT), 0); 592 EXPECT_EQ(DT->compare(NDT), 0);
595 593
596 PostDomTree NPDT(F); 594 PostDominatorTree NPDT(F);
597 EXPECT_EQ(PDT->compare(NPDT), 0); 595 EXPECT_EQ(PDT->compare(NPDT), 0);
596 });
597 }
598
599 // Verify that the IDF returns blocks in a deterministic way.
600 //
601 // Test case:
602 //
603 // CFG
604 //
605 // (A)
606 // / \
607 // / \
608 // (B) (C)
609 // |\ /|
610 // | X |
611 // |/ \|
612 // (D) (E)
613 //
614 // IDF for block B is {D, E}, and the order of blocks in this list is defined by
615 // their 1) level in dom-tree and 2) DFSIn number if the level is the same.
616 //
617 TEST(DominatorTree, IDFDeterminismTest) {
618 StringRef ModuleString =
619 "define void @f() {\n"
620 "A:\n"
621 " br i1 undef, label %B, label %C\n"
622 "B:\n"
623 " br i1 undef, label %D, label %E\n"
624 "C:\n"
625 " br i1 undef, label %D, label %E\n"
626 "D:\n"
627 " ret void\n"
628 "E:\n"
629 " ret void\n"
630 "}\n";
631
632 // Parse the module.
633 LLVMContext Context;
634 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
635
636 runWithDomTree(
637 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
638 Function::iterator FI = F.begin();
639
640 BasicBlock *A = &*FI++;
641 BasicBlock *B = &*FI++;
642 BasicBlock *C = &*FI++;
643 BasicBlock *D = &*FI++;
644 BasicBlock *E = &*FI++;
645 (void)C;
646
647 DT->updateDFSNumbers();
648 ForwardIDFCalculator IDF(*DT);
649 SmallPtrSet<BasicBlock *, 1> DefBlocks;
650 DefBlocks.insert(B);
651 IDF.setDefiningBlocks(DefBlocks);
652
653 SmallVector<BasicBlock *, 32> IDFBlocks;
654 SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
655 IDF.resetLiveInBlocks();
656 IDF.calculate(IDFBlocks);
657
658
659 EXPECT_EQ(IDFBlocks.size(), 2UL);
660 EXPECT_EQ(DT->getNode(A)->getDFSNumIn(), 0UL);
661 EXPECT_EQ(IDFBlocks[0], D);
662 EXPECT_EQ(IDFBlocks[1], E);
663 EXPECT_TRUE(DT->getNode(IDFBlocks[0])->getDFSNumIn() <
664 DT->getNode(IDFBlocks[1])->getDFSNumIn());
598 }); 665 });
599 } 666 }
600 667
601 namespace { 668 namespace {
602 const auto Insert = CFGBuilder::ActionKind::Insert; 669 const auto Insert = CFGBuilder::ActionKind::Insert;
619 {Insert, {"7", "6"}}, 686 {Insert, {"7", "6"}},
620 {Insert, {"7", "5"}}}; 687 {Insert, {"7", "5"}}};
621 CFGBuilder B(Holder.F, Arcs, Updates); 688 CFGBuilder B(Holder.F, Arcs, Updates);
622 DominatorTree DT(*Holder.F); 689 DominatorTree DT(*Holder.F);
623 EXPECT_TRUE(DT.verify()); 690 EXPECT_TRUE(DT.verify());
624 PostDomTree PDT(*Holder.F); 691 PostDominatorTree PDT(*Holder.F);
625 EXPECT_TRUE(PDT.verify()); 692 EXPECT_TRUE(PDT.verify());
626 693
627 Optional<CFGBuilder::Update> LastUpdate; 694 Optional<CFGBuilder::Update> LastUpdate;
628 while ((LastUpdate = B.applyUpdate())) { 695 while ((LastUpdate = B.applyUpdate())) {
629 EXPECT_EQ(LastUpdate->Action, Insert); 696 EXPECT_EQ(LastUpdate->Action, Insert);
645 712
646 std::vector<CFGBuilder::Update> Updates = {{Insert, {"10", "7"}}}; 713 std::vector<CFGBuilder::Update> Updates = {{Insert, {"10", "7"}}};
647 CFGBuilder B(Holder.F, Arcs, Updates); 714 CFGBuilder B(Holder.F, Arcs, Updates);
648 DominatorTree DT(*Holder.F); 715 DominatorTree DT(*Holder.F);
649 EXPECT_TRUE(DT.verify()); 716 EXPECT_TRUE(DT.verify());
650 PostDomTree PDT(*Holder.F); 717 PostDominatorTree PDT(*Holder.F);
651 EXPECT_TRUE(PDT.verify()); 718 EXPECT_TRUE(PDT.verify());
652 719
653 Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); 720 Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();
654 EXPECT_TRUE(LastUpdate); 721 EXPECT_TRUE(LastUpdate);
655 722
673 {Insert, {"10", "12"}}, 740 {Insert, {"10", "12"}},
674 {Insert, {"10", "11"}}}; 741 {Insert, {"10", "11"}}};
675 CFGBuilder B(Holder.F, Arcs, Updates); 742 CFGBuilder B(Holder.F, Arcs, Updates);
676 DominatorTree DT(*Holder.F); 743 DominatorTree DT(*Holder.F);
677 EXPECT_TRUE(DT.verify()); 744 EXPECT_TRUE(DT.verify());
678 PostDomTree PDT(*Holder.F); 745 PostDominatorTree PDT(*Holder.F);
679 EXPECT_TRUE(PDT.verify()); 746 EXPECT_TRUE(PDT.verify());
680 747
681 Optional<CFGBuilder::Update> LastUpdate; 748 Optional<CFGBuilder::Update> LastUpdate;
682 while ((LastUpdate = B.applyUpdate())) { 749 while ((LastUpdate = B.applyUpdate())) {
683 EXPECT_EQ(LastUpdate->Action, Insert); 750 EXPECT_EQ(LastUpdate->Action, Insert);
694 CFGHolder Holder; 761 CFGHolder Holder;
695 std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}}; 762 std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}};
696 763
697 std::vector<CFGBuilder::Update> Updates = {{Insert, {"3", "5"}}}; 764 std::vector<CFGBuilder::Update> Updates = {{Insert, {"3", "5"}}};
698 CFGBuilder B(Holder.F, Arcs, Updates); 765 CFGBuilder B(Holder.F, Arcs, Updates);
699 PostDomTree PDT(*Holder.F); 766 PostDominatorTree PDT(*Holder.F);
700 EXPECT_TRUE(PDT.verify()); 767 EXPECT_TRUE(PDT.verify());
701 768
702 Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); 769 Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();
703 EXPECT_TRUE(LastUpdate); 770 EXPECT_TRUE(LastUpdate);
704 771
706 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 773 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
707 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 774 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
708 PDT.insertEdge(From, To); 775 PDT.insertEdge(From, To);
709 EXPECT_TRUE(PDT.verify()); 776 EXPECT_TRUE(PDT.verify());
710 EXPECT_TRUE(PDT.getRoots().size() == 2); 777 EXPECT_TRUE(PDT.getRoots().size() == 2);
711 EXPECT_NE(PDT.getNode(B.getOrAddBlock("5")), nullptr); 778 // Make sure we can use a const pointer with getNode.
779 const BasicBlock *BB5 = B.getOrAddBlock("5");
780 EXPECT_NE(PDT.getNode(BB5), nullptr);
712 } 781 }
713 782
714 TEST(DominatorTree, InsertMixed) { 783 TEST(DominatorTree, InsertMixed) {
715 CFGHolder Holder; 784 CFGHolder Holder;
716 std::vector<CFGBuilder::Arc> Arcs = { 785 std::vector<CFGBuilder::Arc> Arcs = {
722 {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}}, 791 {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}},
723 {Insert, {"7", "5"}}}; 792 {Insert, {"7", "5"}}};
724 CFGBuilder B(Holder.F, Arcs, Updates); 793 CFGBuilder B(Holder.F, Arcs, Updates);
725 DominatorTree DT(*Holder.F); 794 DominatorTree DT(*Holder.F);
726 EXPECT_TRUE(DT.verify()); 795 EXPECT_TRUE(DT.verify());
727 PostDomTree PDT(*Holder.F); 796 PostDominatorTree PDT(*Holder.F);
728 EXPECT_TRUE(PDT.verify()); 797 EXPECT_TRUE(PDT.verify());
729 798
730 Optional<CFGBuilder::Update> LastUpdate; 799 Optional<CFGBuilder::Update> LastUpdate;
731 while ((LastUpdate = B.applyUpdate())) { 800 while ((LastUpdate = B.applyUpdate())) {
732 EXPECT_EQ(LastUpdate->Action, Insert); 801 EXPECT_EQ(LastUpdate->Action, Insert);
752 while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) { 821 while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) {
753 CFGHolder Holder; 822 CFGHolder Holder;
754 CFGBuilder B(Holder.F, Arcs, Updates); 823 CFGBuilder B(Holder.F, Arcs, Updates);
755 DominatorTree DT(*Holder.F); 824 DominatorTree DT(*Holder.F);
756 EXPECT_TRUE(DT.verify()); 825 EXPECT_TRUE(DT.verify());
757 PostDomTree PDT(*Holder.F); 826 PostDominatorTree PDT(*Holder.F);
758 EXPECT_TRUE(PDT.verify()); 827 EXPECT_TRUE(PDT.verify());
759 828
760 Optional<CFGBuilder::Update> LastUpdate; 829 Optional<CFGBuilder::Update> LastUpdate;
761 while ((LastUpdate = B.applyUpdate())) { 830 while ((LastUpdate = B.applyUpdate())) {
762 EXPECT_EQ(LastUpdate->Action, Insert); 831 EXPECT_EQ(LastUpdate->Action, Insert);
779 std::vector<CFGBuilder::Update> Updates = { 848 std::vector<CFGBuilder::Update> Updates = {
780 {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}}; 849 {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}};
781 CFGBuilder B(Holder.F, Arcs, Updates); 850 CFGBuilder B(Holder.F, Arcs, Updates);
782 DominatorTree DT(*Holder.F); 851 DominatorTree DT(*Holder.F);
783 EXPECT_TRUE(DT.verify()); 852 EXPECT_TRUE(DT.verify());
784 PostDomTree PDT(*Holder.F); 853 PostDominatorTree PDT(*Holder.F);
785 EXPECT_TRUE(PDT.verify()); 854 EXPECT_TRUE(PDT.verify());
786 855
787 Optional<CFGBuilder::Update> LastUpdate; 856 Optional<CFGBuilder::Update> LastUpdate;
788 while ((LastUpdate = B.applyUpdate())) { 857 while ((LastUpdate = B.applyUpdate())) {
789 EXPECT_EQ(LastUpdate->Action, Delete); 858 EXPECT_EQ(LastUpdate->Action, Delete);
805 std::vector<CFGBuilder::Update> Updates = { 874 std::vector<CFGBuilder::Update> Updates = {
806 {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}}; 875 {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}};
807 CFGBuilder B(Holder.F, Arcs, Updates); 876 CFGBuilder B(Holder.F, Arcs, Updates);
808 DominatorTree DT(*Holder.F); 877 DominatorTree DT(*Holder.F);
809 EXPECT_TRUE(DT.verify()); 878 EXPECT_TRUE(DT.verify());
810 PostDomTree PDT(*Holder.F); 879 PostDominatorTree PDT(*Holder.F);
811 EXPECT_TRUE(PDT.verify()); 880 EXPECT_TRUE(PDT.verify());
812 881
813 Optional<CFGBuilder::Update> LastUpdate; 882 Optional<CFGBuilder::Update> LastUpdate;
814 while ((LastUpdate = B.applyUpdate())) { 883 while ((LastUpdate = B.applyUpdate())) {
815 EXPECT_EQ(LastUpdate->Action, Delete); 884 EXPECT_EQ(LastUpdate->Action, Delete);
835 904
836 CFGHolder Holder; 905 CFGHolder Holder;
837 CFGBuilder B(Holder.F, Arcs, Updates); 906 CFGBuilder B(Holder.F, Arcs, Updates);
838 DominatorTree DT(*Holder.F); 907 DominatorTree DT(*Holder.F);
839 EXPECT_TRUE(DT.verify()); 908 EXPECT_TRUE(DT.verify());
840 PostDomTree PDT(*Holder.F); 909 PostDominatorTree PDT(*Holder.F);
841 EXPECT_TRUE(PDT.verify()); 910 EXPECT_TRUE(PDT.verify());
842 911
843 Optional<CFGBuilder::Update> LastUpdate; 912 Optional<CFGBuilder::Update> LastUpdate;
844 while ((LastUpdate = B.applyUpdate())) { 913 while ((LastUpdate = B.applyUpdate())) {
845 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 914 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
873 std::shuffle(Updates.begin(), Updates.end(), Generator); 942 std::shuffle(Updates.begin(), Updates.end(), Generator);
874 CFGHolder Holder; 943 CFGHolder Holder;
875 CFGBuilder B(Holder.F, Arcs, Updates); 944 CFGBuilder B(Holder.F, Arcs, Updates);
876 DominatorTree DT(*Holder.F); 945 DominatorTree DT(*Holder.F);
877 EXPECT_TRUE(DT.verify()); 946 EXPECT_TRUE(DT.verify());
878 PostDomTree PDT(*Holder.F); 947 PostDominatorTree PDT(*Holder.F);
879 EXPECT_TRUE(PDT.verify()); 948 EXPECT_TRUE(PDT.verify());
880 949
881 Optional<CFGBuilder::Update> LastUpdate; 950 Optional<CFGBuilder::Update> LastUpdate;
882 while ((LastUpdate = B.applyUpdate())) { 951 while ((LastUpdate = B.applyUpdate())) {
883 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 952 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);