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

[Xinliang David Li <davidxl at google dot com>]

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. ?*/