GCC Middle and Back End API Reference
profile.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "cgraph.h"
#include "coverage.h"
#include "diagnostic-core.h"
#include "cfganal.h"
#include "value-prof.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "dumpfile.h"
#include "cfgloop.h"
#include "sreal.h"
#include "file-prefix-map.h"
#include "profile.h"
Include dependency graph for profile.cc:

Data Structures

struct  bb_profile_info
 
struct  bb_stats
 
struct  location_triplet
 
struct  location_triplet_hash
 

Macros

#define BB_INFO(b)   ((struct bb_profile_info *) (b)->aux)
 

Functions

struct condcovfind_conditions (struct function *)
 
size_t cov_length (const struct condcov *)
 
array_slice< basic_blockcov_blocks (struct condcov *, size_t)
 
array_slice< uint64_tcov_masks (struct condcov *, size_t)
 
array_slice< sbitmapcov_maps (struct condcov *cov, size_t n)
 
void cov_free (struct condcov *)
 
size_t instrument_decisions (array_slice< basic_block >, size_t, array_slice< sbitmap >, array_slice< gcov_type_unsigned >)
 
static void find_spanning_tree (struct edge_list *)
 
static unsigned instrument_edges (struct edge_list *el)
 
static void instrument_values (histogram_values values)
 
static gcov_typeget_exec_counts (unsigned cfg_checksum, unsigned lineno_checksum)
 
static bool is_edge_inconsistent (vec< edge, va_gc > *edges)
 
static void correct_negative_edge_counts (void)
 
static bool is_inconsistent (void)
 
static void set_bb_counts (void)
 
static int read_profile_edge_counts (gcov_type *exec_counts)
 
static int cmp_stats (const void *ptr1, const void *ptr2)
 
static void compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum)
 
static void sort_hist_values (histogram_value hist)
 
static void compute_value_histograms (histogram_values values, unsigned cfg_checksum, unsigned lineno_checksum)
 
static void output_location (hash_set< location_triplet_hash > *streamed_locations, char const *file_name, int line, gcov_position_t *offset, basic_block bb)
 
static int compare_freqs (const void *p1, const void *p2)
 
void read_thunk_profile (struct cgraph_node *node)
 
void branch_prob (bool thunk)
 
static basic_block find_group (basic_block bb)
 
static void union_groups (basic_block bb1, basic_block bb2)
 
void init_branch_prob (void)
 
void end_branch_prob (void)
 

Variables

vec< gcov_typebb_gcov_counts
 
hash_map< edge, gcov_type > * edge_gcov_counts
 
gcov_summaryprofile_info
 
static int total_num_blocks
 
static int total_num_edges
 
static int total_num_edges_ignored
 
static int total_num_edges_instrumented
 
static int total_num_blocks_created
 
static int total_num_passes
 
static int total_num_times_called
 
static int total_hist_br_prob [20]
 
static int total_num_branches
 
static int total_num_conds
 

Macro Definition Documentation

◆ BB_INFO

#define BB_INFO ( b)    ((struct bb_profile_info *) (b)->aux)

Function Documentation

◆ branch_prob()

void branch_prob ( bool thunk)
Instrument and/or analyze program behavior based on program the CFG.

This function creates a representation of the control flow graph (of
the function being compiled) that is suitable for the instrumentation
of edges and/or converting measured edge counts to counts on the
complete CFG.

When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
the flow graph that are needed to reconstruct the dynamic behavior of the
flow graph.  This data is written to the gcno file for gcov.

When FLAG_PROFILE_CONDITIONS is nonzero, this functions instruments the
edges in the control flow graph to track what conditions are evaluated to in
order to determine what conditions are covered and have an independent
effect on the outcome (modified condition/decision coverage).  This data is
written to the gcno file for gcov.

When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
information from the gcda file containing edge count information from
previous executions of the function being compiled.  In this case, the
control flow graph is annotated with actual execution counts by
compute_branch_probabilities().

Main entry point of this file.   

