121 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/SCCIterator.h"10#include "TestGraph.h"11#include "gtest/gtest.h"12#include <limits.h>13 14using namespace llvm;15 16namespace llvm {17 18TEST(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 only21 // create graphs for which every node has a self-edge.22#define NUM_NODES 423#define NUM_GRAPHS (NUM_NODES * (NUM_NODES - 1))24 using GT = Graph<NUM_NODES>;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 in63 // 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 every70 // other, this means that the set of nodes reachable from any node in the71 // SCC is the same as the set of nodes reachable from every node in the72 // SCC. Check that for every node N not in the SCC but reachable from the73 // 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, so86 // 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 is91 // 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 and99 // guaranteed by it: if a node in SCC S1 has an edge to a node in100 // SCC S2, then S1 is visited *after* S2. This means that the set101 // of nodes reachable from this SCC must be contained either in the102 // 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, so109 // 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 are115 // reachable from the initial node.116 EXPECT_EQ(NodesInSomeSCC, G.NodesReachableFrom(0));117 }118}119 120}121