From 2e6716eb5517f39d7951c23a8b0d9b6fc7c7045d Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Tue, 14 Apr 2015 19:49:26 +0000 Subject: [PATCH] Only recalculate DFS Numbers if invalid. Invalidate DFS numbers on reset. Add unit test to verify recalculation git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@234933 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/GenericDomTree.h | 8 ++++++++ unittests/IR/DominatorTreeTest.cpp | 28 +++++++++++++++++++++++++++ 2 files changed, 36 insertions(+) diff --git a/include/llvm/Support/GenericDomTree.h b/include/llvm/Support/GenericDomTree.h index 5d11766ef44..63678bb98bb 100644 --- a/include/llvm/Support/GenericDomTree.h +++ b/include/llvm/Support/GenericDomTree.h @@ -243,6 +243,8 @@ protected: this->Roots.clear(); Vertex.clear(); RootNode = nullptr; + DFSInfoValid = false; + SlowQueries = 0; } // NewBB is split and now it has one successor. Update dominator tree to @@ -663,6 +665,12 @@ public: /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking /// dominator tree in dfs order. void updateDFSNumbers() const { + + if (DFSInfoValid) { + SlowQueries = 0; + return; + } + unsigned DFSNum = 0; SmallVector *, diff --git a/unittests/IR/DominatorTreeTest.cpp b/unittests/IR/DominatorTreeTest.cpp index 287a9448454..6a5838e693a 100644 --- a/unittests/IR/DominatorTreeTest.cpp +++ b/unittests/IR/DominatorTreeTest.cpp @@ -10,6 +10,7 @@ #include "llvm/IR/Dominators.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/AsmParser/Parser.h" +#include "llvm/IR/Constants.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" @@ -174,6 +175,33 @@ namespace llvm { EXPECT_EQ(DominatedBBs.size(), 0UL); EXPECT_EQ(PostDominatedBBs.size(), 0UL); + // Check DFS Numbers before + EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); + EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL); + EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); + EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL); + EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL); + EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL); + EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL); + EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL); + + // Reattach block 3 to block 1 and recalculate + BB1->getTerminator()->eraseFromParent(); + BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1); + DT->recalculate(F); + + // Check DFS Numbers after + EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); + EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL); + EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); + EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL); + EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL); + EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL); + EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL); + EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL); + EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL); + EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL); + return false; } void getAnalysisUsage(AnalysisUsage &AU) const override { -- 2.34.1