References add_noreturn_fake_exit_edges(), alloc_aux_for_edges(), loop::any_estimate, cfun, compact_blocks(), compare_freqs(), compute_branch_probabilities(), compute_function_frequency(), compute_value_histograms(), basic_block_def::count, cov_blocks(), cov_free(), cov_length(), cov_maps(), cov_masks(), coverage_begin_function(), coverage_compute_cfg_checksum(), coverage_compute_lineno_checksum(), coverage_counter_alloc(), coverage_end_function(), create_edge_list(), curr_location, current_function_decl, DECL_SOURCE_LOCATION, dump_file, dump_flags, dump_function_to_file(), ECF_RETURNS_TWICE, EDGE_INFO, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, expand_location(), expected_loop_iterations_by_profile(), find_conditions(), find_spanning_tree(), flow_call_edges_add(), FOR_BB_BETWEEN, FOR_EACH_BB_FN, FOR_EACH_EDGE, free_aux_for_edges(), free_edge_list(), gcc_assert, gcc_checking_assert, GCOV_ARC_FAKE, GCOV_ARC_FALLTHROUGH, GCOV_ARC_ON_TREE, GCOV_TAG_ARCS, GCOV_TAG_BLOCKS, GCOV_TAG_CONDS, gcov_write_length(), gcov_write_string(), gcov_write_tag(), gcov_write_unsigned(), ggc_alloc(), gimple_call_builtin_p(), gimple_call_flags(), gimple_call_internal_fn(), gimple_call_internal_p(), gimple_filename(), gimple_find_values_to_profile(), gimple_has_location(), gimple_init_gcov_profiler(), gimple_lineno(), gimple_location(), gsi_commit_edge_inserts(), gsi_end_p(), gsi_last_nondebug_bb(), gsi_next(), gsi_prev_nondebug(), gsi_start_bb(), gsi_start_nondebug_after_labels_bb(), gsi_stmt(), loop::header, i, basic_block_def::index, INDEX_EDGE, instrument_decisions(), instrument_edges(), instrument_values(), profile_count::ipa(), is_gimple_call(), array_slice< T >::is_valid(), last, LOCATION_FILE, LOCATION_LINE, make_edge(), MAX, n_basic_blocks_for_fn, profile_count::nonzero_p(), NULL, NUM_EDGES, edge_list::num_edges, offset, output_location(), basic_block_def::preds, PROFILE_READ, profile_status_for_fn, qsort, record_niter_bound(), remove_fake_edges(), report_predictor_hitrates(), RESERVED_LOCATION_P, single_succ_edge(), single_succ_p(), split_block_after_labels(), split_edge(), basic_block_def::succs, TDF_DETAILS, total_num_blocks, total_num_conds, total_num_edges, total_num_edges_ignored, total_num_edges_instrumented, and total_num_times_called.

Referenced by tree_profiling().

◆ cmp_stats()

static int cmp_stats ( const void * ptr1,
const void * ptr2 )
static
Compare limit_tuple intervals by first item in descending order.   

References ggc_alloc().

Referenced by compute_branch_probabilities().

◆ compare_freqs()

static int compare_freqs ( const void * p1,
const void * p2 )
static
Helper for qsort so edges get sorted from highest frequency to smallest.
This controls the weight for minimal spanning tree algorithm   

References EDGE_CRITICAL_P, EDGE_FREQUENCY, and ggc_alloc().

Referenced by branch_prob().

◆ compute_branch_probabilities()

static void compute_branch_probabilities ( unsigned cfg_checksum,
unsigned lineno_checksum )
static
Compute the branch probabilities for the various branches.
Annotate them accordingly.  

CFG_CHECKSUM is the precomputed checksum for the CFG.   

