#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "expr.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "value-prof.h"
#include "flags.h"
#include "insn-config.h"
#include "recog.h"
#include "optabs.h"
#include "regs.h"
#include "ggc.h"
#include "gimple.h"
#include "gimple-ssa.h"
#include "tree-cfg.h"
#include "tree-phinodes.h"
#include "ssa-iterators.h"
#include "tree-ssanames.h"
#include "diagnostic.h"
#include "gimple-pretty-print.h"
#include "coverage.h"
#include "gcov-io.h"
#include "timevar.h"
#include "dumpfile.h"
#include "pointer-set.h"
#include "profile.h"
#include "data-streamer.h"

Include dependency graph for value-prof.c:

Functions
static tree	gimple_divmod_fixed_value (gimple, tree, int, gcov_type, gcov_type)
static tree	gimple_mod_pow2 (gimple, int, gcov_type, gcov_type)
static tree	gimple_mod_subtract (gimple, int, int, int, gcov_type, gcov_type, gcov_type)
static bool	gimple_divmod_fixed_value_transform (gimple_stmt_iterator *)
static bool	gimple_mod_pow2_value_transform (gimple_stmt_iterator *)
static bool	gimple_mod_subtract_transform (gimple_stmt_iterator *)
static bool	gimple_stringops_transform (gimple_stmt_iterator *)
static bool	gimple_ic_transform (gimple_stmt_iterator *)
static histogram_value	gimple_alloc_histogram_value (struct function *fun, enum hist_type type, gimple stmt, tree value)
static hashval_t	histogram_hash ()
static int	histogram_eq ()
static void	set_histogram_value ()
histogram_value	gimple_histogram_value ()
void	gimple_add_histogram_value (struct function *fun, gimple stmt, histogram_value hist)
void	gimple_remove_histogram_value (struct function *fun, gimple stmt, histogram_value hist)
histogram_value	gimple_histogram_value_of_type (struct function *fun, gimple stmt, enum hist_type type)
static void	dump_histogram_value ()
void	stream_out_histogram_value ()
void	stream_in_histogram_value ()
void	dump_histograms_for_stmt ()
void	gimple_remove_stmt_histograms ()
void	gimple_duplicate_stmt_histograms (struct function fun, gimple stmt, struct function ofun, gimple ostmt)
void	gimple_move_stmt_histograms ()
static int	visit_hist ()
DEBUG_FUNCTION void	verify_histograms ()
static int	free_hist ()
void	free_histograms ()
static bool	check_counter (gimple stmt, const char name, gcov_type count, gcov_type *all, gcov_type bb_count)
bool	gimple_value_profile_transformations ()
static bool	gimple_divmod_fixed_value_transform ()
static tree	gimple_mod_pow2 ()
static bool	gimple_mod_pow2_value_transform ()
static bool	gimple_mod_subtract_transform ()
void	init_node_map ()
void	del_node_map ()
struct cgraph_node *	find_func_by_profile_id ()
static bool	check_ic_target ()
gimple	gimple_ic (gimple icall_stmt, struct cgraph_node *direct_call, int prob, gcov_type count, gcov_type all)
static bool	gimple_ic_transform ()
static bool	interesting_stringop_to_profile_p ()
static void	gimple_stringop_fixed_value (gimple vcall_stmt, tree icall_size, int prob, gcov_type count, gcov_type all)
static bool	gimple_stringops_transform ()
void	stringop_block_profile (gimple stmt, unsigned int expected_align, HOST_WIDE_INT expected_size)
static void	gimple_divmod_values_to_profile ()
static void	gimple_indirect_call_to_profile ()
static void	gimple_stringops_values_to_profile ()
static void	gimple_values_to_profile ()
void	gimple_find_values_to_profile ()

Variables
static bool	error_found = false
static pointer_map_t *	cgraph_node_map

Function Documentation

static bool check_counter	(	gimple	stmt,
		const char *	name,
		gcov_type *	count,
		gcov_type *	all,
		gcov_type	bb_count
	)

static

The overall number of invocations of the counter should match execution count of basic block. Report it as error rather than internal error as it might mean that user has misused the profile somehow.

References error_at().

static bool check_ic_target ( )

static

Perform sanity check on the indirect call target. Due to race conditions, false function target may be attributed to an indirect call site. If the call expression type mismatches with the target function's type, expand_call may ICE. Here we only do very minimal sanity check just to make compiler happy. Returns true if TARGET is considered ok for call CALL_STMT.

void del_node_map ( void )

Delete the CGRAPH_NODE_MAP.

