/* Branch prediction routines for the GNU compiler.
- Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007
+ Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008
Free Software Foundation, Inc.
This file is part of GCC.
static void combine_predictions_for_insn (rtx, basic_block);
static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
-static void predict_paths_leading_to (basic_block, int *, enum br_predictor, enum prediction);
+static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
static void compute_function_frequency (void);
static void choose_function_section (void);
static bool can_predict_insn_p (const_rtx);
};
#undef DEF_PREDICTOR
+/* Return TRUE if frequency FREQ is considered to be hot. */
+static bool
+maybe_hot_frequency_p (int freq)
+{
+ if (!profile_info || !flag_branch_probabilities)
+ {
+ if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
+ return false;
+ if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
+ return true;
+ }
+ if (freq < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
+ return false;
+ return true;
+}
+
/* Return true in case BB can be CPU intensive and should be optimized
for maximal performance. */
&& (bb->count
< profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
return false;
- if (!profile_info || !flag_branch_probabilities)
- {
- if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
- return false;
- if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
- return true;
- }
- if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
+ return maybe_hot_frequency_p (bb->frequency);
+}
+
+/* Return true in case BB can be CPU intensive and should be optimized
+ for maximal performance. */
+
+bool
+maybe_hot_edge_p (edge e)
+{
+ if (profile_info && flag_branch_probabilities
+ && (e->count
+ < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
return false;
- return true;
+ return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
}
/* Return true in case BB is cold and should be optimized for size. */
/* Find the basic block with return expression and look up for possible
return value trying to apply RETURN_PREDICTION heuristics. */
static void
-apply_return_prediction (int *heads)
+apply_return_prediction (void)
{
tree return_stmt = NULL;
tree return_val;
{
pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
if (pred != PRED_NO_PREDICTION)
- predict_paths_leading_to (PHI_ARG_EDGE (phi, i)->src, heads, pred,
+ predict_paths_leading_to (PHI_ARG_EDGE (phi, i)->src, pred,
direction);
}
}
tree_bb_level_predictions (void)
{
basic_block bb;
- int *heads;
-
- heads = XCNEWVEC (int, last_basic_block);
- heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
- apply_return_prediction (heads);
+ apply_return_prediction ();
FOR_EACH_BB (bb)
{
block_stmt_iterator bsi = bsi_last (bb);
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi);)
{
tree stmt = bsi_stmt (bsi);
tree decl;
+ bool next = false;
+
switch (TREE_CODE (stmt))
{
case GIMPLE_MODIFY_STMT:
case CALL_EXPR:
call_expr:;
if (call_expr_flags (stmt) & ECF_NORETURN)
- predict_paths_leading_to (bb, heads, PRED_NORETURN,
+ predict_paths_leading_to (bb, PRED_NORETURN,
NOT_TAKEN);
decl = get_callee_fndecl (stmt);
if (decl
&& lookup_attribute ("cold",
DECL_ATTRIBUTES (decl)))
- predict_paths_leading_to (bb, heads, PRED_COLD_FUNCTION,
+ predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
NOT_TAKEN);
break;
+ case PREDICT_EXPR:
+ predict_paths_leading_to (bb, PREDICT_EXPR_PREDICTOR (stmt),
+ PREDICT_EXPR_OUTCOME (stmt));
+ bsi_remove (&bsi, true);
+ next = true;
+ break;
default:
break;
}
+ if (!next)
+ bsi_next (&bsi);
}
}
-
- free (heads);
}
#ifdef ENABLE_CHECKING
return 0;
}
\f
-/* Sets branch probabilities according to PREDiction and
- FLAGS. HEADS[bb->index] should be index of basic block in that we
- need to alter branch predictions (i.e. the first of our dominators
- such that we do not post-dominate it) (but we fill this information
- on demand, so -1 may be there in case this was not needed yet). */
+/* Predict edges to successors of CUR whose sources are not postdominated by
+ BB by PRED and recurse to all postdominators. */
static void
-predict_paths_leading_to (basic_block bb, int *heads, enum br_predictor pred,
- enum prediction taken)
+predict_paths_for_bb (basic_block cur, basic_block bb,
+ enum br_predictor pred,
+ enum prediction taken)
{
edge e;
edge_iterator ei;
- int y;
+ basic_block son;
- if (heads[bb->index] == ENTRY_BLOCK)
+ /* 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)
+ if (e->src->index >= NUM_FIXED_BLOCKS
+ && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
{
- /* This is first time we need this field in heads array; so
- find first dominator that we do not post-dominate (we are
- using already known members of heads array). */
- basic_block ai = bb;
- basic_block next_ai = get_immediate_dominator (CDI_DOMINATORS, bb);
- int head;
-
- while (heads[next_ai->index] == ENTRY_BLOCK)
- {
- if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
- break;
- heads[next_ai->index] = ai->index;
- ai = next_ai;
- next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai);
- }
- if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
- head = next_ai->index;
- else
- head = heads[next_ai->index];
- while (next_ai != bb)
- {
- next_ai = ai;
- ai = BASIC_BLOCK (heads[ai->index]);
- heads[next_ai->index] = head;
- }
+ gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
+ predict_edge_def (e, pred, taken);
}
- y = heads[bb->index];
+ 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);
+}
- /* Now find the edge that leads to our branch and aply the prediction. */
+/* Sets branch probabilities according to PREDiction and
+ FLAGS. */
- if (y == last_basic_block)
- return;
- FOR_EACH_EDGE (e, ei, BASIC_BLOCK (y)->succs)
- if (e->dest->index >= NUM_FIXED_BLOCKS
- && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb))
- predict_edge_def (e, pred, taken);
+static void
+predict_paths_leading_to (basic_block bb, enum br_predictor pred,
+ enum prediction taken)
+{
+ predict_paths_for_bb (bb, bb, pred, taken);
}
\f
/* This is used to carry information about basic blocks. It is
return flag_guess_branch_prob;
}
-struct tree_opt_pass pass_profile =
+/* Build PREDICT_EXPR. */
+tree
+build_predict_expr (enum br_predictor predictor, enum prediction taken)
+{
+ tree t = build1 (PREDICT_EXPR, NULL_TREE, build_int_cst (NULL, predictor));
+ PREDICT_EXPR_OUTCOME (t) = taken;
+ return t;
+}
+
+const char *
+predictor_name (enum br_predictor predictor)
+{
+ return predictor_info[predictor].name;
+}
+
+struct gimple_opt_pass pass_profile =
{
+ {
+ GIMPLE_PASS,
"profile", /* name */
gate_estimate_probability, /* gate */
tree_estimate_probability, /* execute */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
- 0 /* letter */
+ TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
+ }
};