References alloc_aux_for_blocks(), bb_gcov_count(), bb_gcov_counts, BB_INFO, block_ends_with_call_p(), block_ends_with_condjump_p(), cfun, changes, cmp_stats(), correct_negative_edge_counts(), basic_block_def::count, count, bb_profile_info::count_valid, dump_enabled_p(), dump_file, dump_flags, dump_printf_loc(), EDGE_COMPLEX, EDGE_COUNT, edge_gcov_count(), edge_gcov_counts, EDGE_INFO, ENTRY_BLOCK_PTR_FOR_FN, error(), EXIT_BLOCK_PTR_FOR_FN, FOR_ALL_BB_FN, FOR_BB_BETWEEN, FOR_EACH_BB_FN, FOR_EACH_EDGE, fputc(), free_aux_for_blocks(), profile_count::from_gcov_type(), dump_user_location_t::from_location_t(), gcc_assert, get_exec_counts(), ggc_alloc(), gimple_dump_cfg(), profile_count::global0(), profile_probability::guessed_always(), profile_count::guessed_zero(), i, basic_block_def::index, input_location, is_inconsistent(), last_basic_block_for_fn, mcf_smooth_cfg(), MSG_NOTE, profile_probability::never(), NULL, NUM_FIXED_BLOCKS, bb_profile_info::pred_count, basic_block_def::preds, PRId64, profile_probability::probability_in_gcov_type(), PROFILE_ABSENT, profile_info, PROFILE_READ, profile_status_for_fn, read_profile_edge_counts(), REG_BR_PROB_BASE, set_bb_counts(), stats, bb_profile_info::succ_count, basic_block_def::succs, TDF_BLOCKS, TDF_DETAILS, sreal::to_double(), profile_count::to_sreal_scale(), total_hist_br_prob, total_num_branches, total_num_passes, update_max_bb_count(), and profile_count::zero().

Referenced by branch_prob().

◆ compute_value_histograms()

static void compute_value_histograms ( histogram_values values,
unsigned cfg_checksum,
unsigned lineno_checksum )
static
Load value histograms values whose description is stored in VALUES array
from .gcda file.  

CFG_CHECKSUM is the precomputed checksum for the CFG.   

References cfun, COUNTER_FOR_HIST_TYPE, dump_file, error(), free(), GCOV_N_VALUE_COUNTERS, cgraph_node::get(), get_coverage_counts(), ggc_alloc(), gimple_add_histogram_value(), HIST_TYPE_INDIR_CALL, HIST_TYPE_TIME_PROFILE, HIST_TYPE_TOPN_VALUES, i, INT_MAX, NULL, PROFILE_REPRODUCIBILITY_MULTITHREADED, sort_hist_values(), and cgraph_node::tp_first_run.

Referenced by branch_prob().

◆ correct_negative_edge_counts()

◆ cov_blocks()

array_slice< basic_block > cov_blocks ( struct condcov * cov,
size_t n )
The subgraph, exluding intermediates, for the nth Boolean expression.   

References begin(), end(), ggc_alloc(), and array_slice< T >::invalid().

Referenced by branch_prob(), and find_conditions().

◆ cov_free()

void cov_free ( struct condcov * cov)
Deleter for condcov.   

References ggc_alloc(), and sbitmap_vector_free().

Referenced by branch_prob().

◆ cov_length()

size_t cov_length ( const struct condcov * cov)
Get the length, that is the number of Boolean expression found.  cov_length
is the one-past index for cov_{blocks,masks,maps}.   

References ggc_alloc().

Referenced by branch_prob(), and find_conditions().

◆ cov_maps()

array_slice< sbitmap > cov_maps ( struct condcov * cov,
size_t n )
The maps for the nth Boolean expression.   

References begin(), end(), ggc_alloc(), and array_slice< T >::invalid().

Referenced by branch_prob(), and find_conditions().

◆ cov_masks()

array_slice< uint64_t > cov_masks ( struct condcov * cov,
size_t n )
The masks for the nth Boolean expression.   

References begin(), end(), ggc_alloc(), and array_slice< T >::invalid().

Referenced by branch_prob(), and find_conditions().

◆ end_branch_prob()

◆ find_conditions()

struct condcov * find_conditions ( struct function * fn)
Condition coverage (MC/DC)

Whalen, Heimdahl, De Silva in "Efficient Test Coverage Measurement for
MC/DC" describe an algorithm for modified condition/decision coverage based
on AST analysis.  This algorithm does analyzes the control flow graph
(interpreted as a binary decision diagram) to determine the masking vectors.
The individual phases are described in more detail closer to the
implementation.

