Index: include/llvm/ADT/DepthFirstIterator.h =================================================================== --- include/llvm/ADT/DepthFirstIterator.h +++ 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: unittests/ADT/CMakeLists.txt =================================================================== --- unittests/ADT/CMakeLists.txt +++ unittests/ADT/CMakeLists.txt @@ -13,6 +13,7 @@ DeltaAlgorithmTest.cpp DenseMapTest.cpp DenseSetTest.cpp + DepthFirstIteratorTest.cpp FoldingSet.cpp FunctionRefTest.cpp HashingTest.cpp Index: unittests/ADT/DepthFirstIteratorTest.cpp =================================================================== --- /dev/null +++ unittests/ADT/DepthFirstIteratorTest.cpp @@ -0,0 +1,56 @@ +//=== 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 class CountedSet { + SmallPtrSet S; + +public: + using iterator = typename SmallPtrSet::iterator; + + int InsertVisited = 0; + + CountedSet() {} + + 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) {} + df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {} + CountedSet &Visited; +}; + +TEST(DepthFirstIteratorTest, ActuallyUpdateIterator) { + using StorageT = CountedSet::NodeType *>; + using DFIter = df_iterator, StorageT, true>; + + 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: unittests/ADT/SCCIteratorTest.cpp =================================================================== --- unittests/ADT/SCCIteratorTest.cpp +++ unittests/ADT/SCCIteratorTest.cpp @@ -8,7 +8,6 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/SCCIterator.h" -#include "llvm/ADT/GraphTraits.h" #include "gtest/gtest.h" #include Index: unittests/ADT/TestGraph.h =================================================================== --- unittests/ADT/TestGraph.h +++ unittests/ADT/TestGraph.h @@ -1,4 +1,4 @@ -//===----- llvm/unittest/ADT/SCCIteratorTest.cpp - SCCIterator tests ------===// +//===- llvm/unittest/ADT/TestGraph.h - Graph for testing ------------------===// // // The LLVM Compiler Infrastructure // @@ -6,13 +6,18 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// +// +// Common graph data structure for testing. +// +//===----------------------------------------------------------------------===// -#include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/GraphTraits.h" -#include "gtest/gtest.h" -#include +#include +#include +#include -using namespace llvm; +#ifndef LLVM_UNITTESTS_ADT_TEST_GRAPH_H +#define LLVM_UNITTESTS_ADT_TEST_GRAPH_H namespace llvm { @@ -237,110 +242,12 @@ } static inline ChildIteratorType child_begin(NodeRef Node) { return Graph::child_begin(Node); - } - static inline ChildIteratorType child_end(NodeRef Node) { - return Graph::child_end(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 - // create graphs for which every node has a self-edge. -#define NUM_NODES 4 -#define NUM_GRAPHS (NUM_NODES * (NUM_NODES - 1)) - typedef Graph GT; - - /// Enumerate all graphs using NUM_GRAPHS bits. - static_assert(NUM_GRAPHS < sizeof(unsigned) * CHAR_BIT, "Too many graphs!"); - for (unsigned GraphDescriptor = 0; GraphDescriptor < (1U << NUM_GRAPHS); - ++GraphDescriptor) { - GT G; - - // Add edges as specified by the descriptor. - unsigned DescriptorCopy = GraphDescriptor; - for (unsigned i = 0; i != NUM_NODES; ++i) - for (unsigned j = 0; j != NUM_NODES; ++j) { - // Always add a self-edge. - if (i == j) { - G.AddEdge(i, j); - continue; - } - if (DescriptorCopy & 1) - G.AddEdge(i, j); - DescriptorCopy >>= 1; - } - - // Test the SCC logic on this graph. - - /// NodesInSomeSCC - Those nodes which are in some SCC. - GT::NodeSubset NodesInSomeSCC; - - for (scc_iterator I = scc_begin(G), E = scc_end(G); I != E; ++I) { - const std::vector &SCC = *I; - - // Get the nodes in this SCC as a NodeSubset rather than a vector. - GT::NodeSubset NodesInThisSCC; - for (unsigned i = 0, e = SCC.size(); i != e; ++i) - NodesInThisSCC.AddNode(SCC[i]->first); - - // There should be at least one node in every SCC. - EXPECT_FALSE(NodesInThisSCC.isEmpty()); - - // Check that every node in the SCC is reachable from every other node in - // the SCC. - for (unsigned i = 0; i != NUM_NODES; ++i) - if (NodesInThisSCC.count(i)) - EXPECT_TRUE(NodesInThisSCC.isSubsetOf(G.NodesReachableFrom(i))); - - // OK, now that we now that every node in the SCC is reachable from every - // other, this means that the set of nodes reachable from any node in the - // SCC is the same as the set of nodes reachable from every node in the - // SCC. Check that for every node N not in the SCC but reachable from the - // SCC, no element of the SCC is reachable from N. - for (unsigned i = 0; i != NUM_NODES; ++i) - if (NodesInThisSCC.count(i)) { - GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i); - GT::NodeSubset ReachableButNotInSCC = - NodesReachableFromSCC.Meet(NodesInThisSCC.Complement()); - - for (unsigned j = 0; j != NUM_NODES; ++j) - if (ReachableButNotInSCC.count(j)) - EXPECT_TRUE(G.NodesReachableFrom(j).Meet(NodesInThisSCC).isEmpty()); - - // The result must be the same for all other nodes in this SCC, so - // there is no point in checking them. - break; - } - - // This is indeed a SCC: a maximal set of nodes for which each node is - // reachable from every other. - - // Check that we didn't already see this SCC. - EXPECT_TRUE(NodesInSomeSCC.Meet(NodesInThisSCC).isEmpty()); - - NodesInSomeSCC = NodesInSomeSCC.Join(NodesInThisSCC); - - // Check a property that is specific to the LLVM SCC iterator and - // guaranteed by it: if a node in SCC S1 has an edge to a node in - // SCC S2, then S1 is visited *after* S2. This means that the set - // of nodes reachable from this SCC must be contained either in the - // union of this SCC and all previously visited SCC's. - - for (unsigned i = 0; i != NUM_NODES; ++i) - if (NodesInThisSCC.count(i)) { - GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i); - EXPECT_TRUE(NodesReachableFromSCC.isSubsetOf(NodesInSomeSCC)); - // The result must be the same for all other nodes in this SCC, so - // there is no point in checking them. - break; - } - } - - // Finally, check that the nodes in some SCC are exactly those that are - // reachable from the initial node. - EXPECT_EQ(NodesInSomeSCC, G.NodesReachableFrom(0)); - } -} +} // End namespace llvm -} +#endif