From c6d939818b7c50f6e14d04447657e670aedc3f6f Mon Sep 17 00:00:00 2001
From: Daniel Berlin <dberlin@dberlin.org>
Date: Sun, 16 Sep 2007 23:59:53 +0000
Subject: [PATCH] Fix bug in andersen's related to test_and_set. Add operator
 == and != to SparseBitVector. Simplify code for test_and_set

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42018 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/SparseBitVector.h | 30 ++++++++++++++++++++++++++----
 lib/Analysis/IPA/Andersens.cpp     |  7 +++----
 2 files changed, 29 insertions(+), 8 deletions(-)

diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index 5622aab6540..6ffc6edcfc7 100644
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -128,9 +128,11 @@ public:
 
   bool test_and_set (unsigned Idx) {
     bool old = test(Idx);
-    if (!old)
+    if (!old) {
       set(Idx);
-    return !old;
+      return true;
+    }
+    return false;
   }
 
   void reset(unsigned Idx) {
@@ -533,9 +535,29 @@ public:
 
   bool test_and_set (unsigned Idx) {
     bool old = test(Idx);
-    if (!old)
+    if (!old) {
       set(Idx);
-    return !old;
+      return true;
+    }
+    return false;
+  }
+
+  bool operator!=(const SparseBitVector &RHS) {
+    return !(*this == RHS);
+  }
+
+  bool operator==(const SparseBitVector &RHS) {
+    ElementListConstIter Iter1 = Elements.begin();
+    ElementListConstIter Iter2 = RHS.Elements.begin();
+
+    while (Iter2 != RHS.Elements.end()) {
+      if (Iter1->index() != Iter2->index()
+          || *Iter1 != *Iter2)
+        return false;
+      ++Iter1;
+      ++Iter2;
+    }
+    return Iter1 == Elements.end();
   }
 
   // Union our bitmap with the RHS and return true if we changed.
diff --git a/lib/Analysis/IPA/Andersens.cpp b/lib/Analysis/IPA/Andersens.cpp
index fed246091d7..9a1ff569b88 100644
--- a/lib/Analysis/IPA/Andersens.cpp
+++ b/lib/Analysis/IPA/Andersens.cpp
@@ -1212,10 +1212,9 @@ void Andersens::SolveConstraints() {
   }
 
   do {
-     Changed = false;
-
+    Changed = false;
     ++NumIters;
-    DOUT << "Starting iteration #" << Iteration++ << "!\n";
+    DOUT << "Starting iteration #" << Iteration++;
     // TODO: In the microoptimization category, we could just make Topo2Node
     // a fast map and thus only contain the visited nodes.
     for (unsigned i = 0; i < GraphNodes.size(); ++i) {
@@ -1295,7 +1294,7 @@ void Andersens::SolveConstraints() {
 
           // Add an edge to the graph, so we can just do regular bitmap ior next
           // time.  It may also let us notice a cycle.
-          if (!GraphNodes[*Src].Edges->test_and_set(*Dest)) {
+          if (GraphNodes[*Src].Edges->test_and_set(*Dest)) {
             if (GraphNodes[*Dest].PointsTo |= *(GraphNodes[*Src].PointsTo)) {
               GraphNodes[*Dest].Changed = true;
               // If we changed a node we've already processed, we need another
-- 
2.34.1