This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Beter analyzis of branch predictors
- To: rth at cygnus dot com, patches at x86-64 dot org, gcc-patches at gcc dot gnu dot org
- Subject: Beter analyzis of branch predictors
- From: Jan Hubicka <jh at suse dot cz>
- Date: Mon, 30 Jul 2001 21:17:11 +0200
Hi,
to compute values for predict.def files, we ought to use only cases,
the heuristic's outcome was actually used. This is the case of all
heuristics applying to the branch for DS theory and first heuristics
for first_match scheme used for loop branches.
This patch does the trick by adding an "(ignored)" to debug output for
ignored heuristics, so the line is not seen by abalyze_brprob, but still
I can figure what is going on.
I also added output for the DS theory separately, as it is not equivalent
to our combined heuristics and to catch cases no heuristic applies at
all.
Mon Jul 30 21:15:04 CEST 2001 Jan Hubicka <jh@suse.cz>
* 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.29
diff -c -3 -p -r1.29 predict.c
*** predict.c 2001/07/28 21:37:35 1.29
--- predict.c 2001/07/30 19:12:11
***************
*** 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 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 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 something, use
+ no_predictoin heuristic, in case we did matched, use eighter
+ 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.7
diff -c -3 -p -r1.7 predict.def
*** predict.def 2001/07/30 15:54:12 1.7
--- predict.def 2001/07/30 19:12:11
*************** 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). */
! /* An 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 applied. */
+ DEF_PREDICTOR (PRED_NO_PREDICTION, "no prediction", PROB_ALWAYS, 0)
/* Mark unconditional jump as taken. */
DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS,