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 @@ -307,6 +307,10 @@ CfgBlockRef findNearestCommonDominatorBlock(CfgBlockRef A, CfgBlockRef B) const; + const GenericDomTreeNodeBase * + findSiblingOfUncle(const GenericDomTreeNodeBase *A, + const GenericDomTreeNodeBase *Uncle) const; + void updateDFSNumbers() const; private: @@ -497,6 +501,12 @@ return dom->getBlock(); } + const TreeNode *findSiblingOfUncle(const TreeNode *A, + const TreeNode *Uncle) const { + return static_cast( + GenericDominatorTreeBase::findSiblingOfUncle(A, Uncle)); + } + //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to // the CFG... diff --git a/llvm/lib/Support/GenericDomTree.cpp b/llvm/lib/Support/GenericDomTree.cpp --- a/llvm/lib/Support/GenericDomTree.cpp +++ b/llvm/lib/Support/GenericDomTree.cpp @@ -214,6 +214,24 @@ return Dom ? Dom->getBlock() : CfgBlockRef(); } +/// findSiblingOfUncle - Under the assumption that \p Uncle is the sibling +/// of some ancestor of \p A in the tree, find that ancestor. Also handles +/// the degenerate case where \p A itself is a sibling of \p Uncle. +const GenericDomTreeNodeBase *GenericDominatorTreeBase::findSiblingOfUncle( + const GenericDomTreeNodeBase *A, + const GenericDomTreeNodeBase *Uncle) const { + assert(A && Uncle && "Pointers are not valid"); + + // Use level information to go up the tree until the levels match. + assert(A->getLevel() >= Uncle->getLevel()); + while (A->getLevel() > Uncle->getLevel()) + A = A->IDom; + + assert(A->IDom == Uncle->IDom && "Uncle was not in fact an uncle"); + + return A; +} + /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking /// dominator tree in dfs order. void GenericDominatorTreeBase::updateDFSNumbers() const {