autofdo Namespace Reference

Data Structures
class	autofdo_source_profile
class	count_info
class	edge_info
class	function_instance
struct	string_compare
class	string_table

Typedefs
typedef std::pair< tree, unsigned >	decl_lineno
typedef auto_vec< decl_lineno >	inline_stack
typedef auto_vec< char * >	string_vector
typedef std::map< unsigned, gcov_type >	icall_target_map
typedef std::set< gimple * >	stmt_set
typedef std::set< basic_block >	bb_set
typedef std::set< edge >	edge_set

Functions
static char *	get_original_name (const char *name)
static unsigned	get_combined_location (location_t loc, tree decl)
static tree	get_function_decl_from_block (tree block)
static void	get_inline_stack (location_t locus, inline_stack *stack)
static unsigned	get_relative_location_for_stmt (gimple *stmt)
static bool	has_indirect_call (basic_block bb)
static void	fake_read_autofdo_module_profile ()
static void	read_profile (void)
static bool	afdo_indirect_call (gimple_stmt_iterator *gsi, const icall_target_map &map, bool transform)
static bool	afdo_vpt (gimple_stmt_iterator *gsi, const icall_target_map &map, bool transform)
static bool	is_bb_annotated (const basic_block bb, const bb_set &annotated)
static void	set_bb_annotated (basic_block bb, bb_set *annotated)
static bool	afdo_set_bb_count (basic_block bb, const stmt_set &promoted)
static void	afdo_find_equiv_class (bb_set *annotated_bb)
static bool	afdo_propagate_edge (bool is_succ, bb_set *annotated_bb)
static void	afdo_propagate_circuit (const bb_set &annotated_bb)
static void	afdo_propagate (bb_set *annotated_bb)
static void	afdo_calculate_branch_prob (bb_set *annotated_bb)
static bool	afdo_vpt_for_early_inline (stmt_set *promoted_stmts)
static void	afdo_annotate_cfg (const stmt_set &promoted_stmts)
static unsigned int	early_inline ()
static unsigned int	auto_profile (void)

Variables
static string_table *	afdo_string_table
static autofdo_source_profile *	afdo_source_profile
static gcov_summary *	afdo_profile_info

Typedef Documentation

bb_set

typedef std::set<basic_block> autofdo::bb_set

decl_lineno

typedef std::pair<tree, unsigned> autofdo::decl_lineno

Represent a source location: (function_decl, lineno).   

edge_set

typedef std::set<edge> autofdo::edge_set

icall_target_map

typedef std::map<unsigned, gcov_type> autofdo::icall_target_map

Map from function name's index in string_table to target's
execution count.   

inline_stack

typedef auto_vec<decl_lineno> autofdo::inline_stack

Represent an inline stack. vector[0] is the leaf node.   

stmt_set

typedef std::set<gimple *> autofdo::stmt_set

Set of gimple stmts. Used to track if the stmt has already been promoted
to direct call.   

string_vector

typedef auto_vec<char *> autofdo::string_vector

String array that stores function names.   

Function Documentation

afdo_annotate_cfg()

static void autofdo::afdo_annotate_cfg ( const stmt_set & promoted_stmts )

static

Annotate auto profile to the control flow graph. Do not annotate value
profile for stmts in PROMOTED_STMTS.   

References profile_count::afdo(), afdo_calculate_branch_prob(), afdo_set_bb_count(), afdo_source_profile, CDI_DOMINATORS, CDI_POST_DOMINATORS, cfun, basic_block_def::count, cgraph_node::count, count, current_function_decl, DECL_SOURCE_LOCATION, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, FOR_EACH_BB_FN, free_dominance_info(), profile_count::from_gcov_type(), cgraph_node::get(), gimple_value_profile_transformations(), autofdo::function_instance::head_count(), max_count, NULL, PROFILE_READ, profile_status_for_fn, set_bb_annotated(), TODO_update_ssa, update_max_bb_count(), update_ssa(), and profile_count::zero().

Referenced by auto_profile().

afdo_calculate_branch_prob()

static void autofdo::afdo_calculate_branch_prob ( bb_set * annotated_bb )

static

Propagate counts on control flow graph and calculate branch
probabilities.   

References profile_count::afdo(), AFDO_EINFO, afdo_find_equiv_class(), afdo_propagate(), basic_block_def::aux, calculate_dominance_info(), CDI_DOMINATORS, CDI_POST_DOMINATORS, cfun, FOR_ALL_BB_FN, FOR_EACH_BB_FN, FOR_EACH_EDGE, free_dominance_info(), gcc_assert, loop_optimizer_finalize(), loop_optimizer_init(), profile_count::nonzero_p(), NULL, basic_block_def::succs, and profile_count::zero().

