OSDN Git Service

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