X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=unittests%2FADT%2FSCCIteratorTest.cpp;h=da8c04483f9cabddaf12720f20efcf43a9f6e0d3;hb=HEAD;hp=8146e28f08f6b4a250a0eea3331de558661f69ee;hpb=8537e8a9a506a2ca1b7795e8d907982ec2235973;p=oota-llvm.git

diff --git a/unittests/ADT/SCCIteratorTest.cpp b/unittests/ADT/SCCIteratorTest.cpp
index 8146e28f08f..da8c04483f9 100644
--- a/unittests/ADT/SCCIteratorTest.cpp
+++ b/unittests/ADT/SCCIteratorTest.cpp
@@ -7,10 +7,10 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include <limits.h>
-#include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/GraphTraits.h"
 #include "gtest/gtest.h"
+#include <limits.h>
 
 using namespace llvm;
 
@@ -33,14 +33,12 @@ public:
   class NodeSubset {
     typedef unsigned char BitVector; // Where the limitation N <= 8 comes from.
     BitVector Elements;
-    NodeSubset(BitVector e) : Elements(e) {};
+    NodeSubset(BitVector e) : Elements(e) {}
   public:
     /// NodeSubset - Default constructor, creates an empty subset.
     NodeSubset() : Elements(0) {
       assert(N <= sizeof(BitVector)*CHAR_BIT && "Graph too big!");
     }
-    /// NodeSubset - Copy constructor.
-    NodeSubset(const NodeSubset &other) : Elements(other.Elements) {}
 
     /// Comparison operators.
     bool operator==(const NodeSubset &other) const {
@@ -213,7 +211,7 @@ public:
           // Return a pointer to it.
           return FirstNode + i;
       assert(false && "Dereferencing end iterator!");
-      return 0; // Avoid compiler warning.
+      return nullptr; // Avoid compiler warning.
     }
   };
 
@@ -249,18 +247,16 @@ TEST(SCCIteratorTest, AllSmallGraphs) {
   // create graphs for which every node has a self-edge.
 #define NUM_NODES 4
 #define NUM_GRAPHS (NUM_NODES * (NUM_NODES - 1))
+  typedef Graph<NUM_NODES> GT;
 
-  /// GraphDescriptor - Enumerate all graphs using NUM_GRAPHS bits.
-  uint16_t GraphDescriptor = 0;
-  assert(NUM_GRAPHS <= sizeof(uint16_t) * CHAR_BIT && "Too many graphs!");
-
-  do {
-    typedef Graph<NUM_NODES> GT;
-
+  /// Enumerate all graphs using NUM_GRAPHS bits.
+  static_assert(NUM_GRAPHS < sizeof(unsigned) * CHAR_BIT, "Too many graphs!");
+  for (unsigned GraphDescriptor = 0; GraphDescriptor < (1U << NUM_GRAPHS);
+       ++GraphDescriptor) {
     GT G;
 
     // Add edges as specified by the descriptor.
-    uint16_t DescriptorCopy = GraphDescriptor;
+    unsigned DescriptorCopy = GraphDescriptor;
     for (unsigned i = 0; i != NUM_NODES; ++i)
       for (unsigned j = 0; j != NUM_NODES; ++j) {
         // Always add a self-edge.
@@ -279,7 +275,7 @@ TEST(SCCIteratorTest, AllSmallGraphs) {
     GT::NodeSubset NodesInSomeSCC;
 
     for (scc_iterator<GT> I = scc_begin(G), E = scc_end(G); I != E; ++I) {
-      std::vector<GT::NodeType*> &SCC = *I;
+      const std::vector<GT::NodeType *> &SCC = *I;
 
       // Get the nodes in this SCC as a NodeSubset rather than a vector.
       GT::NodeSubset NodesInThisSCC;
@@ -322,14 +318,27 @@ TEST(SCCIteratorTest, AllSmallGraphs) {
       EXPECT_TRUE(NodesInSomeSCC.Meet(NodesInThisSCC).isEmpty());
 
       NodesInSomeSCC = NodesInSomeSCC.Join(NodesInThisSCC);
+
+      // Check a property that is specific to the LLVM SCC iterator and
+      // guaranteed by it: if a node in SCC S1 has an edge to a node in
+      // SCC S2, then S1 is visited *after* S2.  This means that the set
+      // of nodes reachable from this SCC must be contained either in the
+      // union of this SCC and all previously visited SCC's.
+
+      for (unsigned i = 0; i != NUM_NODES; ++i)
+        if (NodesInThisSCC.count(i)) {
+          GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i);
+          EXPECT_TRUE(NodesReachableFromSCC.isSubsetOf(NodesInSomeSCC));
+          // The result must be the same for all other nodes in this SCC, so
+          // there is no point in checking them.
+          break;
+        }
     }
 
     // Finally, check that the nodes in some SCC are exactly those that are
     // reachable from the initial node.
     EXPECT_EQ(NodesInSomeSCC, G.NodesReachableFrom(0));
-
-    ++GraphDescriptor;
-  } while (GraphDescriptor && (unsigned)GraphDescriptor < (1U << NUM_GRAPHS));
+  }
 }
 
 }