SCCIteratorTest.cpp [plain text]
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "gtest/gtest.h"
#include <limits.h>
using namespace llvm;
namespace llvm {
template <unsigned N>
class Graph {
private:
Graph(const Graph&);
Graph& operator=(const Graph&);
static void ValidateIndex(unsigned Idx) {
assert(Idx < N && "Invalid node index!");
}
public:
class NodeSubset {
typedef unsigned char BitVector; BitVector Elements;
NodeSubset(BitVector e) : Elements(e) {}
public:
NodeSubset() : Elements(0) {
assert(N <= sizeof(BitVector)*CHAR_BIT && "Graph too big!");
}
NodeSubset(const NodeSubset &other) : Elements(other.Elements) {}
bool operator==(const NodeSubset &other) const {
return other.Elements == this->Elements;
}
bool operator!=(const NodeSubset &other) const {
return !(*this == other);
}
void AddNode(unsigned Idx) {
ValidateIndex(Idx);
Elements |= 1U << Idx;
}
void DeleteNode(unsigned Idx) {
ValidateIndex(Idx);
Elements &= ~(1U << Idx);
}
bool count(unsigned Idx) {
ValidateIndex(Idx);
return (Elements & (1U << Idx)) != 0;
}
bool isEmpty() const {
return Elements == 0;
}
bool isSubsetOf(const NodeSubset &other) const {
return (this->Elements | other.Elements) == other.Elements;
}
NodeSubset Complement() const {
return ~(unsigned)this->Elements & ((1U << N) - 1);
}
NodeSubset Join(const NodeSubset &other) const {
return this->Elements | other.Elements;
}
NodeSubset Meet(const NodeSubset &other) const {
return this->Elements & other.Elements;
}
};
typedef std::pair<unsigned, NodeSubset> NodeType;
private:
NodeType Nodes[N];
public:
Graph() {
for (unsigned i = 0; i != N; ++i)
Nodes[i].first = i;
}
void AddEdge(unsigned FromIdx, unsigned ToIdx) {
ValidateIndex(FromIdx);
Nodes[FromIdx].second.AddNode(ToIdx);
}
void DeleteEdge(unsigned FromIdx, unsigned ToIdx) {
ValidateIndex(FromIdx);
Nodes[FromIdx].second.DeleteNode(ToIdx);
}
NodeType *AccessNode(unsigned Idx) const {
ValidateIndex(Idx);
return const_cast<NodeType *>(&Nodes[Idx]);
}
NodeSubset NodesReachableFrom(unsigned Idx) const {
NodeSubset Reachable;
Reachable.AddNode(Idx);
do {
NodeSubset Previous(Reachable);
for (unsigned i = 0; i != N; ++i)
if (Previous.count(i))
Reachable = Reachable.Join(Nodes[i].second);
if (Reachable == Previous)
return Reachable;
} while (1);
}
class ChildIterator {
friend class Graph;
NodeType *FirstNode;
NodeSubset Children;
ChildIterator(); protected:
ChildIterator(NodeType *F, NodeSubset C) : FirstNode(F), Children(C) {}
public:
ChildIterator(const ChildIterator& other) : FirstNode(other.FirstNode),
Children(other.Children) {}
bool operator==(const ChildIterator &other) const {
return other.FirstNode == this->FirstNode &&
other.Children == this->Children;
}
bool operator!=(const ChildIterator &other) const {
return !(*this == other);
}
ChildIterator& operator++() {
for (unsigned i = 0; i != N; ++i)
if (Children.count(i)) {
Children.DeleteNode(i);
return *this;
}
assert(false && "Incrementing end iterator!");
return *this; }
ChildIterator operator++(int) {
ChildIterator Result(*this);
++(*this);
return Result;
}
NodeType *operator*() {
for (unsigned i = 0; i != N; ++i)
if (Children.count(i))
return FirstNode + i;
assert(false && "Dereferencing end iterator!");
return nullptr; }
};
static ChildIterator child_begin(NodeType *Parent) {
return ChildIterator(Parent - Parent->first, Parent->second);
}
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) {
#define NUM_NODES 4
#define NUM_GRAPHS (NUM_NODES * (NUM_NODES - 1))
typedef Graph<NUM_NODES> GT;
assert(NUM_GRAPHS < sizeof(unsigned) * CHAR_BIT && "Too many graphs!");
for (unsigned GraphDescriptor = 0; GraphDescriptor < (1U << NUM_GRAPHS);
++GraphDescriptor) {
GT G;
unsigned DescriptorCopy = GraphDescriptor;
for (unsigned i = 0; i != NUM_NODES; ++i)
for (unsigned j = 0; j != NUM_NODES; ++j) {
if (i == j) {
G.AddEdge(i, j);
continue;
}
if (DescriptorCopy & 1)
G.AddEdge(i, j);
DescriptorCopy >>= 1;
}
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;
GT::NodeSubset NodesInThisSCC;
for (unsigned i = 0, e = SCC.size(); i != e; ++i)
NodesInThisSCC.AddNode(SCC[i]->first);
EXPECT_FALSE(NodesInThisSCC.isEmpty());
for (unsigned i = 0; i != NUM_NODES; ++i)
if (NodesInThisSCC.count(i))
EXPECT_TRUE(NodesInThisSCC.isSubsetOf(G.NodesReachableFrom(i)));
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());
break;
}
EXPECT_TRUE(NodesInSomeSCC.Meet(NodesInThisSCC).isEmpty());
NodesInSomeSCC = NodesInSomeSCC.Join(NodesInThisSCC);
for (unsigned i = 0; i != NUM_NODES; ++i)
if (NodesInThisSCC.count(i)) {
GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i);
EXPECT_TRUE(NodesReachableFromSCC.isSubsetOf(NodesInSomeSCC));
break;
}
}
EXPECT_EQ(NodesInSomeSCC, G.NodesReachableFrom(0));
}
}
}