Re: Predict for loop exits in short-circuit conditions

[Dehao Chen <dehao at google dot com>]

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)