diff mbox

[google] Refine static branch prediction (iv-compare heuristic)

Message ID CAO2gOZXS1-cpEc-8cH8c==5thZcDUH5YxVTadA+SYUP6hEHXuw@mail.gmail.com
State New
Headers show

Commit Message

Dehao Chen March 29, 2012, 2:55 a.m. UTC 
Thanks, attached is the updated patch.

Dehao


On Thu, Mar 29, 2012 at 8:06 AM, Xinliang David Li <davidxl@google.com> wrote:
> Can the test case be improved so that expected prediction results is
> checked (with the help of more dumping such as blah blah is predicted
> to be taken/not taken with probability xyz) ?
>
> Also the more test cases need to be added to cover more cases >base, >
> base +1, >=base +2, < base+1, <=base+1 etc -- even though expression
> reassociation will normalize them ...
>
> Thanks,
>
> David
>
> On Wed, Mar 28, 2012 at 4:54 PM, Dehao Chen <dehao@google.com> wrote:
>> Hi,
>>
>> This patch handles the comparison of iv against the loop iv initial
>> value. Previously, we only handle the comparison of iv against its
>> bound.
>>
>> Bootstrapped and passed all regression tests.
>>
>> Ok for google branches?
>>
>> Thanks,
>> Dehao
>>
>> 2012-03-29  Dehao Chen  <dehao@google.com>
>>
>>        * predict.c (predict_iv_comparison): Add the comparison of induction
>>        variable against its initial value.
>>
>> 2012-03-29  Dehao Chen  <dehao@google.com>
>>
>>        * gcc.dg/predict-5.c: Check if LOOP_IV_COMPARE static predict
>>        heuristic is working properly.
>>
>> Index: gcc/testsuite/gcc.dg/predict-5.c
>> ===================================================================
>> --- gcc/testsuite/gcc.dg/predict-5.c    (revision 0)
>> +++ gcc/testsuite/gcc.dg/predict-5.c    (revision 0)
>> @@ -0,0 +1,21 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
>> +
>> +extern int global;
>> +
>> +int bar(int);
>> +
>> +void foo (int base, int bound)
>> +{
>> +  int i, ret = 0;
>> +  for (i = base; i <= bound; i++)
>> +    {
>> +      if (i > base + 2)
>> +       global += bar (i);
>> +      else
>> +        global += bar (i + 1);
>> +    }
>> +}
>> +
>> +/* { dg-final { scan-tree-dump "loop iv compare heuristics"
>> "profile_estimate"} } */
>> +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
>> Index: gcc/predict.c
>> ===================================================================
>> --- gcc/predict.c       (revision 185903)
>> +++ gcc/predict.c       (working copy)
>> @@ -1185,8 +1185,7 @@
>>       return;
>>     }
>>
>> -  if (!expr_coherent_p (loop_bound_var, compare_var)
>> -      || loop_iv_base_var != compare_base)
>> +  if (loop_iv_base_var != compare_base)
>>     return;
>>
>>   /* If loop bound, base and compare bound are all constents, we can
>> @@ -1230,34 +1229,52 @@
>>       return;
>>     }
>>
>> -  if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
>> -      && (compare_code == LT_EXPR || compare_code == LE_EXPR))
>> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>> -  else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
>> -          && (compare_code == GT_EXPR || compare_code == GE_EXPR))
>> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>> -  else if (loop_bound_code == NE_EXPR)
>> -    {
>> -      /* If the loop backedge condition is "(i != bound)", we do
>> -        the comparison based on the step of IV:
>> -          * step < 0 : backedge condition is like (i > bound)
>> -          * step > 0 : backedge condition is like (i < bound)  */
>> -      gcc_assert (loop_bound_step != 0);
>> +  if (expr_coherent_p (loop_bound_var, compare_var))
>> +    {
>> +      if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
>> +         && (compare_code == LT_EXPR || compare_code == LE_EXPR))
>> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>> +      else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
>> +              && (compare_code == GT_EXPR || compare_code == GE_EXPR))
>> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>> +      else if (loop_bound_code == NE_EXPR)
>> +       {
>> +         /* If the loop backedge condition is "(i != bound)", we do
>> +            the comparison based on the step of IV:
>> +            * step < 0 : backedge condition is like (i > bound)
>> +            * step > 0 : backedge condition is like (i < bound)  */
>> +         gcc_assert (loop_bound_step != 0);
>> +         if (loop_bound_step > 0
>> +             && (compare_code == LT_EXPR
>> +                 || compare_code == LE_EXPR))
>> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>> +         else if (loop_bound_step < 0
>> +                  && (compare_code == GT_EXPR
>> +                      || compare_code == GE_EXPR))
>> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>> +         else
>> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
>> +       }
>> +      else
>> +       /* The branch is predicted not-taken if loop_bound_code is
>> +          opposite with compare_code.  */
>> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
>> +    }
>> +  else if (expr_coherent_p (loop_iv_base_var, compare_var))
>> +    {
>> +      /* For cases like:
>> +          for (i = s; i < h; i++)
>> +            if (i > s + 2) ....
>> +        The branch should be predicted taken.  */
>>       if (loop_bound_step > 0
>> -         && (compare_code == LT_EXPR
>> -             || compare_code == LE_EXPR))
>> +         && (compare_code == GT_EXPR || compare_code == GE_EXPR))
>>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>>       else if (loop_bound_step < 0
>> -              && (compare_code == GT_EXPR
>> -                  || compare_code == GE_EXPR))
>> +              && (compare_code == LT_EXPR || compare_code == LE_EXPR))
>>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>>       else
>>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
>>     }
>> -  else
>> -    /* The branch is predicted not-taken if loop_bound_code is
>> -       opposite with compare_code.  */
>> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
>>  }
>>
>>  /* Predict edge probabilities by exploiting loop structure.  */

