//
//===----------------------------------------------------------------------===//
-#include <limits.h>
-#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/GraphTraits.h"
#include "gtest/gtest.h"
+#include <limits.h>
using namespace llvm;
class NodeSubset {
typedef unsigned char BitVector; // Where the limitation N <= 8 comes from.
BitVector Elements;
- NodeSubset(BitVector e) : Elements(e) {};
+ NodeSubset(BitVector e) : Elements(e) {}
public:
/// NodeSubset - Default constructor, creates an empty subset.
NodeSubset() : Elements(0) {
assert(N <= sizeof(BitVector)*CHAR_BIT && "Graph too big!");
}
- /// NodeSubset - Copy constructor.
- NodeSubset(const NodeSubset &other) : Elements(other.Elements) {}
/// Comparison operators.
bool operator==(const NodeSubset &other) const {
// Return a pointer to it.
return FirstNode + i;
assert(false && "Dereferencing end iterator!");
- return 0; // Avoid compiler warning.
+ return nullptr; // Avoid compiler warning.
}
};
// create graphs for which every node has a self-edge.
#define NUM_NODES 4
#define NUM_GRAPHS (NUM_NODES * (NUM_NODES - 1))
+ typedef Graph<NUM_NODES> GT;
- /// GraphDescriptor - Enumerate all graphs using NUM_GRAPHS bits.
- uint16_t GraphDescriptor = 0;
- assert(NUM_GRAPHS <= sizeof(uint16_t) * CHAR_BIT && "Too many graphs!");
-
- do {
- typedef Graph<NUM_NODES> GT;
-
+ /// Enumerate all graphs using NUM_GRAPHS bits.
+ static_assert(NUM_GRAPHS < sizeof(unsigned) * CHAR_BIT, "Too many graphs!");
+ for (unsigned GraphDescriptor = 0; GraphDescriptor < (1U << NUM_GRAPHS);
+ ++GraphDescriptor) {
GT G;
// Add edges as specified by the descriptor.
- uint16_t DescriptorCopy = GraphDescriptor;
+ unsigned DescriptorCopy = GraphDescriptor;
for (unsigned i = 0; i != NUM_NODES; ++i)
for (unsigned j = 0; j != NUM_NODES; ++j) {
// Always add a self-edge.
GT::NodeSubset NodesInSomeSCC;
for (scc_iterator<GT> I = scc_begin(G), E = scc_end(G); I != E; ++I) {
- std::vector<GT::NodeType*> &SCC = *I;
+ const std::vector<GT::NodeType *> &SCC = *I;
// Get the nodes in this SCC as a NodeSubset rather than a vector.
GT::NodeSubset NodesInThisSCC;
EXPECT_TRUE(NodesInSomeSCC.Meet(NodesInThisSCC).isEmpty());
NodesInSomeSCC = NodesInSomeSCC.Join(NodesInThisSCC);
+
+ // Check a property that is specific to the LLVM SCC iterator and
+ // guaranteed by it: if a node in SCC S1 has an edge to a node in
+ // SCC S2, then S1 is visited *after* S2. This means that the set
+ // of nodes reachable from this SCC must be contained either in the
+ // union of this SCC and all previously visited SCC's.
+
+ for (unsigned i = 0; i != NUM_NODES; ++i)
+ if (NodesInThisSCC.count(i)) {
+ GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i);
+ EXPECT_TRUE(NodesReachableFromSCC.isSubsetOf(NodesInSomeSCC));
+ // The result must be the same for all other nodes in this SCC, so
+ // there is no point in checking them.
+ break;
+ }
}
// Finally, check that the nodes in some SCC are exactly those that are
// reachable from the initial node.
EXPECT_EQ(NodesInSomeSCC, G.NodesReachableFrom(0));
-
- ++GraphDescriptor;
- } while (GraphDescriptor && (unsigned)GraphDescriptor < (1U << NUM_GRAPHS));
+ }
}
}