This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Static branch prediction: compare IV to loop bound variable (issue 5504086)


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/


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]