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