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