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"
63 #include "pointer-set.h"
65 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
66 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
67 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
68 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
70 /* Random guesstimation given names. */
71 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 100 - 1)
72 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
73 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
74 #define PROB_ALWAYS (REG_BR_PROB_BASE)
76 static void combine_predictions_for_insn (rtx
, basic_block
);
77 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
78 static void predict_paths_leading_to (basic_block
, int *, enum br_predictor
, enum prediction
);
79 static void compute_function_frequency (void);
80 static void choose_function_section (void);
81 static bool can_predict_insn_p (rtx
);
83 /* Information we hold about each branch predictor.
84 Filled using information from predict.def. */
88 const char *const name
; /* Name used in the debugging dumps. */
89 const int hitrate
; /* Expected hitrate used by
90 predict_insn_def call. */
94 /* Use given predictor without Dempster-Shaffer theory if it matches
95 using first_match heuristics. */
96 #define PRED_FLAG_FIRST_MATCH 1
98 /* Recompute hitrate in percent to our representation. */
100 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
102 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
103 static const struct predictor_info predictor_info
[]= {
104 #include "predict.def"
106 /* Upper bound on predictors. */
111 /* Return true in case BB can be CPU intensive and should be optimized
112 for maximal performance. */
115 maybe_hot_bb_p (basic_block bb
)
117 if (profile_info
&& flag_branch_probabilities
119 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
121 if (!profile_info
|| !flag_branch_probabilities
)
123 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
125 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
128 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
133 /* Return true in case BB is cold and should be optimized for size. */
136 probably_cold_bb_p (basic_block bb
)
138 if (profile_info
&& flag_branch_probabilities
140 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
142 if ((!profile_info
|| !flag_branch_probabilities
)
143 && cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
145 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
150 /* Return true in case BB is probably never executed. */
152 probably_never_executed_bb_p (basic_block bb
)
154 if (profile_info
&& flag_branch_probabilities
)
155 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
156 if ((!profile_info
|| !flag_branch_probabilities
)
157 && cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
162 /* Return true if the one of outgoing edges is already predicted by
166 rtl_predicted_by_p (basic_block bb
, enum br_predictor predictor
)
169 if (!INSN_P (BB_END (bb
)))
171 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
172 if (REG_NOTE_KIND (note
) == REG_BR_PRED
173 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
178 /* This map contains for a basic block the list of predictions for the
181 static struct pointer_map_t
*bb_predictions
;
183 /* Return true if the one of outgoing edges is already predicted by
187 tree_predicted_by_p (basic_block bb
, enum br_predictor predictor
)
189 struct edge_prediction
*i
;
190 void **preds
= pointer_map_contains (bb_predictions
, bb
);
195 for (i
= *preds
; i
; i
= i
->ep_next
)
196 if (i
->ep_predictor
== predictor
)
201 /* Return true when the probability of edge is reliable.
203 The profile guessing code is good at predicting branch outcome (ie.
204 taken/not taken), that is predicted right slightly over 75% of time.
205 It is however notoriously poor on predicting the probability itself.
206 In general the profile appear a lot flatter (with probabilities closer
207 to 50%) than the reality so it is bad idea to use it to drive optimization
208 such as those disabling dynamic branch prediction for well predictable
211 There are two exceptions - edges leading to noreturn edges and edges
212 predicted by number of iterations heuristics are predicted well. This macro
213 should be able to distinguish those, but at the moment it simply check for
214 noreturn heuristic that is only one giving probability over 99% or bellow
215 1%. In future we might want to propagate reliability information across the
216 CFG if we find this information useful on multiple places. */
218 probability_reliable_p (int prob
)
220 return (profile_status
== PROFILE_READ
221 || (profile_status
== PROFILE_GUESSED
222 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
225 /* Same predicate as above, working on edges. */
227 edge_probability_reliable_p (edge e
)
229 return probability_reliable_p (e
->probability
);
232 /* Same predicate as edge_probability_reliable_p, working on notes. */
234 br_prob_note_reliable_p (rtx note
)
236 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
237 return probability_reliable_p (INTVAL (XEXP (note
, 0)));
241 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
243 gcc_assert (any_condjump_p (insn
));
244 if (!flag_guess_branch_prob
)
248 = gen_rtx_EXPR_LIST (REG_BR_PRED
,
249 gen_rtx_CONCAT (VOIDmode
,
250 GEN_INT ((int) predictor
),
251 GEN_INT ((int) probability
)),
255 /* Predict insn by given predictor. */
258 predict_insn_def (rtx insn
, enum br_predictor predictor
,
259 enum prediction taken
)
261 int probability
= predictor_info
[(int) predictor
].hitrate
;
264 probability
= REG_BR_PROB_BASE
- probability
;
266 predict_insn (insn
, predictor
, probability
);
269 /* Predict edge E with given probability if possible. */
272 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
275 last_insn
= BB_END (e
->src
);
277 /* We can store the branch prediction information only about
278 conditional jumps. */
279 if (!any_condjump_p (last_insn
))
282 /* We always store probability of branching. */
283 if (e
->flags
& EDGE_FALLTHRU
)
284 probability
= REG_BR_PROB_BASE
- probability
;
286 predict_insn (last_insn
, predictor
, probability
);
289 /* Predict edge E with the given PROBABILITY. */
291 tree_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
293 gcc_assert (profile_status
!= PROFILE_GUESSED
);
294 if ((e
->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (e
->src
->succs
) > 1)
295 && flag_guess_branch_prob
&& optimize
)
297 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
298 void **preds
= pointer_map_insert (bb_predictions
, e
->src
);
302 i
->ep_probability
= probability
;
303 i
->ep_predictor
= predictor
;
308 /* Remove all predictions on given basic block that are attached
311 remove_predictions_associated_with_edge (edge e
)
318 preds
= pointer_map_contains (bb_predictions
, e
->src
);
322 struct edge_prediction
**prediction
= (struct edge_prediction
**) preds
;
323 struct edge_prediction
*next
;
327 if ((*prediction
)->ep_edge
== e
)
329 next
= (*prediction
)->ep_next
;
334 prediction
= &((*prediction
)->ep_next
);
339 /* Clears the list of predictions stored for BB. */
342 clear_bb_predictions (basic_block bb
)
344 void **preds
= pointer_map_contains (bb_predictions
, bb
);
345 struct edge_prediction
*pred
, *next
;
350 for (pred
= *preds
; pred
; pred
= next
)
352 next
= pred
->ep_next
;
358 /* Return true when we can store prediction on insn INSN.
359 At the moment we represent predictions only on conditional
360 jumps, not at computed jump or other complicated cases. */
362 can_predict_insn_p (rtx insn
)
364 return (JUMP_P (insn
)
365 && any_condjump_p (insn
)
366 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
369 /* Predict edge E by given predictor if possible. */
372 predict_edge_def (edge e
, enum br_predictor predictor
,
373 enum prediction taken
)
375 int probability
= predictor_info
[(int) predictor
].hitrate
;
378 probability
= REG_BR_PROB_BASE
- probability
;
380 predict_edge (e
, predictor
, probability
);
383 /* Invert all branch predictions or probability notes in the INSN. This needs
384 to be done each time we invert the condition used by the jump. */
387 invert_br_probabilities (rtx insn
)
391 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
392 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
393 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
394 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
395 XEXP (XEXP (note
, 0), 1)
396 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
399 /* Dump information about the branch prediction to the output file. */
402 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
403 basic_block bb
, int used
)
411 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
412 if (! (e
->flags
& EDGE_FALLTHRU
))
415 fprintf (file
, " %s heuristics%s: %.1f%%",
416 predictor_info
[predictor
].name
,
417 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
421 fprintf (file
, " exec ");
422 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
425 fprintf (file
, " hit ");
426 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
427 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
431 fprintf (file
, "\n");
434 /* We can not predict the probabilities of outgoing edges of bb. Set them
435 evenly and hope for the best. */
437 set_even_probabilities (basic_block bb
)
443 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
444 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
446 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
447 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
448 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
453 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
454 note if not already present. Remove now useless REG_BR_PRED notes. */
457 combine_predictions_for_insn (rtx insn
, basic_block bb
)
462 int best_probability
= PROB_EVEN
;
463 int best_predictor
= END_PREDICTORS
;
464 int combined_probability
= REG_BR_PROB_BASE
/ 2;
466 bool first_match
= false;
469 if (!can_predict_insn_p (insn
))
471 set_even_probabilities (bb
);
475 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
476 pnote
= ®_NOTES (insn
);
478 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
481 /* We implement "first match" heuristics and use probability guessed
482 by predictor with smallest index. */
483 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
484 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
486 int predictor
= INTVAL (XEXP (XEXP (note
, 0), 0));
487 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
490 if (best_predictor
> predictor
)
491 best_probability
= probability
, best_predictor
= predictor
;
493 d
= (combined_probability
* probability
494 + (REG_BR_PROB_BASE
- combined_probability
)
495 * (REG_BR_PROB_BASE
- probability
));
497 /* Use FP math to avoid overflows of 32bit integers. */
499 /* If one probability is 0% and one 100%, avoid division by zero. */
500 combined_probability
= REG_BR_PROB_BASE
/ 2;
502 combined_probability
= (((double) combined_probability
) * probability
503 * REG_BR_PROB_BASE
/ d
+ 0.5);
506 /* Decide which heuristic to use. In case we didn't match anything,
507 use no_prediction heuristic, in case we did match, use either
508 first match or Dempster-Shaffer theory depending on the flags. */
510 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
514 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
515 combined_probability
, bb
, true);
518 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
520 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
525 combined_probability
= best_probability
;
526 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
530 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
532 int predictor
= INTVAL (XEXP (XEXP (*pnote
, 0), 0));
533 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
535 dump_prediction (dump_file
, predictor
, probability
, bb
,
536 !first_match
|| best_predictor
== predictor
);
537 *pnote
= XEXP (*pnote
, 1);
540 pnote
= &XEXP (*pnote
, 1);
546 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
547 GEN_INT (combined_probability
), REG_NOTES (insn
));
549 /* Save the prediction into CFG in case we are seeing non-degenerated
551 if (!single_succ_p (bb
))
553 BRANCH_EDGE (bb
)->probability
= combined_probability
;
554 FALLTHRU_EDGE (bb
)->probability
555 = REG_BR_PROB_BASE
- combined_probability
;
558 else if (!single_succ_p (bb
))
560 int prob
= INTVAL (XEXP (prob_note
, 0));
562 BRANCH_EDGE (bb
)->probability
= prob
;
563 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
566 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
569 /* Combine predictions into single probability and store them into CFG.
570 Remove now useless prediction entries. */
573 combine_predictions_for_bb (basic_block bb
)
575 int best_probability
= PROB_EVEN
;
576 int best_predictor
= END_PREDICTORS
;
577 int combined_probability
= REG_BR_PROB_BASE
/ 2;
579 bool first_match
= false;
581 struct edge_prediction
*pred
;
583 edge e
, first
= NULL
, second
= NULL
;
587 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
588 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
591 if (first
&& !second
)
597 /* When there is no successor or only one choice, prediction is easy.
599 We are lazy for now and predict only basic blocks with two outgoing
600 edges. It is possible to predict generic case too, but we have to
601 ignore first match heuristics and do more involved combining. Implement
606 set_even_probabilities (bb
);
607 clear_bb_predictions (bb
);
609 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
615 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
617 preds
= pointer_map_contains (bb_predictions
, bb
);
620 /* We implement "first match" heuristics and use probability guessed
621 by predictor with smallest index. */
622 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
624 int predictor
= pred
->ep_predictor
;
625 int probability
= pred
->ep_probability
;
627 if (pred
->ep_edge
!= first
)
628 probability
= REG_BR_PROB_BASE
- probability
;
631 if (best_predictor
> predictor
)
632 best_probability
= probability
, best_predictor
= predictor
;
634 d
= (combined_probability
* probability
635 + (REG_BR_PROB_BASE
- combined_probability
)
636 * (REG_BR_PROB_BASE
- probability
));
638 /* Use FP math to avoid overflows of 32bit integers. */
640 /* If one probability is 0% and one 100%, avoid division by zero. */
641 combined_probability
= REG_BR_PROB_BASE
/ 2;
643 combined_probability
= (((double) combined_probability
)
645 * REG_BR_PROB_BASE
/ d
+ 0.5);
649 /* Decide which heuristic to use. In case we didn't match anything,
650 use no_prediction heuristic, in case we did match, use either
651 first match or Dempster-Shaffer theory depending on the flags. */
653 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
657 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
660 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
662 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
667 combined_probability
= best_probability
;
668 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
672 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
674 int predictor
= pred
->ep_predictor
;
675 int probability
= pred
->ep_probability
;
677 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
678 probability
= REG_BR_PROB_BASE
- probability
;
679 dump_prediction (dump_file
, predictor
, probability
, bb
,
680 !first_match
|| best_predictor
== predictor
);
683 clear_bb_predictions (bb
);
687 first
->probability
= combined_probability
;
688 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
692 /* Predict edge probabilities by exploiting loop structure. */
702 /* Try to predict out blocks in a loop that are not part of a
704 FOR_EACH_LOOP (li
, loop
, 0)
706 basic_block bb
, *bbs
;
708 VEC (edge
, heap
) *exits
;
709 struct tree_niter_desc niter_desc
;
712 exits
= get_loop_exit_edges (loop
);
713 n_exits
= VEC_length (edge
, exits
);
715 for (j
= 0; VEC_iterate (edge
, exits
, j
, ex
); j
++)
718 HOST_WIDE_INT nitercst
;
719 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
721 enum br_predictor predictor
;
723 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
724 niter
= niter_desc
.niter
;
725 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
726 niter
= loop_niter_by_eval (loop
, ex
);
728 if (TREE_CODE (niter
) == INTEGER_CST
)
730 if (host_integerp (niter
, 1)
731 && compare_tree_int (niter
, max
-1) == -1)
732 nitercst
= tree_low_cst (niter
, 1) + 1;
735 predictor
= PRED_LOOP_ITERATIONS
;
737 /* If we have just one exit and we can derive some information about
738 the number of iterations of the loop from the statements inside
739 the loop, use it to predict this exit. */
740 else if (n_exits
== 1)
742 nitercst
= estimated_loop_iterations_int (loop
, false);
748 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
753 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
754 predict_edge (ex
, predictor
, probability
);
756 VEC_free (edge
, heap
, exits
);
758 bbs
= get_loop_body (loop
);
760 for (j
= 0; j
< loop
->num_nodes
; j
++)
762 int header_found
= 0;
768 /* Bypass loop heuristics on continue statement. These
769 statements construct loops via "non-loop" constructs
770 in the source language and are better to be handled
772 if (predicted_by_p (bb
, PRED_CONTINUE
))
775 /* Loop branch heuristics - predict an edge back to a
776 loop's head as taken. */
777 if (bb
== loop
->latch
)
779 e
= find_edge (loop
->latch
, loop
->header
);
783 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
787 /* Loop exit heuristics - predict an edge exiting the loop if the
788 conditional has no loop header successors as not taken. */
790 /* If we already used more reliable loop exit predictors, do not
791 bother with PRED_LOOP_EXIT. */
792 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
793 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
795 /* For loop with many exits we don't want to predict all exits
796 with the pretty large probability, because if all exits are
797 considered in row, the loop would be predicted to iterate
798 almost never. The code to divide probability by number of
799 exits is very rough. It should compute the number of exits
800 taken in each patch through function (not the overall number
801 of exits that might be a lot higher for loops with wide switch
802 statements in them) and compute n-th square root.
804 We limit the minimal probability by 2% to avoid
805 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
806 as this was causing regression in perl benchmark containing such
809 int probability
= ((REG_BR_PROB_BASE
810 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
812 if (probability
< HITRATE (2))
813 probability
= HITRATE (2);
814 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
815 if (e
->dest
->index
< NUM_FIXED_BLOCKS
816 || !flow_bb_inside_loop_p (loop
, e
->dest
))
817 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
821 /* Free basic blocks from get_loop_body. */
828 /* Attempt to predict probabilities of BB outgoing edges using local
831 bb_estimate_probability_locally (basic_block bb
)
833 rtx last_insn
= BB_END (bb
);
836 if (! can_predict_insn_p (last_insn
))
838 cond
= get_condition (last_insn
, NULL
, false, false);
842 /* Try "pointer heuristic."
843 A comparison ptr == 0 is predicted as false.
844 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
845 if (COMPARISON_P (cond
)
846 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
847 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
849 if (GET_CODE (cond
) == EQ
)
850 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
851 else if (GET_CODE (cond
) == NE
)
852 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
856 /* Try "opcode heuristic."
857 EQ tests are usually false and NE tests are usually true. Also,
858 most quantities are positive, so we can make the appropriate guesses
859 about signed comparisons against zero. */
860 switch (GET_CODE (cond
))
863 /* Unconditional branch. */
864 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
865 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
870 /* Floating point comparisons appears to behave in a very
871 unpredictable way because of special role of = tests in
873 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
875 /* Comparisons with 0 are often used for booleans and there is
876 nothing useful to predict about them. */
877 else if (XEXP (cond
, 1) == const0_rtx
878 || XEXP (cond
, 0) == const0_rtx
)
881 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
886 /* Floating point comparisons appears to behave in a very
887 unpredictable way because of special role of = tests in
889 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
891 /* Comparisons with 0 are often used for booleans and there is
892 nothing useful to predict about them. */
893 else if (XEXP (cond
, 1) == const0_rtx
894 || XEXP (cond
, 0) == const0_rtx
)
897 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
901 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
905 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
910 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
911 || XEXP (cond
, 1) == constm1_rtx
)
912 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
917 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
918 || XEXP (cond
, 1) == constm1_rtx
)
919 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
927 /* Set edge->probability for each successor edge of BB. */
929 guess_outgoing_edge_probabilities (basic_block bb
)
931 bb_estimate_probability_locally (bb
);
932 combine_predictions_for_insn (BB_END (bb
), bb
);
935 /* Return constant EXPR will likely have at execution time, NULL if unknown.
936 The function is used by builtin_expect branch predictor so the evidence
937 must come from this construct and additional possible constant folding.
939 We may want to implement more involved value guess (such as value range
940 propagation based prediction), but such tricks shall go to new
944 expr_expected_value (tree expr
, bitmap visited
)
946 if (TREE_CONSTANT (expr
))
948 else if (TREE_CODE (expr
) == SSA_NAME
)
950 tree def
= SSA_NAME_DEF_STMT (expr
);
952 /* If we were already here, break the infinite cycle. */
953 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (expr
)))
955 bitmap_set_bit (visited
, SSA_NAME_VERSION (expr
));
957 if (TREE_CODE (def
) == PHI_NODE
)
959 /* All the arguments of the PHI node must have the same constant
962 tree val
= NULL
, new_val
;
964 for (i
= 0; i
< PHI_NUM_ARGS (def
); i
++)
966 tree arg
= PHI_ARG_DEF (def
, i
);
968 /* If this PHI has itself as an argument, we cannot
969 determine the string length of this argument. However,
970 if we can find an expected constant value for the other
971 PHI args then we can still be sure that this is
972 likely a constant. So be optimistic and just
973 continue with the next argument. */
974 if (arg
== PHI_RESULT (def
))
977 new_val
= expr_expected_value (arg
, visited
);
982 else if (!operand_equal_p (val
, new_val
, false))
987 if (TREE_CODE (def
) != GIMPLE_MODIFY_STMT
988 || GIMPLE_STMT_OPERAND (def
, 0) != expr
)
990 return expr_expected_value (GIMPLE_STMT_OPERAND (def
, 1), visited
);
992 else if (TREE_CODE (expr
) == CALL_EXPR
)
994 tree decl
= get_callee_fndecl (expr
);
997 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
998 && DECL_FUNCTION_CODE (decl
) == BUILT_IN_EXPECT
)
1002 if (call_expr_nargs (expr
) != 2)
1004 val
= CALL_EXPR_ARG (expr
, 0);
1005 if (TREE_CONSTANT (val
))
1007 return CALL_EXPR_ARG (expr
, 1);
1010 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
1013 op0
= expr_expected_value (TREE_OPERAND (expr
, 0), visited
);
1016 op1
= expr_expected_value (TREE_OPERAND (expr
, 1), visited
);
1019 res
= fold_build2 (TREE_CODE (expr
), TREE_TYPE (expr
), op0
, op1
);
1020 if (TREE_CONSTANT (res
))
1024 if (UNARY_CLASS_P (expr
))
1027 op0
= expr_expected_value (TREE_OPERAND (expr
, 0), visited
);
1030 res
= fold_build1 (TREE_CODE (expr
), TREE_TYPE (expr
), op0
);
1031 if (TREE_CONSTANT (res
))
1038 /* Get rid of all builtin_expect calls we no longer need. */
1040 strip_builtin_expect (void)
1045 block_stmt_iterator bi
;
1046 for (bi
= bsi_start (bb
); !bsi_end_p (bi
); bsi_next (&bi
))
1048 tree stmt
= bsi_stmt (bi
);
1052 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1053 && (call
= GIMPLE_STMT_OPERAND (stmt
, 1))
1054 && TREE_CODE (call
) == CALL_EXPR
1055 && (fndecl
= get_callee_fndecl (call
))
1056 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
1057 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
1058 && call_expr_nargs (call
) == 2)
1060 GIMPLE_STMT_OPERAND (stmt
, 1) = CALL_EXPR_ARG (call
, 0);
1067 /* Predict using opcode of the last statement in basic block. */
1069 tree_predict_by_opcode (basic_block bb
)
1071 tree stmt
= last_stmt (bb
);
1080 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
1082 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1083 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1085 cond
= TREE_OPERAND (stmt
, 0);
1086 if (!COMPARISON_CLASS_P (cond
))
1088 op0
= TREE_OPERAND (cond
, 0);
1089 type
= TREE_TYPE (op0
);
1090 visited
= BITMAP_ALLOC (NULL
);
1091 val
= expr_expected_value (cond
, visited
);
1092 BITMAP_FREE (visited
);
1095 if (integer_zerop (val
))
1096 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, NOT_TAKEN
);
1098 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, TAKEN
);
1101 /* Try "pointer heuristic."
1102 A comparison ptr == 0 is predicted as false.
1103 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1104 if (POINTER_TYPE_P (type
))
1106 if (TREE_CODE (cond
) == EQ_EXPR
)
1107 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1108 else if (TREE_CODE (cond
) == NE_EXPR
)
1109 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1113 /* Try "opcode heuristic."
1114 EQ tests are usually false and NE tests are usually true. Also,
1115 most quantities are positive, so we can make the appropriate guesses
1116 about signed comparisons against zero. */
1117 switch (TREE_CODE (cond
))
1121 /* Floating point comparisons appears to behave in a very
1122 unpredictable way because of special role of = tests in
1124 if (FLOAT_TYPE_P (type
))
1126 /* Comparisons with 0 are often used for booleans and there is
1127 nothing useful to predict about them. */
1128 else if (integer_zerop (op0
)
1129 || integer_zerop (TREE_OPERAND (cond
, 1)))
1132 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
1137 /* Floating point comparisons appears to behave in a very
1138 unpredictable way because of special role of = tests in
1140 if (FLOAT_TYPE_P (type
))
1142 /* Comparisons with 0 are often used for booleans and there is
1143 nothing useful to predict about them. */
1144 else if (integer_zerop (op0
)
1145 || integer_zerop (TREE_OPERAND (cond
, 1)))
1148 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
1152 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
1155 case UNORDERED_EXPR
:
1156 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
1161 if (integer_zerop (TREE_OPERAND (cond
, 1))
1162 || integer_onep (TREE_OPERAND (cond
, 1))
1163 || integer_all_onesp (TREE_OPERAND (cond
, 1))
1164 || real_zerop (TREE_OPERAND (cond
, 1))
1165 || real_onep (TREE_OPERAND (cond
, 1))
1166 || real_minus_onep (TREE_OPERAND (cond
, 1)))
1167 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
1172 if (integer_zerop (TREE_OPERAND (cond
, 1))
1173 || integer_onep (TREE_OPERAND (cond
, 1))
1174 || integer_all_onesp (TREE_OPERAND (cond
, 1))
1175 || real_zerop (TREE_OPERAND (cond
, 1))
1176 || real_onep (TREE_OPERAND (cond
, 1))
1177 || real_minus_onep (TREE_OPERAND (cond
, 1)))
1178 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
1186 /* Try to guess whether the value of return means error code. */
1187 static enum br_predictor
1188 return_prediction (tree val
, enum prediction
*prediction
)
1192 return PRED_NO_PREDICTION
;
1193 /* Different heuristics for pointers and scalars. */
1194 if (POINTER_TYPE_P (TREE_TYPE (val
)))
1196 /* NULL is usually not returned. */
1197 if (integer_zerop (val
))
1199 *prediction
= NOT_TAKEN
;
1200 return PRED_NULL_RETURN
;
1203 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
1205 /* Negative return values are often used to indicate
1207 if (TREE_CODE (val
) == INTEGER_CST
1208 && tree_int_cst_sgn (val
) < 0)
1210 *prediction
= NOT_TAKEN
;
1211 return PRED_NEGATIVE_RETURN
;
1213 /* Constant return values seems to be commonly taken.
1214 Zero/one often represent booleans so exclude them from the
1216 if (TREE_CONSTANT (val
)
1217 && (!integer_zerop (val
) && !integer_onep (val
)))
1219 *prediction
= TAKEN
;
1220 return PRED_CONST_RETURN
;
1223 return PRED_NO_PREDICTION
;
1226 /* Find the basic block with return expression and look up for possible
1227 return value trying to apply RETURN_PREDICTION heuristics. */
1229 apply_return_prediction (int *heads
)
1231 tree return_stmt
= NULL
;
1235 int phi_num_args
, i
;
1236 enum br_predictor pred
;
1237 enum prediction direction
;
1240 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1242 return_stmt
= last_stmt (e
->src
);
1244 && TREE_CODE (return_stmt
) == RETURN_EXPR
)
1249 return_val
= TREE_OPERAND (return_stmt
, 0);
1252 if (TREE_CODE (return_val
) == GIMPLE_MODIFY_STMT
)
1253 return_val
= GIMPLE_STMT_OPERAND (return_val
, 1);
1254 if (TREE_CODE (return_val
) != SSA_NAME
1255 || !SSA_NAME_DEF_STMT (return_val
)
1256 || TREE_CODE (SSA_NAME_DEF_STMT (return_val
)) != PHI_NODE
)
1258 for (phi
= SSA_NAME_DEF_STMT (return_val
); phi
; phi
= PHI_CHAIN (phi
))
1259 if (PHI_RESULT (phi
) == return_val
)
1263 phi_num_args
= PHI_NUM_ARGS (phi
);
1264 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
1266 /* Avoid the degenerate case where all return values form the function
1267 belongs to same category (ie they are all positive constants)
1268 so we can hardly say something about them. */
1269 for (i
= 1; i
< phi_num_args
; i
++)
1270 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
1272 if (i
!= phi_num_args
)
1273 for (i
= 0; i
< phi_num_args
; i
++)
1275 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
1276 if (pred
!= PRED_NO_PREDICTION
)
1277 predict_paths_leading_to (PHI_ARG_EDGE (phi
, i
)->src
, heads
, pred
,
1282 /* Look for basic block that contains unlikely to happen events
1283 (such as noreturn calls) and mark all paths leading to execution
1284 of this basic blocks as unlikely. */
1287 tree_bb_level_predictions (void)
1292 heads
= XCNEWVEC (int, last_basic_block
);
1293 heads
[ENTRY_BLOCK_PTR
->next_bb
->index
] = last_basic_block
;
1295 apply_return_prediction (heads
);
1299 block_stmt_iterator bsi
= bsi_last (bb
);
1301 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1303 tree stmt
= bsi_stmt (bsi
);
1305 switch (TREE_CODE (stmt
))
1307 case GIMPLE_MODIFY_STMT
:
1308 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == CALL_EXPR
)
1310 stmt
= GIMPLE_STMT_OPERAND (stmt
, 1);
1316 if (call_expr_flags (stmt
) & ECF_NORETURN
)
1317 predict_paths_leading_to (bb
, heads
, PRED_NORETURN
,
1319 decl
= get_callee_fndecl (stmt
);
1321 && lookup_attribute ("cold",
1322 DECL_ATTRIBUTES (decl
)))
1323 predict_paths_leading_to (bb
, heads
, PRED_COLD_FUNCTION
,
1335 #ifdef ENABLE_CHECKING
1337 /* Callback for pointer_map_traverse, asserts that the pointer map is
1341 assert_is_empty (void *key ATTRIBUTE_UNUSED
, void **value
,
1342 void *data ATTRIBUTE_UNUSED
)
1344 gcc_assert (!*value
);
1349 /* Predict branch probabilities and estimate profile of the tree CFG. */
1351 tree_estimate_probability (void)
1355 loop_optimizer_init (0);
1356 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1357 flow_loops_dump (dump_file
, NULL
, 0);
1359 add_noreturn_fake_exit_edges ();
1360 connect_infinite_loops_to_exit ();
1361 /* We use loop_niter_by_eval, which requires that the loops have
1363 create_preheaders (CP_SIMPLE_PREHEADERS
);
1364 calculate_dominance_info (CDI_POST_DOMINATORS
);
1366 bb_predictions
= pointer_map_create ();
1367 tree_bb_level_predictions ();
1369 mark_irreducible_loops ();
1370 record_loop_exits ();
1371 if (number_of_loops () > 1)
1379 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1381 /* Predict early returns to be probable, as we've already taken
1382 care for error returns and other cases are often used for
1383 fast paths through function.
1385 Since we've already removed the return statements, we are
1386 looking for CFG like:
1396 if (e
->dest
!= bb
->next_bb
1397 && e
->dest
!= EXIT_BLOCK_PTR
1398 && single_succ_p (e
->dest
)
1399 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR
1400 && TREE_CODE (last_stmt (e
->dest
)) == RETURN_EXPR
)
1405 if (single_succ_p (bb
))
1407 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
1408 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
1409 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
1410 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
1411 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1414 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
1415 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
1416 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
1417 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1420 /* Look for block we are guarding (ie we dominate it,
1421 but it doesn't postdominate us). */
1422 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
1423 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
1424 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
1426 block_stmt_iterator bi
;
1428 /* The call heuristic claims that a guarded function call
1429 is improbable. This is because such calls are often used
1430 to signal exceptional situations such as printing error
1432 for (bi
= bsi_start (e
->dest
); !bsi_end_p (bi
);
1435 tree stmt
= bsi_stmt (bi
);
1436 if ((TREE_CODE (stmt
) == CALL_EXPR
1437 || (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1438 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1))
1440 /* Constant and pure calls are hardly used to signalize
1441 something exceptional. */
1442 && TREE_SIDE_EFFECTS (stmt
))
1444 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
1450 tree_predict_by_opcode (bb
);
1453 combine_predictions_for_bb (bb
);
1455 #ifdef ENABLE_CHECKING
1456 pointer_map_traverse (bb_predictions
, assert_is_empty
, NULL
);
1458 pointer_map_destroy (bb_predictions
);
1459 bb_predictions
= NULL
;
1461 strip_builtin_expect ();
1462 estimate_bb_frequencies ();
1463 free_dominance_info (CDI_POST_DOMINATORS
);
1464 remove_fake_exit_edges ();
1465 loop_optimizer_finalize ();
1466 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1467 dump_tree_cfg (dump_file
, dump_flags
);
1468 if (profile_status
== PROFILE_ABSENT
)
1469 profile_status
= PROFILE_GUESSED
;
1473 /* Sets branch probabilities according to PREDiction and
1474 FLAGS. HEADS[bb->index] should be index of basic block in that we
1475 need to alter branch predictions (i.e. the first of our dominators
1476 such that we do not post-dominate it) (but we fill this information
1477 on demand, so -1 may be there in case this was not needed yet). */
1480 predict_paths_leading_to (basic_block bb
, int *heads
, enum br_predictor pred
,
1481 enum prediction taken
)
1487 if (heads
[bb
->index
] == ENTRY_BLOCK
)
1489 /* This is first time we need this field in heads array; so
1490 find first dominator that we do not post-dominate (we are
1491 using already known members of heads array). */
1492 basic_block ai
= bb
;
1493 basic_block next_ai
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1496 while (heads
[next_ai
->index
] == ENTRY_BLOCK
)
1498 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
1500 heads
[next_ai
->index
] = ai
->index
;
1502 next_ai
= get_immediate_dominator (CDI_DOMINATORS
, next_ai
);
1504 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
1505 head
= next_ai
->index
;
1507 head
= heads
[next_ai
->index
];
1508 while (next_ai
!= bb
)
1511 ai
= BASIC_BLOCK (heads
[ai
->index
]);
1512 heads
[next_ai
->index
] = head
;
1515 y
= heads
[bb
->index
];
1517 /* Now find the edge that leads to our branch and aply the prediction. */
1519 if (y
== last_basic_block
)
1521 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (y
)->succs
)
1522 if (e
->dest
->index
>= NUM_FIXED_BLOCKS
1523 && dominated_by_p (CDI_POST_DOMINATORS
, e
->dest
, bb
))
1524 predict_edge_def (e
, pred
, taken
);
1527 /* This is used to carry information about basic blocks. It is
1528 attached to the AUX field of the standard CFG block. */
1530 typedef struct block_info_def
1532 /* Estimated frequency of execution of basic_block. */
1535 /* To keep queue of basic blocks to process. */
1538 /* Number of predecessors we need to visit first. */
1542 /* Similar information for edges. */
1543 typedef struct edge_info_def
1545 /* In case edge is a loopback edge, the probability edge will be reached
1546 in case header is. Estimated number of iterations of the loop can be
1547 then computed as 1 / (1 - back_edge_prob). */
1548 sreal back_edge_prob
;
1549 /* True if the edge is a loopback edge in the natural loop. */
1550 unsigned int back_edge
:1;
1553 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1554 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1556 /* Helper function for estimate_bb_frequencies.
1557 Propagate the frequencies in blocks marked in
1558 TOVISIT, starting in HEAD. */
1561 propagate_freq (basic_block head
, bitmap tovisit
)
1570 /* For each basic block we need to visit count number of his predecessors
1571 we need to visit first. */
1572 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
1577 /* The outermost "loop" includes the exit block, which we can not
1578 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1579 directly. Do the same for the entry block. */
1580 bb
= BASIC_BLOCK (i
);
1582 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1584 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
1586 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
1588 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
1590 "Irreducible region hit, ignoring edge to %i->%i\n",
1591 e
->src
->index
, bb
->index
);
1593 BLOCK_INFO (bb
)->npredecessors
= count
;
1596 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
1598 for (bb
= head
; bb
; bb
= nextbb
)
1601 sreal cyclic_probability
, frequency
;
1603 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
1604 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
1606 nextbb
= BLOCK_INFO (bb
)->next
;
1607 BLOCK_INFO (bb
)->next
= NULL
;
1609 /* Compute frequency of basic block. */
1612 #ifdef ENABLE_CHECKING
1613 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1614 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
1615 || (e
->flags
& EDGE_DFS_BACK
));
1618 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1619 if (EDGE_INFO (e
)->back_edge
)
1621 sreal_add (&cyclic_probability
, &cyclic_probability
,
1622 &EDGE_INFO (e
)->back_edge_prob
);
1624 else if (!(e
->flags
& EDGE_DFS_BACK
))
1628 /* frequency += (e->probability
1629 * BLOCK_INFO (e->src)->frequency /
1630 REG_BR_PROB_BASE); */
1632 sreal_init (&tmp
, e
->probability
, 0);
1633 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
1634 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
1635 sreal_add (&frequency
, &frequency
, &tmp
);
1638 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
1640 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
1641 sizeof (frequency
));
1645 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
1647 memcpy (&cyclic_probability
, &real_almost_one
,
1648 sizeof (real_almost_one
));
1651 /* BLOCK_INFO (bb)->frequency = frequency
1652 / (1 - cyclic_probability) */
1654 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
1655 sreal_div (&BLOCK_INFO (bb
)->frequency
,
1656 &frequency
, &cyclic_probability
);
1660 bitmap_clear_bit (tovisit
, bb
->index
);
1662 e
= find_edge (bb
, head
);
1667 /* EDGE_INFO (e)->back_edge_prob
1668 = ((e->probability * BLOCK_INFO (bb)->frequency)
1669 / REG_BR_PROB_BASE); */
1671 sreal_init (&tmp
, e
->probability
, 0);
1672 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
1673 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1674 &tmp
, &real_inv_br_prob_base
);
1677 /* Propagate to successor blocks. */
1678 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1679 if (!(e
->flags
& EDGE_DFS_BACK
)
1680 && BLOCK_INFO (e
->dest
)->npredecessors
)
1682 BLOCK_INFO (e
->dest
)->npredecessors
--;
1683 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
1688 BLOCK_INFO (last
)->next
= e
->dest
;
1696 /* Estimate probabilities of loopback edges in loops at same nest level. */
1699 estimate_loops_at_level (struct loop
*first_loop
)
1703 for (loop
= first_loop
; loop
; loop
= loop
->next
)
1708 bitmap tovisit
= BITMAP_ALLOC (NULL
);
1710 estimate_loops_at_level (loop
->inner
);
1712 /* Find current loop back edge and mark it. */
1713 e
= loop_latch_edge (loop
);
1714 EDGE_INFO (e
)->back_edge
= 1;
1716 bbs
= get_loop_body (loop
);
1717 for (i
= 0; i
< loop
->num_nodes
; i
++)
1718 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
1720 propagate_freq (loop
->header
, tovisit
);
1721 BITMAP_FREE (tovisit
);
1725 /* Propagates frequencies through structure of loops. */
1728 estimate_loops (void)
1730 bitmap tovisit
= BITMAP_ALLOC (NULL
);
1733 /* Start by estimating the frequencies in the loops. */
1734 if (number_of_loops () > 1)
1735 estimate_loops_at_level (current_loops
->tree_root
->inner
);
1737 /* Now propagate the frequencies through all the blocks. */
1740 bitmap_set_bit (tovisit
, bb
->index
);
1742 propagate_freq (ENTRY_BLOCK_PTR
, tovisit
);
1743 BITMAP_FREE (tovisit
);
1746 /* Convert counts measured by profile driven feedback to frequencies.
1747 Return nonzero iff there was any nonzero execution count. */
1750 counts_to_freqs (void)
1752 gcov_type count_max
, true_count_max
= 0;
1756 true_count_max
= MAX (bb
->count
, true_count_max
);
1758 count_max
= MAX (true_count_max
, 1);
1759 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1760 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
1762 return true_count_max
;
1765 /* Return true if function is likely to be expensive, so there is no point to
1766 optimize performance of prologue, epilogue or do inlining at the expense
1767 of code size growth. THRESHOLD is the limit of number of instructions
1768 function can execute at average to be still considered not expensive. */
1771 expensive_function_p (int threshold
)
1773 unsigned int sum
= 0;
1777 /* We can not compute accurately for large thresholds due to scaled
1779 gcc_assert (threshold
<= BB_FREQ_MAX
);
1781 /* Frequencies are out of range. This either means that function contains
1782 internal loop executing more than BB_FREQ_MAX times or profile feedback
1783 is available and function has not been executed at all. */
1784 if (ENTRY_BLOCK_PTR
->frequency
== 0)
1787 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1788 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
1793 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
1794 insn
= NEXT_INSN (insn
))
1795 if (active_insn_p (insn
))
1797 sum
+= bb
->frequency
;
1806 /* Estimate basic blocks frequency by given branch probabilities. */
1809 estimate_bb_frequencies (void)
1814 if (!flag_branch_probabilities
|| !counts_to_freqs ())
1816 static int real_values_initialized
= 0;
1818 if (!real_values_initialized
)
1820 real_values_initialized
= 1;
1821 sreal_init (&real_zero
, 0, 0);
1822 sreal_init (&real_one
, 1, 0);
1823 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
1824 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
1825 sreal_init (&real_one_half
, 1, -1);
1826 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
1827 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
1830 mark_dfs_back_edges ();
1832 single_succ_edge (ENTRY_BLOCK_PTR
)->probability
= REG_BR_PROB_BASE
;
1834 /* Set up block info for each basic block. */
1835 alloc_aux_for_blocks (sizeof (struct block_info_def
));
1836 alloc_aux_for_edges (sizeof (struct edge_info_def
));
1837 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1842 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1844 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
1845 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1846 &EDGE_INFO (e
)->back_edge_prob
,
1847 &real_inv_br_prob_base
);
1851 /* First compute probabilities locally for each loop from innermost
1852 to outermost to examine probabilities for back edges. */
1855 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
1857 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
1858 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
1860 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
1861 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1865 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
1866 sreal_add (&tmp
, &tmp
, &real_one_half
);
1867 bb
->frequency
= sreal_to_int (&tmp
);
1870 free_aux_for_blocks ();
1871 free_aux_for_edges ();
1873 compute_function_frequency ();
1874 if (flag_reorder_functions
)
1875 choose_function_section ();
1878 /* Decide whether function is hot, cold or unlikely executed. */
1880 compute_function_frequency (void)
1884 if (!profile_info
|| !flag_branch_probabilities
)
1886 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
1888 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
1889 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
1891 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
1894 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
1897 if (maybe_hot_bb_p (bb
))
1899 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
1902 if (!probably_never_executed_bb_p (bb
))
1903 cfun
->function_frequency
= FUNCTION_FREQUENCY_NORMAL
;
1907 /* Choose appropriate section for the function. */
1909 choose_function_section (void)
1911 if (DECL_SECTION_NAME (current_function_decl
)
1912 || !targetm
.have_named_sections
1913 /* Theoretically we can split the gnu.linkonce text section too,
1914 but this requires more work as the frequency needs to match
1915 for all generated objects so we need to merge the frequency
1916 of all instances. For now just never set frequency for these. */
1917 || DECL_ONE_ONLY (current_function_decl
))
1920 /* If we are doing the partitioning optimization, let the optimization
1921 choose the correct section into which to put things. */
1923 if (flag_reorder_blocks_and_partition
)
1926 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
1927 DECL_SECTION_NAME (current_function_decl
) =
1928 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
1929 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
1930 DECL_SECTION_NAME (current_function_decl
) =
1931 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
1932 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);
1936 gate_estimate_probability (void)
1938 return flag_guess_branch_prob
;
1941 struct tree_opt_pass pass_profile
=
1943 "profile", /* name */
1944 gate_estimate_probability
, /* gate */
1945 tree_estimate_probability
, /* execute */
1948 0, /* static_pass_number */
1949 TV_BRANCH_PROB
, /* tv_id */
1950 PROP_cfg
, /* properties_required */
1951 0, /* properties_provided */
1952 0, /* properties_destroyed */
1953 0, /* todo_flags_start */
1954 TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */