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