summaryrefslogtreecommitdiff
path: root/unittests/IR/DominatorTreeTest.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'unittests/IR/DominatorTreeTest.cpp')
-rw-r--r--unittests/IR/DominatorTreeTest.cpp179
1 files changed, 122 insertions, 57 deletions
diff --git a/unittests/IR/DominatorTreeTest.cpp b/unittests/IR/DominatorTreeTest.cpp
index bf5aced49289..cf81623d0d17 100644
--- a/unittests/IR/DominatorTreeTest.cpp
+++ b/unittests/IR/DominatorTreeTest.cpp
@@ -9,6 +9,7 @@
#include <random>
#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/AsmParser/Parser.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
@@ -21,19 +22,17 @@
using namespace llvm;
-struct PostDomTree : PostDomTreeBase<BasicBlock> {
- PostDomTree(Function &F) { recalculate(F); }
-};
/// Build the dominator tree for the function and run the Test.
static void runWithDomTree(
Module &M, StringRef FuncName,
- function_ref<void(Function &F, DominatorTree *DT, PostDomTree *PDT)> Test) {
+ function_ref<void(Function &F, DominatorTree *DT, PostDominatorTree *PDT)>
+ Test) {
auto *F = M.getFunction(FuncName);
ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
// Compute the dominator tree for the function.
DominatorTree DT(*F);
- PostDomTree PDT(*F);
+ PostDominatorTree PDT(*F);
Test(*F, &DT, &PDT);
}
@@ -75,7 +74,7 @@ TEST(DominatorTree, Unreachable) {
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
runWithDomTree(
- *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
+ *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
Function::iterator FI = F.begin();
BasicBlock *BB0 = &*FI++;
@@ -264,14 +263,14 @@ TEST(DominatorTree, Unreachable) {
EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U);
// Change root node
- DT->verifyDomTree();
+ EXPECT_TRUE(DT->verify());
BasicBlock *NewEntry =
BasicBlock::Create(F.getContext(), "new_entry", &F, BB0);
BranchInst::Create(BB0, NewEntry);
EXPECT_EQ(F.begin()->getName(), NewEntry->getName());
EXPECT_TRUE(&F.getEntryBlock() == NewEntry);
DT->setNewRoot(NewEntry);
- DT->verifyDomTree();
+ EXPECT_TRUE(DT->verify());
});
}
@@ -295,7 +294,7 @@ TEST(DominatorTree, NonUniqueEdges) {
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
runWithDomTree(
- *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
+ *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
Function::iterator FI = F.begin();
BasicBlock *BB0 = &*FI++;
@@ -359,7 +358,7 @@ TEST(DominatorTree, NonUniqueEdges) {
// unreachable Exit
//
// Both the blocks that end with ret and with unreachable become trivial
-// PostDomTree roots, as they have no successors.
+// PostDominatorTree roots, as they have no successors.
//
TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) {
StringRef ModuleString =
@@ -379,7 +378,7 @@ TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) {
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
runWithDomTree(
- *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
+ *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
Function::iterator FI = F.begin();
FI++;
@@ -406,7 +405,7 @@ TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) {
DominatorTree NDT(F);
EXPECT_EQ(DT->compare(NDT), 0);
- PostDomTree NPDT(F);
+ PostDominatorTree NPDT(F);
EXPECT_EQ(PDT->compare(NPDT), 0);
});
}
@@ -473,7 +472,7 @@ TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) {
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
runWithDomTree(
- *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
+ *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
Function::iterator FI = F.begin();
FI++;
@@ -498,7 +497,7 @@ TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) {
DominatorTree NDT(F);
EXPECT_EQ(DT->compare(NDT), 0);
- PostDomTree NPDT(F);
+ PostDominatorTree NPDT(F);
EXPECT_EQ(PDT->compare(NPDT), 0);
});
}
@@ -562,7 +561,7 @@ TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) {
std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
runWithDomTree(
- *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) {
+ *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
Function::iterator FI = F.begin();
FI++;
@@ -593,11 +592,80 @@ TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) {
DominatorTree NDT(F);
EXPECT_EQ(DT->compare(NDT), 0);
- PostDomTree NPDT(F);
+ PostDominatorTree NPDT(F);
EXPECT_EQ(PDT->compare(NPDT), 0);
});
}
+// Verify that the IDF returns blocks in a deterministic way.
+//
+// Test case:
+//
+// CFG
+//
+// (A)
+// / \
+// / \
+// (B) (C)
+// |\ /|
+// | X |
+// |/ \|
+// (D) (E)
+//
+// IDF for block B is {D, E}, and the order of blocks in this list is defined by
+// their 1) level in dom-tree and 2) DFSIn number if the level is the same.
+//
+TEST(DominatorTree, IDFDeterminismTest) {
+ StringRef ModuleString =
+ "define void @f() {\n"
+ "A:\n"
+ " br i1 undef, label %B, label %C\n"
+ "B:\n"
+ " br i1 undef, label %D, label %E\n"
+ "C:\n"
+ " br i1 undef, label %D, label %E\n"
+ "D:\n"
+ " ret void\n"
+ "E:\n"
+ " ret void\n"
+ "}\n";
+
+ // Parse the module.
+ LLVMContext Context;
+ std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+ runWithDomTree(
+ *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
+ Function::iterator FI = F.begin();
+
+ BasicBlock *A = &*FI++;
+ BasicBlock *B = &*FI++;
+ BasicBlock *C = &*FI++;
+ BasicBlock *D = &*FI++;
+ BasicBlock *E = &*FI++;
+ (void)C;
+
+ DT->updateDFSNumbers();
+ ForwardIDFCalculator IDF(*DT);
+ SmallPtrSet<BasicBlock *, 1> DefBlocks;
+ DefBlocks.insert(B);
+ IDF.setDefiningBlocks(DefBlocks);
+
+ SmallVector<BasicBlock *, 32> IDFBlocks;
+ SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
+ IDF.resetLiveInBlocks();
+ IDF.calculate(IDFBlocks);
+
+
+ EXPECT_EQ(IDFBlocks.size(), 2UL);
+ EXPECT_EQ(DT->getNode(A)->getDFSNumIn(), 0UL);
+ EXPECT_EQ(IDFBlocks[0], D);
+ EXPECT_EQ(IDFBlocks[1], E);
+ EXPECT_TRUE(DT->getNode(IDFBlocks[0])->getDFSNumIn() <
+ DT->getNode(IDFBlocks[1])->getDFSNumIn());
+ });
+}
+
namespace {
const auto Insert = CFGBuilder::ActionKind::Insert;
const auto Delete = CFGBuilder::ActionKind::Delete;
@@ -621,7 +689,7 @@ TEST(DominatorTree, InsertReachable) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
Optional<CFGBuilder::Update> LastUpdate;
@@ -647,7 +715,7 @@ TEST(DominatorTree, InsertReachable2) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();
@@ -675,7 +743,7 @@ TEST(DominatorTree, InsertUnreachable) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
Optional<CFGBuilder::Update> LastUpdate;
@@ -696,7 +764,7 @@ TEST(DominatorTree, InsertFromUnreachable) {
std::vector<CFGBuilder::Update> Updates = {{Insert, {"3", "5"}}};
CFGBuilder B(Holder.F, Arcs, Updates);
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();
@@ -708,7 +776,9 @@ TEST(DominatorTree, InsertFromUnreachable) {
PDT.insertEdge(From, To);
EXPECT_TRUE(PDT.verify());
EXPECT_TRUE(PDT.getRoots().size() == 2);
- EXPECT_NE(PDT.getNode(B.getOrAddBlock("5")), nullptr);
+ // Make sure we can use a const pointer with getNode.
+ const BasicBlock *BB5 = B.getOrAddBlock("5");
+ EXPECT_NE(PDT.getNode(BB5), nullptr);
}
TEST(DominatorTree, InsertMixed) {
@@ -724,7 +794,7 @@ TEST(DominatorTree, InsertMixed) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
Optional<CFGBuilder::Update> LastUpdate;
@@ -754,7 +824,7 @@ TEST(DominatorTree, InsertPermut) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
Optional<CFGBuilder::Update> LastUpdate;
@@ -781,7 +851,7 @@ TEST(DominatorTree, DeleteReachable) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
Optional<CFGBuilder::Update> LastUpdate;
@@ -807,7 +877,7 @@ TEST(DominatorTree, DeleteUnreachable) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
Optional<CFGBuilder::Update> LastUpdate;
@@ -822,36 +892,6 @@ TEST(DominatorTree, DeleteUnreachable) {
}
}
-TEST(DominatorTree, DeletionsInSubtrees) {
- CFGHolder Holder;
- std::vector<CFGBuilder::Arc> Arcs = {{"0", "1"}, {"1", "2"}, {"1", "3"},
- {"1", "6"}, {"3", "4"}, {"2", "5"},
- {"5", "2"}};
-
- // It is possible to perform multiple deletions and inform the
- // DominatorTree about them at the same time, if the all of the
- // deletions happen in different subtrees.
- std::vector<CFGBuilder::Update> Updates = {{Delete, {"1", "2"}},
- {Delete, {"1", "3"}}};
- CFGBuilder B(Holder.F, Arcs, Updates);
- DominatorTree DT(*Holder.F);
- EXPECT_TRUE(DT.verify());
-
- Optional<CFGBuilder::Update> LastUpdate;
- while ((LastUpdate = B.applyUpdate()))
- ;
-
- DT.deleteEdge(B.getOrAddBlock("1"), B.getOrAddBlock("2"));
- DT.deleteEdge(B.getOrAddBlock("1"), B.getOrAddBlock("3"));
-
- EXPECT_TRUE(DT.verify());
- EXPECT_EQ(DT.getNode(B.getOrAddBlock("2")), nullptr);
- EXPECT_EQ(DT.getNode(B.getOrAddBlock("3")), nullptr);
- EXPECT_EQ(DT.getNode(B.getOrAddBlock("4")), nullptr);
- EXPECT_EQ(DT.getNode(B.getOrAddBlock("5")), nullptr);
- EXPECT_NE(DT.getNode(B.getOrAddBlock("6")), nullptr);
-}
-
TEST(DominatorTree, InsertDelete) {
std::vector<CFGBuilder::Arc> Arcs = {
{"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
@@ -867,7 +907,7 @@ TEST(DominatorTree, InsertDelete) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
Optional<CFGBuilder::Update> LastUpdate;
@@ -905,7 +945,7 @@ TEST(DominatorTree, InsertDeleteExhaustive) {
CFGBuilder B(Holder.F, Arcs, Updates);
DominatorTree DT(*Holder.F);
EXPECT_TRUE(DT.verify());
- PostDomTree PDT(*Holder.F);
+ PostDominatorTree PDT(*Holder.F);
EXPECT_TRUE(PDT.verify());
Optional<CFGBuilder::Update> LastUpdate;
@@ -925,3 +965,28 @@ TEST(DominatorTree, InsertDeleteExhaustive) {
}
}
}
+
+TEST(DominatorTree, InsertIntoIrreducible) {
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"0", "1"},
+ {"1", "27"}, {"1", "7"},
+ {"10", "18"},
+ {"13", "10"},
+ {"18", "13"}, {"18", "23"},
+ {"23", "13"}, {"23", "24"},
+ {"24", "1"}, {"24", "18"},
+ {"27", "24"}};
+
+ CFGHolder Holder;
+ CFGBuilder B(Holder.F, Arcs, {{Insert, {"7", "23"}}});
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+
+ B.applyUpdate();
+ BasicBlock *From = B.getOrAddBlock("7");
+ BasicBlock *To = B.getOrAddBlock("23");
+ DT.insertEdge(From, To);
+
+ EXPECT_TRUE(DT.verify());
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-09 13:17:30 +0000