Referenced by afdo_annotate_cfg().

afdo_find_equiv_class()

static void autofdo::afdo_find_equiv_class ( bb_set * annotated_bb )

static

BB1 and BB2 are in an equivalent class iff:
1. BB1 dominates BB2.
2. BB2 post-dominates BB1.
3. BB1 and BB2 are in the same loop nest.
This function finds the equivalent class for each basic block, and
stores a pointer to the first BB in its equivalent class. Meanwhile,
set bb counts for the same equivalent class to be idenical. Update
ANNOTATED_BB for the first BB in its equivalent class.   

References basic_block_def::aux, CDI_DOMINATORS, CDI_POST_DOMINATORS, cfun, basic_block_def::count, dominated_by_p(), FOR_ALL_BB_FN, get_dominated_by(), is_bb_annotated(), basic_block_def::loop_father, NULL, and set_bb_annotated().

Referenced by afdo_calculate_branch_prob().

afdo_indirect_call()

static bool autofdo::afdo_indirect_call ( gimple_stmt_iterator * gsi, const icall_target_map & map, bool transform )

static

From AutoFDO profiles, find values inside STMT for that we want to measure
histograms for indirect-call optimization.

This function is actually served for 2 purposes:
  * before annotation, we need to mark histogram, promote and inline
  * after annotation, we just need to mark, and let follow-up logic to
    decide if it needs to promote and inline.   

References afdo_string_table, cfun, histogram_value_t::counters, current_function_decl, symtab_node::decl, DECL_STRUCT_FUNCTION, dump_file, dyn_cast(), cgraph_node::get(), cgraph_node::get_edge(), cgraph_node::get_for_asmname(), get_identifier(), gimple_add_histogram_value(), gimple_alloc_histogram_value(), gimple_call_fn(), gimple_call_fndecl(), gimple_call_internal_p(), gimple_remove_histogram_value(), gsi_stmt(), HIST_TYPE_INDIR_CALL, histogram_value_t::hvalue, inline_call(), cgraph_edge::make_speculative(), map, histogram_value_t::n_counters, NULL, NULL_TREE, print_generic_expr(), print_gimple_stmt(), cgraph_node::profile_id, cgraph_edge::redirect_call_stmt_to_callee(), TDF_SLIM, and profile_count::uninitialized().

Referenced by afdo_vpt().

afdo_propagate()

static void autofdo::afdo_propagate ( bb_set * annotated_bb )

static

Propagate the basic block count and edge count on the control flow
graph. We do the propagation iteratively until stablize.   

References afdo_propagate_circuit(), afdo_propagate_edge(), basic_block_def::aux, cfun, changed, basic_block_def::count, count, FOR_ALL_BB_FN, i, is_bb_annotated(), and set_bb_annotated().

Referenced by afdo_calculate_branch_prob().

afdo_propagate_circuit()

static void autofdo::afdo_propagate_circuit ( const bb_set & annotated_bb )

static

Special propagation for circuit expressions. Because GCC translates
control flow into data flow for circuit expressions. E.g.
BB1:
if (a && b)
  BB2
else
  BB3

will be translated into:

BB1:
  if (a)
    goto BB.t1
  else
    goto BB.t3
BB.t1:
  if (b)
    goto BB.t2
  else
    goto BB.t3
BB.t2:
  goto BB.t3
