This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Separate loop exit predictor from extra exit predictor
- From: Jan Hubicka <hubicka at ucw dot cz>
- To: gcc-patches at gcc dot gnu dot org, mliska at suse dot cz, law at redhat dot com
- Date: Wed, 1 Jun 2016 01:37:18 +0200
- Subject: Separate loop exit predictor from extra exit predictor
- Authentication-results: sourceware.org; auth=none
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"} } */