[PATCH] increase builtin_expert probability in loop exit test

[Rong Xu]

Attached is the patchset 2. It takes the max to two hitrates then does
the incremental.


On Fri, Oct 11, 2013 at 2:01 PM, Rong Xu <xur@google.com> wrote:
> Hi,
>
> An earlier patch (r203167) changed the default probability for
> builtin_expect to 90%.
> It does not work properly for the following case:
>    while (__builin_expect (expr, 1)) { ....}
>
> W/o builtin_expect, the exit probability is 9% while w/
> builtin_expect, the exit probability is 10%.
> It seems to be wrong as we should estimate this loop has more
> iterations than w/o the annotation.
>
> This attached patch bump the probability for this particular case.
>
> Tested with bootstrap.
>
> Thanks,
>
> -Rong
-------------- next part --------------
2013-10-11  Rong Xu  <xur@google.com>

        * predict.c (tree_predict_by_opcode): Bump the 
        estimiated probability if builtin_expect expression is
        in loop exit test.

Index: predict.c
===================================================================
--- predict.c	(revision 203463)
+++ predict.c	(working copy)
@@ -2001,11 +2001,39 @@ tree_predict_by_opcode (basic_block bb)
   if (val)
     {
       int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
+      void **preds;
+      int hitrate;
 
       gcc_assert (percent >= 0 && percent <= 100);
+      /* 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.  */
+      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;
+                }
+            }
+        }
       if (integer_zerop (val))
-        percent = 100 - percent;
-      predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
+        hitrate = REG_BR_PROB_BASE - hitrate;
+      predict_edge (then_edge, PRED_BUILTIN_EXPECT, hitrate);
     }
   /* Try "pointer heuristic."
      A comparison ptr == 0 is predicted as false.