From 93c91e39b29142dec1d03a30df9f6e757f56c193 Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Wed, 19 Jul 2017 07:02:10 +0000 Subject: Vendor import of llvm trunk r308421: https://llvm.org/svn/llvm-project/llvm/trunk@308421 --- include/llvm/Support/GenericDomTree.h | 160 ++++++++++++++++++++++------------ 1 file changed, 105 insertions(+), 55 deletions(-) (limited to 'include/llvm/Support/GenericDomTree.h') diff --git a/include/llvm/Support/GenericDomTree.h b/include/llvm/Support/GenericDomTree.h index 394a45387d8a..706320fed9a7 100644 --- a/include/llvm/Support/GenericDomTree.h +++ b/include/llvm/Support/GenericDomTree.h @@ -41,27 +41,21 @@ namespace llvm { -template class DominatorTreeBase; +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; +namespace DomTreeBuilder { +template +struct SemiNCAInfo; +} // namespace DomTreeBuilder /// \brief Base class for the actual dominator tree node. template class DomTreeNodeBase { friend struct PostDominatorTree; - template friend class DominatorTreeBase; + friend class DominatorTreeBase; + friend class DominatorTreeBase; + friend struct DomTreeBuilder::SemiNCAInfo>; + friend struct DomTreeBuilder::SemiNCAInfo>; NodeT *TheBB; DomTreeNodeBase *IDom; @@ -192,58 +186,69 @@ void PrintDomTree(const DomTreeNodeBase *N, raw_ostream &O, } namespace DomTreeBuilder { -template -struct SemiNCAInfo; +// The routines below are provided in a separate header but referenced here. +template +void Calculate(DomTreeT &DT, FuncT &F); + +template +void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, + typename DomTreeT::NodePtr To); -// The calculate routine is provided in a separate header but referenced here. -template -void Calculate(DominatorTreeBaseByGraphTraits> &DT, FuncT &F); +template +void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, + typename DomTreeT::NodePtr To); -// 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. /// /// This class is a generic template over graph nodes. It is instantiated for /// various graphs in the LLVM IR or in the code generator. -template class DominatorTreeBase { +template +class DominatorTreeBase { protected: std::vector Roots; - bool IsPostDominators; using DomTreeNodeMapType = DenseMap>>; DomTreeNodeMapType DomTreeNodes; DomTreeNodeBase *RootNode; + using ParentPtr = decltype(std::declval()->getParent()); + ParentPtr Parent = nullptr; mutable bool DFSInfoValid = false; mutable unsigned int SlowQueries = 0; - friend struct DomTreeBuilder::SemiNCAInfo; - using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo; + friend struct DomTreeBuilder::SemiNCAInfo; public: - explicit DominatorTreeBase(bool isPostDom) : IsPostDominators(isPostDom) {} + static_assert(std::is_pointer::NodeRef>::value, + "Currently DominatorTreeBase supports only pointer nodes"); + using NodeType = NodeT; + using NodePtr = NodeT *; + static constexpr bool IsPostDominator = IsPostDom; + + DominatorTreeBase() {} DominatorTreeBase(DominatorTreeBase &&Arg) : Roots(std::move(Arg.Roots)), - IsPostDominators(Arg.IsPostDominators), DomTreeNodes(std::move(Arg.DomTreeNodes)), - RootNode(std::move(Arg.RootNode)), - DFSInfoValid(std::move(Arg.DFSInfoValid)), - SlowQueries(std::move(Arg.SlowQueries)) { + RootNode(Arg.RootNode), + Parent(Arg.Parent), + DFSInfoValid(Arg.DFSInfoValid), + SlowQueries(Arg.SlowQueries) { Arg.wipe(); } DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { Roots = std::move(RHS.Roots); - IsPostDominators = RHS.IsPostDominators; DomTreeNodes = std::move(RHS.DomTreeNodes); - RootNode = std::move(RHS.RootNode); - DFSInfoValid = std::move(RHS.DFSInfoValid); - SlowQueries = std::move(RHS.SlowQueries); + RootNode = RHS.RootNode; + Parent = RHS.Parent; + DFSInfoValid = RHS.DFSInfoValid; + SlowQueries = RHS.SlowQueries; RHS.wipe(); return *this; } @@ -259,11 +264,12 @@ template class DominatorTreeBase { /// isPostDominator - Returns true if analysis based of postdoms /// - bool isPostDominator() const { return IsPostDominators; } + bool isPostDominator() const { return IsPostDominator; } /// compare - Return false if the other dominator tree base matches this /// dominator tree base. Otherwise return true. bool compare(const DominatorTreeBase &Other) const { + if (Parent != Other.Parent) return true; const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; if (DomTreeNodes.size() != OtherDomTreeNodes.size()) @@ -443,10 +449,50 @@ template class DominatorTreeBase { const_cast(B)); } + bool isVirtualRoot(const DomTreeNodeBase *A) const { + return isPostDominator() && !A->getBlock(); + } + //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to // the CFG... + /// Inform the dominator tree about a CFG edge insertion and update the tree. + /// + /// This function has to be called just before or just after making the update + /// on the actual CFG. There cannot be any other updates that the dominator + /// tree doesn't know about. + /// + /// Note that for postdominators it automatically takes care of inserting + /// a reverse edge internally (so there's no need to swap the parameters). + /// + void insertEdge(NodeT *From, NodeT *To) { + assert(From); + assert(To); + assert(From->getParent() == Parent); + assert(To->getParent() == Parent); + DomTreeBuilder::InsertEdge(*this, From, To); + } + + /// Inform the dominator tree about a CFG edge deletion and update the tree. + /// + /// This function has to be called just after making the update + /// on the actual CFG. There cannot be any other updates that the dominator + /// tree doesn't know about. The only exception is when the deletion that the + /// tree is informed about makes some (domominator) subtree unreachable -- in + /// this case, it is fine to perform deletions within this subtree. + /// + /// Note that for postdominators it automatically takes care of deleting + /// a reverse edge internally (so there's no need to swap the parameters). + /// + void deleteEdge(NodeT *From, NodeT *To) { + assert(From); + assert(To); + assert(From->getParent() == Parent); + assert(To->getParent() == Parent); + DomTreeBuilder::DeleteEdge(*this, From, To); + } + /// Add a new node to the dominator tree information. /// /// This creates a new node as a child of DomBB dominator node, linking it @@ -530,7 +576,7 @@ template class DominatorTreeBase { /// splitBlock - BB is split and now it has one successor. Update dominator /// tree to reflect this change. void splitBlock(NodeT *NewBB) { - if (this->IsPostDominators) + if (IsPostDominator) Split>(NewBB); else Split(NewBB); @@ -607,37 +653,33 @@ public: template void recalculate(FT &F) { using TraitsTy = GraphTraits; reset(); + Parent = &F; - if (!this->IsPostDominators) { + if (!IsPostDominator) { // 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; + Parent = nullptr; DFSInfoValid = false; SlowQueries = 0; } @@ -719,13 +761,21 @@ public: void wipe() { DomTreeNodes.clear(); RootNode = nullptr; + Parent = nullptr; } }; +template +using DomTreeBase = DominatorTreeBase; + +template +using PostDomTreeBase = DominatorTreeBase; + // These two functions are declared out of line as a workaround for building // with old (< r147295) versions of clang because of pr11642. -template -bool DominatorTreeBase::dominates(const NodeT *A, const NodeT *B) const { +template +bool DominatorTreeBase::dominates(const NodeT *A, + const NodeT *B) const { if (A == B) return true; @@ -735,9 +785,9 @@ bool DominatorTreeBase::dominates(const NodeT *A, const NodeT *B) const { return dominates(getNode(const_cast(A)), getNode(const_cast(B))); } -template -bool DominatorTreeBase::properlyDominates(const NodeT *A, - const NodeT *B) const { +template +bool DominatorTreeBase::properlyDominates( + const NodeT *A, const NodeT *B) const { if (A == B) return false; -- cgit v1.2.3