Patchwork [google] Add options to pattern match function name for hotness attributes

login
register
mail settings
Submitter Dehao Chen
Date June 1, 2012, 8:26 a.m.
Message ID <CAO2gOZUrnW+V-wUbZ5vLCN5yne+uivUtpptzemkrRU5o5UhFLg@mail.gmail.com>
Download mbox | patch
Permalink /patch/162274/
State New
Headers show

Comments

Dehao Chen - June 1, 2012, 8:26 a.m.
Hi,

This patch adds 4 flags to enable user to type in a list of name
patterns. Compiler will match the function name with the given
patterns, and add "hot", "cold", "likely_hot", "likely_cold"
attributes to function declaration. The static branch prediction
checks if a basic block contains call to a annotated function, and set
the branch probability accordingly.

Bootstrapped and passed gcc testsuites.

Ok for google branches?

Thanks,
Dehao

gcc/ChangeLog.google-4_6
2012-06-01  Dehao Chen  <dehao@google.com>

	* gcc/cgraph.c (cgraph_match_hotness_by_name): New function.
	(cgraph_add_hotness_attribute): New function.
	(cgraph_node): Add hotness attribute to function decl.
	* gcc/opts.c (common_handle_option): Handle new options.
	* gcc/predict.c (tree_bb_level_predictions): New prediction.
	* gcc/predict.def (PRED_LIKELY_COLD_FUNCTION): New prediction.
	* gcc/common.opt (flag_function_hot_list): New option.
	(flag_function_cold_list): New option.
	(flag_function_likely_hot_list): New option.
	(flag_function_likely_cold_list): New option.
Xinliang David Li - June 1, 2012, 4:43 p.m.
On Fri, Jun 1, 2012 at 1:26 AM, Dehao Chen <dehao@google.com> wrote:
> Hi,
>
> This patch adds 4 flags to enable user to type in a list of name
> patterns. Compiler will match the function name with the given
> patterns, and add "hot", "cold", "likely_hot", "likely_cold"
> attributes to function declaration. The static branch prediction
> checks if a basic block contains call to a annotated function, and set
> the branch probability accordingly.

This is generally useful for cases where shared library code exhibits
different behavior among the applications  (so that source annotation
is not applicable).

You need to explain more on the likely_cold|hot attribute and the
intuition behind it.

>
> Bootstrapped and passed gcc testsuites.
>
> Ok for google branches?
>
> Thanks,
> Dehao
>
> gcc/ChangeLog.google-4_6
> 2012-06-01  Dehao Chen  <dehao@google.com>
>
>        * gcc/cgraph.c (cgraph_match_hotness_by_name): New function.
>        (cgraph_add_hotness_attribute): New function.
>        (cgraph_node): Add hotness attribute to function decl.
>        * gcc/opts.c (common_handle_option): Handle new options.
>        * gcc/predict.c (tree_bb_level_predictions): New prediction.
>        * gcc/predict.def (PRED_LIKELY_COLD_FUNCTION): New prediction.
>        * gcc/common.opt (flag_function_hot_list): New option.
>        (flag_function_cold_list): New option.
>        (flag_function_likely_hot_list): New option.
>        (flag_function_likely_cold_list): New option.
>
> Index: gcc/doc/invoke.texi
> ===================================================================
> --- gcc/doc/invoke.texi (revision 188050)
> +++ gcc/doc/invoke.texi (working copy)
> @@ -362,7 +362,9 @@
>  -fdelete-null-pointer-checks -fdse -fdevirtualize -fdse @gol
>  -fearly-inlining -fipa-sra -fexpensive-optimizations -ffast-math @gol
>  -ffinite-math-only -ffloat-store -fexcess-precision=@var{style} @gol
> --fforward-propagate -ffp-contract=@var{style} -ffunction-sections @gol
> +-fforward-propagate -ffp-contract=@var{style} @gol
> +-ffunction-cold-list -ffunction-hot-list -ffunction-likely-cold-list @gol
> +-ffunction-likely-hot-list -ffunction-sections @gol
>  -fgcse -fgcse-after-reload -fgcse-las -fgcse-lm -fgraphite-identity @gol
>  -fgcse-sm -fif-conversion -fif-conversion2 -findirect-inlining @gol
>  -finline-functions -finline-functions-called-once -finline-limit=@var{n} @gol
> @@ -8585,6 +8587,22 @@
>  specify this option and you may have problems with debugging if
>  you specify both this option and @option{-g}.
>
> +@item -ffunction-cold-list
> +@opindex ffunction-cold-list
> +List of function name patterns that will be applied "cold" attribute.
> +
> +@item -ffunction-hot-list
> +@opindex ffunction-hot-list
> +List of function name patterns that will be applied "hot" attribute.
> +
> +@item -ffunction-likely-cold-list
> +@opindex ffunction-likely-cold-list
> +List of function name patterns that will be applied "likely_cold" attribute.
> +
> +@item -ffunction-likely-hot-list
> +@opindex ffunction-likely-hot-list
> +List of function name patterns that will be applied "likely_hot" attribute.
> +
>  @item -fbranch-target-load-optimize
>  @opindex fbranch-target-load-optimize
>  Perform branch target register load optimization before prologue / epilogue
> Index: gcc/cgraph.c
> ===================================================================
> --- gcc/cgraph.c        (revision 188050)
> +++ gcc/cgraph.c        (working copy)
> @@ -520,6 +520,70 @@
>     }
>  }
>
> +typedef char *char_pointer;
> +DEF_VEC_P(char_pointer);
> +DEF_VEC_ALLOC_P(char_pointer,heap);
> +
> +/* Match FNDECL's name with PATTERNS. If matched, add HOTNESS attribute
> +   to FNDECL.
> +   name matches with pattern, iff one of the following conditions satisfy:
> +     1. strcmp (name, pattern) != 0


strcmp(name, pattern) == 0


> +     2. pattern[len - 1] = '*' && strncmp (name, pattern, len - 1) != 0  */
> +static bool

strncmp (name, pattern, len -1 ) == 0

> +cgraph_match_hotness_by_name (tree fndecl,
> +                             VEC(char_pointer, heap) *patterns,
> +                             const char *hotness)
> +{
> +  unsigned i;
> +  char_pointer n;
> +  const char *name = lang_hooks.decl_printable_name(fndecl, 0);
> +
> +  if (!name)
> +    return false;
> +
> +  FOR_EACH_VEC_ELT (char_pointer, patterns, i, n)
> +    {
> +      int len = strlen (n);
> +      if ((n[len - 1] == '*' && !strncmp (name, n, len - 1))
> +          || !strcmp (name, n))
> +        {
> +          decl_attributes (&fndecl, tree_cons (
> +              get_identifier (hotness), NULL, NULL), 0);
> +          return true;
> +        }
> +    }
> +  return false;
> +}
> +
> +/* Add hotness attributes to FNDECL.  */

Empty line after.

> +static void
> +cgraph_add_hotness_attribute (tree fndecl)
> +{
> +  if (lookup_attribute ("cold", DECL_ATTRIBUTES (fndecl))
> +      || lookup_attribute ("hot", DECL_ATTRIBUTES (fndecl))
> +      || lookup_attribute ("likely_cold", DECL_ATTRIBUTES (fndecl))
> +      || lookup_attribute ("likely_hot", DECL_ATTRIBUTES (fndecl)))
> +    return;
> +
> +  if (cgraph_match_hotness_by_name (fndecl,
> +       (VEC(char_pointer, heap) *) flag_function_cold_list, "cold"))
> +    return;
> +
> +  if (cgraph_match_hotness_by_name (fndecl,
> +       (VEC(char_pointer, heap) *) flag_function_hot_list, "hot"))
> +    return;
> +
> +  if (cgraph_match_hotness_by_name (fndecl,
> +       (VEC(char_pointer, heap) *) flag_function_likely_cold_list,
> +       "likely_cold"))
> +    return;
> +
> +  if (cgraph_match_hotness_by_name (fndecl,
> +       (VEC(char_pointer, heap) *) flag_function_likely_hot_list,
> +       "likely_hot"))
> +    return;
> +}
> +
>  /* Return cgraph node assigned to DECL.  Create new one when needed.  */
>
>  struct cgraph_node *
> @@ -554,6 +618,7 @@
>       node->origin->nested = node;
>     }
>   cgraph_add_assembler_hash_node (node);
> +  cgraph_add_hotness_attribute (decl);
>   return node;
>  }
>
> Index: gcc/opts.c
> ===================================================================
> --- gcc/opts.c  (revision 188050)
> +++ gcc/opts.c  (working copy)
> @@ -1539,6 +1539,26 @@
>        (&opts->x_flag_instrument_functions_exclude_files, arg);
>       break;
>
> +    case OPT_ffunction_hot_list_:
> +      add_comma_separated_to_vector
> +       (&opts->x_flag_function_hot_list, arg);
> +      break;
> +
> +    case OPT_ffunction_cold_list_:
> +      add_comma_separated_to_vector
> +       (&opts->x_flag_function_cold_list, arg);
> +      break;
> +
> +    case OPT_ffunction_likely_hot_list_:
> +      add_comma_separated_to_vector
> +       (&opts->x_flag_function_likely_hot_list, arg);
> +      break;
> +
> +    case OPT_ffunction_likely_cold_list_:
> +      add_comma_separated_to_vector
> +       (&opts->x_flag_function_likely_cold_list, arg);
> +      break;
> +
>     case OPT_fmessage_length_:
>       pp_set_line_maximum_length (dc->printer, value);
>       break;

thanks,

David
Jan Hubicka - June 2, 2012, 9:36 a.m.
> Hi,
> 
> This patch adds 4 flags to enable user to type in a list of name
> patterns. Compiler will match the function name with the given
> patterns, and add "hot", "cold", "likely_hot", "likely_cold"
> attributes to function declaration. The static branch prediction
> checks if a basic block contains call to a annotated function, and set
> the branch probability accordingly.
> 
> Bootstrapped and passed gcc testsuites.
> 
> Ok for google branches?

Just out of curiosity, what is main advantage of this over annotating your source?

