From 1a2e7d2ddca2ecd7d3188786dcab56518745d73b Mon Sep 17 00:00:00 2001 From: Jakub Kuderski Date: Thu, 13 Jul 2017 20:45:32 +0000 Subject: [PATCH] [Dominators] Simplify templates Summary: DominatorTreeBase and related classes used overcomplicated template machinery. This patch simplifies them and gets rid of DominatorTreeBaseTraits and DominatorTreeBaseByTraits, which weren't actually used outside the DomTree construction. Reviewers: dberlin, sanjoy, davide, grosser Reviewed By: dberlin, davide, grosser Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D35285 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@307953 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/IR/Dominators.h | 14 ++---- include/llvm/Support/GenericDomTree.h | 50 ++++++------------- .../llvm/Support/GenericDomTreeConstruction.h | 29 ++++------- lib/IR/Dominators.cpp | 22 +++----- 4 files changed, 36 insertions(+), 79 deletions(-) diff --git a/include/llvm/IR/Dominators.h b/include/llvm/IR/Dominators.h index e10d14c1979..f0a4867415b 100644 --- a/include/llvm/IR/Dominators.h +++ b/include/llvm/IR/Dominators.h @@ -37,19 +37,11 @@ extern template class DomTreeNodeBase; extern template class DominatorTreeBase; namespace DomTreeBuilder { -extern template void Calculate( - DominatorTreeBaseByGraphTraits> &DT, Function &F); +using BBDomTree = DominatorTreeBase; -extern template void Calculate>( - DominatorTreeBaseByGraphTraits>> &DT, - Function &F); +extern template void Calculate(BBDomTree &DT, Function &F); -extern template bool Verify( - const DominatorTreeBaseByGraphTraits> &DT); - -extern template bool Verify>( - const DominatorTreeBaseByGraphTraits>> - &DT); +extern template bool Verify(const BBDomTree &DT); } // namespace DomTreeBuilder using DomTreeNode = DomTreeNodeBase; diff --git a/include/llvm/Support/GenericDomTree.h b/include/llvm/Support/GenericDomTree.h index 142e3ec3343..5acf9977640 100644 --- a/include/llvm/Support/GenericDomTree.h +++ b/include/llvm/Support/GenericDomTree.h @@ -43,25 +43,10 @@ namespace llvm { template class DominatorTreeBase; -namespace detail { - -template struct DominatorTreeBaseTraits { - static_assert(std::is_pointer::value, - "Currently NodeRef must be a pointer type."); - using type = DominatorTreeBase< - typename std::remove_pointer::type>; -}; - -} // end namespace detail - -template -using DominatorTreeBaseByGraphTraits = - typename detail::DominatorTreeBaseTraits::type; - /// \brief Base class for the actual dominator tree node. template class DomTreeNodeBase { friend struct PostDominatorTree; - template friend class DominatorTreeBase; + friend class DominatorTreeBase; NodeT *TheBB; DomTreeNodeBase *IDom; @@ -192,16 +177,16 @@ void PrintDomTree(const DomTreeNodeBase *N, raw_ostream &O, } namespace DomTreeBuilder { -template +template struct SemiNCAInfo; // The calculate routine is provided in a separate header but referenced here. -template -void Calculate(DominatorTreeBaseByGraphTraits> &DT, FuncT &F); +template +void Calculate(DomTreeT &DT, FuncT &F); // The verify function is provided in a separate header but referenced here. -template -bool Verify(const DominatorTreeBaseByGraphTraits> &DT); +template +bool Verify(const DomTreeT &DT); } // namespace DomTreeBuilder /// \brief Core dominator tree base class. @@ -221,10 +206,13 @@ template class DominatorTreeBase { mutable bool DFSInfoValid = false; mutable unsigned int SlowQueries = 0; - friend struct DomTreeBuilder::SemiNCAInfo; - using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo; + friend struct DomTreeBuilder::SemiNCAInfo; public: + static_assert(std::is_pointer::NodeRef>::value, + "Currently DominatorTreeBase supports only pointer nodes"); + using NodeType = NodeT; + using NodePtr = NodeT *; explicit DominatorTreeBase(bool isPostDom) : IsPostDominators(isPostDom) {} DominatorTreeBase(DominatorTreeBase &&Arg) @@ -612,35 +600,29 @@ public: using TraitsTy = GraphTraits; reset(); - if (!this->IsPostDominators) { + if (!IsPostDominators) { // Initialize root NodeT *entry = TraitsTy::getEntryNode(&F); addRoot(entry); - - DomTreeBuilder::Calculate(*this, F); } else { // Initialize the roots list for (auto *Node : nodes(&F)) if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node)) addRoot(Node); - - DomTreeBuilder::Calculate>(*this, F); } + + DomTreeBuilder::Calculate(*this, F); } /// verify - check parent and sibling property - bool verify() const { - return this->isPostDominator() - ? DomTreeBuilder::Verify>(*this) - : DomTreeBuilder::Verify(*this); - } + bool verify() const { return DomTreeBuilder::Verify(*this); } protected: void addRoot(NodeT *BB) { this->Roots.push_back(BB); } void reset() { DomTreeNodes.clear(); - this->Roots.clear(); + Roots.clear(); RootNode = nullptr; DFSInfoValid = false; SlowQueries = 0; diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h index 3aad8664c9a..a605585e84c 100644 --- a/include/llvm/Support/GenericDomTreeConstruction.h +++ b/include/llvm/Support/GenericDomTreeConstruction.h @@ -49,13 +49,13 @@ struct ChildrenGetter { } }; -// Information record used by Semi-NCA during tree construction. -template +template struct SemiNCAInfo { - using NodePtr = NodeT *; - using DomTreeT = DominatorTreeBase; + using NodePtr = typename DomTreeT::NodePtr; + using NodeT = typename DomTreeT::NodeType; using TreeNodePtr = DomTreeNodeBase *; + // Information record used by Semi-NCA during tree construction. struct InfoRec { unsigned DFSNum = 0; unsigned Parent = 0; @@ -524,23 +524,16 @@ struct SemiNCAInfo { } }; -template -void Calculate(DominatorTreeBaseByGraphTraits> &DT, - FuncT &F) { - using NodePtr = typename GraphTraits::NodeRef; - static_assert(std::is_pointer::value, - "NodePtr should be a pointer type"); - SemiNCAInfo::type> SNCA; + +template +void Calculate(DomTreeT &DT, FuncT &F) { + SemiNCAInfo SNCA; SNCA.calculateFromScratch(DT, GraphTraits::size(&F)); } -template -bool Verify(const DominatorTreeBaseByGraphTraits> &DT) { - using NodePtr = typename GraphTraits::NodeRef; - static_assert(std::is_pointer::value, - "NodePtr should be a pointer type"); - SemiNCAInfo::type> SNCA; - +template +bool Verify(const DomTreeT &DT) { + SemiNCAInfo SNCA; return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) && SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT); diff --git a/lib/IR/Dominators.cpp b/lib/IR/Dominators.cpp index 9bd0e297f4e..a76f9e9d04c 100644 --- a/lib/IR/Dominators.cpp +++ b/lib/IR/Dominators.cpp @@ -63,22 +63,12 @@ bool BasicBlockEdge::isSingleEdge() const { template class llvm::DomTreeNodeBase; template class llvm::DominatorTreeBase; -template void llvm::DomTreeBuilder::Calculate( - DominatorTreeBase< - typename std::remove_pointer::NodeRef>::type> - &DT, - Function &F); -template void llvm::DomTreeBuilder::Calculate>( - DominatorTreeBase>::NodeRef>::type> &DT, - Function &F); -template bool llvm::DomTreeBuilder::Verify( - const DominatorTreeBase< - typename std::remove_pointer::NodeRef>::type> - &DT); -template bool llvm::DomTreeBuilder::Verify>( - const DominatorTreeBase>::NodeRef>::type> &DT); +template void +llvm::DomTreeBuilder::Calculate( + DomTreeBuilder::BBDomTree &DT, Function &F); + +template bool llvm::DomTreeBuilder::Verify( + const DomTreeBuilder::BBDomTree &DT); bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &) { -- 2.49.0