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