static void dump_histogram_value ( )

static

Dump information about HIST to DUMP_FILE.

Referenced by gimple_move_stmt_histograms().

void dump_histograms_for_stmt ( )

Dump all histograms attached to STMT to DUMP_FILE.

struct cgraph_node* find_func_by_profile_id ( )

read

Return cgraph node for function with pid

static int free_hist ( )

static

Helper function for verify_histograms. For each histogram reachable via htab walk verify that it was reached via statement walk.

void free_histograms ( void )

References DECL_SOURCE_LOCATION, dump_enabled_p(), dump_printf_loc(), gimple_location(), MSG_MISSED_OPTIMIZATION, and NULL.

void gimple_add_histogram_value	(	struct function *	fun,
		gimple	stmt,
		histogram_value	hist
	)

Add histogram for STMT.

References gimple_histogram_value(), histogram_value_t::hvalue, histogram_value_t::next, and set_histogram_value().

Referenced by gimple_remove_stmt_histograms().

static histogram_value gimple_alloc_histogram_value	(	struct function *	fun,
		enum hist_type	type,
		gimple	stmt,
		tree	value
	)

static

Allocate histogram value.

Referenced by gimple_remove_stmt_histograms(), and stringop_block_profile().

static tree gimple_divmod_fixed_value	(	gimple	stmt,
		tree	value,
		int	prob,
		gcov_type	count,
		gcov_type	all
	)

static

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/. In this file value profile based optimizations are placed. Currently the following optimizations are implemented (for more detailed descriptions see comments at value_profile_transformations):

1) Division/modulo specialization. Provided that we can determine that the operands of the division have some special properties, we may use it to produce more effective code.

2) Indirect/virtual call specialization. If we can determine most common function callee in indirect/virtual call. We can use this information to improve code effectiveness (especially info for the inliner).

3) Speculative prefetching. If we are able to determine that the difference between addresses accessed by a memory reference is usually constant, we may add the prefetch instructions. FIXME: This transformation was removed together with RTL based value profiling.

Value profiling internals

Every value profiling transformation starts with defining what values to profile. There are different histogram types (see HIST_TYPE_* in value-prof.h) and each transformation can request one or more histogram types per GIMPLE statement. The function gimple_find_values_to_profile() collects the values to profile in a vec, and adds the number of counters required for the different histogram types.

For a -fprofile-generate run, the statements for which values should be recorded, are instrumented in instrument_values(). The instrumentation is done by helper functions that can be found in tree-profile.c, where new types of histograms can be added if necessary.

After a -fprofile-use, the value profiling data is read back in by compute_value_histograms() that translates the collected data to histograms and attaches them to the profiled statements via gimple_add_histogram_value(). Histograms are stored in a hash table that is attached to every intrumented function, see VALUE_HISTOGRAMS in function.h.

The value-profile transformations driver is the function gimple_value_profile_transformations(). It traverses all statements in the to-be-transformed function, and looks for statements with one or more histograms attached to it. If a statement has histograms, the transformation functions are called on the statement.

Limitations / FIXME / TODO: Only one histogram of each type can be associated with a statement. Currently, HIST_TYPE_CONST_DELTA is not implemented. (This type of histogram was originally used to implement a form of stride profiling based speculative prefetching to improve SPEC2000 scores for memory-bound benchmarks, mcf and equake. However, this was an RTL value-profiling transformation, and those have all been removed.) Some value profile transformations are done in builtins.c (?!) Updating of histograms needs some TLC. The value profiling code could be used to record analysis results from non-profiling (e.g. VRP). Adding new profilers should be simplified, starting with a cleanup of what-happens-where andwith making gimple_find_values_to_profile and gimple_value_profile_transformations table-driven, perhaps...

Generate code for transformation 1 (with parent gimple assignment STMT and probability of taking the optimal path PROB, which is equivalent to COUNT/ALL within roundoff error). This generates the result into a temp and returns the temp; it does not replace or alter the original STMT.

Fix CFG.

 Edge e23 connects bb2 to bb3, etc.

static bool gimple_divmod_fixed_value_transform ( gimple_stmt_iterator * )

static

static bool gimple_divmod_fixed_value_transform ( )

static

Do transform 1) on INSN if applicable.

We require that count is at least half of all; this means that for the transformation to fire the value must be constant at least 50% of time (and 75% gives the guarantee of usage).

 Compute probability of taking the optimal path.

static void gimple_divmod_values_to_profile ( )

static

