gcc/predict.c

   1 /* Branch prediction routines for the GNU compiler.
   2    Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 /* References:
  22
  23    [1] "Branch Prediction for Free"
  24        Ball and Larus; PLDI '93.
  25    [2] "Static Branch Frequency and Program Profile Analysis"
  26        Wu and Larus; MICRO-27.
  27    [3] "Corpus-based Static Branch Prediction"
  28        Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.  */
  29
  30
  31 #include "config.h"
  32 #include "system.h"
  33 #include "coretypes.h"
  34 #include "tm.h"
  35 #include "tree.h"
  36 #include "rtl.h"
  37 #include "tm_p.h"
  38 #include "hard-reg-set.h"
  39 #include "basic-block.h"
  40 #include "insn-config.h"
  41 #include "regs.h"
  42 #include "flags.h"
  43 #include "output.h"
  44 #include "function.h"
  45 #include "except.h"
  46 #include "toplev.h"
  47 #include "recog.h"
  48 #include "expr.h"
  49 #include "predict.h"
  50 #include "coverage.h"
  51 #include "sreal.h"
  52 #include "params.h"
  53 #include "target.h"
  54 #include "loop.h"
  55 #include "cfgloop.h"
  56
  57 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
  58                    1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX.  */
  59 static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
  60              real_inv_br_prob_base, real_one_half, real_bb_freq_max;
  61
  62 /* Random guesstimation given names.  */
  63 #define PROB_VERY_UNLIKELY      (REG_BR_PROB_BASE / 10 - 1)
  64 #define PROB_EVEN               (REG_BR_PROB_BASE / 2)
  65 #define PROB_VERY_LIKELY        (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
  66 #define PROB_ALWAYS             (REG_BR_PROB_BASE)
  67
  68 static bool predicted_by_p (basic_block, enum br_predictor);
  69 static void combine_predictions_for_insn (rtx, basic_block);
  70 static void dump_prediction (enum br_predictor, int, basic_block, int);
  71 static void estimate_loops_at_level (struct loop *loop);
  72 static void propagate_freq (struct loop *);
  73 static void estimate_bb_frequencies (struct loops *);
  74 static void counts_to_freqs (void);
  75 static void process_note_predictions (basic_block, int *);
  76 static void process_note_prediction (basic_block, int *, int, int);
  77 static bool last_basic_block_p (basic_block);
  78 static void compute_function_frequency (void);
  79 static void choose_function_section (void);
  80 static bool can_predict_insn_p (rtx);
  81
  82 /* Information we hold about each branch predictor.
  83    Filled using information from predict.def.  */
  84
  85 struct predictor_info
  86 {
  87   const char *const name;       /* Name used in the debugging dumps.  */
  88   const int hitrate;            /* Expected hitrate used by
  89                                    predict_insn_def call.  */
  90   const int flags;
  91 };
  92
  93 /* Use given predictor without Dempster-Shaffer theory if it matches
  94    using first_match heuristics.  */
  95 #define PRED_FLAG_FIRST_MATCH 1
  96
  97 /* Recompute hitrate in percent to our representation.  */
  98
  99 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
 100
 101 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
 102 static const struct predictor_info predictor_info[]= {
 103 #include "predict.def"
 104
 105   /* Upper bound on predictors.  */
 106   {NULL, 0, 0}
 107 };
 108 #undef DEF_PREDICTOR
 109
 110 /* Return true in case BB can be CPU intensive and should be optimized
 111    for maximal performance.  */
 112
 113 bool
 114 maybe_hot_bb_p (basic_block bb)
 115 {
 116   if (profile_info && flag_branch_probabilities
 117       && (bb->count
 118           < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
 119     return false;
 120   if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
 121     return false;
 122   return true;
 123 }
 124
 125 /* Return true in case BB is cold and should be optimized for size.  */
 126
 127 bool
 128 probably_cold_bb_p (basic_block bb)
 129 {
 130   if (profile_info && flag_branch_probabilities
 131       && (bb->count
 132           < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
 133     return true;
 134   if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
 135     return true;
 136   return false;
 137 }
 138
 139 /* Return true in case BB is probably never executed.  */
 140 bool
 141 probably_never_executed_bb_p (basic_block bb)
 142 {
 143   if (profile_info && flag_branch_probabilities)
 144     return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
 145   return false;
 146 }
 147
 148 /* Return true if the one of outgoing edges is already predicted by
 149    PREDICTOR.  */
 150
 151 static bool
 152 predicted_by_p (basic_block bb, enum br_predictor predictor)
 153 {
 154   rtx note;
 155   if (!INSN_P (BB_END (bb)))
 156     return false;
 157   for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
 158     if (REG_NOTE_KIND (note) == REG_BR_PRED
 159         && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
 160       return true;
 161   return false;
 162 }
 163
 164 void
 165 predict_insn (rtx insn, enum br_predictor predictor, int probability)
 166 {
 167   if (!any_condjump_p (insn))
 168     abort ();
 169   if (!flag_guess_branch_prob)
 170     return;
 171
 172   REG_NOTES (insn)
 173     = gen_rtx_EXPR_LIST (REG_BR_PRED,
 174                          gen_rtx_CONCAT (VOIDmode,
 175                                          GEN_INT ((int) predictor),
 176                                          GEN_INT ((int) probability)),
 177                          REG_NOTES (insn));
 178 }
 179
 180 /* Predict insn by given predictor.  */
 181
 182 void
 183 predict_insn_def (rtx insn, enum br_predictor predictor,
 184                   enum prediction taken)
 185 {
 186    int probability = predictor_info[(int) predictor].hitrate;
 187
 188    if (taken != TAKEN)
 189      probability = REG_BR_PROB_BASE - probability;
 190
 191    predict_insn (insn, predictor, probability);
 192 }
 193
 194 /* Predict edge E with given probability if possible.  */
 195
 196 void
 197 predict_edge (edge e, enum br_predictor predictor, int probability)
 198 {
 199   rtx last_insn;
 200   last_insn = BB_END (e->src);
 201
 202   /* We can store the branch prediction information only about
 203      conditional jumps.  */
 204   if (!any_condjump_p (last_insn))
 205     return;
 206
 207   /* We always store probability of branching.  */
 208   if (e->flags & EDGE_FALLTHRU)
 209     probability = REG_BR_PROB_BASE - probability;
 210
 211   predict_insn (last_insn, predictor, probability);
 212 }
 213
 214 /* Return true when we can store prediction on insn INSN.
 215    At the moment we represent predictions only on conditional
 216    jumps, not at computed jump or other complicated cases.  */
 217 static bool
 218 can_predict_insn_p (rtx insn)
 219 {
 220   return (GET_CODE (insn) == JUMP_INSN
 221           && any_condjump_p (insn)
 222           && BLOCK_FOR_INSN (insn)->succ->succ_next);
 223 }
 224
 225 /* Predict edge E by given predictor if possible.  */
 226
 227 void
 228 predict_edge_def (edge e, enum br_predictor predictor,
 229                   enum prediction taken)
 230 {
 231    int probability = predictor_info[(int) predictor].hitrate;
 232
 233    if (taken != TAKEN)
 234      probability = REG_BR_PROB_BASE - probability;
 235
 236    predict_edge (e, predictor, probability);
 237 }
 238
 239 /* Invert all branch predictions or probability notes in the INSN.  This needs
 240    to be done each time we invert the condition used by the jump.  */
 241
 242 void
 243 invert_br_probabilities (rtx insn)
 244 {
 245   rtx note;
 246
 247   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 248     if (REG_NOTE_KIND (note) == REG_BR_PROB)
 249       XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
 250     else if (REG_NOTE_KIND (note) == REG_BR_PRED)
 251       XEXP (XEXP (note, 0), 1)
 252         = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
 253 }
 254
 255 /* Dump information about the branch prediction to the output file.  */
 256
 257 static void
 258 dump_prediction (enum br_predictor predictor, int probability,
 259                  basic_block bb, int used)
 260 {
 261   edge e = bb->succ;
 262
 263   if (!rtl_dump_file)
 264     return;
 265
 266   while (e && (e->flags & EDGE_FALLTHRU))
 267     e = e->succ_next;
 268
 269   fprintf (rtl_dump_file, "  %s heuristics%s: %.1f%%",
 270            predictor_info[predictor].name,
 271            used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
 272
 273   if (bb->count)
 274     {
 275       fprintf (rtl_dump_file, "  exec ");
 276       fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 277       if (e)
 278         {
 279           fprintf (rtl_dump_file, " hit ");
 280           fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 281           fprintf (rtl_dump_file, " (%.1f%%)", e->count * 100.0 / bb->count);
 282         }
 283     }
 284
 285   fprintf (rtl_dump_file, "\n");
 286 }
 287
 288 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
 289    note if not already present.  Remove now useless REG_BR_PRED notes.  */
 290
 291 static void
 292 combine_predictions_for_insn (rtx insn, basic_block bb)
 293 {
 294   rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
 295   rtx *pnote = &REG_NOTES (insn);
 296   rtx note;
 297   int best_probability = PROB_EVEN;
 298   int best_predictor = END_PREDICTORS;
 299   int combined_probability = REG_BR_PROB_BASE / 2;
 300   int d;
 301   bool first_match = false;
 302   bool found = false;
 303
 304   if (rtl_dump_file)
 305     fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
 306              bb->index);
 307
 308   /* We implement "first match" heuristics and use probability guessed
 309      by predictor with smallest index.  In the future we will use better
 310      probability combination techniques.  */
 311   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 312     if (REG_NOTE_KIND (note) == REG_BR_PRED)
 313       {
 314         int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
 315         int probability = INTVAL (XEXP (XEXP (note, 0), 1));
 316
 317         found = true;
 318         if (best_predictor > predictor)
 319           best_probability = probability, best_predictor = predictor;
 320
 321         d = (combined_probability * probability
 322              + (REG_BR_PROB_BASE - combined_probability)
 323              * (REG_BR_PROB_BASE - probability));
 324
 325         /* Use FP math to avoid overflows of 32bit integers.  */
 326         if (d == 0)
 327           /* If one probability is 0% and one 100%, avoid division by zero.  */
 328           combined_probability = REG_BR_PROB_BASE / 2;
 329         else
 330           combined_probability = (((double) combined_probability) * probability
 331                                   * REG_BR_PROB_BASE / d + 0.5);
 332       }
 333
 334   /* Decide which heuristic to use.  In case we didn't match anything,
 335      use no_prediction heuristic, in case we did match, use either
 336      first match or Dempster-Shaffer theory depending on the flags.  */
 337
 338   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
 339     first_match = true;
 340
 341   if (!found)
 342     dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true);
 343   else
 344     {
 345       dump_prediction (PRED_DS_THEORY, combined_probability, bb, !first_match);
 346       dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match);
 347     }
 348
 349   if (first_match)
 350     combined_probability = best_probability;
 351   dump_prediction (PRED_COMBINED, combined_probability, bb, true);
 352
 353   while (*pnote)
 354     {
 355       if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
 356         {
 357           int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
 358           int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
 359
 360           dump_prediction (predictor, probability, bb,
 361                            !first_match || best_predictor == predictor);
 362           *pnote = XEXP (*pnote, 1);
 363         }
 364       else
 365         pnote = &XEXP (*pnote, 1);
 366     }
 367
 368   if (!prob_note)
 369     {
 370       REG_NOTES (insn)
 371         = gen_rtx_EXPR_LIST (REG_BR_PROB,
 372                              GEN_INT (combined_probability), REG_NOTES (insn));
 373
 374       /* Save the prediction into CFG in case we are seeing non-degenerated
 375          conditional jump.  */
 376       if (bb->succ->succ_next)
 377         {
 378           BRANCH_EDGE (bb)->probability = combined_probability;
 379           FALLTHRU_EDGE (bb)->probability
 380             = REG_BR_PROB_BASE - combined_probability;
 381         }
 382     }
 383 }
 384
 385 /* Statically estimate the probability that a branch will be taken.
 386    ??? In the next revision there will be a number of other predictors added
 387    from the above references. Further, each heuristic will be factored out
 388    into its own function for clarity (and to facilitate the combination of
 389    predictions).  */
 390
 391 void
 392 estimate_probability (struct loops *loops_info)
 393 {
 394   basic_block bb;
 395   unsigned i;
 396
 397   connect_infinite_loops_to_exit ();
 398   calculate_dominance_info (CDI_DOMINATORS);
 399   calculate_dominance_info (CDI_POST_DOMINATORS);
 400
 401   /* Try to predict out blocks in a loop that are not part of a
 402      natural loop.  */
 403   for (i = 1; i < loops_info->num; i++)
 404     {
 405       basic_block bb, *bbs;
 406       unsigned j;
 407       int exits;
 408       struct loop *loop = loops_info->parray[i];
 409       struct loop_desc desc;
 410       unsigned HOST_WIDE_INT niter;
 411
 412       flow_loop_scan (loop, LOOP_EXIT_EDGES);
 413       exits = loop->num_exits;
 414
 415       if (simple_loop_p (loop, &desc) && desc.const_iter)
 416         {
 417           int prob;
 418           niter = desc.niter + 1;
 419           if (niter == 0)        /* We might overflow here.  */
 420             niter = desc.niter;
 421
 422           prob = (REG_BR_PROB_BASE
 423                   - (REG_BR_PROB_BASE + niter /2) / niter);
 424           /* Branch prediction algorithm gives 0 frequency for everything
 425              after the end of loop for loop having 0 probability to finish.  */
 426           if (prob == REG_BR_PROB_BASE)
 427             prob = REG_BR_PROB_BASE - 1;
 428           predict_edge (desc.in_edge, PRED_LOOP_ITERATIONS,
 429                         prob);
 430         }
 431
 432       bbs = get_loop_body (loop);
 433       for (j = 0; j < loop->num_nodes; j++)
 434         {
 435           int header_found = 0;
 436           edge e;
 437
 438           bb = bbs[j];
 439
 440           /* Bypass loop heuristics on continue statement.  These
 441              statements construct loops via "non-loop" constructs
 442              in the source language and are better to be handled
 443              separately.  */
 444           if (!can_predict_insn_p (BB_END (bb))
 445               || predicted_by_p (bb, PRED_CONTINUE))
 446             continue;
 447
 448           /* Loop branch heuristics - predict an edge back to a
 449              loop's head as taken.  */
 450           for (e = bb->succ; e; e = e->succ_next)
 451             if (e->dest == loop->header
 452                 && e->src == loop->latch)
 453               {
 454                 header_found = 1;
 455                 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
 456               }
 457
 458           /* Loop exit heuristics - predict an edge exiting the loop if the
 459              conditional has no loop header successors as not taken.  */
 460           if (!header_found)
 461             for (e = bb->succ; e; e = e->succ_next)
 462               if (e->dest->index < 0
 463                   || !flow_bb_inside_loop_p (loop, e->dest))
 464                 predict_edge
 465                   (e, PRED_LOOP_EXIT,
 466                    (REG_BR_PROB_BASE
 467                     - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
 468                    / exits);
 469         }
 470     }
 471
 472   /* Attempt to predict conditional jumps using a number of heuristics.  */
 473   FOR_EACH_BB (bb)
 474     {
 475       rtx last_insn = BB_END (bb);
 476       rtx cond, earliest;
 477       edge e;
 478
 479       if (! can_predict_insn_p (last_insn))
 480         continue;
 481
 482       for (e = bb->succ; e; e = e->succ_next)
 483         {
 484           /* Predict early returns to be probable, as we've already taken
 485              care for error returns and other are often used for fast paths
 486              trought function.  */
 487           if ((e->dest == EXIT_BLOCK_PTR
 488                || (e->dest->succ && !e->dest->succ->succ_next
 489                    && e->dest->succ->dest == EXIT_BLOCK_PTR))
 490                && !predicted_by_p (bb, PRED_NULL_RETURN)
 491                && !predicted_by_p (bb, PRED_CONST_RETURN)
 492                && !predicted_by_p (bb, PRED_NEGATIVE_RETURN)
 493                && !last_basic_block_p (e->dest))
 494             predict_edge_def (e, PRED_EARLY_RETURN, TAKEN);
 495
 496           /* Look for block we are guarding (ie we dominate it,
 497              but it doesn't postdominate us).  */
 498           if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
 499               && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
 500               && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
 501             {
 502               rtx insn;
 503
 504               /* The call heuristic claims that a guarded function call
 505                  is improbable.  This is because such calls are often used
 506                  to signal exceptional situations such as printing error
 507                  messages.  */
 508               for (insn = BB_HEAD (e->dest); insn != NEXT_INSN (BB_END (e->dest));
 509                    insn = NEXT_INSN (insn))
 510                 if (GET_CODE (insn) == CALL_INSN
 511                     /* Constant and pure calls are hardly used to signalize
 512                        something exceptional.  */
 513                     && ! CONST_OR_PURE_CALL_P (insn))
 514                   {
 515                     predict_edge_def (e, PRED_CALL, NOT_TAKEN);
 516                     break;
 517                   }
 518             }
 519         }
 520
 521       cond = get_condition (last_insn, &earliest, false);
 522       if (! cond)
 523         continue;
 524
 525       /* Try "pointer heuristic."
 526          A comparison ptr == 0 is predicted as false.
 527          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 528       if (GET_RTX_CLASS (GET_CODE (cond)) == '<'
 529           && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
 530               || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
 531         {
 532           if (GET_CODE (cond) == EQ)
 533             predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
 534           else if (GET_CODE (cond) == NE)
 535             predict_insn_def (last_insn, PRED_POINTER, TAKEN);
 536         }
 537       else
 538
 539       /* Try "opcode heuristic."
 540          EQ tests are usually false and NE tests are usually true. Also,
 541          most quantities are positive, so we can make the appropriate guesses
 542          about signed comparisons against zero.  */
 543         switch (GET_CODE (cond))
 544           {
 545           case CONST_INT:
 546             /* Unconditional branch.  */
 547             predict_insn_def (last_insn, PRED_UNCONDITIONAL,
 548                               cond == const0_rtx ? NOT_TAKEN : TAKEN);
 549             break;
 550
 551           case EQ:
 552           case UNEQ:
 553             /* Floating point comparisons appears to behave in a very
 554                unpredictable way because of special role of = tests in
 555                FP code.  */
 556             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 557               ;
 558             /* Comparisons with 0 are often used for booleans and there is
 559                nothing useful to predict about them.  */
 560             else if (XEXP (cond, 1) == const0_rtx
 561                      || XEXP (cond, 0) == const0_rtx)
 562               ;
 563             else
 564               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
 565             break;
 566
 567           case NE:
 568           case LTGT:
 569             /* Floating point comparisons appears to behave in a very
 570                unpredictable way because of special role of = tests in
 571                FP code.  */
 572             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 573               ;
 574             /* Comparisons with 0 are often used for booleans and there is
 575                nothing useful to predict about them.  */
 576             else if (XEXP (cond, 1) == const0_rtx
 577                      || XEXP (cond, 0) == const0_rtx)
 578               ;
 579             else
 580               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
 581             break;
 582
 583           case ORDERED:
 584             predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
 585             break;
 586
 587           case UNORDERED:
 588             predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
 589             break;
 590
 591           case LE:
 592           case LT:
 593             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 594                 || XEXP (cond, 1) == constm1_rtx)
 595               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
 596             break;
 597
 598           case GE:
 599           case GT:
 600             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 601                 || XEXP (cond, 1) == constm1_rtx)
 602               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
 603             break;
 604
 605           default:
 606             break;
 607           }
 608     }
 609
 610   /* Attach the combined probability to each conditional jump.  */
 611   FOR_EACH_BB (bb)
 612     if (GET_CODE (BB_END (bb)) == JUMP_INSN
 613         && any_condjump_p (BB_END (bb))
 614         && bb->succ->succ_next != NULL)
 615       combine_predictions_for_insn (BB_END (bb), bb);
 616
 617   free_dominance_info (CDI_POST_DOMINATORS);
 618
 619   remove_fake_edges ();
 620   estimate_bb_frequencies (loops_info);
 621 }
 622 \f
 623 /* __builtin_expect dropped tokens into the insn stream describing expected
 624    values of registers.  Generate branch probabilities based off these
 625    values.  */
 626
 627 void
 628 expected_value_to_br_prob (void)
 629 {
 630   rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
 631
 632   for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
 633     {
 634       switch (GET_CODE (insn))
 635         {
 636         case NOTE:
 637           /* Look for expected value notes.  */
 638           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
 639             {
 640               ev = NOTE_EXPECTED_VALUE (insn);
 641               ev_reg = XEXP (ev, 0);
 642               delete_insn (insn);
 643             }
 644           continue;
 645
 646         case CODE_LABEL:
 647           /* Never propagate across labels.  */
 648           ev = NULL_RTX;
 649           continue;
 650
 651         case JUMP_INSN:
 652           /* Look for simple conditional branches.  If we haven't got an
 653              expected value yet, no point going further.  */
 654           if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX
 655               || ! any_condjump_p (insn))
 656             continue;
 657           break;
 658
 659         default:
 660           /* Look for insns that clobber the EV register.  */
 661           if (ev && reg_set_p (ev_reg, insn))
 662             ev = NULL_RTX;
 663           continue;
 664         }
 665
 666       /* Collect the branch condition, hopefully relative to EV_REG.  */
 667       /* ???  At present we'll miss things like
 668                 (expected_value (eq r70 0))
 669                 (set r71 -1)
 670                 (set r80 (lt r70 r71))
 671                 (set pc (if_then_else (ne r80 0) ...))
 672          as canonicalize_condition will render this to us as
 673                 (lt r70, r71)
 674          Could use cselib to try and reduce this further.  */
 675       cond = XEXP (SET_SRC (pc_set (insn)), 0);
 676       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg, false);
 677       if (! cond || XEXP (cond, 0) != ev_reg
 678           || GET_CODE (XEXP (cond, 1)) != CONST_INT)
 679         continue;
 680
 681       /* Substitute and simplify.  Given that the expression we're
 682          building involves two constants, we should wind up with either
 683          true or false.  */
 684       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 685                              XEXP (ev, 1), XEXP (cond, 1));
 686       cond = simplify_rtx (cond);
 687
 688       /* Turn the condition into a scaled branch probability.  */
 689       if (cond != const_true_rtx && cond != const0_rtx)
 690         abort ();
 691       predict_insn_def (insn, PRED_BUILTIN_EXPECT,
 692                         cond == const_true_rtx ? TAKEN : NOT_TAKEN);
 693     }
 694 }
 695 \f
 696 /* Check whether this is the last basic block of function.  Commonly
 697    there is one extra common cleanup block.  */
 698 static bool
 699 last_basic_block_p (basic_block bb)
 700 {
 701   if (bb == EXIT_BLOCK_PTR)
 702     return false;
 703
 704   return (bb->next_bb == EXIT_BLOCK_PTR
 705           || (bb->next_bb->next_bb == EXIT_BLOCK_PTR
 706               && bb->succ && !bb->succ->succ_next
 707               && bb->succ->dest->next_bb == EXIT_BLOCK_PTR));
 708 }
 709
 710 /* Sets branch probabilities according to PREDiction and
 711    FLAGS. HEADS[bb->index] should be index of basic block in that we
 712    need to alter branch predictions (i.e. the first of our dominators
 713    such that we do not post-dominate it) (but we fill this information
 714    on demand, so -1 may be there in case this was not needed yet).  */
 715
 716 static void
 717 process_note_prediction (basic_block bb, int *heads, int pred, int flags)
 718 {
 719   edge e;
 720   int y;
 721   bool taken;
 722
 723   taken = flags & IS_TAKEN;
 724
 725   if (heads[bb->index] < 0)
 726     {
 727       /* This is first time we need this field in heads array; so
 728          find first dominator that we do not post-dominate (we are
 729          using already known members of heads array).  */
 730       basic_block ai = bb;
 731       basic_block next_ai = get_immediate_dominator (CDI_DOMINATORS, bb);
 732       int head;
 733
 734       while (heads[next_ai->index] < 0)
 735         {
 736           if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
 737             break;
 738           heads[next_ai->index] = ai->index;
 739           ai = next_ai;
 740           next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai);
 741         }
 742       if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
 743         head = next_ai->index;
 744       else
 745         head = heads[next_ai->index];
 746       while (next_ai != bb)
 747         {
 748           next_ai = ai;
 749           if (heads[ai->index] == ENTRY_BLOCK)
 750             ai = ENTRY_BLOCK_PTR;
 751           else
 752             ai = BASIC_BLOCK (heads[ai->index]);
 753           heads[next_ai->index] = head;
 754         }
 755     }
 756   y = heads[bb->index];
 757
 758   /* Now find the edge that leads to our branch and aply the prediction.  */
 759
 760   if (y == last_basic_block || !can_predict_insn_p (BB_END (BASIC_BLOCK (y))))
 761     return;
 762   for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
 763     if (e->dest->index >= 0
 764         && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb))
 765       predict_edge_def (e, pred, taken);
 766 }
 767
 768 /* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them
 769    into branch probabilities.  For description of heads array, see
 770    process_note_prediction.  */
 771
 772 static void
 773 process_note_predictions (basic_block bb, int *heads)
 774 {
 775   rtx insn;
 776   edge e;
 777
 778   /* Additionally, we check here for blocks with no successors.  */
 779   int contained_noreturn_call = 0;
 780   int was_bb_head = 0;
 781   int noreturn_block = 1;
 782
 783   for (insn = BB_END (bb); insn;
 784        was_bb_head |= (insn == BB_HEAD (bb)), insn = PREV_INSN (insn))
 785     {
 786       if (GET_CODE (insn) != NOTE)
 787         {
 788           if (was_bb_head)
 789             break;
 790           else
 791             {
 792               /* Noreturn calls cause program to exit, therefore they are
 793                  always predicted as not taken.  */
 794               if (GET_CODE (insn) == CALL_INSN
 795                   && find_reg_note (insn, REG_NORETURN, NULL))
 796                 contained_noreturn_call = 1;
 797               continue;
 798             }
 799         }
 800       if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION)
 801         {
 802           int alg = (int) NOTE_PREDICTION_ALG (insn);
 803           /* Process single prediction note.  */
 804           process_note_prediction (bb,
 805                                    heads,
 806                                    alg, (int) NOTE_PREDICTION_FLAGS (insn));
 807           delete_insn (insn);
 808         }
 809     }
 810   for (e = bb->succ; e; e = e->succ_next)
 811     if (!(e->flags & EDGE_FAKE))
 812       noreturn_block = 0;
 813   if (contained_noreturn_call)
 814     {
 815       /* This block ended from other reasons than because of return.
 816          If it is because of noreturn call, this should certainly not
 817          be taken.  Otherwise it is probably some error recovery.  */
 818       process_note_prediction (bb, heads, PRED_NORETURN, NOT_TAKEN);
 819     }
 820 }
 821
 822 /* Gathers NOTE_INSN_PREDICTIONs and turns them into
 823    branch probabilities.  */
 824
 825 void
 826 note_prediction_to_br_prob (void)
 827 {
 828   basic_block bb;
 829   int *heads;
 830
 831   /* To enable handling of noreturn blocks.  */
 832   add_noreturn_fake_exit_edges ();
 833   connect_infinite_loops_to_exit ();
 834
 835   calculate_dominance_info (CDI_POST_DOMINATORS);
 836   calculate_dominance_info (CDI_DOMINATORS);
 837
 838   heads = xmalloc (sizeof (int) * last_basic_block);
 839   memset (heads, -1, sizeof (int) * last_basic_block);
 840   heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
 841
 842   /* Process all prediction notes.  */
 843
 844   FOR_EACH_BB (bb)
 845     process_note_predictions (bb, heads);
 846
 847   free_dominance_info (CDI_POST_DOMINATORS);
 848   free_dominance_info (CDI_DOMINATORS);
 849   free (heads);
 850
 851   remove_fake_edges ();
 852 }
 853 \f
 854 /* This is used to carry information about basic blocks.  It is
 855    attached to the AUX field of the standard CFG block.  */
 856
 857 typedef struct block_info_def
 858 {
 859   /* Estimated frequency of execution of basic_block.  */
 860   sreal frequency;
 861
 862   /* To keep queue of basic blocks to process.  */
 863   basic_block next;
 864
 865   /* True if block needs to be visited in propagate_freq.  */
 866   unsigned int tovisit:1;
 867
 868   /* Number of predecessors we need to visit first.  */
 869   int npredecessors;
 870 } *block_info;
 871
 872 /* Similar information for edges.  */
 873 typedef struct edge_info_def
 874 {
 875   /* In case edge is an loopback edge, the probability edge will be reached
 876      in case header is.  Estimated number of iterations of the loop can be
 877      then computed as 1 / (1 - back_edge_prob).  */
 878   sreal back_edge_prob;
 879   /* True if the edge is an loopback edge in the natural loop.  */
 880   unsigned int back_edge:1;
 881 } *edge_info;
 882
 883 #define BLOCK_INFO(B)   ((block_info) (B)->aux)
 884 #define EDGE_INFO(E)    ((edge_info) (E)->aux)
 885
 886 /* Helper function for estimate_bb_frequencies.
 887    Propagate the frequencies for LOOP.  */
 888
 889 static void
 890 propagate_freq (struct loop *loop)
 891 {
 892   basic_block head = loop->header;
 893   basic_block bb;
 894   basic_block last;
 895   edge e;
 896   basic_block nextbb;
 897
 898   /* For each basic block we need to visit count number of his predecessors
 899      we need to visit first.  */
 900   FOR_EACH_BB (bb)
 901     {
 902       if (BLOCK_INFO (bb)->tovisit)
 903         {
 904           int count = 0;
 905
 906           for (e = bb->pred; e; e = e->pred_next)
 907             if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
 908               count++;
 909             else if (BLOCK_INFO (e->src)->tovisit
 910                      && rtl_dump_file && !EDGE_INFO (e)->back_edge)
 911               fprintf (rtl_dump_file,
 912                        "Irreducible region hit, ignoring edge to %i->%i\n",
 913                        e->src->index, bb->index);
 914           BLOCK_INFO (bb)->npredecessors = count;
 915         }
 916     }
 917
 918   memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
 919   last = head;
 920   for (bb = head; bb; bb = nextbb)
 921     {
 922       sreal cyclic_probability, frequency;
 923
 924       memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
 925       memcpy (&frequency, &real_zero, sizeof (real_zero));
 926
 927       nextbb = BLOCK_INFO (bb)->next;
 928       BLOCK_INFO (bb)->next = NULL;
 929
 930       /* Compute frequency of basic block.  */
 931       if (bb != head)
 932         {
 933 #ifdef ENABLE_CHECKING
 934           for (e = bb->pred; e; e = e->pred_next)
 935             if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
 936               abort ();
 937 #endif
 938
 939           for (e = bb->pred; e; e = e->pred_next)
 940             if (EDGE_INFO (e)->back_edge)
 941               {
 942                 sreal_add (&cyclic_probability, &cyclic_probability,
 943                            &EDGE_INFO (e)->back_edge_prob);
 944               }
 945             else if (!(e->flags & EDGE_DFS_BACK))
 946               {
 947                 sreal tmp;
 948
 949                 /*  frequency += (e->probability
 950                                   * BLOCK_INFO (e->src)->frequency /
 951                                   REG_BR_PROB_BASE);  */
 952
 953                 sreal_init (&tmp, e->probability, 0);
 954                 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
 955                 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
 956                 sreal_add (&frequency, &frequency, &tmp);
 957               }
 958
 959           if (sreal_compare (&cyclic_probability, &real_zero) == 0)
 960             {
 961               memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
 962                       sizeof (frequency));
 963             }
 964           else
 965             {
 966               if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
 967                 {
 968                   memcpy (&cyclic_probability, &real_almost_one,
 969                           sizeof (real_almost_one));
 970                 }
 971
 972               /* BLOCK_INFO (bb)->frequency = frequency
 973                                               / (1 - cyclic_probability) */
 974
 975               sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
 976               sreal_div (&BLOCK_INFO (bb)->frequency,
 977                          &frequency, &cyclic_probability);
 978             }
 979         }
 980
 981       BLOCK_INFO (bb)->tovisit = 0;
 982
 983       /* Compute back edge frequencies.  */
 984       for (e = bb->succ; e; e = e->succ_next)
 985         if (e->dest == head)
 986           {
 987             sreal tmp;
 988
 989             /* EDGE_INFO (e)->back_edge_prob
 990                   = ((e->probability * BLOCK_INFO (bb)->frequency)
 991                      / REG_BR_PROB_BASE); */
 992
 993             sreal_init (&tmp, e->probability, 0);
 994             sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
 995             sreal_mul (&EDGE_INFO (e)->back_edge_prob,
 996                        &tmp, &real_inv_br_prob_base);
 997           }
 998
 999       /* Propagate to successor blocks.  */
1000       for (e = bb->succ; e; e = e->succ_next)
1001         if (!(e->flags & EDGE_DFS_BACK)
1002             && BLOCK_INFO (e->dest)->npredecessors)
1003           {
1004             BLOCK_INFO (e->dest)->npredecessors--;
1005             if (!BLOCK_INFO (e->dest)->npredecessors)
1006               {
1007                 if (!nextbb)
1008                   nextbb = e->dest;
1009                 else
1010                   BLOCK_INFO (last)->next = e->dest;
1011
1012                 last = e->dest;
1013               }
1014            }
1015     }
1016 }
1017
1018 /* Estimate probabilities of loopback edges in loops at same nest level.  */
1019
1020 static void
1021 estimate_loops_at_level (struct loop *first_loop)
1022 {
1023   struct loop *loop;
1024
1025   for (loop = first_loop; loop; loop = loop->next)
1026     {
1027       edge e;
1028       basic_block *bbs;
1029       unsigned i;
1030
1031       estimate_loops_at_level (loop->inner);
1032
1033       if (loop->latch->succ)  /* Do not do this for dummy function loop.  */
1034         {
1035           /* Find current loop back edge and mark it.  */
1036           e = loop_latch_edge (loop);
1037           EDGE_INFO (e)->back_edge = 1;
1038        }
1039
1040       bbs = get_loop_body (loop);
1041       for (i = 0; i < loop->num_nodes; i++)
1042         BLOCK_INFO (bbs[i])->tovisit = 1;
1043       free (bbs);
1044       propagate_freq (loop);
1045     }
1046 }
1047
1048 /* Convert counts measured by profile driven feedback to frequencies.  */
1049
1050 static void
1051 counts_to_freqs (void)
1052 {
1053   gcov_type count_max = 1;
1054   basic_block bb;
1055
1056   FOR_EACH_BB (bb)
1057     count_max = MAX (bb->count, count_max);
1058
1059   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1060     bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1061 }
1062
1063 /* Return true if function is likely to be expensive, so there is no point to
1064    optimize performance of prologue, epilogue or do inlining at the expense
1065    of code size growth.  THRESHOLD is the limit of number of instructions
1066    function can execute at average to be still considered not expensive.  */
1067
1068 bool
1069 expensive_function_p (int threshold)
1070 {
1071   unsigned int sum = 0;
1072   basic_block bb;
1073   unsigned int limit;
1074
1075   /* We can not compute accurately for large thresholds due to scaled
1076      frequencies.  */
1077   if (threshold > BB_FREQ_MAX)
1078     abort ();
1079
1080   /* Frequencies are out of range.  This either means that function contains
1081      internal loop executing more than BB_FREQ_MAX times or profile feedback
1082      is available and function has not been executed at all.  */
1083   if (ENTRY_BLOCK_PTR->frequency == 0)
1084     return true;
1085
1086   /* Maximally BB_FREQ_MAX^2 so overflow won't happen.  */
1087   limit = ENTRY_BLOCK_PTR->frequency * threshold;
1088   FOR_EACH_BB (bb)
1089     {
1090       rtx insn;
1091
1092       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
1093            insn = NEXT_INSN (insn))
1094         if (active_insn_p (insn))
1095           {
1096             sum += bb->frequency;
1097             if (sum > limit)
1098               return true;
1099         }
1100     }
1101
1102   return false;
1103 }
1104
1105 /* Estimate basic blocks frequency by given branch probabilities.  */
1106
1107 static void
1108 estimate_bb_frequencies (struct loops *loops)
1109 {
1110   basic_block bb;
1111   sreal freq_max;
1112
1113   if (flag_branch_probabilities)
1114     counts_to_freqs ();
1115   else
1116     {
1117       static int real_values_initialized = 0;
1118
1119       if (!real_values_initialized)
1120         {
1121           real_values_initialized = 1;
1122           sreal_init (&real_zero, 0, 0);
1123           sreal_init (&real_one, 1, 0);
1124           sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
1125           sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
1126           sreal_init (&real_one_half, 1, -1);
1127           sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
1128           sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
1129         }
1130
1131       mark_dfs_back_edges ();
1132       /* Fill in the probability values in flowgraph based on the REG_BR_PROB
1133          notes.  */
1134       FOR_EACH_BB (bb)
1135         {
1136           rtx last_insn = BB_END (bb);
1137
1138           if (!can_predict_insn_p (last_insn))
1139             {
1140               /* We can predict only conditional jumps at the moment.
1141                  Expect each edge to be equally probable.
1142                  ?? In the future we want to make abnormal edges improbable.  */
1143               int nedges = 0;
1144               edge e;
1145
1146               for (e = bb->succ; e; e = e->succ_next)
1147                 {
1148                   nedges++;
1149                   if (e->probability != 0)
1150                     break;
1151                 }
1152               if (!e)
1153                 for (e = bb->succ; e; e = e->succ_next)
1154                   e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
1155             }
1156         }
1157
1158       ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
1159
1160       /* Set up block info for each basic block.  */
1161       alloc_aux_for_blocks (sizeof (struct block_info_def));
1162       alloc_aux_for_edges (sizeof (struct edge_info_def));
1163       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1164         {
1165           edge e;
1166
1167           BLOCK_INFO (bb)->tovisit = 0;
1168           for (e = bb->succ; e; e = e->succ_next)
1169             {
1170               sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
1171               sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1172                          &EDGE_INFO (e)->back_edge_prob,
1173                          &real_inv_br_prob_base);
1174             }
1175         }
1176
1177       /* First compute probabilities locally for each loop from innermost
1178          to outermost to examine probabilities for back edges.  */
1179       estimate_loops_at_level (loops->tree_root);
1180
1181       memcpy (&freq_max, &real_zero, sizeof (real_zero));
1182       FOR_EACH_BB (bb)
1183         if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
1184           memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
1185
1186       sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
1187       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1188         {
1189           sreal tmp;
1190
1191           sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
1192           sreal_add (&tmp, &tmp, &real_one_half);
1193           bb->frequency = sreal_to_int (&tmp);
1194         }
1195
1196       free_aux_for_blocks ();
1197       free_aux_for_edges ();
1198     }
1199   compute_function_frequency ();
1200   if (flag_reorder_functions)
1201     choose_function_section ();
1202 }
1203
1204 /* Decide whether function is hot, cold or unlikely executed.  */
1205 static void
1206 compute_function_frequency (void)
1207 {
1208   basic_block bb;
1209
1210   if (!profile_info || !flag_branch_probabilities)
1211     return;
1212   cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1213   FOR_EACH_BB (bb)
1214     {
1215       if (maybe_hot_bb_p (bb))
1216         {
1217           cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
1218           return;
1219         }
1220       if (!probably_never_executed_bb_p (bb))
1221         cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
1222     }
1223 }
1224
1225 /* Choose appropriate section for the function.  */
1226 static void
1227 choose_function_section (void)
1228 {
1229   if (DECL_SECTION_NAME (current_function_decl)
1230       || !targetm.have_named_sections
1231       /* Theoretically we can split the gnu.linkonce text section too,
1232          but this requires more work as the frequency needs to match
1233          for all generated objects so we need to merge the frequency
1234          of all instances.  For now just never set frequency for these.  */
1235       || DECL_ONE_ONLY (current_function_decl))
1236     return;
1237   if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
1238     DECL_SECTION_NAME (current_function_decl) =
1239       build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
1240   if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
1241     DECL_SECTION_NAME (current_function_decl) =
1242       build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
1243                     UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
1244 }