Branch data Line data Source code
1 : : /* Find prime paths
2 : : Copyright (C) 2024-2025 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
6 : : GCC is free software; you can redistribute it and/or modify it under
7 : : the terms of the GNU General Public License as published by the Free
8 : : Software Foundation; either version 3, or (at your option) any later
9 : : version.
10 : :
11 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : for more details.
15 : :
16 : : You should have received a copy of the GNU General Public License
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "obstack.h"
24 : : #include "sbitmap.h"
25 : : #include "vec.h"
26 : : #include "graphds.h"
27 : : #include "selftest.h"
28 : :
29 : : namespace
30 : : {
31 : :
32 : : /* Counter for the number of candidate paths to generate before giving up. It
33 : : is neater to use a global because it has to be checked deep in helper
34 : : functions, which may also suffer under path explosion. It is a heuristic
35 : : guaranteed to overshoot the number of actual paths (which is difficult to
36 : : estimate), and is intended to give up on (absurdly) large functions with
37 : : millions of paths, not be a high fidelity rejection mechanism. This is
38 : : essentially an exception. */
39 : : size_t approx_limit;
40 : :
41 : : /* Reset the threshold to APPROX when a function is too complex and finding
42 : : paths should give up. */
43 : : void
44 : 575 : limit_reset (size_t approx)
45 : : {
46 : 575 : approx_limit = approx;
47 : 0 : }
48 : :
49 : : /* Record approximately APPROX new paths. Returns true if the limit is
50 : : exceeded and coverage should give up. */
51 : : bool
52 : 6748 : limit_checked_add (size_t approx)
53 : : {
54 : 0 : approx_limit -= approx < approx_limit ? approx : approx_limit;
55 : 6748 : return approx_limit == 0;
56 : : }
57 : :
58 : : /* Check if adding APPROX would exceed the path limit. This is necessary when
59 : : (pessimistically counted) trie insertions would exceed the limit and yields
60 : : a partial result, when the path count would drop below the limit again once
61 : : redundancies are eliminated. */
62 : : bool
63 : 3795409 : limit_exceed_p (size_t approx)
64 : : {
65 : 3795409 : return approx > approx_limit;
66 : : }
67 : :
68 : : /* A silly RAII wrapper for struct graph. The prime_paths function has multiple
69 : : returns, and this helps reliably clean up. */
70 : : struct auto_graph
71 : : {
72 : 1186 : auto_graph (struct graph *graph) : ptr (graph) {}
73 : : auto_graph (const auto_graph &) = delete;
74 : 575 : ~auto_graph () { free_graph (ptr); }
75 : : operator struct graph* () { return ptr; }
76 : : struct graph* operator -> () { return ptr; }
77 : : graph *ptr;
78 : : };
79 : :
80 : : /* A silly RAII wrapper for an sbitmap vector. The prime_paths function has
81 : : multiple returns, and this helps reliably clean up. */
82 : : struct auto_sbitmap_vector
83 : : {
84 : 575 : auto_sbitmap_vector (sbitmap *s) : ptr (s) {}
85 : : auto_sbitmap_vector (const auto_sbitmap_vector &) = delete;
86 : 571 : ~auto_sbitmap_vector () { sbitmap_vector_free (ptr); }
87 : : operator sbitmap* () { return ptr; }
88 : : sbitmap* ptr;
89 : : };
90 : :
91 : : /* A silly RAII wrpaper for automatically releasing a vec<vec<int>>. */
92 : : struct auto_vec_vec : vec<vec<int>>
93 : : {
94 : : auto_vec_vec () = default;
95 : 64 : auto_vec_vec (vec<vec<int>> v) : vec<vec<int>>(v) {}
96 : 1282 : ~auto_vec_vec () { release_vec_vec (*this); }
97 : : };
98 : :
99 : : /* A silly RAII wrpaper for automatically releasing a vec<vec<vec<int>>>. */
100 : : struct auto_vec_vec_vec : vec<vec<vec<int>>>
101 : : {
102 : 1143 : ~auto_vec_vec_vec ()
103 : : {
104 : 13556 : for (vec<vec<int>> &v : *this)
105 : 10127 : release_vec_vec (v);
106 : 1143 : release ();
107 : 1143 : }
108 : : };
109 : :
110 : : /* A trivial key/value pair for a short linear map type. */
111 : : struct xpair
112 : : {
113 : : int key;
114 : : unsigned val;
115 : : };
116 : :
117 : : /* A node in a trie, optimized for mid-sized alphabets possibly larger than 256
118 : : but not much more. Finding the prime paths ends up creating a large amount
119 : : of these nodes so space and access costs matters a lot.
120 : :
121 : : The node does not explicitly store its own key (CFG vertex ID/basic block
122 : : index), nor does it store pointers to its successors. Rather, it stores the
123 : : key+offset pairs for its successors the root trie object, and in a sense
124 : : behaves like near pointers. This makes the trie vertices small and
125 : : reloctable, and removes the need for pointer chasing when releasing the trie.
126 : :
127 : : The union of near/far is essentially a short-vector optimization, switching
128 : : to a heap-allocated vector when necessary. This happens relatively rarely
129 : : (usually maxes out at 1-2%), and the vertices that have more than 2 sucessors
130 : : also tend to have more than 4. The root vertex tends to use the dynamic
131 : : vector because the subpaths are recorded as the successors of the root.
132 : :
133 : : Conceptually, this is a small map from vertex-id -> index and the API is
134 : : modelled as such. The insert and search functions are unrolled by hand when
135 : : using the small vector. This has a noticable performance impact on insert in
136 : : particular, and is not too complex since we know we are limited to 2
137 : : elements.
138 : :
139 : : Vertices are tagged with endofpath and inserted. If endofpath is set, the
140 : : path from the root to this vertex is a complete path. If inserted is set
141 : : then the vertex is a part of proper path (one given to insert) and not
142 : : generated as a suffix. For example:
143 : :
144 : : insert ([2 4 6])
145 : : insert ([9 7 2 4 6])
146 : : insert ([2 4 6 8])
147 : :
148 : : The inserted flags for [2 4 6] are not cleared, because otherwise [2 4 6 8]
149 : : would be dropped when only following inserted vertices. The endofpath flag
150 : : in [2 4 6] is cleared when the suffixes of [9 7 2 4 6] are inserted.
151 : :
152 : : The node will be inserted into a vec, and should be trivial. Instances
153 : : should be value-initialized to zero-intialized state. */
154 : : struct trie_node
155 : : {
156 : 89331 : unsigned length () const
157 : 89331 : { return !heaped ? len : far.length (); }
158 : :
159 : : const xpair *begin () const
160 : : { return !heaped ? near : far.begin (); }
161 : :
162 : : const xpair *end () const
163 : : { return !heaped ? (near + len) : far.end (); }
164 : :
165 : : /* Get the ith successor. This is used for traversal and not lookup, and
166 : : should only be used by the iterator. */
167 : 53983 : const xpair &at (unsigned i) const
168 : 53983 : { return !heaped ? near[i] : far[i]; }
169 : :
170 : : const xpair *get (int key) const;
171 : : void put (int key, unsigned val);
172 : :
173 : : unsigned near_lower_bound (int key) const;
174 : :
175 : : /* Experimentally I found that using a union with 2 elements in the near array
176 : : to be faster than 4 or without the union (very slightly). A lot of trie
177 : : vertices will be created, and vast majority of vertices will have 1 or 2
178 : : successors (straight line or if-then), and the cost of size and copying
179 : : adds up. */
180 : : union
181 : : {
182 : : xpair near[2];
183 : : vec<xpair> far;
184 : : };
185 : : unsigned len : 8;
186 : : unsigned endofpath : 1;
187 : : unsigned inserted : 1;
188 : : unsigned heaped : 1;
189 : : };
190 : :
191 : : /* Compare LHS.key < RHS.key, for use with vec.lower_bound. */
192 : : bool
193 : 30423 : xpair_less (const xpair& lhs, const xpair& rhs)
194 : : {
195 : 30423 : return lhs.key < rhs.key;
196 : : }
197 : :
198 : : /* Compare LHS.key to RHS.key, for use with vec.bsearch. */
199 : : int
200 : 96955 : xpair_cmp (const void *lhs, const void *rhs)
201 : : {
202 : 96955 : return ((const xpair*)lhs)->key - ((const xpair*)rhs)->key;
203 : : }
204 : :
205 : : /* Get a pointer to the element at KEY if it exists, otherwise NULL. */
206 : : const xpair*
207 : 40693816 : trie_node::get (int key) const
208 : : {
209 : 40693816 : if (!heaped)
210 : : {
211 : 40667151 : if (len == 0) return NULL;
212 : 40653825 : if (len >= 1 && key == near[0].key) return near + 0;
213 : 6681275 : if (len >= 2 && key == near[1].key) return near + 1;
214 : : return NULL;
215 : : }
216 : : else
217 : : {
218 : 26665 : xpair kv;
219 : 26665 : kv.key = key;
220 : 53330 : return const_cast <vec<xpair>&> (far).bsearch (&kv, xpair_cmp);
221 : : }
222 : : }
223 : :
224 : : /* Put ("emplace") VAL at KEY, extending the paths that pass through this
225 : : vertex. This function assumes that KEY is not already a successor, and does
226 : : not perform this check. get () should be called and checked for NULL putting
227 : : with this function. Put maintains the order of the successors. */
228 : : void
229 : 3819033 : trie_node::put (int key, unsigned val)
230 : : {
231 : 3819033 : xpair kv;
232 : 3819033 : kv.key = key;
233 : 3819033 : kv.val = val;
234 : 3819033 : if (!heaped)
235 : : {
236 : 3811633 : const unsigned i = near_lower_bound (key);
237 : 3811633 : if (len < 2)
238 : : {
239 : 3810360 : near[1] = near[0];
240 : 3810360 : near[i] = kv;
241 : 3810360 : len += 1;
242 : : }
243 : : else
244 : : {
245 : : /* This insert is the 3rd element, which does not fit in the embedded
246 : : storage, so we must create a vector and convert to a far node. */
247 : 1273 : vec<xpair> xs {};
248 : 1273 : xs.reserve (13);
249 : 1273 : xs.quick_grow (3);
250 : 1273 : gcc_checking_assert (i <= 2);
251 : 1273 : if (i == 0)
252 : : {
253 : 157 : xs[0] = kv;
254 : 157 : xs[1] = near[0];
255 : 157 : xs[2] = near[1];
256 : : }
257 : 1116 : else if (i == 1)
258 : : {
259 : 129 : xs[0] = near[0];
260 : 129 : xs[1] = kv;
261 : 129 : xs[2] = near[1];
262 : : }
263 : : else
264 : : {
265 : 987 : xs[0] = near[0];
266 : 987 : xs[1] = near[1];
267 : 987 : xs[2] = kv;
268 : : }
269 : :
270 : 1273 : far = xs;
271 : 1273 : heaped = 1;
272 : : }
273 : : }
274 : : else
275 : : {
276 : 7400 : const unsigned i = far.lower_bound (kv, xpair_less);
277 : 7400 : far.safe_insert (i, kv);
278 : : }
279 : 3819033 : }
280 : :
281 : : /* Get the index to the last element that compares less than KEY, similar to
282 : : vec.lower_bound. This assumes the near vector is active, and is for internal
283 : : use. */
284 : : unsigned
285 : 3811633 : trie_node::near_lower_bound (int key) const
286 : : {
287 : 3811633 : gcc_checking_assert (!heaped);
288 : 3811633 : if (len == 0) return 0;
289 : 759882 : if (len >= 1 && key < near[0].key) return 0;
290 : 755469 : if (len >= 2 && key < near[1].key) return 1;
291 : 755340 : return len;
292 : : }
293 : :
294 : : /* The trie is a major workhorse for this algorithm. It has two key properties
295 : : - set-like subpath elimination and sorted output.
296 : :
297 : : Many evaluated paths will be non-prime, that is, a sequence of vertices that
298 : : is also fully embedded in a longer sequence of vertices. For example the
299 : : path [3 4 5 8] is a subpath of both [2 3 4 5 8] and [3 4 5 8 10]. The
300 : : insert_with_suffix function maintains this property so that inserting a
301 : : subpath into the trie is effectively a no-op, and inserting a superpath will
302 : : effectively remove (unmark) the subpath. Sometimes it can be guaranteed that
303 : : no redundant (subpaths) will be generated, in which case the insert function
304 : : can be used. The insert function is really only set insert, only becoming a
305 : : no-op for identical paths, which will be a lot faster.
306 : :
307 : : Paths can be extracted with an iterator, which will output paths in
308 : : lexicographically sorted order. This is an important property because the
309 : : index of a path in the sorted set will be used by the coverage to record when
310 : : a path is taken and completed. The iterator has different behavior than the
311 : : standard C++ iterators, and to avoid mixups the interface is deliberately
312 : : different. The iterator has a (large) stack which is not cheap to copy, and
313 : : if the stack is shallow copied it would mean iterator copies have non-local
314 : : effects. */
315 : : struct trie
316 : : {
317 : : struct iter;
318 : : trie ();
319 : : trie (const trie &o);
320 : : trie (trie &&o);
321 : : ~trie ();
322 : :
323 : : bool insert (const vec<int>&);
324 : : bool insert (const array_slice<const int>);
325 : : bool hard_insert (const array_slice<const int>);
326 : : bool insert_with_suffix (const array_slice<const int>);
327 : : bool insert_suffix (const array_slice<const int>);
328 : :
329 : : void merge (const trie&);
330 : :
331 : : iter paths (vec<int>&) const;
332 : : iter paths (vec<int>&, int from) const;
333 : :
334 : : vec<vec<int>> paths () const;
335 : :
336 : 3798249 : size_t size () const { return len; }
337 : :
338 : : vec<trie_node> vertices;
339 : : size_t len;
340 : :
341 : : /* An iterator for the paths of the trie. The iterator yields all paths in
342 : : lexicographical order. The iterator will be invalidated on any insertion
343 : : into the trie. The iterator should not be constructed directly, but
344 : : through the paths functions on the trie. It is essentially an explicit
345 : : stack depth-first traversal.
346 : :
347 : : The iter fills a user-provided buffer which should only be read as a when
348 : : the iter is active. Whenever next returns true the buffer is filled with
349 : : the current path. Uses will generally look like this:
350 : :
351 : : vec<int> path {};
352 : : auto iter = trie.paths (path);
353 : : while (iter.next ())
354 : : use_path (path);
355 : : */
356 : : struct iter
357 : : {
358 : : iter (vec<int>&, const vec<trie_node>&);
359 : : iter (int first, vec<int>& path, const vec<trie_node> &vertices);
360 : 19815 : ~iter ()
361 : 14119 : { stack.release (); }
362 : :
363 : : bool next ();
364 : : bool next (int);
365 : : bool next (bool);
366 : :
367 : :
368 : : /* This is the analog of the stack frame when implementing a recursive
369 : : depth-first path traversal and collecting paths to the leafs:
370 : :
371 : : for (auto successor : vertex[ix])
372 : : {
373 : : path.push (successor.value);
374 : : collect (successor.ix, successor.begin, successor.end, path)
375 : : path.pop ();
376 : : }
377 : :
378 : : Using size_t + 2x unsigned helped make the frame more compact and faster
379 : : than pointers. */
380 : : struct frame
381 : : {
382 : : /* The index of this frame's vertex, so that vertices[ix]. */
383 : : size_t ix;
384 : : /* The index of the current active successor of vertices[ix]. */
385 : : unsigned itr;
386 : : /* The end of vertices[ix] successors. When itr == end, vertex[ix] is
387 : : exhausted. */
388 : : unsigned end;
389 : : };
390 : :
391 : : /* User provided buffer to fill with the paths. */
392 : : vec<int> &path;
393 : : /* Direct reference to the trie vertices vector. */
394 : : const vec<trie_node> &vertices;
395 : : /* The call stack. */
396 : : vec<frame> stack;
397 : : /* Yield flag. If this is true then next () is permitted to and return a
398 : : new value. If this is false, a value has already been yielded and next
399 : : must first reset the state before building the next value. */
400 : : bool yield = true;
401 : :
402 : : iter (const iter& o) : path (o.path), vertices (o.vertices),
403 : : stack (o.stack.copy ()), yield (o.yield)
404 : : {
405 : : }
406 : :
407 : : /* Delete the copy assignment as the iter stores references and would cause
408 : : bad bugs. It is not necessary for the iterator to work well. To support
409 : : these the references would need to be (explicit) pointers. */
410 : : iter& operator = (const iter& o) = delete;
411 : : };
412 : : };
413 : :
414 : : /* Construct an iterator filling BUFFER. */
415 : : trie::iter
416 : 19596 : trie::paths (vec<int> &buffer) const
417 : : {
418 : 0 : buffer.truncate (0);
419 : 0 : return iter (buffer, vertices);
420 : : }
421 : :
422 : : /* Construct an iterator filling BUFFER for paths starting at FROM. */
423 : : trie::iter
424 : 219 : trie::paths (vec<int>& buffer, int from) const
425 : : {
426 : 0 : buffer.truncate (0);
427 : 0 : return iter (from, buffer, vertices);
428 : : }
429 : :
430 : : /* Default construct a new trie. */
431 : 18663 : trie::trie () : vertices (vec<trie_node> {}), len (0)
432 : : {
433 : 18663 : vertices.safe_push (trie_node {});
434 : 18663 : vertices[0].inserted = true;
435 : 18663 : }
436 : :
437 : : /* Copy construct a new trie. */
438 : 0 : trie::trie (const trie &o) : vertices (o.vertices.copy ()), len (o.len)
439 : : {
440 : 0 : }
441 : :
442 : : /* Move construct a new trie. */
443 : 0 : trie::trie (trie &&o) : vertices (o.vertices), len (o.len)
444 : : {
445 : 0 : o.vertices = {};
446 : 0 : o.len = 0;
447 : 0 : }
448 : :
449 : : /* Destroy a trie and release all the heaped resources. */
450 : 18663 : trie::~trie ()
451 : : {
452 : 3893685 : for (trie_node &v : vertices)
453 : 3837696 : if (v.heaped)
454 : 1273 : v.far.release ();
455 : 18663 : vertices.release ();
456 : 18663 : }
457 : :
458 : : /* Insert PATH into the trie. */
459 : : bool
460 : 759864 : trie::insert (const vec<int>& path)
461 : : {
462 : 1519728 : return insert (array_slice <const int> (path));
463 : : }
464 : :
465 : : /* Insert the PATH into the trie. Duplicate entries will not be entered twice.
466 : : If PATH is a subpath of another path this will not be detected or if there is
467 : : a path previously inserted that is a subpath of PATH then this redundancy
468 : : will not be eliminated. For that behavior, call insert_with_suffix. */
469 : : bool
470 : 771784 : trie::insert (array_slice<const int> path)
471 : : {
472 : 771784 : size_t index = 0;
473 : 771784 : size_t partition = 0;
474 : 40648461 : for (const int v : path)
475 : : {
476 : 40641679 : trie_node ¤t = vertices[index];
477 : 40641679 : current.inserted = true;
478 : 40641679 : partition++;
479 : :
480 : 40641679 : const auto *xp = current.get (v);
481 : 40641679 : if (xp)
482 : : {
483 : 39876677 : index = xp->val;
484 : : }
485 : : else
486 : : {
487 : : /* A new vertex on this path has been created, which means the rest of
488 : : the path will also have to be created. Drain the path and create
489 : : the remaining vertices in a single operation. */
490 : 765002 : unsigned ix = vertices.length ();
491 : 765002 : current.put (v, ix);
492 : 765002 : current.endofpath = false;
493 : :
494 : 765002 : array_slice<const int> tail (path.begin () + partition,
495 : 765002 : path.size () - partition);
496 : 765002 : vertices.safe_grow_cleared (1 + ix + tail.size ());
497 : :
498 : 3783151 : for (const int v : tail)
499 : : {
500 : 3018149 : trie_node &last = vertices[ix];
501 : 3018149 : ix += 1;
502 : 3018149 : last.put (v, ix);
503 : 3018149 : last.inserted = true;
504 : : }
505 : :
506 : 765002 : vertices.last ().endofpath = true;
507 : 765002 : vertices.last ().inserted = true;
508 : 765002 : len += 1;
509 : 765002 : return true;
510 : : }
511 : : }
512 : :
513 : : return false;
514 : : }
515 : :
516 : : /* hard_insert is like insert, except it does not overwrite any endofpath flags,
517 : : and records the endofpath flag even when a superpath of PATH has been
518 : : inserted previously. This effectively disables subpath elimination. */
519 : : bool
520 : 5394 : trie::hard_insert (array_slice<const int> path)
521 : : {
522 : 5394 : size_t index = 0;
523 : 5394 : size_t partition = 0;
524 : 5909 : for (const int v : path)
525 : : {
526 : 5773 : trie_node ¤t = vertices[index];
527 : 5773 : current.inserted = true;
528 : 5773 : partition++;
529 : :
530 : 5773 : const auto *xp = current.get (v);
531 : 5773 : if (xp)
532 : : {
533 : 515 : index = xp->val;
534 : : }
535 : : else
536 : : {
537 : 5258 : unsigned ix = vertices.length ();
538 : 5258 : current.put (v, ix);
539 : :
540 : 5258 : array_slice<const int> tail (path.begin () + partition,
541 : 5258 : path.size () - partition);
542 : 5258 : vertices.safe_grow_cleared (1 + ix + tail.size ());
543 : :
544 : 5868 : for (const int v : tail)
545 : : {
546 : 610 : trie_node &last = vertices[ix];
547 : 610 : ix += 1;
548 : 610 : last.put (v, ix);
549 : 610 : last.inserted = true;
550 : : }
551 : :
552 : 5258 : vertices.last ().endofpath = true;
553 : 5258 : vertices.last ().inserted = true;
554 : 5258 : len += 1;
555 : 5258 : return true;
556 : : }
557 : : }
558 : :
559 : 136 : vertices[index].endofpath = true;
560 : 136 : return false;
561 : : }
562 : :
563 : : /* Insert a suffixes of PATH. This is identical to insert except that it is
564 : : assumed that PATH is a subpath, and that the inserted path should clear the
565 : : inserted and endofpath flags. This function should only be called by
566 : : insert_with_suffix. */
567 : : bool
568 : 13712 : trie::insert_suffix (array_slice<const int> path)
569 : : {
570 : 13712 : size_t index = 0;
571 : 13712 : size_t partition = 0;
572 : 48925 : for (const int v : path)
573 : : {
574 : 45561 : trie_node ¤t = vertices[index];
575 : 45561 : current.endofpath = false;
576 : 45561 : partition++;
577 : :
578 : 45561 : const auto *xp = current.get (v);
579 : 45561 : if (xp)
580 : : {
581 : 35213 : index = xp->val;
582 : : }
583 : : else
584 : : {
585 : : /* A new vertex on this path has been created, which means the rest of
586 : : the path will also have to be created. Drain the path and create
587 : : the remaining vertices in a single operation. */
588 : 10348 : unsigned ix = vertices.length ();
589 : 10348 : current.put (v, ix);
590 : :
591 : 10348 : array_slice<const int> tail (path.begin () + partition,
592 : 10348 : path.size () - partition);
593 : 10348 : vertices.safe_grow_cleared (1 + ix + tail.size ());
594 : :
595 : 30014 : for (const int v : tail)
596 : : {
597 : 19666 : vertices[ix].put (v, ix + 1);
598 : 19666 : ix += 1;
599 : : }
600 : :
601 : 10348 : return true;
602 : : }
603 : : }
604 : :
605 : 3364 : vertices[index].endofpath = false;
606 : 3364 : return false;
607 : : }
608 : :
609 : : /* Insert the paths from OTHER into this trie. */
610 : : void
611 : 1136 : trie::merge (const trie& other)
612 : : {
613 : 1136 : auto_vec<int, 32> p {};
614 : 1136 : iter itr = other.paths (p);
615 : 1428 : while (itr.next ())
616 : 584 : insert_with_suffix (p);
617 : 1136 : }
618 : :
619 : : /* Insert PATH and all its subpaths into the trie. This function implements the
620 : : redundancy property of the trie - if an inserted path is either a subpath or
621 : : superpath of some other path then only the longest will keep its inserted
622 : : flag. */
623 : : bool
624 : 10897 : trie::insert_with_suffix (array_slice<const int> path)
625 : : {
626 : 10897 : bool inserted = insert (path);
627 : 10897 : path = array_slice<const int> (path.begin () + 1, path.size () - 1);
628 : 24609 : while (inserted && !path.empty ())
629 : : {
630 : 13712 : inserted = insert_suffix (path);
631 : 13712 : path = array_slice<const int> (path.begin () + 1, path.size () - 1);
632 : : }
633 : 10897 : return inserted;
634 : : }
635 : :
636 : : /* Convert the paths of a trie to a vec-of-vec. */
637 : : vec<vec<int>>
638 : 5668 : trie::paths () const
639 : : {
640 : 5668 : auto_vec<int> path {};
641 : 5668 : vec<vec<int>> all {};
642 : 5668 : auto iter = paths (path);
643 : 16659 : while (iter.next ())
644 : 10991 : all.safe_push (path.copy ());
645 : 5668 : return all;
646 : 5668 : }
647 : :
648 : : /* Create an iterator over VERTICES with the caller-provided buffer PATH. */
649 : 19596 : trie::iter::iter (vec<int> &path, const vec<trie_node> &vertices) : path (path),
650 : 19596 : vertices (vertices), stack (vec<frame> {})
651 : : {
652 : 19596 : gcc_checking_assert (!vertices.is_empty ());
653 : 19596 : stack.reserve (13);
654 : 19596 : frame f;
655 : 19596 : f.ix = 0;
656 : 19596 : f.itr = 0;
657 : 19596 : f.end = vertices[0].length ();
658 : 19596 : stack.quick_push (f);
659 : 19596 : }
660 : :
661 : : /* Create an iterator over VERTICES with the caller-provided buffer PATH for all
662 : : paths and subpaths (suffixes) starting in FROM. Note that FROM will not be
663 : : in the output buffer PATH, mainly because non-rooted paths are used when
664 : : splicing with paths that end in FROM. */
665 : 219 : trie::iter::iter (int from, vec<int> &path, const vec<trie_node> &vertices) :
666 : 219 : path (path), vertices (vertices), stack (vec<frame> {})
667 : : {
668 : 219 : gcc_checking_assert (!vertices.is_empty ());
669 : 219 : stack.reserve (13);
670 : :
671 : 219 : auto *xp = vertices[0].get (from);
672 : 219 : if (!xp)
673 : : {
674 : : /* No paths start with FROM, so construct an iterator where next () always
675 : : returns false. */
676 : 0 : frame f;
677 : 0 : f.ix = 0;
678 : 0 : f.itr = 0;
679 : 0 : f.end = 0;
680 : 0 : stack.safe_push (f);
681 : 0 : return;
682 : : }
683 : :
684 : 219 : frame f;
685 : 219 : f.ix = xp->val;
686 : 219 : f.itr = 0;
687 : 219 : f.end = vertices[f.ix].length ();
688 : 219 : stack.safe_push (f);
689 : : }
690 : :
691 : : /* Find the next complete prime path in the trie and write it to the caller's
692 : : buffer. Returns true if a path is written and false if the iterator is
693 : : exhausted, in which case no path is written and the contents of the buffer is
694 : : garbage. */
695 : : bool
696 : 39878 : trie::iter::next ()
697 : : {
698 : 133306 : while (true)
699 : : {
700 : 133306 : frame &top = stack.last ();
701 : 133306 : const trie_node &vertex = vertices[top.ix];
702 : :
703 : 41288 : if (vertex.endofpath && yield
704 : 174594 : && (top.itr != top.end || vertex.length () == 0))
705 : : {
706 : 20610 : yield = false;
707 : 20610 : return true;
708 : : }
709 : :
710 : 112696 : yield = true;
711 : :
712 : 112696 : if (top.itr != top.end)
713 : : {
714 : 49337 : const xpair succ = vertex.at (top.itr);
715 : 49337 : const trie_node &next = vertices[succ.val];
716 : 49337 : top.itr++;
717 : :
718 : 49337 : if (!next.inserted)
719 : 5246 : continue;
720 : :
721 : 44091 : frame f {};
722 : 44091 : f.ix = succ.val;
723 : 44091 : f.itr = 0;
724 : 44091 : f.end = next.length ();
725 : 44091 : path.safe_push (succ.key);
726 : 44091 : stack.safe_push (f);
727 : : }
728 : : else
729 : : {
730 : 63359 : stack.pop ();
731 : 63359 : if (stack.is_empty ())
732 : : return false;
733 : 44091 : path.pop ();
734 : : }
735 : : }
736 : : }
737 : :
738 : : /* Find the next path in the trie that would continue (but does not include)
739 : : LIMIT. If the trie contains the paths [2 4 6 8 9] [2 4 6 8 10] and [2 4 5
740 : : 8], iter.next (8) would yield [2 4 6] and [2 4 5]. Returns true if a path is
741 : : written and false if the iterator is exhausted, in which case no path is
742 : : written and the contents of the buffer is garbage. */
743 : : bool
744 : 1148 : trie::iter::next (int limit)
745 : : {
746 : 6726 : while (true)
747 : : {
748 : 6726 : frame &top = stack.last ();
749 : 6726 : const trie_node &vertex = vertices[top.ix];
750 : :
751 : 6726 : if (yield && top.itr != top.end)
752 : : {
753 : 3935 : const xpair succ = vertex.at (top.itr);
754 : 3935 : const trie_node &next = vertices[succ.val];
755 : 3935 : const int key = succ.key;
756 : 3935 : const int val = succ.val;
757 : 3935 : top.itr++;
758 : :
759 : 3935 : if (!next.inserted)
760 : 652 : continue;
761 : :
762 : 3307 : if (key == limit)
763 : : {
764 : 844 : if (path.is_empty ())
765 : 24 : continue;
766 : 820 : yield = false;
767 : 820 : return true;
768 : : }
769 : :
770 : 2463 : frame f {};
771 : 2463 : f.ix = val;
772 : 2463 : f.itr = 0;
773 : 2463 : f.end = next.length ();
774 : 2463 : path.safe_push (key);
775 : 2463 : stack.safe_push (f);
776 : 2463 : }
777 : : else
778 : : {
779 : 2791 : yield = true;
780 : 2791 : stack.pop ();
781 : 2791 : if (stack.is_empty ())
782 : : return false;
783 : 2463 : path.pop ();
784 : : }
785 : : }
786 : : }
787 : :
788 : : /* Find the next path in among all paths including subpaths/suffixes. This is
789 : : mainly useful in combination with trie.paths (from) for finding the paths
790 : : that go through some vertex. */
791 : : bool
792 : 534 : trie::iter::next (bool)
793 : : {
794 : 1956 : while (true)
795 : : {
796 : 1956 : frame &top = stack.last ();
797 : 1956 : const trie_node &vertex = vertices[top.ix];
798 : :
799 : 3597 : if (yield && vertex.length () == 0)
800 : : {
801 : 315 : yield = false;
802 : 315 : return true;
803 : : }
804 : :
805 : 1641 : yield = true;
806 : :
807 : 1641 : if (top.itr != top.end)
808 : : {
809 : 711 : const xpair succ = vertex.at (top.itr);
810 : 711 : const trie_node &next = vertices[succ.val];
811 : 711 : top.itr++;
812 : :
813 : 711 : frame f {};
814 : 711 : f.ix = succ.val;
815 : 711 : f.itr = 0;
816 : 711 : f.end = next.length ();
817 : 711 : path.safe_push (succ.key);
818 : 711 : stack.safe_push (f);
819 : : }
820 : : else
821 : : {
822 : 930 : stack.pop ();
823 : 930 : if (stack.is_empty ())
824 : : return false;
825 : 711 : path.pop ();
826 : : }
827 : : }
828 : : }
829 : :
830 : : /* Return the index of NEEDLE in HAYSTACK, or (size_t)-1 if not found. */
831 : : template <typename T>
832 : : size_t
833 : 13030 : index_of (T needle, const vec <T> &haystack)
834 : : {
835 : 13030 : size_t len = haystack.length ();
836 : 20869 : for (size_t i = 0; i != len; ++i)
837 : 20653 : if (haystack[i] == needle)
838 : : return i;
839 : : return (size_t)-1;
840 : : }
841 : :
842 : : /* Check if there is an edge in GRAPH from SRC to DST. */
843 : : bool
844 : 5753 : edge_p (const struct graph *graph, int src, int dest)
845 : : {
846 : 50432 : for (struct graph_edge *e = graph->vertices[src].succ; e; e = e->succ_next)
847 : 44878 : if (e->dest == dest)
848 : : return true;
849 : : return false;
850 : : }
851 : :
852 : : /* Check if PATH is a cycle starting (and ending) with V. */
853 : : bool
854 : 12226 : cycle_p (const vec<int>& path, int v)
855 : : {
856 : 12226 : return path[0] == v && path[path.length ()-1] == v;
857 : : }
858 : :
859 : : /* Find the SCC entry-exit paths, the simple paths from ENTRY to EXIT, and add
860 : : them to OUT. PRIME_PATHS is the prime paths of the SCC. Paths are hard
861 : : inserted into OUT, which disables subpath eliminiation and essentially makes
862 : : OUT a compact set. This is important to not eliminate paths from ENTRY to
863 : : EXIT which are traversed by other ENTRY/EXIT pairs. Duplicated entries are
864 : : removed. */
865 : : void
866 : 5087 : scc_entry_exit_paths (const vec<vec<int>> &internal_pp, int entry, int exit,
867 : : trie &out)
868 : : {
869 : 5087 : if (entry == exit)
870 : : {
871 : 5019 : out.hard_insert (array_slice <const int> (&entry, 1));
872 : 5019 : return;
873 : : }
874 : :
875 : 544 : for (const vec<int> &path : internal_pp)
876 : : {
877 : 340 : const size_t Ven = index_of (entry, path);
878 : 340 : const size_t Vex = index_of (exit, path);
879 : :
880 : 340 : if (Ven == (size_t)-1 || Vex == (size_t)-1 || Vex <= Ven)
881 : 192 : continue;
882 : :
883 : 148 : const size_t len = (Vex + 1) - Ven;
884 : 296 : array_slice <const int> p (path.begin () + Ven, len);
885 : 148 : out.hard_insert (p);
886 : : }
887 : : }
888 : :
889 : : /* Find the SCC exit paths, the simple paths that starts in a non-entry vertex
890 : : in the SCC and ends in EXIT and are not a cycles. INTERNAL_PP are the
891 : : internal prime paths for the SCC with EXIT as an exit vertex.
892 : :
893 : : Fazli claims the path must not be a subpath of another exit path in the SCC,
894 : : but this is only half true: see gcov-29.c/pathcov005a. Subpaths must survive
895 : : if they end in a different exit vertex than the superpath, so the hard_insert
896 : : is important. */
897 : : void
898 : 5083 : scc_exit_paths (const vec<vec<int>> &prime_paths, int exit, trie &out)
899 : : {
900 : 5083 : trie trie;
901 : 21508 : for (const vec<int> &path : prime_paths)
902 : : {
903 : 6259 : const size_t Vex = index_of (exit, path);
904 : 6259 : if (Vex == (size_t)-1 || cycle_p (path, exit))
905 : 5224 : continue;
906 : 2070 : array_slice <const int> p (path.begin (), Vex + 1);
907 : 1035 : trie.insert_with_suffix (p);
908 : : }
909 : :
910 : 5083 : auto_vec<int> path {};
911 : 5083 : auto iter = trie.paths (path);
912 : 5302 : while (iter.next ())
913 : 438 : out.hard_insert (path);
914 : 5083 : }
915 : :
916 : : /* Find the SCC entry paths, the simple paths that start in the entry vertex
917 : : ENTRY and are not cycles. INTERNAL_PP are the internal prime paths for the
918 : : SCC with ENTRY as an entry vertex. The paths are inserted into OUT. */
919 : : void
920 : 5043 : scc_entry_paths (const vec<vec<int>> &internal_pp, int entry, trie &trie)
921 : : {
922 : 21220 : for (const vec<int> &path : internal_pp)
923 : : {
924 : 6091 : const size_t Ven = index_of (entry, path);
925 : 6091 : if (Ven == (size_t)-1 || cycle_p (path, entry))
926 : 5144 : continue;
927 : 2841 : array_slice <const int> p (path.begin () + Ven, path.length () - Ven);
928 : 947 : trie.insert (p);
929 : : }
930 : 5043 : }
931 : :
932 : : /* Worker for cfg_complete_prime_paths. ITR is the current id for the current
933 : : path. END is end of the path so that when ITR == END, the walk is completed.
934 : : EDGES is the matrix of edges where EDGES[src][dst] is set if there is an edge
935 : : from src to dest. PATH is the vertices that make up this walk so far. TRIE
936 : : is the output trie where paths are inserted. SCC_ENEX_PATHS are the
937 : : entry-exit paths found by the scc_entry_exit_paths function. */
938 : : void
939 : 15967 : cfg_complete_prime_paths1 (const int *itr, const int *end,
940 : : const sbitmap *edges,
941 : : const vec<vec<vec<int>>> &scc_enex_paths,
942 : : vec<int> &path, trie &trie)
943 : : {
944 : 15967 : if (itr == end)
945 : : {
946 : 6696 : trie.insert_with_suffix (path);
947 : 3348 : return;
948 : : }
949 : :
950 : 12619 : const unsigned pathlen = path.length ();
951 : 12619 : const sbitmap succs = edges[path.last ()];
952 : 50556 : for (const vec<int> &enex : scc_enex_paths[*itr])
953 : : {
954 : 12731 : if (!bitmap_bit_p (succs, enex[0]))
955 : 104 : continue;
956 : :
957 : 12627 : path.safe_splice (enex);
958 : 12627 : cfg_complete_prime_paths1 (itr + 1, end, edges, scc_enex_paths,
959 : : path, trie);
960 : 12627 : path.truncate (pathlen);
961 : 12627 : if (limit_exceed_p (trie.size ()))
962 : : return;
963 : : }
964 : : }
965 : :
966 : : /* Find the complete prime paths of the CFG, the prime paths that start in the
967 : : entry vertex and end in the exit vertex. */
968 : : trie
969 : 572 : cfg_complete_prime_paths (const sbitmap *edges,
970 : : const vec<trie> &scc_entry_exit_paths,
971 : : const trie &ccfg_prime_paths)
972 : : {
973 : 572 : trie trie;
974 : 572 : auto_vec<int, 16> path {};
975 : 572 : auto_vec<int, 16> cfgpp {};
976 : 572 : auto_vec_vec_vec scc_enex {};
977 : 572 : scc_enex.reserve (scc_entry_exit_paths.length ());
978 : :
979 : 11274 : for (size_t i = 0; i != scc_entry_exit_paths.length (); ++i)
980 : : {
981 : 5065 : scc_enex.quick_push (vec<vec<int>> {});
982 : 5065 : auto iter = scc_entry_exit_paths[i].paths (path);
983 : 10172 : while (iter.next ())
984 : 5107 : scc_enex[i].safe_push (path.copy ());
985 : 5065 : }
986 : :
987 : 572 : auto iter = ccfg_prime_paths.paths (cfgpp);
988 : 3918 : while (!limit_exceed_p (trie.size ()) && iter.next ())
989 : 13366 : for (const vec<int> &enex : scc_enex[cfgpp[0]])
990 : : {
991 : 3340 : path.truncate (0);
992 : 3340 : path.safe_splice (enex);
993 : 6680 : cfg_complete_prime_paths1 (cfgpp.begin () + 1, cfgpp.end (), edges,
994 : : scc_enex, path, trie);
995 : 3340 : if (limit_exceed_p (trie.size ()))
996 : : return trie;
997 : : }
998 : :
999 : : return trie;
1000 : 572 : }
1001 : :
1002 : : /* Find the SCC exit prime paths, the prime paths that start from a strongly
1003 : : connected component and end in the end vertex. SCCS is a vector where
1004 : : SCCS[i] = SCC (vertex_i) so that if vertex[2].component == 5 then SCCS[2] ==
1005 : : 5. SCC_EXIT_PATHS is the output of scc_exit_paths (). COMPLETE_PRIME_PATHS
1006 : : is the output of cfg_complete_prime_paths ().
1007 : :
1008 : : This function can suffer under path explosion and will terminate early if
1009 : : the number of inserts in COMPLETE_PRIME_PATHS exceeds approx_limit. */
1010 : : trie
1011 : 572 : scc_exit_prime_paths (const struct graph *cfg, const trie &scc_exit_paths,
1012 : : const trie &complete_prime_paths)
1013 : : {
1014 : 572 : trie trie;
1015 : 572 : auto_vec<int, 8> path {};
1016 : 572 : auto_vec<int, 8> r {};
1017 : 572 : auto_vec<int, 8> q {};
1018 : :
1019 : 572 : auto exiter = scc_exit_paths.paths (q);
1020 : 791 : while (exiter.next ())
1021 : : {
1022 : 219 : const int Vex = q.last ();
1023 : 219 : auto iter = complete_prime_paths.paths (r, Vex);
1024 : 534 : while (iter.next (true))
1025 : : {
1026 : : /* There could be multiple Vex in the SCC. Even if scc_exit_paths
1027 : : did not kill the subpaths, this trie probably would. It can be
1028 : : assumed that all vertices in q are in the same SCC.
1029 : :
1030 : : This is an important note, as the Fazli and Afsharchi paper does
1031 : : not properly capture this subtlety. */
1032 : 315 : const int p0 = Vex;
1033 : 315 : const int p1 = r[0];
1034 : :
1035 : 315 : if (cfg->vertices[p0].component == cfg->vertices[p1].component)
1036 : 96 : continue;
1037 : :
1038 : 219 : path.truncate (0);
1039 : 438 : path.reserve (q.length () + r.length ());
1040 : 219 : path.splice (q);
1041 : 219 : path.splice (r);
1042 : : /* This can probably insert without subpath elimination because:
1043 : : 1. Conflicts are *really* rare (see patmatch in tree.c), but they
1044 : : do happen.
1045 : : 2. The output of this function is "filtered" through another trie
1046 : : anyway so the redundant paths generated here will be eliminated
1047 : : in the consumers at a very low extra cost. */
1048 : 219 : trie.insert (path);
1049 : 219 : if (limit_exceed_p (trie.size ()))
1050 : 0 : return trie;
1051 : : }
1052 : 219 : }
1053 : :
1054 : : return trie;
1055 : 572 : }
1056 : :
1057 : : /* Check if PATH in CFG enters the VERTEX's SCC through VERTEX. */
1058 : : bool
1059 : 820 : enters_through_p (const struct graph *cfg, const vec<int> &path, int vertex)
1060 : : {
1061 : 820 : gcc_checking_assert (!path.is_empty ());
1062 : 820 : const int last = path.address()[path.length ()-1];
1063 : 820 : if (cfg->vertices[last].component == cfg->vertices[vertex].component)
1064 : : return false;
1065 : 151 : return edge_p (cfg, last, vertex);
1066 : : }
1067 : :
1068 : : /* Worker for scc_entry_prime_paths. CFG is the CFG for the function,
1069 : : SCC_ENTRY_PATHS the accumulated scc_entry_paths for all the SCCs, PRIME_PATHS
1070 : : is either the result of cfg_complete_prime_paths or exit_prime_paths, and OUT
1071 : : the output trie.
1072 : :
1073 : : This function can suffer under path explosion and will terminate early if
1074 : : the number of inserts in OUT exceeds approx_limit. */
1075 : : void
1076 : 1144 : scc_entry_prime_paths1 (const struct graph *cfg, const trie &scc_entry_paths,
1077 : : const trie &prime_paths, trie &out)
1078 : : {
1079 : 1144 : auto_vec<int, 8> p {};
1080 : 1144 : auto_vec<int, 8> q {};
1081 : 1144 : auto_vec<int, 8> path {};
1082 : 1144 : auto itr = scc_entry_paths.paths (q);
1083 : 1472 : while (itr.next ())
1084 : : {
1085 : 328 : const int Ven = q[0];
1086 : : /* TODO: This might benefit from a reversed trie lookup. */
1087 : 328 : auto xitr = prime_paths.paths (p);
1088 : 1148 : while (xitr.next (Ven))
1089 : : {
1090 : 820 : if (!enters_through_p (cfg, p, Ven))
1091 : 669 : continue;
1092 : :
1093 : 151 : path.truncate (0);
1094 : 453 : path.reserve (p.length () + q.length ());
1095 : 151 : path.splice (p);
1096 : 151 : path.splice (q);
1097 : 302 : out.insert_with_suffix (path);
1098 : 151 : if (limit_exceed_p (out.size ()))
1099 : 0 : return;
1100 : : }
1101 : 328 : }
1102 : 1144 : }
1103 : :
1104 : : /* Find the entry prime paths - the prime paths that start in the root and end
1105 : : in a strongly connected component. CFG is the CFG for this function,
1106 : : SCC_ENTRY_PATHS the accumulated scc_entry_paths for all the SCCs,
1107 : : COMPLETE_PRIME_PATHS the result of cfg_complete_prime_paths, and
1108 : : EXIT_PRIME_PATHS result of exit_prime_paths.
1109 : :
1110 : : This function can suffer under path explosion and will terminate early if
1111 : : the return value grows beyond approx_limit. */
1112 : : trie
1113 : 572 : scc_entry_prime_paths (const struct graph *cfg,
1114 : : const trie &scc_entry_paths,
1115 : : const trie &complete_prime_paths,
1116 : : const trie &exit_prime_paths)
1117 : : {
1118 : 572 : trie trie;
1119 : 572 : scc_entry_prime_paths1 (cfg, scc_entry_paths, complete_prime_paths, trie);
1120 : 572 : scc_entry_prime_paths1 (cfg, scc_entry_paths, exit_prime_paths, trie);
1121 : 572 : return trie;
1122 : : }
1123 : :
1124 : : /* Build a new control flow graph from the strongly connected components, so
1125 : : that every node in the CCFG is a strongly connected component in the original
1126 : : CFG. NSSC is the number of vertices in the new graph, and the return value
1127 : : of graphds_ssc. */
1128 : : struct graph*
1129 : 575 : build_ccfg (struct graph *cfg, int nscc)
1130 : : {
1131 : 575 : struct graph *ccfg = new_graph (nscc);
1132 : 6157 : for (int i = 0; i != cfg->n_vertices; ++i)
1133 : : {
1134 : 5582 : struct vertex v = cfg->vertices[i];
1135 : 11920 : for (struct graph_edge *e = v.succ; e; e = e->succ_next)
1136 : : {
1137 : 6338 : int src = v.component;
1138 : 6338 : int dest = cfg->vertices[e->dest].component;
1139 : 11916 : if (src != dest && !edge_p (ccfg, src, dest))
1140 : 5554 : add_edge (ccfg, src, dest);
1141 : : }
1142 : : }
1143 : :
1144 : 575 : return ccfg;
1145 : : }
1146 : :
1147 : : /* Create a new graph from CFG where the edges between strongly connected
1148 : : components removed. */
1149 : : struct graph*
1150 : 575 : disconnect_sccs (struct graph *cfg)
1151 : : {
1152 : 575 : struct graph *ccfg = new_graph (cfg->n_vertices);
1153 : 575 : const struct vertex *vertices = cfg->vertices;
1154 : 6157 : for (int i = 0; i != cfg->n_vertices; ++i)
1155 : : {
1156 : 5582 : ccfg->vertices[i].data = &cfg->vertices[i];
1157 : 11920 : for (struct graph_edge *e = vertices[i].succ; e; e = e->succ_next)
1158 : 6338 : if (vertices[e->src].component == vertices[e->dest].component)
1159 : 760 : add_edge (ccfg, e->src, e->dest)->data = e;
1160 : : }
1161 : 575 : return ccfg;
1162 : : }
1163 : :
1164 : : /* Check if vertex I in CFG is the entry vertex of a strongly connected
1165 : : component. A vertex is an entry vertex if 1) there are no predecessors
1166 : : (i.e. the root vertex is always an entry vertex) or 2) a predecessor belongs
1167 : : to a different SCC. */
1168 : : bool
1169 : 10664 : scc_entry_vertex_p (struct graph *cfg, size_t i)
1170 : : {
1171 : 10664 : if (!cfg->vertices[i].pred)
1172 : : return true;
1173 : 8234 : const int scc = cfg->vertices[i].component;
1174 : 9102 : for (struct graph_edge *e = cfg->vertices[i].pred; e; e = e->pred_next)
1175 : 8540 : if (cfg->vertices[e->src].component != scc)
1176 : : return true;
1177 : : return false;
1178 : : }
1179 : :
1180 : : /* Check if vertex I in CFG is an exit vertex of a strongly connected component.
1181 : : A vertex is an exit vertex if 1) there are no successors (i.e. the sink is
1182 : : always an exit vertex) or 2) if a successor belongs to a different SCC. */
1183 : : bool
1184 : 10672 : scc_exit_vertex_p (struct graph *cfg, size_t i)
1185 : : {
1186 : 10672 : if (!cfg->vertices[i].succ)
1187 : : return true;
1188 : 8124 : const int scc = cfg->vertices[i].component;
1189 : 8812 : for (struct graph_edge *e = cfg->vertices[i].succ; e; e = e->succ_next)
1190 : 8322 : if (cfg->vertices[e->dest].component != scc)
1191 : : return true;
1192 : : return false;
1193 : : }
1194 : :
1195 : : /* Worker for simple_paths. Find all the simple paths in CFG starting at NODE
1196 : : and insert into OUT. This is a DFS where the search stops when entering a
1197 : : vertex already in SEEN. PATH is the sequence of ids for the vertices taken
1198 : : from the from the root to NODE. When the number of inserts reaches LIMIT
1199 : : the function aborts and returns so the caller can report that it is giving
1200 : : up because the function is too complex.
1201 : :
1202 : : This function can suffer under path explosion and will terminate early if
1203 : : the number of inserts in OUT exceeds approx_limit. */
1204 : : void
1205 : 3769539 : simple_paths1 (const struct graph *cfg, int node, sbitmap seen, vec<int> &path,
1206 : : trie &out)
1207 : : {
1208 : 3769539 : if (limit_exceed_p (out.size ()))
1209 : : return;
1210 : :
1211 : 3769278 : if (!bitmap_set_bit (seen, node))
1212 : : {
1213 : 751367 : if (path[0] == node)
1214 : 750836 : path.quick_push (node);
1215 : 751367 : out.insert (path);
1216 : 751367 : if (path[0] == node)
1217 : 750836 : path.pop ();
1218 : 751367 : return;
1219 : : }
1220 : 3017911 : path.quick_push (node);
1221 : :
1222 : 3017911 : struct graph_edge *succs = cfg->vertices[node].succ;
1223 : 3017911 : if (!succs)
1224 : : {
1225 : 8278 : out.insert (path);
1226 : 8278 : bitmap_clear_bit (seen, node);
1227 : 8278 : path.pop ();
1228 : 8278 : return;
1229 : : }
1230 : :
1231 : 6772394 : for (struct graph_edge *e = succs; e; e = e->succ_next)
1232 : 3762761 : simple_paths1 (cfg, e->dest, seen, path, out);
1233 : :
1234 : 3009633 : bitmap_clear_bit (seen, node);
1235 : 3009633 : path.pop ();
1236 : : }
1237 : :
1238 : : /* Find all the simple paths in CFG starting at ROOT and insert into OUT. A
1239 : : simple path is a sequence of vertices without any duplicated vertices (i.e.
1240 : : no loops). SEEN should be an sbitmap of CFG->n_vertices size. PATH and
1241 : : SEEN will be cleared entry and is for buffer reuse between calls. When the
1242 : : number of inserts reaches LIMIT the function aborts and returns so the
1243 : : caller can report that it is giving up because the function is too complex.
1244 : : Note that there might be fewer prime paths than inserts, but if the number
1245 : : of inserts alone is larger than LIMIT the function is very complex and would
1246 : : take too long to compile in later stages.
1247 : :
1248 : : This function can suffer under path explosion and will terminate early if
1249 : : the number of inserts in OUT exceeds approx_limit. Since OUT is often
1250 : : shared between calls it is ok to use in a loop, and only check the size of
1251 : : OUT after the loop terminates. */
1252 : : void
1253 : 6778 : simple_paths (struct graph *cfg, int root, sbitmap seen, vec<int> &path,
1254 : : trie &out)
1255 : : {
1256 : 6778 : bitmap_clear (seen);
1257 : 6778 : path.reserve (cfg->n_vertices);
1258 : 6778 : path.truncate (0);
1259 : 6778 : simple_paths1 (cfg, root, seen, path, out);
1260 : 6778 : }
1261 : :
1262 : : /* Merge the tries T1, T2, T3, and set of paths VECS into the larges trie.
1263 : : Returns a reference to the trie merged into. Merging tries and resolving
1264 : : redundant paths is the slowest step (at least in the sense it works on the
1265 : : largest input), and merging into a partial result reduces the work
1266 : : accordingly. For large problems this is a massive improvement, which in the
1267 : : worst cases (where all tries but one are empty or almost empty) speed up
1268 : : 30-40%. */
1269 : : trie&
1270 : 568 : merge (trie &t1, trie &t2, trie &t3, vec<vec<vec<int>>> &vecs)
1271 : : {
1272 : 568 : trie *dst = nullptr;
1273 : 568 : const size_t s1 = t1.size ();
1274 : 568 : const size_t s2 = t2.size ();
1275 : 568 : const size_t s3 = t3.size ();
1276 : :
1277 : 568 : if (s1 >= s2 && s1 >= s3)
1278 : : {
1279 : 552 : dst = &t1;
1280 : 552 : t1.merge (t2);
1281 : 552 : t1.merge (t3);
1282 : : }
1283 : 16 : else if (s2 >= s1 && s2 >= s3)
1284 : : {
1285 : 10 : dst = &t2;
1286 : 10 : t2.merge (t1);
1287 : 10 : t2.merge (t3);
1288 : : }
1289 : : else
1290 : : {
1291 : 6 : dst = &t3;
1292 : 6 : t3.merge (t1);
1293 : 6 : t3.merge (t2);
1294 : : }
1295 : :
1296 : 568 : gcc_checking_assert (dst);
1297 : 6745 : for (const vec<vec<int>> &v2 : vecs)
1298 : 21138 : for (const vec<int> &v1 : v2)
1299 : 12030 : dst->insert_with_suffix (v1);
1300 : 568 : return *dst;
1301 : : }
1302 : :
1303 : : /* Store the edges of CFG in a matrix of bitmaps so that bit_p (edges[src],
1304 : : dest) is true if there is an edge from src to dest. This is faster and more
1305 : : convenient than walking the linked list of successors in hot loops. The
1306 : : vector will have N bitmaps of N bits where N is the number of vertices in
1307 : : CFG. */
1308 : : sbitmap*
1309 : 571 : edge_matrix (const struct graph *cfg)
1310 : : {
1311 : 571 : sbitmap *edges = sbitmap_vector_alloc (cfg->n_vertices, cfg->n_vertices);
1312 : 571 : bitmap_vector_clear (edges, cfg->n_vertices);
1313 : 6109 : for (int i = 0; i != cfg->n_vertices; ++i)
1314 : 11824 : for (graph_edge *e = cfg->vertices[i].succ; e; e = e->succ_next)
1315 : 6286 : bitmap_set_bit (edges[e->src], e->dest);
1316 : 571 : return edges;
1317 : : }
1318 : :
1319 : : } // namespace
1320 : :
1321 : : /* Find the prime paths for CFG. The search gives up after approximate
1322 : : PATHLIMIT probable paths have been generated to address path explosions.
1323 : : The PATHLIMIT flag is typically controlled by -fpath-coverage-limit. This
1324 : : function is a part of -fpath-coverage and will also be called from gcov.
1325 : : The paths are returned in lexicographical order based on node (basic block)
1326 : : ID. If the path limit was exceeded, an empty vector is returned.
1327 : :
1328 : : A simple path is a path where all vertices are unique, except possibly the
1329 : : first and last. A prime path is a maximal-length simple path which is not a
1330 : : part of any other simple path. Prime paths strike a good balance between
1331 : : coverage thoroughness, loops (requiring them to be taken and skipped), and
1332 : : number of paths.
1333 : :
1334 : : The algorithm is based on Fazli & Afsharchi's "A Time and Space-Efficient
1335 : : Compositional Method for Prime and Test Paths Generation" (2019), combined
1336 : : with a suffix trie for removing duplicate or redundant paths. An auxillary
1337 : : graph of the strongly connected components (SCCs) is built. Then, the prime
1338 : : paths of the SCCs composes the prime paths of each SCC with the prime paths
1339 : : of this auxillary graph. This can drastically cut the number of redundant
1340 : : paths generated compared to a naive algorithm.
1341 : :
1342 : : This does not work for all graphs. Some structures, e.g. when most of the
1343 : : graph is inside a single SCC, cause the algorithm to degenerate to a naive
1344 : : one. The same happens for functions with many SCCs that are either
1345 : : singletons or very small. Those cases will be slower with respect to the
1346 : : number of paths, but still fast enough if the path limit is kept reasonably
1347 : : low (a few hundred thousand). */
1348 : : vec<vec<int>>
1349 : 571 : prime_paths (struct graph *cfg, size_t pathlimit)
1350 : : {
1351 : 571 : const int nscc = graphds_scc (cfg, NULL);
1352 : 571 : auto_graph disconnected (disconnect_sccs (cfg));
1353 : 571 : auto_graph ccfg (build_ccfg (cfg, nscc));
1354 : 571 : auto_sbitmap_vector edges (edge_matrix (cfg));
1355 : :
1356 : 571 : auto_sbitmap seen (cfg->n_vertices);
1357 : 571 : auto_vec<int, 8> pathbuf {};
1358 : :
1359 : 571 : limit_reset (pathlimit);
1360 : :
1361 : : /* Store an SCC-ID -> vertices mapping to quickly find the vertices that
1362 : : make up a strongly connected component. */
1363 : 571 : auto_vec_vec sccs {};
1364 : 571 : sccs.safe_grow_cleared (ccfg->n_vertices);
1365 : 6109 : for (int i = 0; i != cfg->n_vertices; ++i)
1366 : 5538 : sccs[cfg->vertices[i].component].safe_push (i);
1367 : :
1368 : 571 : auto_vec_vec_vec scc_internal_pp {};
1369 : 571 : scc_internal_pp.safe_grow_cleared (nscc);
1370 : 5615 : for (int i = 0; i != nscc; ++i)
1371 : : {
1372 : 5047 : trie internal_pp;
1373 : 20652 : for (int V : sccs[i])
1374 : 5511 : simple_paths (disconnected, V, seen, pathbuf, internal_pp);
1375 : 5047 : if (limit_exceed_p (internal_pp.size ()))
1376 : 3 : return {};
1377 : 5044 : scc_internal_pp[i] = internal_pp.paths ();
1378 : 10088 : if (limit_checked_add (scc_internal_pp[i].length ()))
1379 : 0 : return {};
1380 : 5047 : }
1381 : :
1382 : 568 : auto_vec<trie, 8> scc_enex_paths (nscc);
1383 : 568 : scc_enex_paths.safe_grow_cleared (nscc);
1384 : 568 : trie scc_en_paths;
1385 : 568 : trie scc_ex_paths;
1386 : :
1387 : 5609 : for (int i = 0; i != ccfg->n_vertices; ++i)
1388 : : {
1389 : 20433 : for (int Ven : sccs[i])
1390 : : {
1391 : 5310 : if (!scc_entry_vertex_p (cfg, Ven))
1392 : 271 : continue;
1393 : :
1394 : 20435 : for (int Vex : sccs[i])
1395 : : {
1396 : 5318 : if (!scc_exit_vertex_p (cfg, Vex))
1397 : 239 : continue;
1398 : 5079 : scc_entry_exit_paths (scc_internal_pp[i], Ven, Vex,
1399 : : scc_enex_paths[i]);
1400 : : }
1401 : : }
1402 : : }
1403 : :
1404 : 5878 : for (int i = 0; i != cfg->n_vertices; ++i)
1405 : : {
1406 : 5310 : const int scc = cfg->vertices[i].component;
1407 : 5310 : if (scc_entry_vertex_p (cfg, i))
1408 : 5039 : scc_entry_paths (scc_internal_pp[scc], i, scc_en_paths);
1409 : :
1410 : 5310 : if (scc_exit_vertex_p (cfg, i))
1411 : 5075 : scc_exit_paths (scc_internal_pp[scc], i, scc_ex_paths);
1412 : : }
1413 : :
1414 : : /* In the presence of abnormal edges (like longjmp) it is possible to have
1415 : : multiple "entry points" in function -- build ccfg prime paths starting at
1416 : : any vertex without predecessor. For most graphs this will only be the
1417 : : ENTRY_BLOCK. */
1418 : 568 : trie ccfg_prime_paths;
1419 : 5609 : for (int i = 0; i != ccfg->n_vertices; ++i)
1420 : 5041 : if (!ccfg->vertices[i].pred)
1421 : 1219 : simple_paths (ccfg, i, seen, pathbuf, ccfg_prime_paths);
1422 : 568 : if (limit_exceed_p (ccfg_prime_paths.size ()))
1423 : 0 : return {};
1424 : :
1425 : 568 : trie complete_prime_paths = cfg_complete_prime_paths (edges, scc_enex_paths,
1426 : 568 : ccfg_prime_paths);
1427 : 568 : if (limit_checked_add (complete_prime_paths.size ()))
1428 : 0 : return {};
1429 : 568 : trie exit_prime_paths = scc_exit_prime_paths (cfg, scc_ex_paths,
1430 : 568 : complete_prime_paths);
1431 : 568 : if (limit_checked_add (exit_prime_paths.size ()))
1432 : 0 : return {};
1433 : 568 : trie entry_prime_paths = scc_entry_prime_paths (cfg, scc_en_paths,
1434 : : complete_prime_paths,
1435 : 568 : exit_prime_paths);
1436 : 568 : if (limit_checked_add (entry_prime_paths.size ()))
1437 : 0 : return {};
1438 : :
1439 : 568 : trie &merged = merge (complete_prime_paths, entry_prime_paths,
1440 : : exit_prime_paths, scc_internal_pp);
1441 : 568 : if (merged.size () > pathlimit)
1442 : 0 : return {};
1443 : :
1444 : 568 : return merged.paths ();
1445 : 571 : }
1446 : :
1447 : : #if CHECKING_P
1448 : :
1449 : : namespace selftest
1450 : : {
1451 : :
1452 : : /* Check if the trie contains PATH. */
1453 : : static bool
1454 : 108 : contains (const trie &trie, array_slice<const int> path)
1455 : : {
1456 : 108 : size_t index = 0;
1457 : 692 : for (int id : path)
1458 : : {
1459 : 584 : const trie_node ¤t = trie.vertices[index];
1460 : 584 : if (!current.inserted)
1461 : : return false;
1462 : 584 : const auto *xp = current.get (id);
1463 : 584 : if (!xp)
1464 : : return false;
1465 : 584 : index = xp->val;
1466 : : }
1467 : 108 : return trie.vertices[index].inserted && trie.vertices[index].endofpath;
1468 : : }
1469 : :
1470 : : static bool
1471 : 1320 : equal_p (array_slice<const int> lhs, array_slice<const int> rhs)
1472 : : {
1473 : 1320 : if (lhs.size () != rhs.size ())
1474 : : return false;
1475 : :
1476 : 600 : size_t length = lhs.size ();
1477 : 1420 : for (size_t i = 0; i != length; ++i)
1478 : 1252 : if (lhs[i] != rhs[i])
1479 : : return false;
1480 : : return true;
1481 : : }
1482 : :
1483 : : static bool
1484 : 168 : any_equal_p (const array_slice<const int> &needle,
1485 : : const vec<vec<int>> &haystack)
1486 : : {
1487 : 1656 : for (const vec<int> &x : haystack)
1488 : 2640 : if (equal_p (needle, array_slice <const int> (x)))
1489 : : return true;
1490 : : return false;
1491 : : }
1492 : :
1493 : : static size_t
1494 : 28 : count (const trie &trie)
1495 : : {
1496 : 28 : size_t n = 0;
1497 : 28 : auto_vec<int> path {};
1498 : 28 : auto iter = trie.paths (path);
1499 : 136 : while (iter.next ())
1500 : 108 : n += 1;
1501 : 28 : return n;
1502 : 28 : }
1503 : :
1504 : : static vec<vec<int>>
1505 : 48 : simple_paths (struct graph *cfg, trie &trie, int root = 0)
1506 : : {
1507 : 48 : auto_sbitmap seen (cfg->n_vertices);
1508 : 48 : auto_vec<int> path;
1509 : 48 : simple_paths (cfg, root, seen, path, trie);
1510 : 48 : return trie.paths ();
1511 : 48 : }
1512 : :
1513 : : /* Create a CFG that roughly corresponds to this program:
1514 : :
1515 : : int binary_search(int a[], int len, int from, int to, int key)
1516 : : {
1517 : : int low = from;
1518 : : int high = to - 1;
1519 : :
1520 : : while (low <= high)
1521 : : {
1522 : : int mid = (low + high) >> 1;
1523 : : long midVal = a[mid];
1524 : :
1525 : : if (midVal < key)
1526 : : low = mid + 1;
1527 : : else if (midVal > key)
1528 : : high = mid - 1;
1529 : : else
1530 : : return mid; // key found
1531 : : }
1532 : : return -1;
1533 : : }
1534 : :
1535 : : This program would emit a CFG very similar to the CFG used by Fazli &
1536 : : Afsharchi (2019). The selftest cases are built from the partial paths used
1537 : : in that paper. */
1538 : : static struct graph*
1539 : 24 : binary_search_cfg ()
1540 : : {
1541 : 24 : struct graph *g = new_graph (11);
1542 : 24 : add_edge (g, 0, 1);
1543 : 24 : add_edge (g, 1, 2);
1544 : 24 : add_edge (g, 2, 3);
1545 : 24 : add_edge (g, 2, 4);
1546 : 24 : add_edge (g, 3, 10);
1547 : 24 : add_edge (g, 4, 5);
1548 : 24 : add_edge (g, 4, 6);
1549 : 24 : add_edge (g, 5, 7);
1550 : 24 : add_edge (g, 6, 8);
1551 : 24 : add_edge (g, 6, 9);
1552 : 24 : add_edge (g, 7, 2);
1553 : 24 : add_edge (g, 8, 10);
1554 : 24 : add_edge (g, 9, 7);
1555 : 24 : graphds_scc (g, NULL);
1556 : 24 : return g;
1557 : : }
1558 : :
1559 : : /* Test a full run of the algorithm against a known graph (binary-search). */
1560 : : static void
1561 : 4 : test_prime_paths ()
1562 : : {
1563 : 4 : auto_graph g (binary_search_cfg ());
1564 : 4 : vec<vec<int>> paths = prime_paths (g, 100);
1565 : 4 : const int p01[] = { 0, 1, 2, 3, 10 };
1566 : 4 : const int p02[] = { 0, 1, 2, 4, 6, 8, 10 };
1567 : 4 : const int p03[] = { 5, 7, 2, 4, 6, 9 };
1568 : 4 : const int p04[] = { 4, 6, 9, 7, 2, 4 };
1569 : 4 : const int p05[] = { 2, 4, 6, 9, 7, 2 };
1570 : 4 : const int p06[] = { 6, 9, 7, 2, 4, 6 };
1571 : 4 : const int p07[] = { 9, 7, 2, 4, 6, 9 };
1572 : 4 : const int p08[] = { 7, 2, 4, 6, 9, 7 };
1573 : 4 : const int p09[] = { 6, 9, 7, 2, 4, 5 };
1574 : 4 : const int p10[] = { 4, 5, 7, 2, 4 };
1575 : 4 : const int p11[] = { 2, 4, 5, 7, 2 };
1576 : 4 : const int p12[] = { 5, 7, 2, 4, 5 };
1577 : 4 : const int p13[] = { 7, 2, 4, 5, 7 };
1578 : 4 : const int p14[] = { 4, 6, 9, 7, 2, 3, 10 };
1579 : 4 : const int p15[] = { 5, 7, 2, 4, 6, 8, 10 };
1580 : 4 : const int p16[] = { 9, 7, 2, 4, 6, 8, 10 };
1581 : 4 : const int p17[] = { 4, 5, 7, 2, 3, 10 };
1582 : 4 : const int p18[] = { 0, 1, 2, 4, 6, 9, 7 };
1583 : 4 : const int p19[] = { 0, 1, 2, 4, 5, 7 };
1584 : :
1585 : 4 : ASSERT_EQ (paths.length (), 19);
1586 : 4 : ASSERT_TRUE (any_equal_p (p01, paths));
1587 : 4 : ASSERT_TRUE (any_equal_p (p02, paths));
1588 : 4 : ASSERT_TRUE (any_equal_p (p03, paths));
1589 : 4 : ASSERT_TRUE (any_equal_p (p04, paths));
1590 : 4 : ASSERT_TRUE (any_equal_p (p05, paths));
1591 : 4 : ASSERT_TRUE (any_equal_p (p06, paths));
1592 : 4 : ASSERT_TRUE (any_equal_p (p07, paths));
1593 : 4 : ASSERT_TRUE (any_equal_p (p08, paths));
1594 : 4 : ASSERT_TRUE (any_equal_p (p09, paths));
1595 : 4 : ASSERT_TRUE (any_equal_p (p10, paths));
1596 : 4 : ASSERT_TRUE (any_equal_p (p11, paths));
1597 : 4 : ASSERT_TRUE (any_equal_p (p12, paths));
1598 : 4 : ASSERT_TRUE (any_equal_p (p13, paths));
1599 : 4 : ASSERT_TRUE (any_equal_p (p14, paths));
1600 : 4 : ASSERT_TRUE (any_equal_p (p15, paths));
1601 : 4 : ASSERT_TRUE (any_equal_p (p16, paths));
1602 : 4 : ASSERT_TRUE (any_equal_p (p17, paths));
1603 : 4 : ASSERT_TRUE (any_equal_p (p18, paths));
1604 : 4 : ASSERT_TRUE (any_equal_p (p19, paths));
1605 : 4 : release_vec_vec (paths);
1606 : 4 : }
1607 : :
1608 : : /* The strongly connected component graph for binary_search looks like
1609 : : this, using the vertex numbers from the original graph:
1610 : :
1611 : : START
1612 : : |
1613 : : 1
1614 : : |
1615 : : 2 (SCC)
1616 : : / \
1617 : : 3 8
1618 : : \ /
1619 : : END
1620 : :
1621 : : The components gets renumbered by graphds_scc, so the ccfg looks like
1622 : : this. The actual numbers don't matter as long as the structure of the
1623 : : graph is preserved, and this test is now sensitive to the numbering set
1624 : : by graphds_scc. It does not have to be - if that function should reverse
1625 : : the numbering this test must be updated.
1626 : :
1627 : : 5
1628 : : |
1629 : : 4
1630 : : |
1631 : : 3 (SCC)
1632 : : / \
1633 : : 2 1
1634 : : \ /
1635 : : 0
1636 : : */
1637 : : static void
1638 : 4 : test_build_ccfg ()
1639 : : {
1640 : 4 : auto_graph cfg (binary_search_cfg ());
1641 : 4 : const int nscc = graphds_scc (cfg, NULL);
1642 : 4 : auto_graph ccfg (build_ccfg (cfg, nscc));
1643 : 4 : ASSERT_EQ (6, nscc);
1644 : :
1645 : 8 : ASSERT_TRUE (edge_p (ccfg, 5, 4));
1646 : 8 : ASSERT_TRUE (edge_p (ccfg, 4, 3));
1647 : 8 : ASSERT_TRUE (edge_p (ccfg, 3, 2));
1648 : 8 : ASSERT_TRUE (edge_p (ccfg, 3, 1));
1649 : 8 : ASSERT_TRUE (edge_p (ccfg, 2, 0));
1650 : 8 : ASSERT_TRUE (edge_p (ccfg, 1, 0));
1651 : 4 : }
1652 : :
1653 : : /* This test checks some basic assumptions on finding the strongly connected
1654 : : components and disconnecting the graph by removing all edges between SCCs.
1655 : : Creating a single auxillary graph simplifies the bookkeeping. */
1656 : : static void
1657 : 4 : test_split_components ()
1658 : : {
1659 : 4 : auto_graph cfg (binary_search_cfg ());
1660 : 4 : int nscc = graphds_scc (cfg, NULL);
1661 : 4 : auto_graph ccfg (disconnect_sccs (cfg));
1662 : :
1663 : 4 : auto_vec_vec entries {};
1664 : 4 : auto_vec_vec exits {};
1665 : 4 : entries.safe_grow_cleared (nscc);
1666 : 4 : exits.safe_grow_cleared (nscc);
1667 : :
1668 : 48 : for (int i = 0; i != cfg->n_vertices; ++i)
1669 : : {
1670 : 44 : if (scc_entry_vertex_p (cfg, i))
1671 : 24 : entries[cfg->vertices[i].component].safe_push (i);
1672 : 44 : if (scc_exit_vertex_p (cfg, i))
1673 : 28 : exits[cfg->vertices[i].component].safe_push (i);
1674 : : }
1675 : :
1676 : 4 : const int p10[] = { 10 };
1677 : 4 : const int p08[] = { 8 };
1678 : 4 : const int p03[] = { 3 };
1679 : 4 : const int p02[] = { 2 };
1680 : 4 : const int p01[] = { 1 };
1681 : 4 : const int p00[] = { 0 };
1682 : 4 : const int p26[] = { 2, 6 };
1683 : :
1684 : 4 : ASSERT_EQ (entries.length (), 6);
1685 : 4 : ASSERT_TRUE (any_equal_p (p10, entries));
1686 : 4 : ASSERT_TRUE (any_equal_p (p08, entries));
1687 : 4 : ASSERT_TRUE (any_equal_p (p03, entries));
1688 : 4 : ASSERT_TRUE (any_equal_p (p02, entries));
1689 : 4 : ASSERT_TRUE (any_equal_p (p01, entries));
1690 : 4 : ASSERT_TRUE (any_equal_p (p00, entries));
1691 : :
1692 : 4 : ASSERT_EQ (exits.length (), 6);
1693 : 4 : ASSERT_TRUE (any_equal_p (p10, exits));
1694 : 4 : ASSERT_TRUE (any_equal_p (p08, exits));
1695 : 4 : ASSERT_TRUE (any_equal_p (p03, exits));
1696 : 4 : ASSERT_TRUE (any_equal_p (p26, exits));
1697 : 4 : ASSERT_TRUE (any_equal_p (p01, exits));
1698 : 4 : ASSERT_TRUE (any_equal_p (p00, exits));
1699 : :
1700 : : /* The result of disconnect_sccs () disconnects the graph into its strongly
1701 : : connected components. The subgraphs are either singletons (a single
1702 : : vertex with no edges) or graphs with cycles. The SCC internal prime
1703 : : paths can be found by running a DFS from every SCC vertex, terminating
1704 : : on a duplicated vertex. This may create some redundant paths still,
1705 : : which must be filtered out.
1706 : :
1707 : : Singletons can either be detected and skipped (requires counting the
1708 : : components) or filtered after. For this test case they are skipped
1709 : : because other graph inconsistencies are easier to detect. */
1710 : :
1711 : : /* Count and check singleton components. */
1712 : 4 : auto_vec<int> scc_size {};
1713 : 4 : scc_size.safe_grow_cleared (nscc);
1714 : 48 : for (int i = 0; i != cfg->n_vertices; ++i)
1715 : 44 : scc_size[cfg->vertices[i].component]++;
1716 : 4 : ASSERT_EQ (nscc, 6);
1717 : 4 : ASSERT_EQ (scc_size[0], 1);
1718 : 4 : ASSERT_EQ (scc_size[1], 1);
1719 : 4 : ASSERT_EQ (scc_size[2], 1);
1720 : 4 : ASSERT_EQ (scc_size[3], 6);
1721 : 4 : ASSERT_EQ (scc_size[4], 1);
1722 : 4 : ASSERT_EQ (scc_size[5], 1);
1723 : :
1724 : : /* Manually unroll the loop finding the simple paths starting at the
1725 : : vertices in the SCCs. In this case there is only the one SCC. */
1726 : 4 : trie ccfg_paths;
1727 : 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 2));
1728 : 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 4));
1729 : 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 5));
1730 : 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 6));
1731 : 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 7));
1732 : 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 9));
1733 : : /* Then in+out of trie. */
1734 : 4 : auto_vec_vec xscc_internal_pp = ccfg_paths.paths ();
1735 : 4 : trie scc_internal_pp;
1736 : 60 : for (auto &p : xscc_internal_pp)
1737 : 96 : scc_internal_pp.insert_with_suffix (p);
1738 : :
1739 : 4 : const int pp01[] = { 5, 7, 2, 4, 6, 9 };
1740 : 4 : const int pp02[] = { 4, 5, 7, 2, 4 };
1741 : 4 : const int pp03[] = { 4, 6, 9, 7, 2, 4 };
1742 : 4 : const int pp04[] = { 2, 4, 5, 7, 2 };
1743 : 4 : const int pp05[] = { 2, 4, 6, 9, 7, 2 };
1744 : 4 : const int pp06[] = { 5, 7, 2, 4, 5 };
1745 : 4 : const int pp07[] = { 6, 9, 7, 2, 4, 6 };
1746 : 4 : const int pp08[] = { 7, 2, 4, 5, 7 };
1747 : 4 : const int pp09[] = { 9, 7, 2, 4, 6, 9 };
1748 : 4 : const int pp10[] = { 7, 2, 4, 6, 9, 7 };
1749 : 4 : const int pp11[] = { 6, 9, 7, 2, 4, 5 };
1750 : :
1751 : 4 : ASSERT_EQ (count (scc_internal_pp), 11);
1752 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp01));
1753 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp02));
1754 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp03));
1755 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp04));
1756 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp05));
1757 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp06));
1758 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp07));
1759 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp08));
1760 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp09));
1761 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp10));
1762 : 4 : ASSERT_TRUE (contains (scc_internal_pp, pp11));
1763 : 4 : }
1764 : :
1765 : : /* The remaining tests deconstructs the algorithm and runs only a single phase
1766 : : with good inputs at that point. This makes it easier to pinpoint where
1767 : : things go wrong, and helps show in steps how the algorithm works and the
1768 : : phases relate.
1769 : :
1770 : : The phases and their inputs and outputs are bazed on Fazli & Afshsarchi. */
1771 : :
1772 : : static void
1773 : 4 : test_scc_internal_prime_paths ()
1774 : : {
1775 : : /* This graph has only the SCC subgraph. The result of running prime-paths
1776 : : on it should be the SCC internal prime paths of the full graph. */
1777 : 4 : auto_graph scc (new_graph (11));
1778 : 4 : add_edge (scc, 0, 2);
1779 : 4 : add_edge (scc, 2, 4);
1780 : 4 : add_edge (scc, 4, 5);
1781 : 4 : add_edge (scc, 4, 6);
1782 : 4 : add_edge (scc, 5, 7);
1783 : 4 : add_edge (scc, 6, 9);
1784 : 4 : add_edge (scc, 9, 7);
1785 : 4 : add_edge (scc, 7, 2);
1786 : :
1787 : 4 : auto_vec_vec paths = prime_paths (scc, 100);
1788 : 4 : const int p01[] = { 5, 7, 2, 4, 6, 9 };
1789 : 4 : const int p02[] = { 4, 6, 9, 7, 2, 4 };
1790 : 4 : const int p03[] = { 2, 4, 6, 9, 7, 2 };
1791 : 4 : const int p04[] = { 6, 9, 7, 2, 4, 6 };
1792 : 4 : const int p05[] = { 9, 7, 2, 4, 6, 9 };
1793 : 4 : const int p06[] = { 7, 2, 4, 6, 9, 7 };
1794 : 4 : const int p07[] = { 6, 9, 7, 2, 4, 5 };
1795 : 4 : const int p08[] = { 4, 5, 7, 2, 4 };
1796 : 4 : const int p09[] = { 2, 4, 5, 7, 2 };
1797 : 4 : const int p10[] = { 5, 7, 2, 4, 5 };
1798 : 4 : const int p11[] = { 7, 2, 4, 5, 7 };
1799 : :
1800 : 4 : ASSERT_TRUE (any_equal_p (p01, paths));
1801 : 4 : ASSERT_TRUE (any_equal_p (p02, paths));
1802 : 4 : ASSERT_TRUE (any_equal_p (p03, paths));
1803 : 4 : ASSERT_TRUE (any_equal_p (p04, paths));
1804 : 4 : ASSERT_TRUE (any_equal_p (p05, paths));
1805 : 4 : ASSERT_TRUE (any_equal_p (p06, paths));
1806 : 4 : ASSERT_TRUE (any_equal_p (p07, paths));
1807 : 4 : ASSERT_TRUE (any_equal_p (p08, paths));
1808 : 4 : ASSERT_TRUE (any_equal_p (p09, paths));
1809 : 4 : ASSERT_TRUE (any_equal_p (p10, paths));
1810 : 4 : ASSERT_TRUE (any_equal_p (p11, paths));
1811 : 4 : }
1812 : :
1813 : : /* Test the entry/exit path helpers for the strongly connected component in
1814 : : binary_search. The SCC has one entry (2, the loop header) and two exits (2,
1815 : : 6, the loop exit and return). */
1816 : : static void
1817 : 4 : test_scc_entry_exit_paths ()
1818 : : {
1819 : 4 : auto_graph scc (new_graph (11));
1820 : 4 : add_edge (scc, 2, 4);
1821 : 4 : add_edge (scc, 4, 5);
1822 : 4 : add_edge (scc, 4, 6);
1823 : 4 : add_edge (scc, 5, 7);
1824 : 4 : add_edge (scc, 6, 9);
1825 : 4 : add_edge (scc, 9, 7);
1826 : 4 : add_edge (scc, 7, 2);
1827 : :
1828 : 4 : trie scc_internal_trie;
1829 : 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 2));
1830 : 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 4));
1831 : 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 5));
1832 : 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 6));
1833 : 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 7));
1834 : 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 9));
1835 : 4 : auto_vec_vec scc_prime_paths = scc_internal_trie.paths ();
1836 : :
1837 : 4 : trie entry_exits {};
1838 : 4 : scc_entry_exit_paths (scc_prime_paths, 2, 2, entry_exits);
1839 : 4 : scc_entry_exit_paths (scc_prime_paths, 2, 6, entry_exits);
1840 : :
1841 : 4 : const int p01[] = { 2 };
1842 : 4 : const int p02[] = { 2, 4, 6 };
1843 : :
1844 : 4 : ASSERT_EQ (count (entry_exits), 2);
1845 : 4 : ASSERT_TRUE (contains (entry_exits, p01));
1846 : 4 : ASSERT_TRUE (contains (entry_exits, p02));
1847 : :
1848 : 4 : trie exits;
1849 : 4 : scc_exit_paths (scc_prime_paths, 2, exits);
1850 : 4 : scc_exit_paths (scc_prime_paths, 6, exits);
1851 : :
1852 : 4 : const int p03[] = { 4, 6, 9, 7, 2 };
1853 : 4 : const int p04[] = { 5, 7, 2, 4, 6 };
1854 : 4 : const int p05[] = { 9, 7, 2, 4, 6 };
1855 : 4 : const int p06[] = { 4, 5, 7, 2 };
1856 : :
1857 : 4 : ASSERT_EQ (count (exits), 4);
1858 : 4 : ASSERT_TRUE (contains (exits, p03));
1859 : 4 : ASSERT_TRUE (contains (exits, p04));
1860 : 4 : ASSERT_TRUE (contains (exits, p05));
1861 : 4 : ASSERT_TRUE (contains (exits, p06));
1862 : :
1863 : 4 : trie entries;
1864 : 4 : scc_entry_paths (scc_prime_paths, 2, entries);
1865 : :
1866 : 4 : const int p07[] = { 2, 4, 6, 9, 7 };
1867 : 4 : const int p08[] = { 2, 4, 5, 7 };
1868 : 4 : ASSERT_EQ (count (entries), 2);
1869 : 4 : ASSERT_TRUE (contains (entries, p07));
1870 : 4 : ASSERT_TRUE (contains (entries, p08));
1871 : 4 : }
1872 : :
1873 : : static void
1874 : 4 : test_complete_prime_paths ()
1875 : : {
1876 : 4 : const int ccfgpp0[] = { 0, 1, 2, 3, 5 };
1877 : 4 : const int ccfgpp1[] = { 0, 1, 2, 4, 5 };
1878 : 4 : trie ccfg_prime_paths {};
1879 : 4 : ccfg_prime_paths.insert (ccfgpp0);
1880 : 4 : ccfg_prime_paths.insert (ccfgpp1);
1881 : :
1882 : 4 : const int scc0[] = { 2 };
1883 : 4 : const int scc1[] = { 2, 4, 6 };
1884 : :
1885 : 4 : const int ccfg_single[] = { 0, 1, 3, 8, 10 };
1886 : :
1887 : 4 : auto_graph cfg (binary_search_cfg ());
1888 : 4 : auto_sbitmap_vector edges (sbitmap_vector_alloc (cfg->n_vertices,
1889 : 4 : cfg->n_vertices));
1890 : 4 : bitmap_vector_clear (edges, cfg->n_vertices);
1891 : 48 : for (int i = 0; i != cfg->n_vertices; ++i)
1892 : 96 : for (graph_edge *e = cfg->vertices[i].succ; e; e = e->succ_next)
1893 : 52 : bitmap_set_bit (edges[e->src], e->dest);
1894 : :
1895 : 4 : auto_vec<trie> ccfg_paths {};
1896 : 4 : ccfg_paths.safe_grow_cleared (6);
1897 : 4 : ccfg_paths[0].insert (array_slice <const int> (ccfg_single + 0, 1));
1898 : 4 : ccfg_paths[1].insert (array_slice <const int> (ccfg_single + 1, 1));
1899 : 4 : ccfg_paths[3].insert (array_slice <const int> (ccfg_single + 2, 1));
1900 : 4 : ccfg_paths[4].insert (array_slice <const int> (ccfg_single + 3, 1));
1901 : 4 : ccfg_paths[5].insert (array_slice <const int> (ccfg_single + 4, 1));
1902 : :
1903 : : /* The paths for the SCC would need to be updated in ccfg pre pass. This
1904 : : feels like a clumsy interface and should maybe be disconnected from the
1905 : : struct graph. */
1906 : 4 : ccfg_paths[2].hard_insert (scc0);
1907 : 4 : ccfg_paths[2].hard_insert (scc1);
1908 : :
1909 : 4 : trie cpp = cfg_complete_prime_paths (edges, ccfg_paths, ccfg_prime_paths);
1910 : :
1911 : 4 : const int p01[] = { 0, 1, 2, 3, 10 };
1912 : 4 : const int p02[] = { 0, 1, 2, 4, 6, 8, 10 };
1913 : :
1914 : 4 : ASSERT_EQ (count (cpp), 2);
1915 : 4 : ASSERT_TRUE (contains (cpp, p01));
1916 : 4 : ASSERT_TRUE (contains (cpp, p02));
1917 : 4 : }
1918 : :
1919 : : static vec<int>
1920 : 4 : binary_search_scc_map ()
1921 : : {
1922 : 4 : vec<int> sccs {};
1923 : 4 : sccs.safe_grow (11);
1924 : 4 : sccs[0] = 0;
1925 : 4 : sccs[1] = 1;
1926 : 4 : sccs[2] = 2;
1927 : 4 : sccs[3] = 3;
1928 : 4 : sccs[4] = 2;
1929 : 4 : sccs[5] = 2;
1930 : 4 : sccs[6] = 2;
1931 : 4 : sccs[7] = 2;
1932 : 4 : sccs[8] = 4;
1933 : 4 : sccs[9] = 2;
1934 : 4 : sccs[10] = 5;
1935 : 4 : return sccs;
1936 : : }
1937 : :
1938 : : static void
1939 : 4 : test_exit_prime_paths ()
1940 : : {
1941 : 4 : const int cpp01[] = { 0, 1, 2, 3, 10 };
1942 : 4 : const int cpp02[] = { 0, 1, 2, 4, 6, 8, 10 };
1943 : 4 : trie complete_prime_paths {};
1944 : 4 : complete_prime_paths.insert_with_suffix (cpp01);
1945 : 4 : complete_prime_paths.insert_with_suffix (cpp02);
1946 : :
1947 : 4 : const int ep01[] = { 4, 6, 9, 7, 2 };
1948 : 4 : const int ep02[] = { 5, 7, 2, 4, 6 };
1949 : 4 : const int ep03[] = { 9, 7, 2, 4, 6 };
1950 : 4 : const int ep04[] = { 4, 5, 7, 2 };
1951 : 4 : trie exit_paths;
1952 : 4 : exit_paths.insert (ep01);
1953 : 4 : exit_paths.insert (ep02);
1954 : 4 : exit_paths.insert (ep03);
1955 : 4 : exit_paths.insert (ep04);
1956 : :
1957 : 4 : auto_graph cfg (binary_search_cfg ());
1958 : 4 : trie epp = scc_exit_prime_paths (cfg, exit_paths, complete_prime_paths);
1959 : :
1960 : 4 : const int pp01[] = { 4, 6, 9, 7, 2, 3, 10 };
1961 : 4 : const int pp02[] = { 5, 7, 2, 4, 6, 8, 10 };
1962 : 4 : const int pp03[] = { 9, 7, 2, 4, 6, 8, 10 };
1963 : 4 : const int pp04[] = { 4, 5, 7, 2, 3, 10 };
1964 : :
1965 : 4 : ASSERT_EQ (count (epp), 4);
1966 : 4 : ASSERT_TRUE (contains (epp, pp01));
1967 : 4 : ASSERT_TRUE (contains (epp, pp02));
1968 : 4 : ASSERT_TRUE (contains (epp, pp03));
1969 : 4 : ASSERT_TRUE (contains (epp, pp04));
1970 : 4 : }
1971 : :
1972 : : static void
1973 : 4 : test_entry_prime_paths ()
1974 : : {
1975 : 4 : auto_graph cfg (binary_search_cfg ());
1976 : :
1977 : 4 : static int sccep01[] = { 2, 4, 6, 9, 7 };
1978 : 4 : static int sccep02[] = { 2, 4, 5, 7 };
1979 : 4 : trie scc_entry_paths;
1980 : 4 : scc_entry_paths.insert (sccep01);
1981 : 4 : scc_entry_paths.insert (sccep02);
1982 : :
1983 : 4 : const int cpp01[] = { 0, 1, 2, 3, 10 };
1984 : 4 : const int cpp02[] = { 0, 1, 2, 4, 6, 8, 10 };
1985 : 4 : trie complete_prime_paths {};
1986 : 4 : complete_prime_paths.insert (cpp01);
1987 : 4 : complete_prime_paths.insert (cpp02);
1988 : :
1989 : 4 : const int ep01[] = { 4, 6, 9, 7, 2, 3, 10 };
1990 : 4 : const int ep02[] = { 5, 7, 2, 4, 6, 8, 10 };
1991 : 4 : const int ep03[] = { 9, 7, 2, 4, 6, 8, 10 };
1992 : 4 : const int ep04[] = { 4, 5, 7, 2, 3, 10 };
1993 : 4 : trie exit_prime_paths {};
1994 : 4 : exit_prime_paths.insert (ep01);
1995 : 4 : exit_prime_paths.insert (ep02);
1996 : 4 : exit_prime_paths.insert (ep03);
1997 : 4 : exit_prime_paths.insert (ep04);
1998 : :
1999 : 4 : auto_vec<int> sccs = binary_search_scc_map ();
2000 : :
2001 : 4 : trie epp = scc_entry_prime_paths (cfg, scc_entry_paths,
2002 : : complete_prime_paths,
2003 : 4 : exit_prime_paths);
2004 : :
2005 : : /* The 0 (start node) does not show up in the Fazli & Afsharchi paper and
2006 : : kinda, but has no real impact on the result. The prime-paths functions
2007 : : do not care about these vertices, but the path-coverage instrumentation
2008 : : filters out the ENTRY/EXIT blocks from all the paths. */
2009 : 4 : const int pp01[] = { 0, 1, 2, 4, 6, 9, 7 };
2010 : 4 : const int pp02[] = { 0, 1, 2, 4, 5, 7 };
2011 : 4 : ASSERT_EQ (count (epp), 2);
2012 : 4 : ASSERT_TRUE (contains (epp, pp01));
2013 : 4 : ASSERT_TRUE (contains (epp, pp02));
2014 : 4 : }
2015 : :
2016 : : /* A straight-line graph with one vertex should yield a single path of length 1
2017 : : with just the non-exit non-entry node in it. */
2018 : : void
2019 : 4 : test_singleton_path ()
2020 : : {
2021 : 4 : auto_graph cfg (new_graph (3));
2022 : 4 : add_edge (cfg, 0, 2);
2023 : 4 : add_edge (cfg, 2, 1);
2024 : 4 : auto_vec_vec paths = prime_paths (cfg, 100);
2025 : :
2026 : 4 : ASSERT_EQ (paths.length (), 1);
2027 : 4 : ASSERT_EQ (paths[0].length (), 3);
2028 : 4 : ASSERT_EQ (paths[0][0], 0);
2029 : 4 : ASSERT_EQ (paths[0][1], 2);
2030 : 4 : ASSERT_EQ (paths[0][2], 1);
2031 : 4 : }
2032 : :
2033 : : void
2034 : 4 : path_coverage_cc_tests ()
2035 : : {
2036 : 4 : limit_reset (250000);
2037 : 4 : test_prime_paths ();
2038 : 4 : test_build_ccfg ();
2039 : 4 : test_split_components ();
2040 : 4 : test_scc_internal_prime_paths ();
2041 : 4 : test_scc_entry_exit_paths ();
2042 : 4 : test_complete_prime_paths ();
2043 : 4 : test_exit_prime_paths ();
2044 : 4 : test_entry_prime_paths ();
2045 : 4 : test_singleton_path ();
2046 : 4 : }
2047 : :
2048 : : } // namespace selftest
2049 : :
2050 : : #endif /* #if CHECKING_P */
|
