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 
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