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 "llvm/ADT/GraphTraits.h"
  12 #include "gtest/gtest.h"
  13 #include <limits.h>
  14
  15 using namespace llvm;
  16
  17 namespace llvm {
  18
  19 /// Graph<N> - A graph with N nodes.  Note that N can be at most 8.
  20 template <unsigned N>
  21 class Graph {
  22 private:
  23   // Disable copying.
  24   Graph(const Graph&);
  25   Graph& operator=(const Graph&);
  26
  27   static void ValidateIndex(unsigned Idx) {
  28     assert(Idx < N && "Invalid node index!");
  29   }
  30 public:
  31
  32   /// NodeSubset - A subset of the graph's nodes.
  33   class NodeSubset {
  34     typedef unsigned char BitVector; // Where the limitation N <= 8 comes from.
  35     BitVector Elements;
  36     NodeSubset(BitVector e) : Elements(e) {}
  37   public:
  38     /// NodeSubset - Default constructor, creates an empty subset.
  39     NodeSubset() : Elements(0) {
  40       assert(N <= sizeof(BitVector)*CHAR_BIT && "Graph too big!");
  41     }
  42     /// NodeSubset - Copy constructor.
  43     NodeSubset(const NodeSubset &other) : Elements(other.Elements) {}
  44
  45     /// Comparison operators.
  46     bool operator==(const NodeSubset &other) const {
  47       return other.Elements == this->Elements;
  48     }
  49     bool operator!=(const NodeSubset &other) const {
  50       return !(*this == other);
  51     }
  52
  53     /// AddNode - Add the node with the given index to the subset.
  54     void AddNode(unsigned Idx) {
  55       ValidateIndex(Idx);
  56       Elements |= 1U << Idx;
  57     }
  58
  59     /// DeleteNode - Remove the node with the given index from the subset.
  60     void DeleteNode(unsigned Idx) {
  61       ValidateIndex(Idx);
  62       Elements &= ~(1U << Idx);
  63     }
  64
  65     /// count - Return true if the node with the given index is in the subset.
  66     bool count(unsigned Idx) {
  67       ValidateIndex(Idx);
  68       return (Elements & (1U << Idx)) != 0;
  69     }
  70
  71     /// isEmpty - Return true if this is the empty set.
  72     bool isEmpty() const {
  73       return Elements == 0;
  74     }
  75
  76     /// isSubsetOf - Return true if this set is a subset of the given one.
  77     bool isSubsetOf(const NodeSubset &other) const {
  78       return (this->Elements | other.Elements) == other.Elements;
  79     }
  80
  81     /// Complement - Return the complement of this subset.
  82     NodeSubset Complement() const {
  83       return ~(unsigned)this->Elements & ((1U << N) - 1);
  84     }
  85
  86     /// Join - Return the union of this subset and the given one.
  87     NodeSubset Join(const NodeSubset &other) const {
  88       return this->Elements | other.Elements;
  89     }
  90
  91     /// Meet - Return the intersection of this subset and the given one.
  92     NodeSubset Meet(const NodeSubset &other) const {
  93       return this->Elements & other.Elements;
  94     }
  95   };
  96
  97   /// NodeType - Node index and set of children of the node.
  98   typedef std::pair<unsigned, NodeSubset> NodeType;
  99
 100 private:
 101   /// Nodes - The list of nodes for this graph.
 102   NodeType Nodes[N];
 103 public:
 104
 105   /// Graph - Default constructor.  Creates an empty graph.
 106   Graph() {
 107     // Let each node know which node it is.  This allows us to find the start of
 108     // the Nodes array given a pointer to any element of it.
 109     for (unsigned i = 0; i != N; ++i)
 110       Nodes[i].first = i;
 111   }
 112
 113   /// AddEdge - Add an edge from the node with index FromIdx to the node with
 114   /// index ToIdx.
 115   void AddEdge(unsigned FromIdx, unsigned ToIdx) {
 116     ValidateIndex(FromIdx);
 117     Nodes[FromIdx].second.AddNode(ToIdx);
 118   }
 119
 120   /// DeleteEdge - Remove the edge (if any) from the node with index FromIdx to
 121   /// the node with index ToIdx.
 122   void DeleteEdge(unsigned FromIdx, unsigned ToIdx) {
 123     ValidateIndex(FromIdx);
 124     Nodes[FromIdx].second.DeleteNode(ToIdx);
 125   }
 126
 127   /// AccessNode - Get a pointer to the node with the given index.
 128   NodeType *AccessNode(unsigned Idx) const {
 129     ValidateIndex(Idx);
 130     // The constant cast is needed when working with GraphTraits, which insists
 131     // on taking a constant Graph.
 132     return const_cast<NodeType *>(&Nodes[Idx]);
 133   }
 134
 135   /// NodesReachableFrom - Return the set of all nodes reachable from the given
 136   /// node.
 137   NodeSubset NodesReachableFrom(unsigned Idx) const {
 138     // This algorithm doesn't scale, but that doesn't matter given the small
 139     // size of our graphs.
 140     NodeSubset Reachable;
 141
 142     // The initial node is reachable.
 143     Reachable.AddNode(Idx);
 144     do {
 145       NodeSubset Previous(Reachable);
 146
 147       // Add in all nodes which are children of a reachable node.
 148       for (unsigned i = 0; i != N; ++i)
 149         if (Previous.count(i))
 150           Reachable = Reachable.Join(Nodes[i].second);
 151
 152       // If nothing changed then we have found all reachable nodes.
 153       if (Reachable == Previous)
 154         return Reachable;
 155
 156       // Rinse and repeat.
 157     } while (1);
 158   }
 159
 160   /// ChildIterator - Visit all children of a node.
 161   class ChildIterator {
 162     friend class Graph;
 163
 164     /// FirstNode - Pointer to first node in the graph's Nodes array.
 165     NodeType *FirstNode;
 166     /// Children - Set of nodes which are children of this one and that haven't
 167     /// yet been visited.
 168     NodeSubset Children;
 169
 170     ChildIterator(); // Disable default constructor.
 171   protected:
 172     ChildIterator(NodeType *F, NodeSubset C) : FirstNode(F), Children(C) {}
 173
 174   public:
 175     /// ChildIterator - Copy constructor.
 176     ChildIterator(const ChildIterator& other) : FirstNode(other.FirstNode),
 177       Children(other.Children) {}
 178
 179     /// Comparison operators.
 180     bool operator==(const ChildIterator &other) const {
 181       return other.FirstNode == this->FirstNode &&
 182         other.Children == this->Children;
 183     }
 184     bool operator!=(const ChildIterator &other) const {
 185       return !(*this == other);
 186     }
 187
 188     /// Prefix increment operator.
 189     ChildIterator& operator++() {
 190       // Find the next unvisited child node.
 191       for (unsigned i = 0; i != N; ++i)
 192         if (Children.count(i)) {
 193           // Remove that child - it has been visited.  This is the increment!
 194           Children.DeleteNode(i);
 195           return *this;
 196         }
 197       assert(false && "Incrementing end iterator!");
 198       return *this; // Avoid compiler warnings.
 199     }
 200
 201     /// Postfix increment operator.
 202     ChildIterator operator++(int) {
 203       ChildIterator Result(*this);
 204       ++(*this);
 205       return Result;
 206     }
 207
 208     /// Dereference operator.
 209     NodeType *operator*() {
 210       // Find the next unvisited child node.
 211       for (unsigned i = 0; i != N; ++i)
 212         if (Children.count(i))
 213           // Return a pointer to it.
 214           return FirstNode + i;
 215       assert(false && "Dereferencing end iterator!");
 216       return 0; // Avoid compiler warning.
 217     }
 218   };
 219
 220   /// child_begin - Return an iterator pointing to the first child of the given
 221   /// node.
 222   static ChildIterator child_begin(NodeType *Parent) {
 223     return ChildIterator(Parent - Parent->first, Parent->second);
 224   }
 225
 226   /// child_end - Return the end iterator for children of the given node.
 227   static ChildIterator child_end(NodeType *Parent) {
 228     return ChildIterator(Parent - Parent->first, NodeSubset());
 229   }
 230 };
 231
 232 template <unsigned N>
 233 struct GraphTraits<Graph<N> > {
 234   typedef typename Graph<N>::NodeType NodeType;
 235   typedef typename Graph<N>::ChildIterator ChildIteratorType;
 236
 237  static inline NodeType *getEntryNode(const Graph<N> &G) { return G.AccessNode(0); }
 238  static inline ChildIteratorType child_begin(NodeType *Node) {
 239    return Graph<N>::child_begin(Node);
 240  }
 241  static inline ChildIteratorType child_end(NodeType *Node) {
 242    return Graph<N>::child_end(Node);
 243  }
 244 };
 245
 246 TEST(SCCIteratorTest, AllSmallGraphs) {
 247   // Test SCC computation against every graph with NUM_NODES nodes or less.
 248   // Since SCC considers every node to have an implicit self-edge, we only
 249   // create graphs for which every node has a self-edge.
 250 #define NUM_NODES 4
 251 #define NUM_GRAPHS (NUM_NODES * (NUM_NODES - 1))
 252   typedef Graph<NUM_NODES> GT;
 253
 254   /// Enumerate all graphs using NUM_GRAPHS bits.
 255   assert(NUM_GRAPHS < sizeof(unsigned) * CHAR_BIT && "Too many graphs!");
 256   for (unsigned GraphDescriptor = 0; GraphDescriptor < (1U << NUM_GRAPHS);
 257        ++GraphDescriptor) {
 258     GT G;
 259
 260     // Add edges as specified by the descriptor.
 261     unsigned DescriptorCopy = GraphDescriptor;
 262     for (unsigned i = 0; i != NUM_NODES; ++i)
 263       for (unsigned j = 0; j != NUM_NODES; ++j) {
 264         // Always add a self-edge.
 265         if (i == j) {
 266           G.AddEdge(i, j);
 267           continue;
 268         }
 269         if (DescriptorCopy & 1)
 270           G.AddEdge(i, j);
 271         DescriptorCopy >>= 1;
 272       }
 273
 274     // Test the SCC logic on this graph.
 275
 276     /// NodesInSomeSCC - Those nodes which are in some SCC.
 277     GT::NodeSubset NodesInSomeSCC;
 278
 279     for (scc_iterator<GT> I = scc_begin(G), E = scc_end(G); I != E; ++I) {
 280       const std::vector<GT::NodeType *> &SCC = *I;
 281
 282       // Get the nodes in this SCC as a NodeSubset rather than a vector.
 283       GT::NodeSubset NodesInThisSCC;
 284       for (unsigned i = 0, e = SCC.size(); i != e; ++i)
 285         NodesInThisSCC.AddNode(SCC[i]->first);
 286
 287       // There should be at least one node in every SCC.
 288       EXPECT_FALSE(NodesInThisSCC.isEmpty());
 289
 290       // Check that every node in the SCC is reachable from every other node in
 291       // the SCC.
 292       for (unsigned i = 0; i != NUM_NODES; ++i)
 293         if (NodesInThisSCC.count(i))
 294           EXPECT_TRUE(NodesInThisSCC.isSubsetOf(G.NodesReachableFrom(i)));
 295
 296       // OK, now that we now that every node in the SCC is reachable from every
 297       // other, this means that the set of nodes reachable from any node in the
 298       // SCC is the same as the set of nodes reachable from every node in the
 299       // SCC.  Check that for every node N not in the SCC but reachable from the
 300       // SCC, no element of the SCC is reachable from N.
 301       for (unsigned i = 0; i != NUM_NODES; ++i)
 302         if (NodesInThisSCC.count(i)) {
 303           GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i);
 304           GT::NodeSubset ReachableButNotInSCC =
 305             NodesReachableFromSCC.Meet(NodesInThisSCC.Complement());
 306
 307           for (unsigned j = 0; j != NUM_NODES; ++j)
 308             if (ReachableButNotInSCC.count(j))
 309               EXPECT_TRUE(G.NodesReachableFrom(j).Meet(NodesInThisSCC).isEmpty());
 310
 311           // The result must be the same for all other nodes in this SCC, so
 312           // there is no point in checking them.
 313           break;
 314         }
 315
 316       // This is indeed a SCC: a maximal set of nodes for which each node is
 317       // reachable from every other.
 318
 319       // Check that we didn't already see this SCC.
 320       EXPECT_TRUE(NodesInSomeSCC.Meet(NodesInThisSCC).isEmpty());
 321
 322       NodesInSomeSCC = NodesInSomeSCC.Join(NodesInThisSCC);
 323
 324       // Check a property that is specific to the LLVM SCC iterator and
 325       // guaranteed by it: if a node in SCC S1 has an edge to a node in
 326       // SCC S2, then S1 is visited *after* S2.  This means that the set
 327       // of nodes reachable from this SCC must be contained either in the
 328       // union of this SCC and all previously visited SCC's.
 329
 330       for (unsigned i = 0; i != NUM_NODES; ++i)
 331         if (NodesInThisSCC.count(i)) {
 332           GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i);
 333           EXPECT_TRUE(NodesReachableFromSCC.isSubsetOf(NodesInSomeSCC));
 334           // The result must be the same for all other nodes in this SCC, so
 335           // there is no point in checking them.
 336           break;
 337         }
 338     }
 339
 340     // Finally, check that the nodes in some SCC are exactly those that are
 341     // reachable from the initial node.
 342     EXPECT_EQ(NodesInSomeSCC, G.NodesReachableFrom(0));
 343   }
 344 }
 345
 346 }