unittests/ADT/SCCIteratorTest.cpp

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