[RFC] hot/cold attributes on labels

The motivation for this feature is to inform the compiler how
it may wish to layout blocks following an asm goto.

Since we can't annotate the asm goto with __builtin_expect,
putting some information onto the label decl itself seems a
reasonable solution.

Note that one needs to use -O2 and not -Os in order to see the
effects of this patch, since bb-reorder does nothing when
optimizing for size -- despite any explicit option enabling block
reordering.  This is probably a bug.  Of course, a size-sensitive
block reordering pass would be Even Cooler.

Comments?


r~
gcc/
	* doc/extend.texi (hot attribute): Document its use on labels.
	(cold attribute): Likewise.
	* predict.c (tree_estimate_probability_bb): Look for hot/cold
	attributes on user labels.
	* predict.def (PRED_HOT_LABEL, PRED_COLD_LABEL): New.

gcc/c-family/
	* c-common.c (handle_hot_attribute): Allow LABEL_DECLs.
	(handle_cold_attribute): Likewise.

gcc/testsuite/
	* gcc.dg/attr-hotcold-1.c: New.
	* gcc.dg/tree-ssa/attr-hotcold-2.c: New.

On Wed, Oct 20, 2010 at 02:10:07PM -0700, Richard Henderson wrote:
> The motivation for this feature is to inform the compiler how
> it may wish to layout blocks following an asm goto.
> 
> Since we can't annotate the asm goto with __builtin_expect,
> putting some information onto the label decl itself seems a
> reasonable solution.
> 
> Note that one needs to use -O2 and not -Os in order to see the
> effects of this patch, since bb-reorder does nothing when
> optimizing for size -- despite any explicit option enabling block
> reordering.  This is probably a bug.  Of course, a size-sensitive
> block reordering pass would be Even Cooler.
> 
> Comments?
> 
> 

Currently, I am seeing the 'unlikely' path moved out of line, under -02,
while using asm gotos - to the end of the function where the 'asm goto' is
used, (after the typical return path).

So this annotation would allow the unlikely/likely branches to be
grouped in hot/cold sections elsewhere?

more feedback after tyring the patch.

thanks,

-Jason

Richard Henderson <rth@redhat.com> writes:

> The motivation for this feature is to inform the compiler how
> it may wish to layout blocks following an asm goto.
>
> Since we can't annotate the asm goto with __builtin_expect,
> putting some information onto the label decl itself seems a
> reasonable solution.
>
> Note that one needs to use -O2 and not -Os in order to see the
> effects of this patch, since bb-reorder does nothing when
> optimizing for size -- despite any explicit option enabling block
> reordering.  This is probably a bug.  Of course, a size-sensitive
> block reordering pass would be Even Cooler.
>
> Comments?

I would be a bit worried about what this syntax does for syntax error
recovery, because now you can have parts of a type in 
the middle of a expression.  Without a parser generator
double checking this it's hard to know.

It would be bad to do the same mistakes as Stroustrup did 
long ago for C too :-)

It would be probably better to put some more unique syntax markers
around the attribute (maybe [] ? )

And maybe double check the result is still LL(1).

-Andi

On 10/20/2010 02:23 PM, Andi Kleen wrote:
> I would be a bit worried about what this syntax does for syntax error
> recovery, because now you can have parts of a type in 
> the middle of a expression.  Without a parser generator
> double checking this it's hard to know.

This patch does not change the parser at all.

We already accept __attribute__ on labels, though
the syntax is slightly different for C and C++.
At present the only valid attribute for labels is
unused.


r~

On 10/20/2010 2:10 PM, Richard Henderson wrote:

> The motivation for this feature is to inform the compiler how
> it may wish to layout blocks following an asm goto.

> Since we can't annotate the asm goto with __builtin_expect,
> putting some information onto the label decl itself seems a
> reasonable solution.

Why not annotate the asm as whole?  That would seem more consistent with
what we do for C code.  It also seems abstractly nicer: if the compiler
knows whether an edge is likely it can factor it what else it knows
about the target block to decide whether the block itself is hot or cold.

> The motivation for this feature is to inform the compiler how
> it may wish to layout blocks following an asm goto.
> 
> Since we can't annotate the asm goto with __builtin_expect,
> putting some information onto the label decl itself seems a
> reasonable solution.

This seems resonable to me.
I am pretty sure we used to be completely dropping prediction for
BBs with more than 2 exit edges.  Implementing the merging per Wu&Larus
paper is quite easy, I just felt that most of our existing heuristics
don't do well with switch statements anyway.
> 
> Note that one needs to use -O2 and not -Os in order to see the
> effects of this patch, since bb-reorder does nothing when
> optimizing for size -- despite any explicit option enabling block
> reordering.  This is probably a bug.  Of course, a size-sensitive
> block reordering pass would be Even Cooler.

The existing BB reordering pass used to increase code size and Pavel tried to
tune it for -Os but failed and we concluded that problably one would have to
implement special algorithm for that.  This was long time ago, perhaps with a
lot more careless tree-ssa middle end it is a win now.

Honza
> 
> Comments?
> 
> 
> r~

> gcc/
> 	* doc/extend.texi (hot attribute): Document its use on labels.
> 	(cold attribute): Likewise.
> 	* predict.c (tree_estimate_probability_bb): Look for hot/cold
> 	attributes on user labels.
> 	* predict.def (PRED_HOT_LABEL, PRED_COLD_LABEL): New.
> 
> gcc/c-family/
> 	* c-common.c (handle_hot_attribute): Allow LABEL_DECLs.
> 	(handle_cold_attribute): Likewise.
> 
> gcc/testsuite/
> 	* gcc.dg/attr-hotcold-1.c: New.
> 	* gcc.dg/tree-ssa/attr-hotcold-2.c: New.
> 
> 
> 
> diff --git a/gcc/c-family/c-common.c b/gcc/c-family/c-common.c
> index 3716b5b..21345a0 100644
> --- a/gcc/c-family/c-common.c
> +++ b/gcc/c-family/c-common.c
> @@ -5767,7 +5767,8 @@ static tree
>  handle_hot_attribute (tree *node, tree name, tree ARG_UNUSED (args),
>  		      int ARG_UNUSED (flags), bool *no_add_attrs)
>  {
> -  if (TREE_CODE (*node) == FUNCTION_DECL)
> +  if (TREE_CODE (*node) == FUNCTION_DECL
> +      || TREE_CODE (*node) == LABEL_DECL)
>      {
>        if (lookup_attribute ("cold", DECL_ATTRIBUTES (*node)) != NULL)
>  	{
> @@ -5786,6 +5787,7 @@ handle_hot_attribute (tree *node, tree name, tree ARG_UNUSED (args),
>  
>    return NULL_TREE;
>  }
> +
>  /* Handle a "cold" and attribute; arguments as in
>     struct attribute_spec.handler.  */
>  
> @@ -5793,7 +5795,8 @@ static tree
>  handle_cold_attribute (tree *node, tree name, tree ARG_UNUSED (args),
>  		       int ARG_UNUSED (flags), bool *no_add_attrs)
>  {
> -  if (TREE_CODE (*node) == FUNCTION_DECL)
> +  if (TREE_CODE (*node) == FUNCTION_DECL
> +      || TREE_CODE (*node) == LABEL_DECL)
>      {
>        if (lookup_attribute ("hot", DECL_ATTRIBUTES (*node)) != NULL)
>  	{
> diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
> index d39ab48..2cfbe9a 100644
> --- a/gcc/doc/extend.texi
> +++ b/gcc/doc/extend.texi
> @@ -3040,33 +3040,53 @@ than 2.96.
>  
>  @item hot
>  @cindex @code{hot} function attribute
> -The @code{hot} attribute is used to inform the compiler that a function is a
> -hot spot of the compiled program.  The function is optimized more aggressively
> -and on many target it is placed into special subsection of the text section so
> -all hot functions appears close together improving locality.
> +The @code{hot} attribute on a function is used to inform the compiler that
> +the function is a hot spot of the compiled program.  The function is
> +optimized more aggressively and on many target it is placed into special
> +subsection of the text section so all hot functions appears close together
> +improving locality.
>  
>  When profile feedback is available, via @option{-fprofile-use}, hot functions
>  are automatically detected and this attribute is ignored.
>  
> -The @code{hot} attribute is not implemented in GCC versions earlier
> -than 4.3.
> +The @code{hot} attribute on functions is not implemented in GCC versions
> +earlier than 4.3.
> +
> +@cindex @code{hot} label attribute
> +The @code{hot} attribute on a label is used to inform the compiler that
> +path following the label are more likely than paths that are not so
> +annotated.  This attribute is used in cases where @code{__builtin_expect}
> +cannot be used, for instance with computed goto or @code{asm goto}.
> +
> +The @code{hot} attribute on labels is not implemented in GCC versions
> +earlier than 4.6.
>  
>  @item cold
>  @cindex @code{cold} function attribute
> -The @code{cold} attribute is used to inform the compiler that a function is
> -unlikely executed.  The function is optimized for size rather than speed and on
> -many targets it is placed into special subsection of the text section so all
> -cold functions appears close together improving code locality of non-cold parts
> -of program.  The paths leading to call of cold functions within code are marked
> -as unlikely by the branch prediction mechanism. It is thus useful to mark
> -functions used to handle unlikely conditions, such as @code{perror}, as cold to
> -improve optimization of hot functions that do call marked functions in rare
> -occasions.
> -
> -When profile feedback is available, via @option{-fprofile-use}, hot functions
> +The @code{cold} attribute on functions is used to inform the compiler that
> +the function is unlikely to be executed.  The function is optimized for
> +size rather than speed and on many targets it is placed into special
> +subsection of the text section so all cold functions appears close together
> +improving code locality of non-cold parts of program.  The paths leading
> +to call of cold functions within code are marked as unlikely by the branch
> +prediction mechanism.  It is thus useful to mark functions used to handle
> +unlikely conditions, such as @code{perror}, as cold to improve optimization
> +of hot functions that do call marked functions in rare occasions.
> +
> +When profile feedback is available, via @option{-fprofile-use}, cold functions
>  are automatically detected and this attribute is ignored.
>  
> -The @code{cold} attribute is not implemented in GCC versions earlier than 4.3.
> +The @code{cold} attribute on functions is not implemented in GCC versions
> +earlier than 4.3.
> +
> +@cindex @code{cold} label attribute
> +The @code{cold} attribute on labels is used to inform the compiler that
> +the path following the label is unlikely to be executed.  This attribute
> +is used in cases where @code{__builtin_expect} cannot be used, for instance
> +with computed goto or @code{asm goto}.
> +
> +The @code{cold} attribute on labels is not implemented in GCC versions
> +earlier than 4.6.
>  
>  @item regparm (@var{number})
>  @cindex @code{regparm} attribute
> diff --git a/gcc/predict.c b/gcc/predict.c
> index eb91b87..e03d1dd 100644
> --- a/gcc/predict.c
> +++ b/gcc/predict.c
> @@ -1627,6 +1627,29 @@ tree_estimate_probability_bb (basic_block bb)
>  
>    FOR_EACH_EDGE (e, ei, bb->succs)
>      {
> +      /* Predict edges to user labels with attributes.  */
> +      if (e->dest != EXIT_BLOCK_PTR)
> +	{
> +	  gimple_stmt_iterator gi;
> +	  for (gi = gsi_start_bb (e->dest); !gsi_end_p (gi); gsi_next (&gi))
> +	    {
> +	      gimple stmt = gsi_stmt (gi);
> +	      tree decl;
> +
> +	      if (gimple_code (stmt) != GIMPLE_LABEL)
> +		break;
> +	      decl = gimple_label_label (stmt);
> +	      if (DECL_ARTIFICIAL (decl))
> +		continue;
> +
> +	      /* Finally, we have a user-defined label.  */
> +	      if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl)))
> +		predict_edge_def (e, PRED_COLD_LABEL, NOT_TAKEN);
> +	      else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl)))
> +		predict_edge_def (e, PRED_HOT_LABEL, TAKEN);
> +	    }
> +	}
> +
>        /* Predict early returns to be probable, as we've already taken
>  	 care for error returns and other cases are often used for
>  	 fast paths through function.
> diff --git a/gcc/predict.def b/gcc/predict.def
> index 4b3e87a..73a22eb 100644
> --- a/gcc/predict.def
> +++ b/gcc/predict.def
> @@ -116,3 +116,10 @@ DEF_PREDICTOR (PRED_NULL_RETURN, "null return", HITRATE (90), 0)
>  
>  /* Branches to a mudflap bounds check are extremely unlikely.  */
>  DEF_PREDICTOR (PRED_MUDFLAP, "mudflap check", PROB_VERY_LIKELY, 0)
> +
> +/* Branches to hot labels are likely.  */
> +DEF_PREDICTOR (PRED_HOT_LABEL, "hot label", HITRATE (85), 0)
> +
> +/* Branches to cold labels are extremely unlikely.  */
> +DEF_PREDICTOR (PRED_COLD_LABEL, "cold label", PROB_VERY_LIKELY,
> +	       PRED_FLAG_FIRST_MATCH)
> diff --git a/gcc/testsuite/gcc.dg/attr-hotcold-1.c b/gcc/testsuite/gcc.dg/attr-hotcold-1.c
> new file mode 100644
> index 0000000..f63a95c
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/attr-hotcold-1.c
> @@ -0,0 +1,8 @@
> +void f(void)
> +{
> +  goto A;
> + A: __attribute__((cold))
> +  goto B;
> + B: __attribute__((hot))
> +  return;
> +}
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c b/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
> new file mode 100644
> index 0000000..ae6d383
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/attr-hotcold-2.c
> @@ -0,0 +1,28 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-profile-details" } */
> +
> +void g(void);
> +void h(void);
> +void f(int x, int y)
> +{
> +  if (x) goto A;
> +  if (y) goto B;
> +  return;
> +
> + A: __attribute__((cold))
> +  g();
> +  return;
> +
> + B: __attribute__((hot))
> +  h();
> +  return;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "BLOCK 4 freq:1\[^0-9\]" 1 "profile" } } */
> +
> +/* Note: we're attempting to match some number > 6000, i.e. > 60%.
> +   The exact number ought to be tweekable without having to juggle
> +   the testcase around too much.  */
> +/* { dg-final { scan-tree-dump-times "BLOCK 5 freq:\[6-9\]\[0-9\]\[0-9\]\[0-9\]" 1 "profile" } } */
> +
> +/* { dg-final { cleanup-tree-dump "profile" } } */