The coverage only considers the positions, not the symbols, in a
conditional, e.g. !A || (!B && A) is a 3-term conditional even though A
appears twice.  Subexpressions have no effect on term ordering:
(a && (b || (c && d)) || e) comes out as [a b c d e].  Functions whose
arguments are Boolean expressions are treated as separate expressions, that
is, a && fn (b || c) && d is treated as [a _fn d] and [b c], not [a b c d].

The output for gcov is a vector of pairs of unsigned integers, interpreted
as bit-sets, where the bit index corresponds to the index of the condition
in the expression.

The returned condcov should be released by the caller with cov_free.   

References b, basic_block_info_for_fn, bitmap_set_bit, calculate_dominance_info(), CDI_DOMINATORS, CDI_POST_DOMINATORS, condcov::condcov(), CONDITIONS_MAX_TERMS, cov_blocks(), cov_length(), cov_maps(), cov_masks(), condcov::ctx, dom_info_available_p(), exprs, free_dominance_info(), ggc_alloc(), gimple_location(), gsi_last_bb(), gsi_stmt(), i, mark_dfs_back_edges(), n_basic_blocks_for_fn, and warning_at().

Referenced by branch_prob().

◆ find_group()

static basic_block find_group ( basic_block bb)
static
Union find algorithm implementation for the basic blocks using
aux fields.   

References basic_block_def::aux, and ggc_alloc().

Referenced by find_spanning_tree(), and union_groups().

◆ find_spanning_tree()

static void find_spanning_tree ( struct edge_list * el)
static
Forward declarations.   
This function searches all of the edges in the program flow graph, and puts
as many bad edges as possible onto the spanning tree.  Bad edges include
abnormals edges, which can't be instrumented at the moment.  Since it is
possible for fake edges to form a cycle, we will have to develop some
better way in the future.  Also put critical edges to the tree, since they
are more expensive to instrument.   

References basic_block_def::aux, cfun, clear_aux_for_blocks(), dump_file, EDGE_INFO, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, find_group(), FOR_BB_BETWEEN, ggc_alloc(), i, INDEX_EDGE, NULL, NUM_EDGES, and union_groups().

Referenced by branch_prob().

◆ get_exec_counts()

static gcov_type * get_exec_counts ( unsigned cfg_checksum,
unsigned lineno_checksum )
static
Computes hybrid profile for all matching entries in da_file.  

CFG_CHECKSUM is the precomputed checksum for the CFG.   


References cfun, EDGE_INFO, ENTRY_BLOCK_PTR_FOR_FN, FOR_BB_BETWEEN, FOR_EACH_EDGE, get_coverage_counts(), ggc_alloc(), edge_profile_info::ignore, NULL, edge_profile_info::on_tree, and basic_block_def::succs.

Referenced by compute_branch_probabilities().

◆ init_branch_prob()

◆ instrument_decisions()

size_t instrument_decisions ( array_slice< basic_block > expr,
size_t condno,
array_slice< sbitmap > maps,
array_slice< uint64_t > masks )
Add instrumentation to a decision subgraph.  EXPR should be the
(topologically sorted) block of nodes returned by cov_blocks, MAPS the
bitmaps returned by cov_maps, and MASKS the block of bitsets returned by
cov_masks.  CONDNO should be the index of this condition in the function,
i.e. the same argument given to cov_{masks,graphs}.  EXPR may contain nodes
in-between the conditions, e.g.  when an operand contains a function call,
or there is a setjmp and the cfg is filled with complex edges.

Every node is annotated with three counters; the true, false, and mask
value.  First, walk the graph and determine what if there are multiple
possible values for either accumulator depending on the path taken, in which
case a phi node is created and registered as the accumulator.  Then, those
values are pushed as accumulators to the immediate successors.  For some
very particular programs there may be multiple paths into the expression
(e.g. when prior terms are determined by a surrounding conditional) in which
case the default zero-counter is pushed, otherwise all predecessors will
have been considered before the successor because of topologically ordered
traversal.  Finally, expr is traversed again to look for edges to the
outcomes, that is, edges with a destination outside of expr, and the local
accumulators are flushed to the global gcov counters on these edges.  In
some cases there are edge splits that cause 3+ edges to the two outcome
nodes.

