Daily bump.
[official-gcc.git] / gcc / predict.c
blob0cf6b9606bc3b5355f10218db4495f6f328f36ee
1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* References:
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. */
31 #include "config.h"
32 #include "system.h"
33 #include "coretypes.h"
34 #include "tm.h"
35 #include "tree.h"
36 #include "rtl.h"
37 #include "tm_p.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
41 #include "regs.h"
42 #include "flags.h"
43 #include "output.h"
44 #include "function.h"
45 #include "except.h"
46 #include "toplev.h"
47 #include "recog.h"
48 #include "expr.h"
49 #include "predict.h"
50 #include "coverage.h"
51 #include "sreal.h"
52 #include "params.h"
53 #include "target.h"
54 #include "cfgloop.h"
55 #include "tree-flow.h"
56 #include "ggc.h"
57 #include "tree-dump.h"
58 #include "tree-pass.h"
59 #include "timevar.h"
60 #include "tree-scalar-evolution.h"
61 #include "cfgloop.h"
62 #include "pointer-set.h"
64 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
65 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
66 static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
67 real_inv_br_prob_base, real_one_half, real_bb_freq_max;
69 /* Random guesstimation given names. */
70 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 100 - 1)
71 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
72 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
73 #define PROB_ALWAYS (REG_BR_PROB_BASE)
75 static void combine_predictions_for_insn (rtx, basic_block);
76 static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
77 static void predict_paths_leading_to (basic_block, int *, enum br_predictor, enum prediction);
78 static void compute_function_frequency (void);
79 static void choose_function_section (void);
80 static bool can_predict_insn_p (const_rtx);
82 /* Information we hold about each branch predictor.
83 Filled using information from predict.def. */
85 struct predictor_info
87 const char *const name; /* Name used in the debugging dumps. */
88 const int hitrate; /* Expected hitrate used by
89 predict_insn_def call. */
90 const int flags;
93 /* Use given predictor without Dempster-Shaffer theory if it matches
94 using first_match heuristics. */
95 #define PRED_FLAG_FIRST_MATCH 1
97 /* Recompute hitrate in percent to our representation. */
99 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
101 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
102 static const struct predictor_info predictor_info[]= {
103 #include "predict.def"
105 /* Upper bound on predictors. */
106 {NULL, 0, 0}
108 #undef DEF_PREDICTOR
110 /* Return true in case BB can be CPU intensive and should be optimized
111 for maximal performance. */
113 bool
114 maybe_hot_bb_p (const_basic_block bb)
116 if (profile_info && flag_branch_probabilities
117 && (bb->count
118 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
119 return false;
120 if (!profile_info || !flag_branch_probabilities)
122 if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
123 return false;
124 if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
125 return true;
127 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
128 return false;
129 return true;
132 /* Return true in case BB is cold and should be optimized for size. */
134 bool
135 probably_cold_bb_p (const_basic_block bb)
137 if (profile_info && flag_branch_probabilities
138 && (bb->count
139 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
140 return true;
141 if ((!profile_info || !flag_branch_probabilities)
142 && cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
143 return true;
144 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
145 return true;
146 return false;
149 /* Return true in case BB is probably never executed. */
150 bool
151 probably_never_executed_bb_p (const_basic_block bb)
153 if (profile_info && flag_branch_probabilities)
154 return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
155 if ((!profile_info || !flag_branch_probabilities)
156 && cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
157 return true;
158 return false;
161 /* Return true if the one of outgoing edges is already predicted by
162 PREDICTOR. */
164 bool
165 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
167 rtx note;
168 if (!INSN_P (BB_END (bb)))
169 return false;
170 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
171 if (REG_NOTE_KIND (note) == REG_BR_PRED
172 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
173 return true;
174 return false;
177 /* This map contains for a basic block the list of predictions for the
178 outgoing edges. */
180 static struct pointer_map_t *bb_predictions;
182 /* Return true if the one of outgoing edges is already predicted by
183 PREDICTOR. */
185 bool
186 tree_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
188 struct edge_prediction *i;
189 void **preds = pointer_map_contains (bb_predictions, bb);
191 if (!preds)
192 return false;
194 for (i = *preds; i; i = i->ep_next)
195 if (i->ep_predictor == predictor)
196 return true;
197 return false;
200 /* Return true when the probability of edge is reliable.
202 The profile guessing code is good at predicting branch outcome (ie.
203 taken/not taken), that is predicted right slightly over 75% of time.
204 It is however notoriously poor on predicting the probability itself.
205 In general the profile appear a lot flatter (with probabilities closer
206 to 50%) than the reality so it is bad idea to use it to drive optimization
207 such as those disabling dynamic branch prediction for well predictable
208 branches.
210 There are two exceptions - edges leading to noreturn edges and edges
211 predicted by number of iterations heuristics are predicted well. This macro
212 should be able to distinguish those, but at the moment it simply check for
213 noreturn heuristic that is only one giving probability over 99% or bellow
214 1%. In future we might want to propagate reliability information across the
215 CFG if we find this information useful on multiple places. */
216 static bool
217 probability_reliable_p (int prob)
219 return (profile_status == PROFILE_READ
220 || (profile_status == PROFILE_GUESSED
221 && (prob <= HITRATE (1) || prob >= HITRATE (99))));
224 /* Same predicate as above, working on edges. */
225 bool
226 edge_probability_reliable_p (const_edge e)
228 return probability_reliable_p (e->probability);
231 /* Same predicate as edge_probability_reliable_p, working on notes. */
232 bool
233 br_prob_note_reliable_p (const_rtx note)
235 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
236 return probability_reliable_p (INTVAL (XEXP (note, 0)));
239 static void
240 predict_insn (rtx insn, enum br_predictor predictor, int probability)
242 gcc_assert (any_condjump_p (insn));
243 if (!flag_guess_branch_prob)
244 return;
246 REG_NOTES (insn)
247 = gen_rtx_EXPR_LIST (REG_BR_PRED,
248 gen_rtx_CONCAT (VOIDmode,
249 GEN_INT ((int) predictor),
250 GEN_INT ((int) probability)),
251 REG_NOTES (insn));
254 /* Predict insn by given predictor. */
256 void
257 predict_insn_def (rtx insn, enum br_predictor predictor,
258 enum prediction taken)
260 int probability = predictor_info[(int) predictor].hitrate;
262 if (taken != TAKEN)
263 probability = REG_BR_PROB_BASE - probability;
265 predict_insn (insn, predictor, probability);
268 /* Predict edge E with given probability if possible. */
270 void
271 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
273 rtx last_insn;
274 last_insn = BB_END (e->src);
276 /* We can store the branch prediction information only about
277 conditional jumps. */
278 if (!any_condjump_p (last_insn))
279 return;
281 /* We always store probability of branching. */
282 if (e->flags & EDGE_FALLTHRU)
283 probability = REG_BR_PROB_BASE - probability;
285 predict_insn (last_insn, predictor, probability);
288 /* Predict edge E with the given PROBABILITY. */
289 void
290 tree_predict_edge (edge e, enum br_predictor predictor, int probability)
292 gcc_assert (profile_status != PROFILE_GUESSED);
293 if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
294 && flag_guess_branch_prob && optimize)
296 struct edge_prediction *i = XNEW (struct edge_prediction);
297 void **preds = pointer_map_insert (bb_predictions, e->src);
299 i->ep_next = *preds;
300 *preds = i;
301 i->ep_probability = probability;
302 i->ep_predictor = predictor;
303 i->ep_edge = e;
307 /* Remove all predictions on given basic block that are attached
308 to edge E. */
309 void
310 remove_predictions_associated_with_edge (edge e)
312 void **preds;
314 if (!bb_predictions)
315 return;
317 preds = pointer_map_contains (bb_predictions, e->src);
319 if (preds)
321 struct edge_prediction **prediction = (struct edge_prediction **) preds;
322 struct edge_prediction *next;
324 while (*prediction)
326 if ((*prediction)->ep_edge == e)
328 next = (*prediction)->ep_next;
329 free (*prediction);
330 *prediction = next;
332 else
333 prediction = &((*prediction)->ep_next);
338 /* Clears the list of predictions stored for BB. */
340 static void
341 clear_bb_predictions (basic_block bb)
343 void **preds = pointer_map_contains (bb_predictions, bb);
344 struct edge_prediction *pred, *next;
346 if (!preds)
347 return;
349 for (pred = *preds; pred; pred = next)
351 next = pred->ep_next;
352 free (pred);
354 *preds = NULL;
357 /* Return true when we can store prediction on insn INSN.
358 At the moment we represent predictions only on conditional
359 jumps, not at computed jump or other complicated cases. */
360 static bool
361 can_predict_insn_p (const_rtx insn)
363 return (JUMP_P (insn)
364 && any_condjump_p (insn)
365 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
368 /* Predict edge E by given predictor if possible. */
370 void
371 predict_edge_def (edge e, enum br_predictor predictor,
372 enum prediction taken)
374 int probability = predictor_info[(int) predictor].hitrate;
376 if (taken != TAKEN)
377 probability = REG_BR_PROB_BASE - probability;
379 predict_edge (e, predictor, probability);
382 /* Invert all branch predictions or probability notes in the INSN. This needs
383 to be done each time we invert the condition used by the jump. */
385 void
386 invert_br_probabilities (rtx insn)
388 rtx note;
390 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
391 if (REG_NOTE_KIND (note) == REG_BR_PROB)
392 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
393 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
394 XEXP (XEXP (note, 0), 1)
395 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
398 /* Dump information about the branch prediction to the output file. */
400 static void
401 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
402 basic_block bb, int used)
404 edge e;
405 edge_iterator ei;
407 if (!file)
408 return;
410 FOR_EACH_EDGE (e, ei, bb->succs)
411 if (! (e->flags & EDGE_FALLTHRU))
412 break;
414 fprintf (file, " %s heuristics%s: %.1f%%",
415 predictor_info[predictor].name,
416 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
418 if (bb->count)
420 fprintf (file, " exec ");
421 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
422 if (e)
424 fprintf (file, " hit ");
425 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
426 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
430 fprintf (file, "\n");
433 /* We can not predict the probabilities of outgoing edges of bb. Set them
434 evenly and hope for the best. */
435 static void
436 set_even_probabilities (basic_block bb)
438 int nedges = 0;
439 edge e;
440 edge_iterator ei;
442 FOR_EACH_EDGE (e, ei, bb->succs)
443 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
444 nedges ++;
445 FOR_EACH_EDGE (e, ei, bb->succs)
446 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
447 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
448 else
449 e->probability = 0;
452 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
453 note if not already present. Remove now useless REG_BR_PRED notes. */
455 static void
456 combine_predictions_for_insn (rtx insn, basic_block bb)
458 rtx prob_note;
459 rtx *pnote;
460 rtx note;
461 int best_probability = PROB_EVEN;
462 int best_predictor = END_PREDICTORS;
463 int combined_probability = REG_BR_PROB_BASE / 2;
464 int d;
465 bool first_match = false;
466 bool found = false;
468 if (!can_predict_insn_p (insn))
470 set_even_probabilities (bb);
471 return;
474 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
475 pnote = &REG_NOTES (insn);
476 if (dump_file)
477 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
478 bb->index);
480 /* We implement "first match" heuristics and use probability guessed
481 by predictor with smallest index. */
482 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
483 if (REG_NOTE_KIND (note) == REG_BR_PRED)
485 int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
486 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
488 found = true;
489 if (best_predictor > predictor)
490 best_probability = probability, best_predictor = predictor;
492 d = (combined_probability * probability
493 + (REG_BR_PROB_BASE - combined_probability)
494 * (REG_BR_PROB_BASE - probability));
496 /* Use FP math to avoid overflows of 32bit integers. */
497 if (d == 0)
498 /* If one probability is 0% and one 100%, avoid division by zero. */
499 combined_probability = REG_BR_PROB_BASE / 2;
500 else
501 combined_probability = (((double) combined_probability) * probability
502 * REG_BR_PROB_BASE / d + 0.5);
505 /* Decide which heuristic to use. In case we didn't match anything,
506 use no_prediction heuristic, in case we did match, use either
507 first match or Dempster-Shaffer theory depending on the flags. */
509 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
510 first_match = true;
512 if (!found)
513 dump_prediction (dump_file, PRED_NO_PREDICTION,
514 combined_probability, bb, true);
515 else
517 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
518 bb, !first_match);
519 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
520 bb, first_match);
523 if (first_match)
524 combined_probability = best_probability;
525 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
527 while (*pnote)
529 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
531 int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
532 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
534 dump_prediction (dump_file, predictor, probability, bb,
535 !first_match || best_predictor == predictor);
536 *pnote = XEXP (*pnote, 1);
538 else
539 pnote = &XEXP (*pnote, 1);
542 if (!prob_note)
544 REG_NOTES (insn)
545 = gen_rtx_EXPR_LIST (REG_BR_PROB,
546 GEN_INT (combined_probability), REG_NOTES (insn));
548 /* Save the prediction into CFG in case we are seeing non-degenerated
549 conditional jump. */
550 if (!single_succ_p (bb))
552 BRANCH_EDGE (bb)->probability = combined_probability;
553 FALLTHRU_EDGE (bb)->probability
554 = REG_BR_PROB_BASE - combined_probability;
557 else if (!single_succ_p (bb))
559 int prob = INTVAL (XEXP (prob_note, 0));
561 BRANCH_EDGE (bb)->probability = prob;
562 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
564 else
565 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
568 /* Combine predictions into single probability and store them into CFG.
569 Remove now useless prediction entries. */
571 static void
572 combine_predictions_for_bb (basic_block bb)
574 int best_probability = PROB_EVEN;
575 int best_predictor = END_PREDICTORS;
576 int combined_probability = REG_BR_PROB_BASE / 2;
577 int d;
578 bool first_match = false;
579 bool found = false;
580 struct edge_prediction *pred;
581 int nedges = 0;
582 edge e, first = NULL, second = NULL;
583 edge_iterator ei;
584 void **preds;
586 FOR_EACH_EDGE (e, ei, bb->succs)
587 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
589 nedges ++;
590 if (first && !second)
591 second = e;
592 if (!first)
593 first = e;
596 /* When there is no successor or only one choice, prediction is easy.
598 We are lazy for now and predict only basic blocks with two outgoing
599 edges. It is possible to predict generic case too, but we have to
600 ignore first match heuristics and do more involved combining. Implement
601 this later. */
602 if (nedges != 2)
604 if (!bb->count)
605 set_even_probabilities (bb);
606 clear_bb_predictions (bb);
607 if (dump_file)
608 fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
609 nedges, bb->index);
610 return;
613 if (dump_file)
614 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
616 preds = pointer_map_contains (bb_predictions, bb);
617 if (preds)
619 /* We implement "first match" heuristics and use probability guessed
620 by predictor with smallest index. */
621 for (pred = *preds; pred; pred = pred->ep_next)
623 int predictor = pred->ep_predictor;
624 int probability = pred->ep_probability;
626 if (pred->ep_edge != first)
627 probability = REG_BR_PROB_BASE - probability;
629 found = true;
630 if (best_predictor > predictor)
631 best_probability = probability, best_predictor = predictor;
633 d = (combined_probability * probability
634 + (REG_BR_PROB_BASE - combined_probability)
635 * (REG_BR_PROB_BASE - probability));
637 /* Use FP math to avoid overflows of 32bit integers. */
638 if (d == 0)
639 /* If one probability is 0% and one 100%, avoid division by zero. */
640 combined_probability = REG_BR_PROB_BASE / 2;
641 else
642 combined_probability = (((double) combined_probability)
643 * probability
644 * REG_BR_PROB_BASE / d + 0.5);
648 /* Decide which heuristic to use. In case we didn't match anything,
649 use no_prediction heuristic, in case we did match, use either
650 first match or Dempster-Shaffer theory depending on the flags. */
652 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
653 first_match = true;
655 if (!found)
656 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
657 else
659 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
660 !first_match);
661 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
662 first_match);
665 if (first_match)
666 combined_probability = best_probability;
667 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
669 if (preds)
671 for (pred = *preds; pred; pred = pred->ep_next)
673 int predictor = pred->ep_predictor;
674 int probability = pred->ep_probability;
676 if (pred->ep_edge != EDGE_SUCC (bb, 0))
677 probability = REG_BR_PROB_BASE - probability;
678 dump_prediction (dump_file, predictor, probability, bb,
679 !first_match || best_predictor == predictor);
682 clear_bb_predictions (bb);
684 if (!bb->count)
686 first->probability = combined_probability;
687 second->probability = REG_BR_PROB_BASE - combined_probability;
691 /* Predict edge probabilities by exploiting loop structure. */
693 static void
694 predict_loops (void)
696 loop_iterator li;
697 struct loop *loop;
699 scev_initialize ();
701 /* Try to predict out blocks in a loop that are not part of a
702 natural loop. */
703 FOR_EACH_LOOP (li, loop, 0)
705 basic_block bb, *bbs;
706 unsigned j, n_exits;
707 VEC (edge, heap) *exits;
708 struct tree_niter_desc niter_desc;
709 edge ex;
711 exits = get_loop_exit_edges (loop);
712 n_exits = VEC_length (edge, exits);
714 for (j = 0; VEC_iterate (edge, exits, j, ex); j++)
716 tree niter = NULL;
717 HOST_WIDE_INT nitercst;
718 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
719 int probability;
720 enum br_predictor predictor;
722 if (number_of_iterations_exit (loop, ex, &niter_desc, false))
723 niter = niter_desc.niter;
724 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
725 niter = loop_niter_by_eval (loop, ex);
727 if (TREE_CODE (niter) == INTEGER_CST)
729 if (host_integerp (niter, 1)
730 && compare_tree_int (niter, max-1) == -1)
731 nitercst = tree_low_cst (niter, 1) + 1;
732 else
733 nitercst = max;
734 predictor = PRED_LOOP_ITERATIONS;
736 /* If we have just one exit and we can derive some information about
737 the number of iterations of the loop from the statements inside
738 the loop, use it to predict this exit. */
739 else if (n_exits == 1)
741 nitercst = estimated_loop_iterations_int (loop, false);
742 if (nitercst < 0)
743 continue;
744 if (nitercst > max)
745 nitercst = max;
747 predictor = PRED_LOOP_ITERATIONS_GUESSED;
749 else
750 continue;
752 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
753 predict_edge (ex, predictor, probability);
755 VEC_free (edge, heap, exits);
757 bbs = get_loop_body (loop);
759 for (j = 0; j < loop->num_nodes; j++)
761 int header_found = 0;
762 edge e;
763 edge_iterator ei;
765 bb = bbs[j];
767 /* Bypass loop heuristics on continue statement. These
768 statements construct loops via "non-loop" constructs
769 in the source language and are better to be handled
770 separately. */
771 if (predicted_by_p (bb, PRED_CONTINUE))
772 continue;
774 /* Loop branch heuristics - predict an edge back to a
775 loop's head as taken. */
776 if (bb == loop->latch)
778 e = find_edge (loop->latch, loop->header);
779 if (e)
781 header_found = 1;
782 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
786 /* Loop exit heuristics - predict an edge exiting the loop if the
787 conditional has no loop header successors as not taken. */
788 if (!header_found
789 /* If we already used more reliable loop exit predictors, do not
790 bother with PRED_LOOP_EXIT. */
791 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
792 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
794 /* For loop with many exits we don't want to predict all exits
795 with the pretty large probability, because if all exits are
796 considered in row, the loop would be predicted to iterate
797 almost never. The code to divide probability by number of
798 exits is very rough. It should compute the number of exits
799 taken in each patch through function (not the overall number
800 of exits that might be a lot higher for loops with wide switch
801 statements in them) and compute n-th square root.
803 We limit the minimal probability by 2% to avoid
804 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
805 as this was causing regression in perl benchmark containing such
806 a wide loop. */
808 int probability = ((REG_BR_PROB_BASE
809 - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
810 / n_exits);
811 if (probability < HITRATE (2))
812 probability = HITRATE (2);
813 FOR_EACH_EDGE (e, ei, bb->succs)
814 if (e->dest->index < NUM_FIXED_BLOCKS
815 || !flow_bb_inside_loop_p (loop, e->dest))
816 predict_edge (e, PRED_LOOP_EXIT, probability);
820 /* Free basic blocks from get_loop_body. */
821 free (bbs);
824 scev_finalize ();
827 /* Attempt to predict probabilities of BB outgoing edges using local
828 properties. */
829 static void
830 bb_estimate_probability_locally (basic_block bb)
832 rtx last_insn = BB_END (bb);
833 rtx cond;
835 if (! can_predict_insn_p (last_insn))
836 return;
837 cond = get_condition (last_insn, NULL, false, false);
838 if (! cond)
839 return;
841 /* Try "pointer heuristic."
842 A comparison ptr == 0 is predicted as false.
843 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
844 if (COMPARISON_P (cond)
845 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
846 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
848 if (GET_CODE (cond) == EQ)
849 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
850 else if (GET_CODE (cond) == NE)
851 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
853 else
855 /* Try "opcode heuristic."
856 EQ tests are usually false and NE tests are usually true. Also,
857 most quantities are positive, so we can make the appropriate guesses
858 about signed comparisons against zero. */
859 switch (GET_CODE (cond))
861 case CONST_INT:
862 /* Unconditional branch. */
863 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
864 cond == const0_rtx ? NOT_TAKEN : TAKEN);
865 break;
867 case EQ:
868 case UNEQ:
869 /* Floating point comparisons appears to behave in a very
870 unpredictable way because of special role of = tests in
871 FP code. */
872 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
874 /* Comparisons with 0 are often used for booleans and there is
875 nothing useful to predict about them. */
876 else if (XEXP (cond, 1) == const0_rtx
877 || XEXP (cond, 0) == const0_rtx)
879 else
880 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
881 break;
883 case NE:
884 case LTGT:
885 /* Floating point comparisons appears to behave in a very
886 unpredictable way because of special role of = tests in
887 FP code. */
888 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
890 /* Comparisons with 0 are often used for booleans and there is
891 nothing useful to predict about them. */
892 else if (XEXP (cond, 1) == const0_rtx
893 || XEXP (cond, 0) == const0_rtx)
895 else
896 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
897 break;
899 case ORDERED:
900 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
901 break;
903 case UNORDERED:
904 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
905 break;
907 case LE:
908 case LT:
909 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
910 || XEXP (cond, 1) == constm1_rtx)
911 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
912 break;
914 case GE:
915 case GT:
916 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
917 || XEXP (cond, 1) == constm1_rtx)
918 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
919 break;
921 default:
922 break;
926 /* Set edge->probability for each successor edge of BB. */
927 void
928 guess_outgoing_edge_probabilities (basic_block bb)
930 bb_estimate_probability_locally (bb);
931 combine_predictions_for_insn (BB_END (bb), bb);
934 /* Return constant EXPR will likely have at execution time, NULL if unknown.
935 The function is used by builtin_expect branch predictor so the evidence
936 must come from this construct and additional possible constant folding.
938 We may want to implement more involved value guess (such as value range
939 propagation based prediction), but such tricks shall go to new
940 implementation. */
942 static tree
943 expr_expected_value (tree expr, bitmap visited)
945 if (TREE_CONSTANT (expr))
946 return expr;
947 else if (TREE_CODE (expr) == SSA_NAME)
949 tree def = SSA_NAME_DEF_STMT (expr);
951 /* If we were already here, break the infinite cycle. */
952 if (bitmap_bit_p (visited, SSA_NAME_VERSION (expr)))
953 return NULL;
954 bitmap_set_bit (visited, SSA_NAME_VERSION (expr));
956 if (TREE_CODE (def) == PHI_NODE)
958 /* All the arguments of the PHI node must have the same constant
959 length. */
960 int i;
961 tree val = NULL, new_val;
963 for (i = 0; i < PHI_NUM_ARGS (def); i++)
965 tree arg = PHI_ARG_DEF (def, i);
967 /* If this PHI has itself as an argument, we cannot
968 determine the string length of this argument. However,
969 if we can find an expected constant value for the other
970 PHI args then we can still be sure that this is
971 likely a constant. So be optimistic and just
972 continue with the next argument. */
973 if (arg == PHI_RESULT (def))
974 continue;
976 new_val = expr_expected_value (arg, visited);
977 if (!new_val)
978 return NULL;
979 if (!val)
980 val = new_val;
981 else if (!operand_equal_p (val, new_val, false))
982 return NULL;
984 return val;
986 if (TREE_CODE (def) != GIMPLE_MODIFY_STMT
987 || GIMPLE_STMT_OPERAND (def, 0) != expr)
988 return NULL;
989 return expr_expected_value (GIMPLE_STMT_OPERAND (def, 1), visited);
991 else if (TREE_CODE (expr) == CALL_EXPR)
993 tree decl = get_callee_fndecl (expr);
994 if (!decl)
995 return NULL;
996 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
997 && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
999 tree val;
1001 if (call_expr_nargs (expr) != 2)
1002 return NULL;
1003 val = CALL_EXPR_ARG (expr, 0);
1004 if (TREE_CONSTANT (val))
1005 return val;
1006 return CALL_EXPR_ARG (expr, 1);
1009 if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
1011 tree op0, op1, res;
1012 op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited);
1013 if (!op0)
1014 return NULL;
1015 op1 = expr_expected_value (TREE_OPERAND (expr, 1), visited);
1016 if (!op1)
1017 return NULL;
1018 res = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr), op0, op1);
1019 if (TREE_CONSTANT (res))
1020 return res;
1021 return NULL;
1023 if (UNARY_CLASS_P (expr))
1025 tree op0, res;
1026 op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited);
1027 if (!op0)
1028 return NULL;
1029 res = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr), op0);
1030 if (TREE_CONSTANT (res))
1031 return res;
1032 return NULL;
1034 return NULL;
1037 /* Get rid of all builtin_expect calls we no longer need. */
1038 static void
1039 strip_builtin_expect (void)
1041 basic_block bb;
1042 FOR_EACH_BB (bb)
1044 block_stmt_iterator bi;
1045 for (bi = bsi_start (bb); !bsi_end_p (bi); bsi_next (&bi))
1047 tree stmt = bsi_stmt (bi);
1048 tree fndecl;
1049 tree call;
1051 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1052 && (call = GIMPLE_STMT_OPERAND (stmt, 1))
1053 && TREE_CODE (call) == CALL_EXPR
1054 && (fndecl = get_callee_fndecl (call))
1055 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1056 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
1057 && call_expr_nargs (call) == 2)
1059 GIMPLE_STMT_OPERAND (stmt, 1) = CALL_EXPR_ARG (call, 0);
1060 update_stmt (stmt);
1066 /* Predict using opcode of the last statement in basic block. */
1067 static void
1068 tree_predict_by_opcode (basic_block bb)
1070 tree stmt = last_stmt (bb);
1071 edge then_edge;
1072 tree cond;
1073 tree op0;
1074 tree type;
1075 tree val;
1076 bitmap visited;
1077 edge_iterator ei;
1079 if (!stmt || TREE_CODE (stmt) != COND_EXPR)
1080 return;
1081 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1082 if (then_edge->flags & EDGE_TRUE_VALUE)
1083 break;
1084 cond = TREE_OPERAND (stmt, 0);
1085 if (!COMPARISON_CLASS_P (cond))
1086 return;
1087 op0 = TREE_OPERAND (cond, 0);
1088 type = TREE_TYPE (op0);
1089 visited = BITMAP_ALLOC (NULL);
1090 val = expr_expected_value (cond, visited);
1091 BITMAP_FREE (visited);
1092 if (val)
1094 if (integer_zerop (val))
1095 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1096 else
1097 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1098 return;
1100 /* Try "pointer heuristic."
1101 A comparison ptr == 0 is predicted as false.
1102 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1103 if (POINTER_TYPE_P (type))
1105 if (TREE_CODE (cond) == EQ_EXPR)
1106 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1107 else if (TREE_CODE (cond) == NE_EXPR)
1108 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1110 else
1112 /* Try "opcode heuristic."
1113 EQ tests are usually false and NE tests are usually true. Also,
1114 most quantities are positive, so we can make the appropriate guesses
1115 about signed comparisons against zero. */
1116 switch (TREE_CODE (cond))
1118 case EQ_EXPR:
1119 case UNEQ_EXPR:
1120 /* Floating point comparisons appears to behave in a very
1121 unpredictable way because of special role of = tests in
1122 FP code. */
1123 if (FLOAT_TYPE_P (type))
1125 /* Comparisons with 0 are often used for booleans and there is
1126 nothing useful to predict about them. */
1127 else if (integer_zerop (op0)
1128 || integer_zerop (TREE_OPERAND (cond, 1)))
1130 else
1131 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1132 break;
1134 case NE_EXPR:
1135 case LTGT_EXPR:
1136 /* Floating point comparisons appears to behave in a very
1137 unpredictable way because of special role of = tests in
1138 FP code. */
1139 if (FLOAT_TYPE_P (type))
1141 /* Comparisons with 0 are often used for booleans and there is
1142 nothing useful to predict about them. */
1143 else if (integer_zerop (op0)
1144 || integer_zerop (TREE_OPERAND (cond, 1)))
1146 else
1147 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1148 break;
1150 case ORDERED_EXPR:
1151 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1152 break;
1154 case UNORDERED_EXPR:
1155 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1156 break;
1158 case LE_EXPR:
1159 case LT_EXPR:
1160 if (integer_zerop (TREE_OPERAND (cond, 1))
1161 || integer_onep (TREE_OPERAND (cond, 1))
1162 || integer_all_onesp (TREE_OPERAND (cond, 1))
1163 || real_zerop (TREE_OPERAND (cond, 1))
1164 || real_onep (TREE_OPERAND (cond, 1))
1165 || real_minus_onep (TREE_OPERAND (cond, 1)))
1166 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1167 break;
1169 case GE_EXPR:
1170 case GT_EXPR:
1171 if (integer_zerop (TREE_OPERAND (cond, 1))
1172 || integer_onep (TREE_OPERAND (cond, 1))
1173 || integer_all_onesp (TREE_OPERAND (cond, 1))
1174 || real_zerop (TREE_OPERAND (cond, 1))
1175 || real_onep (TREE_OPERAND (cond, 1))
1176 || real_minus_onep (TREE_OPERAND (cond, 1)))
1177 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1178 break;
1180 default:
1181 break;
1185 /* Try to guess whether the value of return means error code. */
1186 static enum br_predictor
1187 return_prediction (tree val, enum prediction *prediction)
1189 /* VOID. */
1190 if (!val)
1191 return PRED_NO_PREDICTION;
1192 /* Different heuristics for pointers and scalars. */
1193 if (POINTER_TYPE_P (TREE_TYPE (val)))
1195 /* NULL is usually not returned. */
1196 if (integer_zerop (val))
1198 *prediction = NOT_TAKEN;
1199 return PRED_NULL_RETURN;
1202 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1204 /* Negative return values are often used to indicate
1205 errors. */
1206 if (TREE_CODE (val) == INTEGER_CST
1207 && tree_int_cst_sgn (val) < 0)
1209 *prediction = NOT_TAKEN;
1210 return PRED_NEGATIVE_RETURN;
1212 /* Constant return values seems to be commonly taken.
1213 Zero/one often represent booleans so exclude them from the
1214 heuristics. */
1215 if (TREE_CONSTANT (val)
1216 && (!integer_zerop (val) && !integer_onep (val)))
1218 *prediction = TAKEN;
1219 return PRED_CONST_RETURN;
1222 return PRED_NO_PREDICTION;
1225 /* Find the basic block with return expression and look up for possible
1226 return value trying to apply RETURN_PREDICTION heuristics. */
1227 static void
1228 apply_return_prediction (int *heads)
1230 tree return_stmt = NULL;
1231 tree return_val;
1232 edge e;
1233 tree phi;
1234 int phi_num_args, i;
1235 enum br_predictor pred;
1236 enum prediction direction;
1237 edge_iterator ei;
1239 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1241 return_stmt = last_stmt (e->src);
1242 if (return_stmt
1243 && TREE_CODE (return_stmt) == RETURN_EXPR)
1244 break;
1246 if (!e)
1247 return;
1248 return_val = TREE_OPERAND (return_stmt, 0);
1249 if (!return_val)
1250 return;
1251 if (TREE_CODE (return_val) == GIMPLE_MODIFY_STMT)
1252 return_val = GIMPLE_STMT_OPERAND (return_val, 1);
1253 if (TREE_CODE (return_val) != SSA_NAME
1254 || !SSA_NAME_DEF_STMT (return_val)
1255 || TREE_CODE (SSA_NAME_DEF_STMT (return_val)) != PHI_NODE)
1256 return;
1257 for (phi = SSA_NAME_DEF_STMT (return_val); phi; phi = PHI_CHAIN (phi))
1258 if (PHI_RESULT (phi) == return_val)
1259 break;
1260 if (!phi)
1261 return;
1262 phi_num_args = PHI_NUM_ARGS (phi);
1263 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1265 /* Avoid the degenerate case where all return values form the function
1266 belongs to same category (ie they are all positive constants)
1267 so we can hardly say something about them. */
1268 for (i = 1; i < phi_num_args; i++)
1269 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1270 break;
1271 if (i != phi_num_args)
1272 for (i = 0; i < phi_num_args; i++)
1274 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1275 if (pred != PRED_NO_PREDICTION)
1276 predict_paths_leading_to (PHI_ARG_EDGE (phi, i)->src, heads, pred,
1277 direction);
1281 /* Look for basic block that contains unlikely to happen events
1282 (such as noreturn calls) and mark all paths leading to execution
1283 of this basic blocks as unlikely. */
1285 static void
1286 tree_bb_level_predictions (void)
1288 basic_block bb;
1289 int *heads;
1291 heads = XCNEWVEC (int, last_basic_block);
1292 heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
1294 apply_return_prediction (heads);
1296 FOR_EACH_BB (bb)
1298 block_stmt_iterator bsi = bsi_last (bb);
1300 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1302 tree stmt = bsi_stmt (bsi);
1303 tree decl;
1304 switch (TREE_CODE (stmt))
1306 case GIMPLE_MODIFY_STMT:
1307 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CALL_EXPR)
1309 stmt = GIMPLE_STMT_OPERAND (stmt, 1);
1310 goto call_expr;
1312 break;
1313 case CALL_EXPR:
1314 call_expr:;
1315 if (call_expr_flags (stmt) & ECF_NORETURN)
1316 predict_paths_leading_to (bb, heads, PRED_NORETURN,
1317 NOT_TAKEN);
1318 decl = get_callee_fndecl (stmt);
1319 if (decl
1320 && lookup_attribute ("cold",
1321 DECL_ATTRIBUTES (decl)))
1322 predict_paths_leading_to (bb, heads, PRED_COLD_FUNCTION,
1323 NOT_TAKEN);
1324 break;
1325 default:
1326 break;
1331 free (heads);
1334 #ifdef ENABLE_CHECKING
1336 /* Callback for pointer_map_traverse, asserts that the pointer map is
1337 empty. */
1339 static bool
1340 assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
1341 void *data ATTRIBUTE_UNUSED)
1343 gcc_assert (!*value);
1344 return false;
1346 #endif
1348 /* Predict branch probabilities and estimate profile of the tree CFG. */
1349 static unsigned int
1350 tree_estimate_probability (void)
1352 basic_block bb;
1354 loop_optimizer_init (0);
1355 if (dump_file && (dump_flags & TDF_DETAILS))
1356 flow_loops_dump (dump_file, NULL, 0);
1358 add_noreturn_fake_exit_edges ();
1359 connect_infinite_loops_to_exit ();
1360 /* We use loop_niter_by_eval, which requires that the loops have
1361 preheaders. */
1362 create_preheaders (CP_SIMPLE_PREHEADERS);
1363 calculate_dominance_info (CDI_POST_DOMINATORS);
1365 bb_predictions = pointer_map_create ();
1366 tree_bb_level_predictions ();
1368 mark_irreducible_loops ();
1369 record_loop_exits ();
1370 if (number_of_loops () > 1)
1371 predict_loops ();
1373 FOR_EACH_BB (bb)
1375 edge e;
1376 edge_iterator ei;
1378 FOR_EACH_EDGE (e, ei, bb->succs)
1380 /* Predict early returns to be probable, as we've already taken
1381 care for error returns and other cases are often used for
1382 fast paths through function.
1384 Since we've already removed the return statements, we are
1385 looking for CFG like:
1387 if (conditional)
1390 goto return_block
1392 some other blocks
1393 return_block:
1394 return_stmt. */
1395 if (e->dest != bb->next_bb
1396 && e->dest != EXIT_BLOCK_PTR
1397 && single_succ_p (e->dest)
1398 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
1399 && TREE_CODE (last_stmt (e->dest)) == RETURN_EXPR)
1401 edge e1;
1402 edge_iterator ei1;
1404 if (single_succ_p (bb))
1406 FOR_EACH_EDGE (e1, ei1, bb->preds)
1407 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1408 && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1409 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
1410 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1412 else
1413 if (!predicted_by_p (e->src, PRED_NULL_RETURN)
1414 && !predicted_by_p (e->src, PRED_CONST_RETURN)
1415 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
1416 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1419 /* Look for block we are guarding (ie we dominate it,
1420 but it doesn't postdominate us). */
1421 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1422 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1423 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1425 block_stmt_iterator bi;
1427 /* The call heuristic claims that a guarded function call
1428 is improbable. This is because such calls are often used
1429 to signal exceptional situations such as printing error
1430 messages. */
1431 for (bi = bsi_start (e->dest); !bsi_end_p (bi);
1432 bsi_next (&bi))
1434 tree stmt = bsi_stmt (bi);
1435 if ((TREE_CODE (stmt) == CALL_EXPR
1436 || (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1437 && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1))
1438 == CALL_EXPR))
1439 /* Constant and pure calls are hardly used to signalize
1440 something exceptional. */
1441 && TREE_SIDE_EFFECTS (stmt))
1443 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1444 break;
1449 tree_predict_by_opcode (bb);
1451 FOR_EACH_BB (bb)
1452 combine_predictions_for_bb (bb);
1454 #ifdef ENABLE_CHECKING
1455 pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
1456 #endif
1457 pointer_map_destroy (bb_predictions);
1458 bb_predictions = NULL;
1460 strip_builtin_expect ();
1461 estimate_bb_frequencies ();
1462 free_dominance_info (CDI_POST_DOMINATORS);
1463 remove_fake_exit_edges ();
1464 loop_optimizer_finalize ();
1465 if (dump_file && (dump_flags & TDF_DETAILS))
1466 dump_tree_cfg (dump_file, dump_flags);
1467 if (profile_status == PROFILE_ABSENT)
1468 profile_status = PROFILE_GUESSED;
1469 return 0;
1472 /* Sets branch probabilities according to PREDiction and
1473 FLAGS. HEADS[bb->index] should be index of basic block in that we
1474 need to alter branch predictions (i.e. the first of our dominators
1475 such that we do not post-dominate it) (but we fill this information
1476 on demand, so -1 may be there in case this was not needed yet). */
1478 static void
1479 predict_paths_leading_to (basic_block bb, int *heads, enum br_predictor pred,
1480 enum prediction taken)
1482 edge e;
1483 edge_iterator ei;
1484 int y;
1486 if (heads[bb->index] == ENTRY_BLOCK)
1488 /* This is first time we need this field in heads array; so
1489 find first dominator that we do not post-dominate (we are
1490 using already known members of heads array). */
1491 basic_block ai = bb;
1492 basic_block next_ai = get_immediate_dominator (CDI_DOMINATORS, bb);
1493 int head;
1495 while (heads[next_ai->index] == ENTRY_BLOCK)
1497 if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
1498 break;
1499 heads[next_ai->index] = ai->index;
1500 ai = next_ai;
1501 next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai);
1503 if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
1504 head = next_ai->index;
1505 else
1506 head = heads[next_ai->index];
1507 while (next_ai != bb)
1509 next_ai = ai;
1510 ai = BASIC_BLOCK (heads[ai->index]);
1511 heads[next_ai->index] = head;
1514 y = heads[bb->index];
1516 /* Now find the edge that leads to our branch and aply the prediction. */
1518 if (y == last_basic_block)
1519 return;
1520 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (y)->succs)
1521 if (e->dest->index >= NUM_FIXED_BLOCKS
1522 && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb))
1523 predict_edge_def (e, pred, taken);
1526 /* This is used to carry information about basic blocks. It is
1527 attached to the AUX field of the standard CFG block. */
1529 typedef struct block_info_def
1531 /* Estimated frequency of execution of basic_block. */
1532 sreal frequency;
1534 /* To keep queue of basic blocks to process. */
1535 basic_block next;
1537 /* Number of predecessors we need to visit first. */
1538 int npredecessors;
1539 } *block_info;
1541 /* Similar information for edges. */
1542 typedef struct edge_info_def
1544 /* In case edge is a loopback edge, the probability edge will be reached
1545 in case header is. Estimated number of iterations of the loop can be
1546 then computed as 1 / (1 - back_edge_prob). */
1547 sreal back_edge_prob;
1548 /* True if the edge is a loopback edge in the natural loop. */
1549 unsigned int back_edge:1;
1550 } *edge_info;
1552 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1553 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1555 /* Helper function for estimate_bb_frequencies.
1556 Propagate the frequencies in blocks marked in
1557 TOVISIT, starting in HEAD. */
1559 static void
1560 propagate_freq (basic_block head, bitmap tovisit)
1562 basic_block bb;
1563 basic_block last;
1564 unsigned i;
1565 edge e;
1566 basic_block nextbb;
1567 bitmap_iterator bi;
1569 /* For each basic block we need to visit count number of his predecessors
1570 we need to visit first. */
1571 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1573 edge_iterator ei;
1574 int count = 0;
1576 /* The outermost "loop" includes the exit block, which we can not
1577 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1578 directly. Do the same for the entry block. */
1579 bb = BASIC_BLOCK (i);
1581 FOR_EACH_EDGE (e, ei, bb->preds)
1583 bool visit = bitmap_bit_p (tovisit, e->src->index);
1585 if (visit && !(e->flags & EDGE_DFS_BACK))
1586 count++;
1587 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1588 fprintf (dump_file,
1589 "Irreducible region hit, ignoring edge to %i->%i\n",
1590 e->src->index, bb->index);
1592 BLOCK_INFO (bb)->npredecessors = count;
1595 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1596 last = head;
1597 for (bb = head; bb; bb = nextbb)
1599 edge_iterator ei;
1600 sreal cyclic_probability, frequency;
1602 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
1603 memcpy (&frequency, &real_zero, sizeof (real_zero));
1605 nextbb = BLOCK_INFO (bb)->next;
1606 BLOCK_INFO (bb)->next = NULL;
1608 /* Compute frequency of basic block. */
1609 if (bb != head)
1611 #ifdef ENABLE_CHECKING
1612 FOR_EACH_EDGE (e, ei, bb->preds)
1613 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
1614 || (e->flags & EDGE_DFS_BACK));
1615 #endif
1617 FOR_EACH_EDGE (e, ei, bb->preds)
1618 if (EDGE_INFO (e)->back_edge)
1620 sreal_add (&cyclic_probability, &cyclic_probability,
1621 &EDGE_INFO (e)->back_edge_prob);
1623 else if (!(e->flags & EDGE_DFS_BACK))
1625 sreal tmp;
1627 /* frequency += (e->probability
1628 * BLOCK_INFO (e->src)->frequency /
1629 REG_BR_PROB_BASE); */
1631 sreal_init (&tmp, e->probability, 0);
1632 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
1633 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
1634 sreal_add (&frequency, &frequency, &tmp);
1637 if (sreal_compare (&cyclic_probability, &real_zero) == 0)
1639 memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
1640 sizeof (frequency));
1642 else
1644 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
1646 memcpy (&cyclic_probability, &real_almost_one,
1647 sizeof (real_almost_one));
1650 /* BLOCK_INFO (bb)->frequency = frequency
1651 / (1 - cyclic_probability) */
1653 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
1654 sreal_div (&BLOCK_INFO (bb)->frequency,
1655 &frequency, &cyclic_probability);
1659 bitmap_clear_bit (tovisit, bb->index);
1661 e = find_edge (bb, head);
1662 if (e)
1664 sreal tmp;
1666 /* EDGE_INFO (e)->back_edge_prob
1667 = ((e->probability * BLOCK_INFO (bb)->frequency)
1668 / REG_BR_PROB_BASE); */
1670 sreal_init (&tmp, e->probability, 0);
1671 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
1672 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1673 &tmp, &real_inv_br_prob_base);
1676 /* Propagate to successor blocks. */
1677 FOR_EACH_EDGE (e, ei, bb->succs)
1678 if (!(e->flags & EDGE_DFS_BACK)
1679 && BLOCK_INFO (e->dest)->npredecessors)
1681 BLOCK_INFO (e->dest)->npredecessors--;
1682 if (!BLOCK_INFO (e->dest)->npredecessors)
1684 if (!nextbb)
1685 nextbb = e->dest;
1686 else
1687 BLOCK_INFO (last)->next = e->dest;
1689 last = e->dest;
1695 /* Estimate probabilities of loopback edges in loops at same nest level. */
1697 static void
1698 estimate_loops_at_level (struct loop *first_loop)
1700 struct loop *loop;
1702 for (loop = first_loop; loop; loop = loop->next)
1704 edge e;
1705 basic_block *bbs;
1706 unsigned i;
1707 bitmap tovisit = BITMAP_ALLOC (NULL);
1709 estimate_loops_at_level (loop->inner);
1711 /* Find current loop back edge and mark it. */
1712 e = loop_latch_edge (loop);
1713 EDGE_INFO (e)->back_edge = 1;
1715 bbs = get_loop_body (loop);
1716 for (i = 0; i < loop->num_nodes; i++)
1717 bitmap_set_bit (tovisit, bbs[i]->index);
1718 free (bbs);
1719 propagate_freq (loop->header, tovisit);
1720 BITMAP_FREE (tovisit);
1724 /* Propagates frequencies through structure of loops. */
1726 static void
1727 estimate_loops (void)
1729 bitmap tovisit = BITMAP_ALLOC (NULL);
1730 basic_block bb;
1732 /* Start by estimating the frequencies in the loops. */
1733 if (number_of_loops () > 1)
1734 estimate_loops_at_level (current_loops->tree_root->inner);
1736 /* Now propagate the frequencies through all the blocks. */
1737 FOR_ALL_BB (bb)
1739 bitmap_set_bit (tovisit, bb->index);
1741 propagate_freq (ENTRY_BLOCK_PTR, tovisit);
1742 BITMAP_FREE (tovisit);
1745 /* Convert counts measured by profile driven feedback to frequencies.
1746 Return nonzero iff there was any nonzero execution count. */
1749 counts_to_freqs (void)
1751 gcov_type count_max, true_count_max = 0;
1752 basic_block bb;
1754 FOR_EACH_BB (bb)
1755 true_count_max = MAX (bb->count, true_count_max);
1757 count_max = MAX (true_count_max, 1);
1758 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1759 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1761 return true_count_max;
1764 /* Return true if function is likely to be expensive, so there is no point to
1765 optimize performance of prologue, epilogue or do inlining at the expense
1766 of code size growth. THRESHOLD is the limit of number of instructions
1767 function can execute at average to be still considered not expensive. */
1769 bool
1770 expensive_function_p (int threshold)
1772 unsigned int sum = 0;
1773 basic_block bb;
1774 unsigned int limit;
1776 /* We can not compute accurately for large thresholds due to scaled
1777 frequencies. */
1778 gcc_assert (threshold <= BB_FREQ_MAX);
1780 /* Frequencies are out of range. This either means that function contains
1781 internal loop executing more than BB_FREQ_MAX times or profile feedback
1782 is available and function has not been executed at all. */
1783 if (ENTRY_BLOCK_PTR->frequency == 0)
1784 return true;
1786 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1787 limit = ENTRY_BLOCK_PTR->frequency * threshold;
1788 FOR_EACH_BB (bb)
1790 rtx insn;
1792 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
1793 insn = NEXT_INSN (insn))
1794 if (active_insn_p (insn))
1796 sum += bb->frequency;
1797 if (sum > limit)
1798 return true;
1802 return false;
1805 /* Estimate basic blocks frequency by given branch probabilities. */
1807 void
1808 estimate_bb_frequencies (void)
1810 basic_block bb;
1811 sreal freq_max;
1813 if (!flag_branch_probabilities || !counts_to_freqs ())
1815 static int real_values_initialized = 0;
1817 if (!real_values_initialized)
1819 real_values_initialized = 1;
1820 sreal_init (&real_zero, 0, 0);
1821 sreal_init (&real_one, 1, 0);
1822 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
1823 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
1824 sreal_init (&real_one_half, 1, -1);
1825 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
1826 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
1829 mark_dfs_back_edges ();
1831 single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
1833 /* Set up block info for each basic block. */
1834 alloc_aux_for_blocks (sizeof (struct block_info_def));
1835 alloc_aux_for_edges (sizeof (struct edge_info_def));
1836 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1838 edge e;
1839 edge_iterator ei;
1841 FOR_EACH_EDGE (e, ei, bb->succs)
1843 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
1844 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1845 &EDGE_INFO (e)->back_edge_prob,
1846 &real_inv_br_prob_base);
1850 /* First compute probabilities locally for each loop from innermost
1851 to outermost to examine probabilities for back edges. */
1852 estimate_loops ();
1854 memcpy (&freq_max, &real_zero, sizeof (real_zero));
1855 FOR_EACH_BB (bb)
1856 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
1857 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
1859 sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
1860 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1862 sreal tmp;
1864 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
1865 sreal_add (&tmp, &tmp, &real_one_half);
1866 bb->frequency = sreal_to_int (&tmp);
1869 free_aux_for_blocks ();
1870 free_aux_for_edges ();
1872 compute_function_frequency ();
1873 if (flag_reorder_functions)
1874 choose_function_section ();
1877 /* Decide whether function is hot, cold or unlikely executed. */
1878 static void
1879 compute_function_frequency (void)
1881 basic_block bb;
1883 if (!profile_info || !flag_branch_probabilities)
1885 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
1886 != NULL)
1887 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1888 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
1889 != NULL)
1890 cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
1891 return;
1893 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1894 FOR_EACH_BB (bb)
1896 if (maybe_hot_bb_p (bb))
1898 cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
1899 return;
1901 if (!probably_never_executed_bb_p (bb))
1902 cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
1906 /* Choose appropriate section for the function. */
1907 static void
1908 choose_function_section (void)
1910 if (DECL_SECTION_NAME (current_function_decl)
1911 || !targetm.have_named_sections
1912 /* Theoretically we can split the gnu.linkonce text section too,
1913 but this requires more work as the frequency needs to match
1914 for all generated objects so we need to merge the frequency
1915 of all instances. For now just never set frequency for these. */
1916 || DECL_ONE_ONLY (current_function_decl))
1917 return;
1919 /* If we are doing the partitioning optimization, let the optimization
1920 choose the correct section into which to put things. */
1922 if (flag_reorder_blocks_and_partition)
1923 return;
1925 if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
1926 DECL_SECTION_NAME (current_function_decl) =
1927 build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
1928 if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
1929 DECL_SECTION_NAME (current_function_decl) =
1930 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
1931 UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
1934 static bool
1935 gate_estimate_probability (void)
1937 return flag_guess_branch_prob;
1940 struct tree_opt_pass pass_profile =
1942 "profile", /* name */
1943 gate_estimate_probability, /* gate */
1944 tree_estimate_probability, /* execute */
1945 NULL, /* sub */
1946 NULL, /* next */
1947 0, /* static_pass_number */
1948 TV_BRANCH_PROB, /* tv_id */
1949 PROP_cfg, /* properties_required */
1950 0, /* properties_provided */
1951 0, /* properties_destroyed */
1952 0, /* todo_flags_start */
1953 TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1954 0 /* letter */