← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to unittests/ADT/SCCIteratorTest.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
unittests/ADT/SCCIteratorTest.cpp
 
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
 
 
15
using namespace llvm;
 
16
 
 
17
namespace llvm {
 
18
 
 
19
/// Graph<N> - A graph with N nodes.  Note that N can be at most 8.
 
20
template <unsigned N>
 
21
class Graph {
 
22
private:
 
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
  }
 
30
public:
 
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
 
 
98
private:
 
99
  /// Nodes - The list of nodes for this graph.
 
100
  NodeType Nodes[N];
 
101
public:
 
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
 
 
230
template <unsigned N>
 
231
struct 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
 
 
244
TEST(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
}