1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 [1] "Branch Prediction for Free"
24 Ball and Larus; PLDI '93.
25 [2] "Static Branch Frequency and Program Profile Analysis"
26 Wu and Larus; MICRO-27.
27 [3] "Corpus-based Static Branch Prediction"
28 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
33 #include "coretypes.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
55 #include "tree-flow.h"
57 #include "tree-dump.h"
58 #include "tree-pass.h"
60 #include "tree-scalar-evolution.h"
63 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
64 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
65 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
66 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
68 /* Random guesstimation given names. */
69 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
70 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
71 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
72 #define PROB_ALWAYS (REG_BR_PROB_BASE)
74 static void combine_predictions_for_insn (rtx
, basic_block
);
75 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
76 static void estimate_loops_at_level (struct loop
*loop
);
77 static void propagate_freq (struct loop
*);
78 static void estimate_bb_frequencies (struct loops
*);
79 static int counts_to_freqs (void);
80 static bool last_basic_block_p (basic_block
);
81 static void compute_function_frequency (void);
82 static void choose_function_section (void);
83 static bool can_predict_insn_p (rtx
);
85 /* Information we hold about each branch predictor.
86 Filled using information from predict.def. */
90 const char *const name
; /* Name used in the debugging dumps. */
91 const int hitrate
; /* Expected hitrate used by
92 predict_insn_def call. */
96 /* Use given predictor without Dempster-Shaffer theory if it matches
97 using first_match heuristics. */
98 #define PRED_FLAG_FIRST_MATCH 1
100 /* Recompute hitrate in percent to our representation. */
102 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
104 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
105 static const struct predictor_info predictor_info
[]= {
106 #include "predict.def"
108 /* Upper bound on predictors. */
113 /* Return true in case BB can be CPU intensive and should be optimized
114 for maximal performance. */
117 maybe_hot_bb_p (basic_block bb
)
119 if (profile_info
&& flag_branch_probabilities
121 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
123 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
128 /* Return true in case BB is cold and should be optimized for size. */
131 probably_cold_bb_p (basic_block bb
)
133 if (profile_info
&& flag_branch_probabilities
135 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
137 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
142 /* Return true in case BB is probably never executed. */
144 probably_never_executed_bb_p (basic_block bb
)
146 if (profile_info
&& flag_branch_probabilities
)
147 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
151 /* Return true if the one of outgoing edges is already predicted by
155 rtl_predicted_by_p (basic_block bb
, enum br_predictor predictor
)
158 if (!INSN_P (BB_END (bb
)))
160 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
161 if (REG_NOTE_KIND (note
) == REG_BR_PRED
162 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
167 /* Return true if the one of outgoing edges is already predicted by
171 tree_predicted_by_p (basic_block bb
, enum br_predictor predictor
)
173 struct edge_prediction
*i
= bb_ann (bb
)->predictions
;
174 for (i
= bb_ann (bb
)->predictions
; i
; i
= i
->next
)
175 if (i
->predictor
== predictor
)
181 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
183 if (!any_condjump_p (insn
))
185 if (!flag_guess_branch_prob
)
189 = gen_rtx_EXPR_LIST (REG_BR_PRED
,
190 gen_rtx_CONCAT (VOIDmode
,
191 GEN_INT ((int) predictor
),
192 GEN_INT ((int) probability
)),
196 /* Predict insn by given predictor. */
199 predict_insn_def (rtx insn
, enum br_predictor predictor
,
200 enum prediction taken
)
202 int probability
= predictor_info
[(int) predictor
].hitrate
;
205 probability
= REG_BR_PROB_BASE
- probability
;
207 predict_insn (insn
, predictor
, probability
);
210 /* Predict edge E with given probability if possible. */
213 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
216 last_insn
= BB_END (e
->src
);
218 /* We can store the branch prediction information only about
219 conditional jumps. */
220 if (!any_condjump_p (last_insn
))
223 /* We always store probability of branching. */
224 if (e
->flags
& EDGE_FALLTHRU
)
225 probability
= REG_BR_PROB_BASE
- probability
;
227 predict_insn (last_insn
, predictor
, probability
);
230 /* Predict edge E with the given PROBABILITY. */
232 tree_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
234 struct edge_prediction
*i
= ggc_alloc (sizeof (struct edge_prediction
));
236 i
->next
= bb_ann (e
->src
)->predictions
;
237 bb_ann (e
->src
)->predictions
= i
;
238 i
->probability
= probability
;
239 i
->predictor
= predictor
;
243 /* Return true when we can store prediction on insn INSN.
244 At the moment we represent predictions only on conditional
245 jumps, not at computed jump or other complicated cases. */
247 can_predict_insn_p (rtx insn
)
249 return (JUMP_P (insn
)
250 && any_condjump_p (insn
)
251 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
254 /* Predict edge E by given predictor if possible. */
257 predict_edge_def (edge e
, enum br_predictor predictor
,
258 enum prediction taken
)
260 int probability
= predictor_info
[(int) predictor
].hitrate
;
263 probability
= REG_BR_PROB_BASE
- probability
;
265 predict_edge (e
, predictor
, probability
);
268 /* Invert all branch predictions or probability notes in the INSN. This needs
269 to be done each time we invert the condition used by the jump. */
272 invert_br_probabilities (rtx insn
)
276 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
277 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
278 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
279 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
280 XEXP (XEXP (note
, 0), 1)
281 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
284 /* Dump information about the branch prediction to the output file. */
287 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
288 basic_block bb
, int used
)
296 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
298 if (! (e
->flags
& EDGE_FALLTHRU
))
302 fprintf (file
, " %s heuristics%s: %.1f%%",
303 predictor_info
[predictor
].name
,
304 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
308 fprintf (file
, " exec ");
309 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
312 fprintf (file
, " hit ");
313 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
314 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
318 fprintf (file
, "\n");
321 /* We can not predict the probabilities of outgoing edges of bb. Set them
322 evenly and hope for the best. */
324 set_even_probabilities (basic_block bb
)
330 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
332 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
336 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
338 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
339 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
345 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
346 note if not already present. Remove now useless REG_BR_PRED notes. */
349 combine_predictions_for_insn (rtx insn
, basic_block bb
)
354 int best_probability
= PROB_EVEN
;
355 int best_predictor
= END_PREDICTORS
;
356 int combined_probability
= REG_BR_PROB_BASE
/ 2;
358 bool first_match
= false;
361 if (!can_predict_insn_p (insn
))
363 set_even_probabilities (bb
);
367 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
368 pnote
= ®_NOTES (insn
);
370 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
373 /* We implement "first match" heuristics and use probability guessed
374 by predictor with smallest index. */
375 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
376 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
378 int predictor
= INTVAL (XEXP (XEXP (note
, 0), 0));
379 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
382 if (best_predictor
> predictor
)
383 best_probability
= probability
, best_predictor
= predictor
;
385 d
= (combined_probability
* probability
386 + (REG_BR_PROB_BASE
- combined_probability
)
387 * (REG_BR_PROB_BASE
- probability
));
389 /* Use FP math to avoid overflows of 32bit integers. */
391 /* If one probability is 0% and one 100%, avoid division by zero. */
392 combined_probability
= REG_BR_PROB_BASE
/ 2;
394 combined_probability
= (((double) combined_probability
) * probability
395 * REG_BR_PROB_BASE
/ d
+ 0.5);
398 /* Decide which heuristic to use. In case we didn't match anything,
399 use no_prediction heuristic, in case we did match, use either
400 first match or Dempster-Shaffer theory depending on the flags. */
402 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
406 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
407 combined_probability
, bb
, true);
410 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
412 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
417 combined_probability
= best_probability
;
418 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
422 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
424 int predictor
= INTVAL (XEXP (XEXP (*pnote
, 0), 0));
425 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
427 dump_prediction (dump_file
, predictor
, probability
, bb
,
428 !first_match
|| best_predictor
== predictor
);
429 *pnote
= XEXP (*pnote
, 1);
432 pnote
= &XEXP (*pnote
, 1);
438 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
439 GEN_INT (combined_probability
), REG_NOTES (insn
));
441 /* Save the prediction into CFG in case we are seeing non-degenerated
443 if (EDGE_COUNT (bb
->succs
) > 1)
445 BRANCH_EDGE (bb
)->probability
= combined_probability
;
446 FALLTHRU_EDGE (bb
)->probability
447 = REG_BR_PROB_BASE
- combined_probability
;
452 /* Combine predictions into single probability and store them into CFG.
453 Remove now useless prediction entries. */
456 combine_predictions_for_bb (FILE *file
, basic_block bb
)
458 int best_probability
= PROB_EVEN
;
459 int best_predictor
= END_PREDICTORS
;
460 int combined_probability
= REG_BR_PROB_BASE
/ 2;
462 bool first_match
= false;
464 struct edge_prediction
*pred
;
466 edge e
, first
= NULL
, second
= NULL
;
469 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
471 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
474 if (first
&& !second
)
481 /* When there is no successor or only one choice, prediction is easy.
483 We are lazy for now and predict only basic blocks with two outgoing
484 edges. It is possible to predict generic case too, but we have to
485 ignore first match heuristics and do more involved combining. Implement
490 set_even_probabilities (bb
);
491 bb_ann (bb
)->predictions
= NULL
;
493 fprintf (file
, "%i edges in bb %i predicted to even probabilities\n",
499 fprintf (file
, "Predictions for bb %i\n", bb
->index
);
501 /* We implement "first match" heuristics and use probability guessed
502 by predictor with smallest index. */
503 for (pred
= bb_ann (bb
)->predictions
; pred
; pred
= pred
->next
)
505 int predictor
= pred
->predictor
;
506 int probability
= pred
->probability
;
508 if (pred
->edge
!= first
)
509 probability
= REG_BR_PROB_BASE
- probability
;
512 if (best_predictor
> predictor
)
513 best_probability
= probability
, best_predictor
= predictor
;
515 d
= (combined_probability
* probability
516 + (REG_BR_PROB_BASE
- combined_probability
)
517 * (REG_BR_PROB_BASE
- probability
));
519 /* Use FP math to avoid overflows of 32bit integers. */
521 /* If one probability is 0% and one 100%, avoid division by zero. */
522 combined_probability
= REG_BR_PROB_BASE
/ 2;
524 combined_probability
= (((double) combined_probability
) * probability
525 * REG_BR_PROB_BASE
/ d
+ 0.5);
528 /* Decide which heuristic to use. In case we didn't match anything,
529 use no_prediction heuristic, in case we did match, use either
530 first match or Dempster-Shaffer theory depending on the flags. */
532 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
536 dump_prediction (file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
539 dump_prediction (file
, PRED_DS_THEORY
, combined_probability
, bb
,
541 dump_prediction (file
, PRED_FIRST_MATCH
, best_probability
, bb
,
546 combined_probability
= best_probability
;
547 dump_prediction (file
, PRED_COMBINED
, combined_probability
, bb
, true);
549 for (pred
= bb_ann (bb
)->predictions
; pred
; pred
= pred
->next
)
551 int predictor
= pred
->predictor
;
552 int probability
= pred
->probability
;
554 if (pred
->edge
!= EDGE_SUCC (bb
, 0))
555 probability
= REG_BR_PROB_BASE
- probability
;
556 dump_prediction (file
, predictor
, probability
, bb
,
557 !first_match
|| best_predictor
== predictor
);
559 bb_ann (bb
)->predictions
= NULL
;
563 first
->probability
= combined_probability
;
564 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
568 /* Predict edge probabilities by exploiting loop structure.
569 When RTLSIMPLELOOPS is set, attempt to count number of iterations by analyzing
570 RTL otherwise use tree based approach. */
572 predict_loops (struct loops
*loops_info
, bool rtlsimpleloops
)
577 scev_initialize (loops_info
);
579 /* Try to predict out blocks in a loop that are not part of a
581 for (i
= 1; i
< loops_info
->num
; i
++)
583 basic_block bb
, *bbs
;
586 struct loop
*loop
= loops_info
->parray
[i
];
587 struct niter_desc desc
;
588 unsigned HOST_WIDE_INT niter
;
590 flow_loop_scan (loop
, LOOP_EXIT_EDGES
);
591 exits
= loop
->num_exits
;
595 iv_analysis_loop_init (loop
);
596 find_simple_exit (loop
, &desc
);
598 if (desc
.simple_p
&& desc
.const_iter
)
601 niter
= desc
.niter
+ 1;
602 if (niter
== 0) /* We might overflow here. */
605 prob
= (REG_BR_PROB_BASE
606 - (REG_BR_PROB_BASE
+ niter
/2) / niter
);
607 /* Branch prediction algorithm gives 0 frequency for everything
608 after the end of loop for loop having 0 probability to finish. */
609 if (prob
== REG_BR_PROB_BASE
)
610 prob
= REG_BR_PROB_BASE
- 1;
611 predict_edge (desc
.in_edge
, PRED_LOOP_ITERATIONS
,
619 struct tree_niter_desc niter_desc
;
621 exits
= get_loop_exit_edges (loop
, &n_exits
);
622 for (j
= 0; j
< n_exits
; j
++)
626 if (number_of_iterations_exit (loop
, exits
[j
], &niter_desc
))
627 niter
= niter_desc
.niter
;
628 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
629 niter
= loop_niter_by_eval (loop
, exits
[j
]);
631 if (TREE_CODE (niter
) == INTEGER_CST
)
634 if (host_integerp (niter
, 1)
635 && tree_int_cst_lt (niter
,
636 build_int_cstu (NULL_TREE
,
637 REG_BR_PROB_BASE
- 1)))
639 HOST_WIDE_INT nitercst
= tree_low_cst (niter
, 1) + 1;
640 probability
= (REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
;
645 predict_edge (exits
[j
], PRED_LOOP_ITERATIONS
, probability
);
652 bbs
= get_loop_body (loop
);
654 for (j
= 0; j
< loop
->num_nodes
; j
++)
656 int header_found
= 0;
662 /* Bypass loop heuristics on continue statement. These
663 statements construct loops via "non-loop" constructs
664 in the source language and are better to be handled
666 if ((rtlsimpleloops
&& !can_predict_insn_p (BB_END (bb
)))
667 || predicted_by_p (bb
, PRED_CONTINUE
))
670 /* Loop branch heuristics - predict an edge back to a
671 loop's head as taken. */
672 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
674 if (e
->dest
== loop
->header
675 && e
->src
== loop
->latch
)
678 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
682 /* Loop exit heuristics - predict an edge exiting the loop if the
683 conditional has no loop header successors as not taken. */
685 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
687 if (e
->dest
->index
< 0
688 || !flow_bb_inside_loop_p (loop
, e
->dest
))
692 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
697 /* Free basic blocks from get_loop_body. */
705 /* Attempt to predict probabilities of BB outgoing edges using local
708 bb_estimate_probability_locally (basic_block bb
)
710 rtx last_insn
= BB_END (bb
);
713 if (! can_predict_insn_p (last_insn
))
715 cond
= get_condition (last_insn
, NULL
, false, false);
719 /* Try "pointer heuristic."
720 A comparison ptr == 0 is predicted as false.
721 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
722 if (COMPARISON_P (cond
)
723 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
724 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
726 if (GET_CODE (cond
) == EQ
)
727 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
728 else if (GET_CODE (cond
) == NE
)
729 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
733 /* Try "opcode heuristic."
734 EQ tests are usually false and NE tests are usually true. Also,
735 most quantities are positive, so we can make the appropriate guesses
736 about signed comparisons against zero. */
737 switch (GET_CODE (cond
))
740 /* Unconditional branch. */
741 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
742 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
747 /* Floating point comparisons appears to behave in a very
748 unpredictable way because of special role of = tests in
750 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
752 /* Comparisons with 0 are often used for booleans and there is
753 nothing useful to predict about them. */
754 else if (XEXP (cond
, 1) == const0_rtx
755 || XEXP (cond
, 0) == const0_rtx
)
758 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
763 /* Floating point comparisons appears to behave in a very
764 unpredictable way because of special role of = tests in
766 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
768 /* Comparisons with 0 are often used for booleans and there is
769 nothing useful to predict about them. */
770 else if (XEXP (cond
, 1) == const0_rtx
771 || XEXP (cond
, 0) == const0_rtx
)
774 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
778 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
782 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
787 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
788 || XEXP (cond
, 1) == constm1_rtx
)
789 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
794 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
795 || XEXP (cond
, 1) == constm1_rtx
)
796 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
804 /* Statically estimate the probability that a branch will be taken and produce
805 estimated profile. When profile feedback is present never executed portions
806 of function gets estimated. */
809 estimate_probability (struct loops
*loops_info
)
813 connect_infinite_loops_to_exit ();
814 calculate_dominance_info (CDI_DOMINATORS
);
815 calculate_dominance_info (CDI_POST_DOMINATORS
);
817 predict_loops (loops_info
, true);
821 /* Attempt to predict conditional jumps using a number of heuristics. */
824 rtx last_insn
= BB_END (bb
);
828 if (! can_predict_insn_p (last_insn
))
831 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
833 /* Predict early returns to be probable, as we've already taken
834 care for error returns and other are often used for fast paths
836 if ((e
->dest
== EXIT_BLOCK_PTR
837 || (EDGE_COUNT (e
->dest
->succs
) == 1
838 && EDGE_SUCC (e
->dest
, 0)->dest
== EXIT_BLOCK_PTR
))
839 && !predicted_by_p (bb
, PRED_NULL_RETURN
)
840 && !predicted_by_p (bb
, PRED_CONST_RETURN
)
841 && !predicted_by_p (bb
, PRED_NEGATIVE_RETURN
)
842 && !last_basic_block_p (e
->dest
))
843 predict_edge_def (e
, PRED_EARLY_RETURN
, TAKEN
);
845 /* Look for block we are guarding (ie we dominate it,
846 but it doesn't postdominate us). */
847 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
848 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
849 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
853 /* The call heuristic claims that a guarded function call
854 is improbable. This is because such calls are often used
855 to signal exceptional situations such as printing error
857 for (insn
= BB_HEAD (e
->dest
); insn
!= NEXT_INSN (BB_END (e
->dest
));
858 insn
= NEXT_INSN (insn
))
860 /* Constant and pure calls are hardly used to signalize
861 something exceptional. */
862 && ! CONST_OR_PURE_CALL_P (insn
))
864 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
869 bb_estimate_probability_locally (bb
);
872 /* Attach the combined probability to each conditional jump. */
874 if (JUMP_P (BB_END (bb
))
875 && any_condjump_p (BB_END (bb
))
876 && EDGE_COUNT (bb
->succs
) >= 2)
877 combine_predictions_for_insn (BB_END (bb
), bb
);
879 remove_fake_exit_edges ();
880 /* Fill in the probability values in flowgraph based on the REG_BR_PROB
885 rtx last_insn
= BB_END (bb
);
887 if (!can_predict_insn_p (last_insn
))
889 /* We can predict only conditional jumps at the moment.
890 Expect each edge to be equally probable.
891 ?? In the future we want to make abnormal edges improbable. */
895 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
898 if (e
->probability
!= 0)
902 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
904 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
908 estimate_bb_frequencies (loops_info
);
909 free_dominance_info (CDI_POST_DOMINATORS
);
910 if (profile_status
== PROFILE_ABSENT
)
911 profile_status
= PROFILE_GUESSED
;
914 /* Set edge->probability for each successor edge of BB. */
916 guess_outgoing_edge_probabilities (basic_block bb
)
918 bb_estimate_probability_locally (bb
);
919 combine_predictions_for_insn (BB_END (bb
), bb
);
922 /* Return constant EXPR will likely have at execution time, NULL if unknown.
923 The function is used by builtin_expect branch predictor so the evidence
924 must come from this construct and additional possible constant folding.
926 We may want to implement more involved value guess (such as value range
927 propagation based prediction), but such tricks shall go to new
931 expr_expected_value (tree expr
, bitmap visited
)
933 if (TREE_CONSTANT (expr
))
935 else if (TREE_CODE (expr
) == SSA_NAME
)
937 tree def
= SSA_NAME_DEF_STMT (expr
);
939 /* If we were already here, break the infinite cycle. */
940 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (expr
)))
942 bitmap_set_bit (visited
, SSA_NAME_VERSION (expr
));
944 if (TREE_CODE (def
) == PHI_NODE
)
946 /* All the arguments of the PHI node must have the same constant
949 tree val
= NULL
, new_val
;
951 for (i
= 0; i
< PHI_NUM_ARGS (def
); i
++)
953 tree arg
= PHI_ARG_DEF (def
, i
);
955 /* If this PHI has itself as an argument, we cannot
956 determine the string length of this argument. However,
957 if we can find a expected constant value for the other
958 PHI args then we can still be sure that this is
959 likely a constant. So be optimistic and just
960 continue with the next argument. */
961 if (arg
== PHI_RESULT (def
))
964 new_val
= expr_expected_value (arg
, visited
);
969 else if (!operand_equal_p (val
, new_val
, false))
974 if (TREE_CODE (def
) != MODIFY_EXPR
|| TREE_OPERAND (def
, 0) != expr
)
976 return expr_expected_value (TREE_OPERAND (def
, 1), visited
);
978 else if (TREE_CODE (expr
) == CALL_EXPR
)
980 tree decl
= get_callee_fndecl (expr
);
983 if (DECL_BUILT_IN (decl
) && DECL_FUNCTION_CODE (decl
) == BUILT_IN_EXPECT
)
985 tree arglist
= TREE_OPERAND (expr
, 1);
988 if (arglist
== NULL_TREE
989 || TREE_CHAIN (arglist
) == NULL_TREE
)
991 val
= TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr
, 1)));
992 if (TREE_CONSTANT (val
))
994 return TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr
, 1)));
997 if (TREE_CODE_CLASS (TREE_CODE (expr
)) == '2'
998 || TREE_CODE_CLASS (TREE_CODE (expr
)) == '<')
1001 op0
= expr_expected_value (TREE_OPERAND (expr
, 0), visited
);
1004 op1
= expr_expected_value (TREE_OPERAND (expr
, 1), visited
);
1007 res
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
), op0
, op1
));
1008 if (TREE_CONSTANT (res
))
1012 if (TREE_CODE_CLASS (TREE_CODE (expr
)) == '1')
1015 op0
= expr_expected_value (TREE_OPERAND (expr
, 0), visited
);
1018 res
= fold (build1 (TREE_CODE (expr
), TREE_TYPE (expr
), op0
));
1019 if (TREE_CONSTANT (res
))
1026 /* Get rid of all builtin_expect calls we no longer need. */
1028 strip_builtin_expect (void)
1033 block_stmt_iterator bi
;
1034 for (bi
= bsi_start (bb
); !bsi_end_p (bi
); bsi_next (&bi
))
1036 tree stmt
= bsi_stmt (bi
);
1040 if (TREE_CODE (stmt
) == MODIFY_EXPR
1041 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
1042 && (fndecl
= get_callee_fndecl (TREE_OPERAND (stmt
, 1)))
1043 && DECL_BUILT_IN (fndecl
)
1044 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
1045 && (arglist
= TREE_OPERAND (TREE_OPERAND (stmt
, 1), 1))
1046 && TREE_CHAIN (arglist
))
1048 TREE_OPERAND (stmt
, 1) = TREE_VALUE (arglist
);
1055 /* Predict using opcode of the last statement in basic block. */
1057 tree_predict_by_opcode (basic_block bb
)
1059 tree stmt
= last_stmt (bb
);
1068 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
1070 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1072 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1075 cond
= TREE_OPERAND (stmt
, 0);
1076 if (!COMPARISON_CLASS_P (cond
))
1078 op0
= TREE_OPERAND (cond
, 0);
1079 type
= TREE_TYPE (op0
);
1080 visited
= BITMAP_XMALLOC ();
1081 val
= expr_expected_value (cond
, visited
);
1082 BITMAP_XFREE (visited
);
1085 if (integer_zerop (val
))
1086 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, NOT_TAKEN
);
1088 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, TAKEN
);
1091 /* Try "pointer heuristic."
1092 A comparison ptr == 0 is predicted as false.
1093 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1094 if (POINTER_TYPE_P (type
))
1096 if (TREE_CODE (cond
) == EQ_EXPR
)
1097 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1098 else if (TREE_CODE (cond
) == NE_EXPR
)
1099 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1103 /* Try "opcode heuristic."
1104 EQ tests are usually false and NE tests are usually true. Also,
1105 most quantities are positive, so we can make the appropriate guesses
1106 about signed comparisons against zero. */
1107 switch (TREE_CODE (cond
))
1111 /* Floating point comparisons appears to behave in a very
1112 unpredictable way because of special role of = tests in
1114 if (FLOAT_TYPE_P (type
))
1116 /* Comparisons with 0 are often used for booleans and there is
1117 nothing useful to predict about them. */
1118 else if (integer_zerop (op0
)
1119 || integer_zerop (TREE_OPERAND (cond
, 1)))
1122 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
1127 /* Floating point comparisons appears to behave in a very
1128 unpredictable way because of special role of = tests in
1130 if (FLOAT_TYPE_P (type
))
1132 /* Comparisons with 0 are often used for booleans and there is
1133 nothing useful to predict about them. */
1134 else if (integer_zerop (op0
)
1135 || integer_zerop (TREE_OPERAND (cond
, 1)))
1138 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
1142 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
1145 case UNORDERED_EXPR
:
1146 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
1151 if (integer_zerop (TREE_OPERAND (cond
, 1))
1152 || integer_onep (TREE_OPERAND (cond
, 1))
1153 || integer_all_onesp (TREE_OPERAND (cond
, 1))
1154 || real_zerop (TREE_OPERAND (cond
, 1))
1155 || real_onep (TREE_OPERAND (cond
, 1))
1156 || real_minus_onep (TREE_OPERAND (cond
, 1)))
1157 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
1162 if (integer_zerop (TREE_OPERAND (cond
, 1))
1163 || integer_onep (TREE_OPERAND (cond
, 1))
1164 || integer_all_onesp (TREE_OPERAND (cond
, 1))
1165 || real_zerop (TREE_OPERAND (cond
, 1))
1166 || real_onep (TREE_OPERAND (cond
, 1))
1167 || real_minus_onep (TREE_OPERAND (cond
, 1)))
1168 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
1176 /* Predict branch probabilities and estimate profile of the tree CFG. */
1178 tree_estimate_probability (void)
1181 struct loops loops_info
;
1183 flow_loops_find (&loops_info
, LOOP_TREE
);
1184 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1185 flow_loops_dump (&loops_info
, dump_file
, NULL
, 0);
1187 connect_infinite_loops_to_exit ();
1188 calculate_dominance_info (CDI_DOMINATORS
);
1189 calculate_dominance_info (CDI_POST_DOMINATORS
);
1191 predict_loops (&loops_info
, false);
1198 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1200 /* Predict early returns to be probable, as we've already taken
1201 care for error returns and other are often used for fast paths
1202 trought function. */
1203 if ((e
->dest
== EXIT_BLOCK_PTR
1204 || (EDGE_COUNT (e
->dest
->succs
) == 1
1205 && EDGE_SUCC (e
->dest
, 0)->dest
== EXIT_BLOCK_PTR
))
1206 && !predicted_by_p (bb
, PRED_NULL_RETURN
)
1207 && !predicted_by_p (bb
, PRED_CONST_RETURN
)
1208 && !predicted_by_p (bb
, PRED_NEGATIVE_RETURN
)
1209 && !last_basic_block_p (e
->dest
))
1210 predict_edge_def (e
, PRED_EARLY_RETURN
, TAKEN
);
1212 /* Look for block we are guarding (ie we dominate it,
1213 but it doesn't postdominate us). */
1214 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
1215 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
1216 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
1218 block_stmt_iterator bi
;
1220 /* The call heuristic claims that a guarded function call
1221 is improbable. This is because such calls are often used
1222 to signal exceptional situations such as printing error
1224 for (bi
= bsi_start (e
->dest
); !bsi_end_p (bi
);
1227 tree stmt
= bsi_stmt (bi
);
1228 if ((TREE_CODE (stmt
) == CALL_EXPR
1229 || (TREE_CODE (stmt
) == MODIFY_EXPR
1230 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
))
1231 /* Constant and pure calls are hardly used to signalize
1232 something exceptional. */
1233 && TREE_SIDE_EFFECTS (stmt
))
1235 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
1241 tree_predict_by_opcode (bb
);
1244 combine_predictions_for_bb (dump_file
, bb
);
1246 if (0) /* FIXME: Enable once we are pass down the profile to RTL level. */
1247 strip_builtin_expect ();
1248 estimate_bb_frequencies (&loops_info
);
1249 free_dominance_info (CDI_POST_DOMINATORS
);
1250 remove_fake_exit_edges ();
1251 flow_loops_free (&loops_info
);
1252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1253 dump_tree_cfg (dump_file
, dump_flags
);
1254 if (profile_status
== PROFILE_ABSENT
)
1255 profile_status
= PROFILE_GUESSED
;
1258 /* __builtin_expect dropped tokens into the insn stream describing expected
1259 values of registers. Generate branch probabilities based off these
1263 expected_value_to_br_prob (void)
1265 rtx insn
, cond
, ev
= NULL_RTX
, ev_reg
= NULL_RTX
;
1267 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1269 switch (GET_CODE (insn
))
1272 /* Look for expected value notes. */
1273 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EXPECTED_VALUE
)
1275 ev
= NOTE_EXPECTED_VALUE (insn
);
1276 ev_reg
= XEXP (ev
, 0);
1282 /* Never propagate across labels. */
1287 /* Look for simple conditional branches. If we haven't got an
1288 expected value yet, no point going further. */
1289 if (!JUMP_P (insn
) || ev
== NULL_RTX
1290 || ! any_condjump_p (insn
))
1295 /* Look for insns that clobber the EV register. */
1296 if (ev
&& reg_set_p (ev_reg
, insn
))
1301 /* Collect the branch condition, hopefully relative to EV_REG. */
1302 /* ??? At present we'll miss things like
1303 (expected_value (eq r70 0))
1305 (set r80 (lt r70 r71))
1306 (set pc (if_then_else (ne r80 0) ...))
1307 as canonicalize_condition will render this to us as
1309 Could use cselib to try and reduce this further. */
1310 cond
= XEXP (SET_SRC (pc_set (insn
)), 0);
1311 cond
= canonicalize_condition (insn
, cond
, 0, NULL
, ev_reg
,
1313 if (! cond
|| XEXP (cond
, 0) != ev_reg
1314 || GET_CODE (XEXP (cond
, 1)) != CONST_INT
)
1317 /* Substitute and simplify. Given that the expression we're
1318 building involves two constants, we should wind up with either
1320 cond
= gen_rtx_fmt_ee (GET_CODE (cond
), VOIDmode
,
1321 XEXP (ev
, 1), XEXP (cond
, 1));
1322 cond
= simplify_rtx (cond
);
1324 /* Turn the condition into a scaled branch probability. */
1325 if (cond
!= const_true_rtx
&& cond
!= const0_rtx
)
1327 predict_insn_def (insn
, PRED_BUILTIN_EXPECT
,
1328 cond
== const_true_rtx
? TAKEN
: NOT_TAKEN
);
1332 /* Check whether this is the last basic block of function. Commonly
1333 there is one extra common cleanup block. */
1335 last_basic_block_p (basic_block bb
)
1337 if (bb
== EXIT_BLOCK_PTR
)
1340 return (bb
->next_bb
== EXIT_BLOCK_PTR
1341 || (bb
->next_bb
->next_bb
== EXIT_BLOCK_PTR
1342 && EDGE_COUNT (bb
->succs
) == 1
1343 && EDGE_SUCC (bb
, 0)->dest
->next_bb
== EXIT_BLOCK_PTR
));
1346 /* This is used to carry information about basic blocks. It is
1347 attached to the AUX field of the standard CFG block. */
1349 typedef struct block_info_def
1351 /* Estimated frequency of execution of basic_block. */
1354 /* To keep queue of basic blocks to process. */
1357 /* True if block needs to be visited in propagate_freq. */
1358 unsigned int tovisit
:1;
1360 /* Number of predecessors we need to visit first. */
1364 /* Similar information for edges. */
1365 typedef struct edge_info_def
1367 /* In case edge is an loopback edge, the probability edge will be reached
1368 in case header is. Estimated number of iterations of the loop can be
1369 then computed as 1 / (1 - back_edge_prob). */
1370 sreal back_edge_prob
;
1371 /* True if the edge is an loopback edge in the natural loop. */
1372 unsigned int back_edge
:1;
1375 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1376 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1378 /* Helper function for estimate_bb_frequencies.
1379 Propagate the frequencies for LOOP. */
1382 propagate_freq (struct loop
*loop
)
1384 basic_block head
= loop
->header
;
1390 /* For each basic block we need to visit count number of his predecessors
1391 we need to visit first. */
1392 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1394 if (BLOCK_INFO (bb
)->tovisit
)
1399 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1401 if (BLOCK_INFO (e
->src
)->tovisit
&& !(e
->flags
& EDGE_DFS_BACK
))
1403 else if (BLOCK_INFO (e
->src
)->tovisit
1404 && dump_file
&& !EDGE_INFO (e
)->back_edge
)
1406 "Irreducible region hit, ignoring edge to %i->%i\n",
1407 e
->src
->index
, bb
->index
);
1409 BLOCK_INFO (bb
)->npredecessors
= count
;
1413 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
1415 for (bb
= head
; bb
; bb
= nextbb
)
1418 sreal cyclic_probability
, frequency
;
1420 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
1421 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
1423 nextbb
= BLOCK_INFO (bb
)->next
;
1424 BLOCK_INFO (bb
)->next
= NULL
;
1426 /* Compute frequency of basic block. */
1429 #ifdef ENABLE_CHECKING
1430 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1432 if (BLOCK_INFO (e
->src
)->tovisit
&& !(e
->flags
& EDGE_DFS_BACK
))
1437 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1439 if (EDGE_INFO (e
)->back_edge
)
1441 sreal_add (&cyclic_probability
, &cyclic_probability
,
1442 &EDGE_INFO (e
)->back_edge_prob
);
1444 else if (!(e
->flags
& EDGE_DFS_BACK
))
1448 /* frequency += (e->probability
1449 * BLOCK_INFO (e->src)->frequency /
1450 REG_BR_PROB_BASE); */
1452 sreal_init (&tmp
, e
->probability
, 0);
1453 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
1454 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
1455 sreal_add (&frequency
, &frequency
, &tmp
);
1459 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
1461 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
1462 sizeof (frequency
));
1466 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
1468 memcpy (&cyclic_probability
, &real_almost_one
,
1469 sizeof (real_almost_one
));
1472 /* BLOCK_INFO (bb)->frequency = frequency
1473 / (1 - cyclic_probability) */
1475 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
1476 sreal_div (&BLOCK_INFO (bb
)->frequency
,
1477 &frequency
, &cyclic_probability
);
1481 BLOCK_INFO (bb
)->tovisit
= 0;
1483 /* Compute back edge frequencies. */
1484 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1486 if (e
->dest
== head
)
1490 /* EDGE_INFO (e)->back_edge_prob
1491 = ((e->probability * BLOCK_INFO (bb)->frequency)
1492 / REG_BR_PROB_BASE); */
1494 sreal_init (&tmp
, e
->probability
, 0);
1495 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
1496 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1497 &tmp
, &real_inv_br_prob_base
);
1501 /* Propagate to successor blocks. */
1502 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1504 if (!(e
->flags
& EDGE_DFS_BACK
)
1505 && BLOCK_INFO (e
->dest
)->npredecessors
)
1507 BLOCK_INFO (e
->dest
)->npredecessors
--;
1508 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
1513 BLOCK_INFO (last
)->next
= e
->dest
;
1522 /* Estimate probabilities of loopback edges in loops at same nest level. */
1525 estimate_loops_at_level (struct loop
*first_loop
)
1529 for (loop
= first_loop
; loop
; loop
= loop
->next
)
1535 estimate_loops_at_level (loop
->inner
);
1537 /* Do not do this for dummy function loop. */
1538 if (EDGE_COUNT (loop
->latch
->succs
) > 0)
1540 /* Find current loop back edge and mark it. */
1541 e
= loop_latch_edge (loop
);
1542 EDGE_INFO (e
)->back_edge
= 1;
1545 bbs
= get_loop_body (loop
);
1546 for (i
= 0; i
< loop
->num_nodes
; i
++)
1547 BLOCK_INFO (bbs
[i
])->tovisit
= 1;
1549 propagate_freq (loop
);
1553 /* Convert counts measured by profile driven feedback to frequencies.
1554 Return nonzero iff there was any nonzero execution count. */
1557 counts_to_freqs (void)
1559 gcov_type count_max
, true_count_max
= 0;
1563 true_count_max
= MAX (bb
->count
, true_count_max
);
1565 count_max
= MAX (true_count_max
, 1);
1566 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1567 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
1568 return true_count_max
;
1571 /* Return true if function is likely to be expensive, so there is no point to
1572 optimize performance of prologue, epilogue or do inlining at the expense
1573 of code size growth. THRESHOLD is the limit of number of instructions
1574 function can execute at average to be still considered not expensive. */
1577 expensive_function_p (int threshold
)
1579 unsigned int sum
= 0;
1583 /* We can not compute accurately for large thresholds due to scaled
1585 if (threshold
> BB_FREQ_MAX
)
1588 /* Frequencies are out of range. This either means that function contains
1589 internal loop executing more than BB_FREQ_MAX times or profile feedback
1590 is available and function has not been executed at all. */
1591 if (ENTRY_BLOCK_PTR
->frequency
== 0)
1594 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1595 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
1600 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
1601 insn
= NEXT_INSN (insn
))
1602 if (active_insn_p (insn
))
1604 sum
+= bb
->frequency
;
1613 /* Estimate basic blocks frequency by given branch probabilities. */
1616 estimate_bb_frequencies (struct loops
*loops
)
1621 if (!flag_branch_probabilities
|| !counts_to_freqs ())
1623 static int real_values_initialized
= 0;
1625 if (!real_values_initialized
)
1627 real_values_initialized
= 1;
1628 sreal_init (&real_zero
, 0, 0);
1629 sreal_init (&real_one
, 1, 0);
1630 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
1631 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
1632 sreal_init (&real_one_half
, 1, -1);
1633 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
1634 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
1637 mark_dfs_back_edges ();
1639 EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->probability
= REG_BR_PROB_BASE
;
1641 /* Set up block info for each basic block. */
1642 alloc_aux_for_blocks (sizeof (struct block_info_def
));
1643 alloc_aux_for_edges (sizeof (struct edge_info_def
));
1644 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1649 BLOCK_INFO (bb
)->tovisit
= 0;
1650 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1652 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
1653 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1654 &EDGE_INFO (e
)->back_edge_prob
,
1655 &real_inv_br_prob_base
);
1659 /* First compute probabilities locally for each loop from innermost
1660 to outermost to examine probabilities for back edges. */
1661 estimate_loops_at_level (loops
->tree_root
);
1663 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
1665 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
1666 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
1668 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
1669 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1673 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
1674 sreal_add (&tmp
, &tmp
, &real_one_half
);
1675 bb
->frequency
= sreal_to_int (&tmp
);
1678 free_aux_for_blocks ();
1679 free_aux_for_edges ();
1681 compute_function_frequency ();
1682 if (flag_reorder_functions
)
1683 choose_function_section ();
1686 /* Decide whether function is hot, cold or unlikely executed. */
1688 compute_function_frequency (void)
1692 if (!profile_info
|| !flag_branch_probabilities
)
1694 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
1697 if (maybe_hot_bb_p (bb
))
1699 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
1702 if (!probably_never_executed_bb_p (bb
))
1703 cfun
->function_frequency
= FUNCTION_FREQUENCY_NORMAL
;
1707 /* Choose appropriate section for the function. */
1709 choose_function_section (void)
1711 if (DECL_SECTION_NAME (current_function_decl
)
1712 || !targetm
.have_named_sections
1713 /* Theoretically we can split the gnu.linkonce text section too,
1714 but this requires more work as the frequency needs to match
1715 for all generated objects so we need to merge the frequency
1716 of all instances. For now just never set frequency for these. */
1717 || DECL_ONE_ONLY (current_function_decl
))
1720 /* If we are doing the partitioning optimization, let the optimization
1721 choose the correct section into which to put things. */
1723 if (flag_reorder_blocks_and_partition
)
1726 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
1727 DECL_SECTION_NAME (current_function_decl
) =
1728 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
1729 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
1730 DECL_SECTION_NAME (current_function_decl
) =
1731 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
1732 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);
1736 struct tree_opt_pass pass_profile
=
1738 "profile", /* name */
1740 tree_estimate_probability
, /* execute */
1743 0, /* static_pass_number */
1744 TV_BRANCH_PROB
, /* tv_id */
1745 PROP_cfg
, /* properties_required */
1746 0, /* properties_provided */
1747 0, /* properties_destroyed */
1748 0, /* todo_flags_start */
1749 TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */