Hi,
I've updated the patch to invoke predict_extra_loop_exits in the right
place. Attached is the new patch.
Bootstrapped and passed gcc testsuite.
Thanks,
Dehao
Index: testsuite/g++.dg/predict-loop-exit-1.C
===================================================================
--- testsuite/g++.dg/predict-loop-exit-1.C (revision 0)
+++ testsuite/g++.dg/predict-loop-exit-1.C (revision 0)
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+int g;
+int foo();
+void test() {
+ while (foo() && g < 10)
+ g++;
+ return;
+}
+
+/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 3
"profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: testsuite/g++.dg/predict-loop-exit-3.C
===================================================================
--- testsuite/g++.dg/predict-loop-exit-3.C (revision 0)
+++ testsuite/g++.dg/predict-loop-exit-3.C (revision 0)
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+int g;
+int foo();
+void test() {
+ while (foo() && (g < 10 || g > 20))
+ g++;
+ return;
+}
+
+/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 3
"profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: testsuite/g++.dg/predict-loop-exit-2.C
===================================================================
--- testsuite/g++.dg/predict-loop-exit-2.C (revision 0)
+++ testsuite/g++.dg/predict-loop-exit-2.C (revision 0)
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+
+int g;
+int foo();
+void test() {
+ while (foo() || g < 10)
+ g++;
+ return;
+}
+
+/* { dg-final { scan-tree-dump-times "loop exit heuristics:" 2
"profile_estimate"} } */
+/* { dg-final { cleanup-tree-dump "profile_estimate" } } */
Index: predict.c
===================================================================
--- predict.c (revision 187922)
+++ predict.c (working copy)
@@ -1294,7 +1294,93 @@
predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
}
}
-
+
+/* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
+ exits are resulted from short-circuit conditions that will generate an
+ if_tmp. E.g.:
+
+ if (foo() || global > 10)
+ break;
+
+ This will be translated into:
+
+ BB3:
+ loop header...
+ BB4:
+ if foo() goto BB6 else goto BB5
+ BB5:
+ if global > 10 goto BB6 else goto BB7
+ BB6:
+ goto BB7
+ BB7:
+ iftmp = (PHI 0(BB5), 1(BB6))
+ if iftmp == 1 goto BB8 else goto BB3
+ BB8:
+ outside of the loop...
+
+ The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
+ From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
+ exits. This function takes BB7->BB8 as input, and finds out the extra loop
+ exits to predict them using PRED_LOOP_EXIT. */
+
+static void
+predict_extra_loop_exits (edge exit_edge)
+{
+ unsigned i;
+ bool check_value_one;
+ gimple phi_stmt;
+ tree cmp_rhs, cmp_lhs;
+ gimple cmp_stmt = last_stmt (exit_edge->src);
+
+ if (!cmp_stmt || gimple_code (cmp_stmt) != GIMPLE_COND)
+ return;
+ cmp_rhs = gimple_cond_rhs (cmp_stmt);
+ cmp_lhs = gimple_cond_lhs (cmp_stmt);
+ if (!TREE_CONSTANT (cmp_rhs)
+ || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
+ return;
+ if (TREE_CODE (cmp_lhs) != SSA_NAME)
+ return;
+
+ /* If check_value_one is true, only the phi_args with value '1' will lead
+ to loop exit. Otherwise, only the phi_args with value '0' will lead to
+ loop exit. */
+ check_value_one = (((integer_onep (cmp_rhs))
+ ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
+ ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
+
+ phi_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
+ if (!phi_stmt || gimple_code (phi_stmt) != GIMPLE_PHI)
+ return;
+
+ for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
+ {
+ edge e1;
+ edge_iterator ei;
+ tree val = gimple_phi_arg_def (phi_stmt, i);
+ edge e = gimple_phi_arg_edge (phi_stmt, i);
+
+ if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
+ continue;
+ if (check_value_one ^ integer_onep (val))
+ continue;
+ if (VEC_length (edge, e->src->succs) != 1)
+ {
+ if (!predicted_by_p (exit_edge->src, PRED_LOOP_ITERATIONS_GUESSED)
+ && !predicted_by_p (exit_edge->src, PRED_LOOP_ITERATIONS)
+ && !predicted_by_p (exit_edge->src, PRED_LOOP_EXIT))
+ predict_edge_def (e, PRED_LOOP_EXIT, NOT_TAKEN);
+ continue;
+ }
+
+ FOR_EACH_EDGE (e1, ei, e->src->preds)
+ if (!predicted_by_p (exit_edge->src, PRED_LOOP_ITERATIONS_GUESSED)
+ && !predicted_by_p (exit_edge->src, PRED_LOOP_ITERATIONS)
+ && !predicted_by_p (exit_edge->src, PRED_LOOP_EXIT))
+ predict_edge_def (e1, PRED_LOOP_EXIT, NOT_TAKEN);
+ }
+}
+
/* Predict edge probabilities by exploiting loop structure. */
static void
@@ -1330,6 +1416,8 @@
int probability;
enum br_predictor predictor;
+ predict_extra_loop_exits (ex);
+
if (number_of_iterations_exit (loop, ex, &niter_desc, false))
niter = niter_desc.niter;
if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
