1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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. */
33 #include "coretypes.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
57 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
58 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
59 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
60 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
62 /* Random guesstimation given names. */
63 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
64 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
65 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
66 #define PROB_ALWAYS (REG_BR_PROB_BASE)
68 static bool predicted_by_p (basic_block
, enum br_predictor
);
69 static void combine_predictions_for_insn (rtx
, basic_block
);
70 static void dump_prediction (enum br_predictor
, int, basic_block
, int);
71 static void estimate_loops_at_level (struct loop
*loop
);
72 static void propagate_freq (struct loop
*);
73 static void estimate_bb_frequencies (struct loops
*);
74 static void counts_to_freqs (void);
75 static void process_note_predictions (basic_block
, int *);
76 static void process_note_prediction (basic_block
, int *, int, int);
77 static bool last_basic_block_p (basic_block
);
78 static void compute_function_frequency (void);
79 static void choose_function_section (void);
80 static bool can_predict_insn_p (rtx
);
82 /* Information we hold about each branch predictor.
83 Filled using information from predict.def. */
87 const char *const name
; /* Name used in the debugging dumps. */
88 const int hitrate
; /* Expected hitrate used by
89 predict_insn_def call. */
93 /* Use given predictor without Dempster-Shaffer theory if it matches
94 using first_match heuristics. */
95 #define PRED_FLAG_FIRST_MATCH 1
97 /* Recompute hitrate in percent to our representation. */
99 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
101 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
102 static const struct predictor_info predictor_info
[]= {
103 #include "predict.def"
105 /* Upper bound on predictors. */
110 /* Return true in case BB can be CPU intensive and should be optimized
111 for maximal performance. */
114 maybe_hot_bb_p (basic_block bb
)
116 if (profile_info
&& flag_branch_probabilities
118 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
120 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
125 /* Return true in case BB is cold and should be optimized for size. */
128 probably_cold_bb_p (basic_block bb
)
130 if (profile_info
&& flag_branch_probabilities
132 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
134 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
139 /* Return true in case BB is probably never executed. */
141 probably_never_executed_bb_p (basic_block bb
)
143 if (profile_info
&& flag_branch_probabilities
)
144 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
148 /* Return true if the one of outgoing edges is already predicted by
152 predicted_by_p (basic_block bb
, enum br_predictor predictor
)
155 if (!INSN_P (BB_END (bb
)))
157 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
158 if (REG_NOTE_KIND (note
) == REG_BR_PRED
159 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
165 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
167 if (!any_condjump_p (insn
))
169 if (!flag_guess_branch_prob
)
173 = gen_rtx_EXPR_LIST (REG_BR_PRED
,
174 gen_rtx_CONCAT (VOIDmode
,
175 GEN_INT ((int) predictor
),
176 GEN_INT ((int) probability
)),
180 /* Predict insn by given predictor. */
183 predict_insn_def (rtx insn
, enum br_predictor predictor
,
184 enum prediction taken
)
186 int probability
= predictor_info
[(int) predictor
].hitrate
;
189 probability
= REG_BR_PROB_BASE
- probability
;
191 predict_insn (insn
, predictor
, probability
);
194 /* Predict edge E with given probability if possible. */
197 predict_edge (edge e
, enum br_predictor predictor
, int probability
)
200 last_insn
= BB_END (e
->src
);
202 /* We can store the branch prediction information only about
203 conditional jumps. */
204 if (!any_condjump_p (last_insn
))
207 /* We always store probability of branching. */
208 if (e
->flags
& EDGE_FALLTHRU
)
209 probability
= REG_BR_PROB_BASE
- probability
;
211 predict_insn (last_insn
, predictor
, probability
);
214 /* Return true when we can store prediction on insn INSN.
215 At the moment we represent predictions only on conditional
216 jumps, not at computed jump or other complicated cases. */
218 can_predict_insn_p (rtx insn
)
220 return (GET_CODE (insn
) == JUMP_INSN
221 && any_condjump_p (insn
)
222 && BLOCK_FOR_INSN (insn
)->succ
->succ_next
);
225 /* Predict edge E by given predictor if possible. */
228 predict_edge_def (edge e
, enum br_predictor predictor
,
229 enum prediction taken
)
231 int probability
= predictor_info
[(int) predictor
].hitrate
;
234 probability
= REG_BR_PROB_BASE
- probability
;
236 predict_edge (e
, predictor
, probability
);
239 /* Invert all branch predictions or probability notes in the INSN. This needs
240 to be done each time we invert the condition used by the jump. */
243 invert_br_probabilities (rtx insn
)
247 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
248 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
249 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
250 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
251 XEXP (XEXP (note
, 0), 1)
252 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
255 /* Dump information about the branch prediction to the output file. */
258 dump_prediction (enum br_predictor predictor
, int probability
,
259 basic_block bb
, int used
)
266 while (e
&& (e
->flags
& EDGE_FALLTHRU
))
269 fprintf (rtl_dump_file
, " %s heuristics%s: %.1f%%",
270 predictor_info
[predictor
].name
,
271 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
275 fprintf (rtl_dump_file
, " exec ");
276 fprintf (rtl_dump_file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
279 fprintf (rtl_dump_file
, " hit ");
280 fprintf (rtl_dump_file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
281 fprintf (rtl_dump_file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
285 fprintf (rtl_dump_file
, "\n");
288 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
289 note if not already present. Remove now useless REG_BR_PRED notes. */
292 combine_predictions_for_insn (rtx insn
, basic_block bb
)
294 rtx prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
295 rtx
*pnote
= ®_NOTES (insn
);
297 int best_probability
= PROB_EVEN
;
298 int best_predictor
= END_PREDICTORS
;
299 int combined_probability
= REG_BR_PROB_BASE
/ 2;
301 bool first_match
= false;
305 fprintf (rtl_dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
308 /* We implement "first match" heuristics and use probability guessed
309 by predictor with smallest index. In the future we will use better
310 probability combination techniques. */
311 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
312 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
314 int predictor
= INTVAL (XEXP (XEXP (note
, 0), 0));
315 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
318 if (best_predictor
> predictor
)
319 best_probability
= probability
, best_predictor
= predictor
;
321 d
= (combined_probability
* probability
322 + (REG_BR_PROB_BASE
- combined_probability
)
323 * (REG_BR_PROB_BASE
- probability
));
325 /* Use FP math to avoid overflows of 32bit integers. */
327 /* If one probability is 0% and one 100%, avoid division by zero. */
328 combined_probability
= REG_BR_PROB_BASE
/ 2;
330 combined_probability
= (((double) combined_probability
) * probability
331 * REG_BR_PROB_BASE
/ d
+ 0.5);
334 /* Decide which heuristic to use. In case we didn't match anything,
335 use no_prediction heuristic, in case we did match, use either
336 first match or Dempster-Shaffer theory depending on the flags. */
338 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
342 dump_prediction (PRED_NO_PREDICTION
, combined_probability
, bb
, true);
345 dump_prediction (PRED_DS_THEORY
, combined_probability
, bb
, !first_match
);
346 dump_prediction (PRED_FIRST_MATCH
, best_probability
, bb
, first_match
);
350 combined_probability
= best_probability
;
351 dump_prediction (PRED_COMBINED
, combined_probability
, bb
, true);
355 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
357 int predictor
= INTVAL (XEXP (XEXP (*pnote
, 0), 0));
358 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
360 dump_prediction (predictor
, probability
, bb
,
361 !first_match
|| best_predictor
== predictor
);
362 *pnote
= XEXP (*pnote
, 1);
365 pnote
= &XEXP (*pnote
, 1);
371 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
372 GEN_INT (combined_probability
), REG_NOTES (insn
));
374 /* Save the prediction into CFG in case we are seeing non-degenerated
376 if (bb
->succ
->succ_next
)
378 BRANCH_EDGE (bb
)->probability
= combined_probability
;
379 FALLTHRU_EDGE (bb
)->probability
380 = REG_BR_PROB_BASE
- combined_probability
;
385 /* Statically estimate the probability that a branch will be taken.
386 ??? In the next revision there will be a number of other predictors added
387 from the above references. Further, each heuristic will be factored out
388 into its own function for clarity (and to facilitate the combination of
392 estimate_probability (struct loops
*loops_info
)
397 connect_infinite_loops_to_exit ();
398 calculate_dominance_info (CDI_DOMINATORS
);
399 calculate_dominance_info (CDI_POST_DOMINATORS
);
401 /* Try to predict out blocks in a loop that are not part of a
403 for (i
= 1; i
< loops_info
->num
; i
++)
405 basic_block bb
, *bbs
;
408 struct loop
*loop
= loops_info
->parray
[i
];
409 struct loop_desc desc
;
410 unsigned HOST_WIDE_INT niter
;
412 flow_loop_scan (loop
, LOOP_EXIT_EDGES
);
413 exits
= loop
->num_exits
;
415 if (simple_loop_p (loop
, &desc
) && desc
.const_iter
)
418 niter
= desc
.niter
+ 1;
419 if (niter
== 0) /* We might overflow here. */
422 prob
= (REG_BR_PROB_BASE
423 - (REG_BR_PROB_BASE
+ niter
/2) / niter
);
424 /* Branch prediction algorithm gives 0 frequency for everything
425 after the end of loop for loop having 0 probability to finish. */
426 if (prob
== REG_BR_PROB_BASE
)
427 prob
= REG_BR_PROB_BASE
- 1;
428 predict_edge (desc
.in_edge
, PRED_LOOP_ITERATIONS
,
432 bbs
= get_loop_body (loop
);
433 for (j
= 0; j
< loop
->num_nodes
; j
++)
435 int header_found
= 0;
440 /* Bypass loop heuristics on continue statement. These
441 statements construct loops via "non-loop" constructs
442 in the source language and are better to be handled
444 if (!can_predict_insn_p (BB_END (bb
))
445 || predicted_by_p (bb
, PRED_CONTINUE
))
448 /* Loop branch heuristics - predict an edge back to a
449 loop's head as taken. */
450 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
451 if (e
->dest
== loop
->header
452 && e
->src
== loop
->latch
)
455 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
458 /* Loop exit heuristics - predict an edge exiting the loop if the
459 conditional has no loop header successors as not taken. */
461 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
462 if (e
->dest
->index
< 0
463 || !flow_bb_inside_loop_p (loop
, e
->dest
))
467 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
472 /* Attempt to predict conditional jumps using a number of heuristics. */
475 rtx last_insn
= BB_END (bb
);
479 if (! can_predict_insn_p (last_insn
))
482 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
484 /* Predict early returns to be probable, as we've already taken
485 care for error returns and other are often used for fast paths
487 if ((e
->dest
== EXIT_BLOCK_PTR
488 || (e
->dest
->succ
&& !e
->dest
->succ
->succ_next
489 && e
->dest
->succ
->dest
== EXIT_BLOCK_PTR
))
490 && !predicted_by_p (bb
, PRED_NULL_RETURN
)
491 && !predicted_by_p (bb
, PRED_CONST_RETURN
)
492 && !predicted_by_p (bb
, PRED_NEGATIVE_RETURN
)
493 && !last_basic_block_p (e
->dest
))
494 predict_edge_def (e
, PRED_EARLY_RETURN
, TAKEN
);
496 /* Look for block we are guarding (ie we dominate it,
497 but it doesn't postdominate us). */
498 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
499 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
500 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
504 /* The call heuristic claims that a guarded function call
505 is improbable. This is because such calls are often used
506 to signal exceptional situations such as printing error
508 for (insn
= BB_HEAD (e
->dest
); insn
!= NEXT_INSN (BB_END (e
->dest
));
509 insn
= NEXT_INSN (insn
))
510 if (GET_CODE (insn
) == CALL_INSN
511 /* Constant and pure calls are hardly used to signalize
512 something exceptional. */
513 && ! CONST_OR_PURE_CALL_P (insn
))
515 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
521 cond
= get_condition (last_insn
, &earliest
, false);
525 /* Try "pointer heuristic."
526 A comparison ptr == 0 is predicted as false.
527 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
528 if (GET_RTX_CLASS (GET_CODE (cond
)) == '<'
529 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
530 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
532 if (GET_CODE (cond
) == EQ
)
533 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
534 else if (GET_CODE (cond
) == NE
)
535 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
539 /* Try "opcode heuristic."
540 EQ tests are usually false and NE tests are usually true. Also,
541 most quantities are positive, so we can make the appropriate guesses
542 about signed comparisons against zero. */
543 switch (GET_CODE (cond
))
546 /* Unconditional branch. */
547 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
548 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
553 /* Floating point comparisons appears to behave in a very
554 unpredictable way because of special role of = tests in
556 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
558 /* Comparisons with 0 are often used for booleans and there is
559 nothing useful to predict about them. */
560 else if (XEXP (cond
, 1) == const0_rtx
561 || XEXP (cond
, 0) == const0_rtx
)
564 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
569 /* Floating point comparisons appears to behave in a very
570 unpredictable way because of special role of = tests in
572 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
574 /* Comparisons with 0 are often used for booleans and there is
575 nothing useful to predict about them. */
576 else if (XEXP (cond
, 1) == const0_rtx
577 || XEXP (cond
, 0) == const0_rtx
)
580 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
584 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
588 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
593 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
594 || XEXP (cond
, 1) == constm1_rtx
)
595 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
600 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
601 || XEXP (cond
, 1) == constm1_rtx
)
602 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
610 /* Attach the combined probability to each conditional jump. */
612 if (GET_CODE (BB_END (bb
)) == JUMP_INSN
613 && any_condjump_p (BB_END (bb
))
614 && bb
->succ
->succ_next
!= NULL
)
615 combine_predictions_for_insn (BB_END (bb
), bb
);
617 free_dominance_info (CDI_POST_DOMINATORS
);
619 remove_fake_edges ();
620 estimate_bb_frequencies (loops_info
);
623 /* __builtin_expect dropped tokens into the insn stream describing expected
624 values of registers. Generate branch probabilities based off these
628 expected_value_to_br_prob (void)
630 rtx insn
, cond
, ev
= NULL_RTX
, ev_reg
= NULL_RTX
;
632 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
634 switch (GET_CODE (insn
))
637 /* Look for expected value notes. */
638 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EXPECTED_VALUE
)
640 ev
= NOTE_EXPECTED_VALUE (insn
);
641 ev_reg
= XEXP (ev
, 0);
647 /* Never propagate across labels. */
652 /* Look for simple conditional branches. If we haven't got an
653 expected value yet, no point going further. */
654 if (GET_CODE (insn
) != JUMP_INSN
|| ev
== NULL_RTX
655 || ! any_condjump_p (insn
))
660 /* Look for insns that clobber the EV register. */
661 if (ev
&& reg_set_p (ev_reg
, insn
))
666 /* Collect the branch condition, hopefully relative to EV_REG. */
667 /* ??? At present we'll miss things like
668 (expected_value (eq r70 0))
670 (set r80 (lt r70 r71))
671 (set pc (if_then_else (ne r80 0) ...))
672 as canonicalize_condition will render this to us as
674 Could use cselib to try and reduce this further. */
675 cond
= XEXP (SET_SRC (pc_set (insn
)), 0);
676 cond
= canonicalize_condition (insn
, cond
, 0, NULL
, ev_reg
, false);
677 if (! cond
|| XEXP (cond
, 0) != ev_reg
678 || GET_CODE (XEXP (cond
, 1)) != CONST_INT
)
681 /* Substitute and simplify. Given that the expression we're
682 building involves two constants, we should wind up with either
684 cond
= gen_rtx_fmt_ee (GET_CODE (cond
), VOIDmode
,
685 XEXP (ev
, 1), XEXP (cond
, 1));
686 cond
= simplify_rtx (cond
);
688 /* Turn the condition into a scaled branch probability. */
689 if (cond
!= const_true_rtx
&& cond
!= const0_rtx
)
691 predict_insn_def (insn
, PRED_BUILTIN_EXPECT
,
692 cond
== const_true_rtx
? TAKEN
: NOT_TAKEN
);
696 /* Check whether this is the last basic block of function. Commonly
697 there is one extra common cleanup block. */
699 last_basic_block_p (basic_block bb
)
701 if (bb
== EXIT_BLOCK_PTR
)
704 return (bb
->next_bb
== EXIT_BLOCK_PTR
705 || (bb
->next_bb
->next_bb
== EXIT_BLOCK_PTR
706 && bb
->succ
&& !bb
->succ
->succ_next
707 && bb
->succ
->dest
->next_bb
== EXIT_BLOCK_PTR
));
710 /* Sets branch probabilities according to PREDiction and
711 FLAGS. HEADS[bb->index] should be index of basic block in that we
712 need to alter branch predictions (i.e. the first of our dominators
713 such that we do not post-dominate it) (but we fill this information
714 on demand, so -1 may be there in case this was not needed yet). */
717 process_note_prediction (basic_block bb
, int *heads
, int pred
, int flags
)
723 taken
= flags
& IS_TAKEN
;
725 if (heads
[bb
->index
] < 0)
727 /* This is first time we need this field in heads array; so
728 find first dominator that we do not post-dominate (we are
729 using already known members of heads array). */
731 basic_block next_ai
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
734 while (heads
[next_ai
->index
] < 0)
736 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
738 heads
[next_ai
->index
] = ai
->index
;
740 next_ai
= get_immediate_dominator (CDI_DOMINATORS
, next_ai
);
742 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
743 head
= next_ai
->index
;
745 head
= heads
[next_ai
->index
];
746 while (next_ai
!= bb
)
749 if (heads
[ai
->index
] == ENTRY_BLOCK
)
750 ai
= ENTRY_BLOCK_PTR
;
752 ai
= BASIC_BLOCK (heads
[ai
->index
]);
753 heads
[next_ai
->index
] = head
;
756 y
= heads
[bb
->index
];
758 /* Now find the edge that leads to our branch and aply the prediction. */
760 if (y
== last_basic_block
|| !can_predict_insn_p (BB_END (BASIC_BLOCK (y
))))
762 for (e
= BASIC_BLOCK (y
)->succ
; e
; e
= e
->succ_next
)
763 if (e
->dest
->index
>= 0
764 && dominated_by_p (CDI_POST_DOMINATORS
, e
->dest
, bb
))
765 predict_edge_def (e
, pred
, taken
);
768 /* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them
769 into branch probabilities. For description of heads array, see
770 process_note_prediction. */
773 process_note_predictions (basic_block bb
, int *heads
)
778 /* Additionally, we check here for blocks with no successors. */
779 int contained_noreturn_call
= 0;
781 int noreturn_block
= 1;
783 for (insn
= BB_END (bb
); insn
;
784 was_bb_head
|= (insn
== BB_HEAD (bb
)), insn
= PREV_INSN (insn
))
786 if (GET_CODE (insn
) != NOTE
)
792 /* Noreturn calls cause program to exit, therefore they are
793 always predicted as not taken. */
794 if (GET_CODE (insn
) == CALL_INSN
795 && find_reg_note (insn
, REG_NORETURN
, NULL
))
796 contained_noreturn_call
= 1;
800 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_PREDICTION
)
802 int alg
= (int) NOTE_PREDICTION_ALG (insn
);
803 /* Process single prediction note. */
804 process_note_prediction (bb
,
806 alg
, (int) NOTE_PREDICTION_FLAGS (insn
));
810 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
811 if (!(e
->flags
& EDGE_FAKE
))
813 if (contained_noreturn_call
)
815 /* This block ended from other reasons than because of return.
816 If it is because of noreturn call, this should certainly not
817 be taken. Otherwise it is probably some error recovery. */
818 process_note_prediction (bb
, heads
, PRED_NORETURN
, NOT_TAKEN
);
822 /* Gathers NOTE_INSN_PREDICTIONs and turns them into
823 branch probabilities. */
826 note_prediction_to_br_prob (void)
831 /* To enable handling of noreturn blocks. */
832 add_noreturn_fake_exit_edges ();
833 connect_infinite_loops_to_exit ();
835 calculate_dominance_info (CDI_POST_DOMINATORS
);
836 calculate_dominance_info (CDI_DOMINATORS
);
838 heads
= xmalloc (sizeof (int) * last_basic_block
);
839 memset (heads
, -1, sizeof (int) * last_basic_block
);
840 heads
[ENTRY_BLOCK_PTR
->next_bb
->index
] = last_basic_block
;
842 /* Process all prediction notes. */
845 process_note_predictions (bb
, heads
);
847 free_dominance_info (CDI_POST_DOMINATORS
);
848 free_dominance_info (CDI_DOMINATORS
);
851 remove_fake_edges ();
854 /* This is used to carry information about basic blocks. It is
855 attached to the AUX field of the standard CFG block. */
857 typedef struct block_info_def
859 /* Estimated frequency of execution of basic_block. */
862 /* To keep queue of basic blocks to process. */
865 /* True if block needs to be visited in propagate_freq. */
866 unsigned int tovisit
:1;
868 /* Number of predecessors we need to visit first. */
872 /* Similar information for edges. */
873 typedef struct edge_info_def
875 /* In case edge is an loopback edge, the probability edge will be reached
876 in case header is. Estimated number of iterations of the loop can be
877 then computed as 1 / (1 - back_edge_prob). */
878 sreal back_edge_prob
;
879 /* True if the edge is an loopback edge in the natural loop. */
880 unsigned int back_edge
:1;
883 #define BLOCK_INFO(B) ((block_info) (B)->aux)
884 #define EDGE_INFO(E) ((edge_info) (E)->aux)
886 /* Helper function for estimate_bb_frequencies.
887 Propagate the frequencies for LOOP. */
890 propagate_freq (struct loop
*loop
)
892 basic_block head
= loop
->header
;
898 /* For each basic block we need to visit count number of his predecessors
899 we need to visit first. */
902 if (BLOCK_INFO (bb
)->tovisit
)
906 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
907 if (BLOCK_INFO (e
->src
)->tovisit
&& !(e
->flags
& EDGE_DFS_BACK
))
909 else if (BLOCK_INFO (e
->src
)->tovisit
910 && rtl_dump_file
&& !EDGE_INFO (e
)->back_edge
)
911 fprintf (rtl_dump_file
,
912 "Irreducible region hit, ignoring edge to %i->%i\n",
913 e
->src
->index
, bb
->index
);
914 BLOCK_INFO (bb
)->npredecessors
= count
;
918 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
920 for (bb
= head
; bb
; bb
= nextbb
)
922 sreal cyclic_probability
, frequency
;
924 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
925 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
927 nextbb
= BLOCK_INFO (bb
)->next
;
928 BLOCK_INFO (bb
)->next
= NULL
;
930 /* Compute frequency of basic block. */
933 #ifdef ENABLE_CHECKING
934 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
935 if (BLOCK_INFO (e
->src
)->tovisit
&& !(e
->flags
& EDGE_DFS_BACK
))
939 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
940 if (EDGE_INFO (e
)->back_edge
)
942 sreal_add (&cyclic_probability
, &cyclic_probability
,
943 &EDGE_INFO (e
)->back_edge_prob
);
945 else if (!(e
->flags
& EDGE_DFS_BACK
))
949 /* frequency += (e->probability
950 * BLOCK_INFO (e->src)->frequency /
951 REG_BR_PROB_BASE); */
953 sreal_init (&tmp
, e
->probability
, 0);
954 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
955 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
956 sreal_add (&frequency
, &frequency
, &tmp
);
959 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
961 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
966 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
968 memcpy (&cyclic_probability
, &real_almost_one
,
969 sizeof (real_almost_one
));
972 /* BLOCK_INFO (bb)->frequency = frequency
973 / (1 - cyclic_probability) */
975 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
976 sreal_div (&BLOCK_INFO (bb
)->frequency
,
977 &frequency
, &cyclic_probability
);
981 BLOCK_INFO (bb
)->tovisit
= 0;
983 /* Compute back edge frequencies. */
984 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
989 /* EDGE_INFO (e)->back_edge_prob
990 = ((e->probability * BLOCK_INFO (bb)->frequency)
991 / REG_BR_PROB_BASE); */
993 sreal_init (&tmp
, e
->probability
, 0);
994 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
995 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
996 &tmp
, &real_inv_br_prob_base
);
999 /* Propagate to successor blocks. */
1000 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1001 if (!(e
->flags
& EDGE_DFS_BACK
)
1002 && BLOCK_INFO (e
->dest
)->npredecessors
)
1004 BLOCK_INFO (e
->dest
)->npredecessors
--;
1005 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
1010 BLOCK_INFO (last
)->next
= e
->dest
;
1018 /* Estimate probabilities of loopback edges in loops at same nest level. */
1021 estimate_loops_at_level (struct loop
*first_loop
)
1025 for (loop
= first_loop
; loop
; loop
= loop
->next
)
1031 estimate_loops_at_level (loop
->inner
);
1033 if (loop
->latch
->succ
) /* Do not do this for dummy function loop. */
1035 /* Find current loop back edge and mark it. */
1036 e
= loop_latch_edge (loop
);
1037 EDGE_INFO (e
)->back_edge
= 1;
1040 bbs
= get_loop_body (loop
);
1041 for (i
= 0; i
< loop
->num_nodes
; i
++)
1042 BLOCK_INFO (bbs
[i
])->tovisit
= 1;
1044 propagate_freq (loop
);
1048 /* Convert counts measured by profile driven feedback to frequencies. */
1051 counts_to_freqs (void)
1053 gcov_type count_max
= 1;
1057 count_max
= MAX (bb
->count
, count_max
);
1059 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1060 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
1063 /* Return true if function is likely to be expensive, so there is no point to
1064 optimize performance of prologue, epilogue or do inlining at the expense
1065 of code size growth. THRESHOLD is the limit of number of instructions
1066 function can execute at average to be still considered not expensive. */
1069 expensive_function_p (int threshold
)
1071 unsigned int sum
= 0;
1075 /* We can not compute accurately for large thresholds due to scaled
1077 if (threshold
> BB_FREQ_MAX
)
1080 /* Frequencies are out of range. This either means that function contains
1081 internal loop executing more than BB_FREQ_MAX times or profile feedback
1082 is available and function has not been executed at all. */
1083 if (ENTRY_BLOCK_PTR
->frequency
== 0)
1086 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1087 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
1092 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
1093 insn
= NEXT_INSN (insn
))
1094 if (active_insn_p (insn
))
1096 sum
+= bb
->frequency
;
1105 /* Estimate basic blocks frequency by given branch probabilities. */
1108 estimate_bb_frequencies (struct loops
*loops
)
1113 if (flag_branch_probabilities
)
1117 static int real_values_initialized
= 0;
1119 if (!real_values_initialized
)
1121 real_values_initialized
= 1;
1122 sreal_init (&real_zero
, 0, 0);
1123 sreal_init (&real_one
, 1, 0);
1124 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
1125 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
1126 sreal_init (&real_one_half
, 1, -1);
1127 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
1128 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
1131 mark_dfs_back_edges ();
1132 /* Fill in the probability values in flowgraph based on the REG_BR_PROB
1136 rtx last_insn
= BB_END (bb
);
1138 if (!can_predict_insn_p (last_insn
))
1140 /* We can predict only conditional jumps at the moment.
1141 Expect each edge to be equally probable.
1142 ?? In the future we want to make abnormal edges improbable. */
1146 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1149 if (e
->probability
!= 0)
1153 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1154 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
1158 ENTRY_BLOCK_PTR
->succ
->probability
= REG_BR_PROB_BASE
;
1160 /* Set up block info for each basic block. */
1161 alloc_aux_for_blocks (sizeof (struct block_info_def
));
1162 alloc_aux_for_edges (sizeof (struct edge_info_def
));
1163 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1167 BLOCK_INFO (bb
)->tovisit
= 0;
1168 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1170 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
1171 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1172 &EDGE_INFO (e
)->back_edge_prob
,
1173 &real_inv_br_prob_base
);
1177 /* First compute probabilities locally for each loop from innermost
1178 to outermost to examine probabilities for back edges. */
1179 estimate_loops_at_level (loops
->tree_root
);
1181 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
1183 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
1184 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
1186 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
1187 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1191 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
1192 sreal_add (&tmp
, &tmp
, &real_one_half
);
1193 bb
->frequency
= sreal_to_int (&tmp
);
1196 free_aux_for_blocks ();
1197 free_aux_for_edges ();
1199 compute_function_frequency ();
1200 if (flag_reorder_functions
)
1201 choose_function_section ();
1204 /* Decide whether function is hot, cold or unlikely executed. */
1206 compute_function_frequency (void)
1210 if (!profile_info
|| !flag_branch_probabilities
)
1212 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
1215 if (maybe_hot_bb_p (bb
))
1217 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
1220 if (!probably_never_executed_bb_p (bb
))
1221 cfun
->function_frequency
= FUNCTION_FREQUENCY_NORMAL
;
1225 /* Choose appropriate section for the function. */
1227 choose_function_section (void)
1229 if (DECL_SECTION_NAME (current_function_decl
)
1230 || !targetm
.have_named_sections
1231 /* Theoretically we can split the gnu.linkonce text section too,
1232 but this requires more work as the frequency needs to match
1233 for all generated objects so we need to merge the frequency
1234 of all instances. For now just never set frequency for these. */
1235 || DECL_ONE_ONLY (current_function_decl
))
1237 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
1238 DECL_SECTION_NAME (current_function_decl
) =
1239 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
1240 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
1241 DECL_SECTION_NAME (current_function_decl
) =
1242 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
1243 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);