BB.t3:
  tmp = PHI (0 (BB1), 0 (BB.t1), 1 (BB.t2)
  if (tmp)
    goto BB2
  else
    goto BB3

In this case, we need to propagate through PHI to determine the edge
count of BB1->BB.t1, BB.t1->BB.t2.   

References AFDO_EINFO, cfun, dyn_cast(), FOR_ALL_BB_FN, FOR_EACH_EDGE, gimple_assign_rhs1(), gimple_assign_single_p(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), i, integer_onep(), integer_zerop(), is_bb_annotated(), last_nondebug_stmt(), SSA_NAME_DEF_STMT, basic_block_def::succs, TREE_CODE, TREE_CONSTANT, and profile_count::zero().

Referenced by afdo_propagate().

afdo_propagate_edge()

static bool autofdo::afdo_propagate_edge ( bool is_succ, bb_set * annotated_bb )

static

If a basic block's count is known, and only one of its in/out edges' count
is unknown, its count can be calculated. Meanwhile, if all of the in/out
edges' counts are known, then the basic block's unknown count can also be
calculated. Also, if a block has a single predecessor or successor, the block's
count can be propagated to that predecessor or successor.
IS_SUCC is true if out edges of a basic blocks are examined.
Update ANNOTATED_BB accordingly.
Return TRUE if any basic block/edge count is changed.   

References profile_count::afdo(), AFDO_EINFO, cfun, changed, basic_block_def::count, FOR_EACH_BB_FN, FOR_EACH_EDGE, gcc_assert, is_bb_annotated(), NULL, basic_block_def::preds, set_bb_annotated(), basic_block_def::succs, and profile_count::zero().

Referenced by afdo_propagate().

afdo_set_bb_count()

static bool autofdo::afdo_set_bb_count ( basic_block bb, const stmt_set & promoted )

static

For a given BB, set its execution count. Attach value profile if a stmt
is not in PROMOTED, because we only want to promote an indirect call once.
Return TRUE if BB is annotated.   

References profile_count::afdo(), afdo_source_profile, afdo_vpt(), autofdo::count_info::count, basic_block_def::count, FOR_EACH_EDGE, profile_count::from_gcov_type(), gimple_clobber_p(), gimple_location(), gimple_phi_arg_location(), gimple_phi_num_args(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), i, is_gimple_debug(), max_count, basic_block_def::succs, and autofdo::count_info::targets.

Referenced by afdo_annotate_cfg().

afdo_vpt()

static bool autofdo::afdo_vpt ( gimple_stmt_iterator * gsi, const icall_target_map & map, bool transform )

static

From AutoFDO profiles, find values inside STMT for that we want to measure
histograms and adds them to list VALUES.   

References afdo_indirect_call(), and map.

Referenced by afdo_set_bb_count(), and afdo_vpt_for_early_inline().

afdo_vpt_for_early_inline()

static bool autofdo::afdo_vpt_for_early_inline ( stmt_set * promoted_stmts )

static

Perform value profile transformation using AutoFDO profile. Add the
promoted stmts to PROMOTED_STMTS. Return TRUE if there is any
indirect call promoted.   

References afdo_source_profile, afdo_vpt(), cfun, compute_fn_summary(), autofdo::count_info::count, current_function_decl, dyn_cast(), FOR_EACH_BB_FN, cgraph_node::get(), gimple_call_fn(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), has_indirect_call(), MAX, NULL, optimize_inline_calls(), autofdo::count_info::targets, todo, TODO_update_ssa, TODO_update_ssa_any, TREE_CODE, and update_ssa().

Referenced by auto_profile().

auto_profile()

static unsigned int autofdo::auto_profile ( void )

static

Use AutoFDO profile to annoate the control flow graph.
Return the todo flag.   

References afdo_annotate_cfg(), afdo_profile_info, afdo_vpt_for_early_inline(), BUILTINS_LOCATION, CDI_DOMINATORS, CDI_POST_DOMINATORS, cleanup_tree_cfg(), compute_fn_summary(), compute_function_frequency(), current_function_decl, symtab_node::decl, DECL_SOURCE_LOCATION, DECL_STRUCT_FUNCTION, early_inline(), execute_fixup_cfg(), FINISHED, FOR_EACH_FUNCTION, free_dominance_info(), cgraph_node::get(), gimple_has_body_p(), i, init_node_map(), pop_cfun(), profile_info, push_cfun(), cgraph_edge::rebuild_edges(), symtab, todo, and TODO_cleanup_cfg.

early_inline()

static unsigned int autofdo::early_inline ( )

static

Wrapper function to invoke early inliner.   

References cfun, compute_fn_summary(), current_function_decl, early_inliner(), cgraph_node::get(), todo, TODO_update_ssa, TODO_update_ssa_any, and update_ssa().

Referenced by auto_profile().

fake_read_autofdo_module_profile()

static void autofdo::fake_read_autofdo_module_profile ( )

static

Module profile is only used by LIPO. Here we simply ignore it.   

References gcc_assert, and gcov_read_unsigned().

Referenced by read_profile().

get_combined_location()

static unsigned autofdo::get_combined_location ( location_t loc, tree decl )

static

Return the combined location, which is a 32bit integer in which
higher 16 bits stores the line offset of LOC to the start lineno
of DECL, The lower 16 bits stores the discriminator.   

References DECL_SOURCE_LINE, get_discriminator_from_loc(), LOCATION_LINE, and warning_at().

Referenced by get_inline_stack(), and get_relative_location_for_stmt().

get_function_decl_from_block()

static tree autofdo::get_function_decl_from_block ( tree block )

static

Return the function decl of a given lexical BLOCK.   

References BLOCK_ABSTRACT_ORIGIN, inlined_function_outer_scope_p(), and NULL_TREE.

Referenced by get_inline_stack(), and get_relative_location_for_stmt().

get_inline_stack()

static void autofdo::get_inline_stack ( location_t locus, inline_stack * stack )

static

Store inline stack for STMT in STACK.   

References BLOCK_SOURCE_LOCATION, BLOCK_SUPERCONTEXT, current_function_decl, get_combined_location(), get_function_decl_from_block(), LOCATION_BLOCK, LOCATION_LOCUS, TREE_CODE, and UNKNOWN_LOCATION.

Referenced by autofdo::autofdo_source_profile::get_callsite_total_count(), autofdo::autofdo_source_profile::get_count_info(), autofdo::autofdo_source_profile::mark_annotated(), and autofdo::autofdo_source_profile::update_inlined_ind_target().

get_original_name()

static char * autofdo::get_original_name ( const char * name )

static

Helper functions.   

Return the original name of NAME: strip the suffix that starts
with '.' Caller is responsible for freeing RET.   

References find(), and NULL.

Referenced by autofdo::string_table::get_index_by_decl(), and autofdo::string_table::read().

get_relative_location_for_stmt()

static unsigned autofdo::get_relative_location_for_stmt ( gimple * stmt )

static

Return STMT's combined location, which is a 32bit integer in which
higher 16 bits stores the line offset of LOC to the start lineno
of DECL, The lower 16 bits stores the discriminator.   

References BLOCK_SOURCE_LOCATION, BLOCK_SUPERCONTEXT, current_function_decl, get_combined_location(), get_function_decl_from_block(), gimple_block(), gimple_location(), LOCATION_LOCUS, TREE_CODE, and UNKNOWN_LOCATION.

Referenced by autofdo::function_instance::find_icall_target_map().

has_indirect_call()

static bool autofdo::has_indirect_call ( basic_block bb )

static

Return true if BB contains indirect call.   

References gimple_call_fn(), gimple_call_internal_p(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), NULL, and TREE_CODE.

Referenced by afdo_vpt_for_early_inline().

is_bb_annotated()

static bool autofdo::is_bb_annotated ( const basic_block bb, const bb_set & annotated )

static

Referenced by afdo_find_equiv_class(), afdo_propagate(), afdo_propagate_circuit(), and afdo_propagate_edge().

read_profile()

static void autofdo::read_profile ( void )

static

Read data from profile data file.   

References afdo_source_profile, afdo_string_table, AUTO_PROFILE_VERSION, autofdo::autofdo_source_profile::create(), error(), fake_read_autofdo_module_profile(), GCOV_DATA_MAGIC, gcov_open(), gcov_read_unsigned(), and NULL.

Referenced by read_autofdo_file().

set_bb_annotated()

static void autofdo::set_bb_annotated ( basic_block bb, bb_set * annotated )

static

Referenced by afdo_annotate_cfg(), afdo_find_equiv_class(), afdo_propagate(), and afdo_propagate_edge().

Variable Documentation

afdo_profile_info

gcov_summary* autofdo::afdo_profile_info

static

gcov_summary structure to store the profile_info.   

Referenced by afdo_callsite_hot_enough_for_early_inline(), auto_profile(), and read_autofdo_file().

afdo_source_profile

autofdo_source_profile* autofdo::afdo_source_profile

static

Store the AutoFDO source profile.   

Referenced by afdo_annotate_cfg(), afdo_callsite_hot_enough_for_early_inline(), afdo_set_bb_count(), afdo_vpt_for_early_inline(), end_auto_profile(), and read_profile().

afdo_string_table

string_table* autofdo::afdo_string_table

static

Store the strings read from the profile data file.   

Referenced by afdo_indirect_call(), end_auto_profile(), autofdo::function_instance::find_icall_target_map(), autofdo::autofdo_source_profile::get_callsite_total_count(), autofdo::autofdo_source_profile::get_function_instance_by_decl(), autofdo::function_instance::get_function_instance_by_decl(), autofdo::autofdo_source_profile::get_function_instance_by_inline_stack(), and read_profile().