Move IsSameValue from clang's ASTImporter to be methods on the

[oota-llvm.git] / include / llvm / ADT / SCCIterator.h

diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h
index d38ce4cd634bb9791e95c3a274de0c3d4c5bc8a7..48436c667474c8342e24b33f2ad809dfb82bfaef 100644 (file)
--- a/include/llvm/ADT/SCCIterator.h
+++ b/include/llvm/ADT/SCCIterator.h
@@ -1,4 +1,4 @@
-//===-- Support/SCCIterator.h - Strongly Connected Comp. Iter. --*- C++ -*-===//
+//===---- ADT/SCCIterator.h - Strongly Connected Comp. Iter. ----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -60,13 +60,13 @@ class scc_iterator
   // First element is basic block pointer, second is the 'next child' to visit
   std::vector<std::pair<NodeType *, ChildItTy> > VisitStack;
 
-  // MinVistNumStack - Stack holding the "min" values for each node in the DFS.
+  // MinVisitNumStack - Stack holding the "min" values for each node in the DFS.
   // This is used to track the minimum uplink values for all children of
   // the corresponding node on the VisitStack.
   std::vector<unsigned> MinVisitNumStack;
 
   // A single "visit" within the non-recursive DFS traversal.
-  void DFSVisitOne(NodeType* N) {
+  void DFSVisitOne(NodeType *N) {
     ++visitNum;                         // Global counter for the visit order
     nodeVisitNumbers[N] = visitNum;
     SCCNodeStack.push_back(N);
@@ -83,13 +83,14 @@ class scc_iterator
       // TOS has at least one more child so continue DFS
       NodeType *childN = *VisitStack.back().second++;
       if (!nodeVisitNumbers.count(childN)) {
-        // this node has never been seen
+        // this node has never been seen.
         DFSVisitOne(childN);
-      } else {
-        unsigned childNum = nodeVisitNumbers[childN];
-        if (MinVisitNumStack.back() > childNum)
-          MinVisitNumStack.back() = childNum;
+        continue;
       }
+
+      unsigned childNum = nodeVisitNumbers[childN];
+      if (MinVisitNumStack.back() > childNum)
+        MinVisitNumStack.back() = childNum;
     }
   }
 
@@ -100,7 +101,7 @@ class scc_iterator
     while (!VisitStack.empty()) {
       DFSVisitChildren();
       assert(VisitStack.back().second ==GT::child_end(VisitStack.back().first));
-      NodeType* visitingN = VisitStack.back().first;
+      NodeType *visitingN = VisitStack.back().first;
       unsigned minVisitNum = MinVisitNumStack.back();
       VisitStack.pop_back();
       MinVisitNumStack.pop_back();
@@ -111,18 +112,19 @@ class scc_iterator
       //      " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
       //      nodeVisitNumbers[visitingN] << "\n";
 
-      if (minVisitNum == nodeVisitNumbers[visitingN]) {
-        // A full SCC is on the SCCNodeStack!  It includes all nodes below
-          // visitingN on the stack.  Copy those nodes to CurrentSCC,
-          // reset their minVisit values, and return (this suspends
-          // the DFS traversal till the next ++).
-          do {
-            CurrentSCC.push_back(SCCNodeStack.back());
-            SCCNodeStack.pop_back();
-            nodeVisitNumbers[CurrentSCC.back()] = ~0U;
-          } while (CurrentSCC.back() != visitingN);
-          return;
-        }
+      if (minVisitNum != nodeVisitNumbers[visitingN])
+        continue;
+
+      // A full SCC is on the SCCNodeStack!  It includes all nodes below
+      // visitingN on the stack.  Copy those nodes to CurrentSCC,
+      // reset their minVisit values, and return (this suspends
+      // the DFS traversal till the next ++).
+      do {
+        CurrentSCC.push_back(SCCNodeStack.back());
+        SCCNodeStack.pop_back();
+        nodeVisitNumbers[CurrentSCC.back()] = ~0U;
+      } while (CurrentSCC.back() != visitingN);
+      return;
     }
   }
 
@@ -136,11 +138,11 @@ public:
   typedef scc_iterator<GraphT, GT> _Self;
 
   // Provide static "constructors"...
-  static inline _Self begin(const GraphT& G) { return _Self(GT::getEntryNode(G)); }
-  static inline _Self end  (const GraphT& G) { return _Self(); }
+  static inline _Self begin(const GraphT &G){return _Self(GT::getEntryNode(G));}
+  static inline _Self end  (const GraphT &) { return _Self(); }
 
-  // Direct loop termination test (I.fini() is more efficient than I == end())
-  inline bool fini() const {
+  // Direct loop termination test: I.isAtEnd() is more efficient than I == end()
+  inline bool isAtEnd() const {
     assert(!CurrentSCC.empty() || VisitStack.empty());
     return CurrentSCC.empty();
   }
@@ -181,28 +183,36 @@ public:
         return true;
     return false;
   }
+
+  /// ReplaceNode - This informs the scc_iterator that the specified Old node
+  /// has been deleted, and New is to be used in its place.
+  void ReplaceNode(NodeType *Old, NodeType *New) {
+    assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
+    nodeVisitNumbers[New] = nodeVisitNumbers[Old];
+    nodeVisitNumbers.erase(Old);
+  }
 };
 
 
 // Global constructor for the SCC iterator.
 template <class T>
-scc_iterator<T> scc_begin(const T& G) {
+scc_iterator<T> scc_begin(const T &G) {
   return scc_iterator<T>::begin(G);
 }
 
 template <class T>
-scc_iterator<T> scc_end(const T& G) {
+scc_iterator<T> scc_end(const T &G) {
   return scc_iterator<T>::end(G);
 }
 
 template <class T>
-scc_iterator<Inverse<T> > scc_begin(const Inverse<T>& G) {
-       return scc_iterator<Inverse<T> >::begin(G);
+scc_iterator<Inverse<T> > scc_begin(const Inverse<T> &G) {
+  return scc_iterator<Inverse<T> >::begin(G);
 }
 
 template <class T>
-scc_iterator<Inverse<T> > scc_end(const Inverse<T>& G) {
-       return scc_iterator<Inverse<T> >::end(G);
+scc_iterator<Inverse<T> > scc_end(const Inverse<T> &G) {
+  return scc_iterator<Inverse<T> >::end(G);
 }
 
 } // End llvm namespace