Re: [google] Refine static branch prediction (iv-compare heuristic)
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 de...@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 de...@google.com
* predict.c (predict_iv_comparison): Add the comparison of induction
variable against its initial value.
2012-03-29 Dehao Chen de...@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
Re: [google] Refine static branch prediction (iv-compare heuristic)
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,
Re: [google] Refine static branch prediction (iv-compare heuristic)
Ok for google branches.
thanks,
David
On Wed, Mar 28, 2012 at 7:55 PM, Dehao Chen de...@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
