DomTree: Add climbLhsUntilSiblings helper

[nhaehnle]

Summary

Change-Id: I0f756786e14ef6228d0275e69d94eb8d7460d94b

[arsenm]

llvm/lib/Support/GenericDomTree.cpp

217–219

Should go in header?

220

I'm not sure these are the right family analogies. This could also find a great uncle, or the same parent.

[nhaehnle]

llvm/lib/Support/GenericDomTree.cpp

220

Fair enough, do you have a suggestion for a better name? findSiblingOfNthUncle perhaps?

[arsenm]

llvm/lib/Support/GenericDomTree.cpp

220

I don't really have a better idea. The comment could maybe explain more of the cases it can encounter? "some ancestor" is a bit vague.

[kuhar]

llvm/lib/Support/GenericDomTree.cpp

220

I agree with arsenm, the naming is unfortunate. Maybe climbUntilSiblings?

Whatever name we settle on here, I think an ascii art with an example would really help here.

[nhaehnle]

v6:
- rename to climbLhsUntilSiblings and add some explanatory ASCII art
  and comments for why this operation could be interesting

llvm/include/llvm/Support/GenericDomTree.h

public:
   bool dominatesBlock(CfgBlockRef A, CfgBlockRef B) const;
 
   const GenericDomTreeNodeBase *
   findNearestCommonDominator(const GenericDomTreeNodeBase *A,
                              const GenericDomTreeNodeBase *B) const;
   CfgBlockRef findNearestCommonDominatorBlock(CfgBlockRef A,
                                               CfgBlockRef B) const;
 
+  const GenericDomTreeNodeBase *
+  climbLhsUntilSiblings(const GenericDomTreeNodeBase *A,
+                        const GenericDomTreeNodeBase *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() {
public:
   NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
     assert(A && B && "Pointers are not valid");
     const TreeNode *dom = static_cast<const TreeNode *>(
         GenericDominatorTreeBase::findNearestCommonDominator(getNode(A),
                                                              getNode(B)));
     return dom->getBlock();
   }
 
+  const TreeNode *climbLhsUntilSiblings(const TreeNode *A,
+                                        const TreeNode *B) const {
+    return static_cast<const TreeNode *>(
+        GenericDominatorTreeBase::climbLhsUntilSiblings(A, B));
+  }
+
   //===--------------------------------------------------------------------===//
   // API to update (Post)DominatorTree information based on modifications to
   // the CFG...
 
   /// Inform the dominator tree about a sequence of CFG edge insertions and
   /// deletions and perform a batch update on the tree.
   ///
   /// This function should be used when there were multiple CFG updates after

llvm/lib/Support/GenericDomTree.cpp

GenericDominatorTreeBase::findNearestCommonDominatorBlock(CfgBlockRef A,
   assert(A && B && "Pointers are not valid");
 
   const GenericDomTreeNodeBase *Dom =
       findNearestCommonDominator(getNode(A), getNode(B));
 
   return Dom ? Dom->getBlock() : CfgBlockRef();
 }
 
+/// climbLhsUntilSiblings - Under the assumption that \p B 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 B, or
+/// \p A is a descendant of \p B.
+///
+/// Given an edge A -> B in the control flow graph where B is _not_ dominated
+/// by A, this returns either B (if B dominates A) or a sibling of B that
+/// dominates A.
+///
+/// Example 1:
+///
+///        *
+///       / \
+///      R   B
+///      |
+///      *
+///      |
+///      A
+///
+///    --> return R
+///
+/// Example 2:
+///
+///         *
+///        / \
+///       A   B
+///
+///    --> return A
+///
+/// Example 3:
+///
+///         *
+///         |
+///         B
+///         |
+///         *
+///         |
+///         A
+///
+///    --> return B
+const GenericDomTreeNodeBase *GenericDominatorTreeBase::climbLhsUntilSiblings(
+    const GenericDomTreeNodeBase *A, const GenericDomTreeNodeBase *B) const {
+  assert(A && B && "Pointers are not valid");
+
+  // Use level information to go up the tree until the levels match.
+  assert(A->getLevel() >= B->getLevel());
+  while (A->getLevel() > B->getLevel())
+    A = A->IDom;
+
+  assert(A->IDom == B->IDom);
+
+  return A;
+}
+
 /// 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;
   }