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