unittests/ADT/SCCIteratorTest.cpp - external/github.com/llvm-mirror/llvm - Git at Google

 //===----- llvm/unittest/ADT/SCCIteratorTest.cpp - SCCIterator tests ------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//

 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "gtest/gtest.h"
 #include <limits.h>

 using namespace llvm;

 namespace llvm {

 /// Graph<N> - A graph with N nodes.  Note that N can be at most 8.
 template <unsigned N>
 class Graph {
 private:
   // Disable copying.
   Graph(const Graph&);
   Graph& operator=(const Graph&);

   static void ValidateIndex(unsigned Idx) {
     assert(Idx < N && "Invalid node index!");
   }
 public:

   /// NodeSubset - A subset of the graph's nodes.
   class NodeSubset {
     typedef unsigned char BitVector; // Where the limitation N <= 8 comes from.
     BitVector Elements;
     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 {
       return other.Elements == this->Elements;
     }
     bool operator!=(const NodeSubset &other) const {
       return !(*this == other);
     }

     /// AddNode - Add the node with the given index to the subset.
     void AddNode(unsigned Idx) {
       ValidateIndex(Idx);
       Elements |= 1U << Idx;
     }

     /// DeleteNode - Remove the node with the given index from the subset.
     void DeleteNode(unsigned Idx) {
       ValidateIndex(Idx);
       Elements &= ~(1U << Idx);
     }

     /// count - Return true if the node with the given index is in the subset.
     bool count(unsigned Idx) {
       ValidateIndex(Idx);
       return (Elements & (1U << Idx)) != 0;
     }

     /// isEmpty - Return true if this is the empty set.
     bool isEmpty() const {
       return Elements == 0;
     }

     /// isSubsetOf - Return true if this set is a subset of the given one.
     bool isSubsetOf(const NodeSubset &other) const {
       return (this->Elements | other.Elements) == other.Elements;
     }

     /// Complement - Return the complement of this subset.
     NodeSubset Complement() const {
       return ~(unsigned)this->Elements & ((1U << N) - 1);
     }

     /// Join - Return the union of this subset and the given one.
     NodeSubset Join(const NodeSubset &other) const {
       return this->Elements | other.Elements;
     }

     /// Meet - Return the intersection of this subset and the given one.
     NodeSubset Meet(const NodeSubset &other) const {
       return this->Elements & other.Elements;
     }
   };

   /// NodeType - Node index and set of children of the node.
   typedef std::pair<unsigned, NodeSubset> NodeType;

 private:
   /// Nodes - The list of nodes for this graph.
   NodeType Nodes[N];
 public:

   /// Graph - Default constructor.  Creates an empty graph.
   Graph() {
     // Let each node know which node it is.  This allows us to find the start of
     // the Nodes array given a pointer to any element of it.
     for (unsigned i = 0; i != N; ++i)
       Nodes[i].first = i;
   }

   /// AddEdge - Add an edge from the node with index FromIdx to the node with
   /// index ToIdx.
   void AddEdge(unsigned FromIdx, unsigned ToIdx) {
     ValidateIndex(FromIdx);
     Nodes[FromIdx].second.AddNode(ToIdx);
   }

   /// DeleteEdge - Remove the edge (if any) from the node with index FromIdx to
   /// the node with index ToIdx.
   void DeleteEdge(unsigned FromIdx, unsigned ToIdx) {
     ValidateIndex(FromIdx);
     Nodes[FromIdx].second.DeleteNode(ToIdx);
   }

   /// AccessNode - Get a pointer to the node with the given index.
   NodeType *AccessNode(unsigned Idx) const {
     ValidateIndex(Idx);
     // The constant cast is needed when working with GraphTraits, which insists
     // on taking a constant Graph.
     return const_cast<NodeType *>(&Nodes[Idx]);
   }

   /// NodesReachableFrom - Return the set of all nodes reachable from the given
   /// node.
   NodeSubset NodesReachableFrom(unsigned Idx) const {
     // This algorithm doesn't scale, but that doesn't matter given the small
     // size of our graphs.
     NodeSubset Reachable;

     // The initial node is reachable.
     Reachable.AddNode(Idx);
     do {
       NodeSubset Previous(Reachable);

       // Add in all nodes which are children of a reachable node.
       for (unsigned i = 0; i != N; ++i)
         if (Previous.count(i))
           Reachable = Reachable.Join(Nodes[i].second);

       // If nothing changed then we have found all reachable nodes.
       if (Reachable == Previous)
         return Reachable;

       // Rinse and repeat.
     } while (1);
   }

   /// ChildIterator - Visit all children of a node.
   class ChildIterator {
     friend class Graph;

     /// FirstNode - Pointer to first node in the graph's Nodes array.
     NodeType *FirstNode;
     /// Children - Set of nodes which are children of this one and that haven't
     /// yet been visited.
     NodeSubset Children;

     ChildIterator(); // Disable default constructor.
   protected:
     ChildIterator(NodeType *F, NodeSubset C) : FirstNode(F), Children(C) {}

   public:
     /// ChildIterator - Copy constructor.
     ChildIterator(const ChildIterator& other) : FirstNode(other.FirstNode),
       Children(other.Children) {}

     /// Comparison operators.
     bool operator==(const ChildIterator &other) const {
       return other.FirstNode == this->FirstNode &&
         other.Children == this->Children;
     }
     bool operator!=(const ChildIterator &other) const {
       return !(*this == other);
     }

     /// Prefix increment operator.
     ChildIterator& operator++() {
       // Find the next unvisited child node.
       for (unsigned i = 0; i != N; ++i)
         if (Children.count(i)) {
           // Remove that child - it has been visited.  This is the increment!
           Children.DeleteNode(i);
           return *this;
         }
       assert(false && "Incrementing end iterator!");
       return *this; // Avoid compiler warnings.
     }

     /// Postfix increment operator.
     ChildIterator operator++(int) {
       ChildIterator Result(*this);
       ++(*this);
       return Result;
     }

     /// Dereference operator.
     NodeType *operator*() {
       // Find the next unvisited child node.
       for (unsigned i = 0; i != N; ++i)
         if (Children.count(i))
           // Return a pointer to it.
           return FirstNode + i;
       assert(false && "Dereferencing end iterator!");
       return nullptr; // Avoid compiler warning.
     }
   };

   /// child_begin - Return an iterator pointing to the first child of the given
   /// node.
   static ChildIterator child_begin(NodeType *Parent) {
     return ChildIterator(Parent - Parent->first, Parent->second);
   }

   /// child_end - Return the end iterator for children of the given node.
   static ChildIterator child_end(NodeType *Parent) {
     return ChildIterator(Parent - Parent->first, NodeSubset());
   }
 };

 template <unsigned N>
 struct GraphTraits<Graph<N> > {
   typedef typename Graph<N>::NodeType NodeType;
   typedef typename Graph<N>::ChildIterator ChildIteratorType;

  static inline NodeType *getEntryNode(const Graph<N> &G) { return G.AccessNode(0); }
  static inline ChildIteratorType child_begin(NodeType *Node) {
    return Graph<N>::child_begin(Node);
  }
  static inline ChildIteratorType child_end(NodeType *Node) {
    return Graph<N>::child_end(Node);
  }
 };

 TEST(SCCIteratorTest, AllSmallGraphs) {
   // Test SCC computation against every graph with NUM_NODES nodes or less.
   // Since SCC considers every node to have an implicit self-edge, we only
   // 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;

   /// Enumerate all graphs using NUM_GRAPHS bits.
   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.
     unsigned DescriptorCopy = GraphDescriptor;
     for (unsigned i = 0; i != NUM_NODES; ++i)
       for (unsigned j = 0; j != NUM_NODES; ++j) {
         // Always add a self-edge.
         if (i == j) {
           G.AddEdge(i, j);
           continue;
         }
         if (DescriptorCopy & 1)
           G.AddEdge(i, j);
         DescriptorCopy >>= 1;
       }

     // Test the SCC logic on this graph.

     /// NodesInSomeSCC - Those nodes which are in some SCC.
     GT::NodeSubset NodesInSomeSCC;

     for (scc_iterator<GT> I = scc_begin(G), E = scc_end(G); I != E; ++I) {
       const std::vector<GT::NodeType *> &SCC = *I;

       // Get the nodes in this SCC as a NodeSubset rather than a vector.
       GT::NodeSubset NodesInThisSCC;
       for (unsigned i = 0, e = SCC.size(); i != e; ++i)
         NodesInThisSCC.AddNode(SCC[i]->first);

       // There should be at least one node in every SCC.
       EXPECT_FALSE(NodesInThisSCC.isEmpty());

       // Check that every node in the SCC is reachable from every other node in
       // the SCC.
       for (unsigned i = 0; i != NUM_NODES; ++i)
         if (NodesInThisSCC.count(i))
           EXPECT_TRUE(NodesInThisSCC.isSubsetOf(G.NodesReachableFrom(i)));

       // OK, now that we now that every node in the SCC is reachable from every
       // other, this means that the set of nodes reachable from any node in the
       // SCC is the same as the set of nodes reachable from every node in the
       // SCC.  Check that for every node N not in the SCC but reachable from the
       // SCC, no element of the SCC is reachable from N.
       for (unsigned i = 0; i != NUM_NODES; ++i)
         if (NodesInThisSCC.count(i)) {
           GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i);
           GT::NodeSubset ReachableButNotInSCC =
             NodesReachableFromSCC.Meet(NodesInThisSCC.Complement());

           for (unsigned j = 0; j != NUM_NODES; ++j)
             if (ReachableButNotInSCC.count(j))
               EXPECT_TRUE(G.NodesReachableFrom(j).Meet(NodesInThisSCC).isEmpty());

           // The result must be the same for all other nodes in this SCC, so
           // there is no point in checking them.
           break;
         }

       // This is indeed a SCC: a maximal set of nodes for which each node is
       // reachable from every other.

       // Check that we didn't already see this SCC.
       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));
   }
 }

 }
	//===----- llvm/unittest/ADT/SCCIteratorTest.cpp - SCCIterator tests ------===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/ADT/SCCIterator.h"
	#include "llvm/ADT/GraphTraits.h"
	#include "gtest/gtest.h"
	#include <limits.h>

	using namespace llvm;

	namespace llvm {

	/// Graph<N> - A graph with N nodes. Note that N can be at most 8.
	template <unsigned N>
	class Graph {
	private:
	// Disable copying.
	Graph(const Graph&);
	Graph& operator=(const Graph&);

	static void ValidateIndex(unsigned Idx) {
	assert(Idx < N && "Invalid node index!");
	}
	public:

	/// NodeSubset - A subset of the graph's nodes.
	class NodeSubset {
	typedef unsigned char BitVector; // Where the limitation N <= 8 comes from.
	BitVector Elements;
	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 {
	return other.Elements == this->Elements;
	}
	bool operator!=(const NodeSubset &other) const {
	return !(*this == other);
	}

	/// AddNode - Add the node with the given index to the subset.
	void AddNode(unsigned Idx) {
	ValidateIndex(Idx);
	Elements \|= 1U << Idx;
	}

	/// DeleteNode - Remove the node with the given index from the subset.
	void DeleteNode(unsigned Idx) {
	ValidateIndex(Idx);
	Elements &= ~(1U << Idx);
	}

	/// count - Return true if the node with the given index is in the subset.
	bool count(unsigned Idx) {
	ValidateIndex(Idx);
	return (Elements & (1U << Idx)) != 0;
	}

	/// isEmpty - Return true if this is the empty set.
	bool isEmpty() const {
	return Elements == 0;
	}

	/// isSubsetOf - Return true if this set is a subset of the given one.
	bool isSubsetOf(const NodeSubset &other) const {
	return (this->Elements \| other.Elements) == other.Elements;
	}

	/// Complement - Return the complement of this subset.
	NodeSubset Complement() const {
	return ~(unsigned)this->Elements & ((1U << N) - 1);
	}

	/// Join - Return the union of this subset and the given one.
	NodeSubset Join(const NodeSubset &other) const {
	return this->Elements \| other.Elements;
	}

	/// Meet - Return the intersection of this subset and the given one.
	NodeSubset Meet(const NodeSubset &other) const {
	return this->Elements & other.Elements;
	}
	};

	/// NodeType - Node index and set of children of the node.
	typedef std::pair<unsigned, NodeSubset> NodeType;

	private:
	/// Nodes - The list of nodes for this graph.
	NodeType Nodes[N];
	public:

	/// Graph - Default constructor. Creates an empty graph.
	Graph() {
	// Let each node know which node it is. This allows us to find the start of
	// the Nodes array given a pointer to any element of it.
	for (unsigned i = 0; i != N; ++i)
	Nodes[i].first = i;
	}

	/// AddEdge - Add an edge from the node with index FromIdx to the node with
	/// index ToIdx.
	void AddEdge(unsigned FromIdx, unsigned ToIdx) {
	ValidateIndex(FromIdx);
	Nodes[FromIdx].second.AddNode(ToIdx);
	}

	/// DeleteEdge - Remove the edge (if any) from the node with index FromIdx to
	/// the node with index ToIdx.
	void DeleteEdge(unsigned FromIdx, unsigned ToIdx) {
	ValidateIndex(FromIdx);
	Nodes[FromIdx].second.DeleteNode(ToIdx);
	}

	/// AccessNode - Get a pointer to the node with the given index.
	NodeType *AccessNode(unsigned Idx) const {
	ValidateIndex(Idx);
	// The constant cast is needed when working with GraphTraits, which insists
	// on taking a constant Graph.
	return const_cast<NodeType *>(&Nodes[Idx]);
	}

	/// NodesReachableFrom - Return the set of all nodes reachable from the given
	/// node.
	NodeSubset NodesReachableFrom(unsigned Idx) const {
	// This algorithm doesn't scale, but that doesn't matter given the small
	// size of our graphs.
	NodeSubset Reachable;

	// The initial node is reachable.
	Reachable.AddNode(Idx);
	do {
	NodeSubset Previous(Reachable);

	// Add in all nodes which are children of a reachable node.
	for (unsigned i = 0; i != N; ++i)
	if (Previous.count(i))
	Reachable = Reachable.Join(Nodes[i].second);

	// If nothing changed then we have found all reachable nodes.
	if (Reachable == Previous)
	return Reachable;

	// Rinse and repeat.
	} while (1);
	}

	/// ChildIterator - Visit all children of a node.
	class ChildIterator {
	friend class Graph;

	/// FirstNode - Pointer to first node in the graph's Nodes array.
	NodeType *FirstNode;
	/// Children - Set of nodes which are children of this one and that haven't
	/// yet been visited.
	NodeSubset Children;

	ChildIterator(); // Disable default constructor.
	protected:
	ChildIterator(NodeType *F, NodeSubset C) : FirstNode(F), Children(C) {}

	public:
	/// ChildIterator - Copy constructor.
	ChildIterator(const ChildIterator& other) : FirstNode(other.FirstNode),
	Children(other.Children) {}

	/// Comparison operators.
	bool operator==(const ChildIterator &other) const {
	return other.FirstNode == this->FirstNode &&
	other.Children == this->Children;
	}
	bool operator!=(const ChildIterator &other) const {
	return !(*this == other);
	}

	/// Prefix increment operator.
	ChildIterator& operator++() {
	// Find the next unvisited child node.
	for (unsigned i = 0; i != N; ++i)
	if (Children.count(i)) {
	// Remove that child - it has been visited. This is the increment!
	Children.DeleteNode(i);
	return *this;
	}
	assert(false && "Incrementing end iterator!");
	return *this; // Avoid compiler warnings.
	}

	/// Postfix increment operator.
	ChildIterator operator++(int) {
	ChildIterator Result(*this);
	++(*this);
	return Result;
	}

	/// Dereference operator.
	NodeType operator() {
	// Find the next unvisited child node.
	for (unsigned i = 0; i != N; ++i)
	if (Children.count(i))
	// Return a pointer to it.
	return FirstNode + i;
	assert(false && "Dereferencing end iterator!");
	return nullptr; // Avoid compiler warning.
	}
	};

	/// child_begin - Return an iterator pointing to the first child of the given
	/// node.
	static ChildIterator child_begin(NodeType *Parent) {
	return ChildIterator(Parent - Parent->first, Parent->second);
	}

	/// child_end - Return the end iterator for children of the given node.
	static ChildIterator child_end(NodeType *Parent) {
	return ChildIterator(Parent - Parent->first, NodeSubset());
	}
	};

	template <unsigned N>
	struct GraphTraits<Graph<N> > {
	typedef typename Graph<N>::NodeType NodeType;
	typedef typename Graph<N>::ChildIterator ChildIteratorType;

	static inline NodeType *getEntryNode(const Graph<N> &G) { return G.AccessNode(0); }
	static inline ChildIteratorType child_begin(NodeType *Node) {
	return Graph<N>::child_begin(Node);
	}
	static inline ChildIteratorType child_end(NodeType *Node) {
	return Graph<N>::child_end(Node);
	}
	};

	TEST(SCCIteratorTest, AllSmallGraphs) {
	// Test SCC computation against every graph with NUM_NODES nodes or less.
	// Since SCC considers every node to have an implicit self-edge, we only
	// 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;

	/// Enumerate all graphs using NUM_GRAPHS bits.
	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.
	unsigned DescriptorCopy = GraphDescriptor;
	for (unsigned i = 0; i != NUM_NODES; ++i)
	for (unsigned j = 0; j != NUM_NODES; ++j) {
	// Always add a self-edge.
	if (i == j) {
	G.AddEdge(i, j);
	continue;
	}
	if (DescriptorCopy & 1)
	G.AddEdge(i, j);
	DescriptorCopy >>= 1;
	}

	// Test the SCC logic on this graph.

	/// NodesInSomeSCC - Those nodes which are in some SCC.
	GT::NodeSubset NodesInSomeSCC;

	for (scc_iterator<GT> I = scc_begin(G), E = scc_end(G); I != E; ++I) {
	const std::vector<GT::NodeType > &SCC = I;

	// Get the nodes in this SCC as a NodeSubset rather than a vector.
	GT::NodeSubset NodesInThisSCC;
	for (unsigned i = 0, e = SCC.size(); i != e; ++i)
	NodesInThisSCC.AddNode(SCC[i]->first);

	// There should be at least one node in every SCC.
	EXPECT_FALSE(NodesInThisSCC.isEmpty());

	// Check that every node in the SCC is reachable from every other node in
	// the SCC.
	for (unsigned i = 0; i != NUM_NODES; ++i)
	if (NodesInThisSCC.count(i))
	EXPECT_TRUE(NodesInThisSCC.isSubsetOf(G.NodesReachableFrom(i)));

	// OK, now that we now that every node in the SCC is reachable from every
	// other, this means that the set of nodes reachable from any node in the
	// SCC is the same as the set of nodes reachable from every node in the
	// SCC. Check that for every node N not in the SCC but reachable from the
	// SCC, no element of the SCC is reachable from N.
	for (unsigned i = 0; i != NUM_NODES; ++i)
	if (NodesInThisSCC.count(i)) {
	GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i);
	GT::NodeSubset ReachableButNotInSCC =
	NodesReachableFromSCC.Meet(NodesInThisSCC.Complement());

	for (unsigned j = 0; j != NUM_NODES; ++j)
	if (ReachableButNotInSCC.count(j))
	EXPECT_TRUE(G.NodesReachableFrom(j).Meet(NodesInThisSCC).isEmpty());

	// The result must be the same for all other nodes in this SCC, so
	// there is no point in checking them.
	break;
	}

	// This is indeed a SCC: a maximal set of nodes for which each node is
	// reachable from every other.

	// Check that we didn't already see this SCC.
	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));
	}
	}

	}