From a45a9e416fb24b55c1a0af2369bfda8560edcb50 Mon Sep 17 00:00:00 2001
From: Devang Patel <dpatel@apple.com>
Date: Tue, 1 Jul 2008 21:41:00 +0000
Subject: [PATCH] Fix dom tree compare. Don't forget to compare children!

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52984 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/Dominators.h | 60 ++++++++++++++++++------------
 1 file changed, 36 insertions(+), 24 deletions(-)

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 86a0457df9f..6e944d32b36 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -94,7 +94,7 @@ public:
   const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const {
     return Children;
   }
-  
+
   DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
     : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
   
@@ -106,7 +106,29 @@ public:
   size_t getNumChildren() const {
     return Children.size();
   }
+
+  void clearAllChildren() {
+    Children.clear();
+  }
   
+  bool compare(DomTreeNodeBase<NodeT> *Other) {
+    if (getNumChildren() != Other->getNumChildren())
+      return true;
+
+    SmallPtrSet<NodeT *, 4> OtherChildren;
+    for(iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
+      NodeT *Nd = (*I)->getBlock();
+      OtherChildren.insert(Nd);
+    }
+
+    for(iterator I = begin(), E = end(); I != E; ++I) {
+      NodeT *N = (*I)->getBlock();
+      if (OtherChildren.count(N) == 0)
+        return true;
+    }
+    return false;
+  }
+
   void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
     assert(IDom && "No immediate dominator?");
     if (IDom != NewIDom) {
@@ -312,36 +334,26 @@ public:
   /// dominator tree base. Otherwise return true.
   bool compare(DominatorTreeBase &Other) const {
 
-    // Collect nodes.
+    const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
+    if (DomTreeNodes.size() != OtherDomTreeNodes.size())
+      return true;
+
     SmallPtrSet<const NodeT *,4> MyBBs;
     for (typename DomTreeNodeMapType::const_iterator 
            I = this->DomTreeNodes.begin(),
            E = this->DomTreeNodes.end(); I != E; ++I) {
-      const NodeT *BB = I->first;
-      MyBBs.insert(BB);
-    }
-
-    SmallPtrSet<const NodeT *,4> OtherBBs;
-    const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
-    for (typename DomTreeNodeMapType::const_iterator 
-           I = OtherDomTreeNodes.begin(),
-           E = OtherDomTreeNodes.end(); I != E; ++I) {
-      const NodeT *BB = I->first;
-      OtherBBs.insert(BB);
-    }
-
-    if (OtherBBs.size() != MyBBs.size())
-      return true;
+      NodeT *BB = I->first;
+      typename DomTreeNodeMapType::const_iterator OI = OtherDomTreeNodes.find(BB);
+      if (OI == OtherDomTreeNodes.end())
+        return true;
 
-    // Compare node sets.
-    for (typename SmallPtrSet<const NodeT *,4>::const_iterator I = MyBBs.begin(),
-           E = MyBBs.end(); I != E; ++I) {
-      const NodeT *BB = *I;
-      if (OtherBBs.erase(BB) == 0)
+      DomTreeNodeBase<NodeT>* MyNd = I->second;
+      DomTreeNodeBase<NodeT>* OtherNd = OI->second;
+      
+      if (MyNd->compare(OtherNd))
         return true;
     }
-    if (!OtherBBs.empty())
-      return true;
+
     return false;
   }
 
-- 
2.34.1