prime-paths.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "obstack.h"
#include "sbitmap.h"
#include "vec.h"
#include "graphds.h"
#include "selftest.h"

Include dependency graph for prime-paths.cc:

Functions
vec< vec< int > >	prime_paths (struct graph *cfg, size_t pathlimit)

Function Documentation

prime_paths()

vec< vec< int > > prime_paths	(	struct graph *	cfg,
		size_t	pathlimit )

Find the prime paths for CFG.  The search gives up after approximate
PATHLIMIT probable paths have been generated to address path explosions.
The PATHLIMIT flag is typically controlled by -fpath-coverage-limit.  This
function is a part of -fpath-coverage and will also be called from gcov.
The paths are returned in lexicographical order based on node (basic block)
ID.  If the path limit was exceeded, an empty vector is returned.

A simple path is a path where all vertices are unique, except possibly the
first and last.  A prime path is a maximal-length simple path which is not a
part of any other simple path.  Prime paths strike a good balance between
coverage thoroughness, loops (requiring them to be taken and skipped), and
number of paths.

The algorithm is based on Fazli & Afsharchi's "A Time and Space-Efficient
Compositional Method for Prime and Test Paths Generation" (2019), combined
with a suffix trie for removing duplicate or redundant paths.  An auxillary
graph of the strongly connected components (SCCs) is built.  Then, the prime
paths of the SCCs composes the prime paths of each SCC with the prime paths
of this auxillary graph.  This can drastically cut the number of redundant
paths generated compared to a naive algorithm.

This does not work for all graphs.  Some structures, e.g. when most of the
graph is inside a single SCC, cause the algorithm to degenerate to a naive
one.  The same happens for functions with many SCCs that are either
singletons or very small.  Those cases will be slower with respect to the
number of paths, but still fast enough if the path limit is kept reasonably
low (a few hundred thousand).   

References vertex::component, graphds_scc(), i, graph::n_vertices, NULL, and graph::vertices.

Referenced by find_prime_paths().