| Message ID | CAO2gOZXswJv1EDBWnHbfitEuTDSsN3F=HNaV7tdk97r+R42oyg@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
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. */
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. */