1 //===----- llvm/unittest/ADT/SCCIteratorTest.cpp - SCCIterator tests ------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "llvm/ADT/SCCIterator.h"
11 #include "TestGraph.h"
12 #include "gtest/gtest.h"
13 #include <limits.h>
14
15 using namespace llvm;
16
17 namespace llvm {
18
TEST(SCCIteratorTest,AllSmallGraphs)19 TEST(SCCIteratorTest, AllSmallGraphs) {
20 // Test SCC computation against every graph with NUM_NODES nodes or less.
21 // Since SCC considers every node to have an implicit self-edge, we only
22 // create graphs for which every node has a self-edge.
23 #define NUM_NODES 4
24 #define NUM_GRAPHS (NUM_NODES * (NUM_NODES - 1))
25 typedef Graph<NUM_NODES> GT;
26
27 /// Enumerate all graphs using NUM_GRAPHS bits.
28 static_assert(NUM_GRAPHS < sizeof(unsigned) * CHAR_BIT, "Too many graphs!");
29 for (unsigned GraphDescriptor = 0; GraphDescriptor < (1U << NUM_GRAPHS);
30 ++GraphDescriptor) {
31 GT G;
32
33 // Add edges as specified by the descriptor.
34 unsigned DescriptorCopy = GraphDescriptor;
35 for (unsigned i = 0; i != NUM_NODES; ++i)
36 for (unsigned j = 0; j != NUM_NODES; ++j) {
37 // Always add a self-edge.
38 if (i == j) {
39 G.AddEdge(i, j);
40 continue;
41 }
42 if (DescriptorCopy & 1)
43 G.AddEdge(i, j);
44 DescriptorCopy >>= 1;
45 }
46
47 // Test the SCC logic on this graph.
48
49 /// NodesInSomeSCC - Those nodes which are in some SCC.
50 GT::NodeSubset NodesInSomeSCC;
51
52 for (scc_iterator<GT> I = scc_begin(G), E = scc_end(G); I != E; ++I) {
53 const std::vector<GT::NodeType *> &SCC = *I;
54
55 // Get the nodes in this SCC as a NodeSubset rather than a vector.
56 GT::NodeSubset NodesInThisSCC;
57 for (unsigned i = 0, e = SCC.size(); i != e; ++i)
58 NodesInThisSCC.AddNode(SCC[i]->first);
59
60 // There should be at least one node in every SCC.
61 EXPECT_FALSE(NodesInThisSCC.isEmpty());
62
63 // Check that every node in the SCC is reachable from every other node in
64 // the SCC.
65 for (unsigned i = 0; i != NUM_NODES; ++i)
66 if (NodesInThisSCC.count(i)) {
67 EXPECT_TRUE(NodesInThisSCC.isSubsetOf(G.NodesReachableFrom(i)));
68 }
69
70 // OK, now that we now that every node in the SCC is reachable from every
71 // other, this means that the set of nodes reachable from any node in the
72 // SCC is the same as the set of nodes reachable from every node in the
73 // SCC. Check that for every node N not in the SCC but reachable from the
74 // SCC, no element of the SCC is reachable from N.
75 for (unsigned i = 0; i != NUM_NODES; ++i)
76 if (NodesInThisSCC.count(i)) {
77 GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i);
78 GT::NodeSubset ReachableButNotInSCC =
79 NodesReachableFromSCC.Meet(NodesInThisSCC.Complement());
80
81 for (unsigned j = 0; j != NUM_NODES; ++j)
82 if (ReachableButNotInSCC.count(j)) {
83 EXPECT_TRUE(G.NodesReachableFrom(j).Meet(NodesInThisSCC).isEmpty());
84 }
85
86 // The result must be the same for all other nodes in this SCC, so
87 // there is no point in checking them.
88 break;
89 }
90
91 // This is indeed a SCC: a maximal set of nodes for which each node is
92 // reachable from every other.
93
94 // Check that we didn't already see this SCC.
95 EXPECT_TRUE(NodesInSomeSCC.Meet(NodesInThisSCC).isEmpty());
96
97 NodesInSomeSCC = NodesInSomeSCC.Join(NodesInThisSCC);
98
99 // Check a property that is specific to the LLVM SCC iterator and
100 // guaranteed by it: if a node in SCC S1 has an edge to a node in
101 // SCC S2, then S1 is visited *after* S2. This means that the set
102 // of nodes reachable from this SCC must be contained either in the
103 // union of this SCC and all previously visited SCC's.
104
105 for (unsigned i = 0; i != NUM_NODES; ++i)
106 if (NodesInThisSCC.count(i)) {
107 GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i);
108 EXPECT_TRUE(NodesReachableFromSCC.isSubsetOf(NodesInSomeSCC));
109 // The result must be the same for all other nodes in this SCC, so
110 // there is no point in checking them.
111 break;
112 }
113 }
114
115 // Finally, check that the nodes in some SCC are exactly those that are
116 // reachable from the initial node.
117 EXPECT_EQ(NodesInSomeSCC, G.NodesReachableFrom(0));
118 }
119 }
120
121 }
122