Patchwork [google,gcc-4_8] alternate hirate for builtin_expert

login
register
mail settings
Submitter Rong Xu
Date Sept. 26, 2013, 10:17 p.m.
Message ID <CAF1bQ=RnCQGRrdUxV0Mpj9wAiB=fUy+fzouGOf0Rj_YWt2TMoA@mail.gmail.com>
Download mbox | patch
Permalink /patch/278285/
State New
Headers show

Comments

Rong Xu - Sept. 26, 2013, 10:17 p.m.
Hi,

Current default probably for builtin_expect is 0.9996.
This makes the freq of unlikely bb very low (4), which
suppresses the inlining of any calls within those bb.

We used FDO data to measure the branch probably for
the branch annotated with builtin_expert.
                                                         For google
internal benchmarks, the weight average
(the profile count value as the weight) is 0.9081.

Linux kernel is another program that is heavily annotated
with builtin-expert. We measured its weight average as 0.8717,
                                              using google search as
the workload.


    This patch sets the alternate hirate probability for
builtin_expert
to 90%. With the alternate hirate, we measured performance
                                              improvement for google
benchmarks and Linux kernel.


                              -Rong
2013-09-26  Rong Xu  <xur@google.com>

	* params.def (DEFPARAM): New.
	* params.def: New.
	* predict.c (tree_predict_by_opcode): Alternate 
        probablity hirate for builtin_expect.
Jan Hubicka - Sept. 26, 2013, 10:27 p.m.
> Hi,
> 
> Current default probably for builtin_expect is 0.9996.
> This makes the freq of unlikely bb very low (4), which
> suppresses the inlining of any calls within those bb.
> 
> We used FDO data to measure the branch probably for
> the branch annotated with builtin_expert.
>                                                          For google
> internal benchmarks, the weight average
> (the profile count value as the weight) is 0.9081.
> 
> Linux kernel is another program that is heavily annotated
> with builtin-expert. We measured its weight average as 0.8717,
>                                               using google search as
> the workload.

This is interesting.  I was always unsure if programmers use builtin_expect
more often to mark an impossible paths (as those leading to crash) or just
unlikely paths.  Your data seems to suggest the second.

We probably also ought to get analyze_brprob working again. It was always
useful to get such a data.
> 
> 
>     This patch sets the alternate hirate probability for
> builtin_expert
> to 90%. With the alternate hirate, we measured performance
>                                               improvement for google
> benchmarks and Linux kernel.
> 
> 
>                               -Rong
> 2013-09-26  Rong Xu  <xur@google.com>
> 
> 	* params.def (DEFPARAM): New.
> 	* params.def: New.
> 	* predict.c (tree_predict_by_opcode): Alternate 
>         probablity hirate for builtin_expect.

This also seems resonable for mainline.  Please add a comment
to the parameter explaining how the value was determined.
Please also add invoke.texi documentation.

For patches that seems resonable for mainline in FDO/IPA area,
i would apprechiate if you just added me to CC, so I do not lose
track of them.
Honza
Xinliang David Li - Sept. 26, 2013, 10:44 p.m.
This patch improves linux kernel performance with a large workload, so
it is good to first submit this to trunk and backport it.

thanks,

David

On Thu, Sep 26, 2013 at 3:27 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Hi,
>>
>> Current default probably for builtin_expect is 0.9996.
>> This makes the freq of unlikely bb very low (4), which
>> suppresses the inlining of any calls within those bb.
>>
>> We used FDO data to measure the branch probably for
>> the branch annotated with builtin_expert.
>>                                                          For google
>> internal benchmarks, the weight average
>> (the profile count value as the weight) is 0.9081.
>>
>> Linux kernel is another program that is heavily annotated
>> with builtin-expert. We measured its weight average as 0.8717,
>>                                               using google search as
>> the workload.
>
> This is interesting.  I was always unsure if programmers use builtin_expect
> more often to mark an impossible paths (as those leading to crash) or just
> unlikely paths.  Your data seems to suggest the second.
>
> We probably also ought to get analyze_brprob working again. It was always
> useful to get such a data.
>>
>>
>>     This patch sets the alternate hirate probability for
>> builtin_expert
>> to 90%. With the alternate hirate, we measured performance
>>                                               improvement for google
>> benchmarks and Linux kernel.
>>
>>
>>                               -Rong
>> 2013-09-26  Rong Xu  <xur@google.com>
>>
>>       * params.def (DEFPARAM): New.
>>       * params.def: New.
>>       * predict.c (tree_predict_by_opcode): Alternate
>>         probablity hirate for builtin_expect.
>
> This also seems resonable for mainline.  Please add a comment
> to the parameter explaining how the value was determined.
> Please also add invoke.texi documentation.
>
> For patches that seems resonable for mainline in FDO/IPA area,
> i would apprechiate if you just added me to CC, so I do not lose
> track of them.
> Honza
Xinliang David Li - Sept. 26, 2013, 10:52 p.m.
it might worth extend __builtin_expect to take more parameters:
1) argument to specify actual probability: __builtin_expect (x, 10, 0.6)
2) a more general way of doing this is to allow specifying multiple
values, and the probability is determined by # of occurances:
__builtin_expect (x, 10, 10, 20) --> tells compiler x is expected to
be 10 66% of the time, and 33% of time with value twenty.
3) a special value can be reserved to indicate if the branch is
predictable or not.

David

