1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 [1] "Branch Prediction for Free"
25 Ball and Larus; PLDI '93.
26 [2] "Static Branch Frequency and Program Profile Analysis"
27 Wu and Larus; MICRO-27.
28 [3] "Corpus-based Static Branch Prediction"
29 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
34 #include "coretypes.h"
39 #include "hard-reg-set.h"
40 #include "basic-block.h"
41 #include "insn-config.h"
56 #include "tree-flow.h"
58 #include "tree-dump.h"
59 #include "tree-pass.h"
61 #include "tree-scalar-evolution.h"
64 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
65 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
66 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
67 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
69 /* Random guesstimation given names. */
70 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 100 - 1)
71 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
72 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
73 #define PROB_ALWAYS (REG_BR_PROB_BASE)
75 static void combine_predictions_for_insn (rtx
, basic_block
);
76 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
77 static void estimate_bb_frequencies (struct loops
*);
78 static void predict_paths_leading_to (basic_block
, int *, enum br_predictor
, enum prediction
);
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
;
173 for (i
= bb
->predictions
; i
; i
= i
->ep_next
)
174 if (i
->ep_predictor
== predictor
)
179 /* Return true when the probability of edge is reliable.
181 The profile guessing code is good at predicting branch outcome (ie.
182 taken/not taken), that is predicted right slightly over 75% of time.
183 It is however notoriously poor on predicting the probability itself.
184 In general the profile appear a lot flatter (with probabilities closer
185 to 50%) than the reality so it is bad idea to use it to drive optimization
186 such as those disabling dynamic branch prediction for well predictable
189 There are two exceptions - edges leading to noreturn edges and edges
190 predicted by number of iterations heuristics are predicted well. This macro
191 should be able to distinguish those, but at the moment it simply check for
192 noreturn heuristic that is only one giving probability over 99% or bellow
193 1%. In future we might want to propagate reliability information across the
194 CFG if we find this information useful on multiple places. */
196 probability_reliable_p (int prob
)
198 return (profile_status
== PROFILE_READ
199 || (profile_status
== PROFILE_GUESSED
200 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
203 /* Same predicate as above, working on edges. */
205 edge_probability_reliable_p (edge e
)
207 return probability_reliable_p (e
->probability
);
210 /* Same predicate as edge_probability_reliable_p, working on notes. */
212 br_prob_note_reliable_p (rtx note
)
214 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
215 return probability_reliable_p (INTVAL (XEXP (note
, 0)));
219 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
221 gcc_assert (any_condjump_p (insn
));
222 if (!flag_guess_branch_prob
)
226 = gen_rtx_EXPR_LIST (REG_BR_PRED
,
227 gen_rtx_CONCAT (VOIDmode
,
228 GEN_INT ((int) predictor
),
229 GEN_INT ((int) probability
)),
233 /* Predict insn by given predictor. */
236 predict_insn_def (rtx insn
, enum br_predictor predictor
,
237 enum prediction taken
)
239 int probability
= predictor_info
[(int) predictor
].hitrate
;
242 probability
= REG_BR_PROB_BASE
- probability
;
244 predict_insn (insn
, predictor
, probability
);
247 /* Predict edge E with given probability if possible. */
250 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
253 last_insn
= BB_END (e
->src
);
255 /* We can store the branch prediction information only about
256 conditional jumps. */
257 if (!any_condjump_p (last_insn
))
260 /* We always store probability of branching. */
261 if (e
->flags
& EDGE_FALLTHRU
)
262 probability
= REG_BR_PROB_BASE
- probability
;
264 predict_insn (last_insn
, predictor
, probability
);
267 /* Predict edge E with the given PROBABILITY. */
269 tree_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
271 gcc_assert (profile_status
!= PROFILE_GUESSED
);
272 if ((e
->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (e
->src
->succs
) > 1)
273 && flag_guess_branch_prob
&& optimize
)
275 struct edge_prediction
*i
= ggc_alloc (sizeof (struct edge_prediction
));
277 i
->ep_next
= e
->src
->predictions
;
278 e
->src
->predictions
= i
;
279 i
->ep_probability
= probability
;
280 i
->ep_predictor
= predictor
;
285 /* Remove all predictions on given basic block that are attached
288 remove_predictions_associated_with_edge (edge e
)
290 if (e
->src
->predictions
)
292 struct edge_prediction
**prediction
= &e
->src
->predictions
;
295 if ((*prediction
)->ep_edge
== e
)
296 *prediction
= (*prediction
)->ep_next
;
298 prediction
= &((*prediction
)->ep_next
);
303 /* Return true when we can store prediction on insn INSN.
304 At the moment we represent predictions only on conditional
305 jumps, not at computed jump or other complicated cases. */
307 can_predict_insn_p (rtx insn
)
309 return (JUMP_P (insn
)
310 && any_condjump_p (insn
)
311 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
314 /* Predict edge E by given predictor if possible. */
317 predict_edge_def (edge e
, enum br_predictor predictor
,
318 enum prediction taken
)
320 int probability
= predictor_info
[(int) predictor
].hitrate
;
323 probability
= REG_BR_PROB_BASE
- probability
;
325 predict_edge (e
, predictor
, probability
);
328 /* Invert all branch predictions or probability notes in the INSN. This needs
329 to be done each time we invert the condition used by the jump. */
332 invert_br_probabilities (rtx insn
)
336 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
337 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
338 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
339 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
340 XEXP (XEXP (note
, 0), 1)
341 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
344 /* Dump information about the branch prediction to the output file. */
347 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
348 basic_block bb
, int used
)
356 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
357 if (! (e
->flags
& EDGE_FALLTHRU
))
360 fprintf (file
, " %s heuristics%s: %.1f%%",
361 predictor_info
[predictor
].name
,
362 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
366 fprintf (file
, " exec ");
367 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
370 fprintf (file
, " hit ");
371 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
372 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
376 fprintf (file
, "\n");
379 /* We can not predict the probabilities of outgoing edges of bb. Set them
380 evenly and hope for the best. */
382 set_even_probabilities (basic_block bb
)
388 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
389 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
391 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
392 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
393 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
398 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
399 note if not already present. Remove now useless REG_BR_PRED notes. */
402 combine_predictions_for_insn (rtx insn
, basic_block bb
)
407 int best_probability
= PROB_EVEN
;
408 int best_predictor
= END_PREDICTORS
;
409 int combined_probability
= REG_BR_PROB_BASE
/ 2;
411 bool first_match
= false;
414 if (!can_predict_insn_p (insn
))
416 set_even_probabilities (bb
);
420 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
421 pnote
= ®_NOTES (insn
);
423 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
426 /* We implement "first match" heuristics and use probability guessed
427 by predictor with smallest index. */
428 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
429 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
431 int predictor
= INTVAL (XEXP (XEXP (note
, 0), 0));
432 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
435 if (best_predictor
> predictor
)
436 best_probability
= probability
, best_predictor
= predictor
;
438 d
= (combined_probability
* probability
439 + (REG_BR_PROB_BASE
- combined_probability
)
440 * (REG_BR_PROB_BASE
- probability
));
442 /* Use FP math to avoid overflows of 32bit integers. */
444 /* If one probability is 0% and one 100%, avoid division by zero. */
445 combined_probability
= REG_BR_PROB_BASE
/ 2;
447 combined_probability
= (((double) combined_probability
) * probability
448 * REG_BR_PROB_BASE
/ d
+ 0.5);
451 /* Decide which heuristic to use. In case we didn't match anything,
452 use no_prediction heuristic, in case we did match, use either
453 first match or Dempster-Shaffer theory depending on the flags. */
455 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
459 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
460 combined_probability
, bb
, true);
463 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
465 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
470 combined_probability
= best_probability
;
471 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
475 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
477 int predictor
= INTVAL (XEXP (XEXP (*pnote
, 0), 0));
478 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
480 dump_prediction (dump_file
, predictor
, probability
, bb
,
481 !first_match
|| best_predictor
== predictor
);
482 *pnote
= XEXP (*pnote
, 1);
485 pnote
= &XEXP (*pnote
, 1);
491 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
492 GEN_INT (combined_probability
), REG_NOTES (insn
));
494 /* Save the prediction into CFG in case we are seeing non-degenerated
496 if (!single_succ_p (bb
))
498 BRANCH_EDGE (bb
)->probability
= combined_probability
;
499 FALLTHRU_EDGE (bb
)->probability
500 = REG_BR_PROB_BASE
- combined_probability
;
503 else if (!single_succ_p (bb
))
505 int prob
= INTVAL (XEXP (prob_note
, 0));
507 BRANCH_EDGE (bb
)->probability
= prob
;
508 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
511 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
514 /* Combine predictions into single probability and store them into CFG.
515 Remove now useless prediction entries. */
518 combine_predictions_for_bb (basic_block bb
)
520 int best_probability
= PROB_EVEN
;
521 int best_predictor
= END_PREDICTORS
;
522 int combined_probability
= REG_BR_PROB_BASE
/ 2;
524 bool first_match
= false;
526 struct edge_prediction
*pred
;
528 edge e
, first
= NULL
, second
= NULL
;
531 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
532 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
535 if (first
&& !second
)
541 /* When there is no successor or only one choice, prediction is easy.
543 We are lazy for now and predict only basic blocks with two outgoing
544 edges. It is possible to predict generic case too, but we have to
545 ignore first match heuristics and do more involved combining. Implement
550 set_even_probabilities (bb
);
551 bb
->predictions
= NULL
;
553 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
559 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
561 /* We implement "first match" heuristics and use probability guessed
562 by predictor with smallest index. */
563 for (pred
= bb
->predictions
; pred
; pred
= pred
->ep_next
)
565 int predictor
= pred
->ep_predictor
;
566 int probability
= pred
->ep_probability
;
568 if (pred
->ep_edge
!= first
)
569 probability
= REG_BR_PROB_BASE
- probability
;
572 if (best_predictor
> predictor
)
573 best_probability
= probability
, best_predictor
= predictor
;
575 d
= (combined_probability
* probability
576 + (REG_BR_PROB_BASE
- combined_probability
)
577 * (REG_BR_PROB_BASE
- probability
));
579 /* Use FP math to avoid overflows of 32bit integers. */
581 /* If one probability is 0% and one 100%, avoid division by zero. */
582 combined_probability
= REG_BR_PROB_BASE
/ 2;
584 combined_probability
= (((double) combined_probability
) * probability
585 * REG_BR_PROB_BASE
/ d
+ 0.5);
588 /* Decide which heuristic to use. In case we didn't match anything,
589 use no_prediction heuristic, in case we did match, use either
590 first match or Dempster-Shaffer theory depending on the flags. */
592 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
596 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
599 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
601 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
606 combined_probability
= best_probability
;
607 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
609 for (pred
= bb
->predictions
; pred
; pred
= pred
->ep_next
)
611 int predictor
= pred
->ep_predictor
;
612 int probability
= pred
->ep_probability
;
614 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
615 probability
= REG_BR_PROB_BASE
- probability
;
616 dump_prediction (dump_file
, predictor
, probability
, bb
,
617 !first_match
|| best_predictor
== predictor
);
619 bb
->predictions
= NULL
;
623 first
->probability
= combined_probability
;
624 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
628 /* Predict edge probabilities by exploiting loop structure.
629 When RTLSIMPLELOOPS is set, attempt to count number of iterations by analyzing
630 RTL otherwise use tree based approach. */
632 predict_loops (struct loops
*loops_info
)
636 scev_initialize (loops_info
);
638 /* Try to predict out blocks in a loop that are not part of a
640 for (i
= 1; i
< loops_info
->num
; i
++)
642 basic_block bb
, *bbs
;
644 struct loop
*loop
= loops_info
->parray
[i
];
645 VEC (edge
, heap
) *exits
;
646 struct tree_niter_desc niter_desc
;
649 exits
= get_loop_exit_edges (loop
);
650 n_exits
= VEC_length (edge
, exits
);
652 for (j
= 0; VEC_iterate (edge
, exits
, j
, ex
); j
++)
656 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
657 niter
= niter_desc
.niter
;
658 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
659 niter
= loop_niter_by_eval (loop
, ex
);
661 if (TREE_CODE (niter
) == INTEGER_CST
)
664 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
665 if (host_integerp (niter
, 1)
666 && tree_int_cst_lt (niter
,
667 build_int_cstu (NULL_TREE
, max
- 1)))
669 HOST_WIDE_INT nitercst
= tree_low_cst (niter
, 1) + 1;
670 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2)
674 probability
= ((REG_BR_PROB_BASE
+ max
/ 2) / max
);
676 predict_edge (ex
, PRED_LOOP_ITERATIONS
, probability
);
679 VEC_free (edge
, heap
, exits
);
681 bbs
= get_loop_body (loop
);
683 for (j
= 0; j
< loop
->num_nodes
; j
++)
685 int header_found
= 0;
691 /* Bypass loop heuristics on continue statement. These
692 statements construct loops via "non-loop" constructs
693 in the source language and are better to be handled
695 if (predicted_by_p (bb
, PRED_CONTINUE
))
698 /* Loop branch heuristics - predict an edge back to a
699 loop's head as taken. */
700 if (bb
== loop
->latch
)
702 e
= find_edge (loop
->latch
, loop
->header
);
706 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
710 /* Loop exit heuristics - predict an edge exiting the loop if the
711 conditional has no loop header successors as not taken. */
714 /* For loop with many exits we don't want to predict all exits
715 with the pretty large probability, because if all exits are
716 considered in row, the loop would be predicted to iterate
717 almost never. The code to divide probability by number of
718 exits is very rough. It should compute the number of exits
719 taken in each patch through function (not the overall number
720 of exits that might be a lot higher for loops with wide switch
721 statements in them) and compute n-th square root.
723 We limit the minimal probability by 2% to avoid
724 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
725 as this was causing regression in perl benchmark containing such
728 int probability
= ((REG_BR_PROB_BASE
729 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
731 if (probability
< HITRATE (2))
732 probability
= HITRATE (2);
733 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
734 if (e
->dest
->index
< NUM_FIXED_BLOCKS
735 || !flow_bb_inside_loop_p (loop
, e
->dest
))
736 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
740 /* Free basic blocks from get_loop_body. */
747 /* Attempt to predict probabilities of BB outgoing edges using local
750 bb_estimate_probability_locally (basic_block bb
)
752 rtx last_insn
= BB_END (bb
);
755 if (! can_predict_insn_p (last_insn
))
757 cond
= get_condition (last_insn
, NULL
, false, false);
761 /* Try "pointer heuristic."
762 A comparison ptr == 0 is predicted as false.
763 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
764 if (COMPARISON_P (cond
)
765 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
766 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
768 if (GET_CODE (cond
) == EQ
)
769 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
770 else if (GET_CODE (cond
) == NE
)
771 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
775 /* Try "opcode heuristic."
776 EQ tests are usually false and NE tests are usually true. Also,
777 most quantities are positive, so we can make the appropriate guesses
778 about signed comparisons against zero. */
779 switch (GET_CODE (cond
))
782 /* Unconditional branch. */
783 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
784 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
789 /* Floating point comparisons appears to behave in a very
790 unpredictable way because of special role of = tests in
792 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
794 /* Comparisons with 0 are often used for booleans and there is
795 nothing useful to predict about them. */
796 else if (XEXP (cond
, 1) == const0_rtx
797 || XEXP (cond
, 0) == const0_rtx
)
800 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
805 /* Floating point comparisons appears to behave in a very
806 unpredictable way because of special role of = tests in
808 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
810 /* Comparisons with 0 are often used for booleans and there is
811 nothing useful to predict about them. */
812 else if (XEXP (cond
, 1) == const0_rtx
813 || XEXP (cond
, 0) == const0_rtx
)
816 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
820 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
824 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
829 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
830 || XEXP (cond
, 1) == constm1_rtx
)
831 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
836 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
837 || XEXP (cond
, 1) == constm1_rtx
)
838 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
846 /* Set edge->probability for each successor edge of BB. */
848 guess_outgoing_edge_probabilities (basic_block bb
)
850 bb_estimate_probability_locally (bb
);
851 combine_predictions_for_insn (BB_END (bb
), bb
);
854 /* Return constant EXPR will likely have at execution time, NULL if unknown.
855 The function is used by builtin_expect branch predictor so the evidence
856 must come from this construct and additional possible constant folding.
858 We may want to implement more involved value guess (such as value range
859 propagation based prediction), but such tricks shall go to new
863 expr_expected_value (tree expr
, bitmap visited
)
865 if (TREE_CONSTANT (expr
))
867 else if (TREE_CODE (expr
) == SSA_NAME
)
869 tree def
= SSA_NAME_DEF_STMT (expr
);
871 /* If we were already here, break the infinite cycle. */
872 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (expr
)))
874 bitmap_set_bit (visited
, SSA_NAME_VERSION (expr
));
876 if (TREE_CODE (def
) == PHI_NODE
)
878 /* All the arguments of the PHI node must have the same constant
881 tree val
= NULL
, new_val
;
883 for (i
= 0; i
< PHI_NUM_ARGS (def
); i
++)
885 tree arg
= PHI_ARG_DEF (def
, i
);
887 /* If this PHI has itself as an argument, we cannot
888 determine the string length of this argument. However,
889 if we can find an expected constant value for the other
890 PHI args then we can still be sure that this is
891 likely a constant. So be optimistic and just
892 continue with the next argument. */
893 if (arg
== PHI_RESULT (def
))
896 new_val
= expr_expected_value (arg
, visited
);
901 else if (!operand_equal_p (val
, new_val
, false))
906 if (TREE_CODE (def
) != MODIFY_EXPR
|| TREE_OPERAND (def
, 0) != expr
)
908 return expr_expected_value (TREE_OPERAND (def
, 1), visited
);
910 else if (TREE_CODE (expr
) == CALL_EXPR
)
912 tree decl
= get_callee_fndecl (expr
);
915 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
916 && DECL_FUNCTION_CODE (decl
) == BUILT_IN_EXPECT
)
918 tree arglist
= TREE_OPERAND (expr
, 1);
921 if (arglist
== NULL_TREE
922 || TREE_CHAIN (arglist
) == NULL_TREE
)
924 val
= TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr
, 1)));
925 if (TREE_CONSTANT (val
))
927 return TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr
, 1)));
930 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
933 op0
= expr_expected_value (TREE_OPERAND (expr
, 0), visited
);
936 op1
= expr_expected_value (TREE_OPERAND (expr
, 1), visited
);
939 res
= fold_build2 (TREE_CODE (expr
), TREE_TYPE (expr
), op0
, op1
);
940 if (TREE_CONSTANT (res
))
944 if (UNARY_CLASS_P (expr
))
947 op0
= expr_expected_value (TREE_OPERAND (expr
, 0), visited
);
950 res
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
), op0
);
951 if (TREE_CONSTANT (res
))
958 /* Get rid of all builtin_expect calls we no longer need. */
960 strip_builtin_expect (void)
965 block_stmt_iterator bi
;
966 for (bi
= bsi_start (bb
); !bsi_end_p (bi
); bsi_next (&bi
))
968 tree stmt
= bsi_stmt (bi
);
972 if (TREE_CODE (stmt
) == MODIFY_EXPR
973 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
974 && (fndecl
= get_callee_fndecl (TREE_OPERAND (stmt
, 1)))
975 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
976 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
977 && (arglist
= TREE_OPERAND (TREE_OPERAND (stmt
, 1), 1))
978 && TREE_CHAIN (arglist
))
980 TREE_OPERAND (stmt
, 1) = TREE_VALUE (arglist
);
987 /* Predict using opcode of the last statement in basic block. */
989 tree_predict_by_opcode (basic_block bb
)
991 tree stmt
= last_stmt (bb
);
1000 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
1002 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1003 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1005 cond
= TREE_OPERAND (stmt
, 0);
1006 if (!COMPARISON_CLASS_P (cond
))
1008 op0
= TREE_OPERAND (cond
, 0);
1009 type
= TREE_TYPE (op0
);
1010 visited
= BITMAP_ALLOC (NULL
);
1011 val
= expr_expected_value (cond
, visited
);
1012 BITMAP_FREE (visited
);
1015 if (integer_zerop (val
))
1016 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, NOT_TAKEN
);
1018 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, TAKEN
);
1021 /* Try "pointer heuristic."
1022 A comparison ptr == 0 is predicted as false.
1023 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1024 if (POINTER_TYPE_P (type
))
1026 if (TREE_CODE (cond
) == EQ_EXPR
)
1027 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1028 else if (TREE_CODE (cond
) == NE_EXPR
)
1029 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1033 /* Try "opcode heuristic."
1034 EQ tests are usually false and NE tests are usually true. Also,
1035 most quantities are positive, so we can make the appropriate guesses
1036 about signed comparisons against zero. */
1037 switch (TREE_CODE (cond
))
1041 /* Floating point comparisons appears to behave in a very
1042 unpredictable way because of special role of = tests in
1044 if (FLOAT_TYPE_P (type
))
1046 /* Comparisons with 0 are often used for booleans and there is
1047 nothing useful to predict about them. */
1048 else if (integer_zerop (op0
)
1049 || integer_zerop (TREE_OPERAND (cond
, 1)))
1052 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
1057 /* Floating point comparisons appears to behave in a very
1058 unpredictable way because of special role of = tests in
1060 if (FLOAT_TYPE_P (type
))
1062 /* Comparisons with 0 are often used for booleans and there is
1063 nothing useful to predict about them. */
1064 else if (integer_zerop (op0
)
1065 || integer_zerop (TREE_OPERAND (cond
, 1)))
1068 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
1072 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
1075 case UNORDERED_EXPR
:
1076 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
1081 if (integer_zerop (TREE_OPERAND (cond
, 1))
1082 || integer_onep (TREE_OPERAND (cond
, 1))
1083 || integer_all_onesp (TREE_OPERAND (cond
, 1))
1084 || real_zerop (TREE_OPERAND (cond
, 1))
1085 || real_onep (TREE_OPERAND (cond
, 1))
1086 || real_minus_onep (TREE_OPERAND (cond
, 1)))
1087 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
1092 if (integer_zerop (TREE_OPERAND (cond
, 1))
1093 || integer_onep (TREE_OPERAND (cond
, 1))
1094 || integer_all_onesp (TREE_OPERAND (cond
, 1))
1095 || real_zerop (TREE_OPERAND (cond
, 1))
1096 || real_onep (TREE_OPERAND (cond
, 1))
1097 || real_minus_onep (TREE_OPERAND (cond
, 1)))
1098 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
1106 /* Try to guess whether the value of return means error code. */
1107 static enum br_predictor
1108 return_prediction (tree val
, enum prediction
*prediction
)
1112 return PRED_NO_PREDICTION
;
1113 /* Different heuristics for pointers and scalars. */
1114 if (POINTER_TYPE_P (TREE_TYPE (val
)))
1116 /* NULL is usually not returned. */
1117 if (integer_zerop (val
))
1119 *prediction
= NOT_TAKEN
;
1120 return PRED_NULL_RETURN
;
1123 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
1125 /* Negative return values are often used to indicate
1127 if (TREE_CODE (val
) == INTEGER_CST
1128 && tree_int_cst_sgn (val
) < 0)
1130 *prediction
= NOT_TAKEN
;
1131 return PRED_NEGATIVE_RETURN
;
1133 /* Constant return values seems to be commonly taken.
1134 Zero/one often represent booleans so exclude them from the
1136 if (TREE_CONSTANT (val
)
1137 && (!integer_zerop (val
) && !integer_onep (val
)))
1139 *prediction
= TAKEN
;
1140 return PRED_NEGATIVE_RETURN
;
1143 return PRED_NO_PREDICTION
;
1146 /* Find the basic block with return expression and look up for possible
1147 return value trying to apply RETURN_PREDICTION heuristics. */
1149 apply_return_prediction (int *heads
)
1151 tree return_stmt
= NULL
;
1155 int phi_num_args
, i
;
1156 enum br_predictor pred
;
1157 enum prediction direction
;
1160 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1162 return_stmt
= last_stmt (e
->src
);
1163 if (TREE_CODE (return_stmt
) == RETURN_EXPR
)
1168 return_val
= TREE_OPERAND (return_stmt
, 0);
1171 if (TREE_CODE (return_val
) == MODIFY_EXPR
)
1172 return_val
= TREE_OPERAND (return_val
, 1);
1173 if (TREE_CODE (return_val
) != SSA_NAME
1174 || !SSA_NAME_DEF_STMT (return_val
)
1175 || TREE_CODE (SSA_NAME_DEF_STMT (return_val
)) != PHI_NODE
)
1177 for (phi
= SSA_NAME_DEF_STMT (return_val
); phi
; phi
= PHI_CHAIN (phi
))
1178 if (PHI_RESULT (phi
) == return_val
)
1182 phi_num_args
= PHI_NUM_ARGS (phi
);
1183 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
1185 /* Avoid the degenerate case where all return values form the function
1186 belongs to same category (ie they are all positive constants)
1187 so we can hardly say something about them. */
1188 for (i
= 1; i
< phi_num_args
; i
++)
1189 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
1191 if (i
!= phi_num_args
)
1192 for (i
= 0; i
< phi_num_args
; i
++)
1194 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
1195 if (pred
!= PRED_NO_PREDICTION
)
1196 predict_paths_leading_to (PHI_ARG_EDGE (phi
, i
)->src
, heads
, pred
,
1201 /* Look for basic block that contains unlikely to happen events
1202 (such as noreturn calls) and mark all paths leading to execution
1203 of this basic blocks as unlikely. */
1206 tree_bb_level_predictions (void)
1211 heads
= XCNEWVEC (int, last_basic_block
);
1212 heads
[ENTRY_BLOCK_PTR
->next_bb
->index
] = last_basic_block
;
1214 apply_return_prediction (heads
);
1218 block_stmt_iterator bsi
= bsi_last (bb
);
1220 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1222 tree stmt
= bsi_stmt (bsi
);
1223 switch (TREE_CODE (stmt
))
1226 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
)
1228 stmt
= TREE_OPERAND (stmt
, 1);
1234 if (call_expr_flags (stmt
) & ECF_NORETURN
)
1235 predict_paths_leading_to (bb
, heads
, PRED_NORETURN
,
1247 /* Predict branch probabilities and estimate profile of the tree CFG. */
1249 tree_estimate_probability (void)
1253 loop_optimizer_init (0);
1254 if (current_loops
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1255 flow_loops_dump (current_loops
, dump_file
, NULL
, 0);
1257 add_noreturn_fake_exit_edges ();
1258 connect_infinite_loops_to_exit ();
1259 calculate_dominance_info (CDI_DOMINATORS
);
1260 calculate_dominance_info (CDI_POST_DOMINATORS
);
1262 tree_bb_level_predictions ();
1264 mark_irreducible_loops (current_loops
);
1266 predict_loops (current_loops
);
1273 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1275 /* Predict early returns to be probable, as we've already taken
1276 care for error returns and other cases are often used for
1277 fast paths through function. */
1278 if (e
->dest
== EXIT_BLOCK_PTR
1279 && TREE_CODE (last_stmt (bb
)) == RETURN_EXPR
1280 && !single_pred_p (bb
))
1285 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
1286 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
1287 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
1288 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
)
1289 && !last_basic_block_p (e1
->src
))
1290 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1293 /* Look for block we are guarding (ie we dominate it,
1294 but it doesn't postdominate us). */
1295 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
1296 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
1297 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
1299 block_stmt_iterator bi
;
1301 /* The call heuristic claims that a guarded function call
1302 is improbable. This is because such calls are often used
1303 to signal exceptional situations such as printing error
1305 for (bi
= bsi_start (e
->dest
); !bsi_end_p (bi
);
1308 tree stmt
= bsi_stmt (bi
);
1309 if ((TREE_CODE (stmt
) == CALL_EXPR
1310 || (TREE_CODE (stmt
) == MODIFY_EXPR
1311 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
))
1312 /* Constant and pure calls are hardly used to signalize
1313 something exceptional. */
1314 && TREE_SIDE_EFFECTS (stmt
))
1316 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
1322 tree_predict_by_opcode (bb
);
1325 combine_predictions_for_bb (bb
);
1327 strip_builtin_expect ();
1328 estimate_bb_frequencies (current_loops
);
1329 free_dominance_info (CDI_POST_DOMINATORS
);
1330 remove_fake_exit_edges ();
1331 loop_optimizer_finalize ();
1332 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1333 dump_tree_cfg (dump_file
, dump_flags
);
1334 if (profile_status
== PROFILE_ABSENT
)
1335 profile_status
= PROFILE_GUESSED
;
1339 /* Check whether this is the last basic block of function. Commonly
1340 there is one extra common cleanup block. */
1342 last_basic_block_p (basic_block bb
)
1344 if (bb
== EXIT_BLOCK_PTR
)
1347 return (bb
->next_bb
== EXIT_BLOCK_PTR
1348 || (bb
->next_bb
->next_bb
== EXIT_BLOCK_PTR
1349 && single_succ_p (bb
)
1350 && single_succ (bb
)->next_bb
== EXIT_BLOCK_PTR
));
1353 /* Sets branch probabilities according to PREDiction and
1354 FLAGS. HEADS[bb->index] should be index of basic block in that we
1355 need to alter branch predictions (i.e. the first of our dominators
1356 such that we do not post-dominate it) (but we fill this information
1357 on demand, so -1 may be there in case this was not needed yet). */
1360 predict_paths_leading_to (basic_block bb
, int *heads
, enum br_predictor pred
,
1361 enum prediction taken
)
1367 if (heads
[bb
->index
] == ENTRY_BLOCK
)
1369 /* This is first time we need this field in heads array; so
1370 find first dominator that we do not post-dominate (we are
1371 using already known members of heads array). */
1372 basic_block ai
= bb
;
1373 basic_block next_ai
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1376 while (heads
[next_ai
->index
] == ENTRY_BLOCK
)
1378 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
1380 heads
[next_ai
->index
] = ai
->index
;
1382 next_ai
= get_immediate_dominator (CDI_DOMINATORS
, next_ai
);
1384 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
1385 head
= next_ai
->index
;
1387 head
= heads
[next_ai
->index
];
1388 while (next_ai
!= bb
)
1391 ai
= BASIC_BLOCK (heads
[ai
->index
]);
1392 heads
[next_ai
->index
] = head
;
1395 y
= heads
[bb
->index
];
1397 /* Now find the edge that leads to our branch and aply the prediction. */
1399 if (y
== last_basic_block
)
1401 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (y
)->succs
)
1402 if (e
->dest
->index
>= NUM_FIXED_BLOCKS
1403 && dominated_by_p (CDI_POST_DOMINATORS
, e
->dest
, bb
))
1404 predict_edge_def (e
, pred
, taken
);
1407 /* This is used to carry information about basic blocks. It is
1408 attached to the AUX field of the standard CFG block. */
1410 typedef struct block_info_def
1412 /* Estimated frequency of execution of basic_block. */
1415 /* To keep queue of basic blocks to process. */
1418 /* Number of predecessors we need to visit first. */
1422 /* Similar information for edges. */
1423 typedef struct edge_info_def
1425 /* In case edge is a loopback edge, the probability edge will be reached
1426 in case header is. Estimated number of iterations of the loop can be
1427 then computed as 1 / (1 - back_edge_prob). */
1428 sreal back_edge_prob
;
1429 /* True if the edge is a loopback edge in the natural loop. */
1430 unsigned int back_edge
:1;
1433 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1434 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1436 /* Helper function for estimate_bb_frequencies.
1437 Propagate the frequencies in blocks marked in
1438 TOVISIT, starting in HEAD. */
1441 propagate_freq (basic_block head
, bitmap tovisit
)
1450 /* For each basic block we need to visit count number of his predecessors
1451 we need to visit first. */
1452 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
1457 /* The outermost "loop" includes the exit block, which we can not
1458 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1459 directly. Do the same for the entry block. */
1460 bb
= BASIC_BLOCK (i
);
1462 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1464 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
1466 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
1468 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
1470 "Irreducible region hit, ignoring edge to %i->%i\n",
1471 e
->src
->index
, bb
->index
);
1473 BLOCK_INFO (bb
)->npredecessors
= count
;
1476 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
1478 for (bb
= head
; bb
; bb
= nextbb
)
1481 sreal cyclic_probability
, frequency
;
1483 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
1484 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
1486 nextbb
= BLOCK_INFO (bb
)->next
;
1487 BLOCK_INFO (bb
)->next
= NULL
;
1489 /* Compute frequency of basic block. */
1492 #ifdef ENABLE_CHECKING
1493 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1494 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
1495 || (e
->flags
& EDGE_DFS_BACK
));
1498 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1499 if (EDGE_INFO (e
)->back_edge
)
1501 sreal_add (&cyclic_probability
, &cyclic_probability
,
1502 &EDGE_INFO (e
)->back_edge_prob
);
1504 else if (!(e
->flags
& EDGE_DFS_BACK
))
1508 /* frequency += (e->probability
1509 * BLOCK_INFO (e->src)->frequency /
1510 REG_BR_PROB_BASE); */
1512 sreal_init (&tmp
, e
->probability
, 0);
1513 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
1514 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
1515 sreal_add (&frequency
, &frequency
, &tmp
);
1518 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
1520 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
1521 sizeof (frequency
));
1525 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
1527 memcpy (&cyclic_probability
, &real_almost_one
,
1528 sizeof (real_almost_one
));
1531 /* BLOCK_INFO (bb)->frequency = frequency
1532 / (1 - cyclic_probability) */
1534 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
1535 sreal_div (&BLOCK_INFO (bb
)->frequency
,
1536 &frequency
, &cyclic_probability
);
1540 bitmap_clear_bit (tovisit
, bb
->index
);
1542 e
= find_edge (bb
, head
);
1547 /* EDGE_INFO (e)->back_edge_prob
1548 = ((e->probability * BLOCK_INFO (bb)->frequency)
1549 / REG_BR_PROB_BASE); */
1551 sreal_init (&tmp
, e
->probability
, 0);
1552 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
1553 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1554 &tmp
, &real_inv_br_prob_base
);
1557 /* Propagate to successor blocks. */
1558 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1559 if (!(e
->flags
& EDGE_DFS_BACK
)
1560 && BLOCK_INFO (e
->dest
)->npredecessors
)
1562 BLOCK_INFO (e
->dest
)->npredecessors
--;
1563 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
1568 BLOCK_INFO (last
)->next
= e
->dest
;
1576 /* Estimate probabilities of loopback edges in loops at same nest level. */
1579 estimate_loops_at_level (struct loop
*first_loop
)
1583 for (loop
= first_loop
; loop
; loop
= loop
->next
)
1588 bitmap tovisit
= BITMAP_ALLOC (NULL
);
1590 estimate_loops_at_level (loop
->inner
);
1592 /* Find current loop back edge and mark it. */
1593 e
= loop_latch_edge (loop
);
1594 EDGE_INFO (e
)->back_edge
= 1;
1596 bbs
= get_loop_body (loop
);
1597 for (i
= 0; i
< loop
->num_nodes
; i
++)
1598 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
1600 propagate_freq (loop
->header
, tovisit
);
1601 BITMAP_FREE (tovisit
);
1605 /* Propates frequencies through structure of LOOPS. */
1608 estimate_loops (struct loops
*loops
)
1610 bitmap tovisit
= BITMAP_ALLOC (NULL
);
1613 /* Start by estimating the frequencies in the loops. */
1615 estimate_loops_at_level (loops
->tree_root
->inner
);
1617 /* Now propagate the frequencies through all the blocks. */
1620 bitmap_set_bit (tovisit
, bb
->index
);
1622 propagate_freq (ENTRY_BLOCK_PTR
, tovisit
);
1623 BITMAP_FREE (tovisit
);
1626 /* Convert counts measured by profile driven feedback to frequencies.
1627 Return nonzero iff there was any nonzero execution count. */
1630 counts_to_freqs (void)
1632 gcov_type count_max
, true_count_max
= 0;
1636 true_count_max
= MAX (bb
->count
, true_count_max
);
1638 count_max
= MAX (true_count_max
, 1);
1639 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1640 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
1641 return true_count_max
;
1644 /* Return true if function is likely to be expensive, so there is no point to
1645 optimize performance of prologue, epilogue or do inlining at the expense
1646 of code size growth. THRESHOLD is the limit of number of instructions
1647 function can execute at average to be still considered not expensive. */
1650 expensive_function_p (int threshold
)
1652 unsigned int sum
= 0;
1656 /* We can not compute accurately for large thresholds due to scaled
1658 gcc_assert (threshold
<= BB_FREQ_MAX
);
1660 /* Frequencies are out of range. This either means that function contains
1661 internal loop executing more than BB_FREQ_MAX times or profile feedback
1662 is available and function has not been executed at all. */
1663 if (ENTRY_BLOCK_PTR
->frequency
== 0)
1666 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1667 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
1672 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
1673 insn
= NEXT_INSN (insn
))
1674 if (active_insn_p (insn
))
1676 sum
+= bb
->frequency
;
1685 /* Estimate basic blocks frequency by given branch probabilities. */
1688 estimate_bb_frequencies (struct loops
*loops
)
1693 if (!flag_branch_probabilities
|| !counts_to_freqs ())
1695 static int real_values_initialized
= 0;
1697 if (!real_values_initialized
)
1699 real_values_initialized
= 1;
1700 sreal_init (&real_zero
, 0, 0);
1701 sreal_init (&real_one
, 1, 0);
1702 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
1703 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
1704 sreal_init (&real_one_half
, 1, -1);
1705 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
1706 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
1709 mark_dfs_back_edges ();
1711 single_succ_edge (ENTRY_BLOCK_PTR
)->probability
= REG_BR_PROB_BASE
;
1713 /* Set up block info for each basic block. */
1714 alloc_aux_for_blocks (sizeof (struct block_info_def
));
1715 alloc_aux_for_edges (sizeof (struct edge_info_def
));
1716 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1721 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1723 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
1724 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1725 &EDGE_INFO (e
)->back_edge_prob
,
1726 &real_inv_br_prob_base
);
1730 /* First compute probabilities locally for each loop from innermost
1731 to outermost to examine probabilities for back edges. */
1732 estimate_loops (loops
);
1734 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
1736 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
1737 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
1739 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
1740 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1744 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
1745 sreal_add (&tmp
, &tmp
, &real_one_half
);
1746 bb
->frequency
= sreal_to_int (&tmp
);
1749 free_aux_for_blocks ();
1750 free_aux_for_edges ();
1752 compute_function_frequency ();
1753 if (flag_reorder_functions
)
1754 choose_function_section ();
1757 /* Decide whether function is hot, cold or unlikely executed. */
1759 compute_function_frequency (void)
1763 if (!profile_info
|| !flag_branch_probabilities
)
1765 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
1768 if (maybe_hot_bb_p (bb
))
1770 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
1773 if (!probably_never_executed_bb_p (bb
))
1774 cfun
->function_frequency
= FUNCTION_FREQUENCY_NORMAL
;
1778 /* Choose appropriate section for the function. */
1780 choose_function_section (void)
1782 if (DECL_SECTION_NAME (current_function_decl
)
1783 || !targetm
.have_named_sections
1784 /* Theoretically we can split the gnu.linkonce text section too,
1785 but this requires more work as the frequency needs to match
1786 for all generated objects so we need to merge the frequency
1787 of all instances. For now just never set frequency for these. */
1788 || DECL_ONE_ONLY (current_function_decl
))
1791 /* If we are doing the partitioning optimization, let the optimization
1792 choose the correct section into which to put things. */
1794 if (flag_reorder_blocks_and_partition
)
1797 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
1798 DECL_SECTION_NAME (current_function_decl
) =
1799 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
1800 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
1801 DECL_SECTION_NAME (current_function_decl
) =
1802 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
1803 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);
1807 gate_estimate_probability (void)
1809 return flag_guess_branch_prob
;
1812 struct tree_opt_pass pass_profile
=
1814 "profile", /* name */
1815 gate_estimate_probability
, /* gate */
1816 tree_estimate_probability
, /* execute */
1819 0, /* static_pass_number */
1820 TV_BRANCH_PROB
, /* tv_id */
1821 PROP_cfg
, /* properties_required */
1822 0, /* properties_provided */
1823 0, /* properties_destroyed */
1824 0, /* todo_flags_start */
1825 TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */