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(FromIdx: i, ToIdx: j); |
39 | continue; |
40 | } |
41 | if (DescriptorCopy & 1) |
42 | G.AddEdge(FromIdx: i, ToIdx: 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(Idx: 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(Idx: 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(Idx: i)) { |
76 | GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(Idx: i); |
77 | GT::NodeSubset ReachableButNotInSCC = |
78 | NodesReachableFromSCC.Meet(other: NodesInThisSCC.Complement()); |
79 | |
80 | for (unsigned j = 0; j != NUM_NODES; ++j) |
81 | if (ReachableButNotInSCC.count(Idx: 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(other: 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(Idx: i)) { |
106 | GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(Idx: 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 | |