This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Branch predictors debug output take II
- To: gcc-patches at gcc dot gnu dot org, rth at cygnus dot com
- Subject: Branch predictors debug output take II
- From: Jan Hubicka <jh at suse dot cz>
- Date: Sun, 12 Aug 2001 23:01:50 +0200
Hi,
while investigating the purpose of recent degradation in spec2000 tests,
I cleaned up the attached unreviewed patch to improve debuggin output of
branch predictors.
The problem is not related to branch predictors, but still I would like to
see this patch reviewed, as it is important to tune them well.
Honza
* predict.c (dump_prediction): New argument "USED".
(combine_predictions_for_insn): Determine the used heuristics,
output the case no heuristic applied.
* predict.def (PRED_DS_THEORY, PRED_NO_HEURISTIC): New.
Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.32
diff -c -3 -p -r1.32 predict.c
*** predict.c 2001/08/09 13:23:01 1.32
--- predict.c 2001/08/12 20:58:38
***************
*** 59,65 ****
static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
static void dump_prediction PARAMS ((enum br_predictor, int,
! basic_block));
static void estimate_loops_at_level PARAMS ((struct loop *loop));
static void propagate_freq PARAMS ((basic_block));
static void estimate_bb_frequencies PARAMS ((struct loops *));
--- 59,65 ----
static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
static void dump_prediction PARAMS ((enum br_predictor, int,
! basic_block, bool));
static void estimate_loops_at_level PARAMS ((struct loop *loop));
static void propagate_freq PARAMS ((basic_block));
static void estimate_bb_frequencies PARAMS ((struct loops *));
*************** invert_br_probabilities (insn)
*** 178,187 ****
/* Dump information about the branch prediction to the output file. */
static void
! dump_prediction (predictor, probability, bb)
enum br_predictor predictor;
int probability;
basic_block bb;
{
edge e = bb->succ;
--- 178,188 ----
/* Dump information about the branch prediction to the output file. */
static void
! dump_prediction (predictor, probability, bb, used)
enum br_predictor predictor;
int probability;
basic_block bb;
+ bool used;
{
edge e = bb->succ;
*************** dump_prediction (predictor, probability,
*** 191,198 ****
while (e->flags & EDGE_FALLTHRU)
e = e->succ_next;
! fprintf (rtl_dump_file, " %s heuristics: %.1f%%",
predictor_info[predictor].name,
probability * 100.0 / REG_BR_PROB_BASE);
if (bb->count)
--- 192,200 ----
while (e->flags & EDGE_FALLTHRU)
e = e->succ_next;
! fprintf (rtl_dump_file, " %s heuristics%s: %.1f%%",
predictor_info[predictor].name,
+ used ? "" : " (ignored)",
probability * 100.0 / REG_BR_PROB_BASE);
if (bb->count)
*************** combine_predictions_for_insn (insn, bb)
*** 218,227 ****
--- 220,232 ----
{
rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
rtx *pnote = ®_NOTES (insn);
+ rtx note = REG_NOTES (insn);
int best_probability = PROB_EVEN;
int best_predictor = END_PREDICTORS;
int combined_probability = REG_BR_PROB_BASE / 2;
int d;
+ bool first_match = false;
+ bool found = false;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
*************** combine_predictions_for_insn (insn, bb)
*** 230,246 ****
/* We implement "first match" heuristics and use probability guessed
by predictor with smallest index. In the future we will use better
probability combination techniques. */
! while (*pnote)
{
! if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
{
! int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
! int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
! dump_prediction (predictor, probability, bb);
if (best_predictor > predictor)
best_probability = probability, best_predictor = predictor;
- *pnote = XEXP (*pnote, 1);
d = (combined_probability * probability
+ (REG_BR_PROB_BASE - combined_probability)
--- 235,250 ----
/* We implement "first match" heuristics and use probability guessed
by predictor with smallest index. In the future we will use better
probability combination techniques. */
! while (note)
{
! if (REG_NOTE_KIND (note) == REG_BR_PRED)
{
! int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
! int probability = INTVAL (XEXP (XEXP (note, 0), 1));
! found = true;
if (best_predictor > predictor)
best_probability = probability, best_predictor = predictor;
d = (combined_probability * probability
+ (REG_BR_PROB_BASE - combined_probability)
*************** combine_predictions_for_insn (insn, bb)
*** 249,261 ****
combined_probability = (((double)combined_probability) * probability
* REG_BR_PROB_BASE / d + 0.5);
}
! else
! pnote = &XEXP (*pnote, 1);
}
if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
combined_probability = best_probability;
! dump_prediction (PRED_FIRST_MATCH, best_probability, bb);
! dump_prediction (PRED_COMBINED, combined_probability, bb);
if (!prob_note)
{
REG_NOTES (insn)
--- 253,295 ----
combined_probability = (((double)combined_probability) * probability
* REG_BR_PROB_BASE / d + 0.5);
}
! note = XEXP (note, 1);
}
+
+ /* Decide heuristic to use. In case we didn't match anything, 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)
+ first_match = true;
+
+ if (!found)
+ dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true);
+ else
+ {
+ dump_prediction (PRED_DS_THEORY, combined_probability, bb,
+ !first_match);
+ dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match);
+ }
+
+ if (first_match)
combined_probability = best_probability;
! dump_prediction (PRED_COMBINED, combined_probability, bb, true);
!
! while (*pnote)
! {
! if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
! {
! int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
! int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
!
! dump_prediction (predictor, probability, bb,
! !first_match || best_predictor == predictor);
! *pnote = XEXP (*pnote, 1);
! }
! else
! pnote = &XEXP (*pnote, 1);
! }
if (!prob_note)
{
REG_NOTES (insn)
Index: predict.def
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.def,v
retrieving revision 1.8
diff -c -3 -p -r1.8 predict.def
*** predict.def 2001/08/08 16:46:22 1.8
--- predict.def 2001/08/12 20:58:38
*************** Boston, MA 02111-1307, USA. */
*** 36,47 ****
REG_BR_PROB_BASE / 2). */
! /* An combined heuristics using Dempster-Shaffer theory. */
DEF_PREDICTOR (PRED_COMBINED, "combined", PROB_ALWAYS, 0)
/* An combined heuristics using probability determined by first
matching heuristics from this list. */
DEF_PREDICTOR (PRED_FIRST_MATCH, "first match", PROB_ALWAYS, 0)
/* Mark unconditional jump as taken. */
DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS,
--- 36,53 ----
REG_BR_PROB_BASE / 2). */
! /* A value used as final outcome of all heuristics. */
DEF_PREDICTOR (PRED_COMBINED, "combined", PROB_ALWAYS, 0)
+ /* An outcome estimated by Dempster-Shaffer theory. */
+ DEF_PREDICTOR (PRED_DS_THEORY, "DS theory", PROB_ALWAYS, 0)
+
/* An combined heuristics using probability determined by first
matching heuristics from this list. */
DEF_PREDICTOR (PRED_FIRST_MATCH, "first match", PROB_ALWAYS, 0)
+
+ /* Heuristic applying when no heuristic bellow applies. */
+ DEF_PREDICTOR (PRED_NO_PREDICTION, "no prediction", PROB_ALWAYS, 0)
/* Mark unconditional jump as taken. */
DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS,