From fe7d4e50b8a34e660a8713da79613041987c19d6 Mon Sep 17 00:00:00 2001
From: Devang Patel <dpatel@apple.com>
Date: Mon, 11 Jun 2007 23:31:22 +0000
Subject: [PATCH] Add and use DominatorTreeBase::findNearestCommonDominator().

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37545 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/Dominators.h    |  4 +++
 lib/Transforms/Utils/LoopSimplify.cpp |  2 +-
 lib/VMCore/Dominators.cpp             | 45 +++++++++++++++++++++++++++
 3 files changed, 50 insertions(+), 1 deletion(-)

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index f1d31eb87e6..755407b40d9 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -234,6 +234,10 @@ protected:
     return dominates(getNode(A), getNode(B));
   }
 
+  /// findNearestCommonDominator - Find nearest common dominator basic block
+  /// for basic block A and B. If there is no such block then return NULL.
+  BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B);
+
   // dominates - Return true if A dominates B. This performs the
   // special checks necessary if A and B are in the same basic block.
   bool dominates(Instruction *A, Instruction *B);
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 98ec288e18a..7e1281213b6 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -768,7 +768,7 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB,
   assert(i != PredBlocks.size() && "No reachable preds?");
   for (i = i + 1; i < PredBlocks.size(); ++i) {
     if (DT.isReachableFromEntry(PredBlocks[i]))
-      NewBBIDom = DT.nearestCommonDominator(NewBBIDom, PredBlocks[i]);
+      NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
   }
   assert(NewBBIDom && "No immediate dominator found??");
   
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 32c435b2c60..8b2c1a45e22 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -23,6 +23,7 @@
 #include "llvm/Instructions.h"
 #include "llvm/Support/Streams.h"
 #include <algorithm>
+#include <set>
 using namespace llvm;
 
 namespace llvm {
@@ -369,6 +370,50 @@ void DominatorTreeBase::reset() {
   RootNode = 0;
 }
 
+/// findNearestCommonDominator - Find nearest common dominator basic block
+/// for basic block A and B. If there is no such block then return NULL.
+BasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A, BasicBlock *B) {
+
+  assert (!isPostDominator()  && "This is not implemented for post dominators");
+  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.
+  BasicBlock &Entry  = A->getParent()->getEntryBlock();
+  if (A == &Entry || B == &Entry)
+    return &Entry;
+
+  // If A and B are same then A is nearest common dominator.
+  DomTreeNode *NodeA = getNode(A);
+  if (A != 0 && A == B)
+    return A;
+
+  DomTreeNode *NodeB = getNode(B);
+
+  // Collect NodeA dominators set.
+  std::set<DomTreeNode *> NodeADoms;
+  NodeADoms.insert(NodeA);
+  DomTreeNode *IDomA = NodeA->getIDom();
+  while(IDomA) {
+    NodeADoms.insert(IDomA);
+    IDomA = IDomA->getIDom();
+  }
+
+  // If B dominates A then B is nearest common dominator.
+  if (NodeADoms.count(NodeB) != 0)
+    return B;
+
+  // Walk NodeB immediate dominators chain and find common dominator node.
+  DomTreeNode *IDomB = NodeB->getIDom();
+  while(IDomB) {
+    if (NodeADoms.count(IDomB) != 0)
+      return IDomB->getBlock();
+
+    IDomB = IDomB->getIDom();
+  }
+
+  return NULL;
+}
+
 void DomTreeNode::setIDom(DomTreeNode *NewIDom) {
   assert(IDom && "No immediate dominator?");
   if (IDom != NewIDom) {
-- 
2.34.1