Comments

Xinliang David Li March 29, 2012, 3 a.m. UTC | #1 
Ok for google branches.

thanks,

David

On Wed, Mar 28, 2012 at 7:55 PM, Dehao Chen <dehao@google.com> wrote:
> Thanks, attached is the updated patch.
>
> Dehao
>
> Index: gcc/testsuite/gcc.dg/predict-3.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-3.c    (revision 185903)
> +++ gcc/testsuite/gcc.dg/predict-3.c    (working copy)
> @@ -10,10 +10,16 @@
>   int i, ret = 0;
>   for (i = 0; i <= bound; i++)
>     {
> +      if (i < bound - 2)
> +       global += bar (i);
> +      if (i <= bound)
> +       global += bar (i);
> +      if (i + 1 < bound)
> +       global += bar (i);
>       if (i != bound)
>        global += bar (i);
>     }
>  }
>
> -/* { dg-final { scan-tree-dump "loop iv compare heuristics"
> "profile_estimate"} } */
> +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics:
> 100.0%" 4 "profile_estimate"} } */
>  /* { dg-final { cleanup-tree-dump "profile_estimate" } } */
> Index: gcc/testsuite/gcc.dg/predict-4.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-4.c    (revision 185903)
> +++ gcc/testsuite/gcc.dg/predict-4.c    (working copy)
> @@ -15,5 +15,5 @@
>     }
>  }
>
> -/* { dg-final { scan-tree-dump "loop iv compare heuristics"
> "profile_estimate"} } */
> +/* { dg-final { scan-tree-dump "loop iv compare heuristics: 50.0%"
> "profile_estimate"} } */
>  /* { dg-final { cleanup-tree-dump "profile_estimate" } } */
> Index: gcc/testsuite/gcc.dg/predict-1.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-1.c    (revision 185903)
> +++ gcc/testsuite/gcc.dg/predict-1.c    (working copy)
> @@ -10,10 +10,18 @@
>   int i, ret = 0;
>   for (i = 0; i < bound; i++)
>     {
> +      if (i > bound)
> +       global += bar (i);
> +      if (i >= bound + 2)
> +       global += bar (i);
>       if (i > bound - 2)
>        global += bar (i);
> +      if (i + 2 > bound)
> +       global += bar (i);
> +      if (i == 10)
> +       global += bar (i);
>     }
>  }
>
> -/* { dg-final { scan-tree-dump "loop iv compare heuristics"
> "profile_estimate"} } */
> +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics:
> 0.0%" 5 "profile_estimate"} } */
>  /* { dg-final { cleanup-tree-dump "profile_estimate" } } */
> Index: gcc/testsuite/gcc.dg/predict-5.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-5.c    (revision 0)
> +++ gcc/testsuite/gcc.dg/predict-5.c    (revision 0)
> @@ -0,0 +1,25 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
> +
> +extern int global;
> +
> +int bar (int);
> +
> +void foo (int base, int bound)
> +{
> +  int i, ret = 0;
> +  for (i = base; i <= bound; i++)
> +    {
> +      if (i > base)
> +       global += bar (i);
> +      if (i > base + 1)
> +       global += bar (i);
> +      if (i >= base + 3)
> +       global += bar (i);
> +      if (i - 2 >= base)
> +       global += bar (i);
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics:
> 100.0%" 4 "profile_estimate"} } */
> +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
> Index: gcc/testsuite/gcc.dg/predict-2.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-2.c    (revision 185903)
> +++ gcc/testsuite/gcc.dg/predict-2.c    (working copy)
> @@ -5,12 +5,20 @@
>
>  int bar(int);
>
> -void foo (int bound)
> +void foo (int base, int bound)
>  {
>   int i, ret = 0;
> -  for (i = 0; i < bound; i++)
> +  for (i = base; i < bound; i++)
>     {
> -      if (i > bound * bound )
> +      if (i > bound * bound)
> +       global += bar (i);
> +      if (i > bound + 10)
> +       global += bar (i);
> +      if (i <= bound + 10)
> +       global += bar (i);
> +      if (i > base + 10)
> +       global += bar (i);
> +      if (i < base - 10)
>        global += bar (i);
>     }
>  }
> Index: gcc/testsuite/gcc.dg/predict-6.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/predict-6.c    (revision 0)
> +++ gcc/testsuite/gcc.dg/predict-6.c    (revision 0)
> @@ -0,0 +1,25 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
> +
> +extern int global;
> +
> +int bar (int);
> +
> +void foo (int base, int bound)
> +{
> +  int i, ret = 0;
> +  for (i = base; i <= bound; i++)
> +    {
> +      if (i < base)
> +       global += bar (i);
> +      if (i < base + 1)
> +       global += bar (i);
> +      if (i <= base + 3)
> +       global += bar (i);
> +      if (i - 1 < base)
> +       global += bar (i);
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump-times "loop iv compare heuristics:
> 0.0%" 4 "profile_estimate"} } */
> +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
> Index: gcc/predict.c
> ===================================================================
> --- gcc/predict.c       (revision 185903)
> +++ gcc/predict.c       (working copy)
> @@ -1070,6 +1070,8 @@
>     bound = get_base_value (bound);
>   if (!bound)
>     return false;
> +  if (TREE_CODE (base) != INTEGER_CST)
> +    base = get_base_value (base);
>
>   *loop_invariant = bound;
>   *compare_code = code;
> @@ -1185,8 +1187,7 @@
>       return;
>     }
>
> -  if (!expr_coherent_p (loop_bound_var, compare_var)
> -      || loop_iv_base_var != compare_base)
> +  if (!expr_coherent_p(loop_iv_base_var, compare_base))
>     return;
>
>   /* If loop bound, base and compare bound are all constents, we can
> @@ -1230,34 +1231,52 @@
>       return;
>     }
>
> -  if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
> -      && (compare_code == LT_EXPR || compare_code == LE_EXPR))
> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
> -  else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
> -          && (compare_code == GT_EXPR || compare_code == GE_EXPR))
> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
> -  else if (loop_bound_code == NE_EXPR)
> -    {
> -      /* If the loop backedge condition is "(i != bound)", we do
> -        the comparison based on the step of IV:
> -          * step < 0 : backedge condition is like (i > bound)
> -          * step > 0 : backedge condition is like (i < bound)  */
> -      gcc_assert (loop_bound_step != 0);
> +  if (expr_coherent_p (loop_bound_var, compare_var))
> +    {
> +      if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
> +         && (compare_code == LT_EXPR || compare_code == LE_EXPR))
> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
> +      else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
> +              && (compare_code == GT_EXPR || compare_code == GE_EXPR))
> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
> +      else if (loop_bound_code == NE_EXPR)
> +       {
> +         /* If the loop backedge condition is "(i != bound)", we do
> +            the comparison based on the step of IV:
> +            * step < 0 : backedge condition is like (i > bound)
> +            * step > 0 : backedge condition is like (i < bound)  */
> +         gcc_assert (loop_bound_step != 0);
> +         if (loop_bound_step > 0
> +             && (compare_code == LT_EXPR
> +                 || compare_code == LE_EXPR))
> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
> +         else if (loop_bound_step < 0
> +                  && (compare_code == GT_EXPR
> +                      || compare_code == GE_EXPR))
> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
> +         else
> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
> +       }
> +      else
> +       /* The branch is predicted not-taken if loop_bound_code is
> +          opposite with compare_code.  */
> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
> +    }
> +  else if (expr_coherent_p (loop_iv_base_var, compare_var))
> +    {
> +      /* For cases like:
> +          for (i = s; i < h; i++)
> +            if (i > s + 2) ....
> +        The branch should be predicted taken.  */
>       if (loop_bound_step > 0
> -         && (compare_code == LT_EXPR
> -             || compare_code == LE_EXPR))
> +         && (compare_code == GT_EXPR || compare_code == GE_EXPR))
>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>       else if (loop_bound_step < 0
> -              && (compare_code == GT_EXPR
> -                  || compare_code == GE_EXPR))
> +              && (compare_code == LT_EXPR || compare_code == LE_EXPR))
>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>       else
>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
>     }
> -  else
> -    /* The branch is predicted not-taken if loop_bound_code is
> -       opposite with compare_code.  */
> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
>  }
>
>  /* Predict edge probabilities by exploiting loop structure.  */
>
> On Thu, Mar 29, 2012 at 8:06 AM, Xinliang David Li <davidxl@google.com> wrote:
>> Can the test case be improved so that expected prediction results is
>> checked (with the help of more dumping such as blah blah is predicted
>> to be taken/not taken with probability xyz) ?
>>
>> Also the more test cases need to be added to cover more cases >base, >
>> base +1, >=base +2, < base+1, <=base+1 etc -- even though expression
>> reassociation will normalize them ...
>>
>> Thanks,
>>
>> David
>>
>> On Wed, Mar 28, 2012 at 4:54 PM, Dehao Chen <dehao@google.com> wrote:
>>> Hi,
>>>
>>> This patch handles the comparison of iv against the loop iv initial
>>> value. Previously, we only handle the comparison of iv against its
>>> bound.
>>>
>>> Bootstrapped and passed all regression tests.
>>>
>>> Ok for google branches?
>>>
>>> Thanks,
>>> Dehao
>>>
>>> 2012-03-29  Dehao Chen  <dehao@google.com>
>>>
>>>        * predict.c (predict_iv_comparison): Add the comparison of induction
>>>        variable against its initial value.
>>>
>>> 2012-03-29  Dehao Chen  <dehao@google.com>
>>>
>>>        * gcc.dg/predict-5.c: Check if LOOP_IV_COMPARE static predict
>>>        heuristic is working properly.
>>>
>>> Index: gcc/testsuite/gcc.dg/predict-5.c
>>> ===================================================================
>>> --- gcc/testsuite/gcc.dg/predict-5.c    (revision 0)
>>> +++ gcc/testsuite/gcc.dg/predict-5.c    (revision 0)
>>> @@ -0,0 +1,21 @@
>>> +/* { dg-do compile } */
>>> +/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
>>> +
>>> +extern int global;
>>> +
>>> +int bar(int);
>>> +
>>> +void foo (int base, int bound)
>>> +{
>>> +  int i, ret = 0;
>>> +  for (i = base; i <= bound; i++)
>>> +    {
>>> +      if (i > base + 2)
>>> +       global += bar (i);
>>> +      else
>>> +        global += bar (i + 1);
>>> +    }
>>> +}
>>> +
>>> +/* { dg-final { scan-tree-dump "loop iv compare heuristics"
>>> "profile_estimate"} } */
>>> +/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
>>> Index: gcc/predict.c
>>> ===================================================================
>>> --- gcc/predict.c       (revision 185903)
>>> +++ gcc/predict.c       (working copy)
>>> @@ -1185,8 +1185,7 @@
>>>       return;
>>>     }
>>>
>>> -  if (!expr_coherent_p (loop_bound_var, compare_var)
>>> -      || loop_iv_base_var != compare_base)
>>> +  if (loop_iv_base_var != compare_base)
>>>     return;
>>>
>>>   /* If loop bound, base and compare bound are all constents, we can
>>> @@ -1230,34 +1229,52 @@
>>>       return;
>>>     }
>>>
>>> -  if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
>>> -      && (compare_code == LT_EXPR || compare_code == LE_EXPR))
>>> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>>> -  else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
>>> -          && (compare_code == GT_EXPR || compare_code == GE_EXPR))
>>> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>>> -  else if (loop_bound_code == NE_EXPR)
>>> -    {
>>> -      /* If the loop backedge condition is "(i != bound)", we do
>>> -        the comparison based on the step of IV:
>>> -          * step < 0 : backedge condition is like (i > bound)
>>> -          * step > 0 : backedge condition is like (i < bound)  */
>>> -      gcc_assert (loop_bound_step != 0);
>>> +  if (expr_coherent_p (loop_bound_var, compare_var))
>>> +    {
>>> +      if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
>>> +         && (compare_code == LT_EXPR || compare_code == LE_EXPR))
>>> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>>> +      else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
>>> +              && (compare_code == GT_EXPR || compare_code == GE_EXPR))
>>> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>>> +      else if (loop_bound_code == NE_EXPR)
>>> +       {
>>> +         /* If the loop backedge condition is "(i != bound)", we do
>>> +            the comparison based on the step of IV:
>>> +            * step < 0 : backedge condition is like (i > bound)
>>> +            * step > 0 : backedge condition is like (i < bound)  */
>>> +         gcc_assert (loop_bound_step != 0);
>>> +         if (loop_bound_step > 0
>>> +             && (compare_code == LT_EXPR
>>> +                 || compare_code == LE_EXPR))
>>> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>>> +         else if (loop_bound_step < 0
>>> +                  && (compare_code == GT_EXPR
>>> +                      || compare_code == GE_EXPR))
>>> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>>> +         else
>>> +           predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
>>> +       }
>>> +      else
>>> +       /* The branch is predicted not-taken if loop_bound_code is
>>> +          opposite with compare_code.  */
>>> +       predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
>>> +    }
>>> +  else if (expr_coherent_p (loop_iv_base_var, compare_var))
>>> +    {
>>> +      /* For cases like:
>>> +          for (i = s; i < h; i++)
>>> +            if (i > s + 2) ....
>>> +        The branch should be predicted taken.  */
>>>       if (loop_bound_step > 0
>>> -         && (compare_code == LT_EXPR
>>> -             || compare_code == LE_EXPR))
>>> +         && (compare_code == GT_EXPR || compare_code == GE_EXPR))
>>>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>>>       else if (loop_bound_step < 0
>>> -              && (compare_code == GT_EXPR
>>> -                  || compare_code == GE_EXPR))
>>> +              && (compare_code == LT_EXPR || compare_code == LE_EXPR))
>>>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
>>>       else
>>>        predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
>>>     }
>>> -  else
>>> -    /* The branch is predicted not-taken if loop_bound_code is
>>> -       opposite with compare_code.  */
>>> -    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
>>>  }
>>>
>>>  /* Predict edge probabilities by exploiting loop structure.  */
diff mbox