Find values inside STMT for that we want to measure histograms for division/modulo optimization.

       Check for the case where the divisor is the same value most
       of the time.

     For mod, check whether it is not often a noop (or replaceable by
     a few subtractions).

         Check for a special case where the divisor is power of 2.

void gimple_duplicate_stmt_histograms	(	struct function *	fun,
		gimple	stmt,
		struct function *	ofun,
		gimple	ostmt
	)

Duplicate all histograms associates with OSTMT to STMT.

References gimple_histogram_value(), histogram_value_t::hvalue, histogram_value_t::next, NULL, set_histogram_value(), and histogram_value_t::stmt.

Referenced by gimple_redirect_edge_and_branch(), and gsi_split_seq_before().

void gimple_find_values_to_profile ( )

histogram_value gimple_histogram_value ( )

Get histogram list for STMT.

References histogram_value_t::hvalue, histogram_value_t::next, and set_histogram_value().

Referenced by gimple_add_histogram_value(), gimple_duplicate_stmt_histograms(), and visit_hist().

histogram_value gimple_histogram_value_of_type	(	struct function *	fun,
		gimple	stmt,
		enum hist_type	type
	)

Lookup histogram of type TYPE in the STMT.

References histogram_value_t::counters, histogram_value_t::hdata, HIST_TYPE_INTERVAL, histogram_value_t::hvalue, histogram_value_t::intvl, and histogram_value_t::type.

gimple gimple_ic	(	gimple	icall_stmt,
		struct cgraph_node *	direct_call,
		int	prob,
		gcov_type	count,
		gcov_type	all
	)

Do transformation

if (actual_callee_address == address_of_most_common_function/method) do direct call else old call

 Fix CFG.

 Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters.

 Do not disturb existing EH edges from the indirect call.

     The indirect call might be noreturn.

 Insert PHI node for the call result if necessary.

 Build an EH edge for the direct call if necessary.

static bool gimple_ic_transform ( gimple_stmt_iterator * )

static

static bool gimple_ic_transform ( )

static

The order of CHECK_COUNTER calls is important - since check_counter can correct the third parameter and we want to make count <= all <= bb_all.

static void gimple_indirect_call_to_profile ( )

static

Find calls inside STMT for that we want to measure histograms for indirect/virtual call optimization.

References HIST_TYPE_CONST_DELTA, HIST_TYPE_INDIR_CALL, HIST_TYPE_INTERVAL, HIST_TYPE_POW2, and HIST_TYPE_SINGLE_VALUE.

static tree gimple_mod_pow2	(	gimple	,
		int	,
		gcov_type	,
		gcov_type
	)

static

static tree gimple_mod_pow2 ( )

static

Generate code for transformation 2 (with parent gimple assign STMT and probability of taking the optimal path PROB, which is equivalent to COUNT/ALL within roundoff error). This generates the result into a temp and returns the temp; it does not replace or alter the original STMT.

 tmp2 == op2-1 inherited from previous block.

 Fix CFG.

 Edge e23 connects bb2 to bb3, etc.

static bool gimple_mod_pow2_value_transform ( gimple_stmt_iterator * )

static

static bool gimple_mod_pow2_value_transform ( )

static

Do transform 2) on INSN if applicable.

We require that we hit a power of 2 at least half of all evaluations.

 Compute probability of taking the optimal path.

References print_gimple_stmt(), and TDF_SLIM.

static tree gimple_mod_subtract	(	gimple	stmt,
		int	prob1,
		int	prob2,
		int	ncounts,
		gcov_type	count1,
		gcov_type	count2,
		gcov_type	all
	)

static

Generate code for transformations 3 and 4 (with parent gimple assign STMT, and NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is supported and this is built into this interface. The probabilities of taking the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and COUNT2/ALL respectively within roundoff error). This generates the result into a temp and returns the temp; it does not replace or alter the original STMT. FIXME: Generalize the interface to handle NCOUNTS > 1.

 Fallback case.

 Fix CFG.

 Edge e23 connects bb2 to bb3, etc.

 However block 3 is optional; if it is not there, references
 to 3 really refer to block 2.

static bool gimple_mod_subtract_transform ( gimple_stmt_iterator * )

static

static bool gimple_mod_subtract_transform ( )

static

Do transforms 3) and 4) on the statement pointed-to by SI if applicable.

 Compute probability of taking the optimal path.

 We require that we use just subtractions in at least 50% of all
 evaluations.

 Compute probability of taking the optimal path(s).

 In practice, "steps" is always 2.  This interface reflects this,
 and will need to be changed if "steps" can change.

void gimple_move_stmt_histograms ( )

Move all histograms associated with OSTMT to STMT.

The following three statements can't be reordered, because histogram hashtab relies on stmt field value for finding the exact slot.

References debug_gimple_stmt(), dump_histogram_value(), error(), histogram_value_t::hvalue, pointer_set_contains(), histogram_value_t::stmt, and visited.

void gimple_remove_histogram_value	(	struct function *	fun,
		gimple	stmt,
		histogram_value	hist
	)

Remove histogram HIST from STMT's histogram list.

References histogram_value_t::hvalue, and histogram_value_t::next.

void gimple_remove_stmt_histograms ( )

Remove all histograms associated with STMT.

References histogram_value_t::counters, gimple_add_histogram_value(), gimple_alloc_histogram_value(), histogram_value_t::hvalue, histogram_value_t::n_counters, NULL, histogram_value_t::stmt, and histogram_value_t::type.

Referenced by gsi_split_seq_before().

static void gimple_stringop_fixed_value	(	gimple	vcall_stmt,
		tree	icall_size,
		int	prob,
		gcov_type	count,
		gcov_type	all
	)

static

Convert stringop (..., vcall_size) into if (vcall_size == icall_size) stringop (..., icall_size); else stringop (..., vcall_size); assuming we'll propagate a true constant into ICALL_SIZE later.

 Fix CFG.

 Edge e_ci connects cond_bb to icall_bb, etc.

 Insert PHI node for the call result if necessary.

 Because these are all string op builtins, they're all nothrow.

References add_phi_arg(), create_phi_node(), duplicate_ssa_name(), gimple_call_lhs(), gimple_call_set_lhs(), and UNKNOWN_LOCATION.

static bool gimple_stringops_transform ( gimple_stmt_iterator * )

static

static bool gimple_stringops_transform ( )

static

Find values inside STMT for that we want to measure histograms for division/modulo optimization.

We require that count is at least half of all; this means that for the transformation to fire the value must be constant at least 80% of time.

static void gimple_stringops_values_to_profile ( )

static

Find values inside STMT for that we want to measure histograms for string operations.

bool gimple_value_profile_transformations ( void )

GIMPLE based transformations.

         Transformations:

         The order of things in this conditional controls which
         transformation is used when more than one is applicable.

         It is expected that any code added by the transformations
         will be added before the current statement, and that the
         current statement remain valid (although possibly
         modified) upon return.

             Original statement may no longer be in the same block.

References gimple_bb(), gsi_for_stmt(), and gsi_stmt().

static void gimple_values_to_profile ( )

static

Find values inside STMT for that we want to measure histograms and adds them to list VALUES.

static int histogram_eq ( )

static

Return nonzero if statement for histogram_value X is Y.

References VALUE_HISTOGRAMS.

static hashval_t histogram_hash ( )

static

Hash value for histogram.

void init_node_map ( )

Initialize map from PROFILE_ID to CGRAPH_NODE. When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume that the PROFILE_IDs was already assigned.

static bool interesting_stringop_to_profile_p ( )

static

Return true if the stringop CALL with FNDECL shall be profiled. SIZE_ARG be set to the argument index for the size of the string operation.

static void set_histogram_value ( )

static

Set histogram for STMT.

Referenced by gimple_add_histogram_value(), gimple_duplicate_stmt_histograms(), and gimple_histogram_value().

void stream_in_histogram_value ( )

Dump information about HIST to DUMP_FILE.

void stream_out_histogram_value ( )

Dump information about HIST to DUMP_FILE.

void stringop_block_profile	(	gimple	stmt,
		unsigned int *	expected_align,
		HOST_WIDE_INT *	expected_size
	)

Even if we can hold bigger value in SIZE, INT_MAX is safe "infinity" for code generation strategies.

References build2, cfun, gimple_alloc_histogram_value(), histogram_value_t::hdata, HIST_TYPE_INTERVAL, HIST_TYPE_POW2, and histogram_value_t::intvl.

DEBUG_FUNCTION void verify_histograms ( void )

Verify sanity of the histograms.

static int visit_hist ( )

static

Helper function for verify_histograms. For each histogram reachable via htab walk verify that it was reached via statement walk.

References cfun, error(), FOR_EACH_BB, gimple_histogram_value(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), histogram_value_t::hvalue, histogram_value_t::next, pointer_set_create(), and histogram_value_t::stmt.

Variable Documentation

pointer_map_t* cgraph_node_map

static

bool error_found = false

static

Referenced by cgraph_edge_cannot_lead_to_return().

Functions

Variables

Function Documentation

Value profiling internals

Variable Documentation