/* Branch prediction routines for the GNU compiler.
- Copyright (C) 2000-2015 Free Software Foundation, Inc.
+ Copyright (C) 2000-2018 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "backend.h"
-#include "cfghooks.h"
+#include "rtl.h"
#include "tree.h"
#include "gimple.h"
-#include "gimple-predict.h"
-#include "rtl.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
#include "ssa.h"
-#include "alias.h"
+#include "memmodel.h"
+#include "emit-rtl.h"
+#include "cgraph.h"
+#include "coverage.h"
+#include "diagnostic-core.h"
+#include "gimple-predict.h"
#include "fold-const.h"
#include "calls.h"
-#include "tm_p.h"
#include "cfganal.h"
-#include "insn-config.h"
-#include "regs.h"
-#include "flags.h"
#include "profile.h"
-#include "except.h"
-#include "diagnostic-core.h"
-#include "recog.h"
-#include "expmed.h"
-#include "dojump.h"
-#include "explow.h"
-#include "emit-rtl.h"
-#include "varasm.h"
-#include "stmt.h"
-#include "expr.h"
-#include "coverage.h"
#include "sreal.h"
#include "params.h"
-#include "target.h"
#include "cfgloop.h"
-#include "internal-fn.h"
#include "gimple-iterator.h"
-#include "cgraph.h"
#include "tree-cfg.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
-#include "tree-pass.h"
#include "tree-scalar-evolution.h"
+#include "ipa-utils.h"
+#include "gimple-pretty-print.h"
+#include "selftest.h"
+#include "cfgrtl.h"
+#include "stringpool.h"
+#include "attribs.h"
+
+/* Enum with reasons why a predictor is ignored. */
+
+enum predictor_reason
+{
+ REASON_NONE,
+ REASON_IGNORED,
+ REASON_SINGLE_EDGE_DUPLICATE,
+ REASON_EDGE_PAIR_DUPLICATE
+};
+
+/* String messages for the aforementioned enum. */
+
+static const char *reason_messages[] = {"", " (ignored)",
+ " (single edge duplicate)", " (edge pair duplicate)"};
/* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
real_inv_br_prob_base, real_one_half, real_bb_freq_max;
static void combine_predictions_for_insn (rtx_insn *, basic_block);
-static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
-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 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,
+ 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.
};
#undef DEF_PREDICTOR
-/* Return TRUE if frequency FREQ is considered to be hot. */
-
-static inline bool
-maybe_hot_frequency_p (struct function *fun, int freq)
-{
- struct cgraph_node *node = cgraph_node::get (fun->decl);
- if (!profile_info
- || !opt_for_fn (fun->decl, flag_branch_probabilities))
- {
- if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
- return false;
- if (node->frequency == NODE_FREQUENCY_HOT)
- return true;
- }
- if (profile_status_for_fn (fun) == PROFILE_ABSENT)
- return true;
- if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
- && freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency * 2 / 3))
- return false;
- if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
- return false;
- if (freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency
- / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
- return false;
- return true;
-}
-
static gcov_type min_count = -1;
/* Determine the threshold for hot BB counts. */
/* Return TRUE if frequency FREQ is considered to be hot. */
bool
-maybe_hot_count_p (struct function *fun, gcov_type count)
+maybe_hot_count_p (struct function *fun, profile_count count)
{
- if (fun && profile_status_for_fn (fun) != PROFILE_READ)
+ if (!count.initialized_p ())
return true;
+ if (count.ipa () == profile_count::zero ())
+ return false;
+ if (!count.ipa_p ())
+ {
+ struct cgraph_node *node = cgraph_node::get (fun->decl);
+ if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
+ {
+ if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
+ return false;
+ if (node->frequency == NODE_FREQUENCY_HOT)
+ return true;
+ }
+ if (profile_status_for_fn (fun) == PROFILE_ABSENT)
+ return true;
+ if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
+ && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
+ return false;
+ if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
+ return false;
+ if (count.apply_scale (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION), 1)
+ < ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
+ return false;
+ return true;
+ }
/* Code executed at most once is not hot. */
- if (profile_info->runs >= count)
+ if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
return false;
- return (count >= get_hot_bb_threshold ());
+ return (count.to_gcov_type () >= get_hot_bb_threshold ());
}
/* Return true in case BB can be CPU intensive and should be optimized
maybe_hot_bb_p (struct function *fun, const_basic_block bb)
{
gcc_checking_assert (fun);
- if (profile_status_for_fn (fun) == PROFILE_READ)
- return maybe_hot_count_p (fun, bb->count);
- return maybe_hot_frequency_p (fun, bb->frequency);
+ return maybe_hot_count_p (fun, bb->count);
}
/* Return true in case BB can be CPU intensive and should be optimized
bool
maybe_hot_edge_p (edge e)
{
- if (profile_status_for_fn (cfun) == PROFILE_READ)
- return maybe_hot_count_p (cfun, e->count);
- return maybe_hot_frequency_p (cfun, EDGE_FREQUENCY (e));
+ return maybe_hot_count_p (cfun, e->count ());
}
/* Return true if profile COUNT and FREQUENCY, or function FUN static
static bool
probably_never_executed (struct function *fun,
- gcov_type count, int frequency)
+ profile_count count)
{
gcc_checking_assert (fun);
- if (profile_status_for_fn (fun) == PROFILE_READ)
+ if (count.ipa () == profile_count::zero ())
+ return true;
+ /* Do not trust adjusted counts. This will make us to drop int cold section
+ code with low execution count as a result of inlining. These low counts
+ are not safe even with read profile and may lead us to dropping
+ code which actually gets executed into cold section of binary that is not
+ desirable. */
+ if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
{
int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
- if (count * unlikely_count_fraction >= profile_info->runs)
- return false;
- if (!frequency)
- return true;
- if (!ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency)
+ if (count.apply_scale (unlikely_count_fraction, 1) >= profile_info->runs)
return false;
- if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
- {
- gcov_type computed_count;
- /* Check for possibility of overflow, in which case entry bb count
- is large enough to do the division first without losing much
- precision. */
- if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count < REG_BR_PROB_BASE *
- REG_BR_PROB_BASE)
- {
- gcov_type scaled_count
- = frequency * ENTRY_BLOCK_PTR_FOR_FN (fun)->count *
- unlikely_count_fraction;
- computed_count = RDIV (scaled_count,
- ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
- }
- else
- {
- computed_count = RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun)->count,
- ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
- computed_count *= frequency * unlikely_count_fraction;
- }
- if (computed_count >= profile_info->runs)
- return false;
- }
return true;
}
- if ((!profile_info || !(opt_for_fn (fun->decl, flag_branch_probabilities)))
+ if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
&& (cgraph_node::get (fun->decl)->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED))
return true;
bool
probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
{
- return probably_never_executed (fun, bb->count, bb->frequency);
+ return probably_never_executed (fun, bb->count);
}
+/* Return true if E is unlikely executed for obvious reasons. */
+
+static bool
+unlikely_executed_edge_p (edge e)
+{
+ return (e->count () == profile_count::zero ()
+ || e->probability == profile_probability::never ())
+ || (e->flags & (EDGE_EH | EDGE_FAKE));
+}
+
/* Return true in case edge E is probably never executed. */
bool
probably_never_executed_edge_p (struct function *fun, edge e)
{
- return probably_never_executed (fun, e->count, EDGE_FREQUENCY (e));
+ if (unlikely_executed_edge_p (e))
+ return true;
+ return probably_never_executed (fun, e->count ());
}
/* Return true when current function should always be optimized for size. */
return !optimize_function_for_size_p (fun);
}
+/* Return the optimization type that should be used for the function FUN. */
+
+optimization_type
+function_optimization_type (struct function *fun)
+{
+ return (optimize_function_for_speed_p (fun)
+ ? OPTIMIZE_FOR_SPEED
+ : OPTIMIZE_FOR_SIZE);
+}
+
/* Return TRUE when BB should be optimized for size. */
bool
return !optimize_bb_for_size_p (bb);
}
+/* Return the optimization type that should be used for block BB. */
+
+optimization_type
+bb_optimization_type (const_basic_block bb)
+{
+ return (optimize_bb_for_speed_p (bb)
+ ? OPTIMIZE_FOR_SPEED
+ : OPTIMIZE_FOR_SIZE);
+}
+
/* Return TRUE when BB should be optimized for size. */
bool
bool
predictable_edge_p (edge e)
{
- if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
+ if (!e->probability.initialized_p ())
return false;
- if ((e->probability
+ if ((e->probability.to_reg_br_prob_base ()
<= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
- || (REG_BR_PROB_BASE - e->probability
+ || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
<= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
return true;
return false;
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.
+/* Return true if the one of outgoing edges is already predicted by
+ PREDICTOR for edge E predicted as TAKEN. */
- 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)
+bool
+edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
{
- return (profile_status_for_fn (cfun) == PROFILE_READ
- || (profile_status_for_fn (cfun) == PROFILE_GUESSED
- && (prob <= HITRATE (1) || prob >= HITRATE (99))));
+ struct edge_prediction *i;
+ basic_block bb = e->src;
+ edge_prediction **preds = bb_predictions->get (bb);
+ if (!preds)
+ return false;
+
+ int probability = predictor_info[(int) predictor].hitrate;
+
+ if (taken != TAKEN)
+ probability = REG_BR_PROB_BASE - probability;
+
+ for (i = *preds; i; i = i->ep_next)
+ if (i->ep_predictor == predictor
+ && i->ep_edge == e
+ && i->ep_probability == probability)
+ return true;
+ return false;
}
/* Same predicate as above, working on edges. */
bool
edge_probability_reliable_p (const_edge e)
{
- return probability_reliable_p (e->probability);
+ return e->probability.probably_reliable_p ();
}
/* Same predicate as edge_probability_reliable_p, working on notes. */
br_prob_note_reliable_p (const_rtx note)
{
gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
- return probability_reliable_p (XINT (note, 0));
+ return profile_probability::from_reg_br_prob_note
+ (XINT (note, 0)).probably_reliable_p ();
}
static void
enum prediction taken)
{
int probability = predictor_info[(int) predictor].hitrate;
+ gcc_assert (probability != PROB_UNINITIALIZED);
if (taken != TAKEN)
probability = REG_BR_PROB_BASE - probability;
void
gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
{
- gcc_assert (profile_status_for_fn (cfun) != PROFILE_GUESSED);
- if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun) && EDGE_COUNT (e->src->succs) >
- 1)
- && flag_guess_branch_prob && optimize)
+ if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
+ && EDGE_COUNT (e->src->succs) > 1
+ && flag_guess_branch_prob
+ && optimize)
{
struct edge_prediction *i = XNEW (struct edge_prediction);
edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
}
}
-/* Remove all predictions on given basic block that are attached
- to edge E. */
+/* Filter edge predictions PREDS by a function FILTER. DATA are passed
+ to the filter function. */
+
void
-remove_predictions_associated_with_edge (edge e)
+filter_predictions (edge_prediction **preds,
+ bool (*filter) (edge_prediction *, void *), void *data)
{
if (!bb_predictions)
return;
- edge_prediction **preds = bb_predictions->get (e->src);
-
if (preds)
{
struct edge_prediction **prediction = preds;
while (*prediction)
{
- if ((*prediction)->ep_edge == e)
+ if ((*filter) (*prediction, data))
+ prediction = &((*prediction)->ep_next);
+ else
{
next = (*prediction)->ep_next;
free (*prediction);
*prediction = next;
}
- else
- prediction = &((*prediction)->ep_next);
}
}
}
+/* Filter function predicate that returns true for a edge predicate P
+ if its edge is equal to DATA. */
+
+bool
+equal_edge_p (edge_prediction *p, void *data)
+{
+ return p->ep_edge == (edge)data;
+}
+
+/* Remove all predictions on given basic block that are attached
+ to edge E. */
+void
+remove_predictions_associated_with_edge (edge e)
+{
+ if (!bb_predictions)
+ return;
+
+ edge_prediction **preds = bb_predictions->get (e->src);
+ filter_predictions (preds, equal_edge_p, e);
+}
+
/* Clears the list of predictions stored for BB. */
static void
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_BR_PROB)
- XINT (note, 0) = REG_BR_PROB_BASE - XINT (note, 0);
+ XINT (note, 0) = profile_probability::from_reg_br_prob_note
+ (XINT (note, 0)).invert ().to_reg_br_prob_note ();
else if (REG_NOTE_KIND (note) == REG_BR_PRED)
XEXP (XEXP (note, 0), 1)
= GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
static void
dump_prediction (FILE *file, enum br_predictor predictor, int probability,
- basic_block bb, int used)
+ basic_block bb, enum predictor_reason reason = REASON_NONE,
+ edge ep_edge = NULL)
{
- edge e;
+ edge e = ep_edge;
edge_iterator ei;
if (!file)
return;
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (! (e->flags & EDGE_FALLTHRU))
- break;
+ if (e == NULL)
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (! (e->flags & EDGE_FALLTHRU))
+ break;
+
+ char edge_info_str[128];
+ if (ep_edge)
+ sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
+ ep_edge->dest->index);
+ else
+ edge_info_str[0] = '\0';
- fprintf (file, " %s heuristics%s: %.1f%%",
+ fprintf (file, " %s heuristics%s%s: %.1f%%",
predictor_info[predictor].name,
- used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
+ edge_info_str, reason_messages[reason],
+ probability * 100.0 / REG_BR_PROB_BASE);
- if (bb->count)
+ if (bb->count.initialized_p ())
{
- fprintf (file, " exec %" PRId64, bb->count);
+ fprintf (file, " exec ");
+ bb->count.dump (file);
if (e)
{
- fprintf (file, " hit %" PRId64, e->count);
- fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
+ fprintf (file, " hit ");
+ e->count ().dump (file);
+ fprintf (file, " (%.1f%%)", e->count ().to_gcov_type() * 100.0
+ / bb->count.to_gcov_type ());
}
}
fprintf (file, "\n");
+
+ /* Print output that be easily read by analyze_brprob.py script. We are
+ interested only in counts that are read from GCDA files. */
+ if (dump_file && (dump_flags & TDF_DETAILS)
+ && bb->count.precise_p ()
+ && reason == REASON_NONE)
+ {
+ gcc_assert (e->count ().precise_p ());
+ fprintf (file, ";;heuristics;%s;%" PRId64 ";%" PRId64 ";%.1f;\n",
+ predictor_info[predictor].name,
+ bb->count.to_gcov_type (), e->count ().to_gcov_type (),
+ probability * 100.0 / REG_BR_PROB_BASE);
+ }
+}
+
+/* Return true if STMT is known to be unlikely executed. */
+
+static bool
+unlikely_executed_stmt_p (gimple *stmt)
+{
+ if (!is_gimple_call (stmt))
+ return false;
+ /* NORETURN attribute alone is not strong enough: exit() may be quite
+ likely executed once during program run. */
+ if (gimple_call_fntype (stmt)
+ && lookup_attribute ("cold",
+ TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
+ && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
+ return true;
+ tree decl = gimple_call_fndecl (stmt);
+ if (!decl)
+ return false;
+ if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
+ && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
+ return true;
+
+ cgraph_node *n = cgraph_node::get (decl);
+ if (!n)
+ return false;
+
+ availability avail;
+ n = n->ultimate_alias_target (&avail);
+ if (avail < AVAIL_AVAILABLE)
+ return false;
+ if (!n->analyzed
+ || n->decl == current_function_decl)
+ return false;
+ return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
+}
+
+/* Return true if BB is unlikely executed. */
+
+static bool
+unlikely_executed_bb_p (basic_block bb)
+{
+ if (bb->count == profile_count::zero ())
+ return true;
+ if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
+ return false;
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
+ return true;
+ if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
+ return false;
+ }
+ return false;
}
/* We can not predict the probabilities of outgoing edges of bb. Set them
- evenly and hope for the best. */
+ evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
+ even probability for all edges not mentioned in the set. These edges
+ are given PROB_VERY_UNLIKELY probability. */
+
static void
-set_even_probabilities (basic_block bb)
+set_even_probabilities (basic_block bb,
+ hash_set<edge> *unlikely_edges = NULL)
{
- int nedges = 0;
- edge e;
+ unsigned nedges = 0, unlikely_count = 0;
+ edge e = NULL;
edge_iterator ei;
+ profile_probability all = profile_probability::always ();
FOR_EACH_EDGE (e, ei, bb->succs)
- if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
- nedges ++;
+ if (e->probability.initialized_p ())
+ all -= e->probability;
+ else if (!unlikely_executed_edge_p (e))
+ {
+ nedges ++;
+ if (unlikely_edges != NULL && unlikely_edges->contains (e))
+ {
+ all -= profile_probability::very_unlikely ();
+ unlikely_count++;
+ }
+ }
+
+ /* Make the distribution even if all edges are unlikely. */
+ if (unlikely_count == nedges)
+ {
+ unlikely_edges = NULL;
+ unlikely_count = 0;
+ }
+
+ unsigned c = nedges - unlikely_count;
+
FOR_EACH_EDGE (e, ei, bb->succs)
- if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
- e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
+ if (e->probability.initialized_p ())
+ ;
+ else if (!unlikely_executed_edge_p (e))
+ {
+ if (unlikely_edges != NULL && unlikely_edges->contains (e))
+ e->probability = profile_probability::very_unlikely ();
+ else
+ e->probability = all.apply_scale (1, c).guessed ();
+ }
else
- e->probability = 0;
+ e->probability = profile_probability::never ();
+}
+
+/* Add REG_BR_PROB note to JUMP with PROB. */
+
+void
+add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
+{
+ gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
+ add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
}
/* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
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)
dump_prediction (dump_file, PRED_NO_PREDICTION,
- combined_probability, bb, true);
+ combined_probability, bb);
else
{
- dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
- bb, !first_match);
- dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
- bb, first_match);
+ 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)
combined_probability = best_probability;
- dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
+ dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
while (*pnote)
{
int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
dump_prediction (dump_file, predictor, probability, bb,
- !first_match || best_predictor == predictor);
+ (!first_match || best_predictor == predictor)
+ ? REASON_NONE : REASON_IGNORED);
*pnote = XEXP (*pnote, 1);
}
else
if (!prob_note)
{
- add_int_reg_note (insn, REG_BR_PROB, combined_probability);
+ profile_probability p
+ = profile_probability::from_reg_br_prob_base (combined_probability);
+ add_reg_br_prob_note (insn, p);
/* Save the prediction into CFG in case we are seeing non-degenerated
conditional jump. */
if (!single_succ_p (bb))
{
- BRANCH_EDGE (bb)->probability = combined_probability;
+ BRANCH_EDGE (bb)->probability = p;
FALLTHRU_EDGE (bb)->probability
- = REG_BR_PROB_BASE - combined_probability;
+ = BRANCH_EDGE (bb)->probability.invert ();
}
}
else if (!single_succ_p (bb))
{
- int prob = XINT (prob_note, 0);
+ profile_probability prob = profile_probability::from_reg_br_prob_note
+ (XINT (prob_note, 0));
BRANCH_EDGE (bb)->probability = prob;
- FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
+ FALLTHRU_EDGE (bb)->probability = prob.invert ();
}
else
- single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
+ single_succ_edge (bb)->probability = profile_probability::always ();
+}
+
+/* Edge prediction hash traits. */
+
+struct predictor_hash: pointer_hash <edge_prediction>
+{
+
+ static inline hashval_t hash (const edge_prediction *);
+ static inline bool equal (const edge_prediction *, const edge_prediction *);
+};
+
+/* Calculate hash value of an edge prediction P based on predictor and
+ normalized probability. */
+
+inline hashval_t
+predictor_hash::hash (const edge_prediction *p)
+{
+ inchash::hash hstate;
+ hstate.add_int (p->ep_predictor);
+
+ int prob = p->ep_probability;
+ if (prob > REG_BR_PROB_BASE / 2)
+ prob = REG_BR_PROB_BASE - prob;
+
+ hstate.add_int (prob);
+
+ return hstate.end ();
+}
+
+/* Return true whether edge predictions P1 and P2 use the same predictor and
+ have equal (or opposed probability). */
+
+inline bool
+predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
+{
+ return (p1->ep_predictor == p2->ep_predictor
+ && (p1->ep_probability == p2->ep_probability
+ || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
+}
+
+struct predictor_hash_traits: predictor_hash,
+ typed_noop_remove <edge_prediction *> {};
+
+/* Return true if edge prediction P is not in DATA hash set. */
+
+static bool
+not_removed_prediction_p (edge_prediction *p, void *data)
+{
+ hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
+ return !remove->contains (p);
+}
+
+/* Prune predictions for a basic block BB. Currently we do following
+ clean-up steps:
+
+ 1) remove duplicate prediction that is guessed with the same probability
+ (different than 1/2) to both edge
+ 2) remove duplicates for a prediction that belongs with the same probability
+ to a single edge
+
+ */
+
+static void
+prune_predictions_for_bb (basic_block bb)
+{
+ edge_prediction **preds = bb_predictions->get (bb);
+
+ if (preds)
+ {
+ hash_table <predictor_hash_traits> s (13);
+ hash_set <edge_prediction *> remove;
+
+ /* Step 1: identify predictors that should be removed. */
+ for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
+ {
+ edge_prediction *existing = s.find (pred);
+ if (existing)
+ {
+ if (pred->ep_edge == existing->ep_edge
+ && pred->ep_probability == existing->ep_probability)
+ {
+ /* Remove a duplicate predictor. */
+ dump_prediction (dump_file, pred->ep_predictor,
+ pred->ep_probability, bb,
+ REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);
+
+ remove.add (pred);
+ }
+ else if (pred->ep_edge != existing->ep_edge
+ && pred->ep_probability == existing->ep_probability
+ && pred->ep_probability != REG_BR_PROB_BASE / 2)
+ {
+ /* Remove both predictors as they predict the same
+ for both edges. */
+ dump_prediction (dump_file, existing->ep_predictor,
+ pred->ep_probability, bb,
+ REASON_EDGE_PAIR_DUPLICATE,
+ existing->ep_edge);
+ dump_prediction (dump_file, pred->ep_predictor,
+ pred->ep_probability, bb,
+ REASON_EDGE_PAIR_DUPLICATE,
+ pred->ep_edge);
+
+ remove.add (existing);
+ remove.add (pred);
+ }
+ }
+
+ edge_prediction **slot2 = s.find_slot (pred, INSERT);
+ *slot2 = pred;
+ }
+
+ /* Step 2: Remove predictors. */
+ filter_predictions (preds, not_removed_prediction_p, &remove);
+ }
}
/* Combine predictions into single probability and store them into CFG.
- Remove now useless prediction entries. */
+ Remove now useless prediction entries.
+ If DRY_RUN is set, only produce dumps and do not modify profile. */
static void
-combine_predictions_for_bb (basic_block bb)
+combine_predictions_for_bb (basic_block bb, bool dry_run)
{
int best_probability = PROB_EVEN;
enum br_predictor best_predictor = END_PREDICTORS;
int nedges = 0;
edge e, first = NULL, second = NULL;
edge_iterator ei;
+ int nzero = 0;
+ int nunknown = 0;
FOR_EACH_EDGE (e, ei, bb->succs)
- if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
- {
- nedges ++;
- if (first && !second)
- second = e;
- if (!first)
- first = e;
- }
+ {
+ if (!unlikely_executed_edge_p (e))
+ {
+ nedges ++;
+ if (first && !second)
+ second = e;
+ if (!first)
+ first = e;
+ }
+ else if (!e->probability.initialized_p ())
+ e->probability = profile_probability::never ();
+ if (!e->probability.initialized_p ())
+ nunknown++;
+ else if (e->probability == profile_probability::never ())
+ nzero++;
+ }
/* When there is no successor or only one choice, prediction is easy.
- We are lazy for now and predict only basic blocks with two outgoing
- edges. It is possible to predict generic case too, but we have to
- ignore first match heuristics and do more involved combining. Implement
- this later. */
+ When we have a basic block with more than 2 successors, the situation
+ is more complicated as DS theory cannot be used literally.
+ More precisely, let's assume we predicted edge e1 with probability p1,
+ thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
+ need to find probability of e.g. m1({b2}), which we don't know.
+ The only approximation is to equally distribute 1-p1 to all edges
+ different from b1.
+
+ According to numbers we've got from SPEC2006 benchark, there's only
+ one interesting reliable predictor (noreturn call), which can be
+ handled with a bit easier approach. */
if (nedges != 2)
{
- if (!bb->count)
- set_even_probabilities (bb);
+ hash_set<edge> unlikely_edges (4);
+
+ /* Identify all edges that have a probability close to very unlikely.
+ Doing the approach for very unlikely doesn't worth for doing as
+ there's no such probability in SPEC2006 benchmark. */
+ edge_prediction **preds = bb_predictions->get (bb);
+ if (preds)
+ for (pred = *preds; pred; pred = pred->ep_next)
+ if (pred->ep_probability <= PROB_VERY_UNLIKELY)
+ unlikely_edges.add (pred->ep_edge);
+
+ if (!dry_run)
+ set_even_probabilities (bb, &unlikely_edges);
clear_bb_predictions (bb);
if (dump_file)
- fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
- nedges, bb->index);
+ {
+ fprintf (dump_file, "Predictions for bb %i\n", bb->index);
+ if (unlikely_edges.elements () == 0)
+ fprintf (dump_file,
+ "%i edges in bb %i predicted to even probabilities\n",
+ nedges, bb->index);
+ else
+ {
+ fprintf (dump_file,
+ "%i edges in bb %i predicted with some unlikely edges\n",
+ nedges, bb->index);
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!unlikely_executed_edge_p (e))
+ dump_prediction (dump_file, PRED_COMBINED,
+ e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
+ }
+ }
return;
}
if (dump_file)
fprintf (dump_file, "Predictions for bb %i\n", bb->index);
+ prune_predictions_for_bb (bb);
+
edge_prediction **preds = bb_predictions->get (bb);
+
if (preds)
{
/* We implement "first match" heuristics and use probability guessed
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;
pred2; pred2 = pred2->ep_next)
if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
{
- int probability2 = pred->ep_probability;
+ int probability2 = pred2->ep_probability;
if (pred2->ep_edge != first)
probability2 = REG_BR_PROB_BASE - probability2;
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, true);
+ dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
else
{
- dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
- !first_match);
- dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
- first_match);
+ 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)
combined_probability = best_probability;
- dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
+ dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
if (preds)
{
enum br_predictor predictor = pred->ep_predictor;
int probability = pred->ep_probability;
- if (pred->ep_edge != EDGE_SUCC (bb, 0))
- probability = REG_BR_PROB_BASE - probability;
dump_prediction (dump_file, predictor, probability, bb,
- !first_match || best_predictor == predictor);
+ (!first_match || best_predictor == predictor)
+ ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
}
}
clear_bb_predictions (bb);
- if (!bb->count)
+
+ /* If we have only one successor which is unknown, we can compute missing
+ probablity. */
+ if (nunknown == 1)
{
- first->probability = combined_probability;
- second->probability = REG_BR_PROB_BASE - combined_probability;
+ profile_probability prob = profile_probability::always ();
+ edge missing = NULL;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->probability.initialized_p ())
+ prob -= e->probability;
+ else if (missing == NULL)
+ missing = e;
+ else
+ gcc_unreachable ();
+ missing->probability = prob;
+ }
+ /* If nothing is unknown, we have nothing to update. */
+ else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
+ ;
+ else if (!dry_run)
+ {
+ first->probability
+ = profile_probability::from_reg_br_prob_base (combined_probability);
+ second->probability = first->probability.invert ();
}
}
static bool
expr_coherent_p (tree t1, tree t2)
{
- gimple stmt;
+ gimple *stmt;
tree ssa_name_1 = NULL;
tree ssa_name_2 = NULL;
return false;
}
+/* Return true if E is predicted by one of loop heuristics. */
+
+static bool
+predicted_by_loop_heuristics_p (basic_block bb)
+{
+ struct edge_prediction *i;
+ edge_prediction **preds = bb_predictions->get (bb);
+
+ if (!preds)
+ return false;
+
+ for (i = *preds; i; i = i->ep_next)
+ if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
+ || 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 branch probability of BB when BB contains a branch that compares
an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
enum tree_code loop_bound_code,
int loop_bound_step)
{
- gimple stmt;
+ gimple *stmt;
tree compare_var, compare_base;
enum tree_code compare_code;
tree compare_step_var;
edge then_edge;
edge_iterator ei;
- if (predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
- || predicted_by_p (bb, PRED_LOOP_ITERATIONS)
- || predicted_by_p (bb, PRED_LOOP_EXIT))
+ if (predicted_by_loop_heuristics_p (bb))
return;
stmt = last_stmt (bb);
probability = tem.to_uhwi ();
}
+ /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
if (!overall_overflow)
predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
exits. This function takes BB7->BB8 as input, and finds out the extra loop
- exits to predict them using PRED_LOOP_EXIT. */
+ exits to predict them using PRED_LOOP_EXTRA_EXIT. */
static void
predict_extra_loop_exits (edge exit_edge)
{
unsigned i;
bool check_value_one;
- gimple lhs_def_stmt;
+ gimple *lhs_def_stmt;
gphi *phi_stmt;
tree cmp_rhs, cmp_lhs;
- gimple last;
+ gimple *last;
gcond *cmp_stmt;
last = last_stmt (exit_edge->src);
continue;
if (EDGE_COUNT (e->src->succs) != 1)
{
- predict_paths_leading_to_edge (e, PRED_LOOP_EXIT, NOT_TAKEN);
+ predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
continue;
}
FOR_EACH_EDGE (e1, ei, e->src->preds)
- predict_paths_leading_to_edge (e1, PRED_LOOP_EXIT, NOT_TAKEN);
+ predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
}
}
+
/* Predict edge probabilities by exploiting loop structure. */
static void
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. */
- FOR_EACH_LOOP (loop, 0)
+ FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
{
basic_block bb, *bbs;
- unsigned j, n_exits;
+ unsigned j, n_exits = 0;
vec<edge> exits;
struct tree_niter_desc niter_desc;
edge ex;
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);
- n_exits = exits.length ();
+ FOR_EACH_VEC_ELT (exits, j, ex)
+ if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
+ n_exits ++;
if (!n_exits)
{
exits.release ();
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;
int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
int probability;
enum br_predictor predictor;
+ widest_int nit;
+ if (unlikely_executed_edge_p (ex)
+ || (ex->flags & EDGE_ABNORMAL_CALL))
+ continue;
+ /* 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))
+ {
+ 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)
{
/* If we have just one exit and we can derive some information about
the number of iterations of the loop from the statements inside
the loop, use it to predict this exit. */
- else if (n_exits == 1)
+ else if (n_exits == 1
+ && estimated_stmt_executions (loop, &nit))
{
- nitercst = estimated_stmt_executions_int (loop);
- if (nitercst < 0)
- continue;
- if (nitercst > max)
+ if (wi::gtu_p (nit, max))
nitercst = max;
-
+ else
+ nitercst = nit.to_shwi ();
predictor = PRED_LOOP_ITERATIONS_GUESSED;
}
+ /* If we have likely upper bound, trust it for very small iteration
+ counts. Such loops would otherwise get mispredicted by standard
+ LOOP_EXIT heuristics. */
+ else if (n_exits == 1
+ && likely_max_stmt_executions (loop, &nit)
+ && wi::ltu_p (nit,
+ RDIV (REG_BR_PROB_BASE,
+ REG_BR_PROB_BASE
+ - predictor_info
+ [recursion
+ ? PRED_LOOP_EXIT_WITH_RECURSION
+ : PRED_LOOP_EXIT].hitrate)))
+ {
+ nitercst = nit.to_shwi ();
+ predictor = PRED_LOOP_ITERATIONS_MAX;
+ }
else
- continue;
+ {
+ 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;
- probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
+ probability = RDIV (REG_BR_PROB_BASE, nitercst);
predict_edge (ex, predictor, probability);
}
exits.release ();
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;
-
- /* Loop branch heuristics - predict an edge back to a
- loop's head as taken. */
- if (bb == loop->latch)
{
- e = find_edge (loop->latch, loop->header);
- if (e)
- {
- header_found = 1;
- predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
- }
+ 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_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
- && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
+ /* 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_call_internal_p (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);
}
expr_expected_value_1 (tree type, tree op0, enum tree_code code,
tree op1, bitmap visited, enum br_predictor *predictor)
{
- gimple def;
+ gimple *def;
if (predictor)
*predictor = PRED_UNCONDITIONAL;
if (TREE_CONSTANT (op0))
return op0;
+ if (code == IMAGPART_EXPR)
+ {
+ if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
+ {
+ def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
+ if (is_gimple_call (def)
+ && gimple_call_internal_p (def)
+ && (gimple_call_internal_fn (def)
+ == IFN_ATOMIC_COMPARE_EXCHANGE))
+ {
+ /* Assume that any given atomic operation has low contention,
+ and thus the compare-and-swap operation succeeds. */
+ if (predictor)
+ *predictor = PRED_COMPARE_AND_SWAP;
+ return build_one_cst (TREE_TYPE (op0));
+ }
+ }
+ }
+
if (code != SSA_NAME)
return NULL_TREE;
static void
tree_predict_by_opcode (basic_block bb)
{
- gimple stmt = last_stmt (bb);
+ gimple *stmt = last_stmt (bb);
edge then_edge;
tree op0, op1;
tree type;
tree val;
enum tree_code cmp;
- bitmap visited;
edge_iterator ei;
enum br_predictor predictor;
op1 = gimple_cond_rhs (stmt);
cmp = gimple_cond_code (stmt);
type = TREE_TYPE (op0);
- visited = BITMAP_ALLOC (NULL);
- val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited,
+ val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
&predictor);
- BITMAP_FREE (visited);
if (val && TREE_CODE (val) == INTEGER_CST)
{
if (predictor == PRED_BUILTIN_EXPECT)
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.
}
}
+/* Returns TRUE if the STMT is exit(0) like statement. */
+
+static bool
+is_exit_with_zero_arg (const gimple *stmt)
+{
+ /* This is not exit, _exit or _Exit. */
+ if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
+ && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
+ && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
+ return false;
+
+ /* Argument is an interger zero. */
+ return integer_zerop (gimple_call_arg (stmt, 0));
+}
+
/* Try to guess whether the value of return means error code. */
static enum br_predictor
if (TREE_CONSTANT (val)
&& (!integer_zerop (val) && !integer_onep (val)))
{
- *prediction = TAKEN;
+ *prediction = NOT_TAKEN;
return PRED_CONST_RETURN;
}
}
return PRED_NO_PREDICTION;
}
+/* Return zero if phi result could have values other than -1, 0 or 1,
+ otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
+ values are used or likely. */
+
+static int
+zero_one_minusone (gphi *phi, int limit)
+{
+ int phi_num_args = gimple_phi_num_args (phi);
+ int ret = 0;
+ for (int i = 0; i < phi_num_args; i++)
+ {
+ tree t = PHI_ARG_DEF (phi, i);
+ if (TREE_CODE (t) != INTEGER_CST)
+ continue;
+ wide_int w = wi::to_wide (t);
+ if (w == -1)
+ ret |= 1;
+ else if (w == 0)
+ ret |= 2;
+ else if (w == 1)
+ ret |= 4;
+ else
+ return 0;
+ }
+ for (int i = 0; i < phi_num_args; i++)
+ {
+ tree t = PHI_ARG_DEF (phi, i);
+ if (TREE_CODE (t) == INTEGER_CST)
+ continue;
+ if (TREE_CODE (t) != SSA_NAME)
+ return 0;
+ gimple *g = SSA_NAME_DEF_STMT (t);
+ if (gimple_code (g) == GIMPLE_PHI && limit > 0)
+ if (int r = zero_one_minusone (as_a <gphi *> (g), limit - 1))
+ {
+ ret |= r;
+ continue;
+ }
+ if (!is_gimple_assign (g))
+ return 0;
+ if (gimple_assign_cast_p (g))
+ {
+ tree rhs1 = gimple_assign_rhs1 (g);
+ if (TREE_CODE (rhs1) != SSA_NAME
+ || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
+ || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
+ || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
+ return 0;
+ ret |= (2 | 4);
+ continue;
+ }
+ if (TREE_CODE_CLASS (gimple_assign_rhs_code (g)) != tcc_comparison)
+ return 0;
+ ret |= (2 | 4);
+ }
+ return ret;
+}
+
/* Find the basic block with return expression and look up for possible
return value trying to apply RETURN_PREDICTION heuristics. */
static void
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
{
- gimple last = last_stmt (e->src);
+ gimple *last = last_stmt (e->src);
if (last
&& gimple_code (last) == GIMPLE_RETURN)
{
phi_num_args = gimple_phi_num_args (phi);
pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
+ /* Avoid the case where the function returns -1, 0 and 1 values and
+ nothing else. Those could be qsort etc. comparison functions
+ where the negative return isn't less probable than positive.
+ For this require that the function returns at least -1 or 1
+ or -1 and a boolean value or comparison result, so that functions
+ returning just -1 and 0 are treated as if -1 represents error value. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
+ && !TYPE_UNSIGNED (TREE_TYPE (return_val))
+ && TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
+ if (int r = zero_one_minusone (phi, 3))
+ if ((r & (1 | 4)) == (1 | 4))
+ return;
+
/* Avoid the degenerate case where all return values form the function
belongs to same category (ie they are all positive constants)
so we can hardly say something about them. */
edge_iterator ei;
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
- if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
+ if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
{
has_return_edges = true;
break;
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple stmt = gsi_stmt (gsi);
+ gimple *stmt = gsi_stmt (gsi);
tree decl;
if (is_gimple_call (stmt))
{
- if ((gimple_call_flags (stmt) & ECF_NORETURN)
- && has_return_edges)
+ if (gimple_call_noreturn_p (stmt)
+ && has_return_edges
+ && !is_exit_with_zero_arg (stmt))
predict_paths_leading_to (bb, PRED_NORETURN,
NOT_TAKEN);
decl = gimple_call_fndecl (stmt);
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)
{
}
}
-#ifdef ENABLE_CHECKING
-
/* Callback for hash_map::traverse, asserts that the pointer map is
empty. */
gcc_assert (!value);
return false;
}
-#endif
-/* Predict branch probabilities and estimate profile for basic block BB. */
+/* Predict branch probabilities and estimate profile for basic block BB.
+ When LOCAL_ONLY is set do not use any global properties of CFG. */
static void
-tree_estimate_probability_bb (basic_block bb)
+tree_estimate_probability_bb (basic_block bb, bool local_only)
{
edge e;
edge_iterator ei;
- gimple last;
FOR_EACH_EDGE (e, ei, bb->succs)
{
- /* Predict edges to user labels with attributes. */
- if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
- {
- gimple_stmt_iterator gi;
- for (gi = gsi_start_bb (e->dest); !gsi_end_p (gi); gsi_next (&gi))
- {
- glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gi));
- tree decl;
-
- if (!label_stmt)
- break;
- decl = gimple_label_label (label_stmt);
- if (DECL_ARTIFICIAL (decl))
- continue;
-
- /* Finally, we have a user-defined label. */
- if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl)))
- predict_edge_def (e, PRED_COLD_LABEL, NOT_TAKEN);
- else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl)))
- predict_edge_def (e, PRED_HOT_LABEL, TAKEN);
- }
- }
-
- /* Predict early returns to be probable, as we've already taken
- care for error returns and other cases are often used for
- fast paths through function.
-
- Since we've already removed the return statements, we are
- looking for CFG like:
-
- if (conditional)
- {
- ..
- goto return_block
- }
- some other blocks
- return_block:
- return_stmt. */
- if (e->dest != bb->next_bb
- && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
- && single_succ_p (e->dest)
- && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
- && (last = last_stmt (e->dest)) != NULL
- && gimple_code (last) == GIMPLE_RETURN)
- {
- edge e1;
- edge_iterator ei1;
-
- if (single_succ_p (bb))
- {
- FOR_EACH_EDGE (e1, ei1, bb->preds)
- if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
- && !predicted_by_p (e1->src, PRED_CONST_RETURN)
- && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
- predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
- }
- else
- if (!predicted_by_p (e->src, PRED_NULL_RETURN)
- && !predicted_by_p (e->src, PRED_CONST_RETURN)
- && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
- predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
- }
-
/* Look for block we are guarding (ie we dominate it,
but it doesn't postdominate us). */
if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
+ && !local_only
&& dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
{
for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
gsi_next (&bi))
{
- gimple stmt = gsi_stmt (bi);
+ 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_edge_def (e, PRED_CALL, NOT_TAKEN);
+ if (gimple_call_fndecl (stmt))
+ predict_edge_def (e, PRED_CALL, NOT_TAKEN);
+ else if (virtual_method_call_p (gimple_call_fn (stmt)))
+ predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
+ else
+ predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
break;
}
}
/* Predict branch probabilities and estimate profile of the tree CFG.
This function can be called from the loop optimizers to recompute
- the profile information. */
+ the profile information.
+ If DRY_RUN is set, do not modify CFG and only produce dump files. */
void
-tree_estimate_probability (void)
+tree_estimate_probability (bool dry_run)
{
basic_block bb;
predict_loops ();
FOR_EACH_BB_FN (bb, cfun)
- tree_estimate_probability_bb (bb);
+ tree_estimate_probability_bb (bb, false);
FOR_EACH_BB_FN (bb, cfun)
- combine_predictions_for_bb (bb);
+ combine_predictions_for_bb (bb, dry_run);
+
+ if (flag_checking)
+ bb_predictions->traverse<void *, assert_is_empty> (NULL);
-#ifdef ENABLE_CHECKING
- bb_predictions->traverse<void *, assert_is_empty> (NULL);
-#endif
delete bb_predictions;
bb_predictions = NULL;
- estimate_bb_frequencies (false);
+ if (!dry_run)
+ estimate_bb_frequencies (false);
free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_exit_edges ();
}
+
+/* Set edge->probability for each successor edge of BB. */
+void
+tree_guess_outgoing_edge_probabilities (basic_block bb)
+{
+ bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
+ tree_estimate_probability_bb (bb, true);
+ combine_predictions_for_bb (bb, false);
+ if (flag_checking)
+ bb_predictions->traverse<void *, assert_is_empty> (NULL);
+ delete bb_predictions;
+ bb_predictions = NULL;
+}
\f
/* Predict edges to successors of CUR whose sources are not postdominated by
BB by PRED and recurse to all postdominators. */
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)
bool found = false;
/* Ignore fake edges and eh, we predict them as not taken anyway. */
- if (e->flags & (EDGE_EH | EDGE_FAKE))
+ if (unlikely_executed_edge_p (e))
continue;
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))
+ && !unlikely_executed_edge_p (e2)
+ && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
+ && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
{
found = true;
break;
regions that are only reachable by abnormal edges. We simply
prevent visiting given BB twice. */
if (found)
- predict_edge_def (e, pred, taken);
+ {
+ if (!edge_predicted_by_p (e, pred, taken))
+ 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);
- BITMAP_FREE (visited);
+ predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
}
/* Like predict_paths_leading_to but take edge instead of basic block. */
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;
basic_block bb = e->src;
FOR_EACH_EDGE (e2, ei, bb->succs)
if (e2->dest != e->src && e2->dest != e->dest
- && !(e->flags & (EDGE_EH | EDGE_FAKE))
+ && !unlikely_executed_edge_p (e)
&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
{
has_nonloop_edge = true;
}
if (!has_nonloop_edge)
{
- bitmap visited = BITMAP_ALLOC (NULL);
- predict_paths_for_bb (bb, bb, pred, taken, visited);
- BITMAP_FREE (visited);
+ predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
}
else
predict_edge_def (e, pred, taken);
BLOCK_INFO (bb)->npredecessors = count;
/* When function never returns, we will never process exit block. */
if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
- bb->count = bb->frequency = 0;
+ bb->count = profile_count::zero ();
}
BLOCK_INFO (head)->frequency = 1;
/* Compute frequency of basic block. */
if (bb != head)
{
-#ifdef ENABLE_CHECKING
- FOR_EACH_EDGE (e, ei, bb->preds)
- gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
- || (e->flags & EDGE_DFS_BACK));
-#endif
+ if (flag_checking)
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
+ || (e->flags & EDGE_DFS_BACK));
FOR_EACH_EDGE (e, ei, bb->preds)
if (EDGE_INFO (e)->back_edge)
* BLOCK_INFO (e->src)->frequency /
REG_BR_PROB_BASE); */
- sreal tmp = e->probability;
+ /* FIXME: Graphite is producing edges with no profile. Once
+ this is fixed, drop this. */
+ sreal tmp = e->probability.initialized_p () ?
+ e->probability.to_reg_br_prob_base () : 0;
tmp *= BLOCK_INFO (e->src)->frequency;
tmp *= real_inv_br_prob_base;
frequency += tmp;
= ((e->probability * BLOCK_INFO (bb)->frequency)
/ REG_BR_PROB_BASE); */
- sreal tmp = e->probability;
+ /* FIXME: Graphite is producing edges with no profile. Once
+ this is fixed, drop this. */
+ sreal tmp = e->probability.initialized_p () ?
+ e->probability.to_reg_br_prob_base () : 0;
tmp *= BLOCK_INFO (bb)->frequency;
EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
}
edge e;
basic_block *bbs;
unsigned i;
- bitmap tovisit = BITMAP_ALLOC (NULL);
+ auto_bitmap tovisit;
estimate_loops_at_level (loop->inner);
bitmap_set_bit (tovisit, bbs[i]->index);
free (bbs);
propagate_freq (loop->header, tovisit);
- BITMAP_FREE (tovisit);
}
}
static void
estimate_loops (void)
{
- bitmap tovisit = BITMAP_ALLOC (NULL);
+ auto_bitmap tovisit;
basic_block bb;
/* Start by estimating the frequencies in the loops. */
bitmap_set_bit (tovisit, bb->index);
}
propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit);
- BITMAP_FREE (tovisit);
}
/* Drop the profile for NODE to guessed, and update its frequency based on
whether it is expected to be hot given the CALL_COUNT. */
static void
-drop_profile (struct cgraph_node *node, gcov_type call_count)
+drop_profile (struct cgraph_node *node, profile_count call_count)
{
struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
/* In the case where this was called by another function with a
if (dump_file)
fprintf (dump_file,
- "Dropping 0 profile for %s/%i. %s based on calls.\n",
- node->name (), node->order,
- hot ? "Function is hot" : "Function is normal");
+ "Dropping 0 profile for %s. %s based on calls.\n",
+ node->dump_name (),
+ hot ? "Function is hot" : "Function is normal");
/* We only expect to miss profiles for functions that are reached
via non-zero call edges in cases where the function may have
been linked from another module or library (COMDATs and extern
{
if (dump_file)
fprintf (dump_file,
- "Missing counts for called function %s/%i\n",
- node->name (), node->order);
+ "Missing counts for called function %s\n",
+ node->dump_name ());
}
else
- warning (0, "Missing counts for called function %s/%i",
- node->name (), node->order);
+ warning (0, "Missing counts for called function %s",
+ node->dump_name ());
+ }
+
+ basic_block bb;
+ if (opt_for_fn (node->decl, flag_guess_branch_prob))
+ {
+ bool clear_zeros
+ = !ENTRY_BLOCK_PTR_FOR_FN (fn)->count.nonzero_p ();
+ FOR_ALL_BB_FN (bb, fn)
+ if (clear_zeros || !(bb->count == profile_count::zero ()))
+ bb->count = bb->count.guessed_local ();
+ fn->cfg->count_max = fn->cfg->count_max.guessed_local ();
+ }
+ else
+ {
+ FOR_ALL_BB_FN (bb, fn)
+ bb->count = profile_count::uninitialized ();
+ fn->cfg->count_max = profile_count::uninitialized ();
}
+ struct cgraph_edge *e;
+ for (e = node->callees; e; e = e->next_callee)
+ e->count = gimple_bb (e->call_stmt)->count;
+ for (e = node->indirect_calls; e; e = e->next_callee)
+ e->count = gimple_bb (e->call_stmt)->count;
+ node->count = ENTRY_BLOCK_PTR_FOR_FN (fn)->count;
+
profile_status_for_fn (fn)
= (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
node->frequency
{
struct cgraph_node *node;
int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
- vec<struct cgraph_node *> worklist;
- worklist.create (64);
+ auto_vec<struct cgraph_node *, 64> worklist;
/* See if 0 count function has non-0 count callers. In this case we
lost some profile. Drop its function profile to PROFILE_GUESSED. */
FOR_EACH_DEFINED_FUNCTION (node)
{
struct cgraph_edge *e;
- gcov_type call_count = 0;
+ profile_count call_count = profile_count::zero ();
gcov_type max_tp_first_run = 0;
struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
- if (node->count)
+ if (node->count.ipa ().nonzero_p ())
continue;
for (e = node->callers; e; e = e->next_caller)
- {
- call_count += e->count;
+ if (e->count.ipa ().initialized_p () && e->count.ipa () > 0)
+ {
+ call_count = call_count + e->count.ipa ();
- if (e->caller->tp_first_run > max_tp_first_run)
- max_tp_first_run = e->caller->tp_first_run;
- }
+ if (e->caller->tp_first_run > max_tp_first_run)
+ max_tp_first_run = e->caller->tp_first_run;
+ }
/* If time profile is missing, let assign the maximum that comes from
caller functions. */
if (!node->tp_first_run && max_tp_first_run)
node->tp_first_run = max_tp_first_run + 1;
- if (call_count
+ if (call_count > 0
&& fn && fn->cfg
- && (call_count * unlikely_count_fraction >= profile_info->runs))
+ && (call_count.apply_scale (unlikely_count_fraction, 1)
+ >= profile_info->runs))
{
drop_profile (node, call_count);
worklist.safe_push (node);
struct cgraph_node *callee = e->callee;
struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
- if (callee->count > 0)
+ if (!(e->count.ipa () == profile_count::zero ())
+ && callee->count.ipa ().nonzero_p ())
continue;
- if (DECL_COMDAT (callee->decl) && fn && fn->cfg
+ if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
+ && fn && fn->cfg
&& profile_status_for_fn (fn) == PROFILE_READ)
{
- drop_profile (node, 0);
+ drop_profile (node, profile_count::zero ());
worklist.safe_push (callee);
}
}
}
- worklist.release ();
}
/* Convert counts measured by profile driven feedback to frequencies.
Return nonzero iff there was any nonzero execution count. */
-int
-counts_to_freqs (void)
+bool
+update_max_bb_count (void)
{
- gcov_type count_max, true_count_max = 0;
+ profile_count true_count_max = profile_count::uninitialized ();
basic_block bb;
- /* Don't overwrite the estimated frequencies when the profile for
- the function is missing. We may drop this function PROFILE_GUESSED
- later in drop_profile (). */
- if (!flag_auto_profile && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
- return 0;
-
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
- true_count_max = MAX (bb->count, true_count_max);
+ true_count_max = true_count_max.max (bb->count);
- count_max = MAX (true_count_max, 1);
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
- bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
+ cfun->cfg->count_max = true_count_max;
- return true_count_max;
+ return true_count_max.ipa ().nonzero_p ();
}
/* Return true if function is likely to be expensive, so there is no point to
bool
expensive_function_p (int threshold)
{
- unsigned int sum = 0;
basic_block bb;
- unsigned int limit;
- /* We can not compute accurately for large thresholds due to scaled
- frequencies. */
- gcc_assert (threshold <= BB_FREQ_MAX);
-
- /* Frequencies are out of range. This either means that function contains
- internal loop executing more than BB_FREQ_MAX times or profile feedback
- is available and function has not been executed at all. */
- if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency == 0)
+ /* If profile was scaled in a way entry block has count 0, then the function
+ is deifnitly taking a lot of time. */
+ if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
return true;
- /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
- limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency * threshold;
+ profile_count limit = ENTRY_BLOCK_PTR_FOR_FN
+ (cfun)->count.apply_scale (threshold, 1);
+ profile_count sum = profile_count::zero ();
FOR_EACH_BB_FN (bb, cfun)
{
rtx_insn *insn;
+ if (!bb->count.initialized_p ())
+ {
+ if (dump_file)
+ fprintf (dump_file, "Function is considered expensive because"
+ " count of bb %i is not initialized\n", bb->index);
+ return true;
+ }
+
FOR_BB_INSNS (bb, insn)
if (active_insn_p (insn))
{
- sum += bb->frequency;
+ sum += bb->count;
if (sum > limit)
return true;
}
return false;
}
+/* All basic blocks that are reachable only from unlikely basic blocks are
+ unlikely. */
+
+void
+propagate_unlikely_bbs_forward (void)
+{
+ auto_vec<basic_block, 64> worklist;
+ basic_block bb;
+ edge_iterator ei;
+ edge e;
+
+ if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
+ {
+ ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
+ worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+
+ while (worklist.length () > 0)
+ {
+ bb = worklist.pop ();
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!(e->count () == profile_count::zero ())
+ && !(e->dest->count == profile_count::zero ())
+ && !e->dest->aux)
+ {
+ e->dest->aux = (void *)(size_t) 1;
+ worklist.safe_push (e->dest);
+ }
+ }
+ }
+
+ FOR_ALL_BB_FN (bb, cfun)
+ {
+ if (!bb->aux)
+ {
+ if (!(bb->count == profile_count::zero ())
+ && (dump_file && (dump_flags & TDF_DETAILS)))
+ fprintf (dump_file,
+ "Basic block %i is marked unlikely by forward prop\n",
+ bb->index);
+ bb->count = profile_count::zero ();
+ }
+ else
+ bb->aux = NULL;
+ }
+}
+
+/* Determine basic blocks/edges that are known to be unlikely executed and set
+ their counters to zero.
+ This is done with first identifying obviously unlikely BBs/edges and then
+ propagating in both directions. */
+
+static void
+determine_unlikely_bbs ()
+{
+ basic_block bb;
+ auto_vec<basic_block, 64> worklist;
+ edge_iterator ei;
+ edge e;
+
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ if (!(bb->count == profile_count::zero ())
+ && unlikely_executed_bb_p (bb))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Basic block %i is locally unlikely\n",
+ bb->index);
+ bb->count = profile_count::zero ();
+ }
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!(e->probability == profile_probability::never ())
+ && unlikely_executed_edge_p (e))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Edge %i->%i is locally unlikely\n",
+ bb->index, e->dest->index);
+ e->probability = profile_probability::never ();
+ }
+
+ gcc_checking_assert (!bb->aux);
+ }
+ propagate_unlikely_bbs_forward ();
+
+ auto_vec<int, 64> nsuccs;
+ nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun));
+ FOR_ALL_BB_FN (bb, cfun)
+ if (!(bb->count == profile_count::zero ())
+ && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
+ {
+ nsuccs[bb->index] = 0;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!(e->probability == profile_probability::never ())
+ && !(e->dest->count == profile_count::zero ()))
+ nsuccs[bb->index]++;
+ if (!nsuccs[bb->index])
+ worklist.safe_push (bb);
+ }
+ while (worklist.length () > 0)
+ {
+ bb = worklist.pop ();
+ if (bb->count == profile_count::zero ())
+ continue;
+ if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
+ {
+ bool found = false;
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ if (stmt_can_terminate_bb_p (gsi_stmt (gsi))
+ /* stmt_can_terminate_bb_p special cases noreturns because it
+ assumes that fake edges are created. We want to know that
+ noreturn alone does not imply BB to be unlikely. */
+ || (is_gimple_call (gsi_stmt (gsi))
+ && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
+ {
+ found = true;
+ break;
+ }
+ if (found)
+ continue;
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Basic block %i is marked unlikely by backward prop\n",
+ bb->index);
+ bb->count = profile_count::zero ();
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!(e->probability == profile_probability::never ()))
+ {
+ if (!(e->src->count == profile_count::zero ()))
+ {
+ gcc_checking_assert (nsuccs[e->src->index] > 0);
+ nsuccs[e->src->index]--;
+ if (!nsuccs[e->src->index])
+ worklist.safe_push (e->src);
+ }
+ }
+ }
+ /* Finally all edges from non-0 regions to 0 are unlikely. */
+ FOR_ALL_BB_FN (bb, cfun)
+ if (!(bb->count == profile_count::zero ()))
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!(e->probability == profile_probability::never ())
+ && e->dest->count == profile_count::zero ())
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Edge %i->%i is unlikely because "
+ "it enters unlikely block\n",
+ bb->index, e->dest->index);
+ e->probability = profile_probability::never ();
+ }
+ if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
+ cgraph_node::get (current_function_decl)->count = profile_count::zero ();
+}
+
/* Estimate and propagate basic block frequencies using the given branch
probabilities. If FORCE is true, the frequencies are used to estimate
the counts even when there are already non-zero profile counts. */
basic_block bb;
sreal freq_max;
- if (force || profile_status_for_fn (cfun) != PROFILE_READ || !counts_to_freqs ())
+ determine_unlikely_bbs ();
+
+ if (force || profile_status_for_fn (cfun) != PROFILE_READ
+ || !update_max_bb_count ())
{
static int real_values_initialized = 0;
{
real_values_initialized = 1;
real_br_prob_base = REG_BR_PROB_BASE;
- real_bb_freq_max = BB_FREQ_MAX;
+ /* Scaling frequencies up to maximal profile count may result in
+ frequent overflows especially when inlining loops.
+ Small scalling results in unnecesary precision loss. Stay in
+ the half of the (exponential) range. */
+ real_bb_freq_max = (uint64_t)1 << (profile_count::n_bits / 2);
real_one_half = sreal (1, -1);
real_inv_br_prob_base = sreal (1) / real_br_prob_base;
real_almost_one = sreal (1) - real_inv_br_prob_base;
mark_dfs_back_edges ();
single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
- REG_BR_PROB_BASE;
+ profile_probability::always ();
/* Set up block info for each basic block. */
alloc_aux_for_blocks (sizeof (block_info));
FOR_EACH_EDGE (e, ei, bb->succs)
{
- EDGE_INFO (e)->back_edge_prob = e->probability;
+ /* FIXME: Graphite is producing edges with no profile. Once
+ this is fixed, drop this. */
+ if (e->probability.initialized_p ())
+ EDGE_INFO (e)->back_edge_prob
+ = e->probability.to_reg_br_prob_base ();
+ else
+ EDGE_INFO (e)->back_edge_prob = REG_BR_PROB_BASE / 2;
EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
}
}
freq_max = BLOCK_INFO (bb)->frequency;
freq_max = real_bb_freq_max / freq_max;
+ if (freq_max < 16)
+ freq_max = 16;
+ profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
+ cfun->cfg->count_max = profile_count::uninitialized ();
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
{
sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half;
- bb->frequency = tmp.to_int ();
+ profile_count count = profile_count::from_gcov_type (tmp.to_int ());
+
+ /* If we have profile feedback in which this function was never
+ executed, then preserve this info. */
+ if (!(bb->count == profile_count::zero ()))
+ bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
+ cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
}
free_aux_for_blocks ();
if (profile_status_for_fn (cfun) != PROFILE_READ)
{
int flags = flags_from_decl_or_type (current_function_decl);
- if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
- != NULL)
- node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
+ if ((ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ()
+ && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
+ || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
+ != NULL)
+ {
+ node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
+ warn_function_cold (current_function_decl);
+ }
else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
!= NULL)
node->frequency = NODE_FREQUENCY_HOT;
return;
}
- /* Only first time try to drop function into unlikely executed.
- After inlining the roundoff errors may confuse us.
- Ipa-profile pass will drop functions only called from unlikely
- functions to unlikely and that is most of what we care about. */
- if (!cfun->after_inlining)
- node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
+ node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
+ warn_function_cold (current_function_decl);
+ if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
+ return;
FOR_EACH_BB_FN (bb, cfun)
{
if (maybe_hot_bb_p (cfun, bb))
if (nb_loops > 1)
scev_initialize ();
- tree_estimate_probability ();
+ tree_estimate_probability (false);
if (nb_loops > 1)
scev_finalize ();
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->count.initialized_p ())
+ fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
+ loop->num,
+ (int)expected_loop_iterations_unbounded (loop));
+ }
return 0;
}
pass_strip_predict_hints::execute (function *fun)
{
basic_block bb;
- gimple ass_stmt;
+ gimple *ass_stmt;
tree var;
+ bool changed = false;
FOR_EACH_BB_FN (bb, fun)
{
gimple_stmt_iterator bi;
for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
{
- gimple stmt = gsi_stmt (bi);
+ gimple *stmt = gsi_stmt (bi);
if (gimple_code (stmt) == GIMPLE_PREDICT)
{
gsi_remove (&bi, true);
+ changed = true;
continue;
}
else if (is_gimple_call (stmt))
&& gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
{
var = gimple_call_lhs (stmt);
+ changed = true;
if (var)
{
ass_stmt
gsi_next (&bi);
}
}
- return 0;
+ return changed ? TODO_cleanup_cfg : 0;
}
} // anon namespace
which may also lead to frequencies incorrectly reduced to 0. There
is less precision in the probabilities, so we only do this for small
max counts. */
- gcov_type count_max = 0;
+ cfun->cfg->count_max = profile_count::uninitialized ();
basic_block bb;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
- count_max = MAX (bb->count, count_max);
+ cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
- if (profile_status_for_fn (cfun) == PROFILE_GUESSED
- || (!flag_auto_profile && profile_status_for_fn (cfun) == PROFILE_READ
- && count_max < REG_BR_PROB_BASE/10))
+ if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
{
loop_optimizer_init (0);
add_noreturn_fake_exit_edges ();
loop_optimizer_finalize ();
}
else if (profile_status_for_fn (cfun) == PROFILE_READ)
- counts_to_freqs ();
+ update_max_bb_count ();
else
gcc_unreachable ();
timevar_pop (TV_REBUILD_FREQUENCIES);
}
+
+/* Perform a dry run of the branch prediction pass and report comparsion of
+ the predicted and real profile into the dump file. */
+
+void
+report_predictor_hitrates (void)
+{
+ unsigned nb_loops;
+
+ loop_optimizer_init (LOOPS_NORMAL);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ flow_loops_dump (dump_file, NULL, 0);
+
+ mark_irreducible_loops ();
+
+ nb_loops = number_of_loops (cfun);
+ if (nb_loops > 1)
+ scev_initialize ();
+
+ tree_estimate_probability (true);
+
+ if (nb_loops > 1)
+ scev_finalize ();
+
+ loop_optimizer_finalize ();
+}
+
+/* Force edge E to be cold.
+ If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
+ keep low probability to represent possible error in a guess. This is used
+ i.e. in case we predict loop to likely iterate given number of times but
+ we are not 100% sure.
+
+ This function locally updates profile without attempt to keep global
+ consistency which can not be reached in full generality without full profile
+ rebuild from probabilities alone. Doing so is not necessarily a good idea
+ because frequencies and counts may be more realistic then probabilities.
+
+ In some cases (such as for elimination of early exits during full loop
+ unrolling) the caller can ensure that profile will get consistent
+ afterwards. */
+
+void
+force_edge_cold (edge e, bool impossible)
+{
+ profile_count count_sum = profile_count::zero ();
+ profile_probability prob_sum = profile_probability::never ();
+ edge_iterator ei;
+ edge e2;
+ bool uninitialized_exit = false;
+
+ /* When branch probability guesses are not known, then do nothing. */
+ if (!impossible && !e->count ().initialized_p ())
+ return;
+
+ profile_probability goal = (impossible ? profile_probability::never ()
+ : profile_probability::very_unlikely ());
+
+ /* If edge is already improbably or cold, just return. */
+ if (e->probability <= goal
+ && (!impossible || e->count () == profile_count::zero ()))
+ return;
+ FOR_EACH_EDGE (e2, ei, e->src->succs)
+ if (e2 != e)
+ {
+ if (e->flags & EDGE_FAKE)
+ continue;
+ if (e2->count ().initialized_p ())
+ count_sum += e2->count ();
+ if (e2->probability.initialized_p ())
+ prob_sum += e2->probability;
+ else
+ uninitialized_exit = true;
+ }
+
+ /* If we are not guessing profiles but have some other edges out,
+ just assume the control flow goes elsewhere. */
+ if (uninitialized_exit)
+ e->probability = goal;
+ /* If there are other edges out of e->src, redistribute probabilitity
+ there. */
+ else if (prob_sum > profile_probability::never ())
+ {
+ if (!(e->probability < goal))
+ e->probability = goal;
+
+ profile_probability prob_comp = prob_sum / e->probability.invert ();
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Making edge %i->%i %s by redistributing "
+ "probability to other edges.\n",
+ e->src->index, e->dest->index,
+ impossible ? "impossible" : "cold");
+ FOR_EACH_EDGE (e2, ei, e->src->succs)
+ if (e2 != e)
+ {
+ e2->probability /= prob_comp;
+ }
+ if (current_ir_type () != IR_GIMPLE
+ && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
+ update_br_prob_note (e->src);
+ }
+ /* If all edges out of e->src are unlikely, the basic block itself
+ is unlikely. */
+ else
+ {
+ if (prob_sum == profile_probability::never ())
+ e->probability = profile_probability::always ();
+ else
+ {
+ if (impossible)
+ e->probability = profile_probability::never ();
+ /* If BB has some edges out that are not impossible, we can not
+ assume that BB itself is. */
+ impossible = false;
+ }
+ if (current_ir_type () != IR_GIMPLE
+ && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
+ update_br_prob_note (e->src);
+ if (e->src->count == profile_count::zero ())
+ return;
+ if (count_sum == profile_count::zero () && impossible)
+ {
+ bool found = false;
+ if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
+ ;
+ else if (current_ir_type () == IR_GIMPLE)
+ for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
+ {
+ found = true;
+ break;
+ }
+ }
+ /* FIXME: Implement RTL path. */
+ else
+ found = true;
+ if (!found)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Making bb %i impossible and dropping count to 0.\n",
+ e->src->index);
+ e->src->count = profile_count::zero ();
+ FOR_EACH_EDGE (e2, ei, e->src->preds)
+ force_edge_cold (e2, impossible);
+ return;
+ }
+ }
+
+ /* If we did not adjusting, the source basic block has no likely edeges
+ leaving other direction. In that case force that bb cold, too.
+ This in general is difficult task to do, but handle special case when
+ BB has only one predecestor. This is common case when we are updating
+ after loop transforms. */
+ if (!(prob_sum > profile_probability::never ())
+ && count_sum == profile_count::zero ()
+ && single_pred_p (e->src) && e->src->count.to_frequency (cfun)
+ > (impossible ? 0 : 1))
+ {
+ int old_frequency = e->src->count.to_frequency (cfun);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
+ impossible ? "impossible" : "cold");
+ int new_frequency = MIN (e->src->count.to_frequency (cfun),
+ impossible ? 0 : 1);
+ if (impossible)
+ e->src->count = profile_count::zero ();
+ else
+ e->src->count = e->count ().apply_scale (new_frequency,
+ old_frequency);
+ force_edge_cold (single_pred_edge (e->src), 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 ? "impossible" : "cold");
+ }
+}
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Test that value range of predictor values defined in predict.def is
+ within range (50, 100]. */
+
+struct branch_predictor
+{
+ const char *name;
+ int probability;
+};
+
+#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
+
+static void
+test_prediction_value_range ()
+{
+ branch_predictor predictors[] = {
+#include "predict.def"
+ {NULL, -1U}
+ };
+
+ for (unsigned i = 0; predictors[i].name != NULL; i++)
+ {
+ if (predictors[i].probability == PROB_UNINITIALIZED)
+ continue;
+
+ unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
+ ASSERT_TRUE (p >= 50 && p <= 100);
+ }
+}
+
+#undef DEF_PREDICTOR
+
+/* Run all of the selfests within this file. */
+
+void
+predict_c_tests ()
+{
+ test_prediction_value_range ();
+}
+
+} // namespace selftest
+#endif /* CHECKING_P. */
projects / gcc.git / blobdiff