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
*, bitmap
);
77 static void propagate_freq (struct loop
*, bitmap
);
78 static void estimate_bb_frequencies (struct loops
*);
79 static void predict_paths_leading_to (basic_block
, int *, enum br_predictor
, enum prediction
);
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
)
297 if (! (e
->flags
& EDGE_FALLTHRU
))
300 fprintf (file
, " %s heuristics%s: %.1f%%",
301 predictor_info
[predictor
].name
,
302 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
306 fprintf (file
, " exec ");
307 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
310 fprintf (file
, " hit ");
311 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
312 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
316 fprintf (file
, "\n");
319 /* We can not predict the probabilities of outgoing edges of bb. Set them
320 evenly and hope for the best. */
322 set_even_probabilities (basic_block bb
)
328 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
329 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
331 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
332 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
333 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
338 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
339 note if not already present. Remove now useless REG_BR_PRED notes. */
342 combine_predictions_for_insn (rtx insn
, basic_block bb
)
347 int best_probability
= PROB_EVEN
;
348 int best_predictor
= END_PREDICTORS
;
349 int combined_probability
= REG_BR_PROB_BASE
/ 2;
351 bool first_match
= false;
354 if (!can_predict_insn_p (insn
))
356 set_even_probabilities (bb
);
360 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
361 pnote
= ®_NOTES (insn
);
363 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
366 /* We implement "first match" heuristics and use probability guessed
367 by predictor with smallest index. */
368 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
369 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
371 int predictor
= INTVAL (XEXP (XEXP (note
, 0), 0));
372 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
375 if (best_predictor
> predictor
)
376 best_probability
= probability
, best_predictor
= predictor
;
378 d
= (combined_probability
* probability
379 + (REG_BR_PROB_BASE
- combined_probability
)
380 * (REG_BR_PROB_BASE
- probability
));
382 /* Use FP math to avoid overflows of 32bit integers. */
384 /* If one probability is 0% and one 100%, avoid division by zero. */
385 combined_probability
= REG_BR_PROB_BASE
/ 2;
387 combined_probability
= (((double) combined_probability
) * probability
388 * REG_BR_PROB_BASE
/ d
+ 0.5);
391 /* Decide which heuristic to use. In case we didn't match anything,
392 use no_prediction heuristic, in case we did match, use either
393 first match or Dempster-Shaffer theory depending on the flags. */
395 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
399 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
400 combined_probability
, bb
, true);
403 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
405 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
410 combined_probability
= best_probability
;
411 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
415 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
417 int predictor
= INTVAL (XEXP (XEXP (*pnote
, 0), 0));
418 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
420 dump_prediction (dump_file
, predictor
, probability
, bb
,
421 !first_match
|| best_predictor
== predictor
);
422 *pnote
= XEXP (*pnote
, 1);
425 pnote
= &XEXP (*pnote
, 1);
431 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
432 GEN_INT (combined_probability
), REG_NOTES (insn
));
434 /* Save the prediction into CFG in case we are seeing non-degenerated
436 if (EDGE_COUNT (bb
->succs
) > 1)
438 BRANCH_EDGE (bb
)->probability
= combined_probability
;
439 FALLTHRU_EDGE (bb
)->probability
440 = REG_BR_PROB_BASE
- combined_probability
;
443 else if (EDGE_COUNT (bb
->succs
) > 1)
445 int prob
= INTVAL (XEXP (prob_note
, 0));
447 BRANCH_EDGE (bb
)->probability
= prob
;
448 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
451 EDGE_SUCC (bb
, 0)->probability
= REG_BR_PROB_BASE
;
454 /* Combine predictions into single probability and store them into CFG.
455 Remove now useless prediction entries. */
458 combine_predictions_for_bb (FILE *file
, basic_block bb
)
460 int best_probability
= PROB_EVEN
;
461 int best_predictor
= END_PREDICTORS
;
462 int combined_probability
= REG_BR_PROB_BASE
/ 2;
464 bool first_match
= false;
466 struct edge_prediction
*pred
;
468 edge e
, first
= NULL
, second
= NULL
;
471 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
472 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
475 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
)
673 if (e
->dest
== loop
->header
674 && e
->src
== loop
->latch
)
677 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
680 /* Loop exit heuristics - predict an edge exiting the loop if the
681 conditional has no loop header successors as not taken. */
683 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
684 if (e
->dest
->index
< 0
685 || !flow_bb_inside_loop_p (loop
, e
->dest
))
689 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
693 /* Free basic blocks from get_loop_body. */
701 /* Attempt to predict probabilities of BB outgoing edges using local
704 bb_estimate_probability_locally (basic_block bb
)
706 rtx last_insn
= BB_END (bb
);
709 if (! can_predict_insn_p (last_insn
))
711 cond
= get_condition (last_insn
, NULL
, false, false);
715 /* Try "pointer heuristic."
716 A comparison ptr == 0 is predicted as false.
717 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
718 if (COMPARISON_P (cond
)
719 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
720 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
722 if (GET_CODE (cond
) == EQ
)
723 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
724 else if (GET_CODE (cond
) == NE
)
725 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
729 /* Try "opcode heuristic."
730 EQ tests are usually false and NE tests are usually true. Also,
731 most quantities are positive, so we can make the appropriate guesses
732 about signed comparisons against zero. */
733 switch (GET_CODE (cond
))
736 /* Unconditional branch. */
737 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
738 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
743 /* Floating point comparisons appears to behave in a very
744 unpredictable way because of special role of = tests in
746 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
748 /* Comparisons with 0 are often used for booleans and there is
749 nothing useful to predict about them. */
750 else if (XEXP (cond
, 1) == const0_rtx
751 || XEXP (cond
, 0) == const0_rtx
)
754 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
759 /* Floating point comparisons appears to behave in a very
760 unpredictable way because of special role of = tests in
762 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
764 /* Comparisons with 0 are often used for booleans and there is
765 nothing useful to predict about them. */
766 else if (XEXP (cond
, 1) == const0_rtx
767 || XEXP (cond
, 0) == const0_rtx
)
770 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
774 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
778 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
783 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
784 || XEXP (cond
, 1) == constm1_rtx
)
785 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
790 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
791 || XEXP (cond
, 1) == constm1_rtx
)
792 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
800 /* Statically estimate the probability that a branch will be taken and produce
801 estimated profile. When profile feedback is present never executed portions
802 of function gets estimated. */
805 estimate_probability (struct loops
*loops_info
)
809 connect_infinite_loops_to_exit ();
810 calculate_dominance_info (CDI_DOMINATORS
);
811 calculate_dominance_info (CDI_POST_DOMINATORS
);
813 predict_loops (loops_info
, true);
817 /* Attempt to predict conditional jumps using a number of heuristics. */
820 rtx last_insn
= BB_END (bb
);
824 if (! can_predict_insn_p (last_insn
))
827 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
829 /* Predict early returns to be probable, as we've already taken
830 care for error returns and other are often used for fast paths
832 if ((e
->dest
== EXIT_BLOCK_PTR
833 || (EDGE_COUNT (e
->dest
->succs
) == 1
834 && EDGE_SUCC (e
->dest
, 0)->dest
== EXIT_BLOCK_PTR
))
835 && !predicted_by_p (bb
, PRED_NULL_RETURN
)
836 && !predicted_by_p (bb
, PRED_CONST_RETURN
)
837 && !predicted_by_p (bb
, PRED_NEGATIVE_RETURN
)
838 && !last_basic_block_p (e
->dest
))
839 predict_edge_def (e
, PRED_EARLY_RETURN
, TAKEN
);
841 /* Look for block we are guarding (i.e. we dominate it,
842 but it doesn't postdominate us). */
843 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
844 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
845 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
849 /* The call heuristic claims that a guarded function call
850 is improbable. This is because such calls are often used
851 to signal exceptional situations such as printing error
853 for (insn
= BB_HEAD (e
->dest
); insn
!= NEXT_INSN (BB_END (e
->dest
));
854 insn
= NEXT_INSN (insn
))
856 /* Constant and pure calls are hardly used to signalize
857 something exceptional. */
858 && ! CONST_OR_PURE_CALL_P (insn
))
860 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
865 bb_estimate_probability_locally (bb
);
868 /* Attach the combined probability to each conditional jump. */
870 combine_predictions_for_insn (BB_END (bb
), bb
);
872 remove_fake_edges ();
873 estimate_bb_frequencies (loops_info
);
874 free_dominance_info (CDI_POST_DOMINATORS
);
875 if (profile_status
== PROFILE_ABSENT
)
876 profile_status
= PROFILE_GUESSED
;
879 /* Set edge->probability for each successor edge of BB. */
881 guess_outgoing_edge_probabilities (basic_block bb
)
883 bb_estimate_probability_locally (bb
);
884 combine_predictions_for_insn (BB_END (bb
), bb
);
887 /* Return constant EXPR will likely have at execution time, NULL if unknown.
888 The function is used by builtin_expect branch predictor so the evidence
889 must come from this construct and additional possible constant folding.
891 We may want to implement more involved value guess (such as value range
892 propagation based prediction), but such tricks shall go to new
896 expr_expected_value (tree expr
, bitmap visited
)
898 if (TREE_CONSTANT (expr
))
900 else if (TREE_CODE (expr
) == SSA_NAME
)
902 tree def
= SSA_NAME_DEF_STMT (expr
);
904 /* If we were already here, break the infinite cycle. */
905 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (expr
)))
907 bitmap_set_bit (visited
, SSA_NAME_VERSION (expr
));
909 if (TREE_CODE (def
) == PHI_NODE
)
911 /* All the arguments of the PHI node must have the same constant
914 tree val
= NULL
, new_val
;
916 for (i
= 0; i
< PHI_NUM_ARGS (def
); i
++)
918 tree arg
= PHI_ARG_DEF (def
, i
);
920 /* If this PHI has itself as an argument, we cannot
921 determine the string length of this argument. However,
922 if we can find an expected constant value for the other
923 PHI args then we can still be sure that this is
924 likely a constant. So be optimistic and just
925 continue with the next argument. */
926 if (arg
== PHI_RESULT (def
))
929 new_val
= expr_expected_value (arg
, visited
);
934 else if (!operand_equal_p (val
, new_val
, false))
939 if (TREE_CODE (def
) != MODIFY_EXPR
|| TREE_OPERAND (def
, 0) != expr
)
941 return expr_expected_value (TREE_OPERAND (def
, 1), visited
);
943 else if (TREE_CODE (expr
) == CALL_EXPR
)
945 tree decl
= get_callee_fndecl (expr
);
948 if (DECL_BUILT_IN (decl
) && DECL_FUNCTION_CODE (decl
) == BUILT_IN_EXPECT
)
950 tree arglist
= TREE_OPERAND (expr
, 1);
953 if (arglist
== NULL_TREE
954 || TREE_CHAIN (arglist
) == NULL_TREE
)
956 val
= TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr
, 1)));
957 if (TREE_CONSTANT (val
))
959 return TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr
, 1)));
962 if (BINARY_CLASS_P (expr
) || COMPARISON_CLASS_P (expr
))
965 op0
= expr_expected_value (TREE_OPERAND (expr
, 0), visited
);
968 op1
= expr_expected_value (TREE_OPERAND (expr
, 1), visited
);
971 res
= fold (build (TREE_CODE (expr
), TREE_TYPE (expr
), op0
, op1
));
972 if (TREE_CONSTANT (res
))
976 if (UNARY_CLASS_P (expr
))
979 op0
= expr_expected_value (TREE_OPERAND (expr
, 0), visited
);
982 res
= fold (build1 (TREE_CODE (expr
), TREE_TYPE (expr
), op0
));
983 if (TREE_CONSTANT (res
))
990 /* Get rid of all builtin_expect calls we no longer need. */
992 strip_builtin_expect (void)
997 block_stmt_iterator bi
;
998 for (bi
= bsi_start (bb
); !bsi_end_p (bi
); bsi_next (&bi
))
1000 tree stmt
= bsi_stmt (bi
);
1004 if (TREE_CODE (stmt
) == MODIFY_EXPR
1005 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
1006 && (fndecl
= get_callee_fndecl (TREE_OPERAND (stmt
, 1)))
1007 && DECL_BUILT_IN (fndecl
)
1008 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
1009 && (arglist
= TREE_OPERAND (TREE_OPERAND (stmt
, 1), 1))
1010 && TREE_CHAIN (arglist
))
1012 TREE_OPERAND (stmt
, 1) = TREE_VALUE (arglist
);
1019 /* Predict using opcode of the last statement in basic block. */
1021 tree_predict_by_opcode (basic_block bb
)
1023 tree stmt
= last_stmt (bb
);
1032 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
1034 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1035 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1037 cond
= TREE_OPERAND (stmt
, 0);
1038 if (!COMPARISON_CLASS_P (cond
))
1040 op0
= TREE_OPERAND (cond
, 0);
1041 type
= TREE_TYPE (op0
);
1042 visited
= BITMAP_XMALLOC ();
1043 val
= expr_expected_value (cond
, visited
);
1044 BITMAP_XFREE (visited
);
1047 if (integer_zerop (val
))
1048 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, NOT_TAKEN
);
1050 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, TAKEN
);
1053 /* Try "pointer heuristic."
1054 A comparison ptr == 0 is predicted as false.
1055 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1056 if (POINTER_TYPE_P (type
))
1058 if (TREE_CODE (cond
) == EQ_EXPR
)
1059 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1060 else if (TREE_CODE (cond
) == NE_EXPR
)
1061 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1065 /* Try "opcode heuristic."
1066 EQ tests are usually false and NE tests are usually true. Also,
1067 most quantities are positive, so we can make the appropriate guesses
1068 about signed comparisons against zero. */
1069 switch (TREE_CODE (cond
))
1073 /* Floating point comparisons appears to behave in a very
1074 unpredictable way because of special role of = tests in
1076 if (FLOAT_TYPE_P (type
))
1078 /* Comparisons with 0 are often used for booleans and there is
1079 nothing useful to predict about them. */
1080 else if (integer_zerop (op0
)
1081 || integer_zerop (TREE_OPERAND (cond
, 1)))
1084 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
1089 /* Floating point comparisons appears to behave in a very
1090 unpredictable way because of special role of = tests in
1092 if (FLOAT_TYPE_P (type
))
1094 /* Comparisons with 0 are often used for booleans and there is
1095 nothing useful to predict about them. */
1096 else if (integer_zerop (op0
)
1097 || integer_zerop (TREE_OPERAND (cond
, 1)))
1100 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
1104 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
1107 case UNORDERED_EXPR
:
1108 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
1113 if (integer_zerop (TREE_OPERAND (cond
, 1))
1114 || integer_onep (TREE_OPERAND (cond
, 1))
1115 || integer_all_onesp (TREE_OPERAND (cond
, 1))
1116 || real_zerop (TREE_OPERAND (cond
, 1))
1117 || real_onep (TREE_OPERAND (cond
, 1))
1118 || real_minus_onep (TREE_OPERAND (cond
, 1)))
1119 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
1124 if (integer_zerop (TREE_OPERAND (cond
, 1))
1125 || integer_onep (TREE_OPERAND (cond
, 1))
1126 || integer_all_onesp (TREE_OPERAND (cond
, 1))
1127 || real_zerop (TREE_OPERAND (cond
, 1))
1128 || real_onep (TREE_OPERAND (cond
, 1))
1129 || real_minus_onep (TREE_OPERAND (cond
, 1)))
1130 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
1138 /* Try to guess whether the value of return means error code. */
1139 static enum br_predictor
1140 return_prediction (tree val
, enum prediction
*prediction
)
1144 return PRED_NO_PREDICTION
;
1145 /* Different heuristics for pointers and scalars. */
1146 if (POINTER_TYPE_P (TREE_TYPE (val
)))
1148 /* NULL is usually not returned. */
1149 if (integer_zerop (val
))
1151 *prediction
= NOT_TAKEN
;
1152 return PRED_NULL_RETURN
;
1155 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
1157 /* Negative return values are often used to indicate
1159 if (TREE_CODE (val
) == INTEGER_CST
1160 && tree_int_cst_sgn (val
) < 0)
1162 *prediction
= NOT_TAKEN
;
1163 return PRED_NEGATIVE_RETURN
;
1165 /* Constant return values seems to be commonly taken.
1166 Zero/one often represent booleans so exclude them from the
1168 if (TREE_CONSTANT (val
)
1169 && (!integer_zerop (val
) && !integer_onep (val
)))
1171 *prediction
= TAKEN
;
1172 return PRED_NEGATIVE_RETURN
;
1175 return PRED_NO_PREDICTION
;
1178 /* Find the basic block with return expression and look up for possible
1179 return value trying to apply RETURN_PREDICTION heuristics. */
1181 apply_return_prediction (int *heads
)
1187 int phi_num_args
, i
;
1188 enum br_predictor pred
;
1189 enum prediction direction
;
1192 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1194 return_stmt
= last_stmt (e
->src
);
1195 if (TREE_CODE (return_stmt
) == RETURN_EXPR
)
1200 return_val
= TREE_OPERAND (return_stmt
, 0);
1203 if (TREE_CODE (return_val
) == MODIFY_EXPR
)
1204 return_val
= TREE_OPERAND (return_val
, 1);
1205 if (TREE_CODE (return_val
) != SSA_NAME
1206 || !SSA_NAME_DEF_STMT (return_val
)
1207 || TREE_CODE (SSA_NAME_DEF_STMT (return_val
)) != PHI_NODE
)
1209 phi
= SSA_NAME_DEF_STMT (return_val
);
1212 tree next
= PHI_CHAIN (phi
);
1213 if (PHI_RESULT (phi
) == return_val
)
1219 phi_num_args
= PHI_NUM_ARGS (phi
);
1220 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
1222 /* Avoid the degenerate case where all return values form the function
1223 belongs to same category (ie they are all positive constants)
1224 so we can hardly say something about them. */
1225 for (i
= 1; i
< phi_num_args
; i
++)
1226 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
1228 if (i
!= phi_num_args
)
1229 for (i
= 0; i
< phi_num_args
; i
++)
1231 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
1232 if (pred
!= PRED_NO_PREDICTION
)
1233 predict_paths_leading_to (PHI_ARG_EDGE (phi
, i
)->src
, heads
, pred
,
1238 /* Look for basic block that contains unlikely to happen events
1239 (such as noreturn calls) and mark all paths leading to execution
1240 of this basic blocks as unlikely. */
1243 tree_bb_level_predictions (void)
1248 heads
= xmalloc (sizeof (int) * last_basic_block
);
1249 memset (heads
, -1, sizeof (int) * last_basic_block
);
1250 heads
[ENTRY_BLOCK_PTR
->next_bb
->index
] = last_basic_block
;
1252 apply_return_prediction (heads
);
1256 block_stmt_iterator bsi
= bsi_last (bb
);
1258 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1260 tree stmt
= bsi_stmt (bsi
);
1261 switch (TREE_CODE (stmt
))
1264 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
)
1266 stmt
= TREE_OPERAND (stmt
, 1);
1272 if (call_expr_flags (stmt
) & ECF_NORETURN
)
1273 predict_paths_leading_to (bb
, heads
, PRED_NORETURN
,
1285 /* Predict branch probabilities and estimate profile of the tree CFG. */
1287 tree_estimate_probability (void)
1290 struct loops loops_info
;
1292 flow_loops_find (&loops_info
, LOOP_TREE
);
1293 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1294 flow_loops_dump (&loops_info
, dump_file
, NULL
, 0);
1296 add_noreturn_fake_exit_edges ();
1297 connect_infinite_loops_to_exit ();
1298 calculate_dominance_info (CDI_DOMINATORS
);
1299 calculate_dominance_info (CDI_POST_DOMINATORS
);
1301 tree_bb_level_predictions ();
1303 mark_irreducible_loops (&loops_info
);
1304 predict_loops (&loops_info
, false);
1311 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1313 /* Predict early returns to be probable, as we've already taken
1314 care for error returns and other cases are often used for
1315 fast paths trought function. */
1316 if (e
->dest
== EXIT_BLOCK_PTR
1317 && TREE_CODE (last_stmt (bb
)) == RETURN_EXPR
1318 && EDGE_COUNT (bb
->preds
) > 1)
1323 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
1324 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
1325 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
1326 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
)
1327 && !last_basic_block_p (e1
->src
))
1328 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1331 /* Look for block we are guarding (ie we dominate it,
1332 but it doesn't postdominate us). */
1333 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
1334 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
1335 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
1337 block_stmt_iterator bi
;
1339 /* The call heuristic claims that a guarded function call
1340 is improbable. This is because such calls are often used
1341 to signal exceptional situations such as printing error
1343 for (bi
= bsi_start (e
->dest
); !bsi_end_p (bi
);
1346 tree stmt
= bsi_stmt (bi
);
1347 if ((TREE_CODE (stmt
) == CALL_EXPR
1348 || (TREE_CODE (stmt
) == MODIFY_EXPR
1349 && TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
))
1350 /* Constant and pure calls are hardly used to signalize
1351 something exceptional. */
1352 && TREE_SIDE_EFFECTS (stmt
))
1354 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
1360 tree_predict_by_opcode (bb
);
1363 combine_predictions_for_bb (dump_file
, bb
);
1365 if (0) /* FIXME: Enable once we are pass down the profile to RTL level. */
1366 strip_builtin_expect ();
1367 estimate_bb_frequencies (&loops_info
);
1368 free_dominance_info (CDI_POST_DOMINATORS
);
1369 remove_fake_exit_edges ();
1370 flow_loops_free (&loops_info
);
1371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1372 dump_tree_cfg (dump_file
, dump_flags
);
1373 if (profile_status
== PROFILE_ABSENT
)
1374 profile_status
= PROFILE_GUESSED
;
1377 /* __builtin_expect dropped tokens into the insn stream describing expected
1378 values of registers. Generate branch probabilities based off these
1382 expected_value_to_br_prob (void)
1384 rtx insn
, cond
, ev
= NULL_RTX
, ev_reg
= NULL_RTX
;
1386 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
1388 switch (GET_CODE (insn
))
1391 /* Look for expected value notes. */
1392 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EXPECTED_VALUE
)
1394 ev
= NOTE_EXPECTED_VALUE (insn
);
1395 ev_reg
= XEXP (ev
, 0);
1401 /* Never propagate across labels. */
1406 /* Look for simple conditional branches. If we haven't got an
1407 expected value yet, no point going further. */
1408 if (!JUMP_P (insn
) || ev
== NULL_RTX
1409 || ! any_condjump_p (insn
))
1414 /* Look for insns that clobber the EV register. */
1415 if (ev
&& reg_set_p (ev_reg
, insn
))
1420 /* Collect the branch condition, hopefully relative to EV_REG. */
1421 /* ??? At present we'll miss things like
1422 (expected_value (eq r70 0))
1424 (set r80 (lt r70 r71))
1425 (set pc (if_then_else (ne r80 0) ...))
1426 as canonicalize_condition will render this to us as
1428 Could use cselib to try and reduce this further. */
1429 cond
= XEXP (SET_SRC (pc_set (insn
)), 0);
1430 cond
= canonicalize_condition (insn
, cond
, 0, NULL
, ev_reg
,
1432 if (! cond
|| XEXP (cond
, 0) != ev_reg
1433 || GET_CODE (XEXP (cond
, 1)) != CONST_INT
)
1436 /* Substitute and simplify. Given that the expression we're
1437 building involves two constants, we should wind up with either
1439 cond
= gen_rtx_fmt_ee (GET_CODE (cond
), VOIDmode
,
1440 XEXP (ev
, 1), XEXP (cond
, 1));
1441 cond
= simplify_rtx (cond
);
1443 /* Turn the condition into a scaled branch probability. */
1444 if (cond
!= const_true_rtx
&& cond
!= const0_rtx
)
1446 predict_insn_def (insn
, PRED_BUILTIN_EXPECT
,
1447 cond
== const_true_rtx
? TAKEN
: NOT_TAKEN
);
1451 /* Check whether this is the last basic block of function. Commonly
1452 there is one extra common cleanup block. */
1454 last_basic_block_p (basic_block bb
)
1456 if (bb
== EXIT_BLOCK_PTR
)
1459 return (bb
->next_bb
== EXIT_BLOCK_PTR
1460 || (bb
->next_bb
->next_bb
== EXIT_BLOCK_PTR
1461 && EDGE_COUNT (bb
->succs
) == 1
1462 && EDGE_SUCC (bb
, 0)->dest
->next_bb
== EXIT_BLOCK_PTR
));
1465 /* Sets branch probabilities according to PREDiction and
1466 FLAGS. HEADS[bb->index] should be index of basic block in that we
1467 need to alter branch predictions (i.e. the first of our dominators
1468 such that we do not post-dominate it) (but we fill this information
1469 on demand, so -1 may be there in case this was not needed yet). */
1472 predict_paths_leading_to (basic_block bb
, int *heads
, enum br_predictor pred
,
1473 enum prediction taken
)
1479 if (heads
[bb
->index
] < 0)
1481 /* This is first time we need this field in heads array; so
1482 find first dominator that we do not post-dominate (we are
1483 using already known members of heads array). */
1484 basic_block ai
= bb
;
1485 basic_block next_ai
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1488 while (heads
[next_ai
->index
] < 0)
1490 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
1492 heads
[next_ai
->index
] = ai
->index
;
1494 next_ai
= get_immediate_dominator (CDI_DOMINATORS
, next_ai
);
1496 if (!dominated_by_p (CDI_POST_DOMINATORS
, next_ai
, bb
))
1497 head
= next_ai
->index
;
1499 head
= heads
[next_ai
->index
];
1500 while (next_ai
!= bb
)
1503 if (heads
[ai
->index
] == ENTRY_BLOCK
)
1504 ai
= ENTRY_BLOCK_PTR
;
1506 ai
= BASIC_BLOCK (heads
[ai
->index
]);
1507 heads
[next_ai
->index
] = head
;
1510 y
= heads
[bb
->index
];
1512 /* Now find the edge that leads to our branch and aply the prediction. */
1514 if (y
== last_basic_block
)
1516 FOR_EACH_EDGE (e
, ei
, BASIC_BLOCK (y
)->succs
)
1517 if (e
->dest
->index
>= 0
1518 && dominated_by_p (CDI_POST_DOMINATORS
, e
->dest
, bb
))
1519 predict_edge_def (e
, pred
, taken
);
1522 /* This is used to carry information about basic blocks. It is
1523 attached to the AUX field of the standard CFG block. */
1525 typedef struct block_info_def
1527 /* Estimated frequency of execution of basic_block. */
1530 /* To keep queue of basic blocks to process. */
1533 /* Number of predecessors we need to visit first. */
1537 /* Similar information for edges. */
1538 typedef struct edge_info_def
1540 /* In case edge is an loopback edge, the probability edge will be reached
1541 in case header is. Estimated number of iterations of the loop can be
1542 then computed as 1 / (1 - back_edge_prob). */
1543 sreal back_edge_prob
;
1544 /* True if the edge is an loopback edge in the natural loop. */
1545 unsigned int back_edge
:1;
1548 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1549 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1551 /* Helper function for estimate_bb_frequencies.
1552 Propagate the frequencies for LOOP. */
1555 propagate_freq (struct loop
*loop
, bitmap tovisit
)
1557 basic_block head
= loop
->header
;
1565 /* For each basic block we need to visit count number of his predecessors
1566 we need to visit first. */
1567 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
1572 /* The outermost "loop" includes the exit block, which we can not
1573 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1574 directly. Do the same for the entry block. */
1575 if (i
== (unsigned)ENTRY_BLOCK
)
1576 bb
= ENTRY_BLOCK_PTR
;
1577 else if (i
== (unsigned)EXIT_BLOCK
)
1578 bb
= EXIT_BLOCK_PTR
;
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 if (bitmap_bit_p (tovisit
, e
->src
->index
)
1615 && !(e
->flags
& EDGE_DFS_BACK
))
1619 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1620 if (EDGE_INFO (e
)->back_edge
)
1622 sreal_add (&cyclic_probability
, &cyclic_probability
,
1623 &EDGE_INFO (e
)->back_edge_prob
);
1625 else if (!(e
->flags
& EDGE_DFS_BACK
))
1629 /* frequency += (e->probability
1630 * BLOCK_INFO (e->src)->frequency /
1631 REG_BR_PROB_BASE); */
1633 sreal_init (&tmp
, e
->probability
, 0);
1634 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
1635 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
1636 sreal_add (&frequency
, &frequency
, &tmp
);
1639 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
1641 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
1642 sizeof (frequency
));
1646 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
1648 memcpy (&cyclic_probability
, &real_almost_one
,
1649 sizeof (real_almost_one
));
1652 /* BLOCK_INFO (bb)->frequency = frequency
1653 / (1 - cyclic_probability) */
1655 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
1656 sreal_div (&BLOCK_INFO (bb
)->frequency
,
1657 &frequency
, &cyclic_probability
);
1661 bitmap_clear_bit (tovisit
, bb
->index
);
1663 /* Compute back edge frequencies. */
1664 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1665 if (e
->dest
== head
)
1669 /* EDGE_INFO (e)->back_edge_prob
1670 = ((e->probability * BLOCK_INFO (bb)->frequency)
1671 / REG_BR_PROB_BASE); */
1673 sreal_init (&tmp
, e
->probability
, 0);
1674 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
1675 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1676 &tmp
, &real_inv_br_prob_base
);
1679 /* Propagate to successor blocks. */
1680 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1681 if (!(e
->flags
& EDGE_DFS_BACK
)
1682 && BLOCK_INFO (e
->dest
)->npredecessors
)
1684 BLOCK_INFO (e
->dest
)->npredecessors
--;
1685 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
1690 BLOCK_INFO (last
)->next
= e
->dest
;
1698 /* Estimate probabilities of loopback edges in loops at same nest level. */
1701 estimate_loops_at_level (struct loop
*first_loop
, bitmap tovisit
)
1705 for (loop
= first_loop
; loop
; loop
= loop
->next
)
1711 estimate_loops_at_level (loop
->inner
, tovisit
);
1713 /* Do not do this for dummy function loop. */
1714 if (EDGE_COUNT (loop
->latch
->succs
) > 0)
1716 /* Find current loop back edge and mark it. */
1717 e
= loop_latch_edge (loop
);
1718 EDGE_INFO (e
)->back_edge
= 1;
1721 bbs
= get_loop_body (loop
);
1722 for (i
= 0; i
< loop
->num_nodes
; i
++)
1723 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
1725 propagate_freq (loop
, tovisit
);
1729 /* Convert counts measured by profile driven feedback to frequencies.
1730 Return nonzero iff there was any nonzero execution count. */
1733 counts_to_freqs (void)
1735 gcov_type count_max
, true_count_max
= 0;
1739 true_count_max
= MAX (bb
->count
, true_count_max
);
1741 count_max
= MAX (true_count_max
, 1);
1742 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1743 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
1744 return true_count_max
;
1747 /* Return true if function is likely to be expensive, so there is no point to
1748 optimize performance of prologue, epilogue or do inlining at the expense
1749 of code size growth. THRESHOLD is the limit of number of instructions
1750 function can execute at average to be still considered not expensive. */
1753 expensive_function_p (int threshold
)
1755 unsigned int sum
= 0;
1759 /* We can not compute accurately for large thresholds due to scaled
1761 if (threshold
> BB_FREQ_MAX
)
1764 /* Frequencies are out of range. This either means that function contains
1765 internal loop executing more than BB_FREQ_MAX times or profile feedback
1766 is available and function has not been executed at all. */
1767 if (ENTRY_BLOCK_PTR
->frequency
== 0)
1770 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1771 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
1776 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
1777 insn
= NEXT_INSN (insn
))
1778 if (active_insn_p (insn
))
1780 sum
+= bb
->frequency
;
1789 /* Estimate basic blocks frequency by given branch probabilities. */
1792 estimate_bb_frequencies (struct loops
*loops
)
1797 if (!flag_branch_probabilities
|| !counts_to_freqs ())
1799 static int real_values_initialized
= 0;
1802 if (!real_values_initialized
)
1804 real_values_initialized
= 1;
1805 sreal_init (&real_zero
, 0, 0);
1806 sreal_init (&real_one
, 1, 0);
1807 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
1808 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
1809 sreal_init (&real_one_half
, 1, -1);
1810 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
1811 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
1814 mark_dfs_back_edges ();
1816 EDGE_SUCC (ENTRY_BLOCK_PTR
, 0)->probability
= REG_BR_PROB_BASE
;
1818 /* Set up block info for each basic block. */
1819 tovisit
= BITMAP_XMALLOC ();
1820 alloc_aux_for_blocks (sizeof (struct block_info_def
));
1821 alloc_aux_for_edges (sizeof (struct edge_info_def
));
1822 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1827 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1829 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
1830 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1831 &EDGE_INFO (e
)->back_edge_prob
,
1832 &real_inv_br_prob_base
);
1836 /* First compute probabilities locally for each loop from innermost
1837 to outermost to examine probabilities for back edges. */
1838 estimate_loops_at_level (loops
->tree_root
, tovisit
);
1840 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
1842 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
1843 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
1845 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
1846 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1850 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
1851 sreal_add (&tmp
, &tmp
, &real_one_half
);
1852 bb
->frequency
= sreal_to_int (&tmp
);
1855 free_aux_for_blocks ();
1856 free_aux_for_edges ();
1857 BITMAP_XFREE (tovisit
);
1859 compute_function_frequency ();
1860 if (flag_reorder_functions
)
1861 choose_function_section ();
1864 /* Decide whether function is hot, cold or unlikely executed. */
1866 compute_function_frequency (void)
1870 if (!profile_info
|| !flag_branch_probabilities
)
1872 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
1875 if (maybe_hot_bb_p (bb
))
1877 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
1880 if (!probably_never_executed_bb_p (bb
))
1881 cfun
->function_frequency
= FUNCTION_FREQUENCY_NORMAL
;
1885 /* Choose appropriate section for the function. */
1887 choose_function_section (void)
1889 if (DECL_SECTION_NAME (current_function_decl
)
1890 || !targetm
.have_named_sections
1891 /* Theoretically we can split the gnu.linkonce text section too,
1892 but this requires more work as the frequency needs to match
1893 for all generated objects so we need to merge the frequency
1894 of all instances. For now just never set frequency for these. */
1895 || DECL_ONE_ONLY (current_function_decl
))
1898 /* If we are doing the partitioning optimization, let the optimization
1899 choose the correct section into which to put things. */
1901 if (flag_reorder_blocks_and_partition
)
1904 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
1905 DECL_SECTION_NAME (current_function_decl
) =
1906 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
1907 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
1908 DECL_SECTION_NAME (current_function_decl
) =
1909 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
1910 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);
1914 struct tree_opt_pass pass_profile
=
1916 "profile", /* name */
1918 tree_estimate_probability
, /* execute */
1921 0, /* static_pass_number */
1922 TV_BRANCH_PROB
, /* tv_id */
1923 PROP_cfg
, /* properties_required */
1924 0, /* properties_provided */
1925 0, /* properties_destroyed */
1926 0, /* todo_flags_start */
1927 TODO_ggc_collect
| TODO_verify_ssa
, /* todo_flags_finish */