OSDN Git Service

* tree-vrp.c (execute_vrp): Do not pass loops structure through
[pf3gnuchains/gcc-fork.git] / gcc / predict.c
1 /* Branch prediction routines for the GNU compiler.
2    Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005
3    Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
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.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22 /* References:
23
24    [1] "Branch Prediction for Free"
25        Ball and Larus; PLDI '93.
26    [2] "Static Branch Frequency and Program Profile Analysis"
27        Wu and Larus; MICRO-27.
28    [3] "Corpus-based Static Branch Prediction"
29        Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.  */
30
31
32 #include "config.h"
33 #include "system.h"
34 #include "coretypes.h"
35 #include "tm.h"
36 #include "tree.h"
37 #include "rtl.h"
38 #include "tm_p.h"
39 #include "hard-reg-set.h"
40 #include "basic-block.h"
41 #include "insn-config.h"
42 #include "regs.h"
43 #include "flags.h"
44 #include "output.h"
45 #include "function.h"
46 #include "except.h"
47 #include "toplev.h"
48 #include "recog.h"
49 #include "expr.h"
50 #include "predict.h"
51 #include "coverage.h"
52 #include "sreal.h"
53 #include "params.h"
54 #include "target.h"
55 #include "cfgloop.h"
56 #include "tree-flow.h"
57 #include "ggc.h"
58 #include "tree-dump.h"
59 #include "tree-pass.h"
60 #include "timevar.h"
61 #include "tree-scalar-evolution.h"
62 #include "cfgloop.h"
63
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;
68
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)
74
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 bool last_basic_block_p (basic_block);
79 static void compute_function_frequency (void);
80 static void choose_function_section (void);
81 static bool can_predict_insn_p (rtx);
82 static void estimate_bb_frequencies (void);
83
84 /* Information we hold about each branch predictor.
85    Filled using information from predict.def.  */
86
87 struct predictor_info
88 {
89   const char *const name;       /* Name used in the debugging dumps.  */
90   const int hitrate;            /* Expected hitrate used by
91                                    predict_insn_def call.  */
92   const int flags;
93 };
94
95 /* Use given predictor without Dempster-Shaffer theory if it matches
96    using first_match heuristics.  */
97 #define PRED_FLAG_FIRST_MATCH 1
98
99 /* Recompute hitrate in percent to our representation.  */
100
101 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
102
103 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
104 static const struct predictor_info predictor_info[]= {
105 #include "predict.def"
106
107   /* Upper bound on predictors.  */
108   {NULL, 0, 0}
109 };
110 #undef DEF_PREDICTOR
111
112 /* Return true in case BB can be CPU intensive and should be optimized
113    for maximal performance.  */
114
115 bool
116 maybe_hot_bb_p (basic_block bb)
117 {
118   if (profile_info && flag_branch_probabilities
119       && (bb->count
120           < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
121     return false;
122   if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
123     return false;
124   return true;
125 }
126
127 /* Return true in case BB is cold and should be optimized for size.  */
128
129 bool
130 probably_cold_bb_p (basic_block bb)
131 {
132   if (profile_info && flag_branch_probabilities
133       && (bb->count
134           < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
135     return true;
136   if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
137     return true;
138   return false;
139 }
140
141 /* Return true in case BB is probably never executed.  */
142 bool
143 probably_never_executed_bb_p (basic_block bb)
144 {
145   if (profile_info && flag_branch_probabilities)
146     return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
147   return false;
148 }
149
150 /* Return true if the one of outgoing edges is already predicted by
151    PREDICTOR.  */
152
153 bool
154 rtl_predicted_by_p (basic_block bb, enum br_predictor predictor)
155 {
156   rtx note;
157   if (!INSN_P (BB_END (bb)))
158     return false;
159   for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
160     if (REG_NOTE_KIND (note) == REG_BR_PRED
161         && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
162       return true;
163   return false;
164 }
165
166 /* Return true if the one of outgoing edges is already predicted by
167    PREDICTOR.  */
168
169 bool
170 tree_predicted_by_p (basic_block bb, enum br_predictor predictor)
171 {
172   struct edge_prediction *i;
173   for (i = bb->predictions; i; i = i->ep_next)
174     if (i->ep_predictor == predictor)
175       return true;
176   return false;
177 }
178
179 /* Return true when the probability of edge is reliable.
180   
181    The profile guessing code is good at predicting branch outcome (ie.
182    taken/not taken), that is predicted right slightly over 75% of time.
183    It is however notoriously poor on predicting the probability itself.
184    In general the profile appear a lot flatter (with probabilities closer
185    to 50%) than the reality so it is bad idea to use it to drive optimization
186    such as those disabling dynamic branch prediction for well predictable
187    branches.
188
189    There are two exceptions - edges leading to noreturn edges and edges
190    predicted by number of iterations heuristics are predicted well.  This macro
191    should be able to distinguish those, but at the moment it simply check for
192    noreturn heuristic that is only one giving probability over 99% or bellow
193    1%.  In future we might want to propagate reliability information across the
194    CFG if we find this information useful on multiple places.   */
195 static bool
196 probability_reliable_p (int prob)
197 {
198   return (profile_status == PROFILE_READ
199           || (profile_status == PROFILE_GUESSED
200               && (prob <= HITRATE (1) || prob >= HITRATE (99))));
201 }
202
203 /* Same predicate as above, working on edges.  */
204 bool
205 edge_probability_reliable_p (edge e)
206 {
207   return probability_reliable_p (e->probability);
208 }
209
210 /* Same predicate as edge_probability_reliable_p, working on notes.  */
211 bool
212 br_prob_note_reliable_p (rtx note)
213 {
214   gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
215   return probability_reliable_p (INTVAL (XEXP (note, 0)));
216 }
217
218 static void
219 predict_insn (rtx insn, enum br_predictor predictor, int probability)
220 {
221   gcc_assert (any_condjump_p (insn));
222   if (!flag_guess_branch_prob)
223     return;
224
225   REG_NOTES (insn)
226     = gen_rtx_EXPR_LIST (REG_BR_PRED,
227                          gen_rtx_CONCAT (VOIDmode,
228                                          GEN_INT ((int) predictor),
229                                          GEN_INT ((int) probability)),
230                          REG_NOTES (insn));
231 }
232
233 /* Predict insn by given predictor.  */
234
235 void
236 predict_insn_def (rtx insn, enum br_predictor predictor,
237                   enum prediction taken)
238 {
239    int probability = predictor_info[(int) predictor].hitrate;
240
241    if (taken != TAKEN)
242      probability = REG_BR_PROB_BASE - probability;
243
244    predict_insn (insn, predictor, probability);
245 }
246
247 /* Predict edge E with given probability if possible.  */
248
249 void
250 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
251 {
252   rtx last_insn;
253   last_insn = BB_END (e->src);
254
255   /* We can store the branch prediction information only about
256      conditional jumps.  */
257   if (!any_condjump_p (last_insn))
258     return;
259
260   /* We always store probability of branching.  */
261   if (e->flags & EDGE_FALLTHRU)
262     probability = REG_BR_PROB_BASE - probability;
263
264   predict_insn (last_insn, predictor, probability);
265 }
266
267 /* Predict edge E with the given PROBABILITY.  */
268 void
269 tree_predict_edge (edge e, enum br_predictor predictor, int probability)
270 {
271   gcc_assert (profile_status != PROFILE_GUESSED);
272   if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
273       && flag_guess_branch_prob && optimize)
274     {
275       struct edge_prediction *i = ggc_alloc (sizeof (struct edge_prediction));
276
277       i->ep_next = e->src->predictions;
278       e->src->predictions = i;
279       i->ep_probability = probability;
280       i->ep_predictor = predictor;
281       i->ep_edge = e;
282     }
283 }
284
285 /* Remove all predictions on given basic block that are attached
286    to edge E.  */
287 void
288 remove_predictions_associated_with_edge (edge e)
289 {
290   if (e->src->predictions)
291     {
292       struct edge_prediction **prediction = &e->src->predictions;
293       while (*prediction)
294         {
295           if ((*prediction)->ep_edge == e)
296             *prediction = (*prediction)->ep_next;
297           else
298             prediction = &((*prediction)->ep_next);
299         }
300     }
301 }
302
303 /* Return true when we can store prediction on insn INSN.
304    At the moment we represent predictions only on conditional
305    jumps, not at computed jump or other complicated cases.  */
306 static bool
307 can_predict_insn_p (rtx insn)
308 {
309   return (JUMP_P (insn)
310           && any_condjump_p (insn)
311           && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
312 }
313
314 /* Predict edge E by given predictor if possible.  */
315
316 void
317 predict_edge_def (edge e, enum br_predictor predictor,
318                   enum prediction taken)
319 {
320    int probability = predictor_info[(int) predictor].hitrate;
321
322    if (taken != TAKEN)
323      probability = REG_BR_PROB_BASE - probability;
324
325    predict_edge (e, predictor, probability);
326 }
327
328 /* Invert all branch predictions or probability notes in the INSN.  This needs
329    to be done each time we invert the condition used by the jump.  */
330
331 void
332 invert_br_probabilities (rtx insn)
333 {
334   rtx note;
335
336   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
337     if (REG_NOTE_KIND (note) == REG_BR_PROB)
338       XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
339     else if (REG_NOTE_KIND (note) == REG_BR_PRED)
340       XEXP (XEXP (note, 0), 1)
341         = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
342 }
343
344 /* Dump information about the branch prediction to the output file.  */
345
346 static void
347 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
348                  basic_block bb, int used)
349 {
350   edge e;
351   edge_iterator ei;
352
353   if (!file)
354     return;
355
356   FOR_EACH_EDGE (e, ei, bb->succs)
357     if (! (e->flags & EDGE_FALLTHRU))
358       break;
359
360   fprintf (file, "  %s heuristics%s: %.1f%%",
361            predictor_info[predictor].name,
362            used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
363
364   if (bb->count)
365     {
366       fprintf (file, "  exec ");
367       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
368       if (e)
369         {
370           fprintf (file, " hit ");
371           fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
372           fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
373         }
374     }
375
376   fprintf (file, "\n");
377 }
378
379 /* We can not predict the probabilities of outgoing edges of bb.  Set them
380    evenly and hope for the best.  */
381 static void
382 set_even_probabilities (basic_block bb)
383 {
384   int nedges = 0;
385   edge e;
386   edge_iterator ei;
387
388   FOR_EACH_EDGE (e, ei, bb->succs)
389     if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
390       nedges ++;
391   FOR_EACH_EDGE (e, ei, bb->succs)
392     if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
393       e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
394     else
395       e->probability = 0;
396 }
397
398 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
399    note if not already present.  Remove now useless REG_BR_PRED notes.  */
400
401 static void
402 combine_predictions_for_insn (rtx insn, basic_block bb)
403 {
404   rtx prob_note;
405   rtx *pnote;
406   rtx note;
407   int best_probability = PROB_EVEN;
408   int best_predictor = END_PREDICTORS;
409   int combined_probability = REG_BR_PROB_BASE / 2;
410   int d;
411   bool first_match = false;
412   bool found = false;
413
414   if (!can_predict_insn_p (insn))
415     {
416       set_even_probabilities (bb);
417       return;
418     }
419
420   prob_note = find_reg_note (insn, REG_BR_PROB, 0);
421   pnote = &REG_NOTES (insn);
422   if (dump_file)
423     fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
424              bb->index);
425
426   /* We implement "first match" heuristics and use probability guessed
427      by predictor with smallest index.  */
428   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
429     if (REG_NOTE_KIND (note) == REG_BR_PRED)
430       {
431         int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
432         int probability = INTVAL (XEXP (XEXP (note, 0), 1));
433
434         found = true;
435         if (best_predictor > predictor)
436           best_probability = probability, best_predictor = predictor;
437
438         d = (combined_probability * probability
439              + (REG_BR_PROB_BASE - combined_probability)
440              * (REG_BR_PROB_BASE - probability));
441
442         /* Use FP math to avoid overflows of 32bit integers.  */
443         if (d == 0)
444           /* If one probability is 0% and one 100%, avoid division by zero.  */
445           combined_probability = REG_BR_PROB_BASE / 2;
446         else
447           combined_probability = (((double) combined_probability) * probability
448                                   * REG_BR_PROB_BASE / d + 0.5);
449       }
450
451   /* Decide which heuristic to use.  In case we didn't match anything,
452      use no_prediction heuristic, in case we did match, use either
453      first match or Dempster-Shaffer theory depending on the flags.  */
454
455   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
456     first_match = true;
457
458   if (!found)
459     dump_prediction (dump_file, PRED_NO_PREDICTION,
460                      combined_probability, bb, true);
461   else
462     {
463       dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
464                        bb, !first_match);
465       dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
466                        bb, first_match);
467     }
468
469   if (first_match)
470     combined_probability = best_probability;
471   dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
472
473   while (*pnote)
474     {
475       if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
476         {
477           int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
478           int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
479
480           dump_prediction (dump_file, predictor, probability, bb,
481                            !first_match || best_predictor == predictor);
482           *pnote = XEXP (*pnote, 1);
483         }
484       else
485         pnote = &XEXP (*pnote, 1);
486     }
487
488   if (!prob_note)
489     {
490       REG_NOTES (insn)
491         = gen_rtx_EXPR_LIST (REG_BR_PROB,
492                              GEN_INT (combined_probability), REG_NOTES (insn));
493
494       /* Save the prediction into CFG in case we are seeing non-degenerated
495          conditional jump.  */
496       if (!single_succ_p (bb))
497         {
498           BRANCH_EDGE (bb)->probability = combined_probability;
499           FALLTHRU_EDGE (bb)->probability
500             = REG_BR_PROB_BASE - combined_probability;
501         }
502     }
503   else if (!single_succ_p (bb))
504     {
505       int prob = INTVAL (XEXP (prob_note, 0));
506
507       BRANCH_EDGE (bb)->probability = prob;
508       FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
509     }
510   else
511     single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
512 }
513
514 /* Combine predictions into single probability and store them into CFG.
515    Remove now useless prediction entries.  */
516
517 static void
518 combine_predictions_for_bb (basic_block bb)
519 {
520   int best_probability = PROB_EVEN;
521   int best_predictor = END_PREDICTORS;
522   int combined_probability = REG_BR_PROB_BASE / 2;
523   int d;
524   bool first_match = false;
525   bool found = false;
526   struct edge_prediction *pred;
527   int nedges = 0;
528   edge e, first = NULL, second = NULL;
529   edge_iterator ei;
530
531   FOR_EACH_EDGE (e, ei, bb->succs)
532     if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
533       {
534         nedges ++;
535         if (first && !second)
536           second = e;
537         if (!first)
538           first = e;
539       }
540
541   /* When there is no successor or only one choice, prediction is easy. 
542
543      We are lazy for now and predict only basic blocks with two outgoing
544      edges.  It is possible to predict generic case too, but we have to
545      ignore first match heuristics and do more involved combining.  Implement
546      this later.  */
547   if (nedges != 2)
548     {
549       if (!bb->count)
550         set_even_probabilities (bb);
551       bb->predictions = NULL;
552       if (dump_file)
553         fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
554                  nedges, bb->index);
555       return;
556     }
557
558   if (dump_file)
559     fprintf (dump_file, "Predictions for bb %i\n", bb->index);
560
561   /* We implement "first match" heuristics and use probability guessed
562      by predictor with smallest index.  */
563   for (pred = bb->predictions; pred; pred = pred->ep_next)
564     {
565       int predictor = pred->ep_predictor;
566       int probability = pred->ep_probability;
567
568       if (pred->ep_edge != first)
569         probability = REG_BR_PROB_BASE - probability;
570
571       found = true;
572       if (best_predictor > predictor)
573         best_probability = probability, best_predictor = predictor;
574
575       d = (combined_probability * probability
576            + (REG_BR_PROB_BASE - combined_probability)
577            * (REG_BR_PROB_BASE - probability));
578
579       /* Use FP math to avoid overflows of 32bit integers.  */
580       if (d == 0)
581         /* If one probability is 0% and one 100%, avoid division by zero.  */
582         combined_probability = REG_BR_PROB_BASE / 2;
583       else
584         combined_probability = (((double) combined_probability) * probability
585                                 * REG_BR_PROB_BASE / d + 0.5);
586     }
587
588   /* Decide which heuristic to use.  In case we didn't match anything,
589      use no_prediction heuristic, in case we did match, use either
590      first match or Dempster-Shaffer theory depending on the flags.  */
591
592   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
593     first_match = true;
594
595   if (!found)
596     dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
597   else
598     {
599       dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
600                        !first_match);
601       dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
602                        first_match);
603     }
604
605   if (first_match)
606     combined_probability = best_probability;
607   dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
608
609   for (pred = bb->predictions; pred; pred = pred->ep_next)
610     {
611       int predictor = pred->ep_predictor;
612       int probability = pred->ep_probability;
613
614       if (pred->ep_edge != EDGE_SUCC (bb, 0))
615         probability = REG_BR_PROB_BASE - probability;
616       dump_prediction (dump_file, predictor, probability, bb,
617                        !first_match || best_predictor == predictor);
618     }
619   bb->predictions = NULL;
620
621   if (!bb->count)
622     {
623       first->probability = combined_probability;
624       second->probability = REG_BR_PROB_BASE - combined_probability;
625     }
626 }
627
628 /* Predict edge probabilities by exploiting loop structure.  */
629
630 static void
631 predict_loops (void)
632 {
633   unsigned i;
634
635   scev_initialize ();
636
637   /* Try to predict out blocks in a loop that are not part of a
638      natural loop.  */
639   for (i = 1; i < current_loops->num; i++)
640     {
641       basic_block bb, *bbs;
642       unsigned j, n_exits;
643       struct loop *loop = current_loops->parray[i];
644       VEC (edge, heap) *exits;
645       struct tree_niter_desc niter_desc;
646       edge ex;
647
648       exits = get_loop_exit_edges (loop);
649       n_exits = VEC_length (edge, exits);
650
651       for (j = 0; VEC_iterate (edge, exits, j, ex); j++)
652         {
653           tree niter = NULL;
654
655           if (number_of_iterations_exit (loop, ex, &niter_desc, false))
656             niter = niter_desc.niter;
657           if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
658             niter = loop_niter_by_eval (loop, ex);
659
660           if (TREE_CODE (niter) == INTEGER_CST)
661             {
662               int probability;
663               int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
664               if (host_integerp (niter, 1)
665                   && tree_int_cst_lt (niter,
666                                       build_int_cstu (NULL_TREE, max - 1)))
667                 {
668                   HOST_WIDE_INT nitercst = tree_low_cst (niter, 1) + 1;
669                   probability = ((REG_BR_PROB_BASE + nitercst / 2)
670                                  / nitercst);
671                 }
672               else
673                 probability = ((REG_BR_PROB_BASE + max / 2) / max);
674
675               predict_edge (ex, PRED_LOOP_ITERATIONS, probability);
676             }
677         }
678       VEC_free (edge, heap, exits);
679
680       bbs = get_loop_body (loop);
681
682       for (j = 0; j < loop->num_nodes; j++)
683         {
684           int header_found = 0;
685           edge e;
686           edge_iterator ei;
687
688           bb = bbs[j];
689
690           /* Bypass loop heuristics on continue statement.  These
691              statements construct loops via "non-loop" constructs
692              in the source language and are better to be handled
693              separately.  */
694           if (predicted_by_p (bb, PRED_CONTINUE))
695             continue;
696
697           /* Loop branch heuristics - predict an edge back to a
698              loop's head as taken.  */
699           if (bb == loop->latch)
700             {
701               e = find_edge (loop->latch, loop->header);
702               if (e)
703                 {
704                   header_found = 1;
705                   predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
706                 }
707             }
708
709           /* Loop exit heuristics - predict an edge exiting the loop if the
710              conditional has no loop header successors as not taken.  */
711           if (!header_found)
712             {
713               /* For loop with many exits we don't want to predict all exits
714                  with the pretty large probability, because if all exits are
715                  considered in row, the loop would be predicted to iterate
716                  almost never.  The code to divide probability by number of
717                  exits is very rough.  It should compute the number of exits
718                  taken in each patch through function (not the overall number
719                  of exits that might be a lot higher for loops with wide switch
720                  statements in them) and compute n-th square root.
721
722                  We limit the minimal probability by 2% to avoid
723                  EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
724                  as this was causing regression in perl benchmark containing such
725                  a wide loop.  */
726                 
727               int probability = ((REG_BR_PROB_BASE
728                                   - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
729                                  / n_exits);
730               if (probability < HITRATE (2))
731                 probability = HITRATE (2);
732               FOR_EACH_EDGE (e, ei, bb->succs)
733                 if (e->dest->index < NUM_FIXED_BLOCKS
734                     || !flow_bb_inside_loop_p (loop, e->dest))
735                   predict_edge (e, PRED_LOOP_EXIT, probability);
736             }
737         }
738       
739       /* Free basic blocks from get_loop_body.  */
740       free (bbs);
741     }
742
743   scev_finalize ();
744 }
745
746 /* Attempt to predict probabilities of BB outgoing edges using local
747    properties.  */
748 static void
749 bb_estimate_probability_locally (basic_block bb)
750 {
751   rtx last_insn = BB_END (bb);
752   rtx cond;
753
754   if (! can_predict_insn_p (last_insn))
755     return;
756   cond = get_condition (last_insn, NULL, false, false);
757   if (! cond)
758     return;
759
760   /* Try "pointer heuristic."
761      A comparison ptr == 0 is predicted as false.
762      Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
763   if (COMPARISON_P (cond)
764       && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
765           || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
766     {
767       if (GET_CODE (cond) == EQ)
768         predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
769       else if (GET_CODE (cond) == NE)
770         predict_insn_def (last_insn, PRED_POINTER, TAKEN);
771     }
772   else
773
774   /* Try "opcode heuristic."
775      EQ tests are usually false and NE tests are usually true. Also,
776      most quantities are positive, so we can make the appropriate guesses
777      about signed comparisons against zero.  */
778     switch (GET_CODE (cond))
779       {
780       case CONST_INT:
781         /* Unconditional branch.  */
782         predict_insn_def (last_insn, PRED_UNCONDITIONAL,
783                           cond == const0_rtx ? NOT_TAKEN : TAKEN);
784         break;
785
786       case EQ:
787       case UNEQ:
788         /* Floating point comparisons appears to behave in a very
789            unpredictable way because of special role of = tests in
790            FP code.  */
791         if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
792           ;
793         /* Comparisons with 0 are often used for booleans and there is
794            nothing useful to predict about them.  */
795         else if (XEXP (cond, 1) == const0_rtx
796                  || XEXP (cond, 0) == const0_rtx)
797           ;
798         else
799           predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
800         break;
801
802       case NE:
803       case LTGT:
804         /* Floating point comparisons appears to behave in a very
805            unpredictable way because of special role of = tests in
806            FP code.  */
807         if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
808           ;
809         /* Comparisons with 0 are often used for booleans and there is
810            nothing useful to predict about them.  */
811         else if (XEXP (cond, 1) == const0_rtx
812                  || XEXP (cond, 0) == const0_rtx)
813           ;
814         else
815           predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
816         break;
817
818       case ORDERED:
819         predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
820         break;
821
822       case UNORDERED:
823         predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
824         break;
825
826       case LE:
827       case LT:
828         if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
829             || XEXP (cond, 1) == constm1_rtx)
830           predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
831         break;
832
833       case GE:
834       case GT:
835         if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
836             || XEXP (cond, 1) == constm1_rtx)
837           predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
838         break;
839
840       default:
841         break;
842       }
843 }
844
845 /* Set edge->probability for each successor edge of BB.  */
846 void
847 guess_outgoing_edge_probabilities (basic_block bb)
848 {
849   bb_estimate_probability_locally (bb);
850   combine_predictions_for_insn (BB_END (bb), bb);
851 }
852 \f
853 /* Return constant EXPR will likely have at execution time, NULL if unknown. 
854    The function is used by builtin_expect branch predictor so the evidence
855    must come from this construct and additional possible constant folding.
856   
857    We may want to implement more involved value guess (such as value range
858    propagation based prediction), but such tricks shall go to new
859    implementation.  */
860
861 static tree
862 expr_expected_value (tree expr, bitmap visited)
863 {
864   if (TREE_CONSTANT (expr))
865     return expr;
866   else if (TREE_CODE (expr) == SSA_NAME)
867     {
868       tree def = SSA_NAME_DEF_STMT (expr);
869
870       /* If we were already here, break the infinite cycle.  */
871       if (bitmap_bit_p (visited, SSA_NAME_VERSION (expr)))
872         return NULL;
873       bitmap_set_bit (visited, SSA_NAME_VERSION (expr));
874
875       if (TREE_CODE (def) == PHI_NODE)
876         {
877           /* All the arguments of the PHI node must have the same constant
878              length.  */
879           int i;
880           tree val = NULL, new_val;
881
882           for (i = 0; i < PHI_NUM_ARGS (def); i++)
883             {
884               tree arg = PHI_ARG_DEF (def, i);
885
886               /* If this PHI has itself as an argument, we cannot
887                  determine the string length of this argument.  However,
888                  if we can find an expected constant value for the other
889                  PHI args then we can still be sure that this is
890                  likely a constant.  So be optimistic and just
891                  continue with the next argument.  */
892               if (arg == PHI_RESULT (def))
893                 continue;
894
895               new_val = expr_expected_value (arg, visited);
896               if (!new_val)
897                 return NULL;
898               if (!val)
899                 val = new_val;
900               else if (!operand_equal_p (val, new_val, false))
901                 return NULL;
902             }
903           return val;
904         }
905       if (TREE_CODE (def) != MODIFY_EXPR || TREE_OPERAND (def, 0) != expr)
906         return NULL;
907       return expr_expected_value (TREE_OPERAND (def, 1), visited);
908     }
909   else if (TREE_CODE (expr) == CALL_EXPR)
910     {
911       tree decl = get_callee_fndecl (expr);
912       if (!decl)
913         return NULL;
914       if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
915           && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
916         {
917           tree arglist = TREE_OPERAND (expr, 1);
918           tree val;
919
920           if (arglist == NULL_TREE
921               || TREE_CHAIN (arglist) == NULL_TREE)
922             return NULL; 
923           val = TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr, 1)));
924           if (TREE_CONSTANT (val))
925             return val;
926           return TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr, 1)));
927         }
928     }
929   if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
930     {
931       tree op0, op1, res;
932       op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited);
933       if (!op0)
934         return NULL;
935       op1 = expr_expected_value (TREE_OPERAND (expr, 1), visited);
936       if (!op1)
937         return NULL;
938       res = fold_build2 (TREE_CODE (expr), TREE_TYPE (expr), op0, op1);
939       if (TREE_CONSTANT (res))
940         return res;
941       return NULL;
942     }
943   if (UNARY_CLASS_P (expr))
944     {
945       tree op0, res;
946       op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited);
947       if (!op0)
948         return NULL;
949       res = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr), op0);
950       if (TREE_CONSTANT (res))
951         return res;
952       return NULL;
953     }
954   return NULL;
955 }
956 \f
957 /* Get rid of all builtin_expect calls we no longer need.  */
958 static void
959 strip_builtin_expect (void)
960 {
961   basic_block bb;
962   FOR_EACH_BB (bb)
963     {
964       block_stmt_iterator bi;
965       for (bi = bsi_start (bb); !bsi_end_p (bi); bsi_next (&bi))
966         {
967           tree stmt = bsi_stmt (bi);
968           tree fndecl;
969           tree arglist;
970
971           if (TREE_CODE (stmt) == MODIFY_EXPR
972               && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR
973               && (fndecl = get_callee_fndecl (TREE_OPERAND (stmt, 1)))
974               && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
975               && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
976               && (arglist = TREE_OPERAND (TREE_OPERAND (stmt, 1), 1))
977               && TREE_CHAIN (arglist))
978             {
979               TREE_OPERAND (stmt, 1) = TREE_VALUE (arglist);
980               update_stmt (stmt);
981             }
982         }
983     }
984 }
985 \f
986 /* Predict using opcode of the last statement in basic block.  */
987 static void
988 tree_predict_by_opcode (basic_block bb)
989 {
990   tree stmt = last_stmt (bb);
991   edge then_edge;
992   tree cond;
993   tree op0;
994   tree type;
995   tree val;
996   bitmap visited;
997   edge_iterator ei;
998
999   if (!stmt || TREE_CODE (stmt) != COND_EXPR)
1000     return;
1001   FOR_EACH_EDGE (then_edge, ei, bb->succs)
1002     if (then_edge->flags & EDGE_TRUE_VALUE)
1003       break;
1004   cond = TREE_OPERAND (stmt, 0);
1005   if (!COMPARISON_CLASS_P (cond))
1006     return;
1007   op0 = TREE_OPERAND (cond, 0);
1008   type = TREE_TYPE (op0);
1009   visited = BITMAP_ALLOC (NULL);
1010   val = expr_expected_value (cond, visited);
1011   BITMAP_FREE (visited);
1012   if (val)
1013     {
1014       if (integer_zerop (val))
1015         predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1016       else
1017         predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1018       return;
1019     }
1020   /* Try "pointer heuristic."
1021      A comparison ptr == 0 is predicted as false.
1022      Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
1023   if (POINTER_TYPE_P (type))
1024     {
1025       if (TREE_CODE (cond) == EQ_EXPR)
1026         predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1027       else if (TREE_CODE (cond) == NE_EXPR)
1028         predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1029     }
1030   else
1031
1032   /* Try "opcode heuristic."
1033      EQ tests are usually false and NE tests are usually true. Also,
1034      most quantities are positive, so we can make the appropriate guesses
1035      about signed comparisons against zero.  */
1036     switch (TREE_CODE (cond))
1037       {
1038       case EQ_EXPR:
1039       case UNEQ_EXPR:
1040         /* Floating point comparisons appears to behave in a very
1041            unpredictable way because of special role of = tests in
1042            FP code.  */
1043         if (FLOAT_TYPE_P (type))
1044           ;
1045         /* Comparisons with 0 are often used for booleans and there is
1046            nothing useful to predict about them.  */
1047         else if (integer_zerop (op0)
1048                  || integer_zerop (TREE_OPERAND (cond, 1)))
1049           ;
1050         else
1051           predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1052         break;
1053
1054       case NE_EXPR:
1055       case LTGT_EXPR:
1056         /* Floating point comparisons appears to behave in a very
1057            unpredictable way because of special role of = tests in
1058            FP code.  */
1059         if (FLOAT_TYPE_P (type))
1060           ;
1061         /* Comparisons with 0 are often used for booleans and there is
1062            nothing useful to predict about them.  */
1063         else if (integer_zerop (op0)
1064                  || integer_zerop (TREE_OPERAND (cond, 1)))
1065           ;
1066         else
1067           predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1068         break;
1069
1070       case ORDERED_EXPR:
1071         predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1072         break;
1073
1074       case UNORDERED_EXPR:
1075         predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1076         break;
1077
1078       case LE_EXPR:
1079       case LT_EXPR:
1080         if (integer_zerop (TREE_OPERAND (cond, 1))
1081             || integer_onep (TREE_OPERAND (cond, 1))
1082             || integer_all_onesp (TREE_OPERAND (cond, 1))
1083             || real_zerop (TREE_OPERAND (cond, 1))
1084             || real_onep (TREE_OPERAND (cond, 1))
1085             || real_minus_onep (TREE_OPERAND (cond, 1)))
1086           predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1087         break;
1088
1089       case GE_EXPR:
1090       case GT_EXPR:
1091         if (integer_zerop (TREE_OPERAND (cond, 1))
1092             || integer_onep (TREE_OPERAND (cond, 1))
1093             || integer_all_onesp (TREE_OPERAND (cond, 1))
1094             || real_zerop (TREE_OPERAND (cond, 1))
1095             || real_onep (TREE_OPERAND (cond, 1))
1096             || real_minus_onep (TREE_OPERAND (cond, 1)))
1097           predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1098         break;
1099
1100       default:
1101         break;
1102       }
1103 }
1104
1105 /* Try to guess whether the value of return means error code.  */
1106 static enum br_predictor
1107 return_prediction (tree val, enum prediction *prediction)
1108 {
1109   /* VOID.  */
1110   if (!val)
1111     return PRED_NO_PREDICTION;
1112   /* Different heuristics for pointers and scalars.  */
1113   if (POINTER_TYPE_P (TREE_TYPE (val)))
1114     {
1115       /* NULL is usually not returned.  */
1116       if (integer_zerop (val))
1117         {
1118           *prediction = NOT_TAKEN;
1119           return PRED_NULL_RETURN;
1120         }
1121     }
1122   else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1123     {
1124       /* Negative return values are often used to indicate
1125          errors.  */
1126       if (TREE_CODE (val) == INTEGER_CST
1127           && tree_int_cst_sgn (val) < 0)
1128         {
1129           *prediction = NOT_TAKEN;
1130           return PRED_NEGATIVE_RETURN;
1131         }
1132       /* Constant return values seems to be commonly taken.
1133          Zero/one often represent booleans so exclude them from the
1134          heuristics.  */
1135       if (TREE_CONSTANT (val)
1136           && (!integer_zerop (val) && !integer_onep (val)))
1137         {
1138           *prediction = TAKEN;
1139           return PRED_NEGATIVE_RETURN;
1140         }
1141     }
1142   return PRED_NO_PREDICTION;
1143 }
1144
1145 /* Find the basic block with return expression and look up for possible
1146    return value trying to apply RETURN_PREDICTION heuristics.  */
1147 static void
1148 apply_return_prediction (int *heads)
1149 {
1150   tree return_stmt = NULL;
1151   tree return_val;
1152   edge e;
1153   tree phi;
1154   int phi_num_args, i;
1155   enum br_predictor pred;
1156   enum prediction direction;
1157   edge_iterator ei;
1158
1159   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1160     {
1161       return_stmt = last_stmt (e->src);
1162       if (TREE_CODE (return_stmt) == RETURN_EXPR)
1163         break;
1164     }
1165   if (!e)
1166     return;
1167   return_val = TREE_OPERAND (return_stmt, 0);
1168   if (!return_val)
1169     return;
1170   if (TREE_CODE (return_val) == MODIFY_EXPR)
1171     return_val = TREE_OPERAND (return_val, 1);
1172   if (TREE_CODE (return_val) != SSA_NAME
1173       || !SSA_NAME_DEF_STMT (return_val)
1174       || TREE_CODE (SSA_NAME_DEF_STMT (return_val)) != PHI_NODE)
1175     return;
1176   for (phi = SSA_NAME_DEF_STMT (return_val); phi; phi = PHI_CHAIN (phi))
1177     if (PHI_RESULT (phi) == return_val)
1178       break;
1179   if (!phi)
1180     return;
1181   phi_num_args = PHI_NUM_ARGS (phi);
1182   pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1183
1184   /* Avoid the degenerate case where all return values form the function
1185      belongs to same category (ie they are all positive constants)
1186      so we can hardly say something about them.  */
1187   for (i = 1; i < phi_num_args; i++)
1188     if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1189       break;
1190   if (i != phi_num_args)
1191     for (i = 0; i < phi_num_args; i++)
1192       {
1193         pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1194         if (pred != PRED_NO_PREDICTION)
1195           predict_paths_leading_to (PHI_ARG_EDGE (phi, i)->src, heads, pred,
1196                                     direction);
1197       }
1198 }
1199
1200 /* Look for basic block that contains unlikely to happen events
1201    (such as noreturn calls) and mark all paths leading to execution
1202    of this basic blocks as unlikely.  */
1203
1204 static void
1205 tree_bb_level_predictions (void)
1206 {
1207   basic_block bb;
1208   int *heads;
1209
1210   heads = XCNEWVEC (int, last_basic_block);
1211   heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
1212
1213   apply_return_prediction (heads);
1214
1215   FOR_EACH_BB (bb)
1216     {
1217       block_stmt_iterator bsi = bsi_last (bb);
1218
1219       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1220         {
1221           tree stmt = bsi_stmt (bsi);
1222           switch (TREE_CODE (stmt))
1223             {
1224               case MODIFY_EXPR:
1225                 if (TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)
1226                   {
1227                     stmt = TREE_OPERAND (stmt, 1);
1228                     goto call_expr;
1229                   }
1230                 break;
1231               case CALL_EXPR:
1232 call_expr:;
1233                 if (call_expr_flags (stmt) & ECF_NORETURN)
1234                   predict_paths_leading_to (bb, heads, PRED_NORETURN,
1235                                             NOT_TAKEN);
1236                 break;
1237               default:
1238                 break;
1239             }
1240         }
1241     }
1242
1243   free (heads);
1244 }
1245
1246 /* Predict branch probabilities and estimate profile of the tree CFG.  */
1247 static unsigned int
1248 tree_estimate_probability (void)
1249 {
1250   basic_block bb;
1251
1252   loop_optimizer_init (0);
1253   if (current_loops && dump_file && (dump_flags & TDF_DETAILS))
1254     flow_loops_dump (dump_file, NULL, 0);
1255
1256   add_noreturn_fake_exit_edges ();
1257   connect_infinite_loops_to_exit ();
1258   calculate_dominance_info (CDI_DOMINATORS);
1259   calculate_dominance_info (CDI_POST_DOMINATORS);
1260
1261   tree_bb_level_predictions ();
1262
1263   mark_irreducible_loops ();
1264   if (current_loops)
1265     predict_loops ();
1266
1267   FOR_EACH_BB (bb)
1268     {
1269       edge e;
1270       edge_iterator ei;
1271
1272       FOR_EACH_EDGE (e, ei, bb->succs)
1273         {
1274           /* Predict early returns to be probable, as we've already taken
1275              care for error returns and other cases are often used for
1276              fast paths through function.  */
1277           if (e->dest == EXIT_BLOCK_PTR
1278               && TREE_CODE (last_stmt (bb)) == RETURN_EXPR
1279               && !single_pred_p (bb))
1280             {
1281               edge e1;
1282               edge_iterator ei1;
1283
1284               FOR_EACH_EDGE (e1, ei1, bb->preds)
1285                 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1286                     && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1287                     && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN)
1288                     && !last_basic_block_p (e1->src))
1289                   predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1290             }
1291
1292           /* Look for block we are guarding (ie we dominate it,
1293              but it doesn't postdominate us).  */
1294           if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1295               && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1296               && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1297             {
1298               block_stmt_iterator bi;
1299
1300               /* The call heuristic claims that a guarded function call
1301                  is improbable.  This is because such calls are often used
1302                  to signal exceptional situations such as printing error
1303                  messages.  */
1304               for (bi = bsi_start (e->dest); !bsi_end_p (bi);
1305                    bsi_next (&bi))
1306                 {
1307                   tree stmt = bsi_stmt (bi);
1308                   if ((TREE_CODE (stmt) == CALL_EXPR
1309                        || (TREE_CODE (stmt) == MODIFY_EXPR
1310                            && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
1311                       /* Constant and pure calls are hardly used to signalize
1312                          something exceptional.  */
1313                       && TREE_SIDE_EFFECTS (stmt))
1314                     {
1315                       predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1316                       break;
1317                     }
1318                 }
1319             }
1320         }
1321       tree_predict_by_opcode (bb);
1322     }
1323   FOR_EACH_BB (bb)
1324     combine_predictions_for_bb (bb);
1325
1326   strip_builtin_expect ();
1327   estimate_bb_frequencies ();
1328   free_dominance_info (CDI_POST_DOMINATORS);
1329   remove_fake_exit_edges ();
1330   loop_optimizer_finalize ();
1331   if (dump_file && (dump_flags & TDF_DETAILS))
1332     dump_tree_cfg (dump_file, dump_flags);
1333   if (profile_status == PROFILE_ABSENT)
1334     profile_status = PROFILE_GUESSED;
1335   return 0;
1336 }
1337 \f
1338 /* Check whether this is the last basic block of function.  Commonly
1339    there is one extra common cleanup block.  */
1340 static bool
1341 last_basic_block_p (basic_block bb)
1342 {
1343   if (bb == EXIT_BLOCK_PTR)
1344     return false;
1345
1346   return (bb->next_bb == EXIT_BLOCK_PTR
1347           || (bb->next_bb->next_bb == EXIT_BLOCK_PTR
1348               && single_succ_p (bb)
1349               && single_succ (bb)->next_bb == EXIT_BLOCK_PTR));
1350 }
1351
1352 /* Sets branch probabilities according to PREDiction and
1353    FLAGS. HEADS[bb->index] should be index of basic block in that we
1354    need to alter branch predictions (i.e. the first of our dominators
1355    such that we do not post-dominate it) (but we fill this information
1356    on demand, so -1 may be there in case this was not needed yet).  */
1357
1358 static void
1359 predict_paths_leading_to (basic_block bb, int *heads, enum br_predictor pred,
1360                           enum prediction taken)
1361 {
1362   edge e;
1363   edge_iterator ei;
1364   int y;
1365
1366   if (heads[bb->index] == ENTRY_BLOCK)
1367     {
1368       /* This is first time we need this field in heads array; so
1369          find first dominator that we do not post-dominate (we are
1370          using already known members of heads array).  */
1371       basic_block ai = bb;
1372       basic_block next_ai = get_immediate_dominator (CDI_DOMINATORS, bb);
1373       int head;
1374
1375       while (heads[next_ai->index] == ENTRY_BLOCK)
1376         {
1377           if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
1378             break;
1379           heads[next_ai->index] = ai->index;
1380           ai = next_ai;
1381           next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai);
1382         }
1383       if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
1384         head = next_ai->index;
1385       else
1386         head = heads[next_ai->index];
1387       while (next_ai != bb)
1388         {
1389           next_ai = ai;
1390           ai = BASIC_BLOCK (heads[ai->index]);
1391           heads[next_ai->index] = head;
1392         }
1393     }
1394   y = heads[bb->index];
1395
1396   /* Now find the edge that leads to our branch and aply the prediction.  */
1397
1398   if (y == last_basic_block)
1399     return;
1400   FOR_EACH_EDGE (e, ei, BASIC_BLOCK (y)->succs)
1401     if (e->dest->index >= NUM_FIXED_BLOCKS
1402         && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb))
1403       predict_edge_def (e, pred, taken);
1404 }
1405 \f
1406 /* This is used to carry information about basic blocks.  It is
1407    attached to the AUX field of the standard CFG block.  */
1408
1409 typedef struct block_info_def
1410 {
1411   /* Estimated frequency of execution of basic_block.  */
1412   sreal frequency;
1413
1414   /* To keep queue of basic blocks to process.  */
1415   basic_block next;
1416
1417   /* Number of predecessors we need to visit first.  */
1418   int npredecessors;
1419 } *block_info;
1420
1421 /* Similar information for edges.  */
1422 typedef struct edge_info_def
1423 {
1424   /* In case edge is a loopback edge, the probability edge will be reached
1425      in case header is.  Estimated number of iterations of the loop can be
1426      then computed as 1 / (1 - back_edge_prob).  */
1427   sreal back_edge_prob;
1428   /* True if the edge is a loopback edge in the natural loop.  */
1429   unsigned int back_edge:1;
1430 } *edge_info;
1431
1432 #define BLOCK_INFO(B)   ((block_info) (B)->aux)
1433 #define EDGE_INFO(E)    ((edge_info) (E)->aux)
1434
1435 /* Helper function for estimate_bb_frequencies.
1436    Propagate the frequencies in blocks marked in
1437    TOVISIT, starting in HEAD.  */
1438
1439 static void
1440 propagate_freq (basic_block head, bitmap tovisit)
1441 {
1442   basic_block bb;
1443   basic_block last;
1444   unsigned i;
1445   edge e;
1446   basic_block nextbb;
1447   bitmap_iterator bi;
1448
1449   /* For each basic block we need to visit count number of his predecessors
1450      we need to visit first.  */
1451   EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1452     {
1453       edge_iterator ei;
1454       int count = 0;
1455
1456        /* The outermost "loop" includes the exit block, which we can not
1457           look up via BASIC_BLOCK.  Detect this and use EXIT_BLOCK_PTR
1458           directly.  Do the same for the entry block.  */
1459       bb = BASIC_BLOCK (i);
1460
1461       FOR_EACH_EDGE (e, ei, bb->preds)
1462         {
1463           bool visit = bitmap_bit_p (tovisit, e->src->index);
1464
1465           if (visit && !(e->flags & EDGE_DFS_BACK))
1466             count++;
1467           else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1468             fprintf (dump_file,
1469                      "Irreducible region hit, ignoring edge to %i->%i\n",
1470                      e->src->index, bb->index);
1471         }
1472       BLOCK_INFO (bb)->npredecessors = count;
1473     }
1474
1475   memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1476   last = head;
1477   for (bb = head; bb; bb = nextbb)
1478     {
1479       edge_iterator ei;
1480       sreal cyclic_probability, frequency;
1481
1482       memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
1483       memcpy (&frequency, &real_zero, sizeof (real_zero));
1484
1485       nextbb = BLOCK_INFO (bb)->next;
1486       BLOCK_INFO (bb)->next = NULL;
1487
1488       /* Compute frequency of basic block.  */
1489       if (bb != head)
1490         {
1491 #ifdef ENABLE_CHECKING
1492           FOR_EACH_EDGE (e, ei, bb->preds)
1493             gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
1494                         || (e->flags & EDGE_DFS_BACK));
1495 #endif
1496
1497           FOR_EACH_EDGE (e, ei, bb->preds)
1498             if (EDGE_INFO (e)->back_edge)
1499               {
1500                 sreal_add (&cyclic_probability, &cyclic_probability,
1501                            &EDGE_INFO (e)->back_edge_prob);
1502               }
1503             else if (!(e->flags & EDGE_DFS_BACK))
1504               {
1505                 sreal tmp;
1506
1507                 /*  frequency += (e->probability
1508                                   * BLOCK_INFO (e->src)->frequency /
1509                                   REG_BR_PROB_BASE);  */
1510
1511                 sreal_init (&tmp, e->probability, 0);
1512                 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
1513                 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
1514                 sreal_add (&frequency, &frequency, &tmp);
1515               }
1516
1517           if (sreal_compare (&cyclic_probability, &real_zero) == 0)
1518             {
1519               memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
1520                       sizeof (frequency));
1521             }
1522           else
1523             {
1524               if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
1525                 {
1526                   memcpy (&cyclic_probability, &real_almost_one,
1527                           sizeof (real_almost_one));
1528                 }
1529
1530               /* BLOCK_INFO (bb)->frequency = frequency
1531                                               / (1 - cyclic_probability) */
1532
1533               sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
1534               sreal_div (&BLOCK_INFO (bb)->frequency,
1535                          &frequency, &cyclic_probability);
1536             }
1537         }
1538
1539       bitmap_clear_bit (tovisit, bb->index);
1540
1541       e = find_edge (bb, head);
1542       if (e)
1543         {
1544           sreal tmp;
1545             
1546           /* EDGE_INFO (e)->back_edge_prob
1547              = ((e->probability * BLOCK_INFO (bb)->frequency)
1548              / REG_BR_PROB_BASE); */
1549             
1550           sreal_init (&tmp, e->probability, 0);
1551           sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
1552           sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1553                      &tmp, &real_inv_br_prob_base);
1554         }
1555
1556       /* Propagate to successor blocks.  */
1557       FOR_EACH_EDGE (e, ei, bb->succs)
1558         if (!(e->flags & EDGE_DFS_BACK)
1559             && BLOCK_INFO (e->dest)->npredecessors)
1560           {
1561             BLOCK_INFO (e->dest)->npredecessors--;
1562             if (!BLOCK_INFO (e->dest)->npredecessors)
1563               {
1564                 if (!nextbb)
1565                   nextbb = e->dest;
1566                 else
1567                   BLOCK_INFO (last)->next = e->dest;
1568                 
1569                 last = e->dest;
1570               }
1571           }
1572     }
1573 }
1574
1575 /* Estimate probabilities of loopback edges in loops at same nest level.  */
1576
1577 static void
1578 estimate_loops_at_level (struct loop *first_loop)
1579 {
1580   struct loop *loop;
1581
1582   for (loop = first_loop; loop; loop = loop->next)
1583     {
1584       edge e;
1585       basic_block *bbs;
1586       unsigned i;
1587       bitmap tovisit = BITMAP_ALLOC (NULL);
1588
1589       estimate_loops_at_level (loop->inner);
1590
1591       /* Find current loop back edge and mark it.  */
1592       e = loop_latch_edge (loop);
1593       EDGE_INFO (e)->back_edge = 1;
1594
1595       bbs = get_loop_body (loop);
1596       for (i = 0; i < loop->num_nodes; i++)
1597         bitmap_set_bit (tovisit, bbs[i]->index);
1598       free (bbs);
1599       propagate_freq (loop->header, tovisit);
1600       BITMAP_FREE (tovisit);
1601     }
1602 }
1603
1604 /* Propates frequencies through structure of loops.  */
1605
1606 static void
1607 estimate_loops (void)
1608 {
1609   bitmap tovisit = BITMAP_ALLOC (NULL);
1610   basic_block bb;
1611
1612   /* Start by estimating the frequencies in the loops.  */
1613   if (current_loops)
1614     estimate_loops_at_level (current_loops->tree_root->inner);
1615
1616   /* Now propagate the frequencies through all the blocks.  */
1617   FOR_ALL_BB (bb)
1618     {
1619       bitmap_set_bit (tovisit, bb->index);
1620     }
1621   propagate_freq (ENTRY_BLOCK_PTR, tovisit);
1622   BITMAP_FREE (tovisit);
1623 }
1624
1625 /* Convert counts measured by profile driven feedback to frequencies.
1626    Return nonzero iff there was any nonzero execution count.  */
1627
1628 int
1629 counts_to_freqs (void)
1630 {
1631   gcov_type count_max, true_count_max = 0;
1632   basic_block bb;
1633
1634   FOR_EACH_BB (bb)
1635     true_count_max = MAX (bb->count, true_count_max);
1636
1637   count_max = MAX (true_count_max, 1);
1638   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1639     bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1640   return true_count_max;
1641 }
1642
1643 /* Return true if function is likely to be expensive, so there is no point to
1644    optimize performance of prologue, epilogue or do inlining at the expense
1645    of code size growth.  THRESHOLD is the limit of number of instructions
1646    function can execute at average to be still considered not expensive.  */
1647
1648 bool
1649 expensive_function_p (int threshold)
1650 {
1651   unsigned int sum = 0;
1652   basic_block bb;
1653   unsigned int limit;
1654
1655   /* We can not compute accurately for large thresholds due to scaled
1656      frequencies.  */
1657   gcc_assert (threshold <= BB_FREQ_MAX);
1658
1659   /* Frequencies are out of range.  This either means that function contains
1660      internal loop executing more than BB_FREQ_MAX times or profile feedback
1661      is available and function has not been executed at all.  */
1662   if (ENTRY_BLOCK_PTR->frequency == 0)
1663     return true;
1664
1665   /* Maximally BB_FREQ_MAX^2 so overflow won't happen.  */
1666   limit = ENTRY_BLOCK_PTR->frequency * threshold;
1667   FOR_EACH_BB (bb)
1668     {
1669       rtx insn;
1670
1671       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
1672            insn = NEXT_INSN (insn))
1673         if (active_insn_p (insn))
1674           {
1675             sum += bb->frequency;
1676             if (sum > limit)
1677               return true;
1678         }
1679     }
1680
1681   return false;
1682 }
1683
1684 /* Estimate basic blocks frequency by given branch probabilities.  */
1685
1686 static void
1687 estimate_bb_frequencies (void)
1688 {
1689   basic_block bb;
1690   sreal freq_max;
1691
1692   if (!flag_branch_probabilities || !counts_to_freqs ())
1693     {
1694       static int real_values_initialized = 0;
1695
1696       if (!real_values_initialized)
1697         {
1698           real_values_initialized = 1;
1699           sreal_init (&real_zero, 0, 0);
1700           sreal_init (&real_one, 1, 0);
1701           sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
1702           sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
1703           sreal_init (&real_one_half, 1, -1);
1704           sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
1705           sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
1706         }
1707
1708       mark_dfs_back_edges ();
1709
1710       single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
1711
1712       /* Set up block info for each basic block.  */
1713       alloc_aux_for_blocks (sizeof (struct block_info_def));
1714       alloc_aux_for_edges (sizeof (struct edge_info_def));
1715       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1716         {
1717           edge e;
1718           edge_iterator ei;
1719
1720           FOR_EACH_EDGE (e, ei, bb->succs)
1721             {
1722               sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
1723               sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1724                          &EDGE_INFO (e)->back_edge_prob,
1725                          &real_inv_br_prob_base);
1726             }
1727         }
1728
1729       /* First compute probabilities locally for each loop from innermost
1730          to outermost to examine probabilities for back edges.  */
1731       estimate_loops ();
1732
1733       memcpy (&freq_max, &real_zero, sizeof (real_zero));
1734       FOR_EACH_BB (bb)
1735         if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
1736           memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
1737
1738       sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
1739       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1740         {
1741           sreal tmp;
1742
1743           sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
1744           sreal_add (&tmp, &tmp, &real_one_half);
1745           bb->frequency = sreal_to_int (&tmp);
1746         }
1747
1748       free_aux_for_blocks ();
1749       free_aux_for_edges ();
1750     }
1751   compute_function_frequency ();
1752   if (flag_reorder_functions)
1753     choose_function_section ();
1754 }
1755
1756 /* Decide whether function is hot, cold or unlikely executed.  */
1757 static void
1758 compute_function_frequency (void)
1759 {
1760   basic_block bb;
1761
1762   if (!profile_info || !flag_branch_probabilities)
1763     return;
1764   cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1765   FOR_EACH_BB (bb)
1766     {
1767       if (maybe_hot_bb_p (bb))
1768         {
1769           cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
1770           return;
1771         }
1772       if (!probably_never_executed_bb_p (bb))
1773         cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
1774     }
1775 }
1776
1777 /* Choose appropriate section for the function.  */
1778 static void
1779 choose_function_section (void)
1780 {
1781   if (DECL_SECTION_NAME (current_function_decl)
1782       || !targetm.have_named_sections
1783       /* Theoretically we can split the gnu.linkonce text section too,
1784          but this requires more work as the frequency needs to match
1785          for all generated objects so we need to merge the frequency
1786          of all instances.  For now just never set frequency for these.  */
1787       || DECL_ONE_ONLY (current_function_decl))
1788     return;
1789
1790   /* If we are doing the partitioning optimization, let the optimization
1791      choose the correct section into which to put things.  */
1792
1793   if (flag_reorder_blocks_and_partition)
1794     return;
1795
1796   if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
1797     DECL_SECTION_NAME (current_function_decl) =
1798       build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
1799   if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
1800     DECL_SECTION_NAME (current_function_decl) =
1801       build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
1802                     UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
1803 }
1804
1805 static bool
1806 gate_estimate_probability (void)
1807 {
1808   return flag_guess_branch_prob;
1809 }
1810
1811 struct tree_opt_pass pass_profile = 
1812 {
1813   "profile",                            /* name */
1814   gate_estimate_probability,            /* gate */
1815   tree_estimate_probability,            /* execute */
1816   NULL,                                 /* sub */
1817   NULL,                                 /* next */
1818   0,                                    /* static_pass_number */
1819   TV_BRANCH_PROB,                       /* tv_id */
1820   PROP_cfg,                             /* properties_required */
1821   0,                                    /* properties_provided */
1822   0,                                    /* properties_destroyed */
1823   0,                                    /* todo_flags_start */
1824   TODO_ggc_collect | TODO_verify_ssa,                   /* todo_flags_finish */
1825   0                                     /* letter */
1826 };