This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Separate loop exit predictor from extra exit predictor


Hi,
predict_extra_loop_exits contains poor man's jump threading code for loop exit conditionals
pattern matching the following:
   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...

Here loop exit heuristics will predict "if iftmp == 1" as unlikely but that
will be later jump threaded and result in inconsistent profile.

This patch just makes this predictor to be separate from loop exit predictor
as they are two different things. This way we get different estimates about
effectivity. 

Ideally we should jump thread this before profile is built.

Bootstrappd/regtested x86_64-linux, comitted.

Honza
	* g++.d/predict-loop-exit-1.C: Update template for new predictor name.
	* g++.d/predict-loop-exit-2.C: Update template for new predictor name.
	* g++.d/predict-loop-exit-3.C: Update template for new predictor name.

	* predict.def (PRED_LOOP_EXTRA_EXIT): Define.
	* predict.c (predict_iv_comparison): Also check PRED_LOOP_EXTRA_EXIT.
	(predict_extra_loop_exits): Use PRED_LOOP_EXTRA_EXIT instead of
	PRED_LOOP_EXIT.
Index: predict.def
===================================================================
--- predict.def	(revision 236965)
+++ predict.def	(working copy)
@@ -92,6 +92,11 @@ DEF_PREDICTOR (PRED_LOOP_BRANCH, "loop b
 DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", HITRATE (91),
 	       PRED_FLAG_FIRST_MATCH)
 
+/* Edge causing loop to terminate by computing value used by later conditional.
+   */
+DEF_PREDICTOR (PRED_LOOP_EXTRA_EXIT, "extra loop exit", HITRATE (91),
+	       PRED_FLAG_FIRST_MATCH)
+
 /* Pointers are usually not NULL.  */
 DEF_PREDICTOR (PRED_POINTER, "pointer", HITRATE (85), 0)
 DEF_PREDICTOR (PRED_TREE_POINTER, "pointer (on trees)", HITRATE (85), 0)
Index: predict.c
===================================================================
--- predict.c	(revision 236965)
+++ predict.c	(working copy)
@@ -1245,7 +1245,8 @@ predict_iv_comparison (struct loop *loop
 
   if (predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
       || predicted_by_p (bb, PRED_LOOP_ITERATIONS)
-      || predicted_by_p (bb, PRED_LOOP_EXIT))
+      || predicted_by_p (bb, PRED_LOOP_EXIT)
+      || predicted_by_p (bb, PRED_LOOP_EXTRA_EXIT))
     return;
 
   stmt = last_stmt (bb);
@@ -1418,7 +1419,7 @@ predict_iv_comparison (struct loop *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.  */
+   exits to predict them using PRED_LOOP_EXTRA_EXIT.  */
 
 static void
 predict_extra_loop_exits (edge exit_edge)
@@ -1474,12 +1475,12 @@ predict_extra_loop_exits (edge exit_edge
 	continue;
       if (EDGE_COUNT (e->src->succs) != 1)
 	{
-	  predict_paths_leading_to_edge (e, PRED_LOOP_EXIT, NOT_TAKEN);
+	  predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
 	  continue;
 	}
 
       FOR_EACH_EDGE (e1, ei, e->src->preds)
-	predict_paths_leading_to_edge (e1, PRED_LOOP_EXIT, NOT_TAKEN);
+	predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
     }
 }
 
Index: testsuite/g++.dg/predict-loop-exit-1.C
===================================================================
--- testsuite/g++.dg/predict-loop-exit-1.C	(revision 236965)
+++ testsuite/g++.dg/predict-loop-exit-1.C	(working copy)
@@ -9,4 +9,5 @@ void test() {
   return;
 }
 
+/* { dg-final { scan-tree-dump-times "extra loop exit heuristics:" 2 "profile_estimate"} } */
 /* { dg-final { scan-tree-dump-times "loop exit heuristics:" 3 "profile_estimate"} } */
Index: testsuite/g++.dg/predict-loop-exit-2.C
===================================================================
--- testsuite/g++.dg/predict-loop-exit-2.C	(revision 236965)
+++ testsuite/g++.dg/predict-loop-exit-2.C	(working copy)
@@ -9,4 +9,5 @@ void test() {
   return;
 }
 
+/* { dg-final { scan-tree-dump-times "extra loop exit heuristics:" 1 "profile_estimate"} } */
 /* { dg-final { scan-tree-dump-times "loop exit heuristics:" 2 "profile_estimate"} } */
Index: testsuite/g++.dg/predict-loop-exit-3.C
===================================================================
--- testsuite/g++.dg/predict-loop-exit-3.C	(revision 236965)
+++ testsuite/g++.dg/predict-loop-exit-3.C	(working copy)
@@ -9,4 +9,5 @@ void test() {
   return;
 }
 
+/* { dg-final { scan-tree-dump-times "extra loop exit heuristics:" 2 "profile_estimate"} } */
 /* { dg-final { scan-tree-dump-times "loop exit heuristics:" 3 "profile_estimate"} } */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]