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 predict_paths_leading_to (basic_block
, int *, enum br_predictor
, enum prediction
);
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 (!profile_info
|| !flag_branch_probabilities
)
122 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
124 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
127 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
132 /* Return true in case BB is cold and should be optimized for size. */
135 probably_cold_bb_p (basic_block bb
)
137 if (profile_info
&& flag_branch_probabilities
139 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
141 if ((!profile_info
|| !flag_branch_probabilities
)
142 && cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
144 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
149 /* Return true in case BB is probably never executed. */
151 probably_never_executed_bb_p (basic_block bb
)
153 if (profile_info
&& flag_branch_probabilities
)
154 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
155 if ((!profile_info
|| !flag_branch_probabilities
)
156 && cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
161 /* Return true if the one of outgoing edges is already predicted by
165 rtl_predicted_by_p (basic_block bb
, enum br_predictor predictor
)
168 if (!INSN_P (BB_END (bb
)))
170 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
171 if (REG_NOTE_KIND (note
) == REG_BR_PRED
172 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
177 /* Return true if the one of outgoing edges is already predicted by
181 tree_predicted_by_p (basic_block bb
, enum br_predictor predictor
)
183 struct edge_prediction
*i
;
184 for (i
= bb
->predictions
; i
; i
= i
->ep_next
)
185 if (i
->ep_predictor
== predictor
)
190 /* Return true when the probability of edge is reliable.
192 The profile guessing code is good at predicting branch outcome (ie.
193 taken/not taken), that is predicted right slightly over 75% of time.
194 It is however notoriously poor on predicting the probability itself.
195 In general the profile appear a lot flatter (with probabilities closer
196 to 50%) than the reality so it is bad idea to use it to drive optimization
197 such as those disabling dynamic branch prediction for well predictable
200 There are two exceptions - edges leading to noreturn edges and edges
201 predicted by number of iterations heuristics are predicted well. This macro
202 should be able to distinguish those, but at the moment it simply check for
203 noreturn heuristic that is only one giving probability over 99% or bellow
204 1%. In future we might want to propagate reliability information across the
205 CFG if we find this information useful on multiple places. */
207 probability_reliable_p (int prob
)
209 return (profile_status
== PROFILE_READ
210 || (profile_status
== PROFILE_GUESSED
211 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
214 /* Same predicate as above, working on edges. */
216 edge_probability_reliable_p (edge e
)
218 return probability_reliable_p (e
->probability
);
221 /* Same predicate as edge_probability_reliable_p, working on notes. */
223 br_prob_note_reliable_p (rtx note
)
225 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
226 return probability_reliable_p (INTVAL (XEXP (note
, 0)));
230 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
232 gcc_assert (any_condjump_p (insn
));
233 if (!flag_guess_branch_prob
)
237 = gen_rtx_EXPR_LIST (REG_BR_PRED
,
238 gen_rtx_CONCAT (VOIDmode
,
239 GEN_INT ((int) predictor
),
240 GEN_INT ((int) probability
)),
244 /* Predict insn by given predictor. */
247 predict_insn_def (rtx insn
, enum br_predictor predictor
,
248 enum prediction taken
)
250 int probability
= predictor_info
[(int) predictor
].hitrate
;
253 probability
= REG_BR_PROB_BASE
- probability
;
255 predict_insn (insn
, predictor
, probability
);
258 /* Predict edge E with given probability if possible. */
261 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
264 last_insn
= BB_END (e
->src
);
266 /* We can store the branch prediction information only about
267 conditional jumps. */
268 if (!any_condjump_p (last_insn
))
271 /* We always store probability of branching. */
272 if (e
->flags
& EDGE_FALLTHRU
)
273 probability
= REG_BR_PROB_BASE
- probability
;
275 predict_insn (last_insn
, predictor
, probability
);
278 /* Predict edge E with the given PROBABILITY. */
280 tree_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
282 gcc_assert (profile_status
!= PROFILE_GUESSED
);
283 if ((e
->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (e
->src
->succs
) > 1)
284 && flag_guess_branch_prob
&& optimize
)
286 struct edge_prediction
*i
= ggc_alloc (sizeof (struct edge_prediction
));
288 i
->ep_next
= e
->src
->predictions
;
289 e
->src
->predictions
= i
;
290 i
->ep_probability
= probability
;
291 i
->ep_predictor
= predictor
;
296 /* Remove all predictions on given basic block that are attached
299 remove_predictions_associated_with_edge (edge e
)
301 if (e
->src
->predictions
)
303 struct edge_prediction
**prediction
= &e
->src
->predictions
;
306 if ((*prediction
)->ep_edge
== e
)
307 *prediction
= (*prediction
)->ep_next
;
309 prediction
= &((*prediction
)->ep_next
);
314 /* Return true when we can store prediction on insn INSN.
315 At the moment we represent predictions only on conditional
316 jumps, not at computed jump or other complicated cases. */
318 can_predict_insn_p (rtx insn
)
320 return (JUMP_P (insn
)
321 && any_condjump_p (insn
)
322 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
325 /* Predict edge E by given predictor if possible. */
328 predict_edge_def (edge e
, enum br_predictor predictor
,
329 enum prediction taken
)
331 int probability
= predictor_info
[(int) predictor
].hitrate
;
334 probability
= REG_BR_PROB_BASE
- probability
;
336 predict_edge (e
, predictor
, probability
);
339 /* Invert all branch predictions or probability notes in the INSN. This needs
340 to be done each time we invert the condition used by the jump. */
343 invert_br_probabilities (rtx insn
)
347 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
348 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
349 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
350 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
351 XEXP (XEXP (note
, 0), 1)
352 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
355 /* Dump information about the branch prediction to the output file. */
358 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
359 basic_block bb
, int used
)
367 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
368 if (! (e
->flags
& EDGE_FALLTHRU
))
371 fprintf (file
, " %s heuristics%s: %.1f%%",
372 predictor_info
[predictor
].name
,
373 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
377 fprintf (file
, " exec ");
378 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
381 fprintf (file
, " hit ");
382 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
383 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
387 fprintf (file
, "\n");
390 /* We can not predict the probabilities of outgoing edges of bb. Set them
391 evenly and hope for the best. */
393 set_even_probabilities (basic_block bb
)
399 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
400 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
402 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
403 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
404 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
409 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
410 note if not already present. Remove now useless REG_BR_PRED notes. */
413 combine_predictions_for_insn (rtx insn
, basic_block bb
)
418 int best_probability
= PROB_EVEN
;
419 int best_predictor
= END_PREDICTORS
;
420 int combined_probability
= REG_BR_PROB_BASE
/ 2;
422 bool first_match
= false;
425 if (!can_predict_insn_p (insn
))
427 set_even_probabilities (bb
);
431 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
432 pnote
= ®_NOTES (insn
);
434 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
437 /* We implement "first match" heuristics and use probability guessed
438 by predictor with smallest index. */
439 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
440 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
442 int predictor
= INTVAL (XEXP (XEXP (note
, 0), 0));
443 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
446 if (best_predictor
> predictor
)
447 best_probability
= probability
, best_predictor
= predictor
;
449 d
= (combined_probability
* probability
450 + (REG_BR_PROB_BASE
- combined_probability
)
451 * (REG_BR_PROB_BASE
- probability
));
453 /* Use FP math to avoid overflows of 32bit integers. */
455 /* If one probability is 0% and one 100%, avoid division by zero. */
456 combined_probability
= REG_BR_PROB_BASE
/ 2;
458 combined_probability
= (((double) combined_probability
) * probability
459 * REG_BR_PROB_BASE
/ d
+ 0.5);
462 /* Decide which heuristic to use. In case we didn't match anything,
463 use no_prediction heuristic, in case we did match, use either
464 first match or Dempster-Shaffer theory depending on the flags. */
466 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
470 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
471 combined_probability
, bb
, true);
474 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
476 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
481 combined_probability
= best_probability
;
482 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
486 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
488 int predictor
= INTVAL (XEXP (XEXP (*pnote
, 0), 0));
489 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
491 dump_prediction (dump_file
, predictor
, probability
, bb
,
492 !first_match
|| best_predictor
== predictor
);
493 *pnote
= XEXP (*pnote
, 1);
496 pnote
= &XEXP (*pnote
, 1);
502 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
503 GEN_INT (combined_probability
), REG_NOTES (insn
));
505 /* Save the prediction into CFG in case we are seeing non-degenerated
507 if (!single_succ_p (bb
))
509 BRANCH_EDGE (bb
)->probability
= combined_probability
;
510 FALLTHRU_EDGE (bb
)->probability
511 = REG_BR_PROB_BASE
- combined_probability
;
514 else if (!single_succ_p (bb
))
516 int prob
= INTVAL (XEXP (prob_note
, 0));
518 BRANCH_EDGE (bb
)->probability
= prob
;
519 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
522 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
525 /* Combine predictions into single probability and store them into CFG.
526 Remove now useless prediction entries. */
529 combine_predictions_for_bb (basic_block bb
)
531 int best_probability
= PROB_EVEN
;
532 int best_predictor
= END_PREDICTORS
;
533 int combined_probability
= REG_BR_PROB_BASE
/ 2;
535 bool first_match
= false;
537 struct edge_prediction
*pred
;
539 edge e
, first
= NULL
, second
= NULL
;
542 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
543 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
546 if (first
&& !second
)
552 /* When there is no successor or only one choice, prediction is easy.
554 We are lazy for now and predict only basic blocks with two outgoing
555 edges. It is possible to predict generic case too, but we have to
556 ignore first match heuristics and do more involved combining. Implement
561 set_even_probabilities (bb
);
562 bb
->predictions
= NULL
;
564 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
570 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
572 /* We implement "first match" heuristics and use probability guessed
573 by predictor with smallest index. */
574 for (pred
= bb
->predictions
; pred
; pred
= pred
->ep_next
)
576 int predictor
= pred
->ep_predictor
;
577 int probability
= pred
->ep_probability
;
579 if (pred
->ep_edge
!= first
)
580 probability
= REG_BR_PROB_BASE
- probability
;
583 if (best_predictor
> predictor
)
584 best_probability
= probability
, best_predictor
= predictor
;
586 d
= (combined_probability
* probability
587 + (REG_BR_PROB_BASE
- combined_probability
)
588 * (REG_BR_PROB_BASE
- probability
));
590 /* Use FP math to avoid overflows of 32bit integers. */
592 /* If one probability is 0% and one 100%, avoid division by zero. */
593 combined_probability
= REG_BR_PROB_BASE
/ 2;
595 combined_probability
= (((double) combined_probability
) * probability
596 * REG_BR_PROB_BASE
/ d
+ 0.5);
599 /* Decide which heuristic to use. In case we didn't match anything,
600 use no_prediction heuristic, in case we did match, use either
601 first match or Dempster-Shaffer theory depending on the flags. */
603 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
607 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
610 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
612 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
617 combined_probability
= best_probability
;
618 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
620 for (pred
= bb
->predictions
; pred
; pred
= pred
->ep_next
)
622 int predictor
= pred
->ep_predictor
;
623 int probability
= pred
->ep_probability
;
625 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
626 probability
= REG_BR_PROB_BASE
- probability
;
627 dump_prediction (dump_file
, predictor
, probability
, bb
,
628 !first_match
|| best_predictor
== predictor
);
630 bb
->predictions
= NULL
;
634 first
->probability
= combined_probability
;
635 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
639 /* Predict edge probabilities by exploiting loop structure. */
649 /* Try to predict out blocks in a loop that are not part of a
651 FOR_EACH_LOOP (li
, loop
, 0)
653 basic_block bb
, *bbs
;
655 VEC (edge
, heap
) *exits
;
656 struct tree_niter_desc niter_desc
;
659 exits
= get_loop_exit_edges (loop
);
660 n_exits
= VEC_length (edge
, exits
);
662 for (j
= 0; VEC_iterate (edge
, exits
, j
, ex
); j
++)
665 HOST_WIDE_INT nitercst
;
666 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
668 enum br_predictor predictor
;
670 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
671 niter
= niter_desc
.niter
;
672 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
673 niter
= loop_niter_by_eval (loop
, ex
);
675 if (TREE_CODE (niter
) == INTEGER_CST
)
677 if (host_integerp (niter
, 1)
678 && compare_tree_int (niter
, max
-1) == -1)
679 nitercst
= tree_low_cst (niter
, 1) + 1;
682 predictor
= PRED_LOOP_ITERATIONS
;
684 /* If we have just one exit and we can derive some information about
685 the number of iterations of the loop from the statements inside
686 the loop, use it to predict this exit. */
687 else if (n_exits
== 1)
689 nitercst
= estimated_loop_iterations_int (loop
, false);
695 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
700 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
701 predict_edge (ex
, predictor
, probability
);
703 VEC_free (edge
, heap
, exits
);
705 bbs
= get_loop_body (loop
);
707 for (j
= 0; j
< loop
->num_nodes
; j
++)
709 int header_found
= 0;
715 /* Bypass loop heuristics on continue statement. These
716 statements construct loops via "non-loop" constructs
717 in the source language and are better to be handled
719 if (predicted_by_p (bb
, PRED_CONTINUE
))
722 /* Loop branch heuristics - predict an edge back to a
723 loop's head as taken. */
724 if (bb
== loop
->latch
)
726 e
= find_edge (loop
->latch
, loop
->header
);
730 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
734 /* Loop exit heuristics - predict an edge exiting the loop if the
735 conditional has no loop header successors as not taken. */
737 /* If we already used more reliable loop exit predictors, do not
738 bother with PRED_LOOP_EXIT. */
739 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
740 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
742 /* For loop with many exits we don't want to predict all exits
743 with the pretty large probability, because if all exits are
744 considered in row, the loop would be predicted to iterate
745 almost never. The code to divide probability by number of
746 exits is very rough. It should compute the number of exits
747 taken in each patch through function (not the overall number
748 of exits that might be a lot higher for loops with wide switch
749 statements in them) and compute n-th square root.
751 We limit the minimal probability by 2% to avoid
752 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
753 as this was causing regression in perl benchmark containing such
756 int probability
= ((REG_BR_PROB_BASE
757 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
759 if (probability
< HITRATE (2))
760 probability
= HITRATE (2);
761 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
762 if (e
->dest
->index
< NUM_FIXED_BLOCKS
763 || !flow_bb_inside_loop_p (loop
, e
->dest
))
764 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
768 /* Free basic blocks from get_loop_body. */
775 /* Attempt to predict probabilities of BB outgoing edges using local
778 bb_estimate_probability_locally (basic_block bb
)
780 rtx last_insn
= BB_END (bb
);
783 if (! can_predict_insn_p (last_insn
))
785 cond
= get_condition (last_insn
, NULL
, false, false);
789 /* Try "pointer heuristic."
790 A comparison ptr == 0 is predicted as false.
791 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
792 if (COMPARISON_P (cond
)
793 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
794 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
796 if (GET_CODE (cond
) == EQ
)
797 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
798 else if (GET_CODE (cond
) == NE
)
799 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
803 /* Try "opcode heuristic."
804 EQ tests are usually false and NE tests are usually true. Also,
805 most quantities are positive, so we can make the appropriate guesses
806 about signed comparisons against zero. */
807 switch (GET_CODE (cond
))
810 /* Unconditional branch. */
811 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
812 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
817 /* Floating point comparisons appears to behave in a very
818 unpredictable way because of special role of = tests in
820 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
822 /* Comparisons with 0 are often used for booleans and there is
823 nothing useful to predict about them. */
824 else if (XEXP (cond
, 1) == const0_rtx
825 || XEXP (cond
, 0) == const0_rtx
)
828 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
833 /* Floating point comparisons appears to behave in a very
834 unpredictable way because of special role of = tests in
836 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
838 /* Comparisons with 0 are often used for booleans and there is
839 nothing useful to predict about them. */
840 else if (XEXP (cond
, 1) == const0_rtx
841 || XEXP (cond
, 0) == const0_rtx
)
844 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
848 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
852 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
857 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
858 || XEXP (cond
, 1) == constm1_rtx
)
859 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
864 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
865 || XEXP (cond
, 1) == constm1_rtx
)
866 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
874 /* Set edge->probability for each successor edge of BB. */
876 guess_outgoing_edge_probabilities (basic_block bb
)
878 bb_estimate_probability_locally (bb
);
879 combine_predictions_for_insn (BB_END (bb
), bb
);
882 /* Return constant EXPR will likely have at execution time, NULL if unknown.
883 The function is used by builtin_expect branch predictor so the evidence
884 must come from this construct and additional possible constant folding.
886 We may want to implement more involved value guess (such as value range
887 propagation based prediction), but such tricks shall go to new
891 expr_expected_value (tree expr
, bitmap visited
)
893 if (TREE_CONSTANT (expr
))
895 else if (TREE_CODE (expr
) == SSA_NAME
)
897 tree def
= SSA_NAME_DEF_STMT (expr
);
899 /* If we were already here, break the infinite cycle. */
900 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (expr
)))
902 bitmap_set_bit (visited
, SSA_NAME_VERSION (expr
));
904 if (TREE_CODE (def
) == PHI_NODE
)
906 /* All the arguments of the PHI node must have the same constant
909 tree val
= NULL
, new_val
;
911 for (i
= 0; i
< PHI_NUM_ARGS (def
); i
++)
913 tree arg
= PHI_ARG_DEF (def
, i
);
915 /* If this PHI has itself as an argument, we cannot
916 determine the string length of this argument. However,
917 if we can find an expected constant value for the other
918 PHI args then we can still be sure that this is
919 likely a constant. So be optimistic and just
920 continue with the next argument. */
921 if (arg
== PHI_RESULT (def
))
924 new_val
= expr_expected_value (arg
, visited
);
929 else if (!operand_equal_p (val
, new_val
, false))
934 if (TREE_CODE (def
) != GIMPLE_MODIFY_STMT
935 || GIMPLE_STMT_OPERAND (def
, 0) != expr
)
937 return expr_expected_value (GIMPLE_STMT_OPERAND (def
, 1), visited
);
939 else if (TREE_CODE (expr
) == CALL_EXPR
)
941 tree decl
= get_callee_fndecl (expr
);
944 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
945 && DECL_FUNCTION_CODE (decl
) == BUILT_IN_EXPECT
)
949 if (call_expr_nargs (expr
) != 2)
951 val
= CALL_EXPR_ARG (expr
, 0);
952 if (TREE_CONSTANT (val
))
954 return CALL_EXPR_ARG (expr
, 1);
957 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
960 op0
= expr_expected_value (TREE_OPERAND (expr
, 0), visited
);
963 op1
= expr_expected_value (TREE_OPERAND (expr
, 1), visited
);
966 res
= fold_build2 (TREE_CODE (expr
), TREE_TYPE (expr
), op0
, op1
);
967 if (TREE_CONSTANT (res
))
971 if (UNARY_CLASS_P (expr
))
974 op0
= expr_expected_value (TREE_OPERAND (expr
, 0), visited
);
977 res
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
), op0
);
978 if (TREE_CONSTANT (res
))
985 /* Get rid of all builtin_expect calls we no longer need. */
987 strip_builtin_expect (void)
992 block_stmt_iterator bi
;
993 for (bi
= bsi_start (bb
); !bsi_end_p (bi
); bsi_next (&bi
))
995 tree stmt
= bsi_stmt (bi
);
999 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1000 && (call
= GIMPLE_STMT_OPERAND (stmt
, 1))
1001 && TREE_CODE (call
) == CALL_EXPR
1002 && (fndecl
= get_callee_fndecl (call
))
1003 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
1004 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
1005 && call_expr_nargs (call
) == 2)
1007 GIMPLE_STMT_OPERAND (stmt
, 1) = CALL_EXPR_ARG (call
, 0);
1014 /* Predict using opcode of the last statement in basic block. */
1016 tree_predict_by_opcode (basic_block bb
)
1018 tree stmt
= last_stmt (bb
);
1027 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
1029 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1030 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1032 cond
= TREE_OPERAND (stmt
, 0);
1033 if (!COMPARISON_CLASS_P (cond
))
1035 op0
= TREE_OPERAND (cond
, 0);
1036 type
= TREE_TYPE (op0
);
1037 visited
= BITMAP_ALLOC (NULL
);
1038 val
= expr_expected_value (cond
, visited
);
1039 BITMAP_FREE (visited
);
1042 if (integer_zerop (val
))
1043 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, NOT_TAKEN
);
1045 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, TAKEN
);
1048 /* Try "pointer heuristic."
1049 A comparison ptr == 0 is predicted as false.
1050 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1051 if (POINTER_TYPE_P (type
))
1053 if (TREE_CODE (cond
) == EQ_EXPR
)
1054 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1055 else if (TREE_CODE (cond
) == NE_EXPR
)
1056 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1060 /* Try "opcode heuristic."
1061 EQ tests are usually false and NE tests are usually true. Also,
1062 most quantities are positive, so we can make the appropriate guesses
1063 about signed comparisons against zero. */
1064 switch (TREE_CODE (cond
))
1068 /* Floating point comparisons appears to behave in a very
1069 unpredictable way because of special role of = tests in
1071 if (FLOAT_TYPE_P (type
))
1073 /* Comparisons with 0 are often used for booleans and there is
1074 nothing useful to predict about them. */
1075 else if (integer_zerop (op0
)
1076 || integer_zerop (TREE_OPERAND (cond
, 1)))
1079 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
1084 /* Floating point comparisons appears to behave in a very
1085 unpredictable way because of special role of = tests in
1087 if (FLOAT_TYPE_P (type
))
1089 /* Comparisons with 0 are often used for booleans and there is
1090 nothing useful to predict about them. */
1091 else if (integer_zerop (op0
)
1092 || integer_zerop (TREE_OPERAND (cond
, 1)))
1095 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
1099 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
1102 case UNORDERED_EXPR
:
1103 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
1108 if (integer_zerop (TREE_OPERAND (cond
, 1))
1109 || integer_onep (TREE_OPERAND (cond
, 1))
1110 || integer_all_onesp (TREE_OPERAND (cond
, 1))
1111 || real_zerop (TREE_OPERAND (cond
, 1))
1112 || real_onep (TREE_OPERAND (cond
, 1))
1113 || real_minus_onep (TREE_OPERAND (cond
, 1)))
1114 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
1119 if (integer_zerop (TREE_OPERAND (cond
, 1))
1120 || integer_onep (TREE_OPERAND (cond
, 1))
1121 || integer_all_onesp (TREE_OPERAND (cond
, 1))
1122 || real_zerop (TREE_OPERAND (cond
, 1))
1123 || real_onep (TREE_OPERAND (cond
, 1))
1124 || real_minus_onep (TREE_OPERAND (cond
, 1)))
1125 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
1133 /* Try to guess whether the value of return means error code. */
1134 static enum br_predictor
1135 return_prediction (tree val
, enum prediction
*prediction
)
1139 return PRED_NO_PREDICTION
;
1140 /* Different heuristics for pointers and scalars. */
1141 if (POINTER_TYPE_P (TREE_TYPE (val
)))
1143 /* NULL is usually not returned. */
1144 if (integer_zerop (val
))
1146 *prediction
= NOT_TAKEN
;
1147 return PRED_NULL_RETURN
;
1150 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
1152 /* Negative return values are often used to indicate
1154 if (TREE_CODE (val
) == INTEGER_CST
1155 && tree_int_cst_sgn (val
) < 0)
1157 *prediction
= NOT_TAKEN
;
1158 return PRED_NEGATIVE_RETURN
;
1160 /* Constant return values seems to be commonly taken.
1161 Zero/one often represent booleans so exclude them from the
1163 if (TREE_CONSTANT (val
)
1164 && (!integer_zerop (val
) && !integer_onep (val
)))
1166 *prediction
= TAKEN
;
1167 return PRED_CONST_RETURN
;
1170 return PRED_NO_PREDICTION
;
1173 /* Find the basic block with return expression and look up for possible
1174 return value trying to apply RETURN_PREDICTION heuristics. */
1176 apply_return_prediction (int *heads
)
1178 tree return_stmt
= NULL
;
1182 int phi_num_args
, i
;
1183 enum br_predictor pred
;
1184 enum prediction direction
;
1187 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1189 return_stmt
= last_stmt (e
->src
);
1190 if (TREE_CODE (return_stmt
) == RETURN_EXPR
)
1195 return_val
= TREE_OPERAND (return_stmt
, 0);
1198 if (TREE_CODE (return_val
) == GIMPLE_MODIFY_STMT
)
1199 return_val
= GIMPLE_STMT_OPERAND (return_val
, 1);
1200 if (TREE_CODE (return_val
) != SSA_NAME
1201 || !SSA_NAME_DEF_STMT (return_val
)
1202 || TREE_CODE (SSA_NAME_DEF_STMT (return_val
)) != PHI_NODE
)
1204 for (phi
= SSA_NAME_DEF_STMT (return_val
); phi
; phi
= PHI_CHAIN (phi
))
1205 if (PHI_RESULT (phi
) == return_val
)
1209 phi_num_args
= PHI_NUM_ARGS (phi
);
1210 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
1212 /* Avoid the degenerate case where all return values form the function
1213 belongs to same category (ie they are all positive constants)
1214 so we can hardly say something about them. */
1215 for (i
= 1; i
< phi_num_args
; i
++)
1216 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
1218 if (i
!= phi_num_args
)
1219 for (i
= 0; i
< phi_num_args
; i
++)
1221 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
1222 if (pred
!= PRED_NO_PREDICTION
)
1223 predict_paths_leading_to (PHI_ARG_EDGE (phi
, i
)->src
, heads
, pred
,
1228 /* Look for basic block that contains unlikely to happen events
1229 (such as noreturn calls) and mark all paths leading to execution
1230 of this basic blocks as unlikely. */
1233 tree_bb_level_predictions (void)
1238 heads
= XCNEWVEC (int, last_basic_block
);
1239 heads
[ENTRY_BLOCK_PTR
->next_bb
->index
] = last_basic_block
;
1241 apply_return_prediction (heads
);
1245 block_stmt_iterator bsi
= bsi_last (bb
);
1247 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1249 tree stmt
= bsi_stmt (bsi
);
1251 switch (TREE_CODE (stmt
))
1253 case GIMPLE_MODIFY_STMT
:
1254 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == CALL_EXPR
)
1256 stmt
= GIMPLE_STMT_OPERAND (stmt
, 1);
1262 if (call_expr_flags (stmt
) & ECF_NORETURN
)
1263 predict_paths_leading_to (bb
, heads
, PRED_NORETURN
,
1265 decl
= get_callee_fndecl (stmt
);
1267 && lookup_attribute ("cold",
1268 DECL_ATTRIBUTES (decl
)))
1269 predict_paths_leading_to (bb
, heads
, PRED_COLD_FUNCTION
,
1281 /* Predict branch probabilities and estimate profile of the tree CFG. */
1283 tree_estimate_probability (void)
1287 loop_optimizer_init (0);
1288 if (current_loops
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
1289 flow_loops_dump (dump_file
, NULL
, 0);
1291 add_noreturn_fake_exit_edges ();
1292 connect_infinite_loops_to_exit ();
1293 /* We use loop_niter_by_eval, which requires that the loops have
1295 create_preheaders (CP_SIMPLE_PREHEADERS
);
1296 calculate_dominance_info (CDI_POST_DOMINATORS
);
1298 tree_bb_level_predictions ();
1300 mark_irreducible_loops ();
1301 record_loop_exits ();
1310 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1312 /* Predict early returns to be probable, as we've already taken
1313 care for error returns and other cases are often used for
1314 fast paths through function.
1316 Since we've already removed the return statements, we are
1317 looking for CFG like:
1327 if (e
->dest
!= bb
->next_bb
1328 && e
->dest
!= EXIT_BLOCK_PTR
1329 && single_succ_p (e
->dest
)
1330 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR
1331 && TREE_CODE (last_stmt (e
->dest
)) == RETURN_EXPR
)
1336 if (single_succ_p (bb
))
1338 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
1339 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
1340 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
1341 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
1342 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1345 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
1346 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
1347 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
1348 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1351 /* Look for block we are guarding (ie we dominate it,
1352 but it doesn't postdominate us). */
1353 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
1354 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
1355 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
1357 block_stmt_iterator bi
;
1359 /* The call heuristic claims that a guarded function call
1360 is improbable. This is because such calls are often used
1361 to signal exceptional situations such as printing error
1363 for (bi
= bsi_start (e
->dest
); !bsi_end_p (bi
);
1366 tree stmt
= bsi_stmt (bi
);
1367 if ((TREE_CODE (stmt
) == CALL_EXPR
1368 || (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1369 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1))
1371 /* Constant and pure calls are hardly used to signalize
1372 something exceptional. */
1373 && TREE_SIDE_EFFECTS (stmt
))
1375 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
1381 tree_predict_by_opcode (bb
);
1384 combine_predictions_for_bb (bb
);
1386 strip_builtin_expect ();
1387 estimate_bb_frequencies ();
1388 free_dominance_info (CDI_POST_DOMINATORS
);
1389 remove_fake_exit_edges ();
1390 loop_optimizer_finalize ();
1391 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1392 dump_tree_cfg (dump_file
, dump_flags
);
1393 if (profile_status
== PROFILE_ABSENT
)
1394 profile_status
= PROFILE_GUESSED
;
1398 /* Sets branch probabilities according to PREDiction and
1399 FLAGS. HEADS[bb->index] should be index of basic block in that we
1400 need to alter branch predictions (i.e. the first of our dominators
1401 such that we do not post-dominate it) (but we fill this information
1402 on demand, so -1 may be there in case this was not needed yet). */
1405 predict_paths_leading_to (basic_block bb
, int *heads
, enum br_predictor pred
,
1406 enum prediction taken
)
1412 if (heads
[bb
->index
] == ENTRY_BLOCK
)
1414 /* This is first time we need this field in heads array; so
1415 find first dominator that we do not post-dominate (we are
1416 using already known members of heads array). */
1417 basic_block ai
= bb
;
1418 basic_block next_ai
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1421 while (heads
[next_ai
->index
] == ENTRY_BLOCK
)
1423 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
1425 heads
[next_ai
->index
] = ai
->index
;
1427 next_ai
= get_immediate_dominator (CDI_DOMINATORS
, next_ai
);
1429 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
1430 head
= next_ai
->index
;
1432 head
= heads
[next_ai
->index
];
1433 while (next_ai
!= bb
)
1436 ai
= BASIC_BLOCK (heads
[ai
->index
]);
1437 heads
[next_ai
->index
] = head
;
1440 y
= heads
[bb
->index
];
1442 /* Now find the edge that leads to our branch and aply the prediction. */
1444 if (y
== last_basic_block
)
1446 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (y
)->succs
)
1447 if (e
->dest
->index
>= NUM_FIXED_BLOCKS
1448 && dominated_by_p (CDI_POST_DOMINATORS
, e
->dest
, bb
))
1449 predict_edge_def (e
, pred
, taken
);
1452 /* This is used to carry information about basic blocks. It is
1453 attached to the AUX field of the standard CFG block. */
1455 typedef struct block_info_def
1457 /* Estimated frequency of execution of basic_block. */
1460 /* To keep queue of basic blocks to process. */
1463 /* Number of predecessors we need to visit first. */
1467 /* Similar information for edges. */
1468 typedef struct edge_info_def
1470 /* In case edge is a loopback edge, the probability edge will be reached
1471 in case header is. Estimated number of iterations of the loop can be
1472 then computed as 1 / (1 - back_edge_prob). */
1473 sreal back_edge_prob
;
1474 /* True if the edge is a loopback edge in the natural loop. */
1475 unsigned int back_edge
:1;
1478 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1479 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1481 /* Helper function for estimate_bb_frequencies.
1482 Propagate the frequencies in blocks marked in
1483 TOVISIT, starting in HEAD. */
1486 propagate_freq (basic_block head
, bitmap tovisit
)
1495 /* For each basic block we need to visit count number of his predecessors
1496 we need to visit first. */
1497 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
1502 /* The outermost "loop" includes the exit block, which we can not
1503 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1504 directly. Do the same for the entry block. */
1505 bb
= BASIC_BLOCK (i
);
1507 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1509 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
1511 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
1513 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
1515 "Irreducible region hit, ignoring edge to %i->%i\n",
1516 e
->src
->index
, bb
->index
);
1518 BLOCK_INFO (bb
)->npredecessors
= count
;
1521 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
1523 for (bb
= head
; bb
; bb
= nextbb
)
1526 sreal cyclic_probability
, frequency
;
1528 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
1529 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
1531 nextbb
= BLOCK_INFO (bb
)->next
;
1532 BLOCK_INFO (bb
)->next
= NULL
;
1534 /* Compute frequency of basic block. */
1537 #ifdef ENABLE_CHECKING
1538 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1539 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
1540 || (e
->flags
& EDGE_DFS_BACK
));
1543 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1544 if (EDGE_INFO (e
)->back_edge
)
1546 sreal_add (&cyclic_probability
, &cyclic_probability
,
1547 &EDGE_INFO (e
)->back_edge_prob
);
1549 else if (!(e
->flags
& EDGE_DFS_BACK
))
1553 /* frequency += (e->probability
1554 * BLOCK_INFO (e->src)->frequency /
1555 REG_BR_PROB_BASE); */
1557 sreal_init (&tmp
, e
->probability
, 0);
1558 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
1559 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
1560 sreal_add (&frequency
, &frequency
, &tmp
);
1563 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
1565 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
1566 sizeof (frequency
));
1570 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
1572 memcpy (&cyclic_probability
, &real_almost_one
,
1573 sizeof (real_almost_one
));
1576 /* BLOCK_INFO (bb)->frequency = frequency
1577 / (1 - cyclic_probability) */
1579 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
1580 sreal_div (&BLOCK_INFO (bb
)->frequency
,
1581 &frequency
, &cyclic_probability
);
1585 bitmap_clear_bit (tovisit
, bb
->index
);
1587 e
= find_edge (bb
, head
);
1592 /* EDGE_INFO (e)->back_edge_prob
1593 = ((e->probability * BLOCK_INFO (bb)->frequency)
1594 / REG_BR_PROB_BASE); */
1596 sreal_init (&tmp
, e
->probability
, 0);
1597 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
1598 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1599 &tmp
, &real_inv_br_prob_base
);
1602 /* Propagate to successor blocks. */
1603 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1604 if (!(e
->flags
& EDGE_DFS_BACK
)
1605 && BLOCK_INFO (e
->dest
)->npredecessors
)
1607 BLOCK_INFO (e
->dest
)->npredecessors
--;
1608 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
1613 BLOCK_INFO (last
)->next
= e
->dest
;
1621 /* Estimate probabilities of loopback edges in loops at same nest level. */
1624 estimate_loops_at_level (struct loop
*first_loop
)
1628 for (loop
= first_loop
; loop
; loop
= loop
->next
)
1633 bitmap tovisit
= BITMAP_ALLOC (NULL
);
1635 estimate_loops_at_level (loop
->inner
);
1637 /* Find current loop back edge and mark it. */
1638 e
= loop_latch_edge (loop
);
1639 EDGE_INFO (e
)->back_edge
= 1;
1641 bbs
= get_loop_body (loop
);
1642 for (i
= 0; i
< loop
->num_nodes
; i
++)
1643 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
1645 propagate_freq (loop
->header
, tovisit
);
1646 BITMAP_FREE (tovisit
);
1650 /* Propagates frequencies through structure of loops. */
1653 estimate_loops (void)
1655 bitmap tovisit
= BITMAP_ALLOC (NULL
);
1658 /* Start by estimating the frequencies in the loops. */
1660 estimate_loops_at_level (current_loops
->tree_root
->inner
);
1662 /* Now propagate the frequencies through all the blocks. */
1665 bitmap_set_bit (tovisit
, bb
->index
);
1667 propagate_freq (ENTRY_BLOCK_PTR
, tovisit
);
1668 BITMAP_FREE (tovisit
);
1671 /* Convert counts measured by profile driven feedback to frequencies.
1672 Return nonzero iff there was any nonzero execution count. */
1675 counts_to_freqs (void)
1677 gcov_type count_max
, true_count_max
= 0;
1681 true_count_max
= MAX (bb
->count
, true_count_max
);
1683 count_max
= MAX (true_count_max
, 1);
1684 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1685 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
1687 return true_count_max
;
1690 /* Return true if function is likely to be expensive, so there is no point to
1691 optimize performance of prologue, epilogue or do inlining at the expense
1692 of code size growth. THRESHOLD is the limit of number of instructions
1693 function can execute at average to be still considered not expensive. */
1696 expensive_function_p (int threshold
)
1698 unsigned int sum
= 0;
1702 /* We can not compute accurately for large thresholds due to scaled
1704 gcc_assert (threshold
<= BB_FREQ_MAX
);
1706 /* Frequencies are out of range. This either means that function contains
1707 internal loop executing more than BB_FREQ_MAX times or profile feedback
1708 is available and function has not been executed at all. */
1709 if (ENTRY_BLOCK_PTR
->frequency
== 0)
1712 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1713 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
1718 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
1719 insn
= NEXT_INSN (insn
))
1720 if (active_insn_p (insn
))
1722 sum
+= bb
->frequency
;
1731 /* Estimate basic blocks frequency by given branch probabilities. */
1734 estimate_bb_frequencies (void)
1739 if (!flag_branch_probabilities
|| !counts_to_freqs ())
1741 static int real_values_initialized
= 0;
1743 if (!real_values_initialized
)
1745 real_values_initialized
= 1;
1746 sreal_init (&real_zero
, 0, 0);
1747 sreal_init (&real_one
, 1, 0);
1748 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
1749 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
1750 sreal_init (&real_one_half
, 1, -1);
1751 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
1752 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
1755 mark_dfs_back_edges ();
1757 single_succ_edge (ENTRY_BLOCK_PTR
)->probability
= REG_BR_PROB_BASE
;
1759 /* Set up block info for each basic block. */
1760 alloc_aux_for_blocks (sizeof (struct block_info_def
));
1761 alloc_aux_for_edges (sizeof (struct edge_info_def
));
1762 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1767 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1769 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
1770 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1771 &EDGE_INFO (e
)->back_edge_prob
,
1772 &real_inv_br_prob_base
);
1776 /* First compute probabilities locally for each loop from innermost
1777 to outermost to examine probabilities for back edges. */
1780 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
1782 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
1783 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
1785 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
1786 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1790 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
1791 sreal_add (&tmp
, &tmp
, &real_one_half
);
1792 bb
->frequency
= sreal_to_int (&tmp
);
1795 free_aux_for_blocks ();
1796 free_aux_for_edges ();
1798 compute_function_frequency ();
1799 if (flag_reorder_functions
)
1800 choose_function_section ();
1803 /* Decide whether function is hot, cold or unlikely executed. */
1805 compute_function_frequency (void)
1809 if (!profile_info
|| !flag_branch_probabilities
)
1811 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
1813 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
1814 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
1816 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
1819 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
1822 if (maybe_hot_bb_p (bb
))
1824 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
1827 if (!probably_never_executed_bb_p (bb
))
1828 cfun
->function_frequency
= FUNCTION_FREQUENCY_NORMAL
;
1832 /* Choose appropriate section for the function. */
1834 choose_function_section (void)
1836 if (DECL_SECTION_NAME (current_function_decl
)
1837 || !targetm
.have_named_sections
1838 /* Theoretically we can split the gnu.linkonce text section too,
1839 but this requires more work as the frequency needs to match
1840 for all generated objects so we need to merge the frequency
1841 of all instances. For now just never set frequency for these. */
1842 || DECL_ONE_ONLY (current_function_decl
))
1845 /* If we are doing the partitioning optimization, let the optimization
1846 choose the correct section into which to put things. */
1848 if (flag_reorder_blocks_and_partition
)
1851 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
1852 DECL_SECTION_NAME (current_function_decl
) =
1853 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
1854 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
1855 DECL_SECTION_NAME (current_function_decl
) =
1856 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
1857 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);
1861 gate_estimate_probability (void)
1863 return flag_guess_branch_prob
;
1866 struct tree_opt_pass pass_profile
=
1868 "profile", /* name */
1869 gate_estimate_probability
, /* gate */
1870 tree_estimate_probability
, /* execute */
1873 0, /* static_pass_number */
1874 TV_BRANCH_PROB
, /* tv_id */
1875 PROP_cfg
, /* properties_required */
1876 0, /* properties_provided */
1877 0, /* properties_destroyed */
1878 0, /* todo_flags_start */
1879 TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */