1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 [1] "Branch Prediction for Free"
24 Ball and Larus; PLDI '93.
25 [2] "Static Branch Frequency and Program Profile Analysis"
26 Wu and Larus; MICRO-27.
27 [3] "Corpus-based Static Branch Prediction"
28 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
51 /* Random guesstimation given names. */
52 #define PROB_NEVER (0)
53 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
54 #define PROB_UNLIKELY (REG_BR_PROB_BASE * 4 / 10 - 1)
55 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
56 #define PROB_LIKELY (REG_BR_PROB_BASE - PROB_UNLIKELY)
57 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
58 #define PROB_ALWAYS (REG_BR_PROB_BASE)
60 static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
61 static void dump_prediction PARAMS ((enum br_predictor, int,
63 static void estimate_loops_at_level PARAMS ((struct loop *loop));
64 static void propagate_freq PARAMS ((basic_block));
65 static void estimate_bb_frequencies PARAMS ((struct loops *));
66 static void counts_to_freqs PARAMS ((void));
68 /* Information we hold about each branch predictor.
69 Filled using information from predict.def. */
72 const char *name; /* Name used in the debugging dumps. */
73 int hitrate; /* Expected hitrate used by
74 predict_insn_def call. */
77 #define DEF_PREDICTOR(ENUM, NAME, HITRATE) {NAME, HITRATE},
78 struct predictor_info predictor_info[] = {
79 #include "predict.def"
81 /* Upper bound on non-language-specific builtins. */
87 predict_insn (insn, predictor, probability)
90 enum br_predictor predictor;
92 if (!any_condjump_p (insn))
95 = gen_rtx_EXPR_LIST (REG_BR_PRED,
96 gen_rtx_CONCAT (VOIDmode,
97 GEN_INT ((int) predictor),
98 GEN_INT ((int) probability)),
102 /* Predict insn by given predictor. */
104 predict_insn_def (insn, predictor, taken)
106 enum br_predictor predictor;
107 enum prediction taken;
109 int probability = predictor_info[(int) predictor].hitrate;
111 probability = REG_BR_PROB_BASE - probability;
112 predict_insn (insn, predictor, probability);
115 /* Predict edge E with given probability if possible. */
117 predict_edge (e, predictor, probability)
120 enum br_predictor predictor;
123 last_insn = e->src->end;
125 /* We can store the branch prediction information only about
126 conditional jumps. */
127 if (!any_condjump_p (last_insn))
130 /* We always store probability of branching. */
131 if (e->flags & EDGE_FALLTHRU)
132 probability = REG_BR_PROB_BASE - probability;
134 predict_insn (last_insn, predictor, probability);
137 /* Predict edge E by given predictor if possible. */
139 predict_edge_def (e, predictor, taken)
141 enum br_predictor predictor;
142 enum prediction taken;
144 int probability = predictor_info[(int) predictor].hitrate;
147 probability = REG_BR_PROB_BASE - probability;
148 predict_edge (e, predictor, probability);
151 /* Invert all branch predictions or probability notes in the INSN. This needs
152 to be done each time we invert the condition used by the jump. */
154 invert_br_probabilities (insn)
157 rtx note = REG_NOTES (insn);
161 if (REG_NOTE_KIND (note) == REG_BR_PROB)
162 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
163 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
164 XEXP (XEXP (note, 0), 1)
165 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
166 note = XEXP (note, 1);
170 /* Dump information about the branch prediction to the output file. */
172 dump_prediction (predictor, probability, bb)
173 enum br_predictor predictor;
182 while (e->flags & EDGE_FALLTHRU)
185 fprintf (rtl_dump_file, " %s heuristics: %.1f%%",
186 predictor_info[predictor].name,
187 probability * 100.0 / REG_BR_PROB_BASE);
191 fprintf (rtl_dump_file, " exec ",
192 bb->count, e->count, e->count * 100.0 / bb->count);
193 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
194 (HOST_WIDEST_INT) bb->count);
195 fprintf (rtl_dump_file, " hit ",
196 e->count, e->count * 100.0 / bb->count);
197 fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
198 (HOST_WIDEST_INT) e->count);
199 fprintf (rtl_dump_file, " (%.1f%%)",
200 e->count, e->count * 100.0 / bb->count);
202 fprintf (rtl_dump_file, "\n");
205 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
206 note if not already present. Remove now useless REG_BR_PRED notes. */
208 combine_predictions_for_insn (insn, bb)
212 rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
213 rtx *pnote = ®_NOTES (insn);
214 int best_probability = PROB_EVEN;
215 int best_predictor = END_PREDICTORS;
218 fprintf (rtl_dump_file, "Predictions for insn %i\n", INSN_UID (insn));
220 /* We implement "first match" heuristics and use probability guessed
221 by predictor with smallest index. In future we will use better
222 probability combination techniques. */
225 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
227 int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
228 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
230 dump_prediction (predictor, probability, bb);
231 if (best_predictor > predictor)
232 best_probability = probability, best_predictor = predictor;
233 *pnote = XEXP (*pnote, 1);
236 pnote = &XEXP (*pnote, 1);
238 dump_prediction (PRED_FIRST_MATCH, best_probability, bb);
242 = gen_rtx_EXPR_LIST (REG_BR_PROB,
243 GEN_INT (best_probability), REG_NOTES (insn));
247 /* Statically estimate the probability that a branch will be taken.
248 ??? In the next revision there will be a number of other predictors added
249 from the above references. Further, each heuristic will be factored out
250 into its own function for clarity (and to facilitate the combination of
254 estimate_probability (loops_info)
255 struct loops *loops_info;
257 sbitmap *dominators, *post_dominators;
260 dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
261 post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
262 calculate_dominance_info (NULL, dominators, 0);
263 calculate_dominance_info (NULL, post_dominators, 1);
265 /* Try to predict out blocks in a loop that are not part of a
267 for (i = 0; i < loops_info->num; i++)
271 for (j = loops_info->array[i].first->index;
272 j <= loops_info->array[i].last->index;
275 if (TEST_BIT (loops_info->array[i].nodes, j))
277 int header_found = 0;
280 /* Loop branch heruistics - predict as taken an edge back to
282 for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
283 if (e->dest == loops_info->array[i].header)
286 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
288 /* Loop exit heruistics - predict as not taken an edge exiting
289 the loop if the conditinal has no loop header successors */
291 for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
292 if (e->dest->index <= 0
293 || !TEST_BIT (loops_info->array[i].nodes, e->dest->index))
294 predict_edge_def (e, PRED_LOOP_EXIT, NOT_TAKEN);
299 /* Attempt to predict conditional jumps using a number of heuristics.
300 For each conditional jump, we try each heuristic in a fixed order.
301 If more than one heuristic applies to a particular branch, the first
302 is used as the prediction for the branch. */
303 for (i = 0; i < n_basic_blocks; i++)
305 basic_block bb = BASIC_BLOCK (i);
306 rtx last_insn = bb->end;
310 /* If block has no sucessor, predict all possible paths to
311 it as improbable, as the block contains a call to a noreturn
312 function and thus can be executed only once. */
313 if (bb->succ == NULL)
316 for (y = 0; y < n_basic_blocks; y++)
317 if (!TEST_BIT (post_dominators[y], i))
319 for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
320 if (e->dest->index >= 0
321 && TEST_BIT (post_dominators[e->dest->index], i))
322 predict_edge_def (e, PRED_NORETURN, NOT_TAKEN);
326 if (GET_CODE (last_insn) != JUMP_INSN
327 || ! any_condjump_p (last_insn))
330 for (e = bb->succ; e; e = e->succ_next)
332 /* Predict edges to blocks that return immediately to be
333 improbable. These are usually used to signal error states. */
334 if (e->dest == EXIT_BLOCK_PTR
335 || (e->dest->succ && !e->dest->succ->succ_next
336 && e->dest->succ->dest == EXIT_BLOCK_PTR))
337 predict_edge_def (e, PRED_ERROR_RETURN, NOT_TAKEN);
339 /* Look for block we are guarding (ie we dominate it,
340 but it doesn't postdominate us). */
341 if (e->dest != EXIT_BLOCK_PTR
343 && TEST_BIT (dominators[e->dest->index], e->src->index)
344 && !TEST_BIT (post_dominators[e->src->index], e->dest->index))
347 /* The call heuristic claims that a guarded function call
348 is improbable. This is because such calls are often used
349 to signal exceptional situations such as printing error
351 for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end);
352 insn = NEXT_INSN (insn))
353 if (GET_CODE (insn) == CALL_INSN
354 /* Constant and pure calls are hardly used to signalize
355 something exceptional. */
356 && ! CONST_CALL_P (insn))
358 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
364 cond = get_condition (last_insn, &earliest);
368 /* Try "pointer heuristic."
369 A comparison ptr == 0 is predicted as false.
370 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
371 switch (GET_CODE (cond))
374 if (GET_CODE (XEXP (cond, 0)) == REG
375 && REG_POINTER (XEXP (cond, 0))
376 && (XEXP (cond, 1) == const0_rtx
377 || (GET_CODE (XEXP (cond, 1)) == REG
378 && REG_POINTER (XEXP (cond, 1)))))
380 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
383 if (GET_CODE (XEXP (cond, 0)) == REG
384 && REG_POINTER (XEXP (cond, 0))
385 && (XEXP (cond, 1) == const0_rtx
386 || (GET_CODE (XEXP (cond, 1)) == REG
387 && REG_POINTER (XEXP (cond, 1)))))
388 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
395 /* Try "opcode heuristic."
396 EQ tests are usually false and NE tests are usually true. Also,
397 most quantities are positive, so we can make the appropriate guesses
398 about signed comparisons against zero. */
399 switch (GET_CODE (cond))
402 /* Unconditional branch. */
403 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
404 cond == const0_rtx ? NOT_TAKEN : TAKEN);
409 predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
413 predict_insn_def (last_insn, PRED_OPCODE, TAKEN);
416 predict_insn_def (last_insn, PRED_OPCODE, TAKEN);
419 predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
423 if (XEXP (cond, 1) == const0_rtx
424 || (GET_CODE (XEXP (cond, 1)) == CONST_INT
425 && INTVAL (XEXP (cond, 1)) == -1))
426 predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
430 if (XEXP (cond, 1) == const0_rtx
431 || (GET_CODE (XEXP (cond, 1)) == CONST_INT
432 && INTVAL (XEXP (cond, 1)) == -1))
433 predict_insn_def (last_insn, PRED_OPCODE, TAKEN);
441 /* Attach the combined probability to each conditional jump. */
442 for (i = 0; i < n_basic_blocks; i++)
444 rtx last_insn = BLOCK_END (i);
446 if (GET_CODE (last_insn) != JUMP_INSN
447 || ! any_condjump_p (last_insn))
449 combine_predictions_for_insn (last_insn, BASIC_BLOCK (i));
451 sbitmap_vector_free (post_dominators);
452 sbitmap_vector_free (dominators);
454 estimate_bb_frequencies (loops_info);
457 /* __builtin_expect dropped tokens into the insn stream describing
458 expected values of registers. Generate branch probabilities
459 based off these values. */
462 expected_value_to_br_prob ()
464 rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
466 for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
468 switch (GET_CODE (insn))
471 /* Look for expected value notes. */
472 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
474 ev = NOTE_EXPECTED_VALUE (insn);
475 ev_reg = XEXP (ev, 0);
480 /* Never propagate across labels. */
485 /* Look for insns that clobber the EV register. */
486 if (ev && reg_set_p (ev_reg, insn))
491 /* Look for simple conditional branches. If we havn't got an
492 expected value yet, no point going further. */
493 if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX)
495 if (! any_condjump_p (insn))
500 /* Collect the branch condition, hopefully relative to EV_REG. */
501 /* ??? At present we'll miss things like
502 (expected_value (eq r70 0))
504 (set r80 (lt r70 r71))
505 (set pc (if_then_else (ne r80 0) ...))
506 as canonicalize_condition will render this to us as
508 Could use cselib to try and reduce this further. */
509 cond = XEXP (SET_SRC (PATTERN (insn)), 0);
510 cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
512 || XEXP (cond, 0) != ev_reg
513 || GET_CODE (XEXP (cond, 1)) != CONST_INT)
516 /* Substitute and simplify. Given that the expression we're
517 building involves two constants, we should wind up with either
519 cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
520 XEXP (ev, 1), XEXP (cond, 1));
521 cond = simplify_rtx (cond);
523 /* Turn the condition into a scaled branch probability. */
524 if (cond != const1_rtx && cond != const0_rtx)
526 predict_insn_def (insn, PRED_BUILTIN_EXPECT,
527 cond == const1_rtx ? TAKEN : NOT_TAKEN);
531 /* This is used to carry information about basic blocks. It is
532 attached to the AUX field of the standard CFG block. */
534 typedef struct block_info_def
536 /* Estimated frequency of execution of basic_block. */
539 /* To keep queue of basic blocks to process. */
542 /* True if block already converted. */
546 /* Similar information for edges. */
547 typedef struct edge_info_def
549 /* In case edge is an loopback edge, the probability edge will be reached
550 in case header is. Estimated number of iterations of the loop can be
551 then computed as 1 / (1 - back_edge_prob). */
552 double back_edge_prob;
553 /* True if the edge is an loopback edge in the natural loop. */
557 #define BLOCK_INFO(B) ((block_info) (B)->aux)
558 #define EDGE_INFO(E) ((edge_info) (E)->aux)
560 /* Helper function for estimate_bb_frequencies.
561 Propagate the frequencies for loops headed by HEAD. */
563 propagate_freq (head)
566 basic_block bb = head;
567 basic_block last = bb;
571 BLOCK_INFO (head)->frequency = 1;
572 for (; bb; bb = nextbb)
574 double cyclic_probability = 0, frequency = 0;
576 nextbb = BLOCK_INFO (bb)->next;
577 BLOCK_INFO (bb)->next = NULL;
579 /* Compute frequency of basic block. */
582 for (e = bb->pred; e; e = e->pred_next)
583 if (!BLOCK_INFO (e->src)->visited && !EDGE_INFO (e)->back_edge)
586 for (e = bb->pred; e; e = e->pred_next)
587 if (EDGE_INFO (e)->back_edge)
588 cyclic_probability += EDGE_INFO (e)->back_edge_prob;
590 frequency += (e->probability
591 * BLOCK_INFO (e->src)->frequency /
594 if (cyclic_probability > 1.0 - 1.0 / REG_BR_PROB_BASE)
595 cyclic_probability = 1.0 - 1.0 / REG_BR_PROB_BASE;
597 BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability);
600 BLOCK_INFO (bb)->visited = 1;
602 /* Compute back edge frequencies. */
603 for (e = bb->succ; e; e = e->succ_next)
605 EDGE_INFO (e)->back_edge_prob = (e->probability
606 * BLOCK_INFO (bb)->frequency
609 /* Propagate to succesor blocks. */
610 for (e = bb->succ; e; e = e->succ_next)
611 if (!EDGE_INFO (e)->back_edge
612 && !BLOCK_INFO (e->dest)->visited
613 && !BLOCK_INFO (e->dest)->next && e->dest != last)
618 BLOCK_INFO (last)->next = e->dest;
624 /* Estimate probabilities of the loopback edges in loops at same nest level. */
626 estimate_loops_at_level (first_loop)
627 struct loop *first_loop;
629 struct loop *l, *loop = first_loop;
631 for (loop = first_loop; loop; loop = loop->next)
636 estimate_loops_at_level (loop->inner);
638 /* find current loop back edge and mark it. */
639 for (e = loop->latch->succ; e->dest != loop->header; e = e->succ_next);
641 EDGE_INFO (e)->back_edge = 1;
643 /* In case loop header is shared, ensure that it is the last one sharing
644 same header, so we avoid redundant work. */
647 for (l = loop->next; l; l = l->next)
648 if (l->header == loop->header)
654 /* Now merge all nodes of all loops with given header as not visited. */
655 for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next)
656 if (loop->header == l->header)
657 EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n,
658 BLOCK_INFO (BASIC_BLOCK (n))->visited =
660 propagate_freq (loop->header);
664 /* Convert counts measured by profile driven feedback to frequencies. */
668 HOST_WIDEST_INT count_max = 1;
671 for (i = 0; i < n_basic_blocks; i++)
672 if (BASIC_BLOCK (i)->count > count_max)
673 count_max = BASIC_BLOCK (i)->count;
675 for (i = -2; i < n_basic_blocks; i++)
679 bb = ENTRY_BLOCK_PTR;
683 bb = BASIC_BLOCK (i);
684 bb->frequency = ((bb->count * BB_FREQ_MAX + count_max / 2)
689 /* Estimate basic blocks frequency by given branch probabilities. */
691 estimate_bb_frequencies (loops)
700 if (flag_branch_probabilities)
706 /* Fill in the probability values in flowgraph based on the REG_BR_PROB
708 for (i = 0; i < n_basic_blocks; i++)
710 rtx last_insn = BLOCK_END (i);
712 edge fallthru, branch;
714 if (GET_CODE (last_insn) != JUMP_INSN || !any_condjump_p (last_insn)
715 /* Avoid handling of conditionals jump jumping to fallthru edge. */
716 || BASIC_BLOCK (i)->succ->succ_next == NULL)
718 /* We can predict only conditional jumps at the moment.
719 Expect each edge to be equall probable.
720 ?? In future we want to make abnormal edges improbable. */
724 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
727 if (e->probability != 0)
731 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
732 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
736 probability = INTVAL (XEXP (find_reg_note (last_insn,
737 REG_BR_PROB, 0), 0));
738 fallthru = BASIC_BLOCK (i)->succ;
739 if (!fallthru->flags & EDGE_FALLTHRU)
740 fallthru = fallthru->succ_next;
741 branch = BASIC_BLOCK (i)->succ;
742 if (branch->flags & EDGE_FALLTHRU)
743 branch = branch->succ_next;
745 branch->probability = probability;
746 fallthru->probability = REG_BR_PROB_BASE - probability;
749 ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
751 /* Set up block info for each basic block. */
752 bi = (block_info) xcalloc ((n_basic_blocks + 2), sizeof (*bi));
753 ei = (edge_info) xcalloc ((n_edges), sizeof (*ei));
754 for (i = -2; i < n_basic_blocks; i++)
760 bb = ENTRY_BLOCK_PTR;
764 bb = BASIC_BLOCK (i);
765 bb->aux = bi + i + 2;
766 BLOCK_INFO (bb)->visited = 1;
767 for (e = bb->succ; e; e = e->succ_next)
769 e->aux = ei + edgenum, edgenum++;
770 EDGE_INFO (e)->back_edge_prob = ((double) e->probability
774 /* First compute probabilities locally for each loop from innermost
775 to outermost to examine probabilities for back edges. */
776 estimate_loops_at_level (loops->tree);
778 /* Now fake loop around whole function to finalize probabilities. */
779 for (i = 0; i < n_basic_blocks; i++)
780 BLOCK_INFO (BASIC_BLOCK (i))->visited = 0;
781 BLOCK_INFO (ENTRY_BLOCK_PTR)->visited = 0;
782 BLOCK_INFO (EXIT_BLOCK_PTR)->visited = 0;
783 propagate_freq (ENTRY_BLOCK_PTR);
785 for (i = 0; i < n_basic_blocks; i++)
786 if (BLOCK_INFO (BASIC_BLOCK (i))->frequency > freq_max)
787 freq_max = BLOCK_INFO (BASIC_BLOCK (i))->frequency;
788 for (i = -2; i < n_basic_blocks; i++)
792 bb = ENTRY_BLOCK_PTR;
796 bb = BASIC_BLOCK (i);
797 bb->frequency = (BLOCK_INFO (bb)->frequency * BB_FREQ_MAX / freq_max