diff options
| author | Jakub Kuderski <kubakuderski@gmail.com> | 2017-06-30 21:51:40 +0000 |
|---|---|---|
| committer | Jakub Kuderski <kubakuderski@gmail.com> | 2017-06-30 21:51:40 +0000 |
| commit | b88303a2c9988f91a1532e2a213713a26c3dcc6a (patch) | |
| tree | 4d404d20d0cc85974d8c6130b0a734697a28c192 /llvm/unittests/IR/DominatorTreeTest.cpp | |
| parent | de6a9796ea00a537f277851230125df5257bff3d (diff) | |
| download | bcm5719-llvm-b88303a2c9988f91a1532e2a213713a26c3dcc6a.tar.gz bcm5719-llvm-b88303a2c9988f91a1532e2a213713a26c3dcc6a.zip | |
[Dominators] Keep tree level in DomTreeNode and use it to find NCD and answer dominance queries
Summary:
This patch makes DomTreeNodes keep their level (depth) in the DomTree. By having this information always available, it is possible to speedup and simplify findNearestCommonDominator and certain dominance queries.
In the future, level information will be also needed to perform incremental updates.
My testing doesn't show any noticeable performance differences after applying this patch. There may be some improvements when other passes are thought to use the level information.
Reviewers: dberlin, sanjoy, chandlerc, grosser
Reviewed By: dberlin
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D34548
llvm-svn: 306892
Diffstat (limited to 'llvm/unittests/IR/DominatorTreeTest.cpp')
| -rw-r--r-- | llvm/unittests/IR/DominatorTreeTest.cpp | 13 |
1 files changed, 13 insertions, 0 deletions
diff --git a/llvm/unittests/IR/DominatorTreeTest.cpp b/llvm/unittests/IR/DominatorTreeTest.cpp index 5d3ef30177a..fa3dad8a2ab 100644 --- a/llvm/unittests/IR/DominatorTreeTest.cpp +++ b/llvm/unittests/IR/DominatorTreeTest.cpp @@ -230,6 +230,12 @@ TEST(DominatorTree, Unreachable) { EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL); EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL); + // Check levels before + EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); + EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); + EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); + EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); + // Reattach block 3 to block 1 and recalculate BB1->getTerminator()->eraseFromParent(); BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1); @@ -248,6 +254,13 @@ TEST(DominatorTree, Unreachable) { EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL); EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL); + // Check levels after + EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); + EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); + EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); + EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U); + EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); + // Change root node DT->verifyDomTree(); BasicBlock *NewEntry = |
