#include "config.h"#include "system.h"#include "coretypes.h"#include "diagnostic-core.h"#include "memmodel.h"#include "target.h"#include "function.h"#include "basic-block.h"#include "tree.h"#include "tree-cfg.h"#include "tree-nested.h"#include "cfg.h"#include "gimple.h"#include "gimple-iterator.h"#include "gimplify.h"#include "coverage.h"#include "ssa.h"#include "vec.h"#include "sbitmap.h"#include "graphds.h"#include "hash-map.h"#include "bitmap.h"#include "cfganal.h"
Functions | |
| bool | mark_dfs_back_edges (struct function *) |
| vec< vec< int > > | prime_paths (struct graph *, size_t) |
| unsigned | instrument_prime_paths (struct function *fn) |
Function Documentation
◆ instrument_prime_paths()
| unsigned instrument_prime_paths | ( | struct function * | fn | ) |
Instrument FN for prime path coverage, enabled by -fpath-coverage. The number of paths grows very fast with the complexity (control flow) which explodes compile times and object file size. Giving up is controlled by the -fpath-coverage-limit flag. The paths are sorted lexicographically by basic block id, and each path is identified by its index in the sorted set of paths, which in turn corresponds to a bit in a large bitset associated with FN. The monitoring code is a few bitwise operations added to edges and basic blocks to maintain a set of live paths (note that many paths may overlap and that many paths may be covered by the same input). When reaching the final vertex of a path the global counters are updated. This is made more complicated by the gcov type having very limited size. To support functions with more than 32/64 paths the bitmap is implemented on top of a sequence of gcov integers, "buckets", where path N is recorded as bit N%64 in bucket N/64. For large functions, an individual basic block will only be part of a small subset of paths, and by extension buckets and local counters. Only the necessary counters are read and written.
References add_phi_arg(), BASIC_BLOCK_FOR_FN, bb_has_abnormal_pred(), build_all_ones_cst(), build_int_cst(), builtin_decl_explicit(), coverage_counter_alloc(), create_phi_node(), find_prime_paths(), function::function_start_locus, gcc_assert, gcc_checking_assert, gcov_type_node, hash_map< KeyId, Value, Traits >::get(), get_gcov_type(), hash_map< KeyId, Value, Traits >::get_or_insert(), gimple_build_assign(), gsi_after_labels(), gsi_insert_on_edge(), i, last, make_ssa_name(), mark_dfs_back_edges(), path, basic_block_def::preds, PROFILE_UPDATE_ATOMIC, hash_map< KeyId, Value, Traits >::put(), release_vec_vec(), single_pred(), single_pred_p(), single_succ_p(), todo, tree_to_uhwi(), TYPE_PRECISION, UNKNOWN_LOCATION, and warning_at().
Referenced by branch_prob().
◆ mark_dfs_back_edges()
Calculate prime path coverage. Copyright (C) 2024-2025 Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see <http://www.gnu.org/licenses/>.
Mark the back edges in DFS traversal. Return nonzero if a loop (natural or otherwise) is present. Inspired by Depth_First_Search_PP described in: Advanced Compiler Design and Implementation Steven Muchnick Morgan Kaufmann, 1997 and heavily borrowed from pre_and_rev_post_order_compute.
References bitmap_bit_p, bitmap_clear(), bitmap_set_bit, EDGE_COUNT, ei_edge(), ei_next(), ei_one_before_end_p(), ei_start, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, basic_block_def::flags, free(), basic_block_def::index, last_basic_block_for_fn, n_basic_blocks_for_fn, basic_block_def::succs, and visited.
Referenced by execute_split_paths(), and finite_function_p().
◆ prime_paths()
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().
