[ADT] Actually mutate the iterator VisitStack.back().second, not its copy.

Summary: Before the change, *Opt never actually gets updated by the end
of toNext(), so for every next time the loop has to start over from
child_begin(). This bug doesn't affect the correctness, since Visited prevents
it from re-entering the same node again; but it's slow.

Reviewers: dberris, dblaikie, dannyb

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D23649

llvm-svn: 279482

1 files changed, 253 insertions, 0 deletions

diff --git a/llvm/unittests/ADT/TestGraph.h b/llvm/unittests/ADT/TestGraph.h
new file mode 100644
index 00000000000..91d7333d72f
--- /dev/null
+++ b/llvm/unittests/ADT/TestGraph.h
@@ -0,0 +1,253 @@
+//===- llvm/unittest/ADT/TestGraph.h - Graph for testing ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Common graph data structure for testing.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/GraphTraits.h"
+#include <cassert>
+#include <climits>
+#include <utility>
+
+#ifndef LLVM_UNITTESTS_ADT_TEST_GRAPH_H
+#define LLVM_UNITTESTS_ADT_TEST_GRAPH_H
+
+namespace llvm {
+
+/// Graph<N> - A graph with N nodes.  Note that N can be at most 8.
+template <unsigned N>
+class Graph {
+private:
+  // Disable copying.
+  Graph(const Graph&);
+  Graph& operator=(const Graph&);
+
+  static void ValidateIndex(unsigned Idx) {
+    assert(Idx < N && "Invalid node index!");
+  }
+public:
+
+  /// NodeSubset - A subset of the graph's nodes.
+  class NodeSubset {
+    typedef unsigned char BitVector; // Where the limitation N <= 8 comes from.
+    BitVector Elements;
+    NodeSubset(BitVector e) : Elements(e) {}
+  public:
+    /// NodeSubset - Default constructor, creates an empty subset.
+    NodeSubset() : Elements(0) {
+      assert(N <= sizeof(BitVector)*CHAR_BIT && "Graph too big!");
+    }
+
+    /// Comparison operators.
+    bool operator==(const NodeSubset &other) const {
+      return other.Elements == this->Elements;
+    }
+    bool operator!=(const NodeSubset &other) const {
+      return !(*this == other);
+    }
+
+    /// AddNode - Add the node with the given index to the subset.
+    void AddNode(unsigned Idx) {
+      ValidateIndex(Idx);
+      Elements |= 1U << Idx;
+    }
+
+    /// DeleteNode - Remove the node with the given index from the subset.
+    void DeleteNode(unsigned Idx) {
+      ValidateIndex(Idx);
+      Elements &= ~(1U << Idx);
+    }
+
+    /// count - Return true if the node with the given index is in the subset.
+    bool count(unsigned Idx) {
+      ValidateIndex(Idx);
+      return (Elements & (1U << Idx)) != 0;
+    }
+
+    /// isEmpty - Return true if this is the empty set.
+    bool isEmpty() const {
+      return Elements == 0;
+    }
+
+    /// isSubsetOf - Return true if this set is a subset of the given one.
+    bool isSubsetOf(const NodeSubset &other) const {
+      return (this->Elements | other.Elements) == other.Elements;
+    }
+
+    /// Complement - Return the complement of this subset.
+    NodeSubset Complement() const {
+      return ~(unsigned)this->Elements & ((1U << N) - 1);
+    }
+
+    /// Join - Return the union of this subset and the given one.
+    NodeSubset Join(const NodeSubset &other) const {
+      return this->Elements | other.Elements;
+    }
+
+    /// Meet - Return the intersection of this subset and the given one.
+    NodeSubset Meet(const NodeSubset &other) const {
+      return this->Elements & other.Elements;
+    }
+  };
+
+  /// NodeType - Node index and set of children of the node.
+  typedef std::pair<unsigned, NodeSubset> NodeType;
+
+private:
+  /// Nodes - The list of nodes for this graph.
+  NodeType Nodes[N];
+public:
+
+  /// Graph - Default constructor.  Creates an empty graph.
+  Graph() {
+    // Let each node know which node it is.  This allows us to find the start of
+    // the Nodes array given a pointer to any element of it.
+    for (unsigned i = 0; i != N; ++i)
+      Nodes[i].first = i;
+  }
+
+  /// AddEdge - Add an edge from the node with index FromIdx to the node with
+  /// index ToIdx.
+  void AddEdge(unsigned FromIdx, unsigned ToIdx) {
+    ValidateIndex(FromIdx);
+    Nodes[FromIdx].second.AddNode(ToIdx);
+  }
+
+  /// DeleteEdge - Remove the edge (if any) from the node with index FromIdx to
+  /// the node with index ToIdx.
+  void DeleteEdge(unsigned FromIdx, unsigned ToIdx) {
+    ValidateIndex(FromIdx);
+    Nodes[FromIdx].second.DeleteNode(ToIdx);
+  }
+
+  /// AccessNode - Get a pointer to the node with the given index.
+  NodeType *AccessNode(unsigned Idx) const {
+    ValidateIndex(Idx);
+    // The constant cast is needed when working with GraphTraits, which insists
+    // on taking a constant Graph.
+    return const_cast<NodeType *>(&Nodes[Idx]);
+  }
+
+  /// NodesReachableFrom - Return the set of all nodes reachable from the given
+  /// node.
+  NodeSubset NodesReachableFrom(unsigned Idx) const {
+    // This algorithm doesn't scale, but that doesn't matter given the small
+    // size of our graphs.
+    NodeSubset Reachable;
+
+    // The initial node is reachable.
+    Reachable.AddNode(Idx);
+    do {
+      NodeSubset Previous(Reachable);
+
+      // Add in all nodes which are children of a reachable node.
+      for (unsigned i = 0; i != N; ++i)
+        if (Previous.count(i))
+          Reachable = Reachable.Join(Nodes[i].second);
+
+      // If nothing changed then we have found all reachable nodes.
+      if (Reachable == Previous)
+        return Reachable;
+
+      // Rinse and repeat.
+    } while (1);
+  }
+
+  /// ChildIterator - Visit all children of a node.
+  class ChildIterator {
+    friend class Graph;
+
+    /// FirstNode - Pointer to first node in the graph's Nodes array.
+    NodeType *FirstNode;
+    /// Children - Set of nodes which are children of this one and that haven't
+    /// yet been visited.
+    NodeSubset Children;
+
+    ChildIterator(); // Disable default constructor.
+  protected:
+    ChildIterator(NodeType *F, NodeSubset C) : FirstNode(F), Children(C) {}
+
+  public:
+    /// ChildIterator - Copy constructor.
+    ChildIterator(const ChildIterator& other) : FirstNode(other.FirstNode),
+      Children(other.Children) {}
+
+    /// Comparison operators.
+    bool operator==(const ChildIterator &other) const {
+      return other.FirstNode == this->FirstNode &&
+        other.Children == this->Children;
+    }
+    bool operator!=(const ChildIterator &other) const {
+      return !(*this == other);
+    }
+
+    /// Prefix increment operator.
+    ChildIterator& operator++() {
+      // Find the next unvisited child node.
+      for (unsigned i = 0; i != N; ++i)
+        if (Children.count(i)) {
+          // Remove that child - it has been visited.  This is the increment!
+          Children.DeleteNode(i);
+          return *this;
+        }
+      assert(false && "Incrementing end iterator!");
+      return *this; // Avoid compiler warnings.
+    }
+
+    /// Postfix increment operator.
+    ChildIterator operator++(int) {
+      ChildIterator Result(*this);
+      ++(*this);
+      return Result;
+    }
+
+    /// Dereference operator.
+    NodeType *operator*() {
+      // Find the next unvisited child node.
+      for (unsigned i = 0; i != N; ++i)
+        if (Children.count(i))
+          // Return a pointer to it.
+          return FirstNode + i;
+      assert(false && "Dereferencing end iterator!");
+      return nullptr; // Avoid compiler warning.
+    }
+  };
+
+  /// child_begin - Return an iterator pointing to the first child of the given
+  /// node.
+  static ChildIterator child_begin(NodeType *Parent) {
+    return ChildIterator(Parent - Parent->first, Parent->second);
+  }
+
+  /// child_end - Return the end iterator for children of the given node.
+  static ChildIterator child_end(NodeType *Parent) {
+    return ChildIterator(Parent - Parent->first, NodeSubset());
+  }
+};
+
+template <unsigned N>
+struct GraphTraits<Graph<N> > {
+  typedef typename Graph<N>::NodeType *NodeRef;
+  typedef typename Graph<N>::ChildIterator ChildIteratorType;
+
+  static inline NodeRef getEntryNode(const Graph<N> &G) {
+    return G.AccessNode(0);
+  }
+  static inline ChildIteratorType child_begin(NodeRef Node) {
+    return Graph<N>::child_begin(Node);
+  }
+  static inline ChildIteratorType child_end(NodeRef Node) {
+    return Graph<N>::child_end(Node);
+  }
+};
+
+} // End namespace llvm
+
+#endif