Index: llvm/trunk/include/llvm/ADT/DepthFirstIterator.h =================================================================== --- llvm/trunk/include/llvm/ADT/DepthFirstIterator.h +++ llvm/trunk/include/llvm/ADT/DepthFirstIterator.h @@ -107,7 +107,11 @@ if (!Opt) Opt.emplace(GT::child_begin(Node)); - for (NodeRef Next : make_range(*Opt, GT::child_end(Node))) { + // Notice that we directly mutate *Opt here, so that + // VisitStack.back().second actually gets updated as the iterator + // increases. + while (*Opt != GT::child_end(Node)) { + NodeRef Next = *(*Opt)++; // Has our next sibling been visited? if (this->Visited.insert(Next).second) { // No, do it now. Index: llvm/trunk/unittests/ADT/CMakeLists.txt =================================================================== --- llvm/trunk/unittests/ADT/CMakeLists.txt +++ llvm/trunk/unittests/ADT/CMakeLists.txt @@ -13,6 +13,7 @@ DeltaAlgorithmTest.cpp DenseMapTest.cpp DenseSetTest.cpp + DepthFirstIteratorTest.cpp FoldingSet.cpp FunctionRefTest.cpp HashingTest.cpp Index: llvm/trunk/unittests/ADT/DepthFirstIteratorTest.cpp =================================================================== --- llvm/trunk/unittests/ADT/DepthFirstIteratorTest.cpp +++ llvm/trunk/unittests/ADT/DepthFirstIteratorTest.cpp @@ -0,0 +1,52 @@ +//=== llvm/unittest/ADT/DepthFirstIteratorTest.cpp - DFS iterator tests ---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "TestGraph.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace llvm { + +template struct CountedSet { + typedef typename SmallPtrSet::iterator iterator; + + SmallPtrSet S; + int InsertVisited = 0; + + std::pair insert(const T &Item) { + InsertVisited++; + return S.insert(Item); + } + + size_t count(const T &Item) const { return S.count(Item); } +}; + +template class df_iterator_storage, true> { +public: + df_iterator_storage(CountedSet &VSet) : Visited(VSet) {} + + CountedSet &Visited; +}; + +TEST(DepthFirstIteratorTest, ActuallyUpdateIterator) { + typedef CountedSet::NodeType *> StorageT; + typedef df_iterator, StorageT, true> DFIter; + + Graph<3> G; + G.AddEdge(0, 1); + G.AddEdge(0, 2); + StorageT S; + for (auto N : make_range(DFIter::begin(G, S), DFIter::end(G, S))) + (void)N; + + EXPECT_EQ(3, S.InsertVisited); +} +} Index: llvm/trunk/unittests/ADT/SCCIteratorTest.cpp =================================================================== --- llvm/trunk/unittests/ADT/SCCIteratorTest.cpp +++ llvm/trunk/unittests/ADT/SCCIteratorTest.cpp @@ -8,241 +8,14 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/SCCIterator.h" -#include "llvm/ADT/GraphTraits.h" #include "gtest/gtest.h" +#include "TestGraph.h" #include using namespace llvm; namespace llvm { -/// Graph - A graph with N nodes. Note that N can be at most 8. -template -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 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(&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 -struct GraphTraits > { - typedef typename Graph::NodeType *NodeRef; - typedef typename Graph::ChildIterator ChildIteratorType; - - static inline NodeRef getEntryNode(const Graph &G) { - return G.AccessNode(0); - } - static inline ChildIteratorType child_begin(NodeRef Node) { - return Graph::child_begin(Node); - } - static inline ChildIteratorType child_end(NodeRef Node) { - return Graph::child_end(Node); - } -}; - TEST(SCCIteratorTest, AllSmallGraphs) { // Test SCC computation against every graph with NUM_NODES nodes or less. // Since SCC considers every node to have an implicit self-edge, we only Index: llvm/trunk/unittests/ADT/TestGraph.h =================================================================== --- llvm/trunk/unittests/ADT/TestGraph.h +++ llvm/trunk/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 +#include +#include + +#ifndef LLVM_UNITTESTS_ADT_TEST_GRAPH_H +#define LLVM_UNITTESTS_ADT_TEST_GRAPH_H + +namespace llvm { + +/// Graph - A graph with N nodes. Note that N can be at most 8. +template +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 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(&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 +struct GraphTraits > { + typedef typename Graph::NodeType *NodeRef; + typedef typename Graph::ChildIterator ChildIteratorType; + + static inline NodeRef getEntryNode(const Graph &G) { + return G.AccessNode(0); + } + static inline ChildIteratorType child_begin(NodeRef Node) { + return Graph::child_begin(Node); + } + static inline ChildIteratorType child_end(NodeRef Node) { + return Graph::child_end(Node); + } +}; + +} // End namespace llvm + +#endif