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