From 5ca98fd98791947eba83a1ed3f2c8191ef7afa6c Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Mon, 24 Nov 2014 09:08:18 +0000 Subject: Vendor import of llvm RELEASE_350/final tag r216957 (effectively, 3.5.0 release): https://llvm.org/svn/llvm-project/llvm/tags/RELEASE_350/final@216957 --- include/llvm/Support/GenericDomTree.h | 736 ++++++++++++++++++++++++++++++++++ 1 file changed, 736 insertions(+) create mode 100644 include/llvm/Support/GenericDomTree.h (limited to 'include/llvm/Support/GenericDomTree.h') diff --git a/include/llvm/Support/GenericDomTree.h b/include/llvm/Support/GenericDomTree.h new file mode 100644 index 000000000000..876ab6ec71a5 --- /dev/null +++ b/include/llvm/Support/GenericDomTree.h @@ -0,0 +1,736 @@ +//===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file defines a set of templates that efficiently compute a dominator +/// tree over a generic graph. This is used typically in LLVM for fast +/// dominance queries on the CFG, but is fully generic w.r.t. the underlying +/// graph types. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_GENERIC_DOM_TREE_H +#define LLVM_SUPPORT_GENERIC_DOM_TREE_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/raw_ostream.h" +#include + +namespace llvm { + +//===----------------------------------------------------------------------===// +/// DominatorBase - Base class that other, more interesting dominator analyses +/// inherit from. +/// +template +class DominatorBase { +protected: + std::vector Roots; + const bool IsPostDominators; + inline explicit DominatorBase(bool isPostDom) : + Roots(), IsPostDominators(isPostDom) {} +public: + + /// getRoots - Return the root blocks of the current CFG. This may include + /// multiple blocks if we are computing post dominators. For forward + /// dominators, this will always be a single block (the entry node). + /// + inline const std::vector &getRoots() const { return Roots; } + + /// isPostDominator - Returns true if analysis based of postdoms + /// + bool isPostDominator() const { return IsPostDominators; } +}; + + +//===----------------------------------------------------------------------===// +// DomTreeNodeBase - Dominator Tree Node +template class DominatorTreeBase; +struct PostDominatorTree; + +template +class DomTreeNodeBase { + NodeT *TheBB; + DomTreeNodeBase *IDom; + std::vector *> Children; + mutable int DFSNumIn, DFSNumOut; + + template friend class DominatorTreeBase; + friend struct PostDominatorTree; +public: + typedef typename std::vector *>::iterator iterator; + typedef typename std::vector *>::const_iterator + 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(); } + + NodeT *getBlock() const { return TheBB; } + DomTreeNodeBase *getIDom() const { return IDom; } + const std::vector*> &getChildren() const { + return Children; + } + + DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) + : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { } + + DomTreeNodeBase *addChild(DomTreeNodeBase *C) { + Children.push_back(C); + return C; + } + + size_t getNumChildren() const { + return Children.size(); + } + + void clearAllChildren() { + Children.clear(); + } + + bool compare(const DomTreeNodeBase *Other) const { + if (getNumChildren() != Other->getNumChildren()) + return true; + + SmallPtrSet OtherChildren; + for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) { + const NodeT *Nd = (*I)->getBlock(); + OtherChildren.insert(Nd); + } + + for (const_iterator I = begin(), E = end(); I != E; ++I) { + 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) { + typename std::vector*>::iterator I = + std::find(IDom->Children.begin(), IDom->Children.end(), 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); + } + } + + /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do + /// not call them. + unsigned getDFSNumIn() const { return DFSNumIn; } + unsigned getDFSNumOut() const { return DFSNumOut; } +private: + // Return true if this node is dominated by other. Use this only if DFS info + // is valid. + bool DominatedBy(const DomTreeNodeBase *other) const { + return this->DFSNumIn >= other->DFSNumIn && + this->DFSNumOut <= other->DFSNumOut; + } +}; + +template +inline raw_ostream &operator<<(raw_ostream &o, + const DomTreeNodeBase *Node) { + if (Node->getBlock()) + Node->getBlock()->printAsOperand(o, false); + else + o << " <>"; + + o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; + + return o << "\n"; +} + +template +inline 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); +} + +//===----------------------------------------------------------------------===// +/// DominatorTree - Calculate the immediate dominator tree for a function. +/// + +template +void Calculate(DominatorTreeBase::NodeType>& DT, + FuncT& F); + +template +class DominatorTreeBase : public DominatorBase { + bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, + const DomTreeNodeBase *B) const { + assert(A != B); + assert(isReachableFromEntry(B)); + assert(isReachableFromEntry(A)); + + const DomTreeNodeBase *IDom; + while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B) + B = IDom; // Walk up the tree + return IDom != nullptr; + } + +protected: + typedef DenseMap*> DomTreeNodeMapType; + DomTreeNodeMapType DomTreeNodes; + DomTreeNodeBase *RootNode; + + mutable bool DFSInfoValid; + mutable unsigned int SlowQueries; + // Information record used during immediate dominators computation. + struct InfoRec { + unsigned DFSNum; + unsigned Parent; + unsigned Semi; + NodeT *Label; + + InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(nullptr) {} + }; + + DenseMap IDoms; + + // Vertex - Map the DFS number to the NodeT* + std::vector Vertex; + + // Info - Collection of information used during the computation of idoms. + DenseMap Info; + + void reset() { + for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(), + E = DomTreeNodes.end(); I != E; ++I) + delete I->second; + DomTreeNodes.clear(); + IDoms.clear(); + this->Roots.clear(); + Vertex.clear(); + RootNode = nullptr; + } + + // NewBB is split and now it has one successor. Update dominator tree to + // reflect this change. + template + void Split(DominatorTreeBase& DT, + typename GraphT::NodeType* NewBB) { + assert(std::distance(GraphT::child_begin(NewBB), + GraphT::child_end(NewBB)) == 1 && + "NewBB should have a single successor!"); + typename GraphT::NodeType* NewBBSucc = *GraphT::child_begin(NewBB); + + std::vector PredBlocks; + typedef GraphTraits > InvTraits; + for (typename InvTraits::ChildIteratorType PI = + InvTraits::child_begin(NewBB), + PE = InvTraits::child_end(NewBB); PI != PE; ++PI) + PredBlocks.push_back(*PI); + + assert(!PredBlocks.empty() && "No predblocks?"); + + bool NewBBDominatesNewBBSucc = true; + for (typename InvTraits::ChildIteratorType PI = + InvTraits::child_begin(NewBBSucc), + E = InvTraits::child_end(NewBBSucc); PI != E; ++PI) { + typename InvTraits::NodeType *ND = *PI; + if (ND != NewBB && !DT.dominates(NewBBSucc, ND) && + DT.isReachableFromEntry(ND)) { + NewBBDominatesNewBBSucc = false; + break; + } + } + + // Find NewBB's immediate dominator and create new dominator tree node for + // NewBB. + NodeT *NewBBIDom = nullptr; + unsigned i = 0; + for (i = 0; i < PredBlocks.size(); ++i) + if (DT.isReachableFromEntry(PredBlocks[i])) { + NewBBIDom = PredBlocks[i]; + break; + } + + // It's possible that none of the predecessors of NewBB are reachable; + // in that case, NewBB itself is unreachable, so nothing needs to be + // changed. + if (!NewBBIDom) + return; + + for (i = i + 1; i < PredBlocks.size(); ++i) { + if (DT.isReachableFromEntry(PredBlocks[i])) + NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); + } + + // Create the new dominator tree node... and set the idom of NewBB. + DomTreeNodeBase *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom); + + // If NewBB strictly dominates other blocks, then it is now the immediate + // dominator of NewBBSucc. Update the dominator tree as appropriate. + if (NewBBDominatesNewBBSucc) { + DomTreeNodeBase *NewBBSuccNode = DT.getNode(NewBBSucc); + DT.changeImmediateDominator(NewBBSuccNode, NewBBNode); + } + } + +public: + explicit DominatorTreeBase(bool isPostDom) + : DominatorBase(isPostDom), DFSInfoValid(false), SlowQueries(0) {} + virtual ~DominatorTreeBase() { reset(); } + + /// compare - Return false if the other dominator tree base matches this + /// dominator tree base. Otherwise return true. + bool compare(const DominatorTreeBase &Other) const { + + const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; + if (DomTreeNodes.size() != OtherDomTreeNodes.size()) + return true; + + for (typename DomTreeNodeMapType::const_iterator + I = this->DomTreeNodes.begin(), + E = this->DomTreeNodes.end(); I != E; ++I) { + NodeT *BB = I->first; + typename DomTreeNodeMapType::const_iterator OI = OtherDomTreeNodes.find(BB); + if (OI == OtherDomTreeNodes.end()) + return true; + + DomTreeNodeBase* MyNd = I->second; + DomTreeNodeBase* OtherNd = OI->second; + + if (MyNd->compare(OtherNd)) + return true; + } + + return false; + } + + virtual void releaseMemory() { reset(); } + + /// getNode - return the (Post)DominatorTree node for the specified basic + /// block. This is the same as using operator[] on this class. + /// + inline DomTreeNodeBase *getNode(NodeT *BB) const { + return DomTreeNodes.lookup(BB); + } + + inline DomTreeNodeBase *operator[](NodeT *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. + /// + DomTreeNodeBase *getRootNode() { return RootNode; } + const DomTreeNodeBase *getRootNode() const { return RootNode; } + + /// Get all nodes dominated by R, including R itself. + void getDescendants(NodeT *R, SmallVectorImpl &Result) const { + Result.clear(); + const DomTreeNodeBase *RN = getNode(R); + if (!RN) + return; // If R is unreachable, it will not be present in the DOM tree. + SmallVector *, 8> WL; + WL.push_back(RN); + + while (!WL.empty()) { + const DomTreeNodeBase *N = WL.pop_back_val(); + Result.push_back(N->getBlock()); + WL.append(N->begin(), N->end()); + } + } + + /// 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; + if (A == B) + return false; + return dominates(A, 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))); + } + + inline bool isReachableFromEntry(const DomTreeNodeBase *A) const { + return A; + } + + /// dominates - Returns true iff A dominates B. Note that this is not a + /// constant time operation! + /// + inline 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 true; + + // And dominates nothing. + if (!isReachableFromEntry(A)) + return false; + + // Compare the result of the tree walk and the dfs numbers, if expensive + // checks are enabled. +#ifdef XDEBUG + 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 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]; + } + + /// findNearestCommonDominator - Find nearest common dominator basic block + /// for basic block A and B. If there is no such block then return NULL. + NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) { + 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 (!this->isPostDominator()) { + NodeT &Entry = A->getParent()->front(); + if (A == &Entry || B == &Entry) + return &Entry; + } + + // If B dominates A then B is nearest common dominator. + if (dominates(B, A)) + return B; + + // If A dominates B then A is nearest common dominator. + if (dominates(A, B)) + return A; + + DomTreeNodeBase *NodeA = getNode(A); + DomTreeNodeBase *NodeB = getNode(B); + + // If we have DFS info, then we can avoid all allocations by just querying + // it from each IDom. Note that because we call 'dominates' twice above, we + // expect to call through this code at most 16 times in a row without + // building valid DFS information. This is important as below is a *very* + // slow tree walk. + if (DFSInfoValid) { + DomTreeNodeBase *IDomA = NodeA->getIDom(); + while (IDomA) { + if (NodeB->DominatedBy(IDomA)) + return IDomA->getBlock(); + IDomA = IDomA->getIDom(); + } + return nullptr; + } + + // Collect NodeA dominators set. + SmallPtrSet*, 16> NodeADoms; + NodeADoms.insert(NodeA); + DomTreeNodeBase *IDomA = NodeA->getIDom(); + while (IDomA) { + NodeADoms.insert(IDomA); + IDomA = IDomA->getIDom(); + } + + // Walk NodeB immediate dominators chain and find common dominator node. + DomTreeNodeBase *IDomB = NodeB->getIDom(); + while (IDomB) { + if (NodeADoms.count(IDomB) != 0) + return IDomB->getBlock(); + + IDomB = IDomB->getIDom(); + } + + return nullptr; + } + + const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { + // 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)); + } + + //===--------------------------------------------------------------------===// + // API to update (Post)DominatorTree information based on modifications to + // the CFG... + + /// addNewBlock - Add a new node to the dominator tree information. This + /// creates a new node as a child of DomBB dominator node,linking it into + /// the children list of the immediate dominator. + DomTreeNodeBase *addNewBlock(NodeT *BB, NodeT *DomBB) { + assert(getNode(BB) == nullptr && "Block already in dominator tree!"); + DomTreeNodeBase *IDomNode = getNode(DomBB); + assert(IDomNode && "Not immediate dominator specified for block!"); + DFSInfoValid = false; + return DomTreeNodes[BB] = + IDomNode->addChild(new DomTreeNodeBase(BB, IDomNode)); + } + + /// changeImmediateDominator - This method is used to update the dominator + /// tree information when a node's immediate dominator changes. + /// + void changeImmediateDominator(DomTreeNodeBase *N, + DomTreeNodeBase *NewIDom) { + assert(N && NewIDom && "Cannot change null node pointers!"); + DFSInfoValid = false; + N->setIDom(NewIDom); + } + + void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { + changeImmediateDominator(getNode(BB), getNode(NewBB)); + } + + /// eraseNode - Removes a node from the dominator tree. Block must not + /// dominate any other blocks. Removes node from its immediate dominator's + /// children list. Deletes dominator node associated with basic block BB. + void eraseNode(NodeT *BB) { + DomTreeNodeBase *Node = getNode(BB); + assert(Node && "Removing node that isn't in dominator tree."); + assert(Node->getChildren().empty() && "Node is not a leaf node."); + + // Remove node from immediate dominator's children list. + DomTreeNodeBase *IDom = Node->getIDom(); + if (IDom) { + typename std::vector*>::iterator I = + std::find(IDom->Children.begin(), IDom->Children.end(), Node); + assert(I != IDom->Children.end() && + "Not in immediate dominator children set!"); + // I am no longer your child... + IDom->Children.erase(I); + } + + DomTreeNodes.erase(BB); + delete Node; + } + + /// removeNode - Removes a node from the dominator tree. Block must not + /// dominate any other blocks. Invalidates any node pointing to removed + /// block. + void removeNode(NodeT *BB) { + assert(getNode(BB) && "Removing node that isn't in dominator tree."); + DomTreeNodes.erase(BB); + } + + /// splitBlock - BB is split and now it has one successor. Update dominator + /// tree to reflect this change. + void splitBlock(NodeT* NewBB) { + if (this->IsPostDominators) + this->Split, GraphTraits > >(*this, NewBB); + else + this->Split >(*this, NewBB); + } + + /// print - Convert to human readable form + /// + void print(raw_ostream &o) const { + o << "=============================--------------------------------\n"; + if (this->isPostDominator()) + o << "Inorder PostDominator Tree: "; + else + o << "Inorder Dominator Tree: "; + if (!this->DFSInfoValid) + o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; + o << "\n"; + + // The postdom tree can have a null root if there are no returns. + if (getRootNode()) + PrintDomTree(getRootNode(), o, 1); + } + +protected: + template + friend typename GraphT::NodeType* Eval( + DominatorTreeBase& DT, + typename GraphT::NodeType* V, + unsigned LastLinked); + + template + friend unsigned DFSPass(DominatorTreeBase& DT, + typename GraphT::NodeType* V, + unsigned N); + + template + friend void Calculate(DominatorTreeBase::NodeType>& DT, + FuncT& F); + + /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking + /// dominator tree in dfs order. + void updateDFSNumbers() const { + unsigned DFSNum = 0; + + SmallVector*, + typename DomTreeNodeBase::const_iterator>, 32> WorkStack; + + const DomTreeNodeBase *ThisRoot = getRootNode(); + + if (!ThisRoot) + return; + + // Even in the case of multiple exits that form the post dominator root + // nodes, do not iterate over all exits, but start from the virtual root + // node. Otherwise bbs, that are not post dominated by any exit but by the + // virtual root node, will never be assigned a DFS number. + WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); + ThisRoot->DFSNumIn = DFSNum++; + + while (!WorkStack.empty()) { + const DomTreeNodeBase *Node = WorkStack.back().first; + typename DomTreeNodeBase::const_iterator 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(std::make_pair(Child, Child->begin())); + Child->DFSNumIn = DFSNum++; + } + } + + SlowQueries = 0; + DFSInfoValid = true; + } + + DomTreeNodeBase *getNodeForBlock(NodeT *BB) { + if (DomTreeNodeBase *Node = getNode(BB)) + return Node; + + // Haven't calculated this node yet? Get or calculate the node for the + // immediate dominator. + NodeT *IDom = getIDom(BB); + + assert(IDom || this->DomTreeNodes[nullptr]); + DomTreeNodeBase *IDomNode = getNodeForBlock(IDom); + + // Add a new tree node for this NodeT, and link it as a child of + // IDomNode + DomTreeNodeBase *C = new DomTreeNodeBase(BB, IDomNode); + return this->DomTreeNodes[BB] = IDomNode->addChild(C); + } + + inline NodeT *getIDom(NodeT *BB) const { + return IDoms.lookup(BB); + } + + inline void addRoot(NodeT* BB) { + this->Roots.push_back(BB); + } + +public: + /// recalculate - compute a dominator tree for the given function + template + void recalculate(FT& F) { + typedef GraphTraits TraitsTy; + reset(); + this->Vertex.push_back(nullptr); + + if (!this->IsPostDominators) { + // Initialize root + NodeT *entry = TraitsTy::getEntryNode(&F); + this->Roots.push_back(entry); + this->IDoms[entry] = nullptr; + this->DomTreeNodes[entry] = nullptr; + + Calculate(*this, F); + } else { + // Initialize the roots list + for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), + E = TraitsTy::nodes_end(&F); I != E; ++I) { + if (TraitsTy::child_begin(I) == TraitsTy::child_end(I)) + addRoot(I); + + // Prepopulate maps so that we don't get iterator invalidation issues later. + this->IDoms[I] = nullptr; + this->DomTreeNodes[I] = nullptr; + } + + Calculate >(*this, F); + } + } +}; + +// 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))); +} + +} + +#endif -- cgit v1.2.3