Hi,
this is first of two patches for getting more realistic predictions of
recursive functions. It is clear that in order for recursion to finish, the
sum of frequencies of recursive calls should not exceed sum of frequencies of
the function entry block. This global condition is however bit hard to achieve
by local predictors.
This predictor simply predicts paths leading to the recursive call as not taken
by 75%. This of course is not perfect as the path is predicted on the last
possible conditional that is often not the one bypassing the call, especially
when call is within a loop (that is a common pattern or backrack).
I will handle that in followup patch.
Other case is when there are multiple recursive calls which I don't see how
to handle elegantly, so I don't do anything about it - dropping probability
to 75% for them is still an improvement.
Bootstrapped/regtested x86_64-linux,
will commit it shortly.
Honza
* predict.c: Include ipa-utils.h
(tree_bb_level_prediction): Predict recursive calls.
(tree_estimate_probability_bb): Skip inexpensive calls for call
predictor.
* predict.def (PRED_RECURSIVE_CALL): New.
* gcc.dg/predict-10.c: New test.
Index: predict.c
===================================================================
--- predict.c (revision 237779)
+++ predict.c (working copy)
@@ -54,6 +54,7 @@ along with GCC; see the file COPYING3.
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-scalar-evolution.h"
+#include "ipa-utils.h"
/* Enum with reasons why a predictor is ignored. */
@@ -2425,6 +2426,9 @@ tree_bb_level_predictions (void)
DECL_ATTRIBUTES (decl)))
predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
NOT_TAKEN);
+ if (decl && recursive_call_p (current_function_decl, decl))
+ predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
+ NOT_TAKEN);
}
else if (gimple_code (stmt) == GIMPLE_PREDICT)
{
@@ -2539,6 +2543,7 @@ tree_estimate_probability_bb (basic_bloc
{
gimple *stmt = gsi_stmt (bi);
if (is_gimple_call (stmt)
+ && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
/* Constant and pure calls are hardly used to signalize
something exceptional. */
&& gimple_has_side_effects (stmt))
Index: predict.def
===================================================================
--- predict.def (revision 237779)
+++ predict.def (working copy)
@@ -112,6 +112,9 @@ DEF_PREDICTOR (PRED_TREE_FPOPCODE, "fp_o
/* Branch guarding call is probably taken. */
DEF_PREDICTOR (PRED_CALL, "call", HITRATE (67), 0)
+/* Recursive calls are usually not taken or the function will recurse
indefinitely. */
+DEF_PREDICTOR (PRED_RECURSIVE_CALL, "recursive call", HITRATE (75), 0)
+
/* Branch causing function to terminate is probably not taken.
FIXME: early return currently predicts code:
int foo (int a)
Index: testsuite/gcc.dg/predict-10.c
===================================================================
--- testsuite/gcc.dg/predict-10.c (revision 0)
+++ testsuite/gcc.dg/predict-10.c (working copy)
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-profile_estimate" } */
+int
+ee(int i)
+{
+ if (i>2)
+ return (ee(i-1)+ee(i-2))/2;
+ else
+ return i;
+}
+/* { dg-final { scan-tree-dump-times "recursive call" 1 "profile_estimate"} }
*/