Patch

Index: gcc/testsuite/gcc.dg/predict-3.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-3.c	(revision 185903)
+++ gcc/testsuite/gcc.dg/predict-3.c	(working copy)
@@ -10,10 +10,16 @@ 
   int i, ret = 0;
   for (i = 0; i <= bound; i++)
     {
+      if (i < bound - 2)
+	global += bar (i);
+      if (i <= bound)
+	global += bar (i);
+      if (i + 1 < bound)
+	global += bar (i);
       if (i != bound)
 	global += bar (i);
     }
 }

-/* { dg-final { scan-tree-dump "loop iv compare heuristics"
"profile_estimate"} } */
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics:
100.0%" 4 "profile_estimate"} } */
 /* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/testsuite/gcc.dg/predict-4.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-4.c	(revision 185903)
+++ gcc/testsuite/gcc.dg/predict-4.c	(working copy)
@@ -15,5 +15,5 @@ 
     }
 }

-/* { dg-final { scan-tree-dump "loop iv compare heuristics"
"profile_estimate"} } */
+/* { dg-final { scan-tree-dump "loop iv compare heuristics: 50.0%"
"profile_estimate"} } */
 /* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/testsuite/gcc.dg/predict-1.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-1.c	(revision 185903)
+++ gcc/testsuite/gcc.dg/predict-1.c	(working copy)
@@ -10,10 +10,18 @@ 
   int i, ret = 0;
   for (i = 0; i < bound; i++)
     {
+      if (i > bound)
+	global += bar (i);
+      if (i >= bound + 2)
+	global += bar (i);
       if (i > bound - 2)
 	global += bar (i);
+      if (i + 2 > bound)
+	global += bar (i);
+      if (i == 10)
+	global += bar (i);
     }
 }

-/* { dg-final { scan-tree-dump "loop iv compare heuristics"
"profile_estimate"} } */
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics:
0.0%" 5 "profile_estimate"} } */
 /* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/testsuite/gcc.dg/predict-5.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-5.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-5.c	(revision 0)
@@ -0,0 +1,25 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i <= bound; i++)
+    {
+      if (i > base)
+	global += bar (i);
+      if (i > base + 1)
+	global += bar (i);
+      if (i >= base + 3)
+	global += bar (i);
+      if (i - 2 >= base)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics:
100.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/testsuite/gcc.dg/predict-2.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-2.c	(revision 185903)
+++ gcc/testsuite/gcc.dg/predict-2.c	(working copy)
@@ -5,12 +5,20 @@ 

 int bar(int);

-void foo (int bound)
+void foo (int base, int bound)
 {
   int i, ret = 0;
-  for (i = 0; i < bound; i++)
+  for (i = base; i < bound; i++)
     {
-      if (i > bound * bound )
+      if (i > bound * bound)
+	global += bar (i);
+      if (i > bound + 10)
+	global += bar (i);
+      if (i <= bound + 10)
+	global += bar (i);
+      if (i > base + 10)
+	global += bar (i);
+      if (i < base - 10)
 	global += bar (i);
     }
 }
Index: gcc/testsuite/gcc.dg/predict-6.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-6.c	(revision 0)
+++ gcc/testsuite/gcc.dg/predict-6.c	(revision 0)
@@ -0,0 +1,25 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar (int);
+
+void foo (int base, int bound)
+{
+  int i, ret = 0;
+  for (i = base; i <= bound; i++)
+    {
+      if (i < base)
+	global += bar (i);
+      if (i < base + 1)
+	global += bar (i);
+      if (i <= base + 3)
+	global += bar (i);
+      if (i - 1 < base)
+	global += bar (i);
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "loop iv compare heuristics:
0.0%" 4 "profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/predict.c
===================================================================
--- gcc/predict.c	(revision 185903)
+++ gcc/predict.c	(working copy)
@@ -1070,6 +1070,8 @@ 
     bound = get_base_value (bound);
   if (!bound)
     return false;
+  if (TREE_CODE (base) != INTEGER_CST)
+    base = get_base_value (base);

   *loop_invariant = bound;
   *compare_code = code;
@@ -1185,8 +1187,7 @@ 
       return;
     }

-  if (!expr_coherent_p (loop_bound_var, compare_var)
-      || loop_iv_base_var != compare_base)
+  if (!expr_coherent_p(loop_iv_base_var, compare_base))
     return;

   /* If loop bound, base and compare bound are all constents, we can
@@ -1230,34 +1231,52 @@ 
       return;
     }

-  if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
-      && (compare_code == LT_EXPR || compare_code == LE_EXPR))
-    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
-  else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
-	   && (compare_code == GT_EXPR || compare_code == GE_EXPR))
-    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
-  else if (loop_bound_code == NE_EXPR)
-    {
-      /* If the loop backedge condition is "(i != bound)", we do
-	 the comparison based on the step of IV:
-	   * step < 0 : backedge condition is like (i > bound)
-	   * step > 0 : backedge condition is like (i < bound)  */
-      gcc_assert (loop_bound_step != 0);
+  if (expr_coherent_p (loop_bound_var, compare_var))
+    {
+      if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
+	  && (compare_code == LT_EXPR || compare_code == LE_EXPR))
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
+      else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
+	       && (compare_code == GT_EXPR || compare_code == GE_EXPR))
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
+      else if (loop_bound_code == NE_EXPR)
+	{
+	  /* If the loop backedge condition is "(i != bound)", we do
+	     the comparison based on the step of IV:
+	     * step < 0 : backedge condition is like (i > bound)
+	     * step > 0 : backedge condition is like (i < bound)  */
+	  gcc_assert (loop_bound_step != 0);
+	  if (loop_bound_step > 0
+	      && (compare_code == LT_EXPR
+		  || compare_code == LE_EXPR))
+	    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
+	  else if (loop_bound_step < 0
+		   && (compare_code == GT_EXPR
+		       || compare_code == GE_EXPR))
+	    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
+	  else
+	    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
+	}
+      else
+	/* The branch is predicted not-taken if loop_bound_code is
+	   opposite with compare_code.  */
+	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
+    }
+  else if (expr_coherent_p (loop_iv_base_var, compare_var))
+    {
+      /* For cases like:
+	   for (i = s; i < h; i++)
+	     if (i > s + 2) ....
+	 The branch should be predicted taken.  */
       if (loop_bound_step > 0
-	  && (compare_code == LT_EXPR
-	      || compare_code == LE_EXPR))
+	  && (compare_code == GT_EXPR || compare_code == GE_EXPR))
 	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
       else if (loop_bound_step < 0
-	       && (compare_code == GT_EXPR
-		   || compare_code == GE_EXPR))
+	       && (compare_code == LT_EXPR || compare_code == LE_EXPR))
 	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
       else
 	predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
     }
-  else
-    /* The branch is predicted not-taken if loop_bound_code is
-       opposite with compare_code.  */
-    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
 }

 /* Predict edge probabilities by exploiting loop structure.  */