1 //===----- llvm/unittest/ADT/SCCIteratorTest.cpp - SCCIterator tests ------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 #include "llvm/ADT/GraphTraits.h"
12 #include "llvm/ADT/SCCIterator.h"
13 #include "gtest/gtest.h"
19 /// Graph<N> - A graph with N nodes. Note that N can be at most 8.
25 Graph& operator=(const Graph&);
27 static void ValidateIndex(unsigned Idx) {
28 assert(Idx < N && "Invalid node index!");
32 /// NodeSubset - A subset of the graph's nodes.
34 typedef unsigned char BitVector; // Where the limitation N <= 8 comes from.
36 NodeSubset(BitVector e) : Elements(e) {}
38 /// NodeSubset - Default constructor, creates an empty subset.
39 NodeSubset() : Elements(0) {
40 assert(N <= sizeof(BitVector)*CHAR_BIT && "Graph too big!");
42 /// NodeSubset - Copy constructor.
43 NodeSubset(const NodeSubset &other) : Elements(other.Elements) {}
45 /// Comparison operators.
46 bool operator==(const NodeSubset &other) const {
47 return other.Elements == this->Elements;
49 bool operator!=(const NodeSubset &other) const {
50 return !(*this == other);
53 /// AddNode - Add the node with the given index to the subset.
54 void AddNode(unsigned Idx) {
56 Elements |= 1U << Idx;
59 /// DeleteNode - Remove the node with the given index from the subset.
60 void DeleteNode(unsigned Idx) {
62 Elements &= ~(1U << Idx);
65 /// count - Return true if the node with the given index is in the subset.
66 bool count(unsigned Idx) {
68 return (Elements & (1U << Idx)) != 0;
71 /// isEmpty - Return true if this is the empty set.
72 bool isEmpty() const {
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;
81 /// Complement - Return the complement of this subset.
82 NodeSubset Complement() const {
83 return ~(unsigned)this->Elements & ((1U << N) - 1);
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;
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;
97 /// NodeType - Node index and set of children of the node.
98 typedef std::pair<unsigned, NodeSubset> NodeType;
101 /// Nodes - The list of nodes for this graph.
105 /// Graph - Default constructor. Creates an empty 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)
113 /// AddEdge - Add an edge from the node with index FromIdx to the node with
115 void AddEdge(unsigned FromIdx, unsigned ToIdx) {
116 ValidateIndex(FromIdx);
117 Nodes[FromIdx].second.AddNode(ToIdx);
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);
127 /// AccessNode - Get a pointer to the node with the given index.
128 NodeType *AccessNode(unsigned Idx) const {
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]);
135 /// NodesReachableFrom - Return the set of all nodes reachable from the given
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;
142 // The initial node is reachable.
143 Reachable.AddNode(Idx);
145 NodeSubset Previous(Reachable);
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);
152 // If nothing changed then we have found all reachable nodes.
153 if (Reachable == Previous)
160 /// ChildIterator - Visit all children of a node.
161 class ChildIterator {
164 /// FirstNode - Pointer to first node in the graph's Nodes array.
166 /// Children - Set of nodes which are children of this one and that haven't
167 /// yet been visited.
170 ChildIterator(); // Disable default constructor.
172 ChildIterator(NodeType *F, NodeSubset C) : FirstNode(F), Children(C) {}
175 /// ChildIterator - Copy constructor.
176 ChildIterator(const ChildIterator& other) : FirstNode(other.FirstNode),
177 Children(other.Children) {}
179 /// Comparison operators.
180 bool operator==(const ChildIterator &other) const {
181 return other.FirstNode == this->FirstNode &&
182 other.Children == this->Children;
184 bool operator!=(const ChildIterator &other) const {
185 return !(*this == other);
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);
197 assert(false && "Incrementing end iterator!");
198 return *this; // Avoid compiler warnings.
201 /// Postfix increment operator.
202 ChildIterator operator++(int) {
203 ChildIterator Result(*this);
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.
220 /// child_begin - Return an iterator pointing to the first child of the given
222 static ChildIterator child_begin(NodeType *Parent) {
223 return ChildIterator(Parent - Parent->first, Parent->second);
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());
232 template <unsigned N>
233 struct GraphTraits<Graph<N> > {
234 typedef typename Graph<N>::NodeType NodeType;
235 typedef typename Graph<N>::ChildIterator ChildIteratorType;
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);
241 static inline ChildIteratorType child_end(NodeType *Node) {
242 return Graph<N>::child_end(Node);
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.
251 #define NUM_GRAPHS (NUM_NODES * (NUM_NODES - 1))
252 typedef Graph<NUM_NODES> GT;
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);
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.
269 if (DescriptorCopy & 1)
271 DescriptorCopy >>= 1;
274 // Test the SCC logic on this graph.
276 /// NodesInSomeSCC - Those nodes which are in some SCC.
277 GT::NodeSubset NodesInSomeSCC;
279 for (scc_iterator<GT> I = scc_begin(G), E = scc_end(G); I != E; ++I) {
280 std::vector<GT::NodeType*> &SCC = *I;
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);
287 // There should be at least one node in every SCC.
288 EXPECT_FALSE(NodesInThisSCC.isEmpty());
290 // Check that every node in the SCC is reachable from every other node in
292 for (unsigned i = 0; i != NUM_NODES; ++i)
293 if (NodesInThisSCC.count(i))
294 EXPECT_TRUE(NodesInThisSCC.isSubsetOf(G.NodesReachableFrom(i)));
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());
307 for (unsigned j = 0; j != NUM_NODES; ++j)
308 if (ReachableButNotInSCC.count(j))
309 EXPECT_TRUE(G.NodesReachableFrom(j).Meet(NodesInThisSCC).isEmpty());
311 // The result must be the same for all other nodes in this SCC, so
312 // there is no point in checking them.
316 // This is indeed a SCC: a maximal set of nodes for which each node is
317 // reachable from every other.
319 // Check that we didn't already see this SCC.
320 EXPECT_TRUE(NodesInSomeSCC.Meet(NodesInThisSCC).isEmpty());
322 NodesInSomeSCC = NodesInSomeSCC.Join(NodesInThisSCC);
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.
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.
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));