diff options
Diffstat (limited to 'include/llvm/Support/GenericDomTree.h')
-rw-r--r-- | include/llvm/Support/GenericDomTree.h | 45 |
1 files changed, 30 insertions, 15 deletions
diff --git a/include/llvm/Support/GenericDomTree.h b/include/llvm/Support/GenericDomTree.h index 6878844..e344220 100644 --- a/include/llvm/Support/GenericDomTree.h +++ b/include/llvm/Support/GenericDomTree.h @@ -186,9 +186,9 @@ class DominatorTreeBase : public DominatorBase<NodeT> { assert(isReachableFromEntry(A)); const DomTreeNodeBase<NodeT> *IDom; - while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B) + while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B) B = IDom; // Walk up the tree - return IDom != 0; + return IDom != nullptr; } protected: @@ -205,7 +205,7 @@ protected: unsigned Semi; NodeT *Label; - InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(0) {} + InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(nullptr) {} }; DenseMap<NodeT*, NodeT*> IDoms; @@ -224,7 +224,7 @@ protected: IDoms.clear(); this->Roots.clear(); Vertex.clear(); - RootNode = 0; + RootNode = nullptr; } // NewBB is split and now it has one successor. Update dominator tree to @@ -260,7 +260,7 @@ protected: // Find NewBB's immediate dominator and create new dominator tree node for // NewBB. - NodeT *NewBBIDom = 0; + NodeT *NewBBIDom = nullptr; unsigned i = 0; for (i = 0; i < PredBlocks.size(); ++i) if (DT.isReachableFromEntry(PredBlocks[i])) { @@ -344,7 +344,7 @@ public: void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { Result.clear(); const DomTreeNodeBase<NodeT> *RN = getNode(R); - if (RN == NULL) + if (!RN) return; // If R is unreachable, it will not be present in the DOM tree. SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; WL.push_back(RN); @@ -361,7 +361,7 @@ public: /// bool properlyDominates(const DomTreeNodeBase<NodeT> *A, const DomTreeNodeBase<NodeT> *B) const { - if (A == 0 || B == 0) + if (!A || !B) return false; if (A == B) return false; @@ -453,6 +453,21 @@ public: DomTreeNodeBase<NodeT> *NodeA = getNode(A); DomTreeNodeBase<NodeT> *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<NodeT> *IDomA = NodeA->getIDom(); + while (IDomA) { + if (NodeB->DominatedBy(IDomA)) + return IDomA->getBlock(); + IDomA = IDomA->getIDom(); + } + return nullptr; + } + // Collect NodeA dominators set. SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms; NodeADoms.insert(NodeA); @@ -471,7 +486,7 @@ public: IDomB = IDomB->getIDom(); } - return NULL; + return nullptr; } const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { @@ -489,7 +504,7 @@ public: /// creates a new node as a child of DomBB dominator node,linking it into /// the children list of the immediate dominator. DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { - assert(getNode(BB) == 0 && "Block already in dominator tree!"); + assert(getNode(BB) == nullptr && "Block already in dominator tree!"); DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); assert(IDomNode && "Not immediate dominator specified for block!"); DFSInfoValid = false; @@ -636,7 +651,7 @@ protected: // immediate dominator. NodeT *IDom = getIDom(BB); - assert(IDom || this->DomTreeNodes[NULL]); + assert(IDom || this->DomTreeNodes[nullptr]); DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom); // Add a new tree node for this NodeT, and link it as a child of @@ -659,14 +674,14 @@ public: void recalculate(FT& F) { typedef GraphTraits<FT*> TraitsTy; reset(); - this->Vertex.push_back(0); + this->Vertex.push_back(nullptr); if (!this->IsPostDominators) { // Initialize root NodeT *entry = TraitsTy::getEntryNode(&F); this->Roots.push_back(entry); - this->IDoms[entry] = 0; - this->DomTreeNodes[entry] = 0; + this->IDoms[entry] = nullptr; + this->DomTreeNodes[entry] = nullptr; Calculate<FT, NodeT*>(*this, F); } else { @@ -677,8 +692,8 @@ public: addRoot(I); // Prepopulate maps so that we don't get iterator invalidation issues later. - this->IDoms[I] = 0; - this->DomTreeNodes[I] = 0; + this->IDoms[I] = nullptr; + this->DomTreeNodes[I] = nullptr; } Calculate<FT, Inverse<NodeT*> >(*this, F); |