1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004 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"
56 #include "tree-flow.h"
58 #include "tree-dump.h"
59 #include "tree-pass.h"
62 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
63 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
64 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
65 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
67 /* Random guesstimation given names. */
68 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
69 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
70 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
71 #define PROB_ALWAYS (REG_BR_PROB_BASE)
73 static void combine_predictions_for_insn (rtx
, basic_block
);
74 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
75 static void estimate_loops_at_level (struct loop
*loop
);
76 static void propagate_freq (struct loop
*);
77 static void estimate_bb_frequencies (struct loops
*);
78 static int counts_to_freqs (void);
79 static bool last_basic_block_p (basic_block
);
80 static void compute_function_frequency (void);
81 static void choose_function_section (void);
82 static bool can_predict_insn_p (rtx
);
84 /* Information we hold about each branch predictor.
85 Filled using information from predict.def. */
89 const char *const name
; /* Name used in the debugging dumps. */
90 const int hitrate
; /* Expected hitrate used by
91 predict_insn_def call. */
95 /* Use given predictor without Dempster-Shaffer theory if it matches
96 using first_match heuristics. */
97 #define PRED_FLAG_FIRST_MATCH 1
99 /* Recompute hitrate in percent to our representation. */
101 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
103 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
104 static const struct predictor_info predictor_info
[]= {
105 #include "predict.def"
107 /* Upper bound on predictors. */
112 /* Return true in case BB can be CPU intensive and should be optimized
113 for maximal performance. */
116 maybe_hot_bb_p (basic_block bb
)
118 if (profile_info
&& flag_branch_probabilities
120 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
122 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
127 /* Return true in case BB is cold and should be optimized for size. */
130 probably_cold_bb_p (basic_block bb
)
132 if (profile_info
&& flag_branch_probabilities
134 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
136 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
141 /* Return true in case BB is probably never executed. */
143 probably_never_executed_bb_p (basic_block bb
)
145 if (profile_info
&& flag_branch_probabilities
)
146 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
150 /* Return true if the one of outgoing edges is already predicted by
154 rtl_predicted_by_p (basic_block bb
, enum br_predictor predictor
)
157 if (!INSN_P (BB_END (bb
)))
159 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
160 if (REG_NOTE_KIND (note
) == REG_BR_PRED
161 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
166 /* Return true if the one of outgoing edges is already predicted by
170 tree_predicted_by_p (basic_block bb
, enum br_predictor predictor
)
172 struct edge_prediction
*i
= bb_ann (bb
)->predictions
;
173 for (i
= bb_ann (bb
)->predictions
; i
; i
= i
->next
)
174 if (i
->predictor
== predictor
)
180 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
182 if (!any_condjump_p (insn
))
184 if (!flag_guess_branch_prob
)
188 = gen_rtx_EXPR_LIST (REG_BR_PRED
,
189 gen_rtx_CONCAT (VOIDmode
,
190 GEN_INT ((int) predictor
),
191 GEN_INT ((int) probability
)),
195 /* Predict insn by given predictor. */
198 predict_insn_def (rtx insn
, enum br_predictor predictor
,
199 enum prediction taken
)
201 int probability
= predictor_info
[(int) predictor
].hitrate
;
204 probability
= REG_BR_PROB_BASE
- probability
;
206 predict_insn (insn
, predictor
, probability
);
209 /* Predict edge E with given probability if possible. */
212 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
215 last_insn
= BB_END (e
->src
);
217 /* We can store the branch prediction information only about
218 conditional jumps. */
219 if (!any_condjump_p (last_insn
))
222 /* We always store probability of branching. */
223 if (e
->flags
& EDGE_FALLTHRU
)
224 probability
= REG_BR_PROB_BASE
- probability
;
226 predict_insn (last_insn
, predictor
, probability
);
229 /* Predict edge E with the given PROBABILITY. */
231 tree_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
233 struct edge_prediction
*i
= ggc_alloc (sizeof (struct edge_prediction
));
235 i
->next
= bb_ann (e
->src
)->predictions
;
236 bb_ann (e
->src
)->predictions
= i
;
237 i
->probability
= probability
;
238 i
->predictor
= predictor
;
242 /* Return true when we can store prediction on insn INSN.
243 At the moment we represent predictions only on conditional
244 jumps, not at computed jump or other complicated cases. */
246 can_predict_insn_p (rtx insn
)
248 return (JUMP_P (insn
)
249 && any_condjump_p (insn
)
250 && BLOCK_FOR_INSN (insn
)->succ
->succ_next
);
253 /* Predict edge E by given predictor if possible. */
256 predict_edge_def (edge e
, enum br_predictor predictor
,
257 enum prediction taken
)
259 int probability
= predictor_info
[(int) predictor
].hitrate
;
262 probability
= REG_BR_PROB_BASE
- probability
;
264 predict_edge (e
, predictor
, probability
);
267 /* Invert all branch predictions or probability notes in the INSN. This needs
268 to be done each time we invert the condition used by the jump. */
271 invert_br_probabilities (rtx insn
)
275 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
276 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
277 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
278 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
279 XEXP (XEXP (note
, 0), 1)
280 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
283 /* Dump information about the branch prediction to the output file. */
286 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
287 basic_block bb
, int used
)
294 while (e
&& (e
->flags
& EDGE_FALLTHRU
))
297 fprintf (file
, " %s heuristics%s: %.1f%%",
298 predictor_info
[predictor
].name
,
299 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
303 fprintf (file
, " exec ");
304 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
307 fprintf (file
, " hit ");
308 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
309 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
313 fprintf (file
, "\n");
316 /* We can not predict the probabilities of outgoing edges of bb. Set them
317 evenly and hope for the best. */
319 set_even_probabilities (basic_block bb
)
324 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
325 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
327 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
328 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
329 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
334 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
335 note if not already present. Remove now useless REG_BR_PRED notes. */
338 combine_predictions_for_insn (rtx insn
, basic_block bb
)
343 int best_probability
= PROB_EVEN
;
344 int best_predictor
= END_PREDICTORS
;
345 int combined_probability
= REG_BR_PROB_BASE
/ 2;
347 bool first_match
= false;
350 if (!can_predict_insn_p (insn
))
352 set_even_probabilities (bb
);
356 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
357 pnote
= ®_NOTES (insn
);
359 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
362 /* We implement "first match" heuristics and use probability guessed
363 by predictor with smallest index. */
364 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
365 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
367 int predictor
= INTVAL (XEXP (XEXP (note
, 0), 0));
368 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
371 if (best_predictor
> predictor
)
372 best_probability
= probability
, best_predictor
= predictor
;
374 d
= (combined_probability
* probability
375 + (REG_BR_PROB_BASE
- combined_probability
)
376 * (REG_BR_PROB_BASE
- probability
));
378 /* Use FP math to avoid overflows of 32bit integers. */
380 /* If one probability is 0% and one 100%, avoid division by zero. */
381 combined_probability
= REG_BR_PROB_BASE
/ 2;
383 combined_probability
= (((double) combined_probability
) * probability
384 * REG_BR_PROB_BASE
/ d
+ 0.5);
387 /* Decide which heuristic to use. In case we didn't match anything,
388 use no_prediction heuristic, in case we did match, use either
389 first match or Dempster-Shaffer theory depending on the flags. */
391 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
395 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
396 combined_probability
, bb
, true);
399 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
401 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
406 combined_probability
= best_probability
;
407 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
411 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
413 int predictor
= INTVAL (XEXP (XEXP (*pnote
, 0), 0));
414 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
416 dump_prediction (dump_file
, predictor
, probability
, bb
,
417 !first_match
|| best_predictor
== predictor
);
418 *pnote
= XEXP (*pnote
, 1);
421 pnote
= &XEXP (*pnote
, 1);
427 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
428 GEN_INT (combined_probability
), REG_NOTES (insn
));
430 /* Save the prediction into CFG in case we are seeing non-degenerated
432 if (bb
->succ
->succ_next
)
434 BRANCH_EDGE (bb
)->probability
= combined_probability
;
435 FALLTHRU_EDGE (bb
)->probability
436 = REG_BR_PROB_BASE
- combined_probability
;
441 /* Combine predictions into single probability and store them into CFG.
442 Remove now useless prediction entries. */
445 combine_predictions_for_bb (FILE *file
, basic_block bb
)
447 int best_probability
= PROB_EVEN
;
448 int best_predictor
= END_PREDICTORS
;
449 int combined_probability
= REG_BR_PROB_BASE
/ 2;
451 bool first_match
= false;
453 struct edge_prediction
*pred
;
455 edge e
, first
= NULL
, second
= NULL
;
457 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
458 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
461 if (first
&& !second
)
467 /* When there is no successor or only one choice, prediction is easy.
469 We are lazy for now and predict only basic blocks with two outgoing
470 edges. It is possible to predict generic case too, but we have to
471 ignore first match heuristics and do more involved combining. Implement
476 set_even_probabilities (bb
);
477 bb_ann (bb
)->predictions
= NULL
;
479 fprintf (file
, "%i edges in bb %i predicted to even probabilities\n",
485 fprintf (file
, "Predictions for bb %i\n", bb
->index
);
487 /* We implement "first match" heuristics and use probability guessed
488 by predictor with smallest index. */
489 for (pred
= bb_ann (bb
)->predictions
; pred
; pred
= pred
->next
)
491 int predictor
= pred
->predictor
;
492 int probability
= pred
->probability
;
494 if (pred
->edge
!= first
)
495 probability
= REG_BR_PROB_BASE
- probability
;
498 if (best_predictor
> predictor
)
499 best_probability
= probability
, best_predictor
= predictor
;
501 d
= (combined_probability
* probability
502 + (REG_BR_PROB_BASE
- combined_probability
)
503 * (REG_BR_PROB_BASE
- probability
));
505 /* Use FP math to avoid overflows of 32bit integers. */
507 /* If one probability is 0% and one 100%, avoid division by zero. */
508 combined_probability
= REG_BR_PROB_BASE
/ 2;
510 combined_probability
= (((double) combined_probability
) * probability
511 * REG_BR_PROB_BASE
/ d
+ 0.5);
514 /* Decide which heuristic to use. In case we didn't match anything,
515 use no_prediction heuristic, in case we did match, use either
516 first match or Dempster-Shaffer theory depending on the flags. */
518 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
522 dump_prediction (file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
525 dump_prediction (file
, PRED_DS_THEORY
, combined_probability
, bb
,
527 dump_prediction (file
, PRED_FIRST_MATCH
, best_probability
, bb
,
532 combined_probability
= best_probability
;
533 dump_prediction (file
, PRED_COMBINED
, combined_probability
, bb
, true);
535 for (pred
= bb_ann (bb
)->predictions
; pred
; pred
= pred
->next
)
537 int predictor
= pred
->predictor
;
538 int probability
= pred
->probability
;
540 if (pred
->edge
!= bb
->succ
)
541 probability
= REG_BR_PROB_BASE
- probability
;
542 dump_prediction (file
, predictor
, probability
, bb
,
543 !first_match
|| best_predictor
== predictor
);
545 bb_ann (bb
)->predictions
= NULL
;
549 first
->probability
= combined_probability
;
550 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
554 /* Predict edge probabilities by exploiting loop structure.
555 When SIMPLELOOPS is set, attempt to count number of iterations by analyzing
558 predict_loops (struct loops
*loops_info
, bool simpleloops
)
562 /* Try to predict out blocks in a loop that are not part of a
564 for (i
= 1; i
< loops_info
->num
; i
++)
566 basic_block bb
, *bbs
;
569 struct loop
*loop
= loops_info
->parray
[i
];
570 struct niter_desc desc
;
571 unsigned HOST_WIDE_INT niter
;
573 flow_loop_scan (loop
, LOOP_EXIT_EDGES
);
574 exits
= loop
->num_exits
;
578 iv_analysis_loop_init (loop
);
579 find_simple_exit (loop
, &desc
);
581 if (desc
.simple_p
&& desc
.const_iter
)
584 niter
= desc
.niter
+ 1;
585 if (niter
== 0) /* We might overflow here. */
588 prob
= (REG_BR_PROB_BASE
589 - (REG_BR_PROB_BASE
+ niter
/2) / niter
);
590 /* Branch prediction algorithm gives 0 frequency for everything
591 after the end of loop for loop having 0 probability to finish. */
592 if (prob
== REG_BR_PROB_BASE
)
593 prob
= REG_BR_PROB_BASE
- 1;
594 predict_edge (desc
.in_edge
, PRED_LOOP_ITERATIONS
,
599 bbs
= get_loop_body (loop
);
601 for (j
= 0; j
< loop
->num_nodes
; j
++)
603 int header_found
= 0;
608 /* Bypass loop heuristics on continue statement. These
609 statements construct loops via "non-loop" constructs
610 in the source language and are better to be handled
612 if ((simpleloops
&& !can_predict_insn_p (BB_END (bb
)))
613 || predicted_by_p (bb
, PRED_CONTINUE
))
616 /* Loop branch heuristics - predict an edge back to a
617 loop's head as taken. */
618 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
619 if (e
->dest
== loop
->header
620 && e
->src
== loop
->latch
)
623 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
626 /* Loop exit heuristics - predict an edge exiting the loop if the
627 conditional has no loop header successors as not taken. */
629 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
630 if (e
->dest
->index
< 0
631 || !flow_bb_inside_loop_p (loop
, e
->dest
))
635 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
639 /* Free basic blocks from get_loop_body. */
644 /* Attempt to predict probabilities of BB outgoing edges using local
647 bb_estimate_probability_locally (basic_block bb
)
649 rtx last_insn
= BB_END (bb
);
652 if (! can_predict_insn_p (last_insn
))
654 cond
= get_condition (last_insn
, NULL
, false, false);
658 /* Try "pointer heuristic."
659 A comparison ptr == 0 is predicted as false.
660 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
661 if (COMPARISON_P (cond
)
662 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
663 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
665 if (GET_CODE (cond
) == EQ
)
666 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
667 else if (GET_CODE (cond
) == NE
)
668 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
672 /* Try "opcode heuristic."
673 EQ tests are usually false and NE tests are usually true. Also,
674 most quantities are positive, so we can make the appropriate guesses
675 about signed comparisons against zero. */
676 switch (GET_CODE (cond
))
679 /* Unconditional branch. */
680 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
681 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
686 /* Floating point comparisons appears to behave in a very
687 unpredictable way because of special role of = tests in
689 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
691 /* Comparisons with 0 are often used for booleans and there is
692 nothing useful to predict about them. */
693 else if (XEXP (cond
, 1) == const0_rtx
694 || XEXP (cond
, 0) == const0_rtx
)
697 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
702 /* Floating point comparisons appears to behave in a very
703 unpredictable way because of special role of = tests in
705 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
707 /* Comparisons with 0 are often used for booleans and there is
708 nothing useful to predict about them. */
709 else if (XEXP (cond
, 1) == const0_rtx
710 || XEXP (cond
, 0) == const0_rtx
)
713 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
717 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
721 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
726 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
727 || XEXP (cond
, 1) == constm1_rtx
)
728 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
733 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
734 || XEXP (cond
, 1) == constm1_rtx
)
735 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
743 /* Statically estimate the probability that a branch will be taken and produce
744 estimated profile. When profile feedback is present never executed portions
745 of function gets estimated. */
748 estimate_probability (struct loops
*loops_info
)
752 connect_infinite_loops_to_exit ();
753 calculate_dominance_info (CDI_DOMINATORS
);
754 calculate_dominance_info (CDI_POST_DOMINATORS
);
756 predict_loops (loops_info
, true);
760 /* Attempt to predict conditional jumps using a number of heuristics. */
763 rtx last_insn
= BB_END (bb
);
766 if (! can_predict_insn_p (last_insn
))
769 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
771 /* Predict early returns to be probable, as we've already taken
772 care for error returns and other are often used for fast paths
774 if ((e
->dest
== EXIT_BLOCK_PTR
775 || (e
->dest
->succ
&& !e
->dest
->succ
->succ_next
776 && e
->dest
->succ
->dest
== EXIT_BLOCK_PTR
))
777 && !predicted_by_p (bb
, PRED_NULL_RETURN
)
778 && !predicted_by_p (bb
, PRED_CONST_RETURN
)
779 && !predicted_by_p (bb
, PRED_NEGATIVE_RETURN
)
780 && !last_basic_block_p (e
->dest
))
781 predict_edge_def (e
, PRED_EARLY_RETURN
, TAKEN
);
783 /* Look for block we are guarding (ie we dominate it,
784 but it doesn't postdominate us). */
785 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
786 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
787 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
791 /* The call heuristic claims that a guarded function call
792 is improbable. This is because such calls are often used
793 to signal exceptional situations such as printing error
795 for (insn
= BB_HEAD (e
->dest
); insn
!= NEXT_INSN (BB_END (e
->dest
));
796 insn
= NEXT_INSN (insn
))
798 /* Constant and pure calls are hardly used to signalize
799 something exceptional. */
800 && ! CONST_OR_PURE_CALL_P (insn
))
802 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
807 bb_estimate_probability_locally (bb
);
810 /* Attach the combined probability to each conditional jump. */
812 if (JUMP_P (BB_END (bb
))
813 && any_condjump_p (BB_END (bb
))
814 && bb
->succ
->succ_next
!= NULL
)
815 combine_predictions_for_insn (BB_END (bb
), bb
);
817 remove_fake_exit_edges ();
818 /* Fill in the probability values in flowgraph based on the REG_BR_PROB
822 rtx last_insn
= BB_END (bb
);
824 if (!can_predict_insn_p (last_insn
))
826 /* We can predict only conditional jumps at the moment.
827 Expect each edge to be equally probable.
828 ?? In the future we want to make abnormal edges improbable. */
832 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
835 if (e
->probability
!= 0)
839 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
840 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
843 estimate_bb_frequencies (loops_info
);
844 free_dominance_info (CDI_POST_DOMINATORS
);
845 if (profile_status
== PROFILE_ABSENT
)
846 profile_status
= PROFILE_GUESSED
;
849 /* Set edge->probability for each successor edge of BB. */
851 guess_outgoing_edge_probabilities (basic_block bb
)
853 bb_estimate_probability_locally (bb
);
854 combine_predictions_for_insn (BB_END (bb
), bb
);
858 /* Predict using opcode of the last statement in basic block. */
860 tree_predict_by_opcode (basic_block bb
)
862 tree stmt
= last_stmt (bb
);
868 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
870 for (then_edge
= bb
->succ
; then_edge
; then_edge
= then_edge
->succ_next
)
871 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
873 cond
= TREE_OPERAND (stmt
, 0);
874 if (TREE_CODE_CLASS (TREE_CODE (cond
)) != '<')
876 op0
= TREE_OPERAND (cond
, 0);
877 type
= TREE_TYPE (op0
);
878 /* Try "pointer heuristic."
879 A comparison ptr == 0 is predicted as false.
880 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
881 if (POINTER_TYPE_P (type
))
883 if (TREE_CODE (cond
) == EQ_EXPR
)
884 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
885 else if (TREE_CODE (cond
) == NE_EXPR
)
886 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
890 /* Try "opcode heuristic."
891 EQ tests are usually false and NE tests are usually true. Also,
892 most quantities are positive, so we can make the appropriate guesses
893 about signed comparisons against zero. */
894 switch (TREE_CODE (cond
))
898 /* Floating point comparisons appears to behave in a very
899 unpredictable way because of special role of = tests in
901 if (FLOAT_TYPE_P (type
))
903 /* Comparisons with 0 are often used for booleans and there is
904 nothing useful to predict about them. */
905 else if (integer_zerop (op0
)
906 || integer_zerop (TREE_OPERAND (cond
, 1)))
909 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
914 /* Floating point comparisons appears to behave in a very
915 unpredictable way because of special role of = tests in
917 if (FLOAT_TYPE_P (type
))
919 /* Comparisons with 0 are often used for booleans and there is
920 nothing useful to predict about them. */
921 else if (integer_zerop (op0
)
922 || integer_zerop (TREE_OPERAND (cond
, 1)))
925 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
929 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
933 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
938 if (integer_zerop (TREE_OPERAND (cond
, 1))
939 || integer_onep (TREE_OPERAND (cond
, 1))
940 || integer_all_onesp (TREE_OPERAND (cond
, 1))
941 || real_zerop (TREE_OPERAND (cond
, 1))
942 || real_onep (TREE_OPERAND (cond
, 1))
943 || real_minus_onep (TREE_OPERAND (cond
, 1)))
944 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
949 if (integer_zerop (TREE_OPERAND (cond
, 1))
950 || integer_onep (TREE_OPERAND (cond
, 1))
951 || integer_all_onesp (TREE_OPERAND (cond
, 1))
952 || real_zerop (TREE_OPERAND (cond
, 1))
953 || real_onep (TREE_OPERAND (cond
, 1))
954 || real_minus_onep (TREE_OPERAND (cond
, 1)))
955 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
963 /* Predict branch probabilities and estimate profile of the tree CFG. */
965 tree_estimate_probability (void)
968 struct loops loops_info
;
970 flow_loops_find (&loops_info
, LOOP_TREE
);
971 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
972 flow_loops_dump (&loops_info
, dump_file
, NULL
, 0);
974 connect_infinite_loops_to_exit ();
975 calculate_dominance_info (CDI_DOMINATORS
);
976 calculate_dominance_info (CDI_POST_DOMINATORS
);
978 predict_loops (&loops_info
, false);
984 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
986 /* Predict early returns to be probable, as we've already taken
987 care for error returns and other are often used for fast paths
989 if ((e
->dest
== EXIT_BLOCK_PTR
990 || (e
->dest
->succ
&& !e
->dest
->succ
->succ_next
991 && e
->dest
->succ
->dest
== EXIT_BLOCK_PTR
))
992 && !predicted_by_p (bb
, PRED_NULL_RETURN
)
993 && !predicted_by_p (bb
, PRED_CONST_RETURN
)
994 && !predicted_by_p (bb
, PRED_NEGATIVE_RETURN
)
995 && !last_basic_block_p (e
->dest
))
996 predict_edge_def (e
, PRED_EARLY_RETURN
, TAKEN
);
998 /* Look for block we are guarding (ie we dominate it,
999 but it doesn't postdominate us). */
1000 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
1001 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
1002 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
1004 block_stmt_iterator bi
;
1006 /* The call heuristic claims that a guarded function call
1007 is improbable. This is because such calls are often used
1008 to signal exceptional situations such as printing error
1010 for (bi
= bsi_start (e
->dest
); !bsi_end_p (bi
);
1013 tree stmt
= bsi_stmt (bi
);
1014 if ((TREE_CODE (stmt
) == CALL_EXPR
1015 || (TREE_CODE (stmt
) == MODIFY_EXPR
1016 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
))
1017 /* Constant and pure calls are hardly used to signalize
1018 something exceptional. */
1019 && TREE_SIDE_EFFECTS (stmt
))
1021 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
1027 tree_predict_by_opcode (bb
);
1030 combine_predictions_for_bb (dump_file
, bb
);
1032 estimate_bb_frequencies (&loops_info
);
1033 free_dominance_info (CDI_POST_DOMINATORS
);
1034 remove_fake_exit_edges ();
1035 flow_loops_free (&loops_info
);
1036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1037 dump_tree_cfg (dump_file
, dump_flags
);
1038 if (profile_status
== PROFILE_ABSENT
)
1039 profile_status
= PROFILE_GUESSED
;
1042 /* __builtin_expect dropped tokens into the insn stream describing expected
1043 values of registers. Generate branch probabilities based off these
1047 expected_value_to_br_prob (void)
1049 rtx insn
, cond
, ev
= NULL_RTX
, ev_reg
= NULL_RTX
;
1051 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1053 switch (GET_CODE (insn
))
1056 /* Look for expected value notes. */
1057 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EXPECTED_VALUE
)
1059 ev
= NOTE_EXPECTED_VALUE (insn
);
1060 ev_reg
= XEXP (ev
, 0);
1066 /* Never propagate across labels. */
1071 /* Look for simple conditional branches. If we haven't got an
1072 expected value yet, no point going further. */
1073 if (!JUMP_P (insn
) || ev
== NULL_RTX
1074 || ! any_condjump_p (insn
))
1079 /* Look for insns that clobber the EV register. */
1080 if (ev
&& reg_set_p (ev_reg
, insn
))
1085 /* Collect the branch condition, hopefully relative to EV_REG. */
1086 /* ??? At present we'll miss things like
1087 (expected_value (eq r70 0))
1089 (set r80 (lt r70 r71))
1090 (set pc (if_then_else (ne r80 0) ...))
1091 as canonicalize_condition will render this to us as
1093 Could use cselib to try and reduce this further. */
1094 cond
= XEXP (SET_SRC (pc_set (insn
)), 0);
1095 cond
= canonicalize_condition (insn
, cond
, 0, NULL
, ev_reg
,
1097 if (! cond
|| XEXP (cond
, 0) != ev_reg
1098 || GET_CODE (XEXP (cond
, 1)) != CONST_INT
)
1101 /* Substitute and simplify. Given that the expression we're
1102 building involves two constants, we should wind up with either
1104 cond
= gen_rtx_fmt_ee (GET_CODE (cond
), VOIDmode
,
1105 XEXP (ev
, 1), XEXP (cond
, 1));
1106 cond
= simplify_rtx (cond
);
1108 /* Turn the condition into a scaled branch probability. */
1109 if (cond
!= const_true_rtx
&& cond
!= const0_rtx
)
1111 predict_insn_def (insn
, PRED_BUILTIN_EXPECT
,
1112 cond
== const_true_rtx
? TAKEN
: NOT_TAKEN
);
1116 /* Check whether this is the last basic block of function. Commonly
1117 there is one extra common cleanup block. */
1119 last_basic_block_p (basic_block bb
)
1121 if (bb
== EXIT_BLOCK_PTR
)
1124 return (bb
->next_bb
== EXIT_BLOCK_PTR
1125 || (bb
->next_bb
->next_bb
== EXIT_BLOCK_PTR
1126 && bb
->succ
&& !bb
->succ
->succ_next
1127 && bb
->succ
->dest
->next_bb
== EXIT_BLOCK_PTR
));
1130 /* This is used to carry information about basic blocks. It is
1131 attached to the AUX field of the standard CFG block. */
1133 typedef struct block_info_def
1135 /* Estimated frequency of execution of basic_block. */
1138 /* To keep queue of basic blocks to process. */
1141 /* True if block needs to be visited in propagate_freq. */
1142 unsigned int tovisit
:1;
1144 /* Number of predecessors we need to visit first. */
1148 /* Similar information for edges. */
1149 typedef struct edge_info_def
1151 /* In case edge is an loopback edge, the probability edge will be reached
1152 in case header is. Estimated number of iterations of the loop can be
1153 then computed as 1 / (1 - back_edge_prob). */
1154 sreal back_edge_prob
;
1155 /* True if the edge is an loopback edge in the natural loop. */
1156 unsigned int back_edge
:1;
1159 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1160 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1162 /* Helper function for estimate_bb_frequencies.
1163 Propagate the frequencies for LOOP. */
1166 propagate_freq (struct loop
*loop
)
1168 basic_block head
= loop
->header
;
1174 /* For each basic block we need to visit count number of his predecessors
1175 we need to visit first. */
1176 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1178 if (BLOCK_INFO (bb
)->tovisit
)
1182 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1183 if (BLOCK_INFO (e
->src
)->tovisit
&& !(e
->flags
& EDGE_DFS_BACK
))
1185 else if (BLOCK_INFO (e
->src
)->tovisit
1186 && dump_file
&& !EDGE_INFO (e
)->back_edge
)
1188 "Irreducible region hit, ignoring edge to %i->%i\n",
1189 e
->src
->index
, bb
->index
);
1190 BLOCK_INFO (bb
)->npredecessors
= count
;
1194 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
1196 for (bb
= head
; bb
; bb
= nextbb
)
1198 sreal cyclic_probability
, frequency
;
1200 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
1201 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
1203 nextbb
= BLOCK_INFO (bb
)->next
;
1204 BLOCK_INFO (bb
)->next
= NULL
;
1206 /* Compute frequency of basic block. */
1209 #ifdef ENABLE_CHECKING
1210 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1211 if (BLOCK_INFO (e
->src
)->tovisit
&& !(e
->flags
& EDGE_DFS_BACK
))
1215 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1216 if (EDGE_INFO (e
)->back_edge
)
1218 sreal_add (&cyclic_probability
, &cyclic_probability
,
1219 &EDGE_INFO (e
)->back_edge_prob
);
1221 else if (!(e
->flags
& EDGE_DFS_BACK
))
1225 /* frequency += (e->probability
1226 * BLOCK_INFO (e->src)->frequency /
1227 REG_BR_PROB_BASE); */
1229 sreal_init (&tmp
, e
->probability
, 0);
1230 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
1231 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
1232 sreal_add (&frequency
, &frequency
, &tmp
);
1235 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
1237 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
1238 sizeof (frequency
));
1242 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
1244 memcpy (&cyclic_probability
, &real_almost_one
,
1245 sizeof (real_almost_one
));
1248 /* BLOCK_INFO (bb)->frequency = frequency
1249 / (1 - cyclic_probability) */
1251 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
1252 sreal_div (&BLOCK_INFO (bb
)->frequency
,
1253 &frequency
, &cyclic_probability
);
1257 BLOCK_INFO (bb
)->tovisit
= 0;
1259 /* Compute back edge frequencies. */
1260 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1261 if (e
->dest
== head
)
1265 /* EDGE_INFO (e)->back_edge_prob
1266 = ((e->probability * BLOCK_INFO (bb)->frequency)
1267 / REG_BR_PROB_BASE); */
1269 sreal_init (&tmp
, e
->probability
, 0);
1270 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
1271 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1272 &tmp
, &real_inv_br_prob_base
);
1275 /* Propagate to successor blocks. */
1276 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1277 if (!(e
->flags
& EDGE_DFS_BACK
)
1278 && BLOCK_INFO (e
->dest
)->npredecessors
)
1280 BLOCK_INFO (e
->dest
)->npredecessors
--;
1281 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
1286 BLOCK_INFO (last
)->next
= e
->dest
;
1294 /* Estimate probabilities of loopback edges in loops at same nest level. */
1297 estimate_loops_at_level (struct loop
*first_loop
)
1301 for (loop
= first_loop
; loop
; loop
= loop
->next
)
1307 estimate_loops_at_level (loop
->inner
);
1309 if (loop
->latch
->succ
) /* Do not do this for dummy function loop. */
1311 /* Find current loop back edge and mark it. */
1312 e
= loop_latch_edge (loop
);
1313 EDGE_INFO (e
)->back_edge
= 1;
1316 bbs
= get_loop_body (loop
);
1317 for (i
= 0; i
< loop
->num_nodes
; i
++)
1318 BLOCK_INFO (bbs
[i
])->tovisit
= 1;
1320 propagate_freq (loop
);
1324 /* Convert counts measured by profile driven feedback to frequencies.
1325 Return nonzero iff there was any nonzero execution count. */
1328 counts_to_freqs (void)
1330 gcov_type count_max
, true_count_max
= 0;
1334 true_count_max
= MAX (bb
->count
, true_count_max
);
1336 count_max
= MAX (true_count_max
, 1);
1337 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1338 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
1339 return true_count_max
;
1342 /* Return true if function is likely to be expensive, so there is no point to
1343 optimize performance of prologue, epilogue or do inlining at the expense
1344 of code size growth. THRESHOLD is the limit of number of instructions
1345 function can execute at average to be still considered not expensive. */
1348 expensive_function_p (int threshold
)
1350 unsigned int sum
= 0;
1354 /* We can not compute accurately for large thresholds due to scaled
1356 if (threshold
> BB_FREQ_MAX
)
1359 /* Frequencies are out of range. This either means that function contains
1360 internal loop executing more than BB_FREQ_MAX times or profile feedback
1361 is available and function has not been executed at all. */
1362 if (ENTRY_BLOCK_PTR
->frequency
== 0)
1365 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1366 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
1371 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
1372 insn
= NEXT_INSN (insn
))
1373 if (active_insn_p (insn
))
1375 sum
+= bb
->frequency
;
1384 /* Estimate basic blocks frequency by given branch probabilities. */
1387 estimate_bb_frequencies (struct loops
*loops
)
1392 if (!flag_branch_probabilities
|| !counts_to_freqs ())
1394 static int real_values_initialized
= 0;
1396 if (!real_values_initialized
)
1398 real_values_initialized
= 1;
1399 sreal_init (&real_zero
, 0, 0);
1400 sreal_init (&real_one
, 1, 0);
1401 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
1402 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
1403 sreal_init (&real_one_half
, 1, -1);
1404 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
1405 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
1408 mark_dfs_back_edges ();
1410 ENTRY_BLOCK_PTR
->succ
->probability
= REG_BR_PROB_BASE
;
1412 /* Set up block info for each basic block. */
1413 alloc_aux_for_blocks (sizeof (struct block_info_def
));
1414 alloc_aux_for_edges (sizeof (struct edge_info_def
));
1415 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1419 BLOCK_INFO (bb
)->tovisit
= 0;
1420 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1422 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
1423 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1424 &EDGE_INFO (e
)->back_edge_prob
,
1425 &real_inv_br_prob_base
);
1429 /* First compute probabilities locally for each loop from innermost
1430 to outermost to examine probabilities for back edges. */
1431 estimate_loops_at_level (loops
->tree_root
);
1433 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
1435 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
1436 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
1438 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
1439 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1443 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
1444 sreal_add (&tmp
, &tmp
, &real_one_half
);
1445 bb
->frequency
= sreal_to_int (&tmp
);
1448 free_aux_for_blocks ();
1449 free_aux_for_edges ();
1451 compute_function_frequency ();
1452 if (flag_reorder_functions
)
1453 choose_function_section ();
1456 /* Decide whether function is hot, cold or unlikely executed. */
1458 compute_function_frequency (void)
1462 if (!profile_info
|| !flag_branch_probabilities
)
1464 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
1467 if (maybe_hot_bb_p (bb
))
1469 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
1472 if (!probably_never_executed_bb_p (bb
))
1473 cfun
->function_frequency
= FUNCTION_FREQUENCY_NORMAL
;
1477 /* Choose appropriate section for the function. */
1479 choose_function_section (void)
1481 if (DECL_SECTION_NAME (current_function_decl
)
1482 || !targetm
.have_named_sections
1483 /* Theoretically we can split the gnu.linkonce text section too,
1484 but this requires more work as the frequency needs to match
1485 for all generated objects so we need to merge the frequency
1486 of all instances. For now just never set frequency for these. */
1487 || DECL_ONE_ONLY (current_function_decl
))
1490 /* If we are doing the partitioning optimization, let the optimization
1491 choose the correct section into which to put things. */
1493 if (flag_reorder_blocks_and_partition
)
1496 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
1497 DECL_SECTION_NAME (current_function_decl
) =
1498 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
1499 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
1500 DECL_SECTION_NAME (current_function_decl
) =
1501 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
1502 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);
1506 struct tree_opt_pass pass_profile
=
1508 "profile", /* name */
1510 tree_estimate_probability
, /* execute */
1513 0, /* static_pass_number */
1514 TV_BRANCH_PROB
, /* tv_id */
1515 PROP_cfg
, /* properties_required */
1516 0, /* properties_provided */
1517 0, /* properties_destroyed */
1518 0, /* todo_flags_start */
1519 TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */