SCCIteratorTest.cpp revision c6a4f5e819217e1e12c458aed8e7b122e23a3a58
18537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands//===----- llvm/unittest/ADT/SCCIteratorTest.cpp - SCCIterator tests ------===// 28537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands// 38537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands// The LLVM Compiler Infrastructure 48537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands// 58537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands// This file is distributed under the University of Illinois Open Source 68537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands// License. See LICENSE.TXT for details. 78537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands// 88537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands//===----------------------------------------------------------------------===// 98537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 108537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands#include "llvm/ADT/SCCIterator.h" 115a88dda4be791426ab4d20a6a6c9c65d66614a27Chandler Carruth#include "llvm/ADT/GraphTraits.h" 128537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands#include "gtest/gtest.h" 135a88dda4be791426ab4d20a6a6c9c65d66614a27Chandler Carruth#include <limits.h> 148537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 158537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sandsusing namespace llvm; 168537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 178537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sandsnamespace llvm { 188537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 198537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands/// Graph<N> - A graph with N nodes. Note that N can be at most 8. 208537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sandstemplate <unsigned N> 218537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sandsclass Graph { 228537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sandsprivate: 238537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Disable copying. 248537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Graph(const Graph&); 258537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Graph& operator=(const Graph&); 268537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 278537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands static void ValidateIndex(unsigned Idx) { 288537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands assert(Idx < N && "Invalid node index!"); 298537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 308537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sandspublic: 318537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 328537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// NodeSubset - A subset of the graph's nodes. 338537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands class NodeSubset { 348537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands typedef unsigned char BitVector; // Where the limitation N <= 8 comes from. 358537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands BitVector Elements; 3600eab6c716e206491de195ae4dd85ea493c98582Jakub Staszak NodeSubset(BitVector e) : Elements(e) {} 378537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands public: 388537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// NodeSubset - Default constructor, creates an empty subset. 398537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeSubset() : Elements(0) { 408537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands assert(N <= sizeof(BitVector)*CHAR_BIT && "Graph too big!"); 418537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 428537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// NodeSubset - Copy constructor. 438537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeSubset(const NodeSubset &other) : Elements(other.Elements) {} 448537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 458537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Comparison operators. 468537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands bool operator==(const NodeSubset &other) const { 478537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return other.Elements == this->Elements; 488537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 498537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands bool operator!=(const NodeSubset &other) const { 508537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return !(*this == other); 518537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 528537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 538537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// AddNode - Add the node with the given index to the subset. 548537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands void AddNode(unsigned Idx) { 558537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ValidateIndex(Idx); 568537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Elements |= 1U << Idx; 578537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 588537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 598537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// DeleteNode - Remove the node with the given index from the subset. 608537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands void DeleteNode(unsigned Idx) { 618537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ValidateIndex(Idx); 628537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Elements &= ~(1U << Idx); 638537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 648537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 658537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// count - Return true if the node with the given index is in the subset. 668537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands bool count(unsigned Idx) { 678537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ValidateIndex(Idx); 688537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return (Elements & (1U << Idx)) != 0; 698537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 708537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 718537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// isEmpty - Return true if this is the empty set. 728537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands bool isEmpty() const { 738537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return Elements == 0; 748537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 758537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 768537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// isSubsetOf - Return true if this set is a subset of the given one. 778537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands bool isSubsetOf(const NodeSubset &other) const { 788537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return (this->Elements | other.Elements) == other.Elements; 798537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 808537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 818537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Complement - Return the complement of this subset. 828537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeSubset Complement() const { 838537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return ~(unsigned)this->Elements & ((1U << N) - 1); 848537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 858537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 868537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Join - Return the union of this subset and the given one. 878537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeSubset Join(const NodeSubset &other) const { 888537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return this->Elements | other.Elements; 898537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 908537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 918537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Meet - Return the intersection of this subset and the given one. 928537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeSubset Meet(const NodeSubset &other) const { 938537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return this->Elements & other.Elements; 948537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 958537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands }; 968537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 978537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// NodeType - Node index and set of children of the node. 988537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands typedef std::pair<unsigned, NodeSubset> NodeType; 998537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1008537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sandsprivate: 1018537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Nodes - The list of nodes for this graph. 1028537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeType Nodes[N]; 1038537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sandspublic: 1048537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1058537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Graph - Default constructor. Creates an empty graph. 1068537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Graph() { 1078537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Let each node know which node it is. This allows us to find the start of 1088537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // the Nodes array given a pointer to any element of it. 1098537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (unsigned i = 0; i != N; ++i) 1108537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Nodes[i].first = i; 1118537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 1128537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1138537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// AddEdge - Add an edge from the node with index FromIdx to the node with 1148537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// index ToIdx. 1158537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands void AddEdge(unsigned FromIdx, unsigned ToIdx) { 1168537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ValidateIndex(FromIdx); 1178537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Nodes[FromIdx].second.AddNode(ToIdx); 1188537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 1198537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1208537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// DeleteEdge - Remove the edge (if any) from the node with index FromIdx to 1218537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// the node with index ToIdx. 1228537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands void DeleteEdge(unsigned FromIdx, unsigned ToIdx) { 1238537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ValidateIndex(FromIdx); 1248537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Nodes[FromIdx].second.DeleteNode(ToIdx); 1258537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 1268537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1278537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// AccessNode - Get a pointer to the node with the given index. 1288537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeType *AccessNode(unsigned Idx) const { 1298537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ValidateIndex(Idx); 1308537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // The constant cast is needed when working with GraphTraits, which insists 1318537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // on taking a constant Graph. 1328537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return const_cast<NodeType *>(&Nodes[Idx]); 1338537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 1348537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1358537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// NodesReachableFrom - Return the set of all nodes reachable from the given 1368537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// node. 1378537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeSubset NodesReachableFrom(unsigned Idx) const { 1388537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // This algorithm doesn't scale, but that doesn't matter given the small 1398537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // size of our graphs. 1408537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeSubset Reachable; 1418537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1428537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // The initial node is reachable. 1438537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Reachable.AddNode(Idx); 1448537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands do { 1458537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeSubset Previous(Reachable); 1468537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1478537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Add in all nodes which are children of a reachable node. 1488537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (unsigned i = 0; i != N; ++i) 1498537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands if (Previous.count(i)) 1508537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Reachable = Reachable.Join(Nodes[i].second); 1518537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1528537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // If nothing changed then we have found all reachable nodes. 1538537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands if (Reachable == Previous) 1548537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return Reachable; 1558537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1568537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Rinse and repeat. 1578537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } while (1); 1588537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 1598537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1608537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// ChildIterator - Visit all children of a node. 1618537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands class ChildIterator { 1628537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands friend class Graph; 1638537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1648537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// FirstNode - Pointer to first node in the graph's Nodes array. 1658537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeType *FirstNode; 1668537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Children - Set of nodes which are children of this one and that haven't 1678537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// yet been visited. 1688537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeSubset Children; 1698537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1708537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ChildIterator(); // Disable default constructor. 1718537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands protected: 1728537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ChildIterator(NodeType *F, NodeSubset C) : FirstNode(F), Children(C) {} 1738537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1748537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands public: 1758537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// ChildIterator - Copy constructor. 1768537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ChildIterator(const ChildIterator& other) : FirstNode(other.FirstNode), 1778537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Children(other.Children) {} 1788537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1798537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Comparison operators. 1808537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands bool operator==(const ChildIterator &other) const { 1818537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return other.FirstNode == this->FirstNode && 1828537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands other.Children == this->Children; 1838537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 1848537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands bool operator!=(const ChildIterator &other) const { 1858537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return !(*this == other); 1868537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 1878537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 1888537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Prefix increment operator. 1898537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ChildIterator& operator++() { 1908537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Find the next unvisited child node. 1918537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (unsigned i = 0; i != N; ++i) 1928537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands if (Children.count(i)) { 1938537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Remove that child - it has been visited. This is the increment! 1948537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands Children.DeleteNode(i); 1958537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return *this; 1968537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 1978537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands assert(false && "Incrementing end iterator!"); 1988537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return *this; // Avoid compiler warnings. 1998537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 2008537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2018537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Postfix increment operator. 2028537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ChildIterator operator++(int) { 2038537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ChildIterator Result(*this); 2048537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands ++(*this); 2058537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return Result; 2068537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 2078537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2088537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// Dereference operator. 2098537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodeType *operator*() { 2108537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Find the next unvisited child node. 2118537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (unsigned i = 0; i != N; ++i) 2128537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands if (Children.count(i)) 2138537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Return a pointer to it. 2148537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return FirstNode + i; 2158537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands assert(false && "Dereferencing end iterator!"); 216c6a4f5e819217e1e12c458aed8e7b122e23a3a58Stephen Hines return nullptr; // Avoid compiler warning. 2178537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 2188537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands }; 2198537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2208537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// child_begin - Return an iterator pointing to the first child of the given 2218537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// node. 2228537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands static ChildIterator child_begin(NodeType *Parent) { 2238537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return ChildIterator(Parent - Parent->first, Parent->second); 2248537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 2258537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2268537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// child_end - Return the end iterator for children of the given node. 2278537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands static ChildIterator child_end(NodeType *Parent) { 2288537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return ChildIterator(Parent - Parent->first, NodeSubset()); 2298537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 2308537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands}; 2318537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2328537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sandstemplate <unsigned N> 2338537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sandsstruct GraphTraits<Graph<N> > { 2348537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands typedef typename Graph<N>::NodeType NodeType; 2358537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands typedef typename Graph<N>::ChildIterator ChildIteratorType; 2368537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2378537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands static inline NodeType *getEntryNode(const Graph<N> &G) { return G.AccessNode(0); } 2388537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands static inline ChildIteratorType child_begin(NodeType *Node) { 2398537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return Graph<N>::child_begin(Node); 2408537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 2418537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands static inline ChildIteratorType child_end(NodeType *Node) { 2428537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands return Graph<N>::child_end(Node); 2438537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 2448537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands}; 2458537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2468537e8a9a506a2ca1b7795e8d907982ec2235973Duncan SandsTEST(SCCIteratorTest, AllSmallGraphs) { 2478537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Test SCC computation against every graph with NUM_NODES nodes or less. 2488537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Since SCC considers every node to have an implicit self-edge, we only 2498537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // create graphs for which every node has a self-edge. 2508537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands#define NUM_NODES 4 2518537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands#define NUM_GRAPHS (NUM_NODES * (NUM_NODES - 1)) 2526815ff07d45e5905b2a5c1e1df8f09ae8c38e5deDuncan Sands typedef Graph<NUM_NODES> GT; 2538537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2546815ff07d45e5905b2a5c1e1df8f09ae8c38e5deDuncan Sands /// Enumerate all graphs using NUM_GRAPHS bits. 2556815ff07d45e5905b2a5c1e1df8f09ae8c38e5deDuncan Sands assert(NUM_GRAPHS < sizeof(unsigned) * CHAR_BIT && "Too many graphs!"); 2566815ff07d45e5905b2a5c1e1df8f09ae8c38e5deDuncan Sands for (unsigned GraphDescriptor = 0; GraphDescriptor < (1U << NUM_GRAPHS); 2576815ff07d45e5905b2a5c1e1df8f09ae8c38e5deDuncan Sands ++GraphDescriptor) { 2588537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands GT G; 2598537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2608537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Add edges as specified by the descriptor. 2615edfbebb7d085ce52fe7c3f96feacfd246b3f071Duncan Sands unsigned DescriptorCopy = GraphDescriptor; 2628537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (unsigned i = 0; i != NUM_NODES; ++i) 2638537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (unsigned j = 0; j != NUM_NODES; ++j) { 2648537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Always add a self-edge. 2658537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands if (i == j) { 2668537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands G.AddEdge(i, j); 2678537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands continue; 2688537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 2698537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands if (DescriptorCopy & 1) 2708537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands G.AddEdge(i, j); 2718537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands DescriptorCopy >>= 1; 2728537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 2738537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2748537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Test the SCC logic on this graph. 2758537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2768537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands /// NodesInSomeSCC - Those nodes which are in some SCC. 2778537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands GT::NodeSubset NodesInSomeSCC; 2788537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2798537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (scc_iterator<GT> I = scc_begin(G), E = scc_end(G); I != E; ++I) { 280dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const std::vector<GT::NodeType *> &SCC = *I; 2818537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2828537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Get the nodes in this SCC as a NodeSubset rather than a vector. 2838537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands GT::NodeSubset NodesInThisSCC; 2848537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (unsigned i = 0, e = SCC.size(); i != e; ++i) 2858537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodesInThisSCC.AddNode(SCC[i]->first); 2868537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2878537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // There should be at least one node in every SCC. 2888537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands EXPECT_FALSE(NodesInThisSCC.isEmpty()); 2898537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2908537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Check that every node in the SCC is reachable from every other node in 2918537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // the SCC. 2928537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (unsigned i = 0; i != NUM_NODES; ++i) 2938537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands if (NodesInThisSCC.count(i)) 2948537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands EXPECT_TRUE(NodesInThisSCC.isSubsetOf(G.NodesReachableFrom(i))); 2958537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 2968537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // OK, now that we now that every node in the SCC is reachable from every 2978537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // other, this means that the set of nodes reachable from any node in the 2988537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // SCC is the same as the set of nodes reachable from every node in the 2998537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // SCC. Check that for every node N not in the SCC but reachable from the 3008537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // SCC, no element of the SCC is reachable from N. 3018537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (unsigned i = 0; i != NUM_NODES; ++i) 3028537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands if (NodesInThisSCC.count(i)) { 3038537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i); 3048537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands GT::NodeSubset ReachableButNotInSCC = 3058537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodesReachableFromSCC.Meet(NodesInThisSCC.Complement()); 3068537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 3078537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands for (unsigned j = 0; j != NUM_NODES; ++j) 3088537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands if (ReachableButNotInSCC.count(j)) 3098537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands EXPECT_TRUE(G.NodesReachableFrom(j).Meet(NodesInThisSCC).isEmpty()); 3108537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 3118537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // The result must be the same for all other nodes in this SCC, so 3128537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // there is no point in checking them. 3138537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands break; 3148537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 3158537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 3168537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // This is indeed a SCC: a maximal set of nodes for which each node is 3178537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // reachable from every other. 3188537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 3198537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Check that we didn't already see this SCC. 3208537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands EXPECT_TRUE(NodesInSomeSCC.Meet(NodesInThisSCC).isEmpty()); 3218537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 3228537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands NodesInSomeSCC = NodesInSomeSCC.Join(NodesInThisSCC); 3236f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands 3246f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands // Check a property that is specific to the LLVM SCC iterator and 3256f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands // guaranteed by it: if a node in SCC S1 has an edge to a node in 3266f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands // SCC S2, then S1 is visited *after* S2. This means that the set 3276f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands // of nodes reachable from this SCC must be contained either in the 3286f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands // union of this SCC and all previously visited SCC's. 3296f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands 3306f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands for (unsigned i = 0; i != NUM_NODES; ++i) 3316f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands if (NodesInThisSCC.count(i)) { 3326f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i); 3336f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands EXPECT_TRUE(NodesReachableFromSCC.isSubsetOf(NodesInSomeSCC)); 3346f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands // The result must be the same for all other nodes in this SCC, so 3356f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands // there is no point in checking them. 3366f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands break; 3376f7eec12941f61148c2615eafa50b49096fb9e2fDuncan Sands } 3388537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands } 3398537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 3408537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // Finally, check that the nodes in some SCC are exactly those that are 3418537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands // reachable from the initial node. 3428537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands EXPECT_EQ(NodesInSomeSCC, G.NodesReachableFrom(0)); 3436815ff07d45e5905b2a5c1e1df8f09ae8c38e5deDuncan Sands } 3448537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands} 3458537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands 3468537e8a9a506a2ca1b7795e8d907982ec2235973Duncan Sands} 347