If a complex edge is taken (e.g. on a longjmp) the accumulators are
attempted poisoned so that there would be no change to the global counters,
but this has proven unreliable in the presence of undefined behavior, see
the setjmp003 test.

It is important that the flushes happen on the basic condition outgoing
edge, otherwise flushes could be lost to exception handling or other
abnormal control flow.   

References b, bitmap_bit_p, bitmap_count_bits(), build_addr(), build_int_cst(), builtin_decl_explicit(), candidates, EDGE_COMPLEX, EDGE_CONDITION, expr, gcc_assert, gcc_checking_assert, gcov_type_node, ggc_alloc(), gimple_build_call(), gsi_insert_on_edge(), integer_type_node, MEMMODEL_RELAXED, NULL, PROFILE_UPDATE_ATOMIC, table, tree_coverage_counter_ref(), TYPE_PRECISION, and unshare_expr().

Referenced by branch_prob().

◆ instrument_edges()

static unsigned instrument_edges ( struct edge_list * el)
static
Add edge instrumentation code to the entire insn chain.

F is the first insn of the chain.
NUM_BLOCKS is the number of basic blocks found in F.   

References cfun, dump_file, EDGE_CRITICAL_P, EDGE_INFO, ENTRY_BLOCK_PTR_FOR_FN, FOR_BB_BETWEEN, FOR_EACH_EDGE, gcc_assert, ggc_alloc(), gimple_gen_edge_profiler(), NULL, NUM_EDGES, basic_block_def::succs, and total_num_blocks_created.

Referenced by branch_prob().

◆ instrument_values()

◆ is_edge_inconsistent()

◆ is_inconsistent()

◆ output_location()

static void output_location ( hash_set< location_triplet_hash > * streamed_locations,
char const * file_name,
int line,
gcov_position_t * offset,
basic_block bb )
static
When passed NULL as file_name, initialize.
When passed something else, output the necessary commands to change
line to LINE and offset to FILE_NAME.   

References GCOV_TAG_LINES, gcov_write_filename(), gcov_write_tag(), gcov_write_unsigned(), ggc_alloc(), basic_block_def::index, NULL, offset, and remap_profile_filename().

Referenced by branch_prob().

◆ read_profile_edge_counts()

static int read_profile_edge_counts ( gcov_type * exec_counts)
static

◆ read_thunk_profile()

◆ set_bb_counts()

static void set_bb_counts ( void )
static
Set each basic block count to the sum of its outgoing edge counts  

References bb_gcov_count(), cfun, ENTRY_BLOCK_PTR_FOR_FN, FOR_BB_BETWEEN, gcc_assert, NULL, basic_block_def::succs, and sum_edge_counts().

Referenced by compute_branch_probabilities().

◆ sort_hist_values()

static void sort_hist_values ( histogram_value hist)
static
Sort the histogram value and count for TOPN and INDIR_CALL type.   

References gcc_assert, ggc_alloc(), HIST_TYPE_INDIR_CALL, HIST_TYPE_TOPN_VALUES, and i.

Referenced by compute_value_histograms().

◆ union_groups()

static void union_groups ( basic_block bb1,
basic_block bb2 )
static

References find_group(), gcc_assert, and ggc_alloc().

Referenced by find_spanning_tree().

Variable Documentation

◆ bb_gcov_counts

vec<gcov_type> bb_gcov_counts
Map from BBs/edges to gcov counters.   

Referenced by bb_gcov_count(), and compute_branch_probabilities().

◆ edge_gcov_counts

◆ profile_info

◆ total_hist_br_prob

int total_hist_br_prob[20]
static

◆ total_num_blocks

int total_num_blocks
static
Collect statistics on the performance of this pass for the entire source
file.   

Referenced by branch_prob(), end_branch_prob(), and init_branch_prob().

◆ total_num_blocks_created

int total_num_blocks_created
static

◆ total_num_branches

int total_num_branches
static

◆ total_num_conds

int total_num_conds
static

◆ total_num_edges

int total_num_edges
static

◆ total_num_edges_ignored

int total_num_edges_ignored
static

◆ total_num_edges_instrumented

int total_num_edges_instrumented
static

◆ total_num_passes

int total_num_passes
static

◆ total_num_times_called

int total_num_times_called
static