gcc/predict.c

   1 /* Branch prediction routines for the GNU compiler.
   2    Copyright (C) 2000, 2001, 2002, 2003, 2004 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 int 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 (!dump_file)
 264     return;
 265
 266   while (e && (e->flags & EDGE_FALLTHRU))
 267     e = e->succ_next;
 268
 269   fprintf (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 (dump_file, "  exec ");
 276       fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 277       if (e)
 278         {
 279           fprintf (dump_file, " hit ");
 280           fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 281           fprintf (dump_file, " (%.1f%%)", e->count * 100.0 / bb->count);
 282         }
 283     }
 284
 285   fprintf (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 (dump_file)
 305     fprintf (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 niter_desc desc;
 410       unsigned HOST_WIDE_INT niter;
 411
 412       flow_loop_scan (loop, LOOP_EXIT_EDGES);
 413       exits = loop->num_exits;
 414
 415       iv_analysis_loop_init (loop);
 416       find_simple_exit (loop, &desc);
 417
 418       if (desc.simple_p && desc.const_iter)
 419         {
 420           int prob;
 421           niter = desc.niter + 1;
 422           if (niter == 0)        /* We might overflow here.  */
 423             niter = desc.niter;
 424
 425           prob = (REG_BR_PROB_BASE
 426                   - (REG_BR_PROB_BASE + niter /2) / niter);
 427           /* Branch prediction algorithm gives 0 frequency for everything
 428              after the end of loop for loop having 0 probability to finish.  */
 429           if (prob == REG_BR_PROB_BASE)
 430             prob = REG_BR_PROB_BASE - 1;
 431           predict_edge (desc.in_edge, PRED_LOOP_ITERATIONS,
 432                         prob);
 433         }
 434
 435       bbs = get_loop_body (loop);
 436       for (j = 0; j < loop->num_nodes; j++)
 437         {
 438           int header_found = 0;
 439           edge e;
 440
 441           bb = bbs[j];
 442
 443           /* Bypass loop heuristics on continue statement.  These
 444              statements construct loops via "non-loop" constructs
 445              in the source language and are better to be handled
 446              separately.  */
 447           if (!can_predict_insn_p (BB_END (bb))
 448               || predicted_by_p (bb, PRED_CONTINUE))
 449             continue;
 450
 451           /* Loop branch heuristics - predict an edge back to a
 452              loop's head as taken.  */
 453           for (e = bb->succ; e; e = e->succ_next)
 454             if (e->dest == loop->header
 455                 && e->src == loop->latch)
 456               {
 457                 header_found = 1;
 458                 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
 459               }
 460
 461           /* Loop exit heuristics - predict an edge exiting the loop if the
 462              conditional has no loop header successors as not taken.  */
 463           if (!header_found)
 464             for (e = bb->succ; e; e = e->succ_next)
 465               if (e->dest->index < 0
 466                   || !flow_bb_inside_loop_p (loop, e->dest))
 467                 predict_edge
 468                   (e, PRED_LOOP_EXIT,
 469                    (REG_BR_PROB_BASE
 470                     - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
 471                    / exits);
 472         }
 473
 474       /* Free basic blocks from get_loop_body.  */
 475       free (bbs);
 476     }
 477
 478   iv_analysis_done ();
 479
 480   /* Attempt to predict conditional jumps using a number of heuristics.  */
 481   FOR_EACH_BB (bb)
 482     {
 483       rtx last_insn = BB_END (bb);
 484       rtx cond, earliest;
 485       edge e;
 486
 487       if (! can_predict_insn_p (last_insn))
 488         continue;
 489
 490       for (e = bb->succ; e; e = e->succ_next)
 491         {
 492           /* Predict early returns to be probable, as we've already taken
 493              care for error returns and other are often used for fast paths
 494              trought function.  */
 495           if ((e->dest == EXIT_BLOCK_PTR
 496                || (e->dest->succ && !e->dest->succ->succ_next
 497                    && e->dest->succ->dest == EXIT_BLOCK_PTR))
 498                && !predicted_by_p (bb, PRED_NULL_RETURN)
 499                && !predicted_by_p (bb, PRED_CONST_RETURN)
 500                && !predicted_by_p (bb, PRED_NEGATIVE_RETURN)
 501                && !last_basic_block_p (e->dest))
 502             predict_edge_def (e, PRED_EARLY_RETURN, TAKEN);
 503
 504           /* Look for block we are guarding (ie we dominate it,
 505              but it doesn't postdominate us).  */
 506           if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
 507               && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
 508               && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
 509             {
 510               rtx insn;
 511
 512               /* The call heuristic claims that a guarded function call
 513                  is improbable.  This is because such calls are often used
 514                  to signal exceptional situations such as printing error
 515                  messages.  */
 516               for (insn = BB_HEAD (e->dest); insn != NEXT_INSN (BB_END (e->dest));
 517                    insn = NEXT_INSN (insn))
 518                 if (GET_CODE (insn) == CALL_INSN
 519                     /* Constant and pure calls are hardly used to signalize
 520                        something exceptional.  */
 521                     && ! CONST_OR_PURE_CALL_P (insn))
 522                   {
 523                     predict_edge_def (e, PRED_CALL, NOT_TAKEN);
 524                     break;
 525                   }
 526             }
 527         }
 528
 529       cond = get_condition (last_insn, &earliest, false);
 530       if (! cond)
 531         continue;
 532
 533       /* Try "pointer heuristic."
 534          A comparison ptr == 0 is predicted as false.
 535          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 536       if (COMPARISON_P (cond)
 537           && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
 538               || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
 539         {
 540           if (GET_CODE (cond) == EQ)
 541             predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
 542           else if (GET_CODE (cond) == NE)
 543             predict_insn_def (last_insn, PRED_POINTER, TAKEN);
 544         }
 545       else
 546
 547       /* Try "opcode heuristic."
 548          EQ tests are usually false and NE tests are usually true. Also,
 549          most quantities are positive, so we can make the appropriate guesses
 550          about signed comparisons against zero.  */
 551         switch (GET_CODE (cond))
 552           {
 553           case CONST_INT:
 554             /* Unconditional branch.  */
 555             predict_insn_def (last_insn, PRED_UNCONDITIONAL,
 556                               cond == const0_rtx ? NOT_TAKEN : TAKEN);
 557             break;
 558
 559           case EQ:
 560           case UNEQ:
 561             /* Floating point comparisons appears to behave in a very
 562                unpredictable way because of special role of = tests in
 563                FP code.  */
 564             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 565               ;
 566             /* Comparisons with 0 are often used for booleans and there is
 567                nothing useful to predict about them.  */
 568             else if (XEXP (cond, 1) == const0_rtx
 569                      || XEXP (cond, 0) == const0_rtx)
 570               ;
 571             else
 572               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
 573             break;
 574
 575           case NE:
 576           case LTGT:
 577             /* Floating point comparisons appears to behave in a very
 578                unpredictable way because of special role of = tests in
 579                FP code.  */
 580             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 581               ;
 582             /* Comparisons with 0 are often used for booleans and there is
 583                nothing useful to predict about them.  */
 584             else if (XEXP (cond, 1) == const0_rtx
 585                      || XEXP (cond, 0) == const0_rtx)
 586               ;
 587             else
 588               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
 589             break;
 590
 591           case ORDERED:
 592             predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
 593             break;
 594
 595           case UNORDERED:
 596             predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
 597             break;
 598
 599           case LE:
 600           case LT:
 601             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 602                 || XEXP (cond, 1) == constm1_rtx)
 603               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
 604             break;
 605
 606           case GE:
 607           case GT:
 608             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 609                 || XEXP (cond, 1) == constm1_rtx)
 610               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
 611             break;
 612
 613           default:
 614             break;
 615           }
 616     }
 617
 618   /* Attach the combined probability to each conditional jump.  */
 619   FOR_EACH_BB (bb)
 620     if (GET_CODE (BB_END (bb)) == JUMP_INSN
 621         && any_condjump_p (BB_END (bb))
 622         && bb->succ->succ_next != NULL)
 623       combine_predictions_for_insn (BB_END (bb), bb);
 624
 625   free_dominance_info (CDI_POST_DOMINATORS);
 626
 627   remove_fake_edges ();
 628   estimate_bb_frequencies (loops_info);
 629 }
 630 \f
 631 /* __builtin_expect dropped tokens into the insn stream describing expected
 632    values of registers.  Generate branch probabilities based off these
 633    values.  */
 634
 635 void
 636 expected_value_to_br_prob (void)
 637 {
 638   rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
 639
 640   for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
 641     {
 642       switch (GET_CODE (insn))
 643         {
 644         case NOTE:
 645           /* Look for expected value notes.  */
 646           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
 647             {
 648               ev = NOTE_EXPECTED_VALUE (insn);
 649               ev_reg = XEXP (ev, 0);
 650               delete_insn (insn);
 651             }
 652           continue;
 653
 654         case CODE_LABEL:
 655           /* Never propagate across labels.  */
 656           ev = NULL_RTX;
 657           continue;
 658
 659         case JUMP_INSN:
 660           /* Look for simple conditional branches.  If we haven't got an
 661              expected value yet, no point going further.  */
 662           if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX
 663               || ! any_condjump_p (insn))
 664             continue;
 665           break;
 666
 667         default:
 668           /* Look for insns that clobber the EV register.  */
 669           if (ev && reg_set_p (ev_reg, insn))
 670             ev = NULL_RTX;
 671           continue;
 672         }
 673
 674       /* Collect the branch condition, hopefully relative to EV_REG.  */
 675       /* ???  At present we'll miss things like
 676                 (expected_value (eq r70 0))
 677                 (set r71 -1)
 678                 (set r80 (lt r70 r71))
 679                 (set pc (if_then_else (ne r80 0) ...))
 680          as canonicalize_condition will render this to us as
 681                 (lt r70, r71)
 682          Could use cselib to try and reduce this further.  */
 683       cond = XEXP (SET_SRC (pc_set (insn)), 0);
 684       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg, false);
 685       if (! cond || XEXP (cond, 0) != ev_reg
 686           || GET_CODE (XEXP (cond, 1)) != CONST_INT)
 687         continue;
 688
 689       /* Substitute and simplify.  Given that the expression we're
 690          building involves two constants, we should wind up with either
 691          true or false.  */
 692       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 693                              XEXP (ev, 1), XEXP (cond, 1));
 694       cond = simplify_rtx (cond);
 695
 696       /* Turn the condition into a scaled branch probability.  */
 697       if (cond != const_true_rtx && cond != const0_rtx)
 698         abort ();
 699       predict_insn_def (insn, PRED_BUILTIN_EXPECT,
 700                         cond == const_true_rtx ? TAKEN : NOT_TAKEN);
 701     }
 702 }
 703 \f
 704 /* Check whether this is the last basic block of function.  Commonly
 705    there is one extra common cleanup block.  */
 706 static bool
 707 last_basic_block_p (basic_block bb)
 708 {
 709   if (bb == EXIT_BLOCK_PTR)
 710     return false;
 711
 712   return (bb->next_bb == EXIT_BLOCK_PTR
 713           || (bb->next_bb->next_bb == EXIT_BLOCK_PTR
 714               && bb->succ && !bb->succ->succ_next
 715               && bb->succ->dest->next_bb == EXIT_BLOCK_PTR));
 716 }
 717
 718 /* Sets branch probabilities according to PREDiction and
 719    FLAGS. HEADS[bb->index] should be index of basic block in that we
 720    need to alter branch predictions (i.e. the first of our dominators
 721    such that we do not post-dominate it) (but we fill this information
 722    on demand, so -1 may be there in case this was not needed yet).  */
 723
 724 static void
 725 process_note_prediction (basic_block bb, int *heads, int pred, int flags)
 726 {
 727   edge e;
 728   int y;
 729   bool taken;
 730
 731   taken = flags & IS_TAKEN;
 732
 733   if (heads[bb->index] < 0)
 734     {
 735       /* This is first time we need this field in heads array; so
 736          find first dominator that we do not post-dominate (we are
 737          using already known members of heads array).  */
 738       basic_block ai = bb;
 739       basic_block next_ai = get_immediate_dominator (CDI_DOMINATORS, bb);
 740       int head;
 741
 742       while (heads[next_ai->index] < 0)
 743         {
 744           if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
 745             break;
 746           heads[next_ai->index] = ai->index;
 747           ai = next_ai;
 748           next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai);
 749         }
 750       if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
 751         head = next_ai->index;
 752       else
 753         head = heads[next_ai->index];
 754       while (next_ai != bb)
 755         {
 756           next_ai = ai;
 757           if (heads[ai->index] == ENTRY_BLOCK)
 758             ai = ENTRY_BLOCK_PTR;
 759           else
 760             ai = BASIC_BLOCK (heads[ai->index]);
 761           heads[next_ai->index] = head;
 762         }
 763     }
 764   y = heads[bb->index];
 765
 766   /* Now find the edge that leads to our branch and aply the prediction.  */
 767
 768   if (y == last_basic_block || !can_predict_insn_p (BB_END (BASIC_BLOCK (y))))
 769     return;
 770   for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
 771     if (e->dest->index >= 0
 772         && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb))
 773       predict_edge_def (e, pred, taken);
 774 }
 775
 776 /* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them
 777    into branch probabilities.  For description of heads array, see
 778    process_note_prediction.  */
 779
 780 static void
 781 process_note_predictions (basic_block bb, int *heads)
 782 {
 783   rtx insn;
 784   edge e;
 785
 786   /* Additionally, we check here for blocks with no successors.  */
 787   int contained_noreturn_call = 0;
 788   int was_bb_head = 0;
 789   int noreturn_block = 1;
 790
 791   for (insn = BB_END (bb); insn;
 792        was_bb_head |= (insn == BB_HEAD (bb)), insn = PREV_INSN (insn))
 793     {
 794       if (GET_CODE (insn) != NOTE)
 795         {
 796           if (was_bb_head)
 797             break;
 798           else
 799             {
 800               /* Noreturn calls cause program to exit, therefore they are
 801                  always predicted as not taken.  */
 802               if (GET_CODE (insn) == CALL_INSN
 803                   && find_reg_note (insn, REG_NORETURN, NULL))
 804                 contained_noreturn_call = 1;
 805               continue;
 806             }
 807         }
 808       if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION)
 809         {
 810           int alg = (int) NOTE_PREDICTION_ALG (insn);
 811           /* Process single prediction note.  */
 812           process_note_prediction (bb,
 813                                    heads,
 814                                    alg, (int) NOTE_PREDICTION_FLAGS (insn));
 815           delete_insn (insn);
 816         }
 817     }
 818   for (e = bb->succ; e; e = e->succ_next)
 819     if (!(e->flags & EDGE_FAKE))
 820       noreturn_block = 0;
 821   if (contained_noreturn_call)
 822     {
 823       /* This block ended from other reasons than because of return.
 824          If it is because of noreturn call, this should certainly not
 825          be taken.  Otherwise it is probably some error recovery.  */
 826       process_note_prediction (bb, heads, PRED_NORETURN, NOT_TAKEN);
 827     }
 828 }
 829
 830 /* Gathers NOTE_INSN_PREDICTIONs and turns them into
 831    branch probabilities.  */
 832
 833 void
 834 note_prediction_to_br_prob (void)
 835 {
 836   basic_block bb;
 837   int *heads;
 838
 839   /* To enable handling of noreturn blocks.  */
 840   add_noreturn_fake_exit_edges ();
 841   connect_infinite_loops_to_exit ();
 842
 843   calculate_dominance_info (CDI_POST_DOMINATORS);
 844   calculate_dominance_info (CDI_DOMINATORS);
 845
 846   heads = xmalloc (sizeof (int) * last_basic_block);
 847   memset (heads, -1, sizeof (int) * last_basic_block);
 848   heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
 849
 850   /* Process all prediction notes.  */
 851
 852   FOR_EACH_BB (bb)
 853     process_note_predictions (bb, heads);
 854
 855   free_dominance_info (CDI_POST_DOMINATORS);
 856   free_dominance_info (CDI_DOMINATORS);
 857   free (heads);
 858
 859   remove_fake_edges ();
 860 }
 861 \f
 862 /* This is used to carry information about basic blocks.  It is
 863    attached to the AUX field of the standard CFG block.  */
 864
 865 typedef struct block_info_def
 866 {
 867   /* Estimated frequency of execution of basic_block.  */
 868   sreal frequency;
 869
 870   /* To keep queue of basic blocks to process.  */
 871   basic_block next;
 872
 873   /* True if block needs to be visited in propagate_freq.  */
 874   unsigned int tovisit:1;
 875
 876   /* Number of predecessors we need to visit first.  */
 877   int npredecessors;
 878 } *block_info;
 879
 880 /* Similar information for edges.  */
 881 typedef struct edge_info_def
 882 {
 883   /* In case edge is an loopback edge, the probability edge will be reached
 884      in case header is.  Estimated number of iterations of the loop can be
 885      then computed as 1 / (1 - back_edge_prob).  */
 886   sreal back_edge_prob;
 887   /* True if the edge is an loopback edge in the natural loop.  */
 888   unsigned int back_edge:1;
 889 } *edge_info;
 890
 891 #define BLOCK_INFO(B)   ((block_info) (B)->aux)
 892 #define EDGE_INFO(E)    ((edge_info) (E)->aux)
 893
 894 /* Helper function for estimate_bb_frequencies.
 895    Propagate the frequencies for LOOP.  */
 896
 897 static void
 898 propagate_freq (struct loop *loop)
 899 {
 900   basic_block head = loop->header;
 901   basic_block bb;
 902   basic_block last;
 903   edge e;
 904   basic_block nextbb;
 905
 906   /* For each basic block we need to visit count number of his predecessors
 907      we need to visit first.  */
 908   FOR_EACH_BB (bb)
 909     {
 910       if (BLOCK_INFO (bb)->tovisit)
 911         {
 912           int count = 0;
 913
 914           for (e = bb->pred; e; e = e->pred_next)
 915             if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
 916               count++;
 917             else if (BLOCK_INFO (e->src)->tovisit
 918                      && dump_file && !EDGE_INFO (e)->back_edge)
 919               fprintf (dump_file,
 920                        "Irreducible region hit, ignoring edge to %i->%i\n",
 921                        e->src->index, bb->index);
 922           BLOCK_INFO (bb)->npredecessors = count;
 923         }
 924     }
 925
 926   memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
 927   last = head;
 928   for (bb = head; bb; bb = nextbb)
 929     {
 930       sreal cyclic_probability, frequency;
 931
 932       memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
 933       memcpy (&frequency, &real_zero, sizeof (real_zero));
 934
 935       nextbb = BLOCK_INFO (bb)->next;
 936       BLOCK_INFO (bb)->next = NULL;
 937
 938       /* Compute frequency of basic block.  */
 939       if (bb != head)
 940         {
 941 #ifdef ENABLE_CHECKING
 942           for (e = bb->pred; e; e = e->pred_next)
 943             if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
 944               abort ();
 945 #endif
 946
 947           for (e = bb->pred; e; e = e->pred_next)
 948             if (EDGE_INFO (e)->back_edge)
 949               {
 950                 sreal_add (&cyclic_probability, &cyclic_probability,
 951                            &EDGE_INFO (e)->back_edge_prob);
 952               }
 953             else if (!(e->flags & EDGE_DFS_BACK))
 954               {
 955                 sreal tmp;
 956
 957                 /*  frequency += (e->probability
 958                                   * BLOCK_INFO (e->src)->frequency /
 959                                   REG_BR_PROB_BASE);  */
 960
 961                 sreal_init (&tmp, e->probability, 0);
 962                 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
 963                 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
 964                 sreal_add (&frequency, &frequency, &tmp);
 965               }
 966
 967           if (sreal_compare (&cyclic_probability, &real_zero) == 0)
 968             {
 969               memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
 970                       sizeof (frequency));
 971             }
 972           else
 973             {
 974               if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
 975                 {
 976                   memcpy (&cyclic_probability, &real_almost_one,
 977                           sizeof (real_almost_one));
 978                 }
 979
 980               /* BLOCK_INFO (bb)->frequency = frequency
 981                                               / (1 - cyclic_probability) */
 982
 983               sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
 984               sreal_div (&BLOCK_INFO (bb)->frequency,
 985                          &frequency, &cyclic_probability);
 986             }
 987         }
 988
 989       BLOCK_INFO (bb)->tovisit = 0;
 990
 991       /* Compute back edge frequencies.  */
 992       for (e = bb->succ; e; e = e->succ_next)
 993         if (e->dest == head)
 994           {
 995             sreal tmp;
 996
 997             /* EDGE_INFO (e)->back_edge_prob
 998                   = ((e->probability * BLOCK_INFO (bb)->frequency)
 999                      / REG_BR_PROB_BASE); */
1000
1001             sreal_init (&tmp, e->probability, 0);
1002             sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
1003             sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1004                        &tmp, &real_inv_br_prob_base);
1005           }
1006
1007       /* Propagate to successor blocks.  */
1008       for (e = bb->succ; e; e = e->succ_next)
1009         if (!(e->flags & EDGE_DFS_BACK)
1010             && BLOCK_INFO (e->dest)->npredecessors)
1011           {
1012             BLOCK_INFO (e->dest)->npredecessors--;
1013             if (!BLOCK_INFO (e->dest)->npredecessors)
1014               {
1015                 if (!nextbb)
1016                   nextbb = e->dest;
1017                 else
1018                   BLOCK_INFO (last)->next = e->dest;
1019
1020                 last = e->dest;
1021               }
1022            }
1023     }
1024 }
1025
1026 /* Estimate probabilities of loopback edges in loops at same nest level.  */
1027
1028 static void
1029 estimate_loops_at_level (struct loop *first_loop)
1030 {
1031   struct loop *loop;
1032
1033   for (loop = first_loop; loop; loop = loop->next)
1034     {
1035       edge e;
1036       basic_block *bbs;
1037       unsigned i;
1038
1039       estimate_loops_at_level (loop->inner);
1040
1041       if (loop->latch->succ)  /* Do not do this for dummy function loop.  */
1042         {
1043           /* Find current loop back edge and mark it.  */
1044           e = loop_latch_edge (loop);
1045           EDGE_INFO (e)->back_edge = 1;
1046        }
1047
1048       bbs = get_loop_body (loop);
1049       for (i = 0; i < loop->num_nodes; i++)
1050         BLOCK_INFO (bbs[i])->tovisit = 1;
1051       free (bbs);
1052       propagate_freq (loop);
1053     }
1054 }
1055
1056 /* Convert counts measured by profile driven feedback to frequencies.
1057    Return nonzero iff there was any nonzero execution count.  */
1058
1059 static int
1060 counts_to_freqs (void)
1061 {
1062   gcov_type count_max, true_count_max = 0;
1063   basic_block bb;
1064
1065   FOR_EACH_BB (bb)
1066     true_count_max = MAX (bb->count, true_count_max);
1067
1068   count_max = MAX (true_count_max, 1);
1069   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1070     bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1071   return true_count_max;
1072 }
1073
1074 /* Return true if function is likely to be expensive, so there is no point to
1075    optimize performance of prologue, epilogue or do inlining at the expense
1076    of code size growth.  THRESHOLD is the limit of number of instructions
1077    function can execute at average to be still considered not expensive.  */
1078
1079 bool
1080 expensive_function_p (int threshold)
1081 {
1082   unsigned int sum = 0;
1083   basic_block bb;
1084   unsigned int limit;
1085
1086   /* We can not compute accurately for large thresholds due to scaled
1087      frequencies.  */
1088   if (threshold > BB_FREQ_MAX)
1089     abort ();
1090
1091   /* Frequencies are out of range.  This either means that function contains
1092      internal loop executing more than BB_FREQ_MAX times or profile feedback
1093      is available and function has not been executed at all.  */
1094   if (ENTRY_BLOCK_PTR->frequency == 0)
1095     return true;
1096
1097   /* Maximally BB_FREQ_MAX^2 so overflow won't happen.  */
1098   limit = ENTRY_BLOCK_PTR->frequency * threshold;
1099   FOR_EACH_BB (bb)
1100     {
1101       rtx insn;
1102
1103       for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
1104            insn = NEXT_INSN (insn))
1105         if (active_insn_p (insn))
1106           {
1107             sum += bb->frequency;
1108             if (sum > limit)
1109               return true;
1110         }
1111     }
1112
1113   return false;
1114 }
1115
1116 /* Estimate basic blocks frequency by given branch probabilities.  */
1117
1118 static void
1119 estimate_bb_frequencies (struct loops *loops)
1120 {
1121   basic_block bb;
1122   sreal freq_max;
1123
1124   if (!flag_branch_probabilities || !counts_to_freqs ())
1125     {
1126       static int real_values_initialized = 0;
1127
1128       if (!real_values_initialized)
1129         {
1130           real_values_initialized = 1;
1131           sreal_init (&real_zero, 0, 0);
1132           sreal_init (&real_one, 1, 0);
1133           sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
1134           sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
1135           sreal_init (&real_one_half, 1, -1);
1136           sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
1137           sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
1138         }
1139
1140       mark_dfs_back_edges ();
1141       /* Fill in the probability values in flowgraph based on the REG_BR_PROB
1142          notes.  */
1143       FOR_EACH_BB (bb)
1144         {
1145           rtx last_insn = BB_END (bb);
1146
1147           if (!can_predict_insn_p (last_insn))
1148             {
1149               /* We can predict only conditional jumps at the moment.
1150                  Expect each edge to be equally probable.
1151                  ?? In the future we want to make abnormal edges improbable.  */
1152               int nedges = 0;
1153               edge e;
1154
1155               for (e = bb->succ; e; e = e->succ_next)
1156                 {
1157                   nedges++;
1158                   if (e->probability != 0)
1159                     break;
1160                 }
1161               if (!e)
1162                 for (e = bb->succ; e; e = e->succ_next)
1163                   e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
1164             }
1165         }
1166
1167       ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
1168
1169       /* Set up block info for each basic block.  */
1170       alloc_aux_for_blocks (sizeof (struct block_info_def));
1171       alloc_aux_for_edges (sizeof (struct edge_info_def));
1172       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1173         {
1174           edge e;
1175
1176           BLOCK_INFO (bb)->tovisit = 0;
1177           for (e = bb->succ; e; e = e->succ_next)
1178             {
1179               sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
1180               sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1181                          &EDGE_INFO (e)->back_edge_prob,
1182                          &real_inv_br_prob_base);
1183             }
1184         }
1185
1186       /* First compute probabilities locally for each loop from innermost
1187          to outermost to examine probabilities for back edges.  */
1188       estimate_loops_at_level (loops->tree_root);
1189
1190       memcpy (&freq_max, &real_zero, sizeof (real_zero));
1191       FOR_EACH_BB (bb)
1192         if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
1193           memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
1194
1195       sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
1196       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1197         {
1198           sreal tmp;
1199
1200           sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
1201           sreal_add (&tmp, &tmp, &real_one_half);
1202           bb->frequency = sreal_to_int (&tmp);
1203         }
1204
1205       free_aux_for_blocks ();
1206       free_aux_for_edges ();
1207     }
1208   compute_function_frequency ();
1209   if (flag_reorder_functions)
1210     choose_function_section ();
1211 }
1212
1213 /* Decide whether function is hot, cold or unlikely executed.  */
1214 static void
1215 compute_function_frequency (void)
1216 {
1217   basic_block bb;
1218
1219   if (!profile_info || !flag_branch_probabilities)
1220     return;
1221   cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1222   FOR_EACH_BB (bb)
1223     {
1224       if (maybe_hot_bb_p (bb))
1225         {
1226           cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
1227           return;
1228         }
1229       if (!probably_never_executed_bb_p (bb))
1230         cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
1231     }
1232 }
1233
1234 /* Choose appropriate section for the function.  */
1235 static void
1236 choose_function_section (void)
1237 {
1238   if (DECL_SECTION_NAME (current_function_decl)
1239       || !targetm.have_named_sections
1240       /* Theoretically we can split the gnu.linkonce text section too,
1241          but this requires more work as the frequency needs to match
1242          for all generated objects so we need to merge the frequency
1243          of all instances.  For now just never set frequency for these.  */
1244       || DECL_ONE_ONLY (current_function_decl))
1245     return;
1246   if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
1247     DECL_SECTION_NAME (current_function_decl) =
1248       build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
1249   if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
1250     DECL_SECTION_NAME (current_function_decl) =
1251       build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
1252                     UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
1253 }