Honza
Xinliang David Li - June 2, 2012, 10:03 a.m.
On Sat, Jun 2, 2012 at 2:36 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Hi,
>>
>> This patch adds 4 flags to enable user to type in a list of name
>> patterns. Compiler will match the function name with the given
>> patterns, and add "hot", "cold", "likely_hot", "likely_cold"
>> attributes to function declaration. The static branch prediction
>> checks if a basic block contains call to a annotated function, and set
>> the branch probability accordingly.
>>
>> Bootstrapped and passed gcc testsuites.
>>
>> Ok for google branches?
>
> Just out of curiosity, what is main advantage of this over annotating your source?
>

This is to avoid too much annotation at source level. Some
applications have good per application knowledge of library functions
(that are compiled and statically linked in). Another example of its
-- coarse grain (function level) profile data collected from data
center can be used to guide branch prediction/estimation.

thanks,

David
> Honza
Jan Hubicka - June 2, 2012, 10:06 a.m.
> On Sat, Jun 2, 2012 at 2:36 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> Hi,
> >>
> >> This patch adds 4 flags to enable user to type in a list of name
> >> patterns. Compiler will match the function name with the given
> >> patterns, and add "hot", "cold", "likely_hot", "likely_cold"
> >> attributes to function declaration. The static branch prediction
> >> checks if a basic block contains call to a annotated function, and set
> >> the branch probability accordingly.
> >>
> >> Bootstrapped and passed gcc testsuites.
> >>
> >> Ok for google branches?
> >
> > Just out of curiosity, what is main advantage of this over annotating your source?
> >
> 
> This is to avoid too much annotation at source level. Some
> applications have good per application knowledge of library functions
> (that are compiled and statically linked in). Another example of its
> -- coarse grain (function level) profile data collected from data
> center can be used to guide branch prediction/estimation.

Well, perhaps the feature would be more useful with command line option allowing
to add an attribute instead of having special case command line options for individual
cases.  I guess the problem would be also solvable with header included after
the library adding the attributes to the declarations

typeof (printf) printf __attribute__ ((cold));

Honza
> 
> thanks,
> 
> David
> > Honza
Dehao Chen - June 2, 2012, 11:34 a.m.
On Sat, Jun 2, 2012 at 6:06 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> On Sat, Jun 2, 2012 at 2:36 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >> Hi,
>> >>
>> >> This patch adds 4 flags to enable user to type in a list of name
>> >> patterns. Compiler will match the function name with the given
>> >> patterns, and add "hot", "cold", "likely_hot", "likely_cold"
>> >> attributes to function declaration. The static branch prediction
>> >> checks if a basic block contains call to a annotated function, and set
>> >> the branch probability accordingly.
>> >>
>> >> Bootstrapped and passed gcc testsuites.
>> >>
>> >> Ok for google branches?
>> >
>> > Just out of curiosity, what is main advantage of this over annotating your source?
>> >
>>
>> This is to avoid too much annotation at source level. Some
>> applications have good per application knowledge of library functions
>> (that are compiled and statically linked in). Another example of its
>> -- coarse grain (function level) profile data collected from data
>> center can be used to guide branch prediction/estimation.
>
> Well, perhaps the feature would be more useful with command line option allowing
> to add an attribute instead of having special case command line options for individual
> cases.

Hi, Honza, I'm not sure what you mean by "command line option allowing
to add an attribution". But this seems what this patch does: it adds
attributes to functions with specified name patterns.

>  I guess the problem would be also solvable with header included after
> the library adding the attributes to the declarations
>
> typeof (printf) printf __attribute__ ((cold));

Do you mean that for each specific application, we extract a common
header file to include all function annotations, and all source files
will include this header file?

Thanks,
Dehao

>
> Honza
>>
>> thanks,
>>
>> David
>> > Honza
Jan Hubicka - June 2, 2012, 1:17 p.m.
> > Well, perhaps the feature would be more useful with command line option allowing
> > to add an attribute instead of having special case command line options for individual
> > cases.
> 
> Hi, Honza, I'm not sure what you mean by "command line option allowing
> to add an attribution". But this seems what this patch does: it adds
> attributes to functions with specified name patterns.

I mean that if we want to go this route, we may want to allow this interface to i.e. add
always_inline attrbute or noinline or such. I can imagine this to be useful especially for
languages that has no attributes.

> 
> >  I guess the problem would be also solvable with header included after
> > the library adding the attributes to the declarations
> >
> > typeof (printf) printf __attribute__ ((cold));
> 
> Do you mean that for each specific application, we extract a common
> header file to include all function annotations, and all source files
> will include this header file?

Yes, something like that...
Where do you use the likely_hot/likely_cold logic?

Honza
> 
> Thanks,
> Dehao
> 
> >
> > Honza
> >>
> >> thanks,
> >>
> >> David
> >> > Honza
Dehao Chen - June 2, 2012, 2:16 p.m.
On Sat, Jun 2, 2012 at 9:17 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> > Well, perhaps the feature would be more useful with command line option allowing
>> > to add an attribute instead of having special case command line options for individual
>> > cases.
>>
>> Hi, Honza, I'm not sure what you mean by "command line option allowing
>> to add an attribution". But this seems what this patch does: it adds
>> attributes to functions with specified name patterns.
>
> I mean that if we want to go this route, we may want to allow this interface to i.e. add
> always_inline attrbute or noinline or such. I can imagine this to be useful especially for
> languages that has no attributes.

This annotation is mainly for static branch prediction. Some functions
may be very cold, but it may still be good to inline it.

>
>>
>> >  I guess the problem would be also solvable with header included after
>> > the library adding the attributes to the declarations
>> >
>> > typeof (printf) printf __attribute__ ((cold));
>>
>> Do you mean that for each specific application, we extract a common
>> header file to include all function annotations, and all source files
>> will include this header file?
>
> Yes, something like that...
> Where do you use the likely_hot/likely_cold logic?

For really cold functions, we predict the branch to be 0.04% taken.
However, some callee functions are not that extremely cold, and
predicting them as 0.04% is too aggressive. Likely_cold is for such
functions, and we predict them as 25% taken (at least we can predict
the direction right). Vise versa for likely_hot annotation.

Thanks,
Dehao

>
> Honza
>>
>> Thanks,
>> Dehao
>>
>> >
>> > Honza
>> >>
>> >> thanks,
>> >>
>> >> David
>> >> > Honza
Xinliang David Li - June 2, 2012, 5:30 p.m.
On Sat, Jun 2, 2012 at 3:06 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> On Sat, Jun 2, 2012 at 2:36 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >> Hi,
>> >>
>> >> This patch adds 4 flags to enable user to type in a list of name
>> >> patterns. Compiler will match the function name with the given
>> >> patterns, and add "hot", "cold", "likely_hot", "likely_cold"
>> >> attributes to function declaration. The static branch prediction
>> >> checks if a basic block contains call to a annotated function, and set
>> >> the branch probability accordingly.
>> >>
>> >> Bootstrapped and passed gcc testsuites.
>> >>
>> >> Ok for google branches?
>> >
>> > Just out of curiosity, what is main advantage of this over annotating your source?
>> >
>>
>> This is to avoid too much annotation at source level. Some
>> applications have good per application knowledge of library functions
>> (that are compiled and statically linked in). Another example of its
>> -- coarse grain (function level) profile data collected from data
>> center can be used to guide branch prediction/estimation.
>
> Well, perhaps the feature would be more useful with command line option allowing
> to add an attribute instead of having special case command line options for individual
> cases.  I guess the problem would be also solvable with header included after
> the library adding the attributes to the declarations

I think this is a good idea.


>
> typeof (printf) printf __attribute__ ((cold));
>

Actually Dehao also plans to teach the static predictor to understand
standard library functions more (e.g IO functions) and add more naming
based heuristics such as 'error, success, failure, fatal etc).

thanks,

David

> Honza
>>
>> thanks,
>>
>> David
>> > Honza
Xinliang David Li - June 2, 2012, 5:42 p.m.
Based on Honza's feedback, I think it is bettre to add command line
interface such as this:

-ffunction-attribute-list=<attribute_name>:<function_pattern_list>
or
-ffunction-attribute-filelist=<attribute_name>:<function_pattern_list_filename>

e.g,

-ffunction-attribute-list=code:foo1,foo2,bar_*,blah

It probably needs to be processed as deferred option to allow other
option to be translated into this form -- for instance extracted from
some global profile data.

thanks,

David

On Sat, Jun 2, 2012 at 7:16 AM, Dehao Chen <dehao@google.com> wrote:
> On Sat, Jun 2, 2012 at 9:17 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>> > Well, perhaps the feature would be more useful with command line option allowing
>>> > to add an attribute instead of having special case command line options for individual
>>> > cases.
>>>
>>> Hi, Honza, I'm not sure what you mean by "command line option allowing
>>> to add an attribution". But this seems what this patch does: it adds
>>> attributes to functions with specified name patterns.
>>
>> I mean that if we want to go this route, we may want to allow this interface to i.e. add
>> always_inline attrbute or noinline or such. I can imagine this to be useful especially for
>> languages that has no attributes.
>
> This annotation is mainly for static branch prediction. Some functions
> may be very cold, but it may still be good to inline it.
>
>>
>>>
>>> >  I guess the problem would be also solvable with header included after
>>> > the library adding the attributes to the declarations
>>> >
>>> > typeof (printf) printf __attribute__ ((cold));
>>>
>>> Do you mean that for each specific application, we extract a common
>>> header file to include all function annotations, and all source files
>>> will include this header file?
>>
>> Yes, something like that...
>> Where do you use the likely_hot/likely_cold logic?
>
> For really cold functions, we predict the branch to be 0.04% taken.
> However, some callee functions are not that extremely cold, and
> predicting them as 0.04% is too aggressive. Likely_cold is for such
> functions, and we predict them as 25% taken (at least we can predict
> the direction right). Vise versa for likely_hot annotation.
>
> Thanks,
> Dehao
>
>>
>> Honza
>>>
>>> Thanks,
>>> Dehao
>>>
>>> >
>>> > Honza
>>> >>
>>> >> thanks,
>>> >>
>>> >> David
>>> >> > Honza
Jan Hubicka - June 2, 2012, 6:11 p.m.
> Actually Dehao also plans to teach the static predictor to understand
> standard library functions more (e.g IO functions) and add more naming

How this differ from annotating the library?

There are indeed quite some possibilities to do about library calls....

One thing I always wondered about is how to tell predictor that paths containing
heavy IO functions don't need to be really opimized to death, since their execution
time is dominated by the IO...

> based heuristics such as 'error, success, failure, fatal etc).

