]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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 | ||
223e47cc | 10 | #include "llvm/ADT/SCCIterator.h" |
970d7e83 | 11 | #include "llvm/ADT/GraphTraits.h" |
223e47cc | 12 | #include "gtest/gtest.h" |
970d7e83 | 13 | #include <limits.h> |
223e47cc LB |
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 | /// NodeSubset - Copy constructor. | |
43 | NodeSubset(const NodeSubset &other) : Elements(other.Elements) {} | |
44 | ||
45 | /// Comparison operators. | |
46 | bool operator==(const NodeSubset &other) const { | |
47 | return other.Elements == this->Elements; | |
48 | } | |
49 | bool operator!=(const NodeSubset &other) const { | |
50 | return !(*this == other); | |
51 | } | |
52 | ||
53 | /// AddNode - Add the node with the given index to the subset. | |
54 | void AddNode(unsigned Idx) { | |
55 | ValidateIndex(Idx); | |
56 | Elements |= 1U << Idx; | |
57 | } | |
58 | ||
59 | /// DeleteNode - Remove the node with the given index from the subset. | |
60 | void DeleteNode(unsigned Idx) { | |
61 | ValidateIndex(Idx); | |
62 | Elements &= ~(1U << Idx); | |
63 | } | |
64 | ||
65 | /// count - Return true if the node with the given index is in the subset. | |
66 | bool count(unsigned Idx) { | |
67 | ValidateIndex(Idx); | |
68 | return (Elements & (1U << Idx)) != 0; | |
69 | } | |
70 | ||
71 | /// isEmpty - Return true if this is the empty set. | |
72 | bool isEmpty() const { | |
73 | return Elements == 0; | |
74 | } | |
75 | ||
76 | /// isSubsetOf - Return true if this set is a subset of the given one. | |
77 | bool isSubsetOf(const NodeSubset &other) const { | |
78 | return (this->Elements | other.Elements) == other.Elements; | |
79 | } | |
80 | ||
81 | /// Complement - Return the complement of this subset. | |
82 | NodeSubset Complement() const { | |
83 | return ~(unsigned)this->Elements & ((1U << N) - 1); | |
84 | } | |
85 | ||
86 | /// Join - Return the union of this subset and the given one. | |
87 | NodeSubset Join(const NodeSubset &other) const { | |
88 | return this->Elements | other.Elements; | |
89 | } | |
90 | ||
91 | /// Meet - Return the intersection of this subset and the given one. | |
92 | NodeSubset Meet(const NodeSubset &other) const { | |
93 | return this->Elements & other.Elements; | |
94 | } | |
95 | }; | |
96 | ||
97 | /// NodeType - Node index and set of children of the node. | |
98 | typedef std::pair<unsigned, NodeSubset> NodeType; | |
99 | ||
100 | private: | |
101 | /// Nodes - The list of nodes for this graph. | |
102 | NodeType Nodes[N]; | |
103 | public: | |
104 | ||
105 | /// Graph - Default constructor. Creates an empty graph. | |
106 | Graph() { | |
107 | // Let each node know which node it is. This allows us to find the start of | |
108 | // the Nodes array given a pointer to any element of it. | |
109 | for (unsigned i = 0; i != N; ++i) | |
110 | Nodes[i].first = i; | |
111 | } | |
112 | ||
113 | /// AddEdge - Add an edge from the node with index FromIdx to the node with | |
114 | /// index ToIdx. | |
115 | void AddEdge(unsigned FromIdx, unsigned ToIdx) { | |
116 | ValidateIndex(FromIdx); | |
117 | Nodes[FromIdx].second.AddNode(ToIdx); | |
118 | } | |
119 | ||
120 | /// DeleteEdge - Remove the edge (if any) from the node with index FromIdx to | |
121 | /// the node with index ToIdx. | |
122 | void DeleteEdge(unsigned FromIdx, unsigned ToIdx) { | |
123 | ValidateIndex(FromIdx); | |
124 | Nodes[FromIdx].second.DeleteNode(ToIdx); | |
125 | } | |
126 | ||
127 | /// AccessNode - Get a pointer to the node with the given index. | |
128 | NodeType *AccessNode(unsigned Idx) const { | |
129 | ValidateIndex(Idx); | |
130 | // The constant cast is needed when working with GraphTraits, which insists | |
131 | // on taking a constant Graph. | |
132 | return const_cast<NodeType *>(&Nodes[Idx]); | |
133 | } | |
134 | ||
135 | /// NodesReachableFrom - Return the set of all nodes reachable from the given | |
136 | /// node. | |
137 | NodeSubset NodesReachableFrom(unsigned Idx) const { | |
138 | // This algorithm doesn't scale, but that doesn't matter given the small | |
139 | // size of our graphs. | |
140 | NodeSubset Reachable; | |
141 | ||
142 | // The initial node is reachable. | |
143 | Reachable.AddNode(Idx); | |
144 | do { | |
145 | NodeSubset Previous(Reachable); | |
146 | ||
147 | // Add in all nodes which are children of a reachable node. | |
148 | for (unsigned i = 0; i != N; ++i) | |
149 | if (Previous.count(i)) | |
150 | Reachable = Reachable.Join(Nodes[i].second); | |
151 | ||
152 | // If nothing changed then we have found all reachable nodes. | |
153 | if (Reachable == Previous) | |
154 | return Reachable; | |
155 | ||
156 | // Rinse and repeat. | |
157 | } while (1); | |
158 | } | |
159 | ||
160 | /// ChildIterator - Visit all children of a node. | |
161 | class ChildIterator { | |
162 | friend class Graph; | |
163 | ||
164 | /// FirstNode - Pointer to first node in the graph's Nodes array. | |
165 | NodeType *FirstNode; | |
166 | /// Children - Set of nodes which are children of this one and that haven't | |
167 | /// yet been visited. | |
168 | NodeSubset Children; | |
169 | ||
170 | ChildIterator(); // Disable default constructor. | |
171 | protected: | |
172 | ChildIterator(NodeType *F, NodeSubset C) : FirstNode(F), Children(C) {} | |
173 | ||
174 | public: | |
175 | /// ChildIterator - Copy constructor. | |
176 | ChildIterator(const ChildIterator& other) : FirstNode(other.FirstNode), | |
177 | Children(other.Children) {} | |
178 | ||
179 | /// Comparison operators. | |
180 | bool operator==(const ChildIterator &other) const { | |
181 | return other.FirstNode == this->FirstNode && | |
182 | other.Children == this->Children; | |
183 | } | |
184 | bool operator!=(const ChildIterator &other) const { | |
185 | return !(*this == other); | |
186 | } | |
187 | ||
188 | /// Prefix increment operator. | |
189 | ChildIterator& operator++() { | |
190 | // Find the next unvisited child node. | |
191 | for (unsigned i = 0; i != N; ++i) | |
192 | if (Children.count(i)) { | |
193 | // Remove that child - it has been visited. This is the increment! | |
194 | Children.DeleteNode(i); | |
195 | return *this; | |
196 | } | |
197 | assert(false && "Incrementing end iterator!"); | |
198 | return *this; // Avoid compiler warnings. | |
199 | } | |
200 | ||
201 | /// Postfix increment operator. | |
202 | ChildIterator operator++(int) { | |
203 | ChildIterator Result(*this); | |
204 | ++(*this); | |
205 | return Result; | |
206 | } | |
207 | ||
208 | /// Dereference operator. | |
209 | NodeType *operator*() { | |
210 | // Find the next unvisited child node. | |
211 | for (unsigned i = 0; i != N; ++i) | |
212 | if (Children.count(i)) | |
213 | // Return a pointer to it. | |
214 | return FirstNode + i; | |
215 | assert(false && "Dereferencing end iterator!"); | |
1a4d82fc | 216 | return nullptr; // Avoid compiler warning. |
223e47cc LB |
217 | } |
218 | }; | |
219 | ||
220 | /// child_begin - Return an iterator pointing to the first child of the given | |
221 | /// node. | |
222 | static ChildIterator child_begin(NodeType *Parent) { | |
223 | return ChildIterator(Parent - Parent->first, Parent->second); | |
224 | } | |
225 | ||
226 | /// child_end - Return the end iterator for children of the given node. | |
227 | static ChildIterator child_end(NodeType *Parent) { | |
228 | return ChildIterator(Parent - Parent->first, NodeSubset()); | |
229 | } | |
230 | }; | |
231 | ||
232 | template <unsigned N> | |
233 | struct GraphTraits<Graph<N> > { | |
234 | typedef typename Graph<N>::NodeType NodeType; | |
235 | typedef typename Graph<N>::ChildIterator ChildIteratorType; | |
236 | ||
237 | static inline NodeType *getEntryNode(const Graph<N> &G) { return G.AccessNode(0); } | |
238 | static inline ChildIteratorType child_begin(NodeType *Node) { | |
239 | return Graph<N>::child_begin(Node); | |
240 | } | |
241 | static inline ChildIteratorType child_end(NodeType *Node) { | |
242 | return Graph<N>::child_end(Node); | |
243 | } | |
244 | }; | |
245 | ||
246 | TEST(SCCIteratorTest, AllSmallGraphs) { | |
247 | // Test SCC computation against every graph with NUM_NODES nodes or less. | |
248 | // Since SCC considers every node to have an implicit self-edge, we only | |
249 | // create graphs for which every node has a self-edge. | |
250 | #define NUM_NODES 4 | |
251 | #define NUM_GRAPHS (NUM_NODES * (NUM_NODES - 1)) | |
252 | typedef Graph<NUM_NODES> GT; | |
253 | ||
254 | /// Enumerate all graphs using NUM_GRAPHS bits. | |
255 | assert(NUM_GRAPHS < sizeof(unsigned) * CHAR_BIT && "Too many graphs!"); | |
256 | for (unsigned GraphDescriptor = 0; GraphDescriptor < (1U << NUM_GRAPHS); | |
257 | ++GraphDescriptor) { | |
258 | GT G; | |
259 | ||
260 | // Add edges as specified by the descriptor. | |
261 | unsigned DescriptorCopy = GraphDescriptor; | |
262 | for (unsigned i = 0; i != NUM_NODES; ++i) | |
263 | for (unsigned j = 0; j != NUM_NODES; ++j) { | |
264 | // Always add a self-edge. | |
265 | if (i == j) { | |
266 | G.AddEdge(i, j); | |
267 | continue; | |
268 | } | |
269 | if (DescriptorCopy & 1) | |
270 | G.AddEdge(i, j); | |
271 | DescriptorCopy >>= 1; | |
272 | } | |
273 | ||
274 | // Test the SCC logic on this graph. | |
275 | ||
276 | /// NodesInSomeSCC - Those nodes which are in some SCC. | |
277 | GT::NodeSubset NodesInSomeSCC; | |
278 | ||
279 | for (scc_iterator<GT> I = scc_begin(G), E = scc_end(G); I != E; ++I) { | |
1a4d82fc | 280 | const std::vector<GT::NodeType *> &SCC = *I; |
223e47cc LB |
281 | |
282 | // Get the nodes in this SCC as a NodeSubset rather than a vector. | |
283 | GT::NodeSubset NodesInThisSCC; | |
284 | for (unsigned i = 0, e = SCC.size(); i != e; ++i) | |
285 | NodesInThisSCC.AddNode(SCC[i]->first); | |
286 | ||
287 | // There should be at least one node in every SCC. | |
288 | EXPECT_FALSE(NodesInThisSCC.isEmpty()); | |
289 | ||
290 | // Check that every node in the SCC is reachable from every other node in | |
291 | // the SCC. | |
292 | for (unsigned i = 0; i != NUM_NODES; ++i) | |
293 | if (NodesInThisSCC.count(i)) | |
294 | EXPECT_TRUE(NodesInThisSCC.isSubsetOf(G.NodesReachableFrom(i))); | |
295 | ||
296 | // OK, now that we now that every node in the SCC is reachable from every | |
297 | // other, this means that the set of nodes reachable from any node in the | |
298 | // SCC is the same as the set of nodes reachable from every node in the | |
299 | // SCC. Check that for every node N not in the SCC but reachable from the | |
300 | // SCC, no element of the SCC is reachable from N. | |
301 | for (unsigned i = 0; i != NUM_NODES; ++i) | |
302 | if (NodesInThisSCC.count(i)) { | |
303 | GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i); | |
304 | GT::NodeSubset ReachableButNotInSCC = | |
305 | NodesReachableFromSCC.Meet(NodesInThisSCC.Complement()); | |
306 | ||
307 | for (unsigned j = 0; j != NUM_NODES; ++j) | |
308 | if (ReachableButNotInSCC.count(j)) | |
309 | EXPECT_TRUE(G.NodesReachableFrom(j).Meet(NodesInThisSCC).isEmpty()); | |
310 | ||
311 | // The result must be the same for all other nodes in this SCC, so | |
312 | // there is no point in checking them. | |
313 | break; | |
314 | } | |
315 | ||
316 | // This is indeed a SCC: a maximal set of nodes for which each node is | |
317 | // reachable from every other. | |
318 | ||
319 | // Check that we didn't already see this SCC. | |
320 | EXPECT_TRUE(NodesInSomeSCC.Meet(NodesInThisSCC).isEmpty()); | |
321 | ||
322 | NodesInSomeSCC = NodesInSomeSCC.Join(NodesInThisSCC); | |
323 | ||
324 | // Check a property that is specific to the LLVM SCC iterator and | |
325 | // guaranteed by it: if a node in SCC S1 has an edge to a node in | |
326 | // SCC S2, then S1 is visited *after* S2. This means that the set | |
327 | // of nodes reachable from this SCC must be contained either in the | |
328 | // union of this SCC and all previously visited SCC's. | |
329 | ||
330 | for (unsigned i = 0; i != NUM_NODES; ++i) | |
331 | if (NodesInThisSCC.count(i)) { | |
332 | GT::NodeSubset NodesReachableFromSCC = G.NodesReachableFrom(i); | |
333 | EXPECT_TRUE(NodesReachableFromSCC.isSubsetOf(NodesInSomeSCC)); | |
334 | // The result must be the same for all other nodes in this SCC, so | |
335 | // there is no point in checking them. | |
336 | break; | |
337 | } | |
338 | } | |
339 | ||
340 | // Finally, check that the nodes in some SCC are exactly those that are | |
341 | // reachable from the initial node. | |
342 | EXPECT_EQ(NodesInSomeSCC, G.NodesReachableFrom(0)); | |
343 | } | |
344 | } | |
345 | ||
346 | } |