From cdbfaa3e1c6b75c960f6d983b70a712631f6042d Mon Sep 17 00:00:00 2001 From: dehao Date: Fri, 11 Oct 2013 14:30:28 +0000 Subject: [PATCH] This patch fixes the issue of indirect call promotion while using AutoFDO optimized binary to collect profile, and use the new profile to re-optimize the binary. Before the patch, the indirect call is promoted (and likely inlined) in the profiled binary, and will not be promoted in the new iteration. With the patch, a new iterative vpt+einline pass is added before annotation to make sure hot promoted indirect calls are still promoted before annotation. 2013-10-11 Dehao Chen * gcc/coverage.h (check_ic_target): New declaration. * gcc/auto-profile.c (stmt_set): New type. (function_instance::find_icall_target_map): New function. (autofdo_source_profile::update_inlined_ind_target): New function. (get_relative_location_for_stmt): New function. (has_indirect_call): New function. (afdo_get_bb_count): New parameter. (afdo_vpt_for_early_inline): New function. (afdo_annotate_cfg): New parameter. * gcc/passes.c (init_optimization_passes): Change order. * gcc/value-prof.c (check_ic_target): Change scope. * gcc/ipa-inline.c (early_inliner): Change scope. * gcc/ipa-inline.h (early_inliner): New declaration. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/google@203445 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc-4_8/gcc/auto-profile.c | 280 +++++++++++++++++++++++++++++++++++++++++++-- gcc-4_8/gcc/coverage.h | 2 + gcc-4_8/gcc/ipa-inline.c | 2 +- gcc-4_8/gcc/ipa-inline.h | 3 + gcc-4_8/gcc/passes.c | 2 +- gcc-4_8/gcc/value-prof.c | 2 +- 6 files changed, 278 insertions(+), 13 deletions(-) diff --git a/gcc-4_8/gcc/auto-profile.c b/gcc-4_8/gcc/auto-profile.c index 62eaf53730c..725d4017bf0 100644 --- a/gcc-4_8/gcc/auto-profile.c +++ b/gcc-4_8/gcc/auto-profile.c @@ -47,6 +47,8 @@ along with GCC; see the file COPYING3. If not see #include "coverage.h" #include "params.h" #include "l-ipo.h" +#include "ipa-utils.h" +#include "ipa-inline.h" #include "auto-profile.h" /* The following routines implements AutoFDO optimization. @@ -106,6 +108,10 @@ typedef std::pair count_info; annotate the program. */ typedef std::set location_set; +/* Set of gimple stmts. Used to track if the stmt has already been promoted + to direct call. */ +typedef std::set stmt_set; + struct string_compare { bool operator() (const char *a, const char *b) const @@ -168,9 +174,16 @@ public: is found. */ bool get_count_info (location_t loc, count_info *info) const; + /* Read the inlinied indirect call target profile for STMT and store it in + MAP, return the total count for all inlined indirect calls. */ + gcov_type find_icall_target_map (gimple stmt, icall_target_map *map) const; + private: function_instance (unsigned name, gcov_type head_count) : name_(name), total_count_(0), head_count_(head_count) {} + + /* Traverse callsites of the current function_instance to find one at the + location of LINENO and callee name represented in DECL. */ const function_instance *get_function_instance_by_decl (unsigned lineno, tree decl) const; @@ -214,6 +227,10 @@ public: /* Find total count of the callee of EDGE. */ gcov_type get_callsite_total_count (struct cgraph_edge *edge) const; + /* Update value profile INFO for STMT from the inlined indirect callsite. + Return true if INFO is updated. */ + bool update_inlined_ind_target (gimple stmt, count_info *info); + private: /* Map from function_instance name index (in function_name_map) to function_instance. */ @@ -352,6 +369,42 @@ get_inline_stack (gimple stmt, inline_stack *stack) get_combined_location (locus, current_function_decl))); } +/* 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 discrimnator. */ + +static unsigned +get_relative_location_for_stmt (gimple stmt) +{ + location_t locus = gimple_location (stmt); + if (LOCATION_LOCUS (locus) == UNKNOWN_LOCATION) + return UNKNOWN_LOCATION; + + for (tree block = gimple_block (stmt); + block && (TREE_CODE (block) == BLOCK); + block = BLOCK_SUPERCONTEXT (block)) + if (LOCATION_LOCUS (BLOCK_SOURCE_LOCATION (block)) != UNKNOWN_LOCATION) + return get_combined_location ( + locus, get_function_decl_from_block (block)); + return get_combined_location (locus, current_function_decl); +} + +/* Return true if BB contains indirect call. */ + +static bool +has_indirect_call (basic_block bb) +{ + gimple_stmt_iterator gsi; + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple stmt = gsi_stmt (gsi); + if (gimple_code (stmt) == GIMPLE_CALL + && TREE_CODE (gimple_call_fn (stmt)) != FUNCTION_DECL) + return true; + } + return false; +} /* Member functions for function_name_map. */ @@ -423,6 +476,9 @@ function_instance::~function_instance () delete iter->second; } +/* Traverse callsites of the current function_instance to find one at the + location of LINENO and callee name represented in DECL. */ + const function_instance *function_instance::get_function_instance_by_decl ( unsigned lineno, tree decl) const { @@ -447,6 +503,9 @@ const function_instance *function_instance::get_function_instance_by_decl ( return NULL; } +/* Recursively traverse STACK starting from LEVEL to find the corresponding + function_instance. */ + const function_instance *function_instance::get_function_instance ( const inline_stack &stack, unsigned level) const { @@ -460,6 +519,9 @@ const function_instance *function_instance::get_function_instance ( return NULL; } +/* Store the profile info for LOC in INFO. Return TRUE if profile info + is found. */ + bool function_instance::get_count_info (location_t loc, count_info *info) const { position_count_map::const_iterator iter = pos_counts.find (loc); @@ -469,6 +531,39 @@ bool function_instance::get_count_info (location_t loc, count_info *info) const return true; } +/* Read the inlinied indirect call target profile for STMT and store it in + MAP, return the total count for all inlined indirect calls. */ + +gcov_type +function_instance::find_icall_target_map ( + gimple stmt, icall_target_map *map) const +{ + gcov_type ret = 0; + unsigned stmt_offset = get_relative_location_for_stmt (stmt); + + for (callsite_map::const_iterator iter = callsites.begin(); + iter != callsites.end(); ++iter) + { + unsigned callee = iter->second->name(); + /* Check if callsite location match the stmt. */ + if (iter->first != stmt_offset) + continue; + struct cgraph_node *node = find_func_by_global_id ( + (unsigned long long) afdo_function_name_map->get_name (callee), true); + if (node == NULL) + continue; + if (!check_ic_target (stmt, node)) + continue; + (*map)[callee] = iter->second->total_count (); + ret += iter->second->total_count (); + } + return ret; +} + +/* Read the profile and create a function_instance with head count as + HEAD_COUNT. Recursively read callsites to create nested function_instances + too. STACK is used to track the recursive creation process. */ + const function_instance *function_instance::read_function_instance ( function_instance_stack *stack, gcov_type head_count) { @@ -513,6 +608,8 @@ autofdo_source_profile::~autofdo_source_profile () delete iter->second; } +/* For a given DECL, returns the top-level function_instance. */ + const function_instance *autofdo_source_profile::get_function_instance_by_decl ( tree decl) const { @@ -523,6 +620,10 @@ const function_instance *autofdo_source_profile::get_function_instance_by_decl ( return ret == map_.end() ? NULL : ret->second; } +/* Find profile info for a given gimple STMT. If found, and if the location + of STMT does not exist in ANNOTATED, store the profile info in INFO, and + return true; otherwise return false. */ + bool autofdo_source_profile::get_count_info ( gimple stmt, count_info *info, const location_set *annotated) const { @@ -541,6 +642,51 @@ bool autofdo_source_profile::get_count_info ( return s->get_count_info (stack[0].second, info); } +/* Update value profile INFO for STMT from the inlined indirect callsite. + Return true if INFO is updated. */ + +bool +autofdo_source_profile::update_inlined_ind_target ( + gimple stmt, count_info *info) +{ + if (LOCATION_LOCUS (gimple_location (stmt)) == cfun->function_end_locus) + return false; + + count_info old_info; + get_count_info (stmt, &old_info, NULL); + gcov_type total = 0; + for (icall_target_map::const_iterator iter = old_info.second.begin(); + iter != old_info.second.end(); ++iter) + total += iter->second; + + /* Program behavior changed, original promoted (and inlined) target is not + hot any more. Will avoid promote the original target. + + To check if original promoted target is still hot, we check the total + count of the unpromoted targets (stored in old_info). If it is no less + than half of the callsite count (stored in INFO), the original promoted + target is considered not hot any more. */ + if (total >= info->first * 0.5) + return false; + + inline_stack stack; + get_inline_stack (stmt, &stack); + if (stack.size () == 0) + return false; + const function_instance *s = get_function_instance_by_inline_stack (stack); + if (s == NULL) + return false; + icall_target_map map; + if (s->find_icall_target_map (stmt, &map) == 0) + return false; + for (icall_target_map::const_iterator iter = map.begin(); + iter != map.end(); ++iter) + info->second[iter->first] = iter->second; + return true; +} + +/* Find total count of the callee of EDGE. */ + gcov_type autofdo_source_profile::get_callsite_total_count ( struct cgraph_edge *edge) const { @@ -555,6 +701,8 @@ gcov_type autofdo_source_profile::get_callsite_total_count ( return s->total_count (); } +/* Read source profile. */ + bool autofdo_source_profile::read () { if (gcov_read_unsigned () != GCOV_TAG_AFDO_FUNCTION) @@ -580,6 +728,9 @@ bool autofdo_source_profile::read () return true; } +/* Return the function_instance in the profile that correspond to the + inline STACK. */ + const function_instance * autofdo_source_profile::get_function_instance_by_inline_stack ( const inline_stack &stack) const @@ -648,6 +799,8 @@ bool autofdo_module_profile::read () return true; } +/* Read the profile from the profile file. */ + static void read_profile (void) { @@ -820,11 +973,13 @@ afdo_vpt (gimple stmt, const icall_target_map &map) afdo_indirect_call (stmt, map); } -/* For a given BB, return its execution count, and annotate value profile - on statements. Add the location of annotated stmt to ANNOTATED. */ +/* For a given BB, return its execution count. Add the location of annotated + stmt to ANNOTATED. Attach value profile if a stmt is not in PROMOTED, + because we only want to promot an indirect call once. */ static gcov_type -afdo_get_bb_count (basic_block bb, location_set *annotated) +afdo_get_bb_count (basic_block bb, location_set *annotated, + const stmt_set &promoted) { gimple_stmt_iterator gsi; gcov_type max_count = 0; @@ -839,7 +994,7 @@ afdo_get_bb_count (basic_block bb, location_set *annotated) if (info.first > max_count) max_count = info.first; has_annotated = true; - if (info.second.size() > 0) + if (info.second.size() > 0 && promoted.find (stmt) == promoted.end ()) afdo_vpt (stmt, info.second); } } @@ -1216,10 +1371,78 @@ afdo_calculate_branch_prob (void) free_dominance_info (CDI_POST_DOMINATORS); } -/* Annotate auto profile to the control flow graph. */ +/* Perform value profile transformation using AutoFDO profile. Add the + promoted stmts to PROMOTED_STMTS. Return TRUE if there is any + indirect call promoted. */ + +static bool +afdo_vpt_for_early_inline (stmt_set *promoted_stmts) +{ + basic_block bb; + if (afdo_source_profile->get_function_instance_by_decl ( + current_function_decl) == NULL) + return false; + + bool has_vpt = false; + FOR_EACH_BB (bb) + { + if (!has_indirect_call (bb)) + continue; + gimple_stmt_iterator gsi; + + gcov_type bb_count = 0; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + count_info info; + gimple stmt = gsi_stmt (gsi); + if (afdo_source_profile->get_count_info (stmt, &info, NULL)) + bb_count = MAX (bb_count, info.first); + } + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple stmt = gsi_stmt (gsi); + /* IC_promotion and early_inline_2 is done in multiple iterations. + No need to promoted the stmt if its in promoted_stmts (means + it is already been promoted in the previous iterations). */ + if (gimple_code (stmt) != GIMPLE_CALL + || TREE_CODE (gimple_call_fn (stmt)) == FUNCTION_DECL + || promoted_stmts->find (stmt) != promoted_stmts->end ()) + continue; + + count_info info; + afdo_source_profile->get_count_info (stmt, &info, NULL); + info.first = bb_count; + if (afdo_source_profile->update_inlined_ind_target (stmt, &info)) + { + /* Promote the indirect call and update the promoted_stmts. */ + promoted_stmts->insert (stmt); + afdo_vpt (stmt, info.second); + has_vpt = true; + } + } + } + if (has_vpt && gimple_value_profile_transformations ()) + { + free_dominance_info (CDI_DOMINATORS); + free_dominance_info (CDI_POST_DOMINATORS); + calculate_dominance_info (CDI_POST_DOMINATORS); + calculate_dominance_info (CDI_DOMINATORS); + rebuild_cgraph_edges (); + update_ssa (TODO_update_ssa); + compute_inline_parameters (cgraph_get_node (current_function_decl), + false); + return true; + } + else + return false; +} + +/* Annotate auto profile to the control flow graph. Do not annotate value + profile for stmts in PROMOTED_STMTS. */ static void -afdo_annotate_cfg (void) +afdo_annotate_cfg (const stmt_set &promoted_stmts) { basic_block bb; const function_instance *s = @@ -1232,7 +1455,7 @@ afdo_annotate_cfg (void) ENTRY_BLOCK_PTR->count = s->head_count (); gcov_type max_count = ENTRY_BLOCK_PTR->count; - location_set annotated_loc_set; + location_set annotated_locs; FOR_EACH_BB (bb) { @@ -1247,7 +1470,7 @@ afdo_annotate_cfg (void) e->flags &= (~EDGE_ANNOTATED); } - bb->count = afdo_get_bb_count (bb, &annotated_loc_set); + bb->count = afdo_get_bb_count (bb, &annotated_locs, promoted_stmts); if (bb->count > max_count) max_count = bb->count; } @@ -1296,7 +1519,44 @@ auto_profile (void) continue; push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl)); - autofdo::afdo_annotate_cfg (); + + /* First do indirect call promotion and early inline to make the + IR match the profiled binary before actual annotation. + + This is needed because an indirect call might have been promoted + and inlined in the profiled binary. If we do not promote and + inline these indirect calls before annotation, the profile for + these promoted functions will be lost. + + e.g. foo() --indirect_call--> bar() + In profiled binary, the callsite is promoted and inlined, making + the profile look like: + + foo: { + loc_foo_1: count_1 + bar@loc_foo_2: { + loc_bar_1: count_2 + loc_bar_2: count_3 + } + } + + Before AutoFDO pass, loc_foo_2 is not promoted thus not inlined. + If we perform annotation on it, the profile inside bar@loc_foo2 + will be wasted. + + To avoid this, we promote loc_foo_2 and inline the promoted bar + function before annotation, so the profile inside bar@loc_foo2 + will be useful. */ + autofdo::stmt_set promoted_stmts; + for (int i = 0; i < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS); i++) + { + if (!flag_value_profile_transformations + || !autofdo::afdo_vpt_for_early_inline (&promoted_stmts)) + break; + early_inliner (); + } + + autofdo::afdo_annotate_cfg (promoted_stmts); compute_function_frequency (); update_ssa (TODO_update_ssa); pop_cfun (); @@ -1321,7 +1581,7 @@ auto_profile (void) push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl)); if (L_IPO_COMP_MODE) - { + { basic_block bb; FOR_EACH_BB (bb) { diff --git a/gcc-4_8/gcc/coverage.h b/gcc-4_8/gcc/coverage.h index 3fd252b8b24..8d610924789 100644 --- a/gcc-4_8/gcc/coverage.h +++ b/gcc-4_8/gcc/coverage.h @@ -58,6 +58,8 @@ extern gcov_type *get_coverage_counts_no_warn (struct function *, extern struct cgraph_node * find_func_by_global_id (unsigned HOST_WIDE_INT gid, bool); +extern bool check_ic_target (gimple call_stmt, struct cgraph_node *target); + /* All the coverage counters are supposed to be allocated by the time coverage_end_function is called. However, direct-call counters are allocated after coverage_end_function has been called. This function diff --git a/gcc-4_8/gcc/ipa-inline.c b/gcc-4_8/gcc/ipa-inline.c index cdc58cf9cc1..4f812d7d550 100644 --- a/gcc-4_8/gcc/ipa-inline.c +++ b/gcc-4_8/gcc/ipa-inline.c @@ -2203,7 +2203,7 @@ early_inline_small_functions (struct cgraph_node *node) /* Do inlining of small functions. Doing so early helps profiling and other passes to be somewhat more effective and avoids some code duplication in later real inlining pass for testcases with very many function calls. */ -static unsigned int +unsigned int early_inliner (void) { struct cgraph_node *node = cgraph_get_node (current_function_decl); diff --git a/gcc-4_8/gcc/ipa-inline.h b/gcc-4_8/gcc/ipa-inline.h index 3988b3b80a5..49b5e27091c 100644 --- a/gcc-4_8/gcc/ipa-inline.h +++ b/gcc-4_8/gcc/ipa-inline.h @@ -201,6 +201,9 @@ typedef struct edge_growth_cache_entry extern vec node_growth_cache; extern vec edge_growth_cache; +/* In ipa-inline.c */ +unsigned int early_inliner (void); + /* In ipa-inline-analysis.c */ void debug_inline_summary (struct cgraph_node *); void dump_inline_summaries (FILE *f); diff --git a/gcc-4_8/gcc/passes.c b/gcc-4_8/gcc/passes.c index a3c5571c01c..1aa06005749 100644 --- a/gcc-4_8/gcc/passes.c +++ b/gcc-4_8/gcc/passes.c @@ -1366,8 +1366,8 @@ init_optimization_passes (void) NEXT_PASS (pass_rebuild_cgraph_edges); NEXT_PASS (pass_inline_parameters); } - NEXT_PASS (pass_ipa_free_inline_summary); NEXT_PASS (pass_ipa_auto_profile); + NEXT_PASS (pass_ipa_free_inline_summary); NEXT_PASS (pass_ipa_tree_profile); { struct opt_pass **p = &pass_ipa_tree_profile.pass.sub; diff --git a/gcc-4_8/gcc/value-prof.c b/gcc-4_8/gcc/value-prof.c index 924174429f4..f14baa1b08a 100644 --- a/gcc-4_8/gcc/value-prof.c +++ b/gcc-4_8/gcc/value-prof.c @@ -1327,7 +1327,7 @@ find_func_by_global_id (unsigned HOST_WIDE_INT gid, bool is_auto_fdo) 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. */ -static bool +bool check_ic_target (gimple call_stmt, struct cgraph_node *target) { location_t locus; -- 2.11.4.GIT