yeah, this is also mentioned by some branch prediction papers. It is bit kludgy
in nature (i.e. it won't understand programs written in Czech language) but it
is an heuristics after all.

Honza
> 
> thanks,
> 
> David
> 
> > Honza
> >>
> >> thanks,
> >>
> >> David
> >> > Honza
Xinliang David Li - June 3, 2012, 4:40 a.m.
On Sat, Jun 2, 2012 at 11:11 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Actually Dehao also plans to teach the static predictor to understand
>> standard library functions more (e.g IO functions) and add more naming
>
> How this differ from annotating the library?

I find them more suitable to be compiler heuristic than being
function's attribute -- attribute is a much stronger assertion.

>
> There are indeed quite some possibilities to do about library calls....
>
> One thing I always wondered about is how to tell predictor that paths containing
> heavy IO functions don't need to be really opimized to death, since their execution
> time is dominated by the IO...
>

Yes -- if branch predictor does the right thing and if function
splitter is powerful enough, the IO code can be outlined and optimized
for size :)


>> based heuristics such as 'error, success, failure, fatal etc).
>
> yeah, this is also mentioned by some branch prediction papers. It is bit kludgy
> in nature (i.e. it won't understand programs written in Czech language) but it
> is an heuristics after all.
>

right.

thanks,

David

> Honza
>>
>> thanks,
>>
>> David
>>
>> > Honza
>> >>
>> >> thanks,
>> >>
>> >> David
>> >> > Honza
Dehao Chen - June 3, 2012, 1:14 p.m.
Thank you guys for the comments, I'll update the patch to :

1. generalize the flag to enable other annotations such always_inline.
2. change to use deferred option.

Thanks,
Dehao

On Sun, Jun 3, 2012 at 12:40 PM, Xinliang David Li <davidxl@google.com> wrote:
> On Sat, Jun 2, 2012 at 11:11 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>> Actually Dehao also plans to teach the static predictor to understand
>>> standard library functions more (e.g IO functions) and add more naming
>>
>> How this differ from annotating the library?
>
> I find them more suitable to be compiler heuristic than being
> function's attribute -- attribute is a much stronger assertion.
>
>>
>> There are indeed quite some possibilities to do about library calls....
>>
>> One thing I always wondered about is how to tell predictor that paths containing
>> heavy IO functions don't need to be really opimized to death, since their execution
>> time is dominated by the IO...
>>
>
> Yes -- if branch predictor does the right thing and if function
> splitter is powerful enough, the IO code can be outlined and optimized
> for size :)
>
>
>>> based heuristics such as 'error, success, failure, fatal etc).
>>
>> yeah, this is also mentioned by some branch prediction papers. It is bit kludgy
>> in nature (i.e. it won't understand programs written in Czech language) but it
>> is an heuristics after all.
>>
>
> right.
>
> thanks,
>
> David
>
>> Honza
>>>
>>> thanks,
>>>
>>> David
>>>
>>> > Honza
>>> >>
>>> >> thanks,
>>> >>
>>> >> David
>>> >> > Honza
Xinliang David Li - June 3, 2012, 4:03 p.m.
Where is the patch -- the code review link is missing (in the original post).

David

On Sun, Jun 3, 2012 at 6:14 AM, Dehao Chen <dehao@google.com> wrote:
> Thank you guys for the comments, I'll update the patch to :
>
> 1. generalize the flag to enable other annotations such always_inline.
> 2. change to use deferred option.
>
> Thanks,
> Dehao
>
> On Sun, Jun 3, 2012 at 12:40 PM, Xinliang David Li <davidxl@google.com> wrote:
>> On Sat, Jun 2, 2012 at 11:11 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>>> Actually Dehao also plans to teach the static predictor to understand
>>>> standard library functions more (e.g IO functions) and add more naming
>>>
>>> How this differ from annotating the library?
>>
>> I find them more suitable to be compiler heuristic than being
>> function's attribute -- attribute is a much stronger assertion.
>>
>>>
>>> There are indeed quite some possibilities to do about library calls....
>>>
>>> One thing I always wondered about is how to tell predictor that paths containing
>>> heavy IO functions don't need to be really opimized to death, since their execution
>>> time is dominated by the IO...
>>>
>>
>> Yes -- if branch predictor does the right thing and if function
>> splitter is powerful enough, the IO code can be outlined and optimized
>> for size :)
>>
>>
>>>> based heuristics such as 'error, success, failure, fatal etc).
>>>
>>> yeah, this is also mentioned by some branch prediction papers. It is bit kludgy
>>> in nature (i.e. it won't understand programs written in Czech language) but it
>>> is an heuristics after all.
>>>
>>
>> right.
>>
>> thanks,
>>
>> David
>>
>>> Honza
>>>>
>>>> thanks,
>>>>
>>>> David
>>>>
>>>> > Honza
>>>> >>
>>>> >> thanks,
>>>> >>
>>>> >> David
>>>> >> > Honza
Andi Kleen - June 4, 2012, 1:34 a.m.
Dehao Chen <dehao@google.com> writes:

> Hi,
>
> This patch adds 4 flags to enable user to type in a list of name
> patterns. Compiler will match the function name with the given
> patterns, and add "hot", "cold", "likely_hot", "likely_cold"
> attributes to function declaration. The static branch prediction
> checks if a basic block contains call to a annotated function, and set
> the branch probability accordingly.

I like the idea (and would have some uses for it), but I don't like the
command line options. That will lead to longer and longer command
lines. Could this be made a pragma instead?

You could still specify it from the Makefile by using -include

-Andi
Dehao Chen - June 4, 2012, 2:23 a.m.
On Mon, Jun 4, 2012 at 9:34 AM, Andi Kleen <andi@firstfloor.org> wrote:
> Dehao Chen <dehao@google.com> writes:
>
>> Hi,
>>
>> This patch adds 4 flags to enable user to type in a list of name
>> patterns. Compiler will match the function name with the given
>> patterns, and add "hot", "cold", "likely_hot", "likely_cold"
>> attributes to function declaration. The static branch prediction
>> checks if a basic block contains call to a annotated function, and set
>> the branch probability accordingly.
>
> I like the idea (and would have some uses for it), but I don't like the
> command line options. That will lead to longer and longer command
> lines. Could this be made a pragma instead?
>
> You could still specify it from the Makefile by using -include

Thanks for the suggestions.

How about we add an option (-ffunction-attribute-list=), and we can
also specify this option using "#pragma GCC optimize" in a separate
-include file?

Thanks,
Dehao

>
> -Andi
>
> --
> ak@linux.intel.com -- Speaking for myself only
Jan Hubicka - June 4, 2012, 1:24 p.m.
> On Sat, Jun 2, 2012 at 11:11 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> Actually Dehao also plans to teach the static predictor to understand
> >> standard library functions more (e.g IO functions) and add more naming
> >
> > How this differ from annotating the library?
> 
> I find them more suitable to be compiler heuristic than being
> function's attribute -- attribute is a much stronger assertion.

Why so? Special matching the function names in compiler is pretty much
the same thing as annotating them in the source, right?
> 
> >
> > There are indeed quite some possibilities to do about library calls....
> >
> > One thing I always wondered about is how to tell predictor that paths containing
> > heavy IO functions don't need to be really opimized to death, since their execution
> > time is dominated by the IO...
> >
> 
> Yes -- if branch predictor does the right thing and if function
> splitter is powerful enough, the IO code can be outlined and optimized
> for size :)