On 10/20/2010 06:04 PM, Mark Mitchell wrote:
> On 10/20/2010 2:10 PM, Richard Henderson wrote:
>
>> The motivation for this feature is to inform the compiler how
>> it may wish to layout blocks following an asm goto.
>
>> Since we can't annotate the asm goto with __builtin_expect,
>> putting some information onto the label decl itself seems a
>> reasonable solution.
>
> Why not annotate the asm as whole?  That would seem more consistent with
> what we do for C code.  It also seems abstractly nicer: if the compiler
> knows whether an edge is likely it can factor it what else it knows
> about the target block to decide whether the block itself is hot or cold.
>

Not speaking for RTH, here is my take on it:

Each exit edge, including the fall through, from the asm goto would have 
to be somehow annotated.  While I fully agree that it would be nicer to 
put this in the asm goto itself, a la __builtin_expect(), a good syntax 
for doing this might be difficult to achieve.  Tagging the target labels 
involves no change to the parsers.  From the point of view of minimizing 
the amount of implementation effort required, I think the patch has merits.

David Daney

On 10/21/2010 1:57 PM, David Daney wrote:

> Each exit edge, including the fall through, from the asm goto would have
> to be somehow annotated.  While I fully agree that it would be nicer to
> put this in the asm goto itself, a la __builtin_expect(), a good syntax
> for doing this might be difficult to achieve.  Tagging the target labels
> involves no change to the parsers.  From the point of view of minimizing
> the amount of implementation effort required, I think the patch has merits.

