Static branch prediction: compare IV to loop bound variable

In loop body, if a branch compares IV to a loop bound variable, or an expr that contains it, we could make more aggressive prediction.

[davidxl, 2011-12-27 20:27:32]

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c
File gcc/predict.c (right):

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode953
gcc/predict.c:953: find_ssa_name (tree t)
Why is the function needed? bound should either be a SSA_NAME or constant. For
other cases just return null.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1054
gcc/predict.c:1054: {
You may want to limit the other operand to be an integer value <=2.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1072
gcc/predict.c:1072: t = gimple_assign_rhs3 (stmt);
rhs3?

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1100
gcc/predict.c:1100: stmt = SSA_NAME_DEF_STMT (t1);
Check to see if t1 is expressed/defined with t2.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1110
gcc/predict.c:1110: stmt = SSA_NAME_DEF_STMT (t2);
Check if t2 is expressed/defined with t1.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1141
gcc/predict.c:1141: predict_iv_comparison(struct loop *loop, basic_block bb,
space

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1173
gcc/predict.c:1173: {
Remove {}

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1181
gcc/predict.c:1181: {
Add more comments on the heuristics here.

[dehao, 2011-12-28 03:19:25]

Hi, David,

I've updated the CL.

Thanks,
Dehao

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c
File gcc/predict.c (right):

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode953
gcc/predict.c:953: find_ssa_name (tree t)
Because iv.base could be either SSA_NAME or a computation expr that is
constituted of SSA_NAME and a constant (as operand). This expr is not
necessarily stored in a SSA_NAME.

Currently, we check if the expression contains only one SSA_NAME operand. Do you
think we need to check that the other operand is constant?

On 2011/12/27 20:27:32, davidxl wrote:
> Why is the function needed? bound should either be a SSA_NAME or constant. For
> other cases just return null.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1054
gcc/predict.c:1054: {
On 2011/12/27 20:27:32, davidxl wrote:
> You may want to limit the other operand to be an integer value <=2.

Done.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1072
gcc/predict.c:1072: t = gimple_assign_rhs3 (stmt);
On 2011/12/27 20:27:32, davidxl wrote:
> rhs3?

Done.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1100
gcc/predict.c:1100: stmt = SSA_NAME_DEF_STMT (t1);
On 2011/12/27 20:27:32, davidxl wrote:
> Check to see if t1 is expressed/defined with t2.

Done.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1110
gcc/predict.c:1110: stmt = SSA_NAME_DEF_STMT (t2);
On 2011/12/27 20:27:32, davidxl wrote:
> Check if t2 is expressed/defined with t1.

Done.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1141
gcc/predict.c:1141: predict_iv_comparison(struct loop *loop, basic_block bb,
On 2011/12/27 20:27:32, davidxl wrote:
> space

Done.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1173
gcc/predict.c:1173: {
On 2011/12/27 20:27:32, davidxl wrote:
> Remove {}

Done.

http://codereview.appspot.com/5504086/diff/1/gcc/predict.c#newcode1181
gcc/predict.c:1181: {
On 2011/12/27 20:27:32, davidxl wrote:
> Add more comments on the heuristics here.

Done.

[davidxl, 2011-12-28 07:03:55]

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c
File gcc/predict.c (right):

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode999
gcc/predict.c:999: switch (TREE_OPERAND_LENGTH (t))
Can the expression 't' be something like indirect ref expression? You may want
to limit the expression to binary arithmetic.

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1032
gcc/predict.c:1032: find_loop_invariant (gimple stmt, struct loop *loop,
change the function name to 'is_comparison_with_loop_invariant_p (...)'

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1147
gcc/predict.c:1147: if (i < bound - 3)
Change the example to bound - 2 to match the implementation.

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1191
gcc/predict.c:1191: else if ((loop_bound_code == LT_EXPR || loop_bound_code ==
LE_EXPR)
The NE and EQ heuristic should be peeled out and moved before the check
'is_bound_expr_similar'.

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1217
gcc/predict.c:1217: predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE,
NOT_TAKEN);
Remove {} and explain this case a little more.

[dehao, 2011-12-28 07:55:20]

Hi, David,

Thanks for reviewing.

Dehao

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c
File gcc/predict.c (right):

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode999
gcc/predict.c:999: switch (TREE_OPERAND_LENGTH (t))
On 2011/12/28 07:03:55, davidxl wrote:
> Can the expression 't' be something like indirect ref expression? You may want
> to limit the expression to binary arithmetic.

Done.

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1032
gcc/predict.c:1032: find_loop_invariant (gimple stmt, struct loop *loop,
On 2011/12/28 07:03:55, davidxl wrote:
> change the function name to 'is_comparison_with_loop_invariant_p (...)'

Done.

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1147
gcc/predict.c:1147: if (i < bound - 3)
On 2011/12/28 07:03:55, davidxl wrote:
> Change the example to bound - 2 to match the implementation.

Done.

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1191
gcc/predict.c:1191: else if ((loop_bound_code == LT_EXPR || loop_bound_code ==
LE_EXPR)
Do you mean that even the exprs are not similar, we still will predict it
taken/not-taken because it's comparing an IV to a Loop-Invariant?

If so, Done.

On 2011/12/28 07:03:55, davidxl wrote:
> The NE and EQ heuristic should be peeled out and moved before the check
> 'is_bound_expr_similar'.

http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1217
gcc/predict.c:1217: predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE,
NOT_TAKEN);
On 2011/12/28 07:03:55, davidxl wrote:
> Remove {} and explain this case a little more.

Done.

[davidxl, 2011-12-28 08:01:23]

After more testing, you can submit it upstream for review..

David

On Tue, Dec 27, 2011 at 11:55 PM,  <dehao@google.com> wrote:
> Hi, David,
>
> Thanks for reviewing.
>
> Dehao
>
>
>
> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c
> File gcc/predict.c (right):
>
> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode999
> gcc/predict.c:999: switch (TREE_OPERAND_LENGTH (t))
> On 2011/12/28 07:03:55, davidxl wrote:
>>
>> Can the expression 't' be something like indirect ref expression? You
>
> may want
>>
>> to limit the expression to binary arithmetic.
>
>
> Done.
>
>
> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1032
> gcc/predict.c:1032: find_loop_invariant (gimple stmt, struct loop *loop,
> On 2011/12/28 07:03:55, davidxl wrote:
>>
>> change the function name to 'is_comparison_with_loop_invariant_p
>
> (...)'
>
> Done.
>
>
> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1147
> gcc/predict.c:1147: if (i < bound - 3)
> On 2011/12/28 07:03:55, davidxl wrote:
>>
>> Change the example to bound - 2 to match the implementation.
>
>
> Done.
>
>
> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1191
> gcc/predict.c:1191: else if ((loop_bound_code == LT_EXPR ||
> loop_bound_code == LE_EXPR)
> Do you mean that even the exprs are not similar, we still will predict
> it taken/not-taken because it's comparing an IV to a Loop-Invariant?
>
> If so, Done.
>
>
> On 2011/12/28 07:03:55, davidxl wrote:
>>
>> The NE and EQ heuristic should be peeled out and moved before the
>
> check
>>
>> 'is_bound_expr_similar'.
>
>
> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1217
> gcc/predict.c:1217: predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE,
> NOT_TAKEN);
> On 2011/12/28 07:03:55, davidxl wrote:
>>
>> Remove {} and explain this case a little more.
>
>
> Done.
>
> http://codereview.appspot.com/5504086/

[dehao, 2011-12-28 08:12:41]

Shall it go to trun/google branch?

Dehao

On Wed, Dec 28, 2011 at 4:01 PM, Xinliang David Li <davidxl@google.com> wrote:
> After more testing, you can submit it upstream for review..
>
> David
>
> On Tue, Dec 27, 2011 at 11:55 PM,  <dehao@google.com> wrote:
>> Hi, David,
>>
>> Thanks for reviewing.
>>
>> Dehao
>>
>>
>>
>> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c
>> File gcc/predict.c (right):
>>
>> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode999
>> gcc/predict.c:999: switch (TREE_OPERAND_LENGTH (t))
>> On 2011/12/28 07:03:55, davidxl wrote:
>>>
>>> Can the expression 't' be something like indirect ref expression? You
>>
>> may want
>>>
>>> to limit the expression to binary arithmetic.
>>
>>
>> Done.
>>
>>
>> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1032
>> gcc/predict.c:1032: find_loop_invariant (gimple stmt, struct loop *loop,
>> On 2011/12/28 07:03:55, davidxl wrote:
>>>
>>> change the function name to 'is_comparison_with_loop_invariant_p
>>
>> (...)'
>>
>> Done.
>>
>>
>> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1147
>> gcc/predict.c:1147: if (i < bound - 3)
>> On 2011/12/28 07:03:55, davidxl wrote:
>>>
>>> Change the example to bound - 2 to match the implementation.
>>
>>
>> Done.
>>
>>
>> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1191
>> gcc/predict.c:1191: else if ((loop_bound_code == LT_EXPR ||
>> loop_bound_code == LE_EXPR)
>> Do you mean that even the exprs are not similar, we still will predict
>> it taken/not-taken because it's comparing an IV to a Loop-Invariant?
>>
>> If so, Done.
>>
>>
>> On 2011/12/28 07:03:55, davidxl wrote:
>>>
>>> The NE and EQ heuristic should be peeled out and moved before the
>>
>> check
>>>
>>> 'is_bound_expr_similar'.
>>
>>
>> http://codereview.appspot.com/5504086/diff/6/gcc/predict.c#newcode1217
>> gcc/predict.c:1217: predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE,
>> NOT_TAKEN);
>> On 2011/12/28 07:03:55, davidxl wrote:
>>>
>>> Remove {} and explain this case a little more.
>>
>>
>> Done.
>>
>> http://codereview.appspot.com/5504086/

[davidxl, 2012-01-31 01:25:42]

Ok for google branches for now.

thanks,

David

http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c
File gcc/predict.c (right):

http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode958
gcc/predict.c:958: find_qualified_ssa_name (tree t1, tree t2)
Better change the name into 'strips_small_constant'

http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode991
gcc/predict.c:991: Return NULL if T does not satisfy IV_COMPARE condition.  */
Fix comment -- there is no IV_COMPARE used here.

http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode995
gcc/predict.c:995: {
Better change the name into 'get_base_value (tree t)' because the method
basically strips the constant 'offset' away.

http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode1102
gcc/predict.c:1102: a similar variable.  */
Fix the comments. Returns true if T1 and T2 are value coherent.

http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode1106
gcc/predict.c:1106: {
May be changing the name to 

expr_coherent_p (tree t1, tree t2)

http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode1206
gcc/predict.c:1206: && (compare_code == LT_EXPR || compare_code == LE_EXPR))
Fix indentation.

[dehao, 2012-02-01 15:33:21]

There are still some minor bugs in the current implementation, which
is fixed by the attached patch:

passed bootstrap/regression tests for both google-4_6 and google-main branch.

ok for google branch?

Thanks,
Dehao

gcc/ChangeLog.google-4_6
2012-01-31  Dehao Chen  <dehao@google.com>

	* predict.c (predict_iv_comparison): Add new parameter, ensure that
	the loop_iv_base and compare_base are identical.

Index: gcc/predict.c
===================================================================
--- gcc/predict.c	(revision 183783)
+++ gcc/predict.c	(working copy)
@@ -1126,8 +1126,8 @@
 }

 /* Predict branch probability of BB when BB contains a branch that compares
-   an induction variable in LOOP to LOOP_BOUND_VAR. The loop exit is
-   compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
+   an induction variable with LOOP_IV_BASE_VAR in LOOP to LOOP_BOUND_VAR. The
+   loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.

    E.g.
      for (int i = 0; i < bound; i++) {
@@ -1142,6 +1142,7 @@
 static void
 predict_iv_comparison (struct loop *loop, basic_block bb,
 		       tree loop_bound_var,
+		       tree loop_iv_base_var,
 		       enum tree_code loop_bound_code,
 		       int loop_bound_step)
 {
@@ -1184,7 +1185,8 @@
       return;
     }

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

   /* If loop bound, base and compare bound are all constents, we can
@@ -1213,13 +1215,17 @@
 	compare_count ++;
       if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
 	loop_count ++;
+      if (compare_count < 0)
+	compare_count = 0;
+      if (loop_count < 0)
+	loop_count = 0;

       if (loop_count == 0)
 	probability = 0;
       else if (compare_count > loop_count)
-	probability = 1;
+	probability = REG_BR_PROB_BASE;
       else
-	probability = REG_BR_PROB_BASE * compare_count / loop_count;
+	probability = (double) REG_BR_PROB_BASE * compare_count / loop_count;
       predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
       return;
     }
@@ -1405,7 +1411,7 @@
 		  predict_edge (e, PRED_LOOP_EXIT, probability);
 	    }
 	  if (loop_bound_var)
-	    predict_iv_comparison (loop, bb, loop_bound_var,
+	    predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
 				   loop_bound_code,
 				   loop_bound_step);
 	}

On Mon, Jan 30, 2012 at 5:25 PM,  <davidxl@google.com> wrote:
> Ok for google branches for now.
>
> thanks,
>
> David
>
>
> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c
> File gcc/predict.c (right):
>
> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode958
> gcc/predict.c:958: find_qualified_ssa_name (tree t1, tree t2)
> Better change the name into 'strips_small_constant'
>
> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode991
> gcc/predict.c:991: Return NULL if T does not satisfy IV_COMPARE
> condition.  */
> Fix comment -- there is no IV_COMPARE used here.
>
> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode995
> gcc/predict.c:995: {
> Better change the name into 'get_base_value (tree t)' because the method
> basically strips the constant 'offset' away.
>
> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode1102
> gcc/predict.c:1102: a similar variable.  */
> Fix the comments. Returns true if T1 and T2 are value coherent.
>
> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode1106
> gcc/predict.c:1106: {
> May be changing the name to
>
> expr_coherent_p (tree t1, tree t2)
>
> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode1206
> gcc/predict.c:1206: && (compare_code == LT_EXPR || compare_code ==
> LE_EXPR))
> Fix indentation.
>
> http://codereview.appspot.com/5504086/

[davidxl, 2012-02-01 16:41:19]

ok.

thanks,

David

On Wed, Feb 1, 2012 at 7:33 AM, Dehao Chen <dehao@google.com> wrote:
> There are still some minor bugs in the current implementation, which
> is fixed by the attached patch:
>
> passed bootstrap/regression tests for both google-4_6 and google-main branch.
>
> ok for google branch?
>
> Thanks,
> Dehao
>
> gcc/ChangeLog.google-4_6
> 2012-01-31  Dehao Chen  <dehao@google.com>
>
>        * predict.c (predict_iv_comparison): Add new parameter, ensure that
>        the loop_iv_base and compare_base are identical.
>
> Index: gcc/predict.c
> ===================================================================
> --- gcc/predict.c       (revision 183783)
> +++ gcc/predict.c       (working copy)
> @@ -1126,8 +1126,8 @@
>  }
>
>  /* Predict branch probability of BB when BB contains a branch that compares
> -   an induction variable in LOOP to LOOP_BOUND_VAR. The loop exit is
> -   compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
> +   an induction variable with LOOP_IV_BASE_VAR in LOOP to LOOP_BOUND_VAR. The
> +   loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
>
>    E.g.
>      for (int i = 0; i < bound; i++) {
> @@ -1142,6 +1142,7 @@
>  static void
>  predict_iv_comparison (struct loop *loop, basic_block bb,
>                       tree loop_bound_var,
> +                      tree loop_iv_base_var,
>                       enum tree_code loop_bound_code,
>                       int loop_bound_step)
>  {
> @@ -1184,7 +1185,8 @@
>       return;
>     }
>
> -  if (!expr_coherent_p (loop_bound_var, compare_var))
> +  if (!expr_coherent_p (loop_bound_var, compare_var)
> +      || loop_iv_base_var != compare_base)
>     return;
>
>   /* If loop bound, base and compare bound are all constents, we can
> @@ -1213,13 +1215,17 @@
>        compare_count ++;
>       if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
>        loop_count ++;
> +      if (compare_count < 0)
> +       compare_count = 0;
> +      if (loop_count < 0)
> +       loop_count = 0;
>
>       if (loop_count == 0)
>        probability = 0;
>       else if (compare_count > loop_count)
> -       probability = 1;
> +       probability = REG_BR_PROB_BASE;
>       else
> -       probability = REG_BR_PROB_BASE * compare_count / loop_count;
> +       probability = (double) REG_BR_PROB_BASE * compare_count / loop_count;
>       predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
>       return;
>     }
> @@ -1405,7 +1411,7 @@
>                  predict_edge (e, PRED_LOOP_EXIT, probability);
>            }
>          if (loop_bound_var)
> -           predict_iv_comparison (loop, bb, loop_bound_var,
> +           predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
>                                   loop_bound_code,
>                                   loop_bound_step);
>        }
>
> On Mon, Jan 30, 2012 at 5:25 PM,  <davidxl@google.com> wrote:
>> Ok for google branches for now.
>>
>> thanks,
>>
>> David
>>
>>
>> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c
>> File gcc/predict.c (right):
>>
>> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode958
>> gcc/predict.c:958: find_qualified_ssa_name (tree t1, tree t2)
>> Better change the name into 'strips_small_constant'
>>
>> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode991
>> gcc/predict.c:991: Return NULL if T does not satisfy IV_COMPARE
>> condition.  */
>> Fix comment -- there is no IV_COMPARE used here.
>>
>> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode995
>> gcc/predict.c:995: {
>> Better change the name into 'get_base_value (tree t)' because the method
>> basically strips the constant 'offset' away.
>>
>> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode1102
>> gcc/predict.c:1102: a similar variable.  */
>> Fix the comments. Returns true if T1 and T2 are value coherent.
>>
>> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode1106
>> gcc/predict.c:1106: {
>> May be changing the name to
>>
>> expr_coherent_p (tree t1, tree t2)
>>
>> http://codereview.appspot.com/5504086/diff/1004/gcc/predict.c#newcode1206
>> gcc/predict.c:1206: && (compare_code == LT_EXPR || compare_code ==
>> LE_EXPR))
>> Fix indentation.
>>
>> http://codereview.appspot.com/5504086/