From c9087d07bbe27d7e3561f6bbe85558f28f35bd12 Mon Sep 17 00:00:00 2001 From: Jakub Kuderski Date: Fri, 30 Jun 2017 01:28:21 +0000 Subject: [PATCH] [Dominators] Don't compute DFS InOut numbers eagerly. Summary: DFS InOut numbers currently get eagerly computer upon DomTree construction. They are only needed to answer dome dominance queries and they get invalidated by updates and recalculations. Because of that, it is faster in practice to compute them lazily when they are actually needed. Clang built without this patch takes 6m 45s to boostrap on my machine, and with the patch applied 6m 38s. Reviewers: sanjoy, dberlin, chandlerc Reviewed By: dberlin Subscribers: davide, llvm-commits Differential Revision: https://reviews.llvm.org/D34296 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@306778 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/GenericDomTreeConstruction.h | 2 -- test/Analysis/Dominators/2006-10-02-BreakCritEdges.ll | 2 +- unittests/IR/DominatorTreeTest.cpp | 2 ++ 3 files changed, 3 insertions(+), 3 deletions(-) diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h index 7899a81751a..038d34fd5c6 100644 --- a/include/llvm/Support/GenericDomTreeConstruction.h +++ b/include/llvm/Support/GenericDomTreeConstruction.h @@ -277,8 +277,6 @@ struct SemiNCAInfo { DT.DomTreeNodes[W] = IDomNode->addChild( llvm::make_unique>(W, IDomNode)); } - - DT.updateDFSNumbers(); } void doFullDFSWalk(const DomTreeT &DT) { diff --git a/test/Analysis/Dominators/2006-10-02-BreakCritEdges.ll b/test/Analysis/Dominators/2006-10-02-BreakCritEdges.ll index a8013176977..c036fe22ab8 100644 --- a/test/Analysis/Dominators/2006-10-02-BreakCritEdges.ll +++ b/test/Analysis/Dominators/2006-10-02-BreakCritEdges.ll @@ -2,7 +2,7 @@ ; RUN: opt < %s -passes='require,break-crit-edges,print' -disable-output 2>&1| FileCheck %s ; PR932 -; CHECK: [3] %brtrue {1,2} +; CHECK: [3] %brtrue {{{[0-9]+}},{{[0-9]+}}} declare void @use1(i32) diff --git a/unittests/IR/DominatorTreeTest.cpp b/unittests/IR/DominatorTreeTest.cpp index 232f0cbd4ed..5d3ef30177a 100644 --- a/unittests/IR/DominatorTreeTest.cpp +++ b/unittests/IR/DominatorTreeTest.cpp @@ -220,6 +220,7 @@ TEST(DominatorTree, Unreachable) { EXPECT_EQ(PostDominatedBBs.size(), 0UL); // Check DFS Numbers before + DT->updateDFSNumbers(); EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL); EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); @@ -235,6 +236,7 @@ TEST(DominatorTree, Unreachable) { DT->recalculate(F); // Check DFS Numbers after + DT->updateDFSNumbers(); EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL); EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); -- 2.50.0