Ok for google branches.
thanks,
David
On Wed, Mar 28, 2012 at 7:55 PM, Dehao Chen <de...@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 <davi...@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 <de...@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 <de...@google.com>
>>>
>>> * predict.c (predict_iv_comparison): Add the comparison of induction
>>> variable against its initial value.
>>>
>>> 2012-03-29 Dehao Chen <de...@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. */
