diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h --- a/llvm/include/llvm/Support/GenericDomTree.h +++ b/llvm/include/llvm/Support/GenericDomTree.h @@ -30,6 +30,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/Support/CFGDiff.h" #include "llvm/Support/CFGUpdate.h" +#include "llvm/Support/Handle.h" #include "llvm/Support/raw_ostream.h" #include #include @@ -41,6 +42,8 @@ namespace llvm { +class GenericDominatorTreeBase; + template class DominatorTreeBase; @@ -49,93 +52,52 @@ struct SemiNCAInfo; } // namespace DomTreeBuilder -/// Base class for the actual dominator tree node. -template class DomTreeNodeBase { - friend class PostDominatorTree; - friend class DominatorTreeBase; - friend class DominatorTreeBase; - friend struct DomTreeBuilder::SemiNCAInfo>; - friend struct DomTreeBuilder::SemiNCAInfo>; +/// Type-erased base class for dominator tree nodes. Can be used for generic +/// read-only queries on a dominator tree. +class GenericDomTreeNodeBase { + friend GenericDominatorTreeBase; + template friend class DominatorTreeBase; + template friend struct DomTreeBuilder::SemiNCAInfo; - NodeT *TheBB; - DomTreeNodeBase *IDom; +protected: + BlockHandle TheBB; + GenericDomTreeNodeBase *IDom; unsigned Level; - SmallVector Children; + SmallVector Children; mutable unsigned DFSNumIn = ~0; mutable unsigned DFSNumOut = ~0; - public: - DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) - : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {} +public: + GenericDomTreeNodeBase(BlockHandle BB, GenericDomTreeNodeBase *idom) + : TheBB(BB), IDom(idom), Level(idom ? idom->Level + 1 : 0) {} - using iterator = typename SmallVector::iterator; + using iterator = typename SmallVector::iterator; using const_iterator = - typename SmallVector::const_iterator; + typename SmallVector::const_iterator; iterator begin() { return Children.begin(); } iterator end() { return Children.end(); } const_iterator begin() const { return Children.begin(); } const_iterator end() const { return Children.end(); } - DomTreeNodeBase *const &back() const { return Children.back(); } - DomTreeNodeBase *&back() { return Children.back(); } + GenericDomTreeNodeBase *const &back() const { return Children.back(); } iterator_range children() { return make_range(begin(), end()); } iterator_range children() const { return make_range(begin(), end()); } - NodeT *getBlock() const { return TheBB; } - DomTreeNodeBase *getIDom() const { return IDom; } + BlockHandle getBlock() const { return TheBB; } + GenericDomTreeNodeBase *getIDom() const { return IDom; } unsigned getLevel() const { return Level; } - std::unique_ptr addChild( - std::unique_ptr C) { - Children.push_back(C.get()); - return C; - } - bool isLeaf() const { return Children.empty(); } size_t getNumChildren() const { return Children.size(); } void clearAllChildren() { Children.clear(); } - bool compare(const DomTreeNodeBase *Other) const { - if (getNumChildren() != Other->getNumChildren()) - return true; - - if (Level != Other->Level) return true; - - SmallPtrSet OtherChildren; - for (const DomTreeNodeBase *I : *Other) { - const NodeT *Nd = I->getBlock(); - OtherChildren.insert(Nd); - } - - for (const DomTreeNodeBase *I : *this) { - const NodeT *N = I->getBlock(); - if (OtherChildren.count(N) == 0) - return true; - } - return false; - } - - void setIDom(DomTreeNodeBase *NewIDom) { - assert(IDom && "No immediate dominator?"); - if (IDom == NewIDom) return; - - auto I = find(IDom->Children, this); - assert(I != IDom->Children.end() && - "Not in immediate dominator children set!"); - // I am no longer your child... - IDom->Children.erase(I); - - // Switch to new dominator - IDom = NewIDom; - IDom->Children.push_back(this); - - UpdateLevel(); - } + bool compare(const GenericDomTreeNodeBase *Other) const; + void setIDom(GenericDomTreeNodeBase *NewIDom); /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes /// in the dominator tree. They are only guaranteed valid if @@ -143,29 +105,74 @@ unsigned getDFSNumIn() const { return DFSNumIn; } unsigned getDFSNumOut() const { return DFSNumOut; } + std::unique_ptr + addChild(std::unique_ptr C) { + Children.push_back(C.get()); + return C; + } + private: // Return true if this node is dominated by other. Use this only if DFS info // is valid. - bool DominatedBy(const DomTreeNodeBase *other) const { + bool DominatedBy(const GenericDomTreeNodeBase *other) const { return this->DFSNumIn >= other->DFSNumIn && this->DFSNumOut <= other->DFSNumOut; } - void UpdateLevel() { - assert(IDom); - if (Level == IDom->Level + 1) return; + void UpdateLevel(); +}; - SmallVector WorkStack = {this}; +/// Base class for the actual dominator tree node. +template class DomTreeNodeBase : public GenericDomTreeNodeBase { + using Wrapper = HandleWrapper; - while (!WorkStack.empty()) { - DomTreeNodeBase *Current = WorkStack.pop_back_val(); - Current->Level = Current->IDom->Level + 1; + friend class PostDominatorTree; + friend class DominatorTreeBase; + friend class DominatorTreeBase; + friend struct DomTreeBuilder::SemiNCAInfo>; + friend struct DomTreeBuilder::SemiNCAInfo>; - for (DomTreeNodeBase *C : *Current) { - assert(C->IDom); - if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C); - } - } +public: + DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *IDom) + : GenericDomTreeNodeBase(Wrapper::wrapRef(BB), IDom) {} + + struct const_iterator; + + using const_iterator_base = iterator_adaptor_base< + const_iterator, GenericDomTreeNodeBase::const_iterator, + typename std::iterator_traits< + GenericDomTreeNodeBase::const_iterator>::iterator_category, + // value_type + DomTreeNodeBase *, + typename std::iterator_traits< + GenericDomTreeNodeBase::const_iterator>::difference_type, + // pointer (not really usable, but we need to put something here) + DomTreeNodeBase *const *, + // reference (not a true reference, because operator* doesn't return one) + DomTreeNodeBase *>; + + struct const_iterator : const_iterator_base { + const_iterator() = default; + explicit const_iterator(GenericDomTreeNodeBase::const_iterator it) + : const_iterator_base(it) {} + + auto operator*() const { return static_cast(*this->I); } + }; + + auto begin() const { return const_iterator{GenericDomTreeNodeBase::begin()}; } + auto end() const { return const_iterator{GenericDomTreeNodeBase::end()}; } + + DomTreeNodeBase *back() const { + return static_cast(Children.back()); + } + + iterator_range children() const { + return make_range(begin(), end()); + } + + NodeT *getBlock() const { return Wrapper::unwrapRef(TheBB); } + DomTreeNodeBase *getIDom() const { + return static_cast(IDom); } }; @@ -186,10 +193,8 @@ void PrintDomTree(const DomTreeNodeBase *N, raw_ostream &O, unsigned Lev) { O.indent(2 * Lev) << "[" << Lev << "] " << N; - for (typename DomTreeNodeBase::const_iterator I = N->begin(), - E = N->end(); - I != E; ++I) - PrintDomTree(*I, O, Lev + 1); + for (const DomTreeNodeBase *Child : N->children()) + PrintDomTree(Child, O, Lev + 1); } namespace DomTreeBuilder { @@ -220,13 +225,111 @@ bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL); } // namespace DomTreeBuilder +/// Type-erased dominator tree base class. +/// +/// This base class of all dominator trees can be used for read-only queries +/// on a dominator tree. +class GenericDominatorTreeBase { +protected: + DenseMap> DomTreeNodes; + GenericDomTreeNodeBase *RootNode = nullptr; + + mutable bool DFSInfoValid = false; + mutable unsigned int SlowQueries = 0; + + // Disallow copying + GenericDominatorTreeBase(const GenericDominatorTreeBase &) = delete; + GenericDominatorTreeBase & + operator=(const GenericDominatorTreeBase &) = delete; + +public: + GenericDominatorTreeBase() {} + + GenericDominatorTreeBase(GenericDominatorTreeBase &&Arg) + : DomTreeNodes(std::move(Arg.DomTreeNodes)), RootNode(Arg.RootNode), + DFSInfoValid(Arg.DFSInfoValid), SlowQueries(Arg.SlowQueries) { + Arg.wipe(); + } + + GenericDominatorTreeBase &operator=(GenericDominatorTreeBase &&RHS) { + DomTreeNodes = std::move(RHS.DomTreeNodes); + RootNode = RHS.RootNode; + DFSInfoValid = RHS.DFSInfoValid; + SlowQueries = RHS.SlowQueries; + RHS.wipe(); + return *this; + } + + void reset(); + + bool compare(const GenericDominatorTreeBase &Other) const; + + /// getNode - return the (Post)DominatorTree node for the specified basic + /// block. This is the same as using operator[] on this class. The result + /// may (but is not required to) be null for a forward (backwards) + /// statically unreachable block. + GenericDomTreeNodeBase *getNode(BlockHandle BB) const { + auto I = DomTreeNodes.find(BB); + if (I != DomTreeNodes.end()) + return I->second.get(); + return nullptr; + } + + /// See getNode. + GenericDomTreeNodeBase *operator[](BlockHandle BB) const { + return getNode(BB); + } + + /// getRootNode - This returns the entry node for the CFG of the function. If + /// this tree represents the post-dominance relations for a function, however, + /// this root may be a node with the block == NULL. This is the case when + /// there are multiple exit nodes from a particular function. Consumers of + /// post-dominance information must be capable of dealing with this + /// possibility. + GenericDomTreeNodeBase *getRootNode() { return RootNode; } + const GenericDomTreeNodeBase *getRootNode() const { return RootNode; } + + bool isReachableFromEntry(const GenericDomTreeNodeBase *A) const { return A; } + + bool properlyDominates(const GenericDomTreeNodeBase *A, + const GenericDomTreeNodeBase *B) const; + bool properlyDominatesBlock(BlockHandle A, BlockHandle B) const; + + bool dominates(const GenericDomTreeNodeBase *A, + const GenericDomTreeNodeBase *B) const; + bool dominatesBlock(BlockHandle A, BlockHandle B) const; + + const GenericDomTreeNodeBase * + findNearestCommonDominator(const GenericDomTreeNodeBase *A, + const GenericDomTreeNodeBase *B) const; + BlockHandle findNearestCommonDominatorBlock(BlockHandle A, + BlockHandle B) const; + + void updateDFSNumbers() const; + +private: + /// Wipe this tree's state without releasing any resources. + /// + /// This is essentially a post-move helper only. It leaves the object in an + /// assignable and destroyable state, but otherwise invalid. + void wipe() { + DomTreeNodes.clear(); + RootNode = nullptr; + } + + bool dominatedBySlowTreeWalk(const GenericDomTreeNodeBase *A, + const GenericDomTreeNodeBase *B) const; +}; + /// 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 { - public: +class DominatorTreeBase : public GenericDominatorTreeBase { +public: + using Wrapper = HandleWrapper; + static_assert(std::is_pointer::NodeRef>::value, "Currently DominatorTreeBase supports only pointer nodes"); using NodeType = NodeT; @@ -247,45 +350,13 @@ protected: // Dominators always have a single root, postdominators can have more. SmallVector Roots; - - using DomTreeNodeMapType = - DenseMap>>; - DomTreeNodeMapType DomTreeNodes; - DomTreeNodeBase *RootNode = nullptr; ParentPtr Parent = nullptr; - mutable bool DFSInfoValid = false; - mutable unsigned int SlowQueries = 0; - friend struct DomTreeBuilder::SemiNCAInfo; - public: +public: DominatorTreeBase() {} - DominatorTreeBase(DominatorTreeBase &&Arg) - : Roots(std::move(Arg.Roots)), - DomTreeNodes(std::move(Arg.DomTreeNodes)), - RootNode(Arg.RootNode), - Parent(Arg.Parent), - DFSInfoValid(Arg.DFSInfoValid), - SlowQueries(Arg.SlowQueries) { - Arg.wipe(); - } - - DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { - Roots = std::move(RHS.Roots); - DomTreeNodes = std::move(RHS.DomTreeNodes); - RootNode = RHS.RootNode; - Parent = RHS.Parent; - DFSInfoValid = RHS.DFSInfoValid; - SlowQueries = RHS.SlowQueries; - RHS.wipe(); - return *this; - } - - DominatorTreeBase(const DominatorTreeBase &) = delete; - DominatorTreeBase &operator=(const DominatorTreeBase &) = delete; - /// Iteration over roots. /// /// This may include multiple blocks if we are computing post dominators. @@ -323,25 +394,7 @@ if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin())) return true; - const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; - if (DomTreeNodes.size() != OtherDomTreeNodes.size()) - return true; - - for (const auto &DomTreeNode : DomTreeNodes) { - NodeT *BB = DomTreeNode.first; - typename DomTreeNodeMapType::const_iterator OI = - OtherDomTreeNodes.find(BB); - if (OI == OtherDomTreeNodes.end()) - return true; - - DomTreeNodeBase &MyNd = *DomTreeNode.second; - DomTreeNodeBase &OtherNd = *OI->second; - - if (MyNd.compare(&OtherNd)) - return true; - } - - return false; + return GenericDominatorTreeBase::compare(Other); } /// getNode - return the (Post)DominatorTree node for the specified basic @@ -349,10 +402,9 @@ /// may (but is not required to) be null for a forward (backwards) /// statically unreachable block. DomTreeNodeBase *getNode(const NodeT *BB) const { - auto I = DomTreeNodes.find(BB); - if (I != DomTreeNodes.end()) - return I->second.get(); - return nullptr; + return static_cast *>( + GenericDominatorTreeBase::getNode( + Wrapper::wrapRef(const_cast(BB)))); } /// See getNode. @@ -367,8 +419,12 @@ /// post-dominance information must be capable of dealing with this /// possibility. /// - DomTreeNodeBase *getRootNode() { return RootNode; } - const DomTreeNodeBase *getRootNode() const { return RootNode; } + DomTreeNodeBase *getRootNode() { + return static_cast *>(RootNode); + } + const DomTreeNodeBase *getRootNode() const { + return static_cast *>(RootNode); + } /// Get all nodes dominated by R, including R itself. void getDescendants(NodeT *R, SmallVectorImpl &Result) const { @@ -386,124 +442,68 @@ } } - /// properlyDominates - Returns true iff A dominates B and A != B. - /// Note that this is not a constant time operation! - /// bool properlyDominates(const DomTreeNodeBase *A, const DomTreeNodeBase *B) const { - if (!A || !B) - return false; + return GenericDominatorTreeBase::properlyDominates(A, B); + } + bool properlyDominates(const NodeT *A, const NodeT *B) const { if (A == B) return false; - return dominates(A, B); + return GenericDominatorTreeBase::dominates(getNode(A), getNode(B)); } - bool properlyDominates(const NodeT *A, const NodeT *B) const; - /// isReachableFromEntry - Return true if A is dominated by the entry /// block of the function containing it. bool isReachableFromEntry(const NodeT *A) const { assert(!this->isPostDominator() && "This is not implemented for post dominators"); - return isReachableFromEntry(getNode(const_cast(A))); + return getNode(const_cast(A)) != nullptr; + } + bool isReachableFromEntry(const DomTreeNodeBase *A) const { + return A != nullptr; } - bool isReachableFromEntry(const DomTreeNodeBase *A) const { return A; } - - /// dominates - Returns true iff A dominates B. Note that this is not a - /// constant time operation! - /// bool dominates(const DomTreeNodeBase *A, const DomTreeNodeBase *B) const { - // A node trivially dominates itself. - if (B == A) - return true; - - // An unreachable node is dominated by anything. - if (!isReachableFromEntry(B)) + return GenericDominatorTreeBase::dominates(A, B); + } + bool dominates(const NodeT *A, const NodeT *B) const { + if (A == B) return true; - - // And dominates nothing. - if (!isReachableFromEntry(A)) - return false; - - if (B->getIDom() == A) return true; - - if (A->getIDom() == B) return false; - - // A can only dominate B if it is higher in the tree. - if (A->getLevel() >= B->getLevel()) return false; - - // Compare the result of the tree walk and the dfs numbers, if expensive - // checks are enabled. -#ifdef EXPENSIVE_CHECKS - assert((!DFSInfoValid || - (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && - "Tree walk disagrees with dfs numbers!"); -#endif - - if (DFSInfoValid) - return B->DominatedBy(A); - - // If we end up with too many slow queries, just update the - // DFS numbers on the theory that we are going to keep querying. - SlowQueries++; - if (SlowQueries > 32) { - updateDFSNumbers(); - return B->DominatedBy(A); - } - - return dominatedBySlowTreeWalk(A, B); + return GenericDominatorTreeBase::dominates(getNode(A), getNode(B)); } - bool dominates(const NodeT *A, const NodeT *B) const; - NodeT *getRoot() const { assert(this->Roots.size() == 1 && "Should always have entry node!"); return this->Roots[0]; } - /// Find nearest common dominator basic block for basic block A and B. A and B - /// must have tree nodes. - NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const { - assert(A && B && "Pointers are not valid"); - assert(A->getParent() == B->getParent() && - "Two blocks are not in same function"); - - // If either A or B is a entry block then it is nearest common dominator - // (for forward-dominators). - if (!isPostDominator()) { - NodeT &Entry = A->getParent()->front(); - if (A == &Entry || B == &Entry) - return &Entry; - } - - DomTreeNodeBase *NodeA = getNode(A); - DomTreeNodeBase *NodeB = getNode(B); - assert(NodeA && "A must be in the tree"); - assert(NodeB && "B must be in the tree"); - - // Use level information to go up the tree until the levels match. Then - // continue going up til we arrive at the same node. - while (NodeA != NodeB) { - if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB); - - NodeA = NodeA->IDom; - } - - return NodeA->getBlock(); + bool isVirtualRoot(const DomTreeNodeBase *A) const { + return isPostDominator() && !A->getBlock(); } + const DomTreeNodeBase * + findNearestCommonDominator(const DomTreeNodeBase *A, + const DomTreeNodeBase *B) const { + return static_cast *>( + GenericDominatorTreeBase::findNearestCommonDominator(A, B)); + } const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) const { - // Cast away the const qualifiers here. This is ok since - // const is re-introduced on the return type. - return findNearestCommonDominator(const_cast(A), - const_cast(B)); + assert(A && B && "Pointers are not valid"); + const DomTreeNodeBase *dom = + static_cast *>( + GenericDominatorTreeBase::findNearestCommonDominator(getNode(A), + getNode(B))); + return dom->getBlock(); } - - bool isVirtualRoot(const DomTreeNodeBase *A) const { - return isPostDominator() && !A->getBlock(); + NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const { + assert(A && B && "Pointers are not valid"); + const DomTreeNodeBase *dom = + static_cast *>( + GenericDominatorTreeBase::findNearestCommonDominator(getNode(A), + getNode(B))); + return dom->getBlock(); } //===--------------------------------------------------------------------===// @@ -638,13 +638,14 @@ } else { assert(Roots.size() == 1); NodeT *OldRoot = Roots.front(); - auto &OldNode = DomTreeNodes[OldRoot]; - OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot])); + auto &OldNode = DomTreeNodes[Wrapper::wrapRef(OldRoot)]; + OldNode = NewNode->addChild(std::move(OldNode)); OldNode->IDom = NewNode; OldNode->UpdateLevel(); Roots[0] = BB; } - return RootNode = NewNode; + RootNode = NewNode; + return static_cast *>(RootNode); } /// changeImmediateDominator - This method is used to update the dominator @@ -681,7 +682,7 @@ IDom->Children.erase(I); } - DomTreeNodes.erase(BB); + DomTreeNodes.erase(Wrapper::wrapRef(BB)); if (!IsPostDom) return; @@ -725,53 +726,6 @@ } 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; - } - - SmallVector *, - typename DomTreeNodeBase::const_iterator>, - 32> WorkStack; - - const DomTreeNodeBase *ThisRoot = getRootNode(); - assert((!Parent || ThisRoot) && "Empty constructed DomTree"); - if (!ThisRoot) - return; - - // Both dominators and postdominators have a single root node. In the case - // case of PostDominatorTree, this node is a virtual root. - WorkStack.push_back({ThisRoot, ThisRoot->begin()}); - - unsigned DFSNum = 0; - ThisRoot->DFSNumIn = DFSNum++; - - while (!WorkStack.empty()) { - const DomTreeNodeBase *Node = WorkStack.back().first; - const auto ChildIt = WorkStack.back().second; - - // If we visited all of the children of this node, "recurse" back up the - // stack setting the DFOutNum. - if (ChildIt == Node->end()) { - Node->DFSNumOut = DFSNum++; - WorkStack.pop_back(); - } else { - // Otherwise, recursively visit this child. - const DomTreeNodeBase *Child = *ChildIt; - ++WorkStack.back().second; - - WorkStack.push_back({Child, Child->begin()}); - Child->DFSNumIn = DFSNum++; - } - } - - SlowQueries = 0; - DFSInfoValid = true; - } - /// recalculate - compute a dominator tree for the given function void recalculate(ParentType &Func) { Parent = &Func; @@ -802,27 +756,28 @@ } void reset() { - DomTreeNodes.clear(); + GenericDominatorTreeBase::reset(); Roots.clear(); - RootNode = nullptr; Parent = nullptr; - DFSInfoValid = false; - SlowQueries = 0; } protected: void addRoot(NodeT *BB) { this->Roots.push_back(BB); } DomTreeNodeBase *createChild(NodeT *BB, DomTreeNodeBase *IDom) { - return (DomTreeNodes[BB] = IDom->addChild( - std::make_unique>(BB, IDom))) - .get(); + BlockHandle bbRef = Wrapper::wrapRef(BB); + return static_cast *>( + (DomTreeNodes[bbRef] = IDom->addChild( + std::make_unique(bbRef, IDom))) + .get()); } DomTreeNodeBase *createNode(NodeT *BB) { - return (DomTreeNodes[BB] = - std::make_unique>(BB, nullptr)) - .get(); + BlockHandle bbRef = Wrapper::wrapRef(BB); + return static_cast *>( + (DomTreeNodes[bbRef] = + std::make_unique(bbRef, nullptr)) + .get()); } // NewBB is split and now it has one successor. Update dominator tree to @@ -881,34 +836,6 @@ changeImmediateDominator(NewBBSuccNode, NewBBNode); } } - - private: - bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, - const DomTreeNodeBase *B) const { - assert(A != B); - assert(isReachableFromEntry(B)); - assert(isReachableFromEntry(A)); - - const unsigned ALevel = A->getLevel(); - const DomTreeNodeBase *IDom; - - // Don't walk nodes above A's subtree. When we reach A's level, we must - // either find A or be in some other subtree not dominated by A. - while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel) - B = IDom; // Walk up the tree - - return B == A; - } - - /// Wipe this tree's state without releasing any resources. - /// - /// This is essentially a post-move helper only. It leaves the object in an - /// assignable and destroyable state, but otherwise invalid. - void wipe() { - DomTreeNodes.clear(); - RootNode = nullptr; - Parent = nullptr; - } }; template @@ -917,33 +844,6 @@ 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 { - if (A == B) - return true; - - // Cast away the const qualifiers here. This is ok since - // this function doesn't actually return the values returned - // from getNode. - return dominates(getNode(const_cast(A)), - getNode(const_cast(B))); -} -template -bool DominatorTreeBase::properlyDominates( - const NodeT *A, const NodeT *B) const { - if (A == B) - return false; - - // Cast away the const qualifiers here. This is ok since - // this function doesn't actually return the values returned - // from getNode. - return dominates(getNode(const_cast(A)), - getNode(const_cast(B))); -} - } // end namespace llvm #endif // LLVM_SUPPORT_GENERICDOMTREE_H diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h --- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -53,6 +53,7 @@ template struct SemiNCAInfo { + using Wrapper = typename DomTreeT::Wrapper; using NodePtr = typename DomTreeT::NodePtr; using NodeT = typename DomTreeT::NodeType; using TreeNodePtr = DomTreeNodeBase *; @@ -137,7 +138,7 @@ // immediate dominator. NodePtr IDom = getIDom(BB); - assert(IDom || DT.DomTreeNodes[nullptr]); + assert(IDom || DT.DomTreeNodes[BlockHandle{}]); TreeNodePtr IDomNode = getNodeForBlock(IDom, DT); // Add a new tree node for this NodeT, and link it as a child of @@ -593,7 +594,7 @@ NodePtr Root = IsPostDom ? nullptr : DT.Roots[0]; DT.RootNode = DT.createNode(Root); - SNCA.attachNewSubtree(DT, DT.RootNode); + SNCA.attachNewSubtree(DT, DT.getRootNode()); } void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) { @@ -604,7 +605,8 @@ NodePtr W = NumToNode[i]; // Don't replace this with 'count', the insertion side effect is important - if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet? + if (DT.DomTreeNodes[Wrapper::wrapRef(W)]) + continue; // Haven't calculated this node yet? NodePtr ImmDom = getIDom(W); @@ -1142,7 +1144,7 @@ std::swap(*ChIt, IDom->Children.back()); IDom->Children.pop_back(); - DT.DomTreeNodes.erase(TN->getBlock()); + DT.DomTreeNodes.erase(Wrapper::wrapRef(TN->getBlock())); } //~~ @@ -1268,7 +1270,8 @@ doFullDFSWalk(DT, AlwaysDescend); for (auto &NodeToTN : DT.DomTreeNodes) { - const TreeNodePtr TN = NodeToTN.second.get(); + const TreeNodePtr TN = + static_cast(NodeToTN.second.get()); const NodePtr BB = TN->getBlock(); // Virtual root has a corresponding virtual CFG node. @@ -1301,7 +1304,8 @@ // Running time: O(N). static bool VerifyLevels(const DomTreeT &DT) { for (auto &NodeToTN : DT.DomTreeNodes) { - const TreeNodePtr TN = NodeToTN.second.get(); + const TreeNodePtr TN = + static_cast(NodeToTN.second.get()); const NodePtr BB = TN->getBlock(); if (!BB) continue; @@ -1356,7 +1360,8 @@ // For each tree node verify if children's DFS numbers cover their parent's // DFS numbers with no gaps. for (const auto &NodeToTN : DT.DomTreeNodes) { - const TreeNodePtr Node = NodeToTN.second.get(); + const TreeNodePtr Node = + static_cast(NodeToTN.second.get()); // Handle tree leaves. if (Node->isLeaf()) { @@ -1469,7 +1474,8 @@ // the nodes it dominated previously will now become unreachable. bool verifyParentProperty(const DomTreeT &DT) { for (auto &NodeToTN : DT.DomTreeNodes) { - const TreeNodePtr TN = NodeToTN.second.get(); + const TreeNodePtr TN = + static_cast(NodeToTN.second.get()); const NodePtr BB = TN->getBlock(); if (!BB || TN->isLeaf()) continue; @@ -1503,7 +1509,8 @@ // siblings will now still be reachable. bool verifySiblingProperty(const DomTreeT &DT) { for (auto &NodeToTN : DT.DomTreeNodes) { - const TreeNodePtr TN = NodeToTN.second.get(); + const TreeNodePtr TN = + static_cast(NodeToTN.second.get()); const NodePtr BB = TN->getBlock(); if (!BB || TN->isLeaf()) continue; diff --git a/llvm/lib/Support/CMakeLists.txt b/llvm/lib/Support/CMakeLists.txt --- a/llvm/lib/Support/CMakeLists.txt +++ b/llvm/lib/Support/CMakeLists.txt @@ -124,6 +124,7 @@ FoldingSet.cpp FormattedStream.cpp FormatVariadic.cpp + GenericDomTree.cpp GlobPattern.cpp GraphWriter.cpp Hashing.cpp diff --git a/llvm/lib/Support/GenericDomTree.cpp b/llvm/lib/Support/GenericDomTree.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Support/GenericDomTree.cpp @@ -0,0 +1,278 @@ +//===- GenericDomTree.cpp - Generic dominator trees for graphs --*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Support/GenericDomTree.h" + +#include "llvm/ADT/SmallSet.h" + +using namespace llvm; + +bool GenericDomTreeNodeBase::compare( + const GenericDomTreeNodeBase *Other) const { + if (getNumChildren() != Other->getNumChildren()) + return true; + + if (Level != Other->Level) + return true; + + SmallSet OtherChildren; + for (const GenericDomTreeNodeBase *I : *Other) { + BlockHandle Nd = I->getBlock(); + OtherChildren.insert(Nd); + } + + for (const GenericDomTreeNodeBase *I : *this) { + BlockHandle N = I->getBlock(); + if (OtherChildren.count(N) == 0) + return true; + } + return false; +} + +void GenericDomTreeNodeBase::setIDom(GenericDomTreeNodeBase *NewIDom) { + assert(IDom && "No immediate dominator?"); + if (IDom == NewIDom) + return; + + auto I = find(IDom->Children, this); + assert(I != IDom->Children.end() && + "Not in immediate dominator children set!"); + // I am no longer your child... + IDom->Children.erase(I); + + // Switch to new dominator + IDom = NewIDom; + IDom->Children.push_back(this); + + UpdateLevel(); +} + +void GenericDomTreeNodeBase::UpdateLevel() { + assert(IDom); + if (Level == IDom->Level + 1) + return; + + SmallVector WorkStack = {this}; + + while (!WorkStack.empty()) { + GenericDomTreeNodeBase *Current = WorkStack.pop_back_val(); + Current->Level = Current->IDom->Level + 1; + + for (GenericDomTreeNodeBase *C : *Current) { + assert(C->IDom); + if (C->Level != C->IDom->Level + 1) + WorkStack.push_back(C); + } + } +} + +/// compare - Return false if the other dominator tree base matches this +/// dominator tree base. Otherwise return true. +bool GenericDominatorTreeBase::compare( + const GenericDominatorTreeBase &Other) const { + if (DomTreeNodes.size() != Other.DomTreeNodes.size()) + return true; + + for (const auto &DomTreeNode : DomTreeNodes) { + BlockHandle BB = DomTreeNode.first; + auto OI = Other.DomTreeNodes.find(BB); + if (OI == Other.DomTreeNodes.end()) + return true; + + GenericDomTreeNodeBase &MyNd = *DomTreeNode.second; + GenericDomTreeNodeBase &OtherNd = *OI->second; + + if (MyNd.compare(&OtherNd)) + return true; + } + + return false; +} + +void GenericDominatorTreeBase::reset() { + DomTreeNodes.clear(); + RootNode = nullptr; + DFSInfoValid = false; + SlowQueries = 0; +} + +/// properlyDominates - Returns true iff A dominates B and A != B. +/// Note that this is not a constant time operation! +bool GenericDominatorTreeBase::properlyDominates( + const GenericDomTreeNodeBase *A, const GenericDomTreeNodeBase *B) const { + if (!A || !B) + return false; + if (A == B) + return false; + return dominates(A, B); +} + +bool GenericDominatorTreeBase::properlyDominatesBlock(BlockHandle A, + BlockHandle B) const { + if (A == B) + return false; + + return dominates(getNode(A), getNode(B)); +} + +/// dominates - Returns true iff A dominates B. Note that this is not a +/// constant time operation! +bool GenericDominatorTreeBase::dominates( + const GenericDomTreeNodeBase *A, const GenericDomTreeNodeBase *B) const { + // A node trivially dominates itself. + if (B == A) + return true; + + // An unreachable node is dominated by anything. + if (!isReachableFromEntry(B)) + return true; + + // And dominates nothing. + if (!isReachableFromEntry(A)) + return false; + + if (B->getIDom() == A) + return true; + + if (A->getIDom() == B) + return false; + + // A can only dominate B if it is higher in the tree. + if (A->getLevel() >= B->getLevel()) + return false; + + // Compare the result of the tree walk and the dfs numbers, if expensive + // checks are enabled. +#ifdef EXPENSIVE_CHECKS + assert( + (!DFSInfoValid || (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && + "Tree walk disagrees with dfs numbers!"); +#endif + + if (DFSInfoValid) + return B->DominatedBy(A); + + // If we end up with too many slow queries, just update the + // DFS numbers on the theory that we are going to keep querying. + SlowQueries++; + if (SlowQueries > 32) { + updateDFSNumbers(); + return B->DominatedBy(A); + } + + return dominatedBySlowTreeWalk(A, B); +} + +bool GenericDominatorTreeBase::dominatesBlock(BlockHandle A, + BlockHandle B) const { + if (A == B) + return true; + + // Cast away the const qualifiers here. This is ok since + // this function doesn't actually return the values returned + // from getNode. + return dominates(getNode(A), getNode(B)); +} + +/// findNearestCommonDominator - Find nearest common dominator of A and B. +const GenericDomTreeNodeBase * +GenericDominatorTreeBase::findNearestCommonDominator( + const GenericDomTreeNodeBase *A, const GenericDomTreeNodeBase *B) const { + if (A == RootNode || B == RootNode) + return RootNode; + + assert(A && "A muset be in the tree"); + assert(B && "B muset be in the tree"); + + // Use level information to go up the tree until the levels match. Then + // continue going up til we arrive at the same node. + while (A != B) { + if (A->getLevel() < B->getLevel()) + std::swap(A, B); + + A = A->IDom; + assert(A != nullptr && "nodes in different dominator trees?"); + } + + return A; +} + +BlockHandle +GenericDominatorTreeBase::findNearestCommonDominatorBlock(BlockHandle A, + BlockHandle B) const { + assert(A && B && "Pointers are not valid"); + + const GenericDomTreeNodeBase *Dom = + findNearestCommonDominator(getNode(A), getNode(B)); + + return Dom ? Dom->getBlock() : BlockHandle(); +} + +/// updateDFSNumbers - Assign In and Out numbers to the nodes while walking +/// dominator tree in dfs order. +void GenericDominatorTreeBase::updateDFSNumbers() const { + if (DFSInfoValid) { + SlowQueries = 0; + return; + } + + SmallVector, + 32> + WorkStack; + + const GenericDomTreeNodeBase *ThisRoot = getRootNode(); + if (!ThisRoot) + return; + + // Both dominators and postdominators have a single root node. In the case + // case of PostDominatorTree, this node is a virtual root. + WorkStack.push_back({ThisRoot, ThisRoot->begin()}); + + unsigned DFSNum = 0; + ThisRoot->DFSNumIn = DFSNum++; + + while (!WorkStack.empty()) { + const GenericDomTreeNodeBase *Node = WorkStack.back().first; + const auto ChildIt = WorkStack.back().second; + + // If we visited all of the children of this node, "recurse" back up the + // stack setting the DFOutNum. + if (ChildIt == Node->end()) { + Node->DFSNumOut = DFSNum++; + WorkStack.pop_back(); + } else { + // Otherwise, recursively visit this child. + const GenericDomTreeNodeBase *Child = *ChildIt; + ++WorkStack.back().second; + + WorkStack.push_back({Child, Child->begin()}); + Child->DFSNumIn = DFSNum++; + } + } + + SlowQueries = 0; + DFSInfoValid = true; +} + +bool GenericDominatorTreeBase::dominatedBySlowTreeWalk( + const GenericDomTreeNodeBase *A, const GenericDomTreeNodeBase *B) const { + assert(A != B); + assert(isReachableFromEntry(B)); + assert(isReachableFromEntry(A)); + + const unsigned ALevel = A->getLevel(); + const GenericDomTreeNodeBase *IDom; + + // Don't walk nodes above A's subtree. When we reach A's level, we must + // either find A or be in some other subtree not dominated by A. + while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel) + B = IDom; // Walk up the tree + + return B == A; +} diff --git a/llvm/lib/Transforms/Scalar/ADCE.cpp b/llvm/lib/Transforms/Scalar/ADCE.cpp --- a/llvm/lib/Transforms/Scalar/ADCE.cpp +++ b/llvm/lib/Transforms/Scalar/ADCE.cpp @@ -295,7 +295,7 @@ // return of the function. // We do this by seeing which of the postdomtree root children exit the // program, and for all others, mark the subtree live. - for (auto &PDTChild : children(PDT.getRootNode())) { + for (auto *PDTChild : children(PDT.getRootNode())) { auto *BB = PDTChild->getBlock(); auto &Info = BlockInfo[BB]; // Real function return diff --git a/llvm/lib/Transforms/Scalar/NewGVN.cpp b/llvm/lib/Transforms/Scalar/NewGVN.cpp --- a/llvm/lib/Transforms/Scalar/NewGVN.cpp +++ b/llvm/lib/Transforms/Scalar/NewGVN.cpp @@ -511,7 +511,7 @@ unsigned int NumFuncArgs = 0; // RPOOrdering of basic blocks - DenseMap RPOOrdering; + DenseMap RPOOrdering; // Congruence class info. @@ -3388,8 +3388,10 @@ for (auto &B : RPOT) { auto *Node = DT->getNode(B); if (Node->getNumChildren() > 1) - llvm::sort(Node->begin(), Node->end(), - [&](const DomTreeNode *A, const DomTreeNode *B) { + llvm::sort(Node->GenericDomTreeNodeBase::begin(), + Node->GenericDomTreeNodeBase::end(), + [&](const GenericDomTreeNodeBase *A, + const GenericDomTreeNodeBase *B) { return RPOOrdering[A] < RPOOrdering[B]; }); }