On Thu, Sep 26, 2013 at 3:27 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Hi,
>>
>> Current default probably for builtin_expect is 0.9996.
>> This makes the freq of unlikely bb very low (4), which
>> suppresses the inlining of any calls within those bb.
>>
>> We used FDO data to measure the branch probably for
>> the branch annotated with builtin_expert.
>>                                                          For google
>> internal benchmarks, the weight average
>> (the profile count value as the weight) is 0.9081.
>>
>> Linux kernel is another program that is heavily annotated
>> with builtin-expert. We measured its weight average as 0.8717,
>>                                               using google search as
>> the workload.
>
> This is interesting.  I was always unsure if programmers use builtin_expect
> more often to mark an impossible paths (as those leading to crash) or just
> unlikely paths.  Your data seems to suggest the second.
>
> We probably also ought to get analyze_brprob working again. It was always
> useful to get such a data.
>>
>>
>>     This patch sets the alternate hirate probability for
>> builtin_expert
>> to 90%. With the alternate hirate, we measured performance
>>                                               improvement for google
>> benchmarks and Linux kernel.
>>
>>
>>                               -Rong
>> 2013-09-26  Rong Xu  <xur@google.com>
>>
>>       * params.def (DEFPARAM): New.
>>       * params.def: New.
>>       * predict.c (tree_predict_by_opcode): Alternate
>>         probablity hirate for builtin_expect.
>
> This also seems resonable for mainline.  Please add a comment
> to the parameter explaining how the value was determined.
> Please also add invoke.texi documentation.
>
> For patches that seems resonable for mainline in FDO/IPA area,
> i would apprechiate if you just added me to CC, so I do not lose
> track of them.
> Honza
Rong Xu - Sept. 27, 2013, 8:42 p.m.
On Thu, Sep 26, 2013 at 3:27 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Hi,
>>
>> Current default probably for builtin_expect is 0.9996.
>> This makes the freq of unlikely bb very low (4), which
>> suppresses the inlining of any calls within those bb.
>>
>> We used FDO data to measure the branch probably for
>> the branch annotated with builtin_expert.
>>                                                          For google
>> internal benchmarks, the weight average
>> (the profile count value as the weight) is 0.9081.
>>
>> Linux kernel is another program that is heavily annotated
>> with builtin-expert. We measured its weight average as 0.8717,
>>                                               using google search as
>> the workload.
>
> This is interesting.  I was always unsure if programmers use builtin_expect
> more often to mark an impossible paths (as those leading to crash) or just
> unlikely paths.  Your data seems to suggest the second.
>

I don't find an official guideline on how this should be used. Maybe
some documentation
in gcc user-guide helps.

> We probably also ought to get analyze_brprob working again. It was always
> useful to get such a data.
>>
>>
>>     This patch sets the alternate hirate probability for
>> builtin_expert
>> to 90%. With the alternate hirate, we measured performance
>>                                               improvement for google
>> benchmarks and Linux kernel.
>>
>>
>>                               -Rong
>> 2013-09-26  Rong Xu  <xur@google.com>
>>
>>       * params.def (DEFPARAM): New.
>>       * params.def: New.
>>       * predict.c (tree_predict_by_opcode): Alternate
>>         probablity hirate for builtin_expect.
>
> This also seems resonable for mainline.  Please add a comment
> to the parameter explaining how the value was determined.
> Please also add invoke.texi documentation.
>

Will do.

> For patches that seems resonable for mainline in FDO/IPA area,
> i would apprechiate if you just added me to CC, so I do not lose
> track of them.

Will do.

> Honza

Patch

Index: params.def
===================================================================
--- params.def	(revision 202638)
+++ params.def	(working copy)
@@ -483,6 +483,10 @@  DEFPARAM(TRACER_MIN_BRANCH_PROBABILITY,
 	 "tracer-min-branch-probability",
 	 "Stop forward growth if the probability of best edge is less than this threshold (in percent). Used when profile feedback is not available",
 	 50, 0, 100)
+DEFPARAM(BUILTIN_EXPECT_PROBABILITY_RELAXED,
+	 "builtin-expect-probability-relaxed",
+	 "Set the estimated probability for builtin expect. By default using PROB_VERY_LIKELY, while value of 1 using HIRATE(90) probability.",
+	 0, 0, 1)
 
 /* The maximum number of incoming edges to consider for crossjumping.  */
 DEFPARAM(PARAM_MAX_CROSSJUMP_EDGES,
Index: params.def
===================================================================
--- params.def	(revision 202638)
+++ params.def	(working copy)
@@ -483,6 +483,10 @@  DEFPARAM(TRACER_MIN_BRANCH_PROBABILITY,
 	 "tracer-min-branch-probability",
 	 "Stop forward growth if the probability of best edge is less than this threshold (in percent). Used when profile feedback is not available",
 	 50, 0, 100)
+DEFPARAM(BUILTIN_EXPECT_PROBABILITY_RELAXED,
+	 "builtin-expect-probability-relaxed",
+	 "Set the estimated probability for builtin expect. By default using PROB_VERY_LIKELY, while value of 1 using HIRATE(90) probability.",
+	 0, 0, 1)
 
 /* The maximum number of incoming edges to consider for crossjumping.  */
 DEFPARAM(PARAM_MAX_CROSSJUMP_EDGES,
Index: predict.c
===================================================================
--- predict.c	(revision 202638)
+++ predict.c	(working copy)
@@ -1950,10 +1950,17 @@  tree_predict_by_opcode (basic_block bb)
   BITMAP_FREE (visited);
   if (val)
     {
+      enum br_predictor predictor;
+
+      if (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY_RELAXED) == 0)
+        predictor = PRED_BUILTIN_EXPECT;
+      else
+        predictor = PRED_BUILTIN_EXPECT_RELAXED;
+
       if (integer_zerop (val))
-	predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
+	predict_edge_def (then_edge, predictor, NOT_TAKEN);
       else
-	predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
+	predict_edge_def (then_edge, predictor, TAKEN);
       return;
     }
   /* Try "pointer heuristic."