[GOOGLE] Iterative AutoFDO
Dehao Chen
dehao@google.com
Mon Oct 7 18:49:00 GMT 2013
Hi, David,
Thanks for the review. Patch updated.
Dehao
On Sun, Oct 6, 2013 at 11:54 AM, Xinliang David Li <davidxl@google.com> wrote:
> Adding additional early inline + value transform (calling them as
> utility functions) is 'unconventional' way of invoking passes. It
> would be helpful to do more heavy documentation by providing more
> examples and explaining why simply augmenting the indirect target info
> for promoted icall site with inlined call stack profile data and rely
> on existing value profile transform to kick in is not enough.
>
> The patch also misses documentation for many functions at the
> definition site. There are also a couple of coding style problems such
> as function name does not start a new line (but following return
> type).
>
>
>
>> /* Return the combined relative location for STMT. */
>
>> static unsigned
>> get_relative_location_for_stmt (gimple stmt)
>> {
>
> More explanation on 'relative' -- it is not mentioned in other places either.
>
>
>> /* Program behavior changed, original promoted (and inlined) target is not
>> hot any more. Will avoid promote the original target. */
>> if (total >= info->first * 0.5)
>> return false;
>
> This needs more explanation.
>
>> /* For a given BB, return its execution count, and annotate value profile
>> if a stmt is not in PROMOTED. Add the location of annotated stmt to
>> ANNOTATED. */
>
> More explanation on why skipping promoted ones.
>
> > || promoted_stmts->find (stmt) != promoted_stmts->end ())
> > continue;
> > promoted_stmts->insert (stmt);
>
> It is not quite clear how 'promoted' stmts are identified here.
>
>> /* First do indirect call promotion and early inline to make the
>> IR match the profiled binary before actual annotation. */
>> autofdo::stmt_set promoted_stmts;
>> for (int i = 0; i < PARAM_VALUE (PARAM_EARLY_INLINER_MAX_ITERATIONS); i++)
>> {
>> early_inliner ();
>> if (!flag_value_profile_transformations
>> || !autofdo::afdo_vpt_for_early_inline (&promoted_stmts))
>> break;
>> }'
>
> This needs heavy documentation. ALso why putting early inline before
> value transform?
>
> David
>
>
>
>
> On Mon, Sep 23, 2013 at 10:51 AM, Dehao Chen <dehao@google.com> wrote:
>> 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.
>>
>> Bootstrapped and passed regression test and benchmark test.
>>
>> OK for google-4_8 branch?
>>
>> Thanks,
>> Dehao
>>
>> http://codereview.appspot.com/13492045
-------------- next part --------------
Index: value-prof.c
===================================================================
--- value-prof.c (revision 203250)
+++ value-prof.c (working copy)
@@ -1327,7 +1327,7 @@ find_func_by_global_id (unsigned HOST_WIDE_INT gid
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;
Index: passes.c
===================================================================
--- passes.c (revision 203250)
+++ passes.c (working copy)
@@ -1366,8 +1366,8 @@ init_optimization_passes (void)
NEXT_PASS (pass_rebuild_cgraph_edges);
NEXT_PASS (pass_inline_parameters);
}
+ NEXT_PASS (pass_ipa_auto_profile);
NEXT_PASS (pass_ipa_free_inline_summary);
- NEXT_PASS (pass_ipa_auto_profile);
NEXT_PASS (pass_ipa_tree_profile);
{
struct opt_pass **p = &pass_ipa_tree_profile.pass.sub;
Index: coverage.h
===================================================================
--- coverage.h (revision 203250)
+++ coverage.h (working copy)
@@ -58,6 +58,8 @@ extern gcov_type *get_coverage_counts_no_warn (str
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
Index: ipa-inline.c
===================================================================
--- ipa-inline.c (revision 203250)
+++ ipa-inline.c (working copy)
@@ -2203,7 +2203,7 @@ early_inline_small_functions (struct cgraph_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);
Index: ipa-inline.h
===================================================================
--- ipa-inline.h (revision 203250)
+++ ipa-inline.h (working copy)
@@ -201,6 +201,9 @@ typedef struct edge_growth_cache_entry
extern vec<int> node_growth_cache;
extern vec<edge_growth_cache_entry> 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);
Index: auto-profile.c
===================================================================
--- auto-profile.c (revision 203250)
+++ auto-profile.c (working copy)
@@ -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<gcov_type, icall_target_map> cou
annotate the program. */
typedef std::set<inline_stack> location_set;
+/* Set of gimple stmts. Used to track if the stmt has already been promoted
+ to direct call. */
+typedef std::set<gimple> stmt_set;
+
struct string_compare
{
bool operator() (const char *a, const char *b) const
@@ -168,6 +174,10 @@ class function_instance {
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) {}
@@ -215,6 +225,10 @@ class autofdo_source_profile {
/* 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. */
@@ -353,7 +367,43 @@ 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. */
function_name_map *function_name_map::create ()
@@ -472,6 +522,35 @@ bool function_instance::get_count_info (location_t
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->first.second;
+ /* Check if callsite location match the stmt. */
+ if (iter->first.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;
+}
+
const function_instance *function_instance::read_function_instance (
function_instance_stack *stack, gcov_type head_count)
{
@@ -547,6 +626,44 @@ 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. */
+ 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;
+}
+
gcov_type autofdo_source_profile::get_callsite_total_count (
struct cgraph_edge *edge) const
{
@@ -826,11 +943,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;
@@ -845,7 +964,7 @@ static gcov_type
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);
}
}
@@ -1222,10 +1341,77 @@ 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);
+ /* 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 =
@@ -1238,7 +1424,7 @@ static 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)
{
@@ -1253,7 +1439,7 @@ static 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;
}
@@ -1302,7 +1488,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 be promoted and
+ inlined in the profiled binary. If we do not promote and inline
+ these indirect calls before annothation, 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 ();
@@ -1327,7 +1550,7 @@ auto_profile (void)
push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl));
if (L_IPO_COMP_MODE)
- {
+ {
basic_block bb;
FOR_EACH_BB (bb)
{
More information about the Gcc-patches
mailing list