return false;
}
+/* Return true when the probability of edge is reliable.
+
+ The profile guessing code is good at predicting branch outcome (ie.
+ taken/not taken), that is predicted right slightly over 75% of time.
+ It is however notoriously poor on predicting the probability itself.
+ In general the profile appear a lot flatter (with probabilities closer
+ to 50%) than the reality so it is bad idea to use it to drive optimization
+ such as those disabling dynamic branch prediction for well predictable
+ branches.
+
+ There are two exceptions - edges leading to noreturn edges and edges
+ predicted by number of iterations heuristics are predicted well. This macro
+ should be able to distinguish those, but at the moment it simply check for
+ noreturn heuristic that is only one giving probability over 99% or bellow
+ 1%. In future we might want to propagate reliability information across the
+ CFG if we find this information useful on multiple places. */
+static bool
+probability_reliable_p (int prob)
+{
+ return (profile_status == PROFILE_READ
+ || (profile_status == PROFILE_GUESSED
+ && (prob <= HITRATE (1) || prob >= HITRATE (99))));
+}
+
+/* Same predicate as above, working on edges. */
+bool
+edge_probability_reliable_p (edge e)
+{
+ return probability_reliable_p (e->probability);
+}
+
+/* Same predicate as edge_probability_reliable_p, working on notes. */
+bool
+br_prob_note_reliable_p (rtx note)
+{
+ gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
+ return probability_reliable_p (INTVAL (XEXP (note, 0)));
+}
+
static void
predict_insn (rtx insn, enum br_predictor predictor, int probability)
{
Remove now useless prediction entries. */
static void
-combine_predictions_for_bb (FILE *file, basic_block bb)
+combine_predictions_for_bb (basic_block bb)
{
int best_probability = PROB_EVEN;
int best_predictor = END_PREDICTORS;
if (!bb->count)
set_even_probabilities (bb);
bb->predictions = NULL;
- if (file)
- fprintf (file, "%i edges in bb %i predicted to even probabilities\n",
+ if (dump_file)
+ fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
nedges, bb->index);
return;
}
- if (file)
- fprintf (file, "Predictions for bb %i\n", bb->index);
+ if (dump_file)
+ fprintf (dump_file, "Predictions for bb %i\n", bb->index);
/* We implement "first match" heuristics and use probability guessed
by predictor with smallest index. */
first_match = true;
if (!found)
- dump_prediction (file, PRED_NO_PREDICTION, combined_probability, bb, true);
+ dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
else
{
- dump_prediction (file, PRED_DS_THEORY, combined_probability, bb,
+ dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
!first_match);
- dump_prediction (file, PRED_FIRST_MATCH, best_probability, bb,
+ dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
first_match);
}
if (first_match)
combined_probability = best_probability;
- dump_prediction (file, PRED_COMBINED, combined_probability, bb, true);
+ dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
for (pred = bb->predictions; pred; pred = pred->ep_next)
{
if (pred->ep_edge != EDGE_SUCC (bb, 0))
probability = REG_BR_PROB_BASE - probability;
- dump_prediction (file, predictor, probability, bb,
+ dump_prediction (dump_file, predictor, probability, bb,
!first_match || best_predictor == predictor);
}
bb->predictions = NULL;
/* Loop exit heuristics - predict an edge exiting the loop if the
conditional has no loop header successors as not taken. */
if (!header_found)
- 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,
- (REG_BR_PROB_BASE
- - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
- / n_exits);
+ {
+ /* For loop with many exits we don't want to predict all exits
+ with the pretty large probability, because if all exits are
+ considered in row, the loop would be predicted to iterate
+ almost never. The code to divide probability by number of
+ exits is very rough. It should compute the number of exits
+ taken in each patch through function (not the overall number
+ of exits that might be a lot higher for loops with wide switch
+ statements in them) and compute n-th square root.
+
+ We limit the minimal probability by 2% to avoid
+ EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
+ as this was causing regression in perl benchmark containing such
+ a wide loop. */
+
+ int probability = ((REG_BR_PROB_BASE
+ - predictor_info [(int) 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);
+ }
}
/* Free basic blocks from get_loop_body. */
}
}
-/* Statically estimate the probability that a branch will be taken and produce
- estimated profile. When profile feedback is present never executed portions
- of function gets estimated. */
-
-void
-estimate_probability (struct loops *loops_info)
-{
- basic_block bb;
-
- connect_infinite_loops_to_exit ();
- calculate_dominance_info (CDI_DOMINATORS);
- calculate_dominance_info (CDI_POST_DOMINATORS);
-
- predict_loops (loops_info, true);
-
- iv_analysis_done ();
-
- /* Attempt to predict conditional jumps using a number of heuristics. */
- FOR_EACH_BB (bb)
- {
- rtx last_insn = BB_END (bb);
- edge e;
- edge_iterator ei;
-
- if (! can_predict_insn_p (last_insn))
- continue;
-
- FOR_EACH_EDGE (e, ei, bb->succs)
- {
- /* Predict early returns to be probable, as we've already taken
- care for error returns and other are often used for fast paths
- trought function. */
- if ((e->dest == EXIT_BLOCK_PTR
- || (single_succ_p (e->dest)
- && single_succ (e->dest) == EXIT_BLOCK_PTR))
- && !predicted_by_p (bb, PRED_NULL_RETURN)
- && !predicted_by_p (bb, PRED_CONST_RETURN)
- && !predicted_by_p (bb, PRED_NEGATIVE_RETURN)
- && !last_basic_block_p (e->dest))
- predict_edge_def (e, PRED_EARLY_RETURN, TAKEN);
-
- /* Look for block we are guarding (i.e. we dominate it,
- but it doesn't postdominate us). */
- if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
- && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
- && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
- {
- rtx insn;
-
- /* The call heuristic claims that a guarded function call
- is improbable. This is because such calls are often used
- to signal exceptional situations such as printing error
- messages. */
- for (insn = BB_HEAD (e->dest); insn != NEXT_INSN (BB_END (e->dest));
- insn = NEXT_INSN (insn))
- if (CALL_P (insn)
- /* Constant and pure calls are hardly used to signalize
- something exceptional. */
- && ! CONST_OR_PURE_CALL_P (insn))
- {
- predict_edge_def (e, PRED_CALL, NOT_TAKEN);
- break;
- }
- }
- }
- bb_estimate_probability_locally (bb);
- }
-
- /* Attach the combined probability to each conditional jump. */
- FOR_EACH_BB (bb)
- combine_predictions_for_insn (BB_END (bb), bb);
-
- remove_fake_edges ();
- estimate_bb_frequencies (loops_info);
- free_dominance_info (CDI_POST_DOMINATORS);
- if (profile_status == PROFILE_ABSENT)
- profile_status = PROFILE_GUESSED;
-}
-
/* Set edge->probability for each successor edge of BB. */
void
guess_outgoing_edge_probabilities (basic_block bb)
basic_block bb;
int *heads;
- heads = xmalloc (sizeof (int) * last_basic_block);
+ heads = XNEWVEC (int, last_basic_block);
memset (heads, ENTRY_BLOCK, sizeof (int) * last_basic_block);
heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
}
/* Predict branch probabilities and estimate profile of the tree CFG. */
-static void
+static unsigned int
tree_estimate_probability (void)
{
basic_block bb;
{
/* Predict early returns to be probable, as we've already taken
care for error returns and other cases are often used for
- fast paths trought function. */
+ fast paths through function. */
if (e->dest == EXIT_BLOCK_PTR
&& TREE_CODE (last_stmt (bb)) == RETURN_EXPR
&& !single_pred_p (bb))
tree_predict_by_opcode (bb);
}
FOR_EACH_BB (bb)
- combine_predictions_for_bb (dump_file, bb);
+ combine_predictions_for_bb (bb);
- if (!flag_loop_optimize)
- strip_builtin_expect ();
+ strip_builtin_expect ();
estimate_bb_frequencies (&loops_info);
free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_exit_edges ();
dump_tree_cfg (dump_file, dump_flags);
if (profile_status == PROFILE_ABSENT)
profile_status = PROFILE_GUESSED;
+ return 0;
}
\f
/* __builtin_expect dropped tokens into the insn stream describing expected
OSDN Git Service
