GCC Middle and Back End API 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"
Data Structures | |
struct | bb_profile_info |
struct | bb_stats |
struct | location_triplet |
struct | location_triplet_hash |
Macros | |
#define | BB_INFO(b) |
Functions | |
struct condcov * | find_conditions (struct function *) |
size_t | cov_length (const struct condcov *) |
array_slice< basic_block > | cov_blocks (struct condcov *, size_t) |
array_slice< uint64_t > | cov_masks (struct condcov *, size_t) |
array_slice< sbitmap > | cov_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_type * | get_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_type > | bb_gcov_counts |
hash_map< edge, gcov_type > * | edge_gcov_counts |
gcov_summary * | profile_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 |
#define BB_INFO | ( | b | ) |
Referenced by compute_branch_probabilities(), and read_profile_edge_counts().
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 hash_set< KeyId, Lazy, Traits >::add(), 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(), hash_set< KeyId, Lazy, Traits >::contains(), 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_FALSE, GCOV_ARC_ON_TREE, GCOV_ARC_TRUE, GCOV_TAG_ARCS, GCOV_TAG_BLOCKS, GCOV_TAG_CONDS, gcov_write_length(), gcov_write_string(), gcov_write_tag(), gcov_write_unsigned(), 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, edge_profile_info::ignore, 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, edge_profile_info::on_tree, 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, sreal::to_nearest_int(), 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().
|
static |
Compare limit_tuple intervals by first item in descending order.
References bb_stats::feedback.
Referenced by compute_branch_probabilities().
|
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, and EDGE_FREQUENCY.
Referenced by branch_prob().
|
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(), 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(), 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().
|
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, histogram_value_t::counters, function::decl, dump_file, error(), free(), histogram_value_t::fun, GCOV_N_VALUE_COUNTERS, cgraph_node::get(), get_coverage_counts(), gimple_add_histogram_value(), HIST_TYPE_INDIR_CALL, HIST_TYPE_TIME_PROFILE, HIST_TYPE_TOPN_VALUES, histogram_value_t::hvalue, i, INT_MAX, histogram_value_t::n_counters, NULL, PROFILE_REPRODUCIBILITY_MULTITHREADED, sort_hist_values(), histogram_value_t::stmt, cgraph_node::tp_first_run, and histogram_value_t::type.
Referenced by branch_prob().
|
static |
References cfun, edge_gcov_count(), ENTRY_BLOCK_PTR_FOR_FN, FOR_BB_BETWEEN, FOR_EACH_EDGE, NULL, and basic_block_def::succs.
Referenced by compute_branch_probabilities().
array_slice< basic_block > cov_blocks | ( | struct condcov * | cov, |
size_t | n ) |
The subgraph, exluding intermediates, for the nth Boolean expression.
References begin(), end(), array_slice< T >::invalid(), condcov::m_blocks, and condcov::m_index.
Referenced by branch_prob(), and find_conditions().
void cov_free | ( | struct condcov * | cov | ) |
Deleter for condcov.
References condcov::m_maps, and sbitmap_vector_free().
Referenced by branch_prob().
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 condcov::m_index.
Referenced by branch_prob(), and find_conditions().
array_slice< sbitmap > cov_maps | ( | struct condcov * | cov, |
size_t | n ) |
The maps for the nth Boolean expression.
References begin(), end(), array_slice< T >::invalid(), condcov::m_index, and condcov::m_maps.
Referenced by branch_prob(), and find_conditions().
array_slice< uint64_t > cov_masks | ( | struct condcov * | cov, |
size_t | n ) |
The masks for the nth Boolean expression.
References begin(), end(), array_slice< T >::invalid(), condcov::m_index, and condcov::m_masks.
Referenced by branch_prob(), and find_conditions().
void end_branch_prob | ( | void | ) |
Performs file-level cleanup after branch-prob processing is completed.
References dump_file, i, total_hist_br_prob, total_num_blocks, total_num_blocks_created, total_num_branches, total_num_conds, total_num_edges, total_num_edges_ignored, total_num_edges_instrumented, total_num_passes, and total_num_times_called.
Referenced by gcc::pass_manager::finish_optimization_passes().
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(), free_dominance_info(), hash_map< KeyId, Value, Traits >::get_or_insert(), gimple_location(), gsi_last_bb(), gsi_stmt(), i, condcov::m_blocks, condcov::m_index, condcov::m_maps, condcov::m_masks, mark_dfs_back_edges(), n_basic_blocks_for_fn, and warning_at().
Referenced by branch_prob().
|
static |
Union find algorithm implementation for the basic blocks using aux fields.
References basic_block_def::aux.
Referenced by find_spanning_tree(), and union_groups().
|
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, i, INDEX_EDGE, NULL, NUM_EDGES, and union_groups().
Referenced by branch_prob().
|
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(), edge_profile_info::ignore, NULL, edge_profile_info::on_tree, and basic_block_def::succs.
Referenced by compute_branch_probabilities().
void init_branch_prob | ( | void | ) |
Perform file-level initialization for branch-prob processing.
References i, total_hist_br_prob, total_num_blocks, total_num_blocks_created, total_num_branches, total_num_conds, total_num_edges, total_num_edges_ignored, total_num_edges_instrumented, total_num_passes, and total_num_times_called.
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, gcc_assert, gcc_checking_assert, gcov_type_node, 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().
|
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, gimple_gen_edge_profiler(), edge_profile_info::ignore, NULL, NUM_EDGES, edge_profile_info::on_tree, basic_block_def::succs, and total_num_blocks_created.
Referenced by branch_prob().
|
static |
Add code to measure histograms for values in list VALUES.
References COUNTER_FOR_HIST_TYPE, coverage_counter_alloc(), gcc_unreachable, gimple_gen_average_profiler(), gimple_gen_ic_profiler(), gimple_gen_interval_profiler(), gimple_gen_ior_profiler(), gimple_gen_pow2_profiler(), gimple_gen_time_profiler(), gimple_gen_topn_values_profiler(), HIST_TYPE_AVERAGE, HIST_TYPE_INDIR_CALL, HIST_TYPE_INTERVAL, HIST_TYPE_IOR, HIST_TYPE_POW2, HIST_TYPE_TIME_PROFILE, HIST_TYPE_TOPN_VALUES, i, histogram_value_t::n_counters, and histogram_value_t::type.
Referenced by branch_prob().
References block_ends_with_call_p(), dump_bb(), dump_file, edge_gcov_count(), EDGE_INFO, FOR_EACH_EDGE, edge_profile_info::ignore, PRId64, and TDF_DETAILS.
Referenced by is_inconsistent().
|
static |
Check consistency. Return true if inconsistency is found.
References bb_gcov_count(), block_ends_with_call_p(), cfun, dump_bb(), dump_file, EXIT_BLOCK_PTR_FOR_FN, find_edge(), FOR_EACH_BB_FN, basic_block_def::index, is_edge_inconsistent(), NULL, basic_block_def::preds, PRId64, basic_block_def::succs, sum_edge_counts(), and TDF_DETAILS.
Referenced by compute_branch_probabilities().
|
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 hash_set< KeyId, Lazy, Traits >::add(), location_triplet::bb_index, location_triplet::filename, GCOV_TAG_LINES, gcov_write_filename(), gcov_write_tag(), gcov_write_unsigned(), basic_block_def::index, location_triplet::lineno, NULL, and remap_profile_filename().
Referenced by branch_prob().
|
static |
Reads profile data and returns total number of edge counts read
References BB_INFO, cfun, dump_file, edge_gcov_count(), EDGE_INFO, ENTRY_BLOCK_PTR_FOR_FN, FOR_BB_BETWEEN, FOR_EACH_EDGE, edge_profile_info::ignore, basic_block_def::index, NULL, edge_profile_info::on_tree, PRId64, and basic_block_def::succs.
Referenced by compute_branch_probabilities().
void read_thunk_profile | ( | struct cgraph_node * | node | ) |
Only read execution count for thunks.
References cgraph_node::callees, cgraph_edge::count, cgraph_node::count, current_function_decl, symtab_node::decl, free(), profile_count::from_gcov_type(), and get_coverage_counts().
Referenced by tree_profiling().
|
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().
|
static |
Sort the histogram value and count for TOPN and INDIR_CALL type.
References histogram_value_t::counters, gcc_assert, HIST_TYPE_INDIR_CALL, HIST_TYPE_TOPN_VALUES, histogram_value_t::hvalue, i, and histogram_value_t::type.
Referenced by compute_value_histograms().
|
static |
References basic_block_def::aux, find_group(), and gcc_assert.
Referenced by find_spanning_tree().
Map from BBs/edges to gcov counters.
Referenced by bb_gcov_count(), and compute_branch_probabilities().
Referenced by compute_branch_probabilities(), and edge_gcov_count().
gcov_summary* profile_info |
Counter summary from the last set of coverage counts read.
Referenced by afdo_callsite_hot_enough_for_early_inline(), autofdo::auto_profile(), compute_branch_probabilities(), drop_profile(), dump_function_to_file(), eliminate_partially_redundant_load(), end_auto_profile(), get_hot_bb_threshold(), get_working_sets(), gimple_account_profile_record(), handle_missing_profiles(), inline_small_functions(), ipa_propagate_frequency_1(), maybe_hot_count_p(), merge_profile_summaries(), output_profile_summary(), probably_never_executed(), profile_record_check_consistency(), read_counts_file(), report_unroll(), rtl_account_profile_record(), and tail_duplicate().
|
static |
Referenced by compute_branch_probabilities(), end_branch_prob(), and init_branch_prob().
|
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().
|
static |
Referenced by end_branch_prob(), init_branch_prob(), and instrument_edges().
|
static |
Referenced by compute_branch_probabilities(), end_branch_prob(), and init_branch_prob().
|
static |
Referenced by branch_prob(), end_branch_prob(), and init_branch_prob().
|
static |
Referenced by branch_prob(), end_branch_prob(), and init_branch_prob().
|
static |
Referenced by branch_prob(), end_branch_prob(), and init_branch_prob().
|
static |
Referenced by branch_prob(), end_branch_prob(), and init_branch_prob().
|
static |
Referenced by compute_branch_probabilities(), end_branch_prob(), and init_branch_prob().
|
static |
Referenced by branch_prob(), end_branch_prob(), and init_branch_prob().