[PATCH]: Add static branch predict heuristic of comparing IV to loop_bound variable
Dehao Chen
dehao@google.com
Fri Dec 30 04:13:00 GMT 2011
Hello,
This patch add a static branch predict heuristic for the following cases:
for (int i = 0; i < bound; i++) {
if (i < bound - 2)
computation_1();
else
computation_2();
}
In this case, we would predict the branch to be taken because it's
comparing loop induction variable to loop bound variable.
Tested with bootstrap, and no regression in the gcc testsuite.
Is it ok for mainline?
Thanks,
Dehao
http://codereview.appspot.com/5504086
gcc/ChangeLog
2011-12-30 Dehao Chen <dehao@google.com>
* predict.c (find_qualified_ssa_name): New
(find_ssa_name_in_expr): New
(find_ssa_name_in_assign_stmt): New
(is_comparison_with_loop_invariant_p): New
(is_bound_expr_similar): New
(predict_iv_comparison): New
(predict_loops): Add heuristic for loop-nested branches that compare an
induction variable to a loop bound variable.
* predict.def (PRED_LOOP_IV_COMPARE): New macro
gcc/testsuite/ChangeLog
2011-12-30 Dehao Chen <dehao@google.com>
* gcc.dg/predict-1.c: Check if LOOP_IV_COMPARE static predict
heuristic is working properly.
* gcc.dg/predict-2.c: Likewise.
* gcc/dg/predict-3.c: Likewise.
Index: gcc/testsuite/gcc.dg/predict-3.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-3.c (revision 0)
+++ gcc/testsuite/gcc.dg/predict-3.c (revision 0)
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+ int i, ret = 0;
+ for (i = 0; i <= bound; i++)
+ {
+ if (i != bound)
+ global += bar (i);
+ }
+}
+
+/* { dg-final { scan-tree-dump "loop iv compare heuristics"
"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 0)
+++ gcc/testsuite/gcc.dg/predict-1.c (revision 0)
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+ int i, ret = 0;
+ for (i = 0; i < bound; i++)
+ {
+ if (i > bound - 2)
+ global += bar (i);
+ }
+}
+
+/* { dg-final { scan-tree-dump "loop iv compare heuristics"
"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 0)
+++ gcc/testsuite/gcc.dg/predict-2.c (revision 0)
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+extern int global;
+
+int bar(int);
+
+void foo (int bound)
+{
+ int i, ret = 0;
+ for (i = 0; i < bound; i++)
+ {
+ if (i > bound * bound )
+ global += bar (i);
+ }
+}
+
+/* { dg-final { scan-tree-dump-not "loop iv compare heuristics"
"profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: gcc/predict.c
===================================================================
--- gcc/predict.c (revision 182738)
+++ gcc/predict.c (working copy)
@@ -946,6 +946,292 @@
}
}
+/* Check if T1 and T2 satisfy the IV_COMPARE condition.
+ Return the SSA_NAME if the condition satisfies, NULL otherwise.
+
+ T1 and T2 should be one of the following cases:
+ 1. T1 is SSA_NAME, T2 is NULL
+ 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
+ 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
+
+static tree
+find_qualified_ssa_name (tree t1, tree t2)
+{
+ tree ret = NULL;
+ int value = 0;
+
+ if (!t1)
+ return NULL;
+ else if (TREE_CODE (t1) == SSA_NAME)
+ ret = t1;
+ else if (TREE_CODE (t1) == INTEGER_CST)
+ value = TREE_INT_CST_LOW (t1);
+ else
+ return NULL;
+
+ if (!t2)
+ return ret;
+ else if (TREE_CODE (t2) == INTEGER_CST)
+ value = TREE_INT_CST_LOW (t2);
+ else if (TREE_CODE (t2) == SSA_NAME)
+ {
+ if (ret)
+ return NULL;
+ else
+ ret = t2;
+ }
+
+ if (value <= 4 && value >= -4)
+ return ret;
+ else
+ return NULL;
+}
+
+/* Return the SSA_NAME in T or T's operands.
+ Return NULL if T does not satisfy IV_COMPARE condition. */
+
+static tree
+find_ssa_name_in_expr (tree t)
+{
+ if (TREE_CODE (t) == SSA_NAME)
+ return t;
+
+ if (!BINARY_CLASS_P (t))
+ return NULL;
+
+ switch (TREE_OPERAND_LENGTH (t))
+ {
+ case 1:
+ return find_qualified_ssa_name (TREE_OPERAND (t, 0), NULL);
+ case 2:
+ return find_qualified_ssa_name (TREE_OPERAND (t, 0),
+ TREE_OPERAND (t, 1));
+ default:
+ return NULL;
+ }
+}
+
+/* Return the SSA_NAME in the rhs of assignment STMT.
+ Return NULL if STMT does not satisfy IV_COMPARE condition. */
+
+static tree
+find_ssa_name_in_assign_stmt (gimple stmt)
+{
+ gcc_assert (is_gimple_assign (stmt));
+
+ if (gimple_assign_rhs3 (stmt) != NULL)
+ return NULL;
+
+ return find_qualified_ssa_name (gimple_assign_rhs1 (stmt),
+ gimple_assign_rhs2 (stmt));
+}
+
+/* Check the compare STMT in LOOP. If it compares an induction
+ variable to a loop invariant, return true, and save
+ LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
+ Otherwise return false and set LOOP_INVAIANT to NULL. */
+
+static bool
+is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop,
+ tree *loop_invariant,
+ enum tree_code *compare_code,
+ int *loop_step)
+{
+ tree op0, op1, bound;
+ affine_iv iv0, iv1;
+ enum tree_code code;
+ int step;
+
+ code = gimple_cond_code (stmt);
+ *loop_invariant = NULL;
+
+ switch (code)
+ {
+ case GT_EXPR:
+ case GE_EXPR:
+ case NE_EXPR:
+ case LT_EXPR:
+ case LE_EXPR:
+ case EQ_EXPR:
+ break;
+
+ default:
+ return false;
+ }
+
+ op0 = gimple_cond_lhs (stmt);
+ op1 = gimple_cond_rhs (stmt);
+
+ if (TREE_CODE (op0) != SSA_NAME || TREE_CODE (op1) != SSA_NAME)
+ return false;
+ if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
+ return false;
+ if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
+ return false;
+ if (TREE_CODE (iv0.step) != INTEGER_CST
+ || TREE_CODE (iv1.step) != INTEGER_CST)
+ return false;
+ if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
+ || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
+ return false;
+
+ if (integer_zerop (iv0.step))
+ {
+ if (code != NE_EXPR && code != EQ_EXPR)
+ code = invert_tree_comparison (code, false);
+ bound = iv0.base;
+ step = TREE_INT_CST_LOW (iv1.step);
+ }
+ else
+ {
+ bound = iv1.base;
+ step = TREE_INT_CST_LOW (iv0.step);
+ }
+
+ bound = find_ssa_name_in_expr (bound);
+ if (!bound)
+ return false;
+
+ *loop_invariant = bound;
+ *compare_code = code;
+ *loop_step = step;
+ return true;
+}
+
+/* Compare two SSA_NAMEs: returns TRUE if T1 and T2 reference
+ a similar variable. */
+
+static bool
+is_bound_expr_similar (tree t1, tree t2)
+{
+ gimple stmt;
+ tree ssa_name_1 = NULL;
+ tree ssa_name_2 = NULL;
+
+ gcc_assert (TREE_CODE (t1) == SSA_NAME);
+ gcc_assert (TREE_CODE (t2) == SSA_NAME);
+
+ if (t1 == t2)
+ return true;
+
+ /* Check to see if t1 is expressed/defined with t2. */
+ stmt = SSA_NAME_DEF_STMT (t1);
+ gcc_assert (stmt != NULL);
+ if (is_gimple_assign (stmt))
+ {
+ ssa_name_1 = find_ssa_name_in_assign_stmt (stmt);
+ if (ssa_name_1 && ssa_name_1 == t2)
+ return true;
+ }
+
+ /* Check to see if t2 is expressed/defined with t1. */
+ stmt = SSA_NAME_DEF_STMT (t2);
+ gcc_assert (stmt != NULL);
+ if (is_gimple_assign (stmt))
+ {
+ ssa_name_2 = find_ssa_name_in_assign_stmt (stmt);
+ if (ssa_name_2 && ssa_name_2 == t1)
+ return true;
+ }
+
+ /* Compare if t1 and t2's def_stmts are identical. */
+ if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
+ return true;
+ else
+ return false;
+}
+
+/* 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.
+
+ E.g.
+ for (int i = 0; i < bound; i++) {
+ if (i < bound - 2)
+ computation_1();
+ else
+ computation_2();
+ }
+
+ In this loop, we will predict the branch inside the loop to be taken. */
+
+static void
+predict_iv_comparison (struct loop *loop, basic_block bb,
+ tree loop_bound_var,
+ enum tree_code loop_bound_code,
+ int loop_bound_step)
+{
+ gimple stmt;
+ tree compare_var;
+ enum tree_code compare_code;
+ int compare_step;
+ edge then_edge;
+ edge_iterator ei;
+
+ if (predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
+ || predicted_by_p (bb, PRED_LOOP_ITERATIONS)
+ || predicted_by_p (bb, PRED_LOOP_EXIT))
+ return;
+
+ stmt = last_stmt (bb);
+ if (!stmt || gimple_code (stmt) != GIMPLE_COND)
+ return;
+ if (!is_comparison_with_loop_invariant_p (stmt, loop, &compare_var,
+ &compare_code,
+ &compare_step))
+ return;
+
+ /* Find the taken edge. */
+ FOR_EACH_EDGE (then_edge, ei, bb->succs)
+ if (then_edge->flags & EDGE_TRUE_VALUE)
+ break;
+
+ /* When comparing an IV to a loop invariant, NE is more likely to be
+ taken while EQ is more likely to be not-taken. */
+ if (compare_code == NE_EXPR)
+ {
+ predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, TAKEN);
+ return;
+ }
+ else if (compare_code == EQ_EXPR)
+ {
+ predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE, NOT_TAKEN);
+ return;
+ }
+
+ if (!is_bound_expr_similar (loop_bound_var, compare_var))
+ 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 (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);
+}
+
/* Predict edge probabilities by exploiting loop structure. */
static void
@@ -963,6 +1249,11 @@
VEC (edge, heap) *exits;
struct tree_niter_desc niter_desc;
edge ex;
+ struct nb_iter_bound *nb_iter;
+ enum tree_code loop_bound_code = ERROR_MARK;
+ int loop_bound_step = 0;
+ tree loop_bound_var = NULL;
+ gimple stmt = NULL;
exits = get_loop_exit_edges (loop);
n_exits = VEC_length (edge, exits);
@@ -1010,6 +1301,24 @@
}
VEC_free (edge, heap, exits);
+ /* Find information about loop bound variables. */
+ for (nb_iter = loop->bounds; nb_iter;
+ nb_iter = nb_iter->next)
+ if (nb_iter->stmt
+ && gimple_code (nb_iter->stmt) == GIMPLE_COND)
+ {
+ stmt = nb_iter->stmt;
+ break;
+ }
+ if (!stmt && last_stmt (loop->header)
+ && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
+ stmt = last_stmt (loop->header);
+ if (stmt)
+ is_comparison_with_loop_invariant_p (stmt, loop,
+ &loop_bound_var,
+ &loop_bound_code,
+ &loop_bound_step);
+
bbs = get_loop_body (loop);
for (j = 0; j < loop->num_nodes; j++)
@@ -1071,6 +1380,10 @@
|| !flow_bb_inside_loop_p (loop, e->dest))
predict_edge (e, PRED_LOOP_EXIT, probability);
}
+ if (loop_bound_var)
+ predict_iv_comparison (loop, bb, loop_bound_var,
+ loop_bound_code,
+ loop_bound_step);
}
/* Free basic blocks from get_loop_body. */
Index: gcc/predict.def
===================================================================
--- gcc/predict.def (revision 182738)
+++ gcc/predict.def (working copy)
@@ -116,3 +116,7 @@
/* Branches to a mudflap bounds check are extremely unlikely. */
DEF_PREDICTOR (PRED_MUDFLAP, "mudflap check", PROB_VERY_LIKELY, 0)
+
+/* Branches to compare induction variable to a loop bound is
+ extremely likely. */
+DEF_PREDICTOR (PRED_LOOP_IV_COMPARE, "loop iv compare", PROB_VERY_LIKELY, 0)
More information about the Gcc-patches
mailing list