No question: RTH's patch is simpler.  I think first we should decide if
something more complex is better, and if it is, whether it's better
enough.  I'm not prejudging the outcome of that discussion, but it's
worth having in that language extensions are like marriage: extend in
haste, repent at leisure. :-)

I'm sure we could invent a syntax, whether something that went in the
asm code itself (which would then be found by GCC), or as arguments to
the asm (e.g., a list of labels and probabilities that once you enter
the asm you exit to that label).

On 10/21/2010 02:03 PM, Mark Mitchell wrote:
> On 10/21/2010 1:57 PM, David Daney wrote:
>
>> Each exit edge, including the fall through, from the asm goto would have
>> to be somehow annotated.  While I fully agree that it would be nicer to
>> put this in the asm goto itself, a la __builtin_expect(), a good syntax
>> for doing this might be difficult to achieve.  Tagging the target labels
>> involves no change to the parsers.  From the point of view of minimizing
>> the amount of implementation effort required, I think the patch has merits.
>
> No question: RTH's patch is simpler.  I think first we should decide if
> something more complex is better, and if it is, whether it's better
> enough.  I'm not prejudging the outcome of that discussion, but it's
> worth having in that language extensions are like marriage: extend in
> haste, repent at leisure. :-)
>
> I'm sure we could invent a syntax, whether something that went in the
> asm code itself (which would then be found by GCC), or as arguments to
> the asm (e.g., a list of labels and probabilities that once you enter
> the asm you exit to that label).
>

FWIW, when I first looked at this a couple of weeks ago, my conclusion 
was that we do as you suggest.

Each label in the asm goto label list could have an optional 
__attribute__((likely)) or __attribute__((unlikely)), the asm goto as a 
whole could also have the same attributes, which would be applied to the 
fall through edge.

I don't know what the implications of adding an attribute to a statement 
would be for the parsers and front ends.

In any event I am happy that RTH is looking at this, and will defer you 
guys as to which is the proper path forward.

Thanks,
David Daney