1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 [1] "Branch Prediction for Free"
24 Ball and Larus; PLDI '93.
25 [2] "Static Branch Frequency and Program Profile Analysis"
26 Wu and Larus; MICRO-27.
27 [3] "Corpus-based Static Branch Prediction"
28 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
33 #include "coretypes.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
56 #include "tree-flow.h"
58 #include "tree-dump.h"
59 #include "tree-pass.h"
62 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
63 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
64 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
65 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
67 /* Random guesstimation given names. */
68 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
69 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
70 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
71 #define PROB_ALWAYS (REG_BR_PROB_BASE)
73 static void combine_predictions_for_insn (rtx
, basic_block
);
74 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
75 static void estimate_loops_at_level (struct loop
*loop
);
76 static void propagate_freq (struct loop
*);
77 static void estimate_bb_frequencies (struct loops
*);
78 static int counts_to_freqs (void);
79 static void process_note_predictions (basic_block
, int *);
80 static void process_note_prediction (basic_block
, int *, int, int);
81 static bool last_basic_block_p (basic_block
);
82 static void compute_function_frequency (void);
83 static void choose_function_section (void);
84 static bool can_predict_insn_p (rtx
);
86 /* Information we hold about each branch predictor.
87 Filled using information from predict.def. */
91 const char *const name
; /* Name used in the debugging dumps. */
92 const int hitrate
; /* Expected hitrate used by
93 predict_insn_def call. */
97 /* Use given predictor without Dempster-Shaffer theory if it matches
98 using first_match heuristics. */
99 #define PRED_FLAG_FIRST_MATCH 1
101 /* Recompute hitrate in percent to our representation. */
103 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
105 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
106 static const struct predictor_info predictor_info
[]= {
107 #include "predict.def"
109 /* Upper bound on predictors. */
114 /* Return true in case BB can be CPU intensive and should be optimized
115 for maximal performance. */
118 maybe_hot_bb_p (basic_block bb
)
120 if (profile_info
&& flag_branch_probabilities
122 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
124 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
129 /* Return true in case BB is cold and should be optimized for size. */
132 probably_cold_bb_p (basic_block bb
)
134 if (profile_info
&& flag_branch_probabilities
136 < profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
138 if (bb
->frequency
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
143 /* Return true in case BB is probably never executed. */
145 probably_never_executed_bb_p (basic_block bb
)
147 if (profile_info
&& flag_branch_probabilities
)
148 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
152 /* Return true if the one of outgoing edges is already predicted by
156 rtl_predicted_by_p (basic_block bb
, enum br_predictor predictor
)
159 if (!INSN_P (BB_END (bb
)))
161 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
162 if (REG_NOTE_KIND (note
) == REG_BR_PRED
163 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
168 /* Return true if the one of outgoing edges is already predicted by
172 tree_predicted_by_p (basic_block bb
, enum br_predictor predictor
)
174 struct edge_prediction
*i
= bb_ann (bb
)->predictions
;
175 for (i
= bb_ann (bb
)->predictions
; i
; i
= i
->next
)
176 if (i
->predictor
== predictor
)
182 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
184 if (!any_condjump_p (insn
))
186 if (!flag_guess_branch_prob
)
190 = gen_rtx_EXPR_LIST (REG_BR_PRED
,
191 gen_rtx_CONCAT (VOIDmode
,
192 GEN_INT ((int) predictor
),
193 GEN_INT ((int) probability
)),
197 /* Predict insn by given predictor. */
200 predict_insn_def (rtx insn
, enum br_predictor predictor
,
201 enum prediction taken
)
203 int probability
= predictor_info
[(int) predictor
].hitrate
;
206 probability
= REG_BR_PROB_BASE
- probability
;
208 predict_insn (insn
, predictor
, probability
);
211 /* Predict edge E with given probability if possible. */
214 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
217 last_insn
= BB_END (e
->src
);
219 /* We can store the branch prediction information only about
220 conditional jumps. */
221 if (!any_condjump_p (last_insn
))
224 /* We always store probability of branching. */
225 if (e
->flags
& EDGE_FALLTHRU
)
226 probability
= REG_BR_PROB_BASE
- probability
;
228 predict_insn (last_insn
, predictor
, probability
);
231 /* Predict edge E with the given PROBABILITY. */
233 tree_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
235 struct edge_prediction
*i
= ggc_alloc (sizeof (struct edge_prediction
));
237 i
->next
= bb_ann (e
->src
)->predictions
;
238 bb_ann (e
->src
)->predictions
= i
;
239 i
->probability
= probability
;
240 i
->predictor
= predictor
;
244 /* Return true when we can store prediction on insn INSN.
245 At the moment we represent predictions only on conditional
246 jumps, not at computed jump or other complicated cases. */
248 can_predict_insn_p (rtx insn
)
250 return (JUMP_P (insn
)
251 && any_condjump_p (insn
)
252 && BLOCK_FOR_INSN (insn
)->succ
->succ_next
);
255 /* Predict edge E by given predictor if possible. */
258 predict_edge_def (edge e
, 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_edge (e
, predictor
, probability
);
269 /* Invert all branch predictions or probability notes in the INSN. This needs
270 to be done each time we invert the condition used by the jump. */
273 invert_br_probabilities (rtx insn
)
277 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
278 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
279 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
280 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
281 XEXP (XEXP (note
, 0), 1)
282 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
285 /* Dump information about the branch prediction to the output file. */
288 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
289 basic_block bb
, int used
)
296 while (e
&& (e
->flags
& EDGE_FALLTHRU
))
299 fprintf (file
, " %s heuristics%s: %.1f%%",
300 predictor_info
[predictor
].name
,
301 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
305 fprintf (file
, " exec ");
306 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
309 fprintf (file
, " hit ");
310 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
311 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
315 fprintf (file
, "\n");
318 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
319 note if not already present. Remove now useless REG_BR_PRED notes. */
322 combine_predictions_for_insn (rtx insn
, basic_block bb
)
324 rtx prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
325 rtx
*pnote
= ®_NOTES (insn
);
327 int best_probability
= PROB_EVEN
;
328 int best_predictor
= END_PREDICTORS
;
329 int combined_probability
= REG_BR_PROB_BASE
/ 2;
331 bool first_match
= false;
335 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
338 /* We implement "first match" heuristics and use probability guessed
339 by predictor with smallest index. */
340 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
341 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
343 int predictor
= INTVAL (XEXP (XEXP (note
, 0), 0));
344 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
347 if (best_predictor
> predictor
)
348 best_probability
= probability
, best_predictor
= predictor
;
350 d
= (combined_probability
* probability
351 + (REG_BR_PROB_BASE
- combined_probability
)
352 * (REG_BR_PROB_BASE
- probability
));
354 /* Use FP math to avoid overflows of 32bit integers. */
356 /* If one probability is 0% and one 100%, avoid division by zero. */
357 combined_probability
= REG_BR_PROB_BASE
/ 2;
359 combined_probability
= (((double) combined_probability
) * probability
360 * REG_BR_PROB_BASE
/ d
+ 0.5);
363 /* Decide which heuristic to use. In case we didn't match anything,
364 use no_prediction heuristic, in case we did match, use either
365 first match or Dempster-Shaffer theory depending on the flags. */
367 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
371 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
372 combined_probability
, bb
, true);
375 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
377 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
382 combined_probability
= best_probability
;
383 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
387 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
389 int predictor
= INTVAL (XEXP (XEXP (*pnote
, 0), 0));
390 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
392 dump_prediction (dump_file
, predictor
, probability
, bb
,
393 !first_match
|| best_predictor
== predictor
);
394 *pnote
= XEXP (*pnote
, 1);
397 pnote
= &XEXP (*pnote
, 1);
403 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
404 GEN_INT (combined_probability
), REG_NOTES (insn
));
406 /* Save the prediction into CFG in case we are seeing non-degenerated
408 if (bb
->succ
->succ_next
)
410 BRANCH_EDGE (bb
)->probability
= combined_probability
;
411 FALLTHRU_EDGE (bb
)->probability
412 = REG_BR_PROB_BASE
- combined_probability
;
417 /* Combine predictions into single probability and store them into CFG.
418 Remove now useless prediction entries. */
421 combine_predictions_for_bb (FILE *file
, basic_block bb
)
423 int best_probability
= PROB_EVEN
;
424 int best_predictor
= END_PREDICTORS
;
425 int combined_probability
= REG_BR_PROB_BASE
/ 2;
427 bool first_match
= false;
429 struct edge_prediction
*pred
;
431 edge e
, first
= NULL
, second
= NULL
;
433 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
434 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
437 if (first
&& !second
)
443 /* When there is no successor or only one choice, prediction is easy.
445 We are lazy for now and predict only basic blocks with two outgoing
446 edges. It is possible to predict generic case too, but we have to
447 ignore first match heuristics and do more involved combining. Implement
451 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
452 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
453 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
456 bb_ann (bb
)->predictions
= NULL
;
458 fprintf (file
, "%i edges in bb %i predicted to even probabilities\n",
464 fprintf (file
, "Predictions for bb %i\n", bb
->index
);
466 /* We implement "first match" heuristics and use probability guessed
467 by predictor with smallest index. */
468 for (pred
= bb_ann (bb
)->predictions
; pred
; pred
= pred
->next
)
470 int predictor
= pred
->predictor
;
471 int probability
= pred
->probability
;
473 if (pred
->edge
!= first
)
474 probability
= REG_BR_PROB_BASE
- probability
;
477 if (best_predictor
> predictor
)
478 best_probability
= probability
, best_predictor
= predictor
;
480 d
= (combined_probability
* probability
481 + (REG_BR_PROB_BASE
- combined_probability
)
482 * (REG_BR_PROB_BASE
- probability
));
484 /* Use FP math to avoid overflows of 32bit integers. */
486 /* If one probability is 0% and one 100%, avoid division by zero. */
487 combined_probability
= REG_BR_PROB_BASE
/ 2;
489 combined_probability
= (((double) combined_probability
) * probability
490 * REG_BR_PROB_BASE
/ d
+ 0.5);
493 /* Decide which heuristic to use. In case we didn't match anything,
494 use no_prediction heuristic, in case we did match, use either
495 first match or Dempster-Shaffer theory depending on the flags. */
497 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
501 dump_prediction (file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
504 dump_prediction (file
, PRED_DS_THEORY
, combined_probability
, bb
,
506 dump_prediction (file
, PRED_FIRST_MATCH
, best_probability
, bb
,
511 combined_probability
= best_probability
;
512 dump_prediction (file
, PRED_COMBINED
, combined_probability
, bb
, true);
514 for (pred
= bb_ann (bb
)->predictions
; pred
; pred
= pred
->next
)
516 int predictor
= pred
->predictor
;
517 int probability
= pred
->probability
;
519 if (pred
->edge
!= bb
->succ
)
520 probability
= REG_BR_PROB_BASE
- probability
;
521 dump_prediction (file
, predictor
, probability
, bb
,
522 !first_match
|| best_predictor
== predictor
);
524 bb_ann (bb
)->predictions
= NULL
;
526 first
->probability
= combined_probability
;
527 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
530 /* Predict edge probabilities by exploiting loop structure.
531 When SIMPLELOOPS is set, attempt to count number of iterations by analyzing
534 predict_loops (struct loops
*loops_info
, bool simpleloops
)
538 /* Try to predict out blocks in a loop that are not part of a
540 for (i
= 1; i
< loops_info
->num
; i
++)
542 basic_block bb
, *bbs
;
545 struct loop
*loop
= loops_info
->parray
[i
];
546 struct niter_desc desc
;
547 unsigned HOST_WIDE_INT niter
;
549 flow_loop_scan (loop
, LOOP_EXIT_EDGES
);
550 exits
= loop
->num_exits
;
554 iv_analysis_loop_init (loop
);
555 find_simple_exit (loop
, &desc
);
557 if (desc
.simple_p
&& desc
.const_iter
)
560 niter
= desc
.niter
+ 1;
561 if (niter
== 0) /* We might overflow here. */
564 prob
= (REG_BR_PROB_BASE
565 - (REG_BR_PROB_BASE
+ niter
/2) / niter
);
566 /* Branch prediction algorithm gives 0 frequency for everything
567 after the end of loop for loop having 0 probability to finish. */
568 if (prob
== REG_BR_PROB_BASE
)
569 prob
= REG_BR_PROB_BASE
- 1;
570 predict_edge (desc
.in_edge
, PRED_LOOP_ITERATIONS
,
575 bbs
= get_loop_body (loop
);
577 for (j
= 0; j
< loop
->num_nodes
; j
++)
579 int header_found
= 0;
584 /* Bypass loop heuristics on continue statement. These
585 statements construct loops via "non-loop" constructs
586 in the source language and are better to be handled
588 if ((simpleloops
&& !can_predict_insn_p (BB_END (bb
)))
589 || predicted_by_p (bb
, PRED_CONTINUE
))
592 /* Loop branch heuristics - predict an edge back to a
593 loop's head as taken. */
594 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
595 if (e
->dest
== loop
->header
596 && e
->src
== loop
->latch
)
599 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
602 /* Loop exit heuristics - predict an edge exiting the loop if the
603 conditional has no loop header successors as not taken. */
605 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
606 if (e
->dest
->index
< 0
607 || !flow_bb_inside_loop_p (loop
, e
->dest
))
611 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
615 /* Free basic blocks from get_loop_body. */
620 /* Statically estimate the probability that a branch will be taken and produce
621 estimated profile. When profile feedback is present never executed portions
622 of function gets estimated. */
625 estimate_probability (struct loops
*loops_info
)
629 connect_infinite_loops_to_exit ();
630 calculate_dominance_info (CDI_DOMINATORS
);
631 calculate_dominance_info (CDI_POST_DOMINATORS
);
633 predict_loops (loops_info
, true);
637 /* Attempt to predict conditional jumps using a number of heuristics. */
640 rtx last_insn
= BB_END (bb
);
644 if (! can_predict_insn_p (last_insn
))
647 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
649 /* Predict early returns to be probable, as we've already taken
650 care for error returns and other are often used for fast paths
652 if ((e
->dest
== EXIT_BLOCK_PTR
653 || (e
->dest
->succ
&& !e
->dest
->succ
->succ_next
654 && e
->dest
->succ
->dest
== EXIT_BLOCK_PTR
))
655 && !predicted_by_p (bb
, PRED_NULL_RETURN
)
656 && !predicted_by_p (bb
, PRED_CONST_RETURN
)
657 && !predicted_by_p (bb
, PRED_NEGATIVE_RETURN
)
658 && !last_basic_block_p (e
->dest
))
659 predict_edge_def (e
, PRED_EARLY_RETURN
, TAKEN
);
661 /* Look for block we are guarding (ie we dominate it,
662 but it doesn't postdominate us). */
663 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
664 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
665 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
669 /* The call heuristic claims that a guarded function call
670 is improbable. This is because such calls are often used
671 to signal exceptional situations such as printing error
673 for (insn
= BB_HEAD (e
->dest
); insn
!= NEXT_INSN (BB_END (e
->dest
));
674 insn
= NEXT_INSN (insn
))
676 /* Constant and pure calls are hardly used to signalize
677 something exceptional. */
678 && ! CONST_OR_PURE_CALL_P (insn
))
680 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
686 cond
= get_condition (last_insn
, &earliest
, false);
690 /* Try "pointer heuristic."
691 A comparison ptr == 0 is predicted as false.
692 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
693 if (COMPARISON_P (cond
)
694 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
695 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
697 if (GET_CODE (cond
) == EQ
)
698 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
699 else if (GET_CODE (cond
) == NE
)
700 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
704 /* Try "opcode heuristic."
705 EQ tests are usually false and NE tests are usually true. Also,
706 most quantities are positive, so we can make the appropriate guesses
707 about signed comparisons against zero. */
708 switch (GET_CODE (cond
))
711 /* Unconditional branch. */
712 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
713 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
718 /* Floating point comparisons appears to behave in a very
719 unpredictable way because of special role of = tests in
721 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
723 /* Comparisons with 0 are often used for booleans and there is
724 nothing useful to predict about them. */
725 else if (XEXP (cond
, 1) == const0_rtx
726 || XEXP (cond
, 0) == const0_rtx
)
729 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
734 /* Floating point comparisons appears to behave in a very
735 unpredictable way because of special role of = tests in
737 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
739 /* Comparisons with 0 are often used for booleans and there is
740 nothing useful to predict about them. */
741 else if (XEXP (cond
, 1) == const0_rtx
742 || XEXP (cond
, 0) == const0_rtx
)
745 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
749 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
753 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
758 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
759 || XEXP (cond
, 1) == constm1_rtx
)
760 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
765 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
766 || XEXP (cond
, 1) == constm1_rtx
)
767 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
775 /* Attach the combined probability to each conditional jump. */
777 if (JUMP_P (BB_END (bb
))
778 && any_condjump_p (BB_END (bb
))
779 && bb
->succ
->succ_next
!= NULL
)
780 combine_predictions_for_insn (BB_END (bb
), bb
);
782 remove_fake_edges ();
783 /* Fill in the probability values in flowgraph based on the REG_BR_PROB
787 rtx last_insn
= BB_END (bb
);
789 if (!can_predict_insn_p (last_insn
))
791 /* We can predict only conditional jumps at the moment.
792 Expect each edge to be equally probable.
793 ?? In the future we want to make abnormal edges improbable. */
797 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
800 if (e
->probability
!= 0)
804 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
805 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
808 estimate_bb_frequencies (loops_info
);
809 free_dominance_info (CDI_POST_DOMINATORS
);
813 /* Predict using opcode of the last statement in basic block. */
815 tree_predict_by_opcode (basic_block bb
)
817 tree stmt
= last_stmt (bb
);
823 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
825 for (then_edge
= bb
->succ
; then_edge
; then_edge
= then_edge
->succ_next
)
826 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
828 cond
= TREE_OPERAND (stmt
, 0);
829 if (TREE_CODE_CLASS (TREE_CODE (cond
)) != '<')
831 op0
= TREE_OPERAND (cond
, 0);
832 type
= TREE_TYPE (op0
);
833 /* Try "pointer heuristic."
834 A comparison ptr == 0 is predicted as false.
835 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
836 if (POINTER_TYPE_P (type
))
838 if (TREE_CODE (cond
) == EQ_EXPR
)
839 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
840 else if (TREE_CODE (cond
) == NE_EXPR
)
841 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
845 /* Try "opcode heuristic."
846 EQ tests are usually false and NE tests are usually true. Also,
847 most quantities are positive, so we can make the appropriate guesses
848 about signed comparisons against zero. */
849 switch (TREE_CODE (cond
))
853 /* Floating point comparisons appears to behave in a very
854 unpredictable way because of special role of = tests in
856 if (FLOAT_TYPE_P (type
))
858 /* Comparisons with 0 are often used for booleans and there is
859 nothing useful to predict about them. */
860 else if (integer_zerop (op0
)
861 || integer_zerop (TREE_OPERAND (cond
, 1)))
864 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
869 /* Floating point comparisons appears to behave in a very
870 unpredictable way because of special role of = tests in
872 if (FLOAT_TYPE_P (type
))
874 /* Comparisons with 0 are often used for booleans and there is
875 nothing useful to predict about them. */
876 else if (integer_zerop (op0
)
877 || integer_zerop (TREE_OPERAND (cond
, 1)))
880 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
884 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
888 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
893 if (integer_zerop (TREE_OPERAND (cond
, 1))
894 || integer_onep (TREE_OPERAND (cond
, 1))
895 || integer_all_onesp (TREE_OPERAND (cond
, 1))
896 || real_zerop (TREE_OPERAND (cond
, 1))
897 || real_onep (TREE_OPERAND (cond
, 1))
898 || real_minus_onep (TREE_OPERAND (cond
, 1)))
899 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
904 if (integer_zerop (TREE_OPERAND (cond
, 1))
905 || integer_onep (TREE_OPERAND (cond
, 1))
906 || integer_all_onesp (TREE_OPERAND (cond
, 1))
907 || real_zerop (TREE_OPERAND (cond
, 1))
908 || real_onep (TREE_OPERAND (cond
, 1))
909 || real_minus_onep (TREE_OPERAND (cond
, 1)))
910 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
918 /* Predict branch probabilities and estimate profile of the tree CFG. */
920 tree_estimate_probability (void)
923 struct loops loops_info
;
925 flow_loops_find (&loops_info
, LOOP_TREE
);
926 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
927 flow_loops_dump (&loops_info
, dump_file
, NULL
, 0);
929 connect_infinite_loops_to_exit ();
930 calculate_dominance_info (CDI_DOMINATORS
);
931 calculate_dominance_info (CDI_POST_DOMINATORS
);
933 predict_loops (&loops_info
, false);
939 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
941 /* Predict early returns to be probable, as we've already taken
942 care for error returns and other are often used for fast paths
944 if ((e
->dest
== EXIT_BLOCK_PTR
945 || (e
->dest
->succ
&& !e
->dest
->succ
->succ_next
946 && e
->dest
->succ
->dest
== EXIT_BLOCK_PTR
))
947 && !predicted_by_p (bb
, PRED_NULL_RETURN
)
948 && !predicted_by_p (bb
, PRED_CONST_RETURN
)
949 && !predicted_by_p (bb
, PRED_NEGATIVE_RETURN
)
950 && !last_basic_block_p (e
->dest
))
951 predict_edge_def (e
, PRED_EARLY_RETURN
, TAKEN
);
953 /* Look for block we are guarding (ie we dominate it,
954 but it doesn't postdominate us). */
955 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
956 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
957 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
959 block_stmt_iterator bi
;
961 /* The call heuristic claims that a guarded function call
962 is improbable. This is because such calls are often used
963 to signal exceptional situations such as printing error
965 for (bi
= bsi_start (e
->dest
); !bsi_end_p (bi
);
968 tree stmt
= bsi_stmt (bi
);
969 if ((TREE_CODE (stmt
) == CALL_EXPR
970 || (TREE_CODE (stmt
) == MODIFY_EXPR
971 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
))
972 /* Constant and pure calls are hardly used to signalize
973 something exceptional. */
974 && TREE_SIDE_EFFECTS (stmt
))
976 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
982 tree_predict_by_opcode (bb
);
985 combine_predictions_for_bb (dump_file
, bb
);
987 estimate_bb_frequencies (&loops_info
);
988 free_dominance_info (CDI_POST_DOMINATORS
);
989 remove_fake_edges ();
990 flow_loops_free (&loops_info
);
991 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
992 dump_tree_cfg (dump_file
, dump_flags
);
995 /* __builtin_expect dropped tokens into the insn stream describing expected
996 values of registers. Generate branch probabilities based off these
1000 expected_value_to_br_prob (void)
1002 rtx insn
, cond
, ev
= NULL_RTX
, ev_reg
= NULL_RTX
;
1004 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1006 switch (GET_CODE (insn
))
1009 /* Look for expected value notes. */
1010 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EXPECTED_VALUE
)
1012 ev
= NOTE_EXPECTED_VALUE (insn
);
1013 ev_reg
= XEXP (ev
, 0);
1019 /* Never propagate across labels. */
1024 /* Look for simple conditional branches. If we haven't got an
1025 expected value yet, no point going further. */
1026 if (!JUMP_P (insn
) || ev
== NULL_RTX
1027 || ! any_condjump_p (insn
))
1032 /* Look for insns that clobber the EV register. */
1033 if (ev
&& reg_set_p (ev_reg
, insn
))
1038 /* Collect the branch condition, hopefully relative to EV_REG. */
1039 /* ??? At present we'll miss things like
1040 (expected_value (eq r70 0))
1042 (set r80 (lt r70 r71))
1043 (set pc (if_then_else (ne r80 0) ...))
1044 as canonicalize_condition will render this to us as
1046 Could use cselib to try and reduce this further. */
1047 cond
= XEXP (SET_SRC (pc_set (insn
)), 0);
1048 cond
= canonicalize_condition (insn
, cond
, 0, NULL
, ev_reg
, false);
1049 if (! cond
|| XEXP (cond
, 0) != ev_reg
1050 || GET_CODE (XEXP (cond
, 1)) != CONST_INT
)
1053 /* Substitute and simplify. Given that the expression we're
1054 building involves two constants, we should wind up with either
1056 cond
= gen_rtx_fmt_ee (GET_CODE (cond
), VOIDmode
,
1057 XEXP (ev
, 1), XEXP (cond
, 1));
1058 cond
= simplify_rtx (cond
);
1060 /* Turn the condition into a scaled branch probability. */
1061 if (cond
!= const_true_rtx
&& cond
!= const0_rtx
)
1063 predict_insn_def (insn
, PRED_BUILTIN_EXPECT
,
1064 cond
== const_true_rtx
? TAKEN
: NOT_TAKEN
);
1068 /* Check whether this is the last basic block of function. Commonly
1069 there is one extra common cleanup block. */
1071 last_basic_block_p (basic_block bb
)
1073 if (bb
== EXIT_BLOCK_PTR
)
1076 return (bb
->next_bb
== EXIT_BLOCK_PTR
1077 || (bb
->next_bb
->next_bb
== EXIT_BLOCK_PTR
1078 && bb
->succ
&& !bb
->succ
->succ_next
1079 && bb
->succ
->dest
->next_bb
== EXIT_BLOCK_PTR
));
1082 /* Sets branch probabilities according to PREDiction and
1083 FLAGS. HEADS[bb->index] should be index of basic block in that we
1084 need to alter branch predictions (i.e. the first of our dominators
1085 such that we do not post-dominate it) (but we fill this information
1086 on demand, so -1 may be there in case this was not needed yet). */
1089 process_note_prediction (basic_block bb
, int *heads
, int pred
, int flags
)
1095 taken
= flags
& IS_TAKEN
;
1097 if (heads
[bb
->index
] < 0)
1099 /* This is first time we need this field in heads array; so
1100 find first dominator that we do not post-dominate (we are
1101 using already known members of heads array). */
1102 basic_block ai
= bb
;
1103 basic_block next_ai
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1106 while (heads
[next_ai
->index
] < 0)
1108 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
1110 heads
[next_ai
->index
] = ai
->index
;
1112 next_ai
= get_immediate_dominator (CDI_DOMINATORS
, next_ai
);
1114 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
1115 head
= next_ai
->index
;
1117 head
= heads
[next_ai
->index
];
1118 while (next_ai
!= bb
)
1121 if (heads
[ai
->index
] == ENTRY_BLOCK
)
1122 ai
= ENTRY_BLOCK_PTR
;
1124 ai
= BASIC_BLOCK (heads
[ai
->index
]);
1125 heads
[next_ai
->index
] = head
;
1128 y
= heads
[bb
->index
];
1130 /* Now find the edge that leads to our branch and aply the prediction. */
1132 if (y
== last_basic_block
|| !can_predict_insn_p (BB_END (BASIC_BLOCK (y
))))
1134 for (e
= BASIC_BLOCK (y
)->succ
; e
; e
= e
->succ_next
)
1135 if (e
->dest
->index
>= 0
1136 && dominated_by_p (CDI_POST_DOMINATORS
, e
->dest
, bb
))
1137 predict_edge_def (e
, pred
, taken
);
1140 /* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them
1141 into branch probabilities. For description of heads array, see
1142 process_note_prediction. */
1145 process_note_predictions (basic_block bb
, int *heads
)
1150 /* Additionally, we check here for blocks with no successors. */
1151 int contained_noreturn_call
= 0;
1152 int was_bb_head
= 0;
1153 int noreturn_block
= 1;
1155 for (insn
= BB_END (bb
); insn
;
1156 was_bb_head
|= (insn
== BB_HEAD (bb
)), insn
= PREV_INSN (insn
))
1164 /* Noreturn calls cause program to exit, therefore they are
1165 always predicted as not taken. */
1167 && find_reg_note (insn
, REG_NORETURN
, NULL
))
1168 contained_noreturn_call
= 1;
1172 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_PREDICTION
)
1174 int alg
= (int) NOTE_PREDICTION_ALG (insn
);
1175 /* Process single prediction note. */
1176 process_note_prediction (bb
,
1178 alg
, (int) NOTE_PREDICTION_FLAGS (insn
));
1182 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1183 if (!(e
->flags
& EDGE_FAKE
))
1185 if (contained_noreturn_call
)
1187 /* This block ended from other reasons than because of return.
1188 If it is because of noreturn call, this should certainly not
1189 be taken. Otherwise it is probably some error recovery. */
1190 process_note_prediction (bb
, heads
, PRED_NORETURN
, NOT_TAKEN
);
1194 /* Gathers NOTE_INSN_PREDICTIONs and turns them into
1195 branch probabilities. */
1198 note_prediction_to_br_prob (void)
1203 /* To enable handling of noreturn blocks. */
1204 add_noreturn_fake_exit_edges ();
1205 connect_infinite_loops_to_exit ();
1207 calculate_dominance_info (CDI_POST_DOMINATORS
);
1208 calculate_dominance_info (CDI_DOMINATORS
);
1210 heads
= xmalloc (sizeof (int) * last_basic_block
);
1211 memset (heads
, -1, sizeof (int) * last_basic_block
);
1212 heads
[ENTRY_BLOCK_PTR
->next_bb
->index
] = last_basic_block
;
1214 /* Process all prediction notes. */
1217 process_note_predictions (bb
, heads
);
1219 free_dominance_info (CDI_POST_DOMINATORS
);
1220 free_dominance_info (CDI_DOMINATORS
);
1223 remove_fake_edges ();
1226 /* This is used to carry information about basic blocks. It is
1227 attached to the AUX field of the standard CFG block. */
1229 typedef struct block_info_def
1231 /* Estimated frequency of execution of basic_block. */
1234 /* To keep queue of basic blocks to process. */
1237 /* True if block needs to be visited in propagate_freq. */
1238 unsigned int tovisit
:1;
1240 /* Number of predecessors we need to visit first. */
1244 /* Similar information for edges. */
1245 typedef struct edge_info_def
1247 /* In case edge is an loopback edge, the probability edge will be reached
1248 in case header is. Estimated number of iterations of the loop can be
1249 then computed as 1 / (1 - back_edge_prob). */
1250 sreal back_edge_prob
;
1251 /* True if the edge is an loopback edge in the natural loop. */
1252 unsigned int back_edge
:1;
1255 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1256 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1258 /* Helper function for estimate_bb_frequencies.
1259 Propagate the frequencies for LOOP. */
1262 propagate_freq (struct loop
*loop
)
1264 basic_block head
= loop
->header
;
1270 /* For each basic block we need to visit count number of his predecessors
1271 we need to visit first. */
1272 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1274 if (BLOCK_INFO (bb
)->tovisit
)
1278 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1279 if (BLOCK_INFO (e
->src
)->tovisit
&& !(e
->flags
& EDGE_DFS_BACK
))
1281 else if (BLOCK_INFO (e
->src
)->tovisit
1282 && dump_file
&& !EDGE_INFO (e
)->back_edge
)
1284 "Irreducible region hit, ignoring edge to %i->%i\n",
1285 e
->src
->index
, bb
->index
);
1286 BLOCK_INFO (bb
)->npredecessors
= count
;
1290 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
1292 for (bb
= head
; bb
; bb
= nextbb
)
1294 sreal cyclic_probability
, frequency
;
1296 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
1297 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
1299 nextbb
= BLOCK_INFO (bb
)->next
;
1300 BLOCK_INFO (bb
)->next
= NULL
;
1302 /* Compute frequency of basic block. */
1305 #ifdef ENABLE_CHECKING
1306 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1307 if (BLOCK_INFO (e
->src
)->tovisit
&& !(e
->flags
& EDGE_DFS_BACK
))
1311 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1312 if (EDGE_INFO (e
)->back_edge
)
1314 sreal_add (&cyclic_probability
, &cyclic_probability
,
1315 &EDGE_INFO (e
)->back_edge_prob
);
1317 else if (!(e
->flags
& EDGE_DFS_BACK
))
1321 /* frequency += (e->probability
1322 * BLOCK_INFO (e->src)->frequency /
1323 REG_BR_PROB_BASE); */
1325 sreal_init (&tmp
, e
->probability
, 0);
1326 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
1327 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
1328 sreal_add (&frequency
, &frequency
, &tmp
);
1331 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
1333 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
1334 sizeof (frequency
));
1338 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
1340 memcpy (&cyclic_probability
, &real_almost_one
,
1341 sizeof (real_almost_one
));
1344 /* BLOCK_INFO (bb)->frequency = frequency
1345 / (1 - cyclic_probability) */
1347 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
1348 sreal_div (&BLOCK_INFO (bb
)->frequency
,
1349 &frequency
, &cyclic_probability
);
1353 BLOCK_INFO (bb
)->tovisit
= 0;
1355 /* Compute back edge frequencies. */
1356 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1357 if (e
->dest
== head
)
1361 /* EDGE_INFO (e)->back_edge_prob
1362 = ((e->probability * BLOCK_INFO (bb)->frequency)
1363 / REG_BR_PROB_BASE); */
1365 sreal_init (&tmp
, e
->probability
, 0);
1366 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
1367 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1368 &tmp
, &real_inv_br_prob_base
);
1371 /* Propagate to successor blocks. */
1372 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1373 if (!(e
->flags
& EDGE_DFS_BACK
)
1374 && BLOCK_INFO (e
->dest
)->npredecessors
)
1376 BLOCK_INFO (e
->dest
)->npredecessors
--;
1377 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
1382 BLOCK_INFO (last
)->next
= e
->dest
;
1390 /* Estimate probabilities of loopback edges in loops at same nest level. */
1393 estimate_loops_at_level (struct loop
*first_loop
)
1397 for (loop
= first_loop
; loop
; loop
= loop
->next
)
1403 estimate_loops_at_level (loop
->inner
);
1405 if (loop
->latch
->succ
) /* Do not do this for dummy function loop. */
1407 /* Find current loop back edge and mark it. */
1408 e
= loop_latch_edge (loop
);
1409 EDGE_INFO (e
)->back_edge
= 1;
1412 bbs
= get_loop_body (loop
);
1413 for (i
= 0; i
< loop
->num_nodes
; i
++)
1414 BLOCK_INFO (bbs
[i
])->tovisit
= 1;
1416 propagate_freq (loop
);
1420 /* Convert counts measured by profile driven feedback to frequencies.
1421 Return nonzero iff there was any nonzero execution count. */
1424 counts_to_freqs (void)
1426 gcov_type count_max
, true_count_max
= 0;
1430 true_count_max
= MAX (bb
->count
, true_count_max
);
1432 count_max
= MAX (true_count_max
, 1);
1433 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1434 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
1435 return true_count_max
;
1438 /* Return true if function is likely to be expensive, so there is no point to
1439 optimize performance of prologue, epilogue or do inlining at the expense
1440 of code size growth. THRESHOLD is the limit of number of instructions
1441 function can execute at average to be still considered not expensive. */
1444 expensive_function_p (int threshold
)
1446 unsigned int sum
= 0;
1450 /* We can not compute accurately for large thresholds due to scaled
1452 if (threshold
> BB_FREQ_MAX
)
1455 /* Frequencies are out of range. This either means that function contains
1456 internal loop executing more than BB_FREQ_MAX times or profile feedback
1457 is available and function has not been executed at all. */
1458 if (ENTRY_BLOCK_PTR
->frequency
== 0)
1461 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1462 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
1467 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
1468 insn
= NEXT_INSN (insn
))
1469 if (active_insn_p (insn
))
1471 sum
+= bb
->frequency
;
1480 /* Estimate basic blocks frequency by given branch probabilities. */
1483 estimate_bb_frequencies (struct loops
*loops
)
1488 if (!flag_branch_probabilities
|| !counts_to_freqs ())
1490 static int real_values_initialized
= 0;
1492 if (!real_values_initialized
)
1494 real_values_initialized
= 1;
1495 sreal_init (&real_zero
, 0, 0);
1496 sreal_init (&real_one
, 1, 0);
1497 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
1498 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
1499 sreal_init (&real_one_half
, 1, -1);
1500 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
1501 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
1504 mark_dfs_back_edges ();
1506 ENTRY_BLOCK_PTR
->succ
->probability
= REG_BR_PROB_BASE
;
1508 /* Set up block info for each basic block. */
1509 alloc_aux_for_blocks (sizeof (struct block_info_def
));
1510 alloc_aux_for_edges (sizeof (struct edge_info_def
));
1511 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1515 BLOCK_INFO (bb
)->tovisit
= 0;
1516 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1518 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
1519 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1520 &EDGE_INFO (e
)->back_edge_prob
,
1521 &real_inv_br_prob_base
);
1525 /* First compute probabilities locally for each loop from innermost
1526 to outermost to examine probabilities for back edges. */
1527 estimate_loops_at_level (loops
->tree_root
);
1529 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
1531 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
1532 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
1534 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
1535 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1539 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
1540 sreal_add (&tmp
, &tmp
, &real_one_half
);
1541 bb
->frequency
= sreal_to_int (&tmp
);
1544 free_aux_for_blocks ();
1545 free_aux_for_edges ();
1547 compute_function_frequency ();
1548 if (flag_reorder_functions
)
1549 choose_function_section ();
1552 /* Decide whether function is hot, cold or unlikely executed. */
1554 compute_function_frequency (void)
1558 if (!profile_info
|| !flag_branch_probabilities
)
1560 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
1563 if (maybe_hot_bb_p (bb
))
1565 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
1568 if (!probably_never_executed_bb_p (bb
))
1569 cfun
->function_frequency
= FUNCTION_FREQUENCY_NORMAL
;
1573 /* Choose appropriate section for the function. */
1575 choose_function_section (void)
1577 if (DECL_SECTION_NAME (current_function_decl
)
1578 || !targetm
.have_named_sections
1579 /* Theoretically we can split the gnu.linkonce text section too,
1580 but this requires more work as the frequency needs to match
1581 for all generated objects so we need to merge the frequency
1582 of all instances. For now just never set frequency for these. */
1583 || DECL_ONE_ONLY (current_function_decl
))
1585 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
1586 DECL_SECTION_NAME (current_function_decl
) =
1587 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
1588 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
1589 DECL_SECTION_NAME (current_function_decl
) =
1590 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
1591 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);
1595 struct tree_opt_pass pass_profile
=
1597 "profile", /* name */
1599 tree_estimate_probability
, /* execute */
1602 0, /* static_pass_number */
1603 TV_BRANCH_PROB
, /* tv_id */
1604 PROP_cfg
, /* properties_required */
1605 0, /* properties_provided */
1606 0, /* properties_destroyed */
1607 0, /* todo_flags_start */
1608 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */