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 569 : limit_reset (size_t approx)
45 : {
46 569 : 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 6641 : limit_checked_add (size_t approx)
53 : {
54 0 : approx_limit -= approx < approx_limit ? approx : approx_limit;
55 6641 : 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 3795239 : limit_exceed_p (size_t approx)
64 : {
65 3795239 : 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 1174 : auto_graph (struct graph *graph) : ptr (graph) {}
73 : auto_graph (const auto_graph &) = delete;
74 569 : ~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 569 : auto_sbitmap_vector (sbitmap *s) : ptr (s) {}
85 : auto_sbitmap_vector (const auto_sbitmap_vector &) = delete;
86 565 : ~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 1270 : ~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 1131 : ~auto_vec_vec_vec ()
103 : {
104 13342 : for (vec<vec<int>> &v : *this)
105 9949 : release_vec_vec (v);
106 1131 : release ();
107 1131 : }
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 88578 : unsigned length () const
158 88578 : { 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 53609 : const xpair &at (unsigned i) const
169 53609 : { 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 30244 : xpair_less (const xpair& lhs, const xpair& rhs)
195 : {
196 30244 : return lhs.key < rhs.key;
197 : }
198 :
199 : /* Compare LHS.key to RHS.key, for use with vec.bsearch. */
200 : int
201 97122 : xpair_cmp (const void *lhs, const void *rhs)
202 : {
203 97122 : 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 40694999 : trie_node::get (int key) const
209 : {
210 40694999 : if (!heaped)
211 : {
212 40668309 : if (len == 0) return NULL;
213 40655170 : if (len >= 1 && key == near[0].key) return near + 0;
214 6681497 : if (len >= 2 && key == near[1].key) return near + 1;
215 : return NULL;
216 : }
217 : else
218 : {
219 26690 : xpair kv;
220 26690 : kv.key = key;
221 53380 : 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 3818190 : trie_node::put (int key, unsigned val)
231 : {
232 3818190 : xpair kv;
233 3818190 : kv.key = key;
234 3818190 : kv.val = val;
235 3818190 : if (!heaped)
236 : {
237 3810852 : const unsigned i = near_lower_bound (key);
238 3810852 : if (len < 2)
239 : {
240 3809580 : near[1] = near[0];
241 3809580 : near[i] = kv;
242 3809580 : 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 1272 : vec<xpair> xs {};
249 1272 : xs.reserve (13);
250 1272 : xs.quick_grow (3);
251 1272 : gcc_checking_assert (i <= 2);
252 1272 : if (i == 0)
253 : {
254 163 : xs[0] = kv;
255 163 : xs[1] = near[0];
256 163 : xs[2] = near[1];
257 : }
258 1109 : else if (i == 1)
259 : {
260 135 : xs[0] = near[0];
261 135 : xs[1] = kv;
262 135 : xs[2] = near[1];
263 : }
264 : else
265 : {
266 974 : xs[0] = near[0];
267 974 : xs[1] = near[1];
268 974 : xs[2] = kv;
269 : }
270 :
271 1272 : far = xs;
272 1272 : heaped = 1;
273 : }
274 : }
275 : else
276 : {
277 7338 : const unsigned i = far.lower_bound (kv, xpair_less);
278 7338 : far.safe_insert (i, kv);
279 : }
280 3818190 : }
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 3810852 : trie_node::near_lower_bound (int key) const
287 : {
288 3810852 : gcc_checking_assert (!heaped);
289 3810852 : if (len == 0) return 0;
290 760049 : if (len >= 1 && key < near[0].key) return 0;
291 755461 : if (len >= 2 && key < near[1].key) return 1;
292 755326 : 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 3798049 : 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 19505 : ~iter ()
362 13904 : { 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 19286 : 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 219 : 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 18359 : trie::trie () : vertices (vec<trie_node> {}), len (0)
433 : {
434 18359 : vertices.safe_push (trie_node {});
435 18359 : vertices[0].inserted = true;
436 18359 : }
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 18359 : trie::~trie ()
452 : {
453 3891626 : for (trie_node &v : vertices)
454 3836549 : if (v.heaped)
455 1272 : v.far.release ();
456 18359 : vertices.release ();
457 18359 : }
458 :
459 : /* Insert PATH into the trie. */
460 : bool
461 759794 : trie::insert (const vec<int>& path)
462 : {
463 1519588 : 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 771651 : trie::insert (array_slice<const int> path)
472 : {
473 771651 : size_t index = 0;
474 771651 : size_t partition = 0;
475 40648655 : for (const int v : path)
476 : {
477 40641960 : trie_node ¤t = vertices[index];
478 40641960 : current.inserted = true;
479 40641960 : partition++;
480 :
481 40641960 : const auto *xp = current.get (v);
482 40641960 : if (xp)
483 : {
484 39877004 : 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 764956 : unsigned ix = vertices.length ();
492 764956 : current.put (v, ix);
493 764956 : current.endofpath = false;
494 :
495 764956 : array_slice<const int> tail (path.begin () + partition,
496 764956 : path.size () - partition);
497 764956 : vertices.safe_grow_cleared (1 + ix + tail.size ());
498 :
499 3782910 : for (const int v : tail)
500 : {
501 3017954 : trie_node &last = vertices[ix];
502 3017954 : ix += 1;
503 3017954 : last.put (v, ix);
504 3017954 : last.inserted = true;
505 : }
506 :
507 764956 : vertices.last ().endofpath = true;
508 764956 : vertices.last ().inserted = true;
509 764956 : len += 1;
510 764956 : 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 5304 : trie::hard_insert (array_slice<const int> path)
522 : {
523 5304 : size_t index = 0;
524 5304 : size_t partition = 0;
525 5819 : for (const int v : path)
526 : {
527 5683 : trie_node ¤t = vertices[index];
528 5683 : current.inserted = true;
529 5683 : partition++;
530 :
531 5683 : const auto *xp = current.get (v);
532 5683 : if (xp)
533 : {
534 515 : index = xp->val;
535 : }
536 : else
537 : {
538 5168 : unsigned ix = vertices.length ();
539 5168 : current.put (v, ix);
540 :
541 5168 : array_slice<const int> tail (path.begin () + partition,
542 5168 : path.size () - partition);
543 5168 : vertices.safe_grow_cleared (1 + ix + tail.size ());
544 :
545 5782 : for (const int v : tail)
546 : {
547 614 : trie_node &last = vertices[ix];
548 614 : ix += 1;
549 614 : last.put (v, ix);
550 614 : last.inserted = true;
551 : }
552 :
553 5168 : vertices.last ().endofpath = true;
554 5168 : vertices.last ().inserted = true;
555 5168 : len += 1;
556 5168 : return true;
557 : }
558 : }
559 :
560 136 : vertices[index].endofpath = true;
561 136 : 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 13793 : trie::insert_suffix (array_slice<const int> path)
570 : {
571 13793 : size_t index = 0;
572 13793 : size_t partition = 0;
573 49944 : for (const int v : path)
574 : {
575 46553 : trie_node ¤t = vertices[index];
576 46553 : current.endofpath = false;
577 46553 : partition++;
578 :
579 46553 : const auto *xp = current.get (v);
580 46553 : if (xp)
581 : {
582 36151 : 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 10402 : unsigned ix = vertices.length ();
590 10402 : current.put (v, ix);
591 :
592 10402 : array_slice<const int> tail (path.begin () + partition,
593 10402 : path.size () - partition);
594 10402 : vertices.safe_grow_cleared (1 + ix + tail.size ());
595 :
596 29498 : for (const int v : tail)
597 : {
598 19096 : vertices[ix].put (v, ix + 1);
599 19096 : ix += 1;
600 : }
601 :
602 10402 : return true;
603 : }
604 : }
605 :
606 3391 : vertices[index].endofpath = false;
607 3391 : return false;
608 : }
609 :
610 : /* Insert the paths from OTHER into this trie. */
611 : void
612 1124 : trie::merge (const trie& other)
613 : {
614 1124 : auto_vec<int, 32> p {};
615 1124 : iter itr = other.paths (p);
616 1416 : while (itr.next ())
617 584 : insert_with_suffix (p);
618 1124 : }
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 10830 : trie::insert_with_suffix (array_slice<const int> path)
626 : {
627 10830 : bool inserted = insert (path);
628 10830 : path = array_slice<const int> (path.begin () + 1, path.size () - 1);
629 24623 : while (inserted && !path.empty ())
630 : {
631 13793 : inserted = insert_suffix (path);
632 13793 : path = array_slice<const int> (path.begin () + 1, path.size () - 1);
633 : }
634 10830 : return inserted;
635 : }
636 :
637 : /* Convert the paths of a trie to a vec-of-vec. */
638 : vec<vec<int>>
639 5573 : trie::paths () const
640 : {
641 5573 : auto_vec<int> path {};
642 5573 : vec<vec<int>> all {};
643 5573 : auto iter = paths (path);
644 16499 : while (iter.next ())
645 10926 : all.safe_push (path.copy ());
646 5573 : return all;
647 5573 : }
648 :
649 : /* Create an iterator over VERTICES with the caller-provided buffer PATH. */
650 19286 : trie::iter::iter (vec<int> &path, const vec<trie_node> &vertices) : path (path),
651 19286 : vertices (vertices), stack (vec<frame> {})
652 : {
653 19286 : gcc_checking_assert (!vertices.is_empty ());
654 19286 : stack.reserve (13);
655 19286 : frame f;
656 19286 : f.ix = 0;
657 19286 : f.itr = 0;
658 19286 : f.end = vertices[0].length ();
659 19286 : stack.quick_push (f);
660 19286 : }
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 219 : trie::iter::iter (int from, vec<int> &path, const vec<trie_node> &vertices) :
667 219 : path (path), vertices (vertices), stack (vec<frame> {})
668 : {
669 219 : gcc_checking_assert (!vertices.is_empty ());
670 219 : stack.reserve (13);
671 :
672 219 : auto *xp = vertices[0].get (from);
673 219 : 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 219 : frame f;
686 219 : f.ix = xp->val;
687 219 : f.itr = 0;
688 219 : f.end = vertices[f.ix].length ();
689 219 : 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 39428 : trie::iter::next ()
698 : {
699 132171 : while (true)
700 : {
701 132171 : frame &top = stack.last ();
702 132171 : const trie_node &vertex = vertices[top.ix];
703 :
704 41008 : if (vertex.endofpath && yield
705 173179 : && (top.itr != top.end || vertex.length () == 0))
706 : {
707 20470 : yield = false;
708 20470 : return true;
709 : }
710 :
711 111701 : yield = true;
712 :
713 111701 : if (top.itr != top.end)
714 : {
715 48959 : const xpair succ = vertex.at (top.itr);
716 48959 : const trie_node &next = vertices[succ.val];
717 48959 : top.itr++;
718 :
719 48959 : if (!next.inserted)
720 5175 : continue;
721 :
722 43784 : frame f {};
723 43784 : f.ix = succ.val;
724 43784 : f.itr = 0;
725 43784 : f.end = next.length ();
726 43784 : path.safe_push (succ.key);
727 43784 : stack.safe_push (f);
728 : }
729 : else
730 : {
731 62742 : stack.pop ();
732 62742 : if (stack.is_empty ())
733 : return false;
734 43784 : 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 1148 : trie::iter::next (int limit)
746 : {
747 6734 : while (true)
748 : {
749 6734 : frame &top = stack.last ();
750 6734 : const trie_node &vertex = vertices[top.ix];
751 :
752 6734 : if (yield && top.itr != top.end)
753 : {
754 3939 : const xpair succ = vertex.at (top.itr);
755 3939 : const trie_node &next = vertices[succ.val];
756 3939 : const int key = succ.key;
757 3939 : const int val = succ.val;
758 3939 : top.itr++;
759 :
760 3939 : if (!next.inserted)
761 652 : continue;
762 :
763 3311 : if (key == limit)
764 : {
765 844 : if (path.is_empty ())
766 24 : continue;
767 820 : yield = false;
768 820 : return true;
769 : }
770 :
771 2467 : frame f {};
772 2467 : f.ix = val;
773 2467 : f.itr = 0;
774 2467 : f.end = next.length ();
775 2467 : path.safe_push (key);
776 2467 : stack.safe_push (f);
777 2467 : }
778 : else
779 : {
780 2795 : yield = true;
781 2795 : stack.pop ();
782 2795 : if (stack.is_empty ())
783 : return false;
784 2467 : 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 534 : trie::iter::next (bool)
794 : {
795 1956 : while (true)
796 : {
797 1956 : frame &top = stack.last ();
798 1956 : const trie_node &vertex = vertices[top.ix];
799 :
800 3597 : if (yield && vertex.length () == 0)
801 : {
802 315 : yield = false;
803 315 : return true;
804 : }
805 :
806 1641 : yield = true;
807 :
808 1641 : if (top.itr != top.end)
809 : {
810 711 : const xpair succ = vertex.at (top.itr);
811 711 : const trie_node &next = vertices[succ.val];
812 711 : top.itr++;
813 :
814 711 : frame f {};
815 711 : f.ix = succ.val;
816 711 : f.itr = 0;
817 711 : f.end = next.length ();
818 711 : path.safe_push (succ.key);
819 711 : stack.safe_push (f);
820 : }
821 : else
822 : {
823 930 : stack.pop ();
824 930 : if (stack.is_empty ())
825 : return false;
826 711 : 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 12859 : index_of (T needle, const vec <T> &haystack)
835 : {
836 12859 : size_t len = haystack.length ();
837 20714 : for (size_t i = 0; i != len; ++i)
838 20498 : 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 5681 : edge_p (const struct graph *graph, int src, int dest)
846 : {
847 50374 : for (struct graph_edge *e = graph->vertices[src].succ; e; e = e->succ_next)
848 44892 : 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 12055 : cycle_p (const vec<int>& path, int v)
856 : {
857 12055 : 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 4997 : scc_entry_exit_paths (const vec<vec<int>> &internal_pp, int entry, int exit,
868 : trie &out)
869 : {
870 4997 : if (entry == exit)
871 : {
872 4929 : out.hard_insert (array_slice <const int> (&entry, 1));
873 4929 : return;
874 : }
875 :
876 544 : for (const vec<int> &path : internal_pp)
877 : {
878 340 : const size_t Ven = index_of (entry, path);
879 340 : const size_t Vex = index_of (exit, path);
880 :
881 340 : if (Ven == (size_t)-1 || Vex == (size_t)-1 || Vex <= Ven)
882 192 : continue;
883 :
884 148 : const size_t len = (Vex + 1) - Ven;
885 296 : array_slice <const int> p (path.begin () + Ven, len);
886 148 : 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 4993 : scc_exit_paths (const vec<vec<int>> &prime_paths, int exit, trie &out)
900 : {
901 4993 : trie trie;
902 21152 : for (const vec<int> &path : prime_paths)
903 : {
904 6173 : const size_t Vex = index_of (exit, path);
905 6173 : if (Vex == (size_t)-1 || cycle_p (path, exit))
906 5134 : continue;
907 2078 : array_slice <const int> p (path.begin (), Vex + 1);
908 1039 : trie.insert_with_suffix (p);
909 : }
910 :
911 4993 : auto_vec<int> path {};
912 4993 : auto iter = trie.paths (path);
913 5212 : while (iter.next ())
914 438 : out.hard_insert (path);
915 4993 : }
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 4954 : scc_entry_paths (const vec<vec<int>> &internal_pp, int entry, trie &trie)
922 : {
923 20868 : for (const vec<int> &path : internal_pp)
924 : {
925 6006 : const size_t Ven = index_of (entry, path);
926 6006 : if (Ven == (size_t)-1 || cycle_p (path, entry))
927 5055 : continue;
928 2853 : array_slice <const int> p (path.begin () + Ven, path.length () - Ven);
929 951 : trie.insert (p);
930 : }
931 4954 : }
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 16054 : 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 16054 : if (itr == end)
946 : {
947 6724 : trie.insert_with_suffix (path);
948 3362 : return;
949 : }
950 :
951 12692 : const unsigned pathlen = path.length ();
952 12692 : const sbitmap succs = edges[path.last ()];
953 50845 : for (const vec<int> &enex : scc_enex_paths[*itr])
954 : {
955 12803 : if (!bitmap_bit_p (succs, enex[0]))
956 104 : continue;
957 :
958 12699 : path.safe_splice (enex);
959 12699 : cfg_complete_prime_paths1 (itr + 1, end, edges, scc_enex_paths,
960 : path, trie);
961 12699 : path.truncate (pathlen);
962 12699 : 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 566 : cfg_complete_prime_paths (const sbitmap *edges,
971 : const vec<trie> &scc_entry_exit_paths,
972 : const trie &ccfg_prime_paths)
973 : {
974 566 : trie trie;
975 566 : auto_vec<int, 16> path {};
976 566 : auto_vec<int, 16> cfgpp {};
977 566 : auto_vec_vec_vec scc_enex {};
978 566 : scc_enex.reserve (scc_entry_exit_paths.length ());
979 :
980 11084 : for (size_t i = 0; i != scc_entry_exit_paths.length (); ++i)
981 : {
982 4976 : scc_enex.quick_push (vec<vec<int>> {});
983 4976 : auto iter = scc_entry_exit_paths[i].paths (path);
984 9993 : while (iter.next ())
985 5017 : scc_enex[i].safe_push (path.copy ());
986 4976 : }
987 :
988 566 : auto iter = ccfg_prime_paths.paths (cfgpp);
989 3927 : while (!limit_exceed_p (trie.size ()) && iter.next ())
990 13426 : for (const vec<int> &enex : scc_enex[cfgpp[0]])
991 : {
992 3355 : path.truncate (0);
993 3355 : path.safe_splice (enex);
994 6710 : cfg_complete_prime_paths1 (cfgpp.begin () + 1, cfgpp.end (), edges,
995 : scc_enex, path, trie);
996 3355 : if (limit_exceed_p (trie.size ()))
997 : return trie;
998 : }
999 :
1000 : return trie;
1001 566 : }
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 566 : scc_exit_prime_paths (const struct graph *cfg, const trie &scc_exit_paths,
1013 : const trie &complete_prime_paths)
1014 : {
1015 566 : trie trie;
1016 566 : auto_vec<int, 8> path {};
1017 566 : auto_vec<int, 8> r {};
1018 566 : auto_vec<int, 8> q {};
1019 :
1020 566 : auto exiter = scc_exit_paths.paths (q);
1021 785 : while (exiter.next ())
1022 : {
1023 219 : const int Vex = q.last ();
1024 219 : auto iter = complete_prime_paths.paths (r, Vex);
1025 534 : 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 315 : const int p0 = Vex;
1034 315 : const int p1 = r[0];
1035 :
1036 315 : if (cfg->vertices[p0].component == cfg->vertices[p1].component)
1037 96 : continue;
1038 :
1039 219 : path.truncate (0);
1040 438 : path.reserve (q.length () + r.length ());
1041 219 : path.splice (q);
1042 219 : path.splice (r);
1043 : /* This can probably insert without subpath elimination because:
1044 : 1. Conflicts are *really* rare (see patmatch in tree.c), but they
1045 : do happen.
1046 : 2. The output of this function is "filtered" through another trie
1047 : anyway so the redundant paths generated here will be eliminated
1048 : in the consumers at a very low extra cost. */
1049 219 : trie.insert (path);
1050 219 : if (limit_exceed_p (trie.size ()))
1051 0 : return trie;
1052 : }
1053 219 : }
1054 :
1055 : return trie;
1056 566 : }
1057 :
1058 : /* Check if PATH in CFG enters the VERTEX's SCC through VERTEX. */
1059 : bool
1060 820 : enters_through_p (const struct graph *cfg, const vec<int> &path, int vertex)
1061 : {
1062 820 : gcc_checking_assert (!path.is_empty ());
1063 820 : const int last = path.address()[path.length ()-1];
1064 820 : if (cfg->vertices[last].component == cfg->vertices[vertex].component)
1065 : return false;
1066 151 : return edge_p (cfg, last, vertex);
1067 : }
1068 :
1069 : /* Worker for scc_entry_prime_paths. CFG is the CFG for the function,
1070 : SCC_ENTRY_PATHS the accumulated scc_entry_paths for all the SCCs, PRIME_PATHS
1071 : is either the result of cfg_complete_prime_paths or exit_prime_paths, and OUT
1072 : the output trie.
1073 :
1074 : This function can suffer under path explosion and will terminate early if
1075 : the number of inserts in OUT exceeds approx_limit. */
1076 : void
1077 1132 : scc_entry_prime_paths1 (const struct graph *cfg, const trie &scc_entry_paths,
1078 : const trie &prime_paths, trie &out)
1079 : {
1080 1132 : auto_vec<int, 8> p {};
1081 1132 : auto_vec<int, 8> q {};
1082 1132 : auto_vec<int, 8> path {};
1083 1132 : auto itr = scc_entry_paths.paths (q);
1084 1460 : while (itr.next ())
1085 : {
1086 328 : const int Ven = q[0];
1087 : /* TODO: This might benefit from a reversed trie lookup. */
1088 328 : auto xitr = prime_paths.paths (p);
1089 1148 : while (xitr.next (Ven))
1090 : {
1091 820 : if (!enters_through_p (cfg, p, Ven))
1092 669 : continue;
1093 :
1094 151 : path.truncate (0);
1095 453 : path.reserve (p.length () + q.length ());
1096 151 : path.splice (p);
1097 151 : path.splice (q);
1098 302 : out.insert_with_suffix (path);
1099 151 : if (limit_exceed_p (out.size ()))
1100 0 : return;
1101 : }
1102 328 : }
1103 1132 : }
1104 :
1105 : /* Find the entry prime paths - the prime paths that start in the root and end
1106 : in a strongly connected component. CFG is the CFG for this function,
1107 : SCC_ENTRY_PATHS the accumulated scc_entry_paths for all the SCCs,
1108 : COMPLETE_PRIME_PATHS the result of cfg_complete_prime_paths, and
1109 : EXIT_PRIME_PATHS result of exit_prime_paths.
1110 :
1111 : This function can suffer under path explosion and will terminate early if
1112 : the return value grows beyond approx_limit. */
1113 : trie
1114 566 : scc_entry_prime_paths (const struct graph *cfg,
1115 : const trie &scc_entry_paths,
1116 : const trie &complete_prime_paths,
1117 : const trie &exit_prime_paths)
1118 : {
1119 566 : trie trie;
1120 566 : scc_entry_prime_paths1 (cfg, scc_entry_paths, complete_prime_paths, trie);
1121 566 : scc_entry_prime_paths1 (cfg, scc_entry_paths, exit_prime_paths, trie);
1122 566 : return trie;
1123 : }
1124 :
1125 : /* Build a new control flow graph from the strongly connected components, so
1126 : that every node in the CCFG is a strongly connected component in the original
1127 : CFG. NSSC is the number of vertices in the new graph, and the return value
1128 : of graphds_ssc. */
1129 : struct graph*
1130 569 : build_ccfg (struct graph *cfg, int nscc)
1131 : {
1132 569 : struct graph *ccfg = new_graph (nscc);
1133 6066 : for (int i = 0; i != cfg->n_vertices; ++i)
1134 : {
1135 5497 : struct vertex v = cfg->vertices[i];
1136 11768 : for (struct graph_edge *e = v.succ; e; e = e->succ_next)
1137 : {
1138 6271 : int src = v.component;
1139 6271 : int dest = cfg->vertices[e->dest].component;
1140 11777 : if (src != dest && !edge_p (ccfg, src, dest))
1141 5482 : add_edge (ccfg, src, dest);
1142 : }
1143 : }
1144 :
1145 569 : return ccfg;
1146 : }
1147 :
1148 : /* Create a new graph from CFG where the edges between strongly connected
1149 : components removed. */
1150 : struct graph*
1151 569 : disconnect_sccs (struct graph *cfg)
1152 : {
1153 569 : struct graph *ccfg = new_graph (cfg->n_vertices);
1154 569 : const struct vertex *vertices = cfg->vertices;
1155 6066 : for (int i = 0; i != cfg->n_vertices; ++i)
1156 : {
1157 5497 : ccfg->vertices[i].data = &cfg->vertices[i];
1158 11768 : for (struct graph_edge *e = vertices[i].succ; e; e = e->succ_next)
1159 6271 : if (vertices[e->src].component == vertices[e->dest].component)
1160 765 : add_edge (ccfg, e->src, e->dest)->data = e;
1161 : }
1162 569 : return ccfg;
1163 : }
1164 :
1165 : /* Check if vertex I in CFG is the entry vertex of a strongly connected
1166 : component. A vertex is an entry vertex if 1) there are no predecessors
1167 : (i.e. the root vertex is always an entry vertex) or 2) a predecessor belongs
1168 : to a different SCC. */
1169 : bool
1170 10494 : scc_entry_vertex_p (struct graph *cfg, size_t i)
1171 : {
1172 10494 : if (!cfg->vertices[i].pred)
1173 : return true;
1174 8086 : const int scc = cfg->vertices[i].component;
1175 8964 : for (struct graph_edge *e = cfg->vertices[i].pred; e; e = e->pred_next)
1176 8394 : if (cfg->vertices[e->src].component != scc)
1177 : return true;
1178 : return false;
1179 : }
1180 :
1181 : /* Check if vertex I in CFG is an exit vertex of a strongly connected component.
1182 : A vertex is an exit vertex if 1) there are no successors (i.e. the sink is
1183 : always an exit vertex) or 2) if a successor belongs to a different SCC. */
1184 : bool
1185 10502 : scc_exit_vertex_p (struct graph *cfg, size_t i)
1186 : {
1187 10502 : if (!cfg->vertices[i].succ)
1188 : return true;
1189 7962 : const int scc = cfg->vertices[i].component;
1190 8660 : for (struct graph_edge *e = cfg->vertices[i].succ; e; e = e->succ_next)
1191 8160 : if (cfg->vertices[e->dest].component != scc)
1192 : return true;
1193 : return false;
1194 : }
1195 :
1196 : /* Worker for simple_paths. Find all the simple paths in CFG starting at NODE
1197 : and insert into OUT. This is a DFS where the search stops when entering a
1198 : vertex already in SEEN. PATH is the sequence of ids for the vertices taken
1199 : from the from the root to NODE. When the number of inserts reaches LIMIT
1200 : the function aborts and returns so the caller can report that it is giving
1201 : up because the function is too complex.
1202 :
1203 : This function can suffer under path explosion and will terminate early if
1204 : the number of inserts in OUT exceeds approx_limit. */
1205 : void
1206 3769368 : simple_paths1 (const struct graph *cfg, int node, sbitmap seen, vec<int> &path,
1207 : trie &out)
1208 : {
1209 3769368 : if (limit_exceed_p (out.size ()))
1210 : return;
1211 :
1212 3769107 : if (!bitmap_set_bit (seen, node))
1213 : {
1214 751372 : if (path[0] == node)
1215 750841 : path.quick_push (node);
1216 751372 : out.insert (path);
1217 751372 : if (path[0] == node)
1218 750841 : path.pop ();
1219 751372 : return;
1220 : }
1221 3017735 : path.quick_push (node);
1222 :
1223 3017735 : struct graph_edge *succs = cfg->vertices[node].succ;
1224 3017735 : if (!succs)
1225 : {
1226 8203 : out.insert (path);
1227 8203 : bitmap_clear_bit (seen, node);
1228 8203 : path.pop ();
1229 8203 : return;
1230 : }
1231 :
1232 6772218 : for (struct graph_edge *e = succs; e; e = e->succ_next)
1233 3762686 : simple_paths1 (cfg, e->dest, seen, path, out);
1234 :
1235 3009532 : bitmap_clear_bit (seen, node);
1236 3009532 : path.pop ();
1237 : }
1238 :
1239 : /* Find all the simple paths in CFG starting at ROOT and insert into OUT. A
1240 : simple path is a sequence of vertices without any duplicated vertices (i.e.
1241 : no loops). SEEN should be an sbitmap of CFG->n_vertices size. PATH and
1242 : SEEN will be cleared entry and is for buffer reuse between calls. When the
1243 : number of inserts reaches LIMIT the function aborts and returns so the
1244 : caller can report that it is giving up because the function is too complex.
1245 : Note that there might be fewer prime paths than inserts, but if the number
1246 : of inserts alone is larger than LIMIT the function is very complex and would
1247 : take too long to compile in later stages.
1248 :
1249 : This function can suffer under path explosion and will terminate early if
1250 : the number of inserts in OUT exceeds approx_limit. Since OUT is often
1251 : shared between calls it is ok to use in a loop, and only check the size of
1252 : OUT after the loop terminates. */
1253 : void
1254 6682 : simple_paths (struct graph *cfg, int root, sbitmap seen, vec<int> &path,
1255 : trie &out)
1256 : {
1257 6682 : bitmap_clear (seen);
1258 6682 : path.reserve (cfg->n_vertices);
1259 6682 : path.truncate (0);
1260 6682 : simple_paths1 (cfg, root, seen, path, out);
1261 6682 : }
1262 :
1263 : /* Merge the tries T1, T2, T3, and set of paths VECS into the larges trie.
1264 : Returns a reference to the trie merged into. Merging tries and resolving
1265 : redundant paths is the slowest step (at least in the sense it works on the
1266 : largest input), and merging into a partial result reduces the work
1267 : accordingly. For large problems this is a massive improvement, which in the
1268 : worst cases (where all tries but one are empty or almost empty) speed up
1269 : 30-40%. */
1270 : trie&
1271 562 : merge (trie &t1, trie &t2, trie &t3, vec<vec<vec<int>>> &vecs)
1272 : {
1273 562 : trie *dst = nullptr;
1274 562 : const size_t s1 = t1.size ();
1275 562 : const size_t s2 = t2.size ();
1276 562 : const size_t s3 = t3.size ();
1277 :
1278 562 : if (s1 >= s2 && s1 >= s3)
1279 : {
1280 546 : dst = &t1;
1281 546 : t1.merge (t2);
1282 546 : t1.merge (t3);
1283 : }
1284 16 : else if (s2 >= s1 && s2 >= s3)
1285 : {
1286 10 : dst = &t2;
1287 10 : t2.merge (t1);
1288 10 : t2.merge (t3);
1289 : }
1290 : else
1291 : {
1292 6 : dst = &t3;
1293 6 : t3.merge (t1);
1294 6 : t3.merge (t2);
1295 : }
1296 :
1297 562 : gcc_checking_assert (dst);
1298 6638 : for (const vec<vec<int>> &v2 : vecs)
1299 20786 : for (const vec<int> &v1 : v2)
1300 11860 : dst->insert_with_suffix (v1);
1301 562 : return *dst;
1302 : }
1303 :
1304 : /* Store the edges of CFG in a matrix of bitmaps so that bit_p (edges[src],
1305 : dest) is true if there is an edge from src to dest. This is faster and more
1306 : convenient than walking the linked list of successors in hot loops. The
1307 : vector will have N bitmaps of N bits where N is the number of vertices in
1308 : CFG. */
1309 : sbitmap*
1310 565 : edge_matrix (const struct graph *cfg)
1311 : {
1312 565 : sbitmap *edges = sbitmap_vector_alloc (cfg->n_vertices, cfg->n_vertices);
1313 565 : bitmap_vector_clear (edges, cfg->n_vertices);
1314 6018 : for (int i = 0; i != cfg->n_vertices; ++i)
1315 11672 : for (graph_edge *e = cfg->vertices[i].succ; e; e = e->succ_next)
1316 6219 : bitmap_set_bit (edges[e->src], e->dest);
1317 565 : return edges;
1318 : }
1319 :
1320 : } // namespace
1321 :
1322 : /* Find the prime paths for CFG. The search gives up after approximate
1323 : PATHLIMIT probable paths have been generated to address path explosions.
1324 : The PATHLIMIT flag is typically controlled by -fpath-coverage-limit. This
1325 : function is a part of -fpath-coverage and will also be called from gcov.
1326 : The paths are returned in lexicographical order based on node (basic block)
1327 : ID. If the path limit was exceeded, an empty vector is returned.
1328 :
1329 : A simple path is a path where all vertices are unique, except possibly the
1330 : first and last. A prime path is a maximal-length simple path which is not a
1331 : part of any other simple path. Prime paths strike a good balance between
1332 : coverage thoroughness, loops (requiring them to be taken and skipped), and
1333 : number of paths.
1334 :
1335 : The algorithm is based on Fazli & Afsharchi's "A Time and Space-Efficient
1336 : Compositional Method for Prime and Test Paths Generation" (2019), combined
1337 : with a suffix trie for removing duplicate or redundant paths. An auxiliary
1338 : graph of the strongly connected components (SCCs) is built. Then, the prime
1339 : paths of the SCCs composes the prime paths of each SCC with the prime paths
1340 : of this auxiliary graph. This can drastically cut the number of redundant
1341 : paths generated compared to a naive algorithm.
1342 :
1343 : This does not work for all graphs. Some structures, e.g. when most of the
1344 : graph is inside a single SCC, cause the algorithm to degenerate to a naive
1345 : one. The same happens for functions with many SCCs that are either
1346 : singletons or very small. Those cases will be slower with respect to the
1347 : number of paths, but still fast enough if the path limit is kept reasonably
1348 : low (a few hundred thousand). */
1349 : vec<vec<int>>
1350 565 : prime_paths (struct graph *cfg, size_t pathlimit)
1351 : {
1352 565 : const int nscc = graphds_scc (cfg, NULL);
1353 565 : auto_graph disconnected (disconnect_sccs (cfg));
1354 565 : auto_graph ccfg (build_ccfg (cfg, nscc));
1355 565 : auto_sbitmap_vector edges (edge_matrix (cfg));
1356 :
1357 565 : auto_sbitmap seen (cfg->n_vertices);
1358 565 : auto_vec<int, 8> pathbuf {};
1359 :
1360 565 : limit_reset (pathlimit);
1361 :
1362 : /* Store an SCC-ID -> vertices mapping to quickly find the vertices that
1363 : make up a strongly connected component. */
1364 565 : auto_vec_vec sccs {};
1365 565 : sccs.safe_grow_cleared (ccfg->n_vertices);
1366 6018 : for (int i = 0; i != cfg->n_vertices; ++i)
1367 5453 : sccs[cfg->vertices[i].component].safe_push (i);
1368 :
1369 565 : auto_vec_vec_vec scc_internal_pp {};
1370 565 : scc_internal_pp.safe_grow_cleared (nscc);
1371 5520 : for (int i = 0; i != nscc; ++i)
1372 : {
1373 4958 : trie internal_pp;
1374 20300 : for (int V : sccs[i])
1375 5426 : simple_paths (disconnected, V, seen, pathbuf, internal_pp);
1376 4958 : if (limit_exceed_p (internal_pp.size ()))
1377 3 : return {};
1378 4955 : scc_internal_pp[i] = internal_pp.paths ();
1379 9910 : if (limit_checked_add (scc_internal_pp[i].length ()))
1380 0 : return {};
1381 4958 : }
1382 :
1383 562 : auto_vec<trie, 8> scc_enex_paths (nscc);
1384 562 : scc_enex_paths.safe_grow_cleared (nscc);
1385 562 : trie scc_en_paths;
1386 562 : trie scc_ex_paths;
1387 :
1388 5514 : for (int i = 0; i != ccfg->n_vertices; ++i)
1389 : {
1390 20081 : for (int Ven : sccs[i])
1391 : {
1392 5225 : if (!scc_entry_vertex_p (cfg, Ven))
1393 275 : continue;
1394 :
1395 20083 : for (int Vex : sccs[i])
1396 : {
1397 5233 : if (!scc_exit_vertex_p (cfg, Vex))
1398 244 : continue;
1399 4989 : scc_entry_exit_paths (scc_internal_pp[i], Ven, Vex,
1400 : scc_enex_paths[i]);
1401 : }
1402 : }
1403 : }
1404 :
1405 5787 : for (int i = 0; i != cfg->n_vertices; ++i)
1406 : {
1407 5225 : const int scc = cfg->vertices[i].component;
1408 5225 : if (scc_entry_vertex_p (cfg, i))
1409 4950 : scc_entry_paths (scc_internal_pp[scc], i, scc_en_paths);
1410 :
1411 5225 : if (scc_exit_vertex_p (cfg, i))
1412 4985 : scc_exit_paths (scc_internal_pp[scc], i, scc_ex_paths);
1413 : }
1414 :
1415 : /* In the presence of abnormal edges (like longjmp) it is possible to have
1416 : multiple "entry points" in function -- build ccfg prime paths starting at
1417 : any vertex without predecessor. For most graphs this will only be the
1418 : ENTRY_BLOCK. */
1419 562 : trie ccfg_prime_paths;
1420 5514 : for (int i = 0; i != ccfg->n_vertices; ++i)
1421 4952 : if (!ccfg->vertices[i].pred)
1422 1208 : simple_paths (ccfg, i, seen, pathbuf, ccfg_prime_paths);
1423 562 : if (limit_exceed_p (ccfg_prime_paths.size ()))
1424 0 : return {};
1425 :
1426 562 : trie complete_prime_paths = cfg_complete_prime_paths (edges, scc_enex_paths,
1427 562 : ccfg_prime_paths);
1428 562 : if (limit_checked_add (complete_prime_paths.size ()))
1429 0 : return {};
1430 562 : trie exit_prime_paths = scc_exit_prime_paths (cfg, scc_ex_paths,
1431 562 : complete_prime_paths);
1432 562 : if (limit_checked_add (exit_prime_paths.size ()))
1433 0 : return {};
1434 562 : trie entry_prime_paths = scc_entry_prime_paths (cfg, scc_en_paths,
1435 : complete_prime_paths,
1436 562 : exit_prime_paths);
1437 562 : if (limit_checked_add (entry_prime_paths.size ()))
1438 0 : return {};
1439 :
1440 562 : trie &merged = merge (complete_prime_paths, entry_prime_paths,
1441 : exit_prime_paths, scc_internal_pp);
1442 562 : if (merged.size () > pathlimit)
1443 0 : return {};
1444 :
1445 562 : return merged.paths ();
1446 565 : }
1447 :
1448 : #if CHECKING_P
1449 :
1450 : namespace selftest
1451 : {
1452 :
1453 : /* Check if the trie contains PATH. */
1454 : static bool
1455 108 : contains (const trie &trie, array_slice<const int> path)
1456 : {
1457 108 : size_t index = 0;
1458 692 : for (int id : path)
1459 : {
1460 584 : const trie_node ¤t = trie.vertices[index];
1461 584 : if (!current.inserted)
1462 : return false;
1463 584 : const auto *xp = current.get (id);
1464 584 : if (!xp)
1465 : return false;
1466 584 : index = xp->val;
1467 : }
1468 108 : return trie.vertices[index].inserted && trie.vertices[index].endofpath;
1469 : }
1470 :
1471 : static bool
1472 1320 : equal_p (array_slice<const int> lhs, array_slice<const int> rhs)
1473 : {
1474 1320 : if (lhs.size () != rhs.size ())
1475 : return false;
1476 :
1477 600 : size_t length = lhs.size ();
1478 1420 : for (size_t i = 0; i != length; ++i)
1479 1252 : if (lhs[i] != rhs[i])
1480 : return false;
1481 : return true;
1482 : }
1483 :
1484 : static bool
1485 168 : any_equal_p (const array_slice<const int> &needle,
1486 : const vec<vec<int>> &haystack)
1487 : {
1488 1656 : for (const vec<int> &x : haystack)
1489 2640 : if (equal_p (needle, array_slice <const int> (x)))
1490 : return true;
1491 : return false;
1492 : }
1493 :
1494 : static size_t
1495 28 : count (const trie &trie)
1496 : {
1497 28 : size_t n = 0;
1498 28 : auto_vec<int> path {};
1499 28 : auto iter = trie.paths (path);
1500 136 : while (iter.next ())
1501 108 : n += 1;
1502 28 : return n;
1503 28 : }
1504 :
1505 : static vec<vec<int>>
1506 48 : simple_paths (struct graph *cfg, trie &trie, int root = 0)
1507 : {
1508 48 : auto_sbitmap seen (cfg->n_vertices);
1509 48 : auto_vec<int> path;
1510 48 : simple_paths (cfg, root, seen, path, trie);
1511 48 : return trie.paths ();
1512 48 : }
1513 :
1514 : /* Create a CFG that roughly corresponds to this program:
1515 :
1516 : int binary_search(int a[], int len, int from, int to, int key)
1517 : {
1518 : int low = from;
1519 : int high = to - 1;
1520 :
1521 : while (low <= high)
1522 : {
1523 : int mid = (low + high) >> 1;
1524 : long midVal = a[mid];
1525 :
1526 : if (midVal < key)
1527 : low = mid + 1;
1528 : else if (midVal > key)
1529 : high = mid - 1;
1530 : else
1531 : return mid; // key found
1532 : }
1533 : return -1;
1534 : }
1535 :
1536 : This program would emit a CFG very similar to the CFG used by Fazli &
1537 : Afsharchi (2019). The selftest cases are built from the partial paths used
1538 : in that paper. */
1539 : static struct graph*
1540 24 : binary_search_cfg ()
1541 : {
1542 24 : struct graph *g = new_graph (11);
1543 24 : add_edge (g, 0, 1);
1544 24 : add_edge (g, 1, 2);
1545 24 : add_edge (g, 2, 3);
1546 24 : add_edge (g, 2, 4);
1547 24 : add_edge (g, 3, 10);
1548 24 : add_edge (g, 4, 5);
1549 24 : add_edge (g, 4, 6);
1550 24 : add_edge (g, 5, 7);
1551 24 : add_edge (g, 6, 8);
1552 24 : add_edge (g, 6, 9);
1553 24 : add_edge (g, 7, 2);
1554 24 : add_edge (g, 8, 10);
1555 24 : add_edge (g, 9, 7);
1556 24 : graphds_scc (g, NULL);
1557 24 : return g;
1558 : }
1559 :
1560 : /* Test a full run of the algorithm against a known graph (binary-search). */
1561 : static void
1562 4 : test_prime_paths ()
1563 : {
1564 4 : auto_graph g (binary_search_cfg ());
1565 4 : vec<vec<int>> paths = prime_paths (g, 100);
1566 4 : const int p01[] = { 0, 1, 2, 3, 10 };
1567 4 : const int p02[] = { 0, 1, 2, 4, 6, 8, 10 };
1568 4 : const int p03[] = { 5, 7, 2, 4, 6, 9 };
1569 4 : const int p04[] = { 4, 6, 9, 7, 2, 4 };
1570 4 : const int p05[] = { 2, 4, 6, 9, 7, 2 };
1571 4 : const int p06[] = { 6, 9, 7, 2, 4, 6 };
1572 4 : const int p07[] = { 9, 7, 2, 4, 6, 9 };
1573 4 : const int p08[] = { 7, 2, 4, 6, 9, 7 };
1574 4 : const int p09[] = { 6, 9, 7, 2, 4, 5 };
1575 4 : const int p10[] = { 4, 5, 7, 2, 4 };
1576 4 : const int p11[] = { 2, 4, 5, 7, 2 };
1577 4 : const int p12[] = { 5, 7, 2, 4, 5 };
1578 4 : const int p13[] = { 7, 2, 4, 5, 7 };
1579 4 : const int p14[] = { 4, 6, 9, 7, 2, 3, 10 };
1580 4 : const int p15[] = { 5, 7, 2, 4, 6, 8, 10 };
1581 4 : const int p16[] = { 9, 7, 2, 4, 6, 8, 10 };
1582 4 : const int p17[] = { 4, 5, 7, 2, 3, 10 };
1583 4 : const int p18[] = { 0, 1, 2, 4, 6, 9, 7 };
1584 4 : const int p19[] = { 0, 1, 2, 4, 5, 7 };
1585 :
1586 4 : ASSERT_EQ (paths.length (), 19);
1587 4 : ASSERT_TRUE (any_equal_p (p01, paths));
1588 4 : ASSERT_TRUE (any_equal_p (p02, paths));
1589 4 : ASSERT_TRUE (any_equal_p (p03, paths));
1590 4 : ASSERT_TRUE (any_equal_p (p04, paths));
1591 4 : ASSERT_TRUE (any_equal_p (p05, paths));
1592 4 : ASSERT_TRUE (any_equal_p (p06, paths));
1593 4 : ASSERT_TRUE (any_equal_p (p07, paths));
1594 4 : ASSERT_TRUE (any_equal_p (p08, paths));
1595 4 : ASSERT_TRUE (any_equal_p (p09, paths));
1596 4 : ASSERT_TRUE (any_equal_p (p10, paths));
1597 4 : ASSERT_TRUE (any_equal_p (p11, paths));
1598 4 : ASSERT_TRUE (any_equal_p (p12, paths));
1599 4 : ASSERT_TRUE (any_equal_p (p13, paths));
1600 4 : ASSERT_TRUE (any_equal_p (p14, paths));
1601 4 : ASSERT_TRUE (any_equal_p (p15, paths));
1602 4 : ASSERT_TRUE (any_equal_p (p16, paths));
1603 4 : ASSERT_TRUE (any_equal_p (p17, paths));
1604 4 : ASSERT_TRUE (any_equal_p (p18, paths));
1605 4 : ASSERT_TRUE (any_equal_p (p19, paths));
1606 4 : release_vec_vec (paths);
1607 4 : }
1608 :
1609 : /* The strongly connected component graph for binary_search looks like
1610 : this, using the vertex numbers from the original graph:
1611 :
1612 : START
1613 : |
1614 : 1
1615 : |
1616 : 2 (SCC)
1617 : / \
1618 : 3 8
1619 : \ /
1620 : END
1621 :
1622 : The components gets renumbered by graphds_scc, so the ccfg looks like
1623 : this. The actual numbers don't matter as long as the structure of the
1624 : graph is preserved, and this test is now sensitive to the numbering set
1625 : by graphds_scc. It does not have to be - if that function should reverse
1626 : the numbering this test must be updated.
1627 :
1628 : 5
1629 : |
1630 : 4
1631 : |
1632 : 3 (SCC)
1633 : / \
1634 : 2 1
1635 : \ /
1636 : 0
1637 : */
1638 : static void
1639 4 : test_build_ccfg ()
1640 : {
1641 4 : auto_graph cfg (binary_search_cfg ());
1642 4 : const int nscc = graphds_scc (cfg, NULL);
1643 4 : auto_graph ccfg (build_ccfg (cfg, nscc));
1644 4 : ASSERT_EQ (6, nscc);
1645 :
1646 8 : ASSERT_TRUE (edge_p (ccfg, 5, 4));
1647 8 : ASSERT_TRUE (edge_p (ccfg, 4, 3));
1648 8 : ASSERT_TRUE (edge_p (ccfg, 3, 2));
1649 8 : ASSERT_TRUE (edge_p (ccfg, 3, 1));
1650 8 : ASSERT_TRUE (edge_p (ccfg, 2, 0));
1651 8 : ASSERT_TRUE (edge_p (ccfg, 1, 0));
1652 4 : }
1653 :
1654 : /* This test checks some basic assumptions on finding the strongly connected
1655 : components and disconnecting the graph by removing all edges between SCCs.
1656 : Creating a single auxiliary graph simplifies the bookkeeping. */
1657 : static void
1658 4 : test_split_components ()
1659 : {
1660 4 : auto_graph cfg (binary_search_cfg ());
1661 4 : int nscc = graphds_scc (cfg, NULL);
1662 4 : auto_graph ccfg (disconnect_sccs (cfg));
1663 :
1664 4 : auto_vec_vec entries {};
1665 4 : auto_vec_vec exits {};
1666 4 : entries.safe_grow_cleared (nscc);
1667 4 : exits.safe_grow_cleared (nscc);
1668 :
1669 48 : for (int i = 0; i != cfg->n_vertices; ++i)
1670 : {
1671 44 : if (scc_entry_vertex_p (cfg, i))
1672 24 : entries[cfg->vertices[i].component].safe_push (i);
1673 44 : if (scc_exit_vertex_p (cfg, i))
1674 28 : exits[cfg->vertices[i].component].safe_push (i);
1675 : }
1676 :
1677 4 : const int p10[] = { 10 };
1678 4 : const int p08[] = { 8 };
1679 4 : const int p03[] = { 3 };
1680 4 : const int p02[] = { 2 };
1681 4 : const int p01[] = { 1 };
1682 4 : const int p00[] = { 0 };
1683 4 : const int p26[] = { 2, 6 };
1684 :
1685 4 : ASSERT_EQ (entries.length (), 6);
1686 4 : ASSERT_TRUE (any_equal_p (p10, entries));
1687 4 : ASSERT_TRUE (any_equal_p (p08, entries));
1688 4 : ASSERT_TRUE (any_equal_p (p03, entries));
1689 4 : ASSERT_TRUE (any_equal_p (p02, entries));
1690 4 : ASSERT_TRUE (any_equal_p (p01, entries));
1691 4 : ASSERT_TRUE (any_equal_p (p00, entries));
1692 :
1693 4 : ASSERT_EQ (exits.length (), 6);
1694 4 : ASSERT_TRUE (any_equal_p (p10, exits));
1695 4 : ASSERT_TRUE (any_equal_p (p08, exits));
1696 4 : ASSERT_TRUE (any_equal_p (p03, exits));
1697 4 : ASSERT_TRUE (any_equal_p (p26, exits));
1698 4 : ASSERT_TRUE (any_equal_p (p01, exits));
1699 4 : ASSERT_TRUE (any_equal_p (p00, exits));
1700 :
1701 : /* The result of disconnect_sccs () disconnects the graph into its strongly
1702 : connected components. The subgraphs are either singletons (a single
1703 : vertex with no edges) or graphs with cycles. The SCC internal prime
1704 : paths can be found by running a DFS from every SCC vertex, terminating
1705 : on a duplicated vertex. This may create some redundant paths still,
1706 : which must be filtered out.
1707 :
1708 : Singletons can either be detected and skipped (requires counting the
1709 : components) or filtered after. For this test case they are skipped
1710 : because other graph inconsistencies are easier to detect. */
1711 :
1712 : /* Count and check singleton components. */
1713 4 : auto_vec<int> scc_size {};
1714 4 : scc_size.safe_grow_cleared (nscc);
1715 48 : for (int i = 0; i != cfg->n_vertices; ++i)
1716 44 : scc_size[cfg->vertices[i].component]++;
1717 4 : ASSERT_EQ (nscc, 6);
1718 4 : ASSERT_EQ (scc_size[0], 1);
1719 4 : ASSERT_EQ (scc_size[1], 1);
1720 4 : ASSERT_EQ (scc_size[2], 1);
1721 4 : ASSERT_EQ (scc_size[3], 6);
1722 4 : ASSERT_EQ (scc_size[4], 1);
1723 4 : ASSERT_EQ (scc_size[5], 1);
1724 :
1725 : /* Manually unroll the loop finding the simple paths starting at the
1726 : vertices in the SCCs. In this case there is only the one SCC. */
1727 4 : trie ccfg_paths;
1728 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 2));
1729 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 4));
1730 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 5));
1731 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 6));
1732 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 7));
1733 4 : auto_vec_vec (simple_paths (ccfg, ccfg_paths, 9));
1734 : /* Then in+out of trie. */
1735 4 : auto_vec_vec xscc_internal_pp = ccfg_paths.paths ();
1736 4 : trie scc_internal_pp;
1737 60 : for (auto &p : xscc_internal_pp)
1738 96 : scc_internal_pp.insert_with_suffix (p);
1739 :
1740 4 : const int pp01[] = { 5, 7, 2, 4, 6, 9 };
1741 4 : const int pp02[] = { 4, 5, 7, 2, 4 };
1742 4 : const int pp03[] = { 4, 6, 9, 7, 2, 4 };
1743 4 : const int pp04[] = { 2, 4, 5, 7, 2 };
1744 4 : const int pp05[] = { 2, 4, 6, 9, 7, 2 };
1745 4 : const int pp06[] = { 5, 7, 2, 4, 5 };
1746 4 : const int pp07[] = { 6, 9, 7, 2, 4, 6 };
1747 4 : const int pp08[] = { 7, 2, 4, 5, 7 };
1748 4 : const int pp09[] = { 9, 7, 2, 4, 6, 9 };
1749 4 : const int pp10[] = { 7, 2, 4, 6, 9, 7 };
1750 4 : const int pp11[] = { 6, 9, 7, 2, 4, 5 };
1751 :
1752 4 : ASSERT_EQ (count (scc_internal_pp), 11);
1753 4 : ASSERT_TRUE (contains (scc_internal_pp, pp01));
1754 4 : ASSERT_TRUE (contains (scc_internal_pp, pp02));
1755 4 : ASSERT_TRUE (contains (scc_internal_pp, pp03));
1756 4 : ASSERT_TRUE (contains (scc_internal_pp, pp04));
1757 4 : ASSERT_TRUE (contains (scc_internal_pp, pp05));
1758 4 : ASSERT_TRUE (contains (scc_internal_pp, pp06));
1759 4 : ASSERT_TRUE (contains (scc_internal_pp, pp07));
1760 4 : ASSERT_TRUE (contains (scc_internal_pp, pp08));
1761 4 : ASSERT_TRUE (contains (scc_internal_pp, pp09));
1762 4 : ASSERT_TRUE (contains (scc_internal_pp, pp10));
1763 4 : ASSERT_TRUE (contains (scc_internal_pp, pp11));
1764 4 : }
1765 :
1766 : /* The remaining tests deconstructs the algorithm and runs only a single phase
1767 : with good inputs at that point. This makes it easier to pinpoint where
1768 : things go wrong, and helps show in steps how the algorithm works and the
1769 : phases relate.
1770 :
1771 : The phases and their inputs and outputs are bazed on Fazli & Afshsarchi. */
1772 :
1773 : static void
1774 4 : test_scc_internal_prime_paths ()
1775 : {
1776 : /* This graph has only the SCC subgraph. The result of running prime-paths
1777 : on it should be the SCC internal prime paths of the full graph. */
1778 4 : auto_graph scc (new_graph (11));
1779 4 : add_edge (scc, 0, 2);
1780 4 : add_edge (scc, 2, 4);
1781 4 : add_edge (scc, 4, 5);
1782 4 : add_edge (scc, 4, 6);
1783 4 : add_edge (scc, 5, 7);
1784 4 : add_edge (scc, 6, 9);
1785 4 : add_edge (scc, 9, 7);
1786 4 : add_edge (scc, 7, 2);
1787 :
1788 4 : auto_vec_vec paths = prime_paths (scc, 100);
1789 4 : const int p01[] = { 5, 7, 2, 4, 6, 9 };
1790 4 : const int p02[] = { 4, 6, 9, 7, 2, 4 };
1791 4 : const int p03[] = { 2, 4, 6, 9, 7, 2 };
1792 4 : const int p04[] = { 6, 9, 7, 2, 4, 6 };
1793 4 : const int p05[] = { 9, 7, 2, 4, 6, 9 };
1794 4 : const int p06[] = { 7, 2, 4, 6, 9, 7 };
1795 4 : const int p07[] = { 6, 9, 7, 2, 4, 5 };
1796 4 : const int p08[] = { 4, 5, 7, 2, 4 };
1797 4 : const int p09[] = { 2, 4, 5, 7, 2 };
1798 4 : const int p10[] = { 5, 7, 2, 4, 5 };
1799 4 : const int p11[] = { 7, 2, 4, 5, 7 };
1800 :
1801 4 : ASSERT_TRUE (any_equal_p (p01, paths));
1802 4 : ASSERT_TRUE (any_equal_p (p02, paths));
1803 4 : ASSERT_TRUE (any_equal_p (p03, paths));
1804 4 : ASSERT_TRUE (any_equal_p (p04, paths));
1805 4 : ASSERT_TRUE (any_equal_p (p05, paths));
1806 4 : ASSERT_TRUE (any_equal_p (p06, paths));
1807 4 : ASSERT_TRUE (any_equal_p (p07, paths));
1808 4 : ASSERT_TRUE (any_equal_p (p08, paths));
1809 4 : ASSERT_TRUE (any_equal_p (p09, paths));
1810 4 : ASSERT_TRUE (any_equal_p (p10, paths));
1811 4 : ASSERT_TRUE (any_equal_p (p11, paths));
1812 4 : }
1813 :
1814 : /* Test the entry/exit path helpers for the strongly connected component in
1815 : binary_search. The SCC has one entry (2, the loop header) and two exits (2,
1816 : 6, the loop exit and return). */
1817 : static void
1818 4 : test_scc_entry_exit_paths ()
1819 : {
1820 4 : auto_graph scc (new_graph (11));
1821 4 : add_edge (scc, 2, 4);
1822 4 : add_edge (scc, 4, 5);
1823 4 : add_edge (scc, 4, 6);
1824 4 : add_edge (scc, 5, 7);
1825 4 : add_edge (scc, 6, 9);
1826 4 : add_edge (scc, 9, 7);
1827 4 : add_edge (scc, 7, 2);
1828 :
1829 4 : trie scc_internal_trie;
1830 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 2));
1831 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 4));
1832 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 5));
1833 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 6));
1834 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 7));
1835 4 : auto_vec_vec (simple_paths (scc, scc_internal_trie, 9));
1836 4 : auto_vec_vec scc_prime_paths = scc_internal_trie.paths ();
1837 :
1838 4 : trie entry_exits {};
1839 4 : scc_entry_exit_paths (scc_prime_paths, 2, 2, entry_exits);
1840 4 : scc_entry_exit_paths (scc_prime_paths, 2, 6, entry_exits);
1841 :
1842 4 : const int p01[] = { 2 };
1843 4 : const int p02[] = { 2, 4, 6 };
1844 :
1845 4 : ASSERT_EQ (count (entry_exits), 2);
1846 4 : ASSERT_TRUE (contains (entry_exits, p01));
1847 4 : ASSERT_TRUE (contains (entry_exits, p02));
1848 :
1849 4 : trie exits;
1850 4 : scc_exit_paths (scc_prime_paths, 2, exits);
1851 4 : scc_exit_paths (scc_prime_paths, 6, exits);
1852 :
1853 4 : const int p03[] = { 4, 6, 9, 7, 2 };
1854 4 : const int p04[] = { 5, 7, 2, 4, 6 };
1855 4 : const int p05[] = { 9, 7, 2, 4, 6 };
1856 4 : const int p06[] = { 4, 5, 7, 2 };
1857 :
1858 4 : ASSERT_EQ (count (exits), 4);
1859 4 : ASSERT_TRUE (contains (exits, p03));
1860 4 : ASSERT_TRUE (contains (exits, p04));
1861 4 : ASSERT_TRUE (contains (exits, p05));
1862 4 : ASSERT_TRUE (contains (exits, p06));
1863 :
1864 4 : trie entries;
1865 4 : scc_entry_paths (scc_prime_paths, 2, entries);
1866 :
1867 4 : const int p07[] = { 2, 4, 6, 9, 7 };
1868 4 : const int p08[] = { 2, 4, 5, 7 };
1869 4 : ASSERT_EQ (count (entries), 2);
1870 4 : ASSERT_TRUE (contains (entries, p07));
1871 4 : ASSERT_TRUE (contains (entries, p08));
1872 4 : }
1873 :
1874 : static void
1875 4 : test_complete_prime_paths ()
1876 : {
1877 4 : const int ccfgpp0[] = { 0, 1, 2, 3, 5 };
1878 4 : const int ccfgpp1[] = { 0, 1, 2, 4, 5 };
1879 4 : trie ccfg_prime_paths {};
1880 4 : ccfg_prime_paths.insert (ccfgpp0);
1881 4 : ccfg_prime_paths.insert (ccfgpp1);
1882 :
1883 4 : const int scc0[] = { 2 };
1884 4 : const int scc1[] = { 2, 4, 6 };
1885 :
1886 4 : const int ccfg_single[] = { 0, 1, 3, 8, 10 };
1887 :
1888 4 : auto_graph cfg (binary_search_cfg ());
1889 4 : auto_sbitmap_vector edges (sbitmap_vector_alloc (cfg->n_vertices,
1890 4 : cfg->n_vertices));
1891 4 : bitmap_vector_clear (edges, cfg->n_vertices);
1892 48 : for (int i = 0; i != cfg->n_vertices; ++i)
1893 96 : for (graph_edge *e = cfg->vertices[i].succ; e; e = e->succ_next)
1894 52 : bitmap_set_bit (edges[e->src], e->dest);
1895 :
1896 4 : auto_vec<trie> ccfg_paths {};
1897 4 : ccfg_paths.safe_grow_cleared (6);
1898 4 : ccfg_paths[0].insert (array_slice <const int> (ccfg_single + 0, 1));
1899 4 : ccfg_paths[1].insert (array_slice <const int> (ccfg_single + 1, 1));
1900 4 : ccfg_paths[3].insert (array_slice <const int> (ccfg_single + 2, 1));
1901 4 : ccfg_paths[4].insert (array_slice <const int> (ccfg_single + 3, 1));
1902 4 : ccfg_paths[5].insert (array_slice <const int> (ccfg_single + 4, 1));
1903 :
1904 : /* The paths for the SCC would need to be updated in ccfg pre pass. This
1905 : feels like a clumsy interface and should maybe be disconnected from the
1906 : struct graph. */
1907 4 : ccfg_paths[2].hard_insert (scc0);
1908 4 : ccfg_paths[2].hard_insert (scc1);
1909 :
1910 4 : trie cpp = cfg_complete_prime_paths (edges, ccfg_paths, ccfg_prime_paths);
1911 :
1912 4 : const int p01[] = { 0, 1, 2, 3, 10 };
1913 4 : const int p02[] = { 0, 1, 2, 4, 6, 8, 10 };
1914 :
1915 4 : ASSERT_EQ (count (cpp), 2);
1916 4 : ASSERT_TRUE (contains (cpp, p01));
1917 4 : ASSERT_TRUE (contains (cpp, p02));
1918 4 : }
1919 :
1920 : static vec<int>
1921 4 : binary_search_scc_map ()
1922 : {
1923 4 : vec<int> sccs {};
1924 4 : sccs.safe_grow (11);
1925 4 : sccs[0] = 0;
1926 4 : sccs[1] = 1;
1927 4 : sccs[2] = 2;
1928 4 : sccs[3] = 3;
1929 4 : sccs[4] = 2;
1930 4 : sccs[5] = 2;
1931 4 : sccs[6] = 2;
1932 4 : sccs[7] = 2;
1933 4 : sccs[8] = 4;
1934 4 : sccs[9] = 2;
1935 4 : sccs[10] = 5;
1936 4 : return sccs;
1937 : }
1938 :
1939 : static void
1940 4 : test_exit_prime_paths ()
1941 : {
1942 4 : const int cpp01[] = { 0, 1, 2, 3, 10 };
1943 4 : const int cpp02[] = { 0, 1, 2, 4, 6, 8, 10 };
1944 4 : trie complete_prime_paths {};
1945 4 : complete_prime_paths.insert_with_suffix (cpp01);
1946 4 : complete_prime_paths.insert_with_suffix (cpp02);
1947 :
1948 4 : const int ep01[] = { 4, 6, 9, 7, 2 };
1949 4 : const int ep02[] = { 5, 7, 2, 4, 6 };
1950 4 : const int ep03[] = { 9, 7, 2, 4, 6 };
1951 4 : const int ep04[] = { 4, 5, 7, 2 };
1952 4 : trie exit_paths;
1953 4 : exit_paths.insert (ep01);
1954 4 : exit_paths.insert (ep02);
1955 4 : exit_paths.insert (ep03);
1956 4 : exit_paths.insert (ep04);
1957 :
1958 4 : auto_graph cfg (binary_search_cfg ());
1959 4 : trie epp = scc_exit_prime_paths (cfg, exit_paths, complete_prime_paths);
1960 :
1961 4 : const int pp01[] = { 4, 6, 9, 7, 2, 3, 10 };
1962 4 : const int pp02[] = { 5, 7, 2, 4, 6, 8, 10 };
1963 4 : const int pp03[] = { 9, 7, 2, 4, 6, 8, 10 };
1964 4 : const int pp04[] = { 4, 5, 7, 2, 3, 10 };
1965 :
1966 4 : ASSERT_EQ (count (epp), 4);
1967 4 : ASSERT_TRUE (contains (epp, pp01));
1968 4 : ASSERT_TRUE (contains (epp, pp02));
1969 4 : ASSERT_TRUE (contains (epp, pp03));
1970 4 : ASSERT_TRUE (contains (epp, pp04));
1971 4 : }
1972 :
1973 : static void
1974 4 : test_entry_prime_paths ()
1975 : {
1976 4 : auto_graph cfg (binary_search_cfg ());
1977 :
1978 4 : static int sccep01[] = { 2, 4, 6, 9, 7 };
1979 4 : static int sccep02[] = { 2, 4, 5, 7 };
1980 4 : trie scc_entry_paths;
1981 4 : scc_entry_paths.insert (sccep01);
1982 4 : scc_entry_paths.insert (sccep02);
1983 :
1984 4 : const int cpp01[] = { 0, 1, 2, 3, 10 };
1985 4 : const int cpp02[] = { 0, 1, 2, 4, 6, 8, 10 };
1986 4 : trie complete_prime_paths {};
1987 4 : complete_prime_paths.insert (cpp01);
1988 4 : complete_prime_paths.insert (cpp02);
1989 :
1990 4 : const int ep01[] = { 4, 6, 9, 7, 2, 3, 10 };
1991 4 : const int ep02[] = { 5, 7, 2, 4, 6, 8, 10 };
1992 4 : const int ep03[] = { 9, 7, 2, 4, 6, 8, 10 };
1993 4 : const int ep04[] = { 4, 5, 7, 2, 3, 10 };
1994 4 : trie exit_prime_paths {};
1995 4 : exit_prime_paths.insert (ep01);
1996 4 : exit_prime_paths.insert (ep02);
1997 4 : exit_prime_paths.insert (ep03);
1998 4 : exit_prime_paths.insert (ep04);
1999 :
2000 4 : auto_vec<int> sccs = binary_search_scc_map ();
2001 :
2002 4 : trie epp = scc_entry_prime_paths (cfg, scc_entry_paths,
2003 : complete_prime_paths,
2004 4 : exit_prime_paths);
2005 :
2006 : /* The 0 (start node) does not show up in the Fazli & Afsharchi paper and
2007 : kinda, but has no real impact on the result. The prime-paths functions
2008 : do not care about these vertices, but the path-coverage instrumentation
2009 : filters out the ENTRY/EXIT blocks from all the paths. */
2010 4 : const int pp01[] = { 0, 1, 2, 4, 6, 9, 7 };
2011 4 : const int pp02[] = { 0, 1, 2, 4, 5, 7 };
2012 4 : ASSERT_EQ (count (epp), 2);
2013 4 : ASSERT_TRUE (contains (epp, pp01));
2014 4 : ASSERT_TRUE (contains (epp, pp02));
2015 4 : }
2016 :
2017 : /* A straight-line graph with one vertex should yield a single path of length 1
2018 : with just the non-exit non-entry node in it. */
2019 : void
2020 4 : test_singleton_path ()
2021 : {
2022 4 : auto_graph cfg (new_graph (3));
2023 4 : add_edge (cfg, 0, 2);
2024 4 : add_edge (cfg, 2, 1);
2025 4 : auto_vec_vec paths = prime_paths (cfg, 100);
2026 :
2027 4 : ASSERT_EQ (paths.length (), 1);
2028 4 : ASSERT_EQ (paths[0].length (), 3);
2029 4 : ASSERT_EQ (paths[0][0], 0);
2030 4 : ASSERT_EQ (paths[0][1], 2);
2031 4 : ASSERT_EQ (paths[0][2], 1);
2032 4 : }
2033 :
2034 : void
2035 4 : path_coverage_cc_tests ()
2036 : {
2037 4 : limit_reset (250000);
2038 4 : test_prime_paths ();
2039 4 : test_build_ccfg ();
2040 4 : test_split_components ();
2041 4 : test_scc_internal_prime_paths ();
2042 4 : test_scc_entry_exit_paths ();
2043 4 : test_complete_prime_paths ();
2044 4 : test_exit_prime_paths ();
2045 4 : test_entry_prime_paths ();
2046 4 : test_singleton_path ();
2047 4 : }
2048 :
2049 : } // namespace selftest
2050 :
2051 : #endif /* #if CHECKING_P */
|
