Patchwork [google,gcc-4_8] increase builtin_expect probability in loop exit test

login
register
mail settings
Submitter Rong Xu
Date Oct. 11, 2013, 10:17 p.m.
Message ID <CAF1bQ=SiYqqca8rdmgi-r=O7=SrLuRuSqCRJmnbpD4ynBc9VAA@mail.gmail.com>
Download mbox | patch
Permalink /patch/282945/
State New
Headers show

Comments

Rong Xu - Oct. 11, 2013, 10:17 p.m.
here is the new patch. Note that the hitrate won't change by this
patch for the case of
  while (__builtin_expect (exp, 0))


On Fri, Oct 11, 2013 at 2:45 PM, Rong Xu <xur@google.com> wrote:
> ok. that makes sense.
>
>
> On Fri, Oct 11, 2013 at 2:41 PM, Xinliang David Li <davidxl@google.com> wrote:
>> Should it be max + some_delta then?
>>
>> David
>>
>> On Fri, Oct 11, 2013 at 2:32 PM, Rong Xu <xur@google.com> wrote:
>>> I want to differentiate the cases w/o and w/ builtin.
>>> If I take the max, they will be the same (91%).
>>>
>>> -Rong
>>>
>>> On Fri, Oct 11, 2013 at 2:26 PM, Xinliang David Li <davidxl@google.com> wrote:
>>>> Why this 'percent += 4'  instead of taking the max?
>>>>
>>>> David
>>>>
>>>> On Fri, Oct 11, 2013 at 2:10 PM, Rong Xu <xur@google.com> wrote:
>>>>> The trunk version of this patch is submitted for review.
>>>>>
>>>>> David: can we have this patch for google/gcc-4_8 branch first?
>>>>> It tested with regression and google internal benchmarks.
>>>>>
>>>>> Thanks,
>>>>>
>>>>> -Rong
Xinliang David Li - Oct. 11, 2013, 10:35 p.m.
ok for google branch.

David

On Fri, Oct 11, 2013 at 3:17 PM, Rong Xu <xur@google.com> wrote:
> here is the new patch. Note that the hitrate won't change by this
> patch for the case of
>   while (__builtin_expect (exp, 0))
>
> Index: predict.c
> ===================================================================
> --- predict.c   (revision 203462)
> +++ predict.c   (working copy)
> @@ -1951,11 +1951,42 @@ tree_predict_by_opcode (basic_block bb)
>    if (val)
>      {
>        int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
> +      int hitrate;
>
>        gcc_assert (percent >= 0 && percent <= 100);
>        if (integer_zerop (val))
> -        percent = 100 - percent;
> -      predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
> +        hitrate = HITRATE (100 - percent);
> +      else
> +        {
> +          /* This handles the cases like
> +               while (__builtin_expect (exp, 1)) { ... }
> +             W/o builtin_expect, the default HITRATE is 91%.
> +             It does not make sense to estimate a lower probability of 90%
> +             (current default for builtin_expect) with the annotation.
> +             So here, we bump the probability by a small amount.  */
> +          void **preds = pointer_map_contains (bb_predictions, bb);
> +
> +          hitrate = HITRATE (percent);
> +          if (preds)
> +            {
> +              struct edge_prediction *pred;
> +              int exit_hitrate = predictor_info [(int) PRED_LOOP_EXIT].hitrate;
> +
> +              for (pred = (struct edge_prediction *) *preds; pred;
> +                   pred = pred->ep_next)
> +                {
> +                  if (pred->ep_predictor == PRED_LOOP_EXIT
> +                      && exit_hitrate > hitrate)
> +                    {
> +                      hitrate = exit_hitrate + HITRATE (4);
> +                      if (hitrate > REG_BR_PROB_BASE)
> +                        hitrate = REG_BR_PROB_BASE;
> +                      break;
> +                    }
> +                }
> +            }
> +        }
> +      predict_edge (then_edge, PRED_BUILTIN_EXPECT, hitrate);
>      }
>    /* Try "pointer heuristic."
>       A comparison ptr == 0 is predicted as false.
>
> On Fri, Oct 11, 2013 at 2:45 PM, Rong Xu <xur@google.com> wrote:
>> ok. that makes sense.
>>
>>
>> On Fri, Oct 11, 2013 at 2:41 PM, Xinliang David Li <davidxl@google.com> wrote:
>>> Should it be max + some_delta then?
>>>
>>> David
>>>
>>> On Fri, Oct 11, 2013 at 2:32 PM, Rong Xu <xur@google.com> wrote:
>>>> I want to differentiate the cases w/o and w/ builtin.
>>>> If I take the max, they will be the same (91%).
>>>>
>>>> -Rong
>>>>
>>>> On Fri, Oct 11, 2013 at 2:26 PM, Xinliang David Li <davidxl@google.com> wrote:
>>>>> Why this 'percent += 4'  instead of taking the max?
>>>>>
>>>>> David
>>>>>
>>>>> On Fri, Oct 11, 2013 at 2:10 PM, Rong Xu <xur@google.com> wrote:
>>>>>> The trunk version of this patch is submitted for review.
>>>>>>
>>>>>> David: can we have this patch for google/gcc-4_8 branch first?
>>>>>> It tested with regression and google internal benchmarks.
>>>>>>
>>>>>> Thanks,
>>>>>>
>>>>>> -Rong

Patch

Index: predict.c
===================================================================
--- predict.c   (revision 203462)
+++ predict.c   (working copy)
@@ -1951,11 +1951,42 @@  tree_predict_by_opcode (basic_block bb)
   if (val)
     {
       int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
+      int hitrate;

       gcc_assert (percent >= 0 && percent <= 100);
       if (integer_zerop (val))
-        percent = 100 - percent;
-      predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
+        hitrate = HITRATE (100 - percent);
+      else
+        {
+          /* This handles the cases like
+               while (__builtin_expect (exp, 1)) { ... }
+             W/o builtin_expect, the default HITRATE is 91%.
+             It does not make sense to estimate a lower probability of 90%
+             (current default for builtin_expect) with the annotation.
+             So here, we bump the probability by a small amount.  */
+          void **preds = pointer_map_contains (bb_predictions, bb);
+
+          hitrate = HITRATE (percent);
+          if (preds)
+            {
+              struct edge_prediction *pred;
+              int exit_hitrate = predictor_info [(int) PRED_LOOP_EXIT].hitrate;
+
+              for (pred = (struct edge_prediction *) *preds; pred;
+                   pred = pred->ep_next)
+                {
+                  if (pred->ep_predictor == PRED_LOOP_EXIT
+                      && exit_hitrate > hitrate)
+                    {
+                      hitrate = exit_hitrate + HITRATE (4);
+                      if (hitrate > REG_BR_PROB_BASE)
+                        hitrate = REG_BR_PROB_BASE;
+                      break;
+                    }
+                }
+            }
+        }
+      predict_edge (then_edge, PRED_BUILTIN_EXPECT, hitrate);
     }
   /* Try "pointer heuristic."
      A comparison ptr == 0 is predicted as false.