We have infrastructure for optimizing for size regions of functions, so this should
be easy. With flag_reorder_blocks_and_partition we can even "outline"
but problem with these things is that they do not really match the usual vision
of profile prediction...

Honza
> 
> 
> >> based heuristics such as 'error, success, failure, fatal etc).
> >
> > yeah, this is also mentioned by some branch prediction papers. It is bit kludgy
> > in nature (i.e. it won't understand programs written in Czech language) but it
> > is an heuristics after all.
> >
> 
> right.
> 
> thanks,
> 
> David
> 
> > Honza
> >>
> >> thanks,
> >>
> >> David
> >>
> >> > Honza
> >> >>
> >> >> thanks,
> >> >>
> >> >> David
> >> >> > Honza
Xinliang David Li - June 4, 2012, 5:11 p.m.
On Mon, Jun 4, 2012 at 6:24 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> On Sat, Jun 2, 2012 at 11:11 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >> Actually Dehao also plans to teach the static predictor to understand
>> >> standard library functions more (e.g IO functions) and add more naming
>> >
>> > How this differ from annotating the library?
>>
>> I find them more suitable to be compiler heuristic than being
>> function's attribute -- attribute is a much stronger assertion.
>
> Why so? Special matching the function names in compiler is pretty much
> the same thing as annotating them in the source, right?

Compiler can choose to do fine grained tuning based on heuristics
which can be hard for user to do/maintain using annotation. For
instance, we provide user __builtin_expect to annotate branches, but
not a more general builtin to annotate the branch with specific
probabilities -- the latter is taken care of by  the compiler.

thanks,

David

>>
>> >
>> > There are indeed quite some possibilities to do about library calls....
>> >
>> > One thing I always wondered about is how to tell predictor that paths containing
>> > heavy IO functions don't need to be really opimized to death, since their execution
>> > time is dominated by the IO...
>> >
>>
>> Yes -- if branch predictor does the right thing and if function
>> splitter is powerful enough, the IO code can be outlined and optimized
>> for size :)
>
> We have infrastructure for optimizing for size regions of functions, so this should
> be easy. With flag_reorder_blocks_and_partition we can even "outline"
> but problem with these things is that they do not really match the usual vision
> of profile prediction...
>
> Honza
>>
>>
>> >> based heuristics such as 'error, success, failure, fatal etc).
>> >
>> > yeah, this is also mentioned by some branch prediction papers. It is bit kludgy
>> > in nature (i.e. it won't understand programs written in Czech language) but it
>> > is an heuristics after all.
>> >
>>
>> right.
>>
>> thanks,
>>
>> David
>>
>> > Honza
>> >>
>> >> thanks,
>> >>
>> >> David
>> >>
>> >> > Honza
>> >> >>
>> >> >> thanks,
>> >> >>
>> >> >> David
>> >> >> > Honza

Patch

Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi	(revision 188050)
+++ gcc/doc/invoke.texi	(working copy)
@@ -362,7 +362,9 @@ 
 -fdelete-null-pointer-checks -fdse -fdevirtualize -fdse @gol
 -fearly-inlining -fipa-sra -fexpensive-optimizations -ffast-math @gol
 -ffinite-math-only -ffloat-store -fexcess-precision=@var{style} @gol
--fforward-propagate -ffp-contract=@var{style} -ffunction-sections @gol
+-fforward-propagate -ffp-contract=@var{style} @gol
+-ffunction-cold-list -ffunction-hot-list -ffunction-likely-cold-list @gol
+-ffunction-likely-hot-list -ffunction-sections @gol
 -fgcse -fgcse-after-reload -fgcse-las -fgcse-lm -fgraphite-identity @gol
 -fgcse-sm -fif-conversion -fif-conversion2 -findirect-inlining @gol
 -finline-functions -finline-functions-called-once -finline-limit=@var{n} @gol
@@ -8585,6 +8587,22 @@ 
 specify this option and you may have problems with debugging if
 you specify both this option and @option{-g}.

+@item -ffunction-cold-list
+@opindex ffunction-cold-list
+List of function name patterns that will be applied "cold" attribute.
+
+@item -ffunction-hot-list
+@opindex ffunction-hot-list
+List of function name patterns that will be applied "hot" attribute.
+
+@item -ffunction-likely-cold-list
+@opindex ffunction-likely-cold-list
+List of function name patterns that will be applied "likely_cold" attribute.
+
+@item -ffunction-likely-hot-list
+@opindex ffunction-likely-hot-list
+List of function name patterns that will be applied "likely_hot" attribute.
+
 @item -fbranch-target-load-optimize
 @opindex fbranch-target-load-optimize
 Perform branch target register load optimization before prologue / epilogue
Index: gcc/cgraph.c
===================================================================
--- gcc/cgraph.c	(revision 188050)
+++ gcc/cgraph.c	(working copy)
@@ -520,6 +520,70 @@ 
     }
 }

+typedef char *char_pointer;
+DEF_VEC_P(char_pointer);
+DEF_VEC_ALLOC_P(char_pointer,heap);
+
+/* Match FNDECL's name with PATTERNS. If matched, add HOTNESS attribute
+   to FNDECL.
+   name matches with pattern, iff one of the following conditions satisfy:
+     1. strcmp (name, pattern) != 0
+     2. pattern[len - 1] = '*' && strncmp (name, pattern, len - 1) != 0  */
+static bool
+cgraph_match_hotness_by_name (tree fndecl,
+			      VEC(char_pointer, heap) *patterns,
+			      const char *hotness)
+{
+  unsigned i;
+  char_pointer n;
+  const char *name = lang_hooks.decl_printable_name(fndecl, 0);
+
+  if (!name)
+    return false;
+
+  FOR_EACH_VEC_ELT (char_pointer, patterns, i, n)
+    {
+      int len = strlen (n);
+      if ((n[len - 1] == '*' && !strncmp (name, n, len - 1))
+          || !strcmp (name, n))
+        {
+          decl_attributes (&fndecl, tree_cons (
+              get_identifier (hotness), NULL, NULL), 0);
+          return true;
+        }
+    }
+  return false;
+}
+
+/* Add hotness attributes to FNDECL.  */
+static void
+cgraph_add_hotness_attribute (tree fndecl)
+{
+  if (lookup_attribute ("cold", DECL_ATTRIBUTES (fndecl))
+      || lookup_attribute ("hot", DECL_ATTRIBUTES (fndecl))
+      || lookup_attribute ("likely_cold", DECL_ATTRIBUTES (fndecl))
+      || lookup_attribute ("likely_hot", DECL_ATTRIBUTES (fndecl)))
+    return;
+
+  if (cgraph_match_hotness_by_name (fndecl,
+	(VEC(char_pointer, heap) *) flag_function_cold_list, "cold"))
+    return;
+
+  if (cgraph_match_hotness_by_name (fndecl,
+	(VEC(char_pointer, heap) *) flag_function_hot_list, "hot"))
+    return;
+
+  if (cgraph_match_hotness_by_name (fndecl,
+	(VEC(char_pointer, heap) *) flag_function_likely_cold_list,
+	"likely_cold"))
+    return;
+
+  if (cgraph_match_hotness_by_name (fndecl,
+	(VEC(char_pointer, heap) *) flag_function_likely_hot_list,
+	"likely_hot"))
+    return;
+}
+
 /* Return cgraph node assigned to DECL.  Create new one when needed.  */

 struct cgraph_node *
@@ -554,6 +618,7 @@ 
       node->origin->nested = node;
     }
   cgraph_add_assembler_hash_node (node);
+  cgraph_add_hotness_attribute (decl);
   return node;
 }

Index: gcc/opts.c
===================================================================
--- gcc/opts.c	(revision 188050)
+++ gcc/opts.c	(working copy)
@@ -1539,6 +1539,26 @@ 
 	(&opts->x_flag_instrument_functions_exclude_files, arg);
       break;

+    case OPT_ffunction_hot_list_:
+      add_comma_separated_to_vector
+	(&opts->x_flag_function_hot_list, arg);
+      break;
+
+    case OPT_ffunction_cold_list_:
+      add_comma_separated_to_vector
+	(&opts->x_flag_function_cold_list, arg);
+      break;
+
+    case OPT_ffunction_likely_hot_list_:
+      add_comma_separated_to_vector
+	(&opts->x_flag_function_likely_hot_list, arg);
+      break;
+
+    case OPT_ffunction_likely_cold_list_:
+      add_comma_separated_to_vector
+	(&opts->x_flag_function_likely_cold_list, arg);
+      break;
+
     case OPT_fmessage_length_:
       pp_set_line_maximum_length (dc->printer, value);
       break;
Index: gcc/predict.c
===================================================================
--- gcc/predict.c	(revision 188050)
+++ gcc/predict.c	(working copy)
@@ -2070,11 +2070,22 @@ 
 		predict_paths_leading_to (bb, PRED_NORETURN,
 					  NOT_TAKEN);
 	      decl = gimple_call_fndecl (stmt);
-	      if (decl
-		  && lookup_attribute ("cold",
-				       DECL_ATTRIBUTES (decl)))
-		predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
-					  NOT_TAKEN);
+	      if (decl)
+		{
+		  tree attr = DECL_ATTRIBUTES (decl);
+		  if (lookup_attribute ("cold", attr))
+		    predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
+					      NOT_TAKEN);
+		  else if (lookup_attribute ("hot", attr))
+		    predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
+					      TAKEN);
+		  else if (lookup_attribute ("likely_cold", attr))
+		    predict_paths_leading_to (bb, PRED_LIKELY_COLD_FUNCTION,
+					      NOT_TAKEN);
+		  else if (lookup_attribute ("likely_hot", attr))
+		    predict_paths_leading_to (bb, PRED_LIKELY_COLD_FUNCTION,
+					      TAKEN);
+		}
 	    }
 	  else if (gimple_code (stmt) == GIMPLE_PREDICT)
 	    {
Index: gcc/ChangeLog.google-4_6
===================================================================
--- gcc/ChangeLog.google-4_6	(revision 188050)
+++ gcc/ChangeLog.google-4_6	(working copy)
@@ -1,3 +1,16 @@ 
+2012-06-01  Dehao Chen  <dehao@google.com>
+
+	* gcc/cgraph.c (cgraph_match_hotness_by_name): New function.
+	(cgraph_add_hotness_attribute): New function.
+	(cgraph_node): Add hotness attribute to function decl.
+	* gcc/opts.c (common_handle_option): Handle new options.
+	* gcc/predict.c (tree_bb_level_predictions): New prediction.
+	* gcc/predict.def (PRED_LIKELY_COLD_FUNCTION): New prediction.
+	* gcc/common.opt (flag_function_hot_list): New option.
+	(flag_function_cold_list): New option.
+	(flag_function_likely_hot_list): New option.
+	(flag_function_likely_cold_list): New option.
+
 2012-05-30   Cary Coutant  <ccoutant@google.com>

 	* gcc/dwarf2out.c (index_location_lists): Don't index location
Index: gcc/predict.def
===================================================================
--- gcc/predict.def	(revision 188050)
+++ gcc/predict.def	(working copy)
@@ -76,6 +76,10 @@ 
 DEF_PREDICTOR (PRED_COLD_FUNCTION, "cold function call", PROB_VERY_LIKELY,
 	       PRED_FLAG_FIRST_MATCH)

+/* Branch to basic block containing call marked by likely_cold
function attribute.  */
+DEF_PREDICTOR (PRED_LIKELY_COLD_FUNCTION, "likely cold function call",
+	       HITRATE (75), PRED_FLAG_FIRST_MATCH)
+
 /* Loopback edge is taken.  */
 DEF_PREDICTOR (PRED_LOOP_BRANCH, "loop branch", HITRATE (86),
 	       PRED_FLAG_FIRST_MATCH)
Index: gcc/common.opt
===================================================================
--- gcc/common.opt	(revision 188050)
+++ gcc/common.opt	(working copy)
@@ -92,6 +92,20 @@ 
 Variable
 void *flag_instrument_functions_exclude_files

+; These four are VEC(char_p,heap) * that indicate function hotness.
+
+Variable
+void *flag_function_hot_list
+
+Variable
+void *flag_function_cold_list
+
+Variable
+void *flag_function_likely_hot_list
+
+Variable
+void *flag_function_likely_cold_list
+
 ; Generic structs (e.g. templates not explicitly specialized)
 ; may not have a compilation unit associated with them, and so
 ; may need to be treated differently from ordinary structs.
@@ -1242,6 +1256,22 @@ 
 Common Report Var(flag_function_sections)
 Place each function into its own section

+ffunction-hot-list=
+Common RejectNegative Joined
+-ffunction-hot-list=name,...  Predict listed functions as hot
+
+ffunction-cold-list=
+Common RejectNegative Joined
+-ffunction-cold-list=name,...  Predict listed functions as cold
+
+ffunction-likely-hot-list=
+Common RejectNegative Joined
+-ffunction-likely-hot-list=name,...  Predict listed functions as likely_hot
+
+ffunction-likely-cold-list=
+Common RejectNegative Joined
+-ffunction-likely-cold-list=name,...  Predict listed functions as likely_cold
+
 fgcda=
 Common Joined RejectNegative Var(gcov_da_name)
 Set the gcov data file name.