* [google] Refine static branch prediction (iv-compare heuristic)
@ 2012-03-28 23:55 Dehao Chen
2012-03-29 0:07 ` Xinliang David Li
0 siblings, 1 reply; 4+ messages in thread
From: Dehao Chen @ 2012-03-28 23:55 UTC (permalink / raw)
To: gcc-patches; +Cc: David Li
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. */
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [google] Refine static branch prediction (iv-compare heuristic)
2012-03-28 23:55 [google] Refine static branch prediction (iv-compare heuristic) Dehao Chen
@ 2012-03-29 0:07 ` Xinliang David Li
2012-03-29 2:56 ` Dehao Chen
0 siblings, 1 reply; 4+ messages in thread
From: Xinliang David Li @ 2012-03-29 0:07 UTC (permalink / raw)
To: Dehao Chen; +Cc: gcc-patches
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. */
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [google] Refine static branch prediction (iv-compare heuristic)
2012-03-29 0:07 ` Xinliang David Li
@ 2012-03-29 2:56 ` Dehao Chen
2012-03-29 3:01 ` Xinliang David Li
0 siblings, 1 reply; 4+ messages in thread
From: Dehao Chen @ 2012-03-29 2:56 UTC (permalink / raw)
To: Xinliang David Li; +Cc: gcc-patches
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 <davidxl@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 <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. */
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [google] Refine static branch prediction (iv-compare heuristic)
2012-03-29 2:56 ` Dehao Chen
@ 2012-03-29 3:01 ` Xinliang David Li
0 siblings, 0 replies; 4+ messages in thread
From: Xinliang David Li @ 2012-03-29 3:01 UTC (permalink / raw)
To: Dehao Chen; +Cc: gcc-patches
Ok for google branches.
thanks,
David
On Wed, Mar 28, 2012 at 7:55 PM, Dehao Chen <dehao@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 <davidxl@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 <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. */
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2012-03-29 3:01 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-03-28 23:55 [google] Refine static branch prediction (iv-compare heuristic) Dehao Chen
2012-03-29 0:07 ` Xinliang David Li
2012-03-29 2:56 ` Dehao Chen
2012-03-29 3:01 ` Xinliang David Li
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).