#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-scalar-evolution.h"
+#include "ipa-utils.h"
+#include "gimple-pretty-print.h"
/* Enum with reasons why a predictor is ignored. */
static void combine_predictions_for_insn (rtx_insn *, basic_block);
static void dump_prediction (FILE *, enum br_predictor, int, basic_block,
enum predictor_reason, edge);
-static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
-static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction);
+static void predict_paths_leading_to (basic_block, enum br_predictor,
+ enum prediction,
+ struct loop *in_loop = NULL);
+static void predict_paths_leading_to_edge (edge, enum br_predictor,
+ enum prediction,
+ struct loop *in_loop = NULL);
static bool can_predict_insn_p (const rtx_insn *);
/* Information we hold about each branch predictor.
int probability = INTVAL (XEXP (XEXP (note, 0), 1));
found = true;
- if (best_predictor > predictor)
+ if (best_predictor > predictor
+ && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
best_probability = probability, best_predictor = predictor;
d = (combined_probability * probability
use no_prediction heuristic, in case we did match, use either
first match or Dempster-Shaffer theory depending on the flags. */
- if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
+ if (best_predictor != END_PREDICTORS)
first_match = true;
if (!found)
combined_probability, bb);
else
{
- dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
- bb, !first_match ? REASON_NONE : REASON_IGNORED);
- dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
- bb, first_match ? REASON_NONE : REASON_IGNORED);
+ if (!first_match)
+ dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
+ bb, !first_match ? REASON_NONE : REASON_IGNORED);
+ else
+ dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
+ bb, first_match ? REASON_NONE : REASON_IGNORED);
}
if (first_match)
found = true;
/* First match heuristics would be widly confused if we predicted
both directions. */
- if (best_predictor > predictor)
+ if (best_predictor > predictor
+ && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
{
struct edge_prediction *pred2;
int prob = probability;
use no_prediction heuristic, in case we did match, use either
first match or Dempster-Shaffer theory depending on the flags. */
- if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
+ if (best_predictor != END_PREDICTORS)
first_match = true;
if (!found)
dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
else
{
- dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
- !first_match ? REASON_NONE : REASON_IGNORED);
- dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
- first_match ? REASON_NONE : REASON_IGNORED);
+ if (!first_match)
+ dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
+ !first_match ? REASON_NONE : REASON_IGNORED);
+ else
+ dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
+ first_match ? REASON_NONE : REASON_IGNORED);
}
if (first_match)
|| i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
|| i->ep_predictor == PRED_LOOP_ITERATIONS
|| i->ep_predictor == PRED_LOOP_EXIT
+ || i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
|| i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
return true;
return false;
predict_loops (void)
{
struct loop *loop;
+ basic_block bb;
+ hash_set <struct loop *> with_recursion(10);
+
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ gimple_stmt_iterator gsi;
+ tree decl;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ if (is_gimple_call (gsi_stmt (gsi))
+ && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
+ && recursive_call_p (current_function_decl, decl))
+ {
+ loop = bb->loop_father;
+ while (loop && !with_recursion.add (loop))
+ loop = loop_outer (loop);
+ }
+ }
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
tree loop_bound_var = NULL;
tree loop_iv_base = NULL;
gcond *stmt = NULL;
+ bool recursion = with_recursion.contains (loop);
exits = get_loop_exit_edges (loop);
FOR_EACH_VEC_ELT (exits, j, ex)
continue;
}
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
+ loop->num, recursion ? " (with recursion)":"", n_exits);
+ if (dump_file && (dump_flags & TDF_DETAILS)
+ && max_loop_iterations_int (loop) >= 0)
+ {
+ fprintf (dump_file,
+ "Loop %d iterates at most %i times.\n", loop->num,
+ (int)max_loop_iterations_int (loop));
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS)
+ && likely_max_loop_iterations_int (loop) >= 0)
+ {
+ fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
+ loop->num, (int)likely_max_loop_iterations_int (loop));
+ }
+
FOR_EACH_VEC_ELT (exits, j, ex)
{
tree niter = NULL;
/* Loop heuristics do not expect exit conditional to be inside
inner loop. We predict from innermost to outermost loop. */
if (predicted_by_loop_heuristics_p (ex->src))
- continue;
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Skipping exit %i->%i because "
+ "it is already predicted.\n",
+ ex->src->index, ex->dest->index);
+ continue;
+ }
predict_extra_loop_exits (ex);
if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
niter = niter_desc.niter;
if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
niter = loop_niter_by_eval (loop, ex);
+ if (dump_file && (dump_flags & TDF_DETAILS)
+ && TREE_CODE (niter) == INTEGER_CST)
+ {
+ fprintf (dump_file, "Exit %i->%i %d iterates ",
+ ex->src->index, ex->dest->index,
+ loop->num);
+ print_generic_expr (dump_file, niter, TDF_SLIM);
+ fprintf (dump_file, " times.\n");
+ }
if (TREE_CODE (niter) == INTEGER_CST)
{
RDIV (REG_BR_PROB_BASE,
REG_BR_PROB_BASE
- predictor_info
- [PRED_LOOP_EXIT].hitrate)))
+ [recursion
+ ? PRED_LOOP_EXIT_WITH_RECURSION
+ : PRED_LOOP_EXIT].hitrate)))
{
nitercst = nit.to_shwi ();
predictor = PRED_LOOP_ITERATIONS_MAX;
}
else
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Nothing known about exit %i->%i.\n",
+ ex->src->index, ex->dest->index);
+ continue;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
+ (int)nitercst, predictor_info[predictor].name);
+ /* If the prediction for number of iterations is zero, do not
+ predict the exit edges. */
+ if (nitercst == 0)
continue;
- gcc_checking_assert (nitercst);
probability = RDIV (REG_BR_PROB_BASE, nitercst);
predict_edge (ex, predictor, probability);
}
for (j = 0; j < loop->num_nodes; j++)
{
- int header_found = 0;
edge e;
edge_iterator ei;
in the source language and are better to be handled
separately. */
if (predicted_by_p (bb, PRED_CONTINUE))
- continue;
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "BB %i predicted by continue.\n",
+ bb->index);
+ continue;
+ }
- /* Loop exit heuristics - predict an edge exiting the loop if the
- conditional has no loop header successors as not taken. */
- if (!header_found
- /* If we already used more reliable loop exit predictors, do not
- bother with PRED_LOOP_EXIT. */
- && !predicted_by_loop_heuristics_p (bb))
+ /* If we already used more reliable loop exit predictors, do not
+ bother with PRED_LOOP_EXIT. */
+ if (!predicted_by_loop_heuristics_p (bb))
{
/* For loop with many exits we don't want to predict all exits
with the pretty large probability, because if all exits are
a wide loop. */
int probability = ((REG_BR_PROB_BASE
- - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
+ - predictor_info
+ [recursion
+ ? PRED_LOOP_EXIT_WITH_RECURSION
+ : PRED_LOOP_EXIT].hitrate)
/ n_exits);
if (probability < HITRATE (2))
probability = HITRATE (2);
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest->index < NUM_FIXED_BLOCKS
|| !flow_bb_inside_loop_p (loop, e->dest))
- predict_edge (e, PRED_LOOP_EXIT, probability);
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Predicting exit %i->%i with prob %i.\n",
+ e->src->index, e->dest->index, probability);
+ predict_edge (e,
+ recursion ? PRED_LOOP_EXIT_WITH_RECURSION
+ : PRED_LOOP_EXIT, probability);
+ }
}
if (loop_bound_var)
predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
tree_to_shwi (loop_bound_step));
}
+ /* In the following code
+ for (loop1)
+ if (cond)
+ for (loop2)
+ body;
+ guess that cond is unlikely. */
+ if (loop_outer (loop)->num)
+ {
+ basic_block bb = NULL;
+ edge preheader_edge = loop_preheader_edge (loop);
+
+ if (single_pred_p (preheader_edge->src)
+ && single_succ_p (preheader_edge->src))
+ preheader_edge = single_pred_edge (preheader_edge->src);
+
+ gimple *stmt = last_stmt (preheader_edge->src);
+ /* Pattern match fortran loop preheader:
+ _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
+ _17 = (logical(kind=4)) _16;
+ if (_17 != 0)
+ goto <bb 11>;
+ else
+ goto <bb 13>;
+
+ Loop guard branch prediction says nothing about duplicated loop
+ headers produced by fortran frontend and in this case we want
+ to predict paths leading to this preheader. */
+
+ if (stmt
+ && gimple_code (stmt) == GIMPLE_COND
+ && gimple_cond_code (stmt) == NE_EXPR
+ && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
+ && integer_zerop (gimple_cond_rhs (stmt)))
+ {
+ gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
+ if (gimple_code (call_stmt) == GIMPLE_ASSIGN
+ && gimple_expr_code (call_stmt) == NOP_EXPR
+ && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
+ call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
+ if (gimple_code (call_stmt) == GIMPLE_CALL
+ && gimple_call_internal_p (call_stmt)
+ && gimple_call_internal_fn (call_stmt) == IFN_BUILTIN_EXPECT
+ && TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
+ && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
+ && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
+ == PRED_FORTRAN_LOOP_PREHEADER)
+ bb = preheader_edge->src;
+ }
+ if (!bb)
+ {
+ if (!dominated_by_p (CDI_DOMINATORS,
+ loop_outer (loop)->latch, loop->header))
+ predict_paths_leading_to_edge (loop_preheader_edge (loop),
+ recursion
+ ? PRED_LOOP_GUARD_WITH_RECURSION
+ : PRED_LOOP_GUARD,
+ NOT_TAKEN,
+ loop_outer (loop));
+ }
+ else
+ {
+ if (!dominated_by_p (CDI_DOMINATORS,
+ loop_outer (loop)->latch, bb))
+ predict_paths_leading_to (bb,
+ recursion
+ ? PRED_LOOP_GUARD_WITH_RECURSION
+ : PRED_LOOP_GUARD,
+ NOT_TAKEN,
+ loop_outer (loop));
+ }
+ }
+
/* Free basic blocks from get_loop_body. */
free (bbs);
}
predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
}
else
- predict_edge (then_edge, predictor,
- integer_zerop (val) ? NOT_TAKEN : TAKEN);
+ predict_edge_def (then_edge, predictor,
+ integer_zerop (val) ? NOT_TAKEN : TAKEN);
}
/* Try "pointer heuristic."
A comparison ptr == 0 is predicted as false.
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)
{
{
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))
predict_paths_for_bb (basic_block cur, basic_block bb,
enum br_predictor pred,
enum prediction taken,
- bitmap visited)
+ bitmap visited, struct loop *in_loop = NULL)
{
edge e;
edge_iterator ei;
basic_block son;
+ /* If we exited the loop or CUR is unconditional in the loop, there is
+ nothing to do. */
+ if (in_loop
+ && (!flow_bb_inside_loop_p (in_loop, cur)
+ || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
+ return;
+
/* We are looking for all edges forming edge cut induced by
set of all blocks postdominated by BB. */
FOR_EACH_EDGE (e, ei, cur->preds)
gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
/* See if there is an edge from e->src that is not abnormal
- and does not lead to BB. */
+ and does not lead to BB and does not exit the loop. */
FOR_EACH_EDGE (e2, ei2, e->src->succs)
if (e2 != e
&& !(e2->flags & (EDGE_EH | EDGE_FAKE))
- && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
+ && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
+ && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
{
found = true;
break;
predict_edge_def (e, pred, taken);
}
else if (bitmap_set_bit (visited, e->src->index))
- predict_paths_for_bb (e->src, e->src, pred, taken, visited);
+ predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
}
for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
son;
son = next_dom_son (CDI_POST_DOMINATORS, son))
- predict_paths_for_bb (son, bb, pred, taken, visited);
+ predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
}
/* Sets branch probabilities according to PREDiction and
static void
predict_paths_leading_to (basic_block bb, enum br_predictor pred,
- enum prediction taken)
+ enum prediction taken, struct loop *in_loop)
{
bitmap visited = BITMAP_ALLOC (NULL);
- predict_paths_for_bb (bb, bb, pred, taken, visited);
+ predict_paths_for_bb (bb, bb, pred, taken, visited, in_loop);
BITMAP_FREE (visited);
}
static void
predict_paths_leading_to_edge (edge e, enum br_predictor pred,
- enum prediction taken)
+ enum prediction taken, struct loop *in_loop)
{
bool has_nonloop_edge = false;
edge_iterator ei;
if (!has_nonloop_edge)
{
bitmap visited = BITMAP_ALLOC (NULL);
- predict_paths_for_bb (bb, bb, pred, taken, visited);
+ predict_paths_for_bb (bb, bb, pred, taken, visited, in_loop);
BITMAP_FREE (visited);
}
else
gimple_dump_cfg (dump_file, dump_flags);
if (profile_status_for_fn (fun) == PROFILE_ABSENT)
profile_status_for_fn (fun) = PROFILE_GUESSED;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ struct loop *loop;
+ FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
+ if (loop->header->frequency)
+ fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
+ loop->num,
+ (int)expected_loop_iterations_unbounded (loop));
+ }
return 0;
}
fprintf (dump_file, "Making edge %i->%i %s by redistributing "
"probability to other edges.\n",
e->src->index, e->dest->index,
- impossible ? "imposisble" : "cold");
+ impossible ? "impossible" : "cold");
FOR_EACH_EDGE (e2, ei, e->src->succs)
if (e2 != e)
{
int old_frequency = e->src->frequency;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
- impossible ? "imposisble" : "cold");
+ impossible ? "impossible" : "cold");
e->src->frequency = MIN (e->src->frequency, impossible ? 0 : 1);
e->src->count = e->count = RDIV (e->src->count * e->src->frequency,
old_frequency);
else if (dump_file && (dump_flags & TDF_DETAILS)
&& maybe_hot_bb_p (cfun, e->src))
fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
- impossible ? "imposisble" : "cold");
+ impossible ? "impossible" : "cold");
}
}
projects / platform / upstream / gcc.git / blobdiff