X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=gcc%2Fpredict.c;h=01f5cfcf9e1f52509b7717517100fbd063daeaea;hb=9bb86f403f3085d0d9b344127f7603d4559370a5;hp=7d55ff7c71c7822a0b1dab4b14d51f50fa62751e;hpb=46c1cff63f942e715c53739610951ea58ab8c228;p=platform%2Fupstream%2Fgcc.git diff --git a/gcc/predict.c b/gcc/predict.c index 7d55ff7..01f5cfc 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -54,6 +54,8 @@ along with GCC; see the file COPYING3. If not see #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. */ @@ -78,8 +80,12 @@ static sreal real_almost_one, real_br_prob_base, 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. @@ -835,7 +841,8 @@ combine_predictions_for_insn (rtx_insn *insn, basic_block bb) 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 @@ -855,7 +862,7 @@ combine_predictions_for_insn (rtx_insn *insn, basic_block bb) 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) @@ -863,10 +870,12 @@ combine_predictions_for_insn (rtx_insn *insn, basic_block bb) 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) @@ -1096,7 +1105,8 @@ combine_predictions_for_bb (basic_block bb, bool dry_run) 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; @@ -1142,17 +1152,19 @@ combine_predictions_for_bb (basic_block bb, bool dry_run) 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) @@ -1396,6 +1408,7 @@ predicted_by_loop_heuristics_p (basic_block bb) || 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; @@ -1675,6 +1688,24 @@ static void predict_loops (void) { struct loop *loop; + basic_block bb; + hash_set 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. */ @@ -1691,6 +1722,7 @@ predict_loops (void) 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) @@ -1702,6 +1734,23 @@ predict_loops (void) 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; @@ -1716,13 +1765,28 @@ predict_loops (void) /* 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) { @@ -1755,15 +1819,29 @@ predict_loops (void) 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); } @@ -1792,7 +1870,6 @@ predict_loops (void) for (j = 0; j < loop->num_nodes; j++) { - int header_found = 0; edge e; edge_iterator ei; @@ -1803,14 +1880,16 @@ predict_loops (void) 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 @@ -1827,14 +1906,25 @@ predict_loops (void) 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, @@ -1842,6 +1932,78 @@ predict_loops (void) 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 ; + else + goto ; + + 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); } @@ -2192,8 +2354,8 @@ tree_predict_by_opcode (basic_block bb) 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. @@ -2415,6 +2577,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) { @@ -2529,6 +2694,7 @@ tree_estimate_probability_bb (basic_block bb) { gimple *stmt = gsi_stmt (bi); if (is_gimple_call (stmt) + && !gimple_inexpensive_call_p (as_a (stmt)) /* Constant and pure calls are hardly used to signalize something exceptional. */ && gimple_has_side_effects (stmt)) @@ -2591,12 +2757,19 @@ static void 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) @@ -2613,11 +2786,12 @@ predict_paths_for_bb (basic_block cur, basic_block bb, 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; @@ -2636,12 +2810,12 @@ predict_paths_for_bb (basic_block cur, basic_block bb, 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 @@ -2649,10 +2823,10 @@ predict_paths_for_bb (basic_block cur, basic_block bb, 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); } @@ -2660,7 +2834,7 @@ predict_paths_leading_to (basic_block bb, enum br_predictor pred, 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; @@ -2678,7 +2852,7 @@ predict_paths_leading_to_edge (edge e, enum br_predictor pred, 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 @@ -3272,6 +3446,15 @@ pass_profile::execute (function *fun) 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; } @@ -3501,7 +3684,7 @@ force_edge_cold (edge e, bool impossible) 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) { @@ -3527,7 +3710,7 @@ force_edge_cold (edge e, bool impossible) 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); @@ -3536,6 +3719,6 @@ force_edge_cold (edge e, bool impossible) 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"); } }