gcc/predict.c

   1 /* Branch prediction routines for the GNU compiler.
   2    Copyright (C) 2000, 2001, 2002 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 "tree.h"
  34 #include "rtl.h"
  35 #include "tm_p.h"
  36 #include "hard-reg-set.h"
  37 #include "basic-block.h"
  38 #include "insn-config.h"
  39 #include "regs.h"
  40 #include "flags.h"
  41 #include "output.h"
  42 #include "function.h"
  43 #include "except.h"
  44 #include "toplev.h"
  45 #include "recog.h"
  46 #include "expr.h"
  47 #include "predict.h"
  48
  49 /* Random guesstimation given names.  */
  50 #define PROB_NEVER              (0)
  51 #define PROB_VERY_UNLIKELY      (REG_BR_PROB_BASE / 10 - 1)
  52 #define PROB_UNLIKELY           (REG_BR_PROB_BASE * 4 / 10 - 1)
  53 #define PROB_EVEN               (REG_BR_PROB_BASE / 2)
  54 #define PROB_LIKELY             (REG_BR_PROB_BASE - PROB_UNLIKELY)
  55 #define PROB_VERY_LIKELY        (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
  56 #define PROB_ALWAYS             (REG_BR_PROB_BASE)
  57
  58 static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
  59 static void dump_prediction              PARAMS ((enum br_predictor, int,
  60                                                   basic_block, int));
  61 static void estimate_loops_at_level      PARAMS ((struct loop *loop));
  62 static void propagate_freq               PARAMS ((basic_block));
  63 static void estimate_bb_frequencies      PARAMS ((struct loops *));
  64 static void counts_to_freqs              PARAMS ((void));
  65
  66 /* Information we hold about each branch predictor.
  67    Filled using information from predict.def.  */
  68
  69 struct predictor_info
  70 {
  71   const char *const name;       /* Name used in the debugging dumps.  */
  72   const int hitrate;            /* Expected hitrate used by
  73                                    predict_insn_def call.  */
  74   const int flags;
  75 };
  76
  77 /* Use given predictor without Dempster-Shaffer theory if it matches
  78    using first_match heuristics.  */
  79 #define PRED_FLAG_FIRST_MATCH 1
  80
  81 /* Recompute hitrate in percent to our representation.  */
  82
  83 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
  84
  85 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
  86 static const struct predictor_info predictor_info[]= {
  87 #include "predict.def"
  88
  89   /* Upper bound on predictors.  */
  90   {NULL, 0, 0}
  91 };
  92 #undef DEF_PREDICTOR
  93
  94 void
  95 predict_insn (insn, predictor, probability)
  96      rtx insn;
  97      int probability;
  98      enum br_predictor predictor;
  99 {
 100   if (!any_condjump_p (insn))
 101     abort ();
 102
 103   REG_NOTES (insn)
 104     = gen_rtx_EXPR_LIST (REG_BR_PRED,
 105                          gen_rtx_CONCAT (VOIDmode,
 106                                          GEN_INT ((int) predictor),
 107                                          GEN_INT ((int) probability)),
 108                          REG_NOTES (insn));
 109 }
 110
 111 /* Predict insn by given predictor.  */
 112
 113 void
 114 predict_insn_def (insn, predictor, taken)
 115      rtx insn;
 116      enum br_predictor predictor;
 117      enum prediction taken;
 118 {
 119    int probability = predictor_info[(int) predictor].hitrate;
 120
 121    if (taken != TAKEN)
 122      probability = REG_BR_PROB_BASE - probability;
 123
 124    predict_insn (insn, predictor, probability);
 125 }
 126
 127 /* Predict edge E with given probability if possible.  */
 128
 129 void
 130 predict_edge (e, predictor, probability)
 131      edge e;
 132      int probability;
 133      enum br_predictor predictor;
 134 {
 135   rtx last_insn;
 136   last_insn = e->src->end;
 137
 138   /* We can store the branch prediction information only about
 139      conditional jumps.  */
 140   if (!any_condjump_p (last_insn))
 141     return;
 142
 143   /* We always store probability of branching.  */
 144   if (e->flags & EDGE_FALLTHRU)
 145     probability = REG_BR_PROB_BASE - probability;
 146
 147   predict_insn (last_insn, predictor, probability);
 148 }
 149
 150 /* Predict edge E by given predictor if possible.  */
 151
 152 void
 153 predict_edge_def (e, predictor, taken)
 154      edge e;
 155      enum br_predictor predictor;
 156      enum prediction taken;
 157 {
 158    int probability = predictor_info[(int) predictor].hitrate;
 159
 160    if (taken != TAKEN)
 161      probability = REG_BR_PROB_BASE - probability;
 162
 163    predict_edge (e, predictor, probability);
 164 }
 165
 166 /* Invert all branch predictions or probability notes in the INSN.  This needs
 167    to be done each time we invert the condition used by the jump.  */
 168
 169 void
 170 invert_br_probabilities (insn)
 171      rtx insn;
 172 {
 173   rtx note;
 174
 175   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 176     if (REG_NOTE_KIND (note) == REG_BR_PROB)
 177       XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
 178     else if (REG_NOTE_KIND (note) == REG_BR_PRED)
 179       XEXP (XEXP (note, 0), 1)
 180         = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
 181 }
 182
 183 /* Dump information about the branch prediction to the output file.  */
 184
 185 static void
 186 dump_prediction (predictor, probability, bb, used)
 187      enum br_predictor predictor;
 188      int probability;
 189      basic_block bb;
 190      int used;
 191 {
 192   edge e = bb->succ;
 193
 194   if (!rtl_dump_file)
 195     return;
 196
 197   while (e && (e->flags & EDGE_FALLTHRU))
 198     e = e->succ_next;
 199
 200   fprintf (rtl_dump_file, "  %s heuristics%s: %.1f%%",
 201            predictor_info[predictor].name,
 202            used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
 203
 204   if (bb->count)
 205     {
 206       fprintf (rtl_dump_file, "  exec ");
 207       fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 208       if (e)
 209         {
 210           fprintf (rtl_dump_file, " hit ");
 211           fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 212           fprintf (rtl_dump_file, " (%.1f%%)", e->count * 100.0 / bb->count);
 213         }
 214     }
 215
 216   fprintf (rtl_dump_file, "\n");
 217 }
 218
 219 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
 220    note if not already present.  Remove now useless REG_BR_PRED notes.  */
 221
 222 static void
 223 combine_predictions_for_insn (insn, bb)
 224      rtx insn;
 225      basic_block bb;
 226 {
 227   rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
 228   rtx *pnote = &REG_NOTES (insn);
 229   rtx note;
 230   int best_probability = PROB_EVEN;
 231   int best_predictor = END_PREDICTORS;
 232   int combined_probability = REG_BR_PROB_BASE / 2;
 233   int d;
 234   bool first_match = false;
 235   bool found = false;
 236
 237   if (rtl_dump_file)
 238     fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
 239              bb->index);
 240
 241   /* We implement "first match" heuristics and use probability guessed
 242      by predictor with smallest index.  In the future we will use better
 243      probability combination techniques.  */
 244   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 245     if (REG_NOTE_KIND (note) == REG_BR_PRED)
 246       {
 247         int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
 248         int probability = INTVAL (XEXP (XEXP (note, 0), 1));
 249
 250         found = true;
 251         if (best_predictor > predictor)
 252           best_probability = probability, best_predictor = predictor;
 253
 254         d = (combined_probability * probability
 255              + (REG_BR_PROB_BASE - combined_probability)
 256              * (REG_BR_PROB_BASE - probability));
 257
 258         /* Use FP math to avoid overflows of 32bit integers.  */
 259         if (d == 0)
 260           /* If one probability is 0% and one 100%, avoid division by zero.  */
 261           combined_probability = REG_BR_PROB_BASE / 2;
 262         else
 263           combined_probability = (((double) combined_probability) * probability
 264                                   * REG_BR_PROB_BASE / d + 0.5);
 265       }
 266
 267   /* Decide which heuristic to use.  In case we didn't match anything,
 268      use no_prediction heuristic, in case we did match, use either
 269      first match or Dempster-Shaffer theory depending on the flags.  */
 270
 271   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
 272     first_match = true;
 273
 274   if (!found)
 275     dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true);
 276   else
 277     {
 278       dump_prediction (PRED_DS_THEORY, combined_probability, bb, !first_match);
 279       dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match);
 280     }
 281
 282   if (first_match)
 283     combined_probability = best_probability;
 284   dump_prediction (PRED_COMBINED, combined_probability, bb, true);
 285
 286   while (*pnote)
 287     {
 288       if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
 289         {
 290           int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
 291           int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
 292
 293           dump_prediction (predictor, probability, bb,
 294                            !first_match || best_predictor == predictor);
 295           *pnote = XEXP (*pnote, 1);
 296         }
 297       else
 298         pnote = &XEXP (*pnote, 1);
 299     }
 300
 301   if (!prob_note)
 302     {
 303       REG_NOTES (insn)
 304         = gen_rtx_EXPR_LIST (REG_BR_PROB,
 305                              GEN_INT (combined_probability), REG_NOTES (insn));
 306
 307       /* Save the prediction into CFG in case we are seeing non-degenerated
 308          conditional jump.  */
 309       if (bb->succ->succ_next)
 310         {
 311           BRANCH_EDGE (bb)->probability = combined_probability;
 312           FALLTHRU_EDGE (bb)->probability
 313             = REG_BR_PROB_BASE - combined_probability;
 314         }
 315     }
 316 }
 317
 318 /* Statically estimate the probability that a branch will be taken.
 319    ??? In the next revision there will be a number of other predictors added
 320    from the above references. Further, each heuristic will be factored out
 321    into its own function for clarity (and to facilitate the combination of
 322    predictions).  */
 323
 324 void
 325 estimate_probability (loops_info)
 326      struct loops *loops_info;
 327 {
 328   sbitmap *dominators, *post_dominators;
 329   int i;
 330   int found_noreturn = 0;
 331
 332   dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 333   post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 334   calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
 335   calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
 336
 337   /* Try to predict out blocks in a loop that are not part of a
 338      natural loop.  */
 339   for (i = 0; i < loops_info->num; i++)
 340     {
 341       int j;
 342       int exits;
 343       struct loop *loop = &loops_info->array[i];
 344
 345       flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
 346       exits = loop->num_exits;
 347
 348       for (j = loop->first->index; j <= loop->last->index; ++j)
 349         if (TEST_BIT (loop->nodes, j))
 350           {
 351             int header_found = 0;
 352             edge e;
 353
 354             /* Loop branch heuristics - predict an edge back to a
 355                loop's head as taken.  */
 356             for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
 357               if (e->dest == loop->header
 358                   && e->src == loop->latch)
 359                 {
 360                   header_found = 1;
 361                   predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
 362                 }
 363
 364             /* Loop exit heuristics - predict an edge exiting the loop if the
 365                conditinal has no loop header successors as not taken.  */
 366             if (!header_found)
 367               for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
 368                 if (e->dest->index < 0
 369                     || !TEST_BIT (loop->nodes, e->dest->index))
 370                   predict_edge
 371                     (e, PRED_LOOP_EXIT,
 372                      (REG_BR_PROB_BASE
 373                       - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
 374                      / exits);
 375           }
 376     }
 377
 378   /* Attempt to predict conditional jumps using a number of heuristics.  */
 379   for (i = 0; i < n_basic_blocks; i++)
 380     {
 381       basic_block bb = BASIC_BLOCK (i);
 382       rtx last_insn = bb->end;
 383       rtx cond, earliest;
 384       edge e;
 385
 386       /* If block has no successor, predict all possible paths to it as
 387          improbable, as the block contains a call to a noreturn function and
 388          thus can be executed only once.  */
 389       if (bb->succ == NULL && !found_noreturn)
 390         {
 391           int y;
 392
 393           /* ??? Postdominator claims each noreturn block to be postdominated
 394              by each, so we need to run only once.  This needs to be changed
 395              once postdominace algorithm is updated to say something more
 396              sane.  */
 397           found_noreturn = 1;
 398           for (y = 0; y < n_basic_blocks; y++)
 399             if (!TEST_BIT (post_dominators[y], i))
 400               for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
 401                 if (e->dest->index >= 0
 402                     && TEST_BIT (post_dominators[e->dest->index], i))
 403                   predict_edge_def (e, PRED_NORETURN, NOT_TAKEN);
 404         }
 405
 406       if (GET_CODE (last_insn) != JUMP_INSN || ! any_condjump_p (last_insn))
 407         continue;
 408
 409       for (e = bb->succ; e; e = e->succ_next)
 410         {
 411           /* Predict edges to blocks that return immediately to be
 412              improbable.  These are usually used to signal error states.  */
 413           if (e->dest == EXIT_BLOCK_PTR
 414               || (e->dest->succ && !e->dest->succ->succ_next
 415                   && e->dest->succ->dest == EXIT_BLOCK_PTR))
 416             predict_edge_def (e, PRED_ERROR_RETURN, NOT_TAKEN);
 417
 418           /* Look for block we are guarding (ie we dominate it,
 419              but it doesn't postdominate us).  */
 420           if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
 421               && TEST_BIT (dominators[e->dest->index], e->src->index)
 422               && !TEST_BIT (post_dominators[e->src->index], e->dest->index))
 423             {
 424               rtx insn;
 425
 426               /* The call heuristic claims that a guarded function call
 427                  is improbable.  This is because such calls are often used
 428                  to signal exceptional situations such as printing error
 429                  messages.  */
 430               for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end);
 431                    insn = NEXT_INSN (insn))
 432                 if (GET_CODE (insn) == CALL_INSN
 433                     /* Constant and pure calls are hardly used to signalize
 434                        something exceptional.  */
 435                     && ! CONST_OR_PURE_CALL_P (insn))
 436                   {
 437                     predict_edge_def (e, PRED_CALL, NOT_TAKEN);
 438                     break;
 439                   }
 440             }
 441         }
 442
 443       cond = get_condition (last_insn, &earliest);
 444       if (! cond)
 445         continue;
 446
 447       /* Try "pointer heuristic."
 448          A comparison ptr == 0 is predicted as false.
 449          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 450       if (GET_RTX_CLASS (GET_CODE (cond)) == '<'
 451           && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
 452               || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
 453         {
 454           if (GET_CODE (cond) == EQ)
 455             predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
 456           else if (GET_CODE (cond) == NE)
 457             predict_insn_def (last_insn, PRED_POINTER, TAKEN);
 458         }
 459       else
 460
 461       /* Try "opcode heuristic."
 462          EQ tests are usually false and NE tests are usually true. Also,
 463          most quantities are positive, so we can make the appropriate guesses
 464          about signed comparisons against zero.  */
 465         switch (GET_CODE (cond))
 466           {
 467           case CONST_INT:
 468             /* Unconditional branch.  */
 469             predict_insn_def (last_insn, PRED_UNCONDITIONAL,
 470                               cond == const0_rtx ? NOT_TAKEN : TAKEN);
 471             break;
 472
 473           case EQ:
 474           case UNEQ:
 475             /* Floating point comparisons appears to behave in a very
 476                inpredictable way because of special role of = tests in
 477                FP code.  */
 478             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 479               ;
 480             /* Comparisons with 0 are often used for booleans and there is
 481                nothing usefull to predict about them.  */
 482             else if (XEXP (cond, 1) == const0_rtx
 483                      || XEXP (cond, 0) == const0_rtx)
 484               ;
 485             else
 486               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
 487             break;
 488
 489           case NE:
 490           case LTGT:
 491             /* Floating point comparisons appears to behave in a very
 492                inpredictable way because of special role of = tests in
 493                FP code.  */
 494             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 495               ;
 496             /* Comparisons with 0 are often used for booleans and there is
 497                nothing usefull to predict about them.  */
 498             else if (XEXP (cond, 1) == const0_rtx
 499                      || XEXP (cond, 0) == const0_rtx)
 500               ;
 501             else
 502               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
 503             break;
 504
 505           case ORDERED:
 506             predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
 507             break;
 508
 509           case UNORDERED:
 510             predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
 511             break;
 512
 513           case LE:
 514           case LT:
 515             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 516                 || XEXP (cond, 1) == constm1_rtx)
 517               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
 518             break;
 519
 520           case GE:
 521           case GT:
 522             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 523                 || XEXP (cond, 1) == constm1_rtx)
 524               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
 525             break;
 526
 527           default:
 528             break;
 529           }
 530     }
 531
 532   /* Attach the combined probability to each conditional jump.  */
 533   for (i = 0; i < n_basic_blocks; i++)
 534     if (GET_CODE (BLOCK_END (i)) == JUMP_INSN
 535         && any_condjump_p (BLOCK_END (i)))
 536       combine_predictions_for_insn (BLOCK_END (i), BASIC_BLOCK (i));
 537
 538   sbitmap_vector_free (post_dominators);
 539   sbitmap_vector_free (dominators);
 540
 541   estimate_bb_frequencies (loops_info);
 542 }
 543 \f
 544 /* __builtin_expect dropped tokens into the insn stream describing expected
 545    values of registers.  Generate branch probabilities based off these
 546    values.  */
 547
 548 void
 549 expected_value_to_br_prob ()
 550 {
 551   rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
 552
 553   for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
 554     {
 555       switch (GET_CODE (insn))
 556         {
 557         case NOTE:
 558           /* Look for expected value notes.  */
 559           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
 560             {
 561               ev = NOTE_EXPECTED_VALUE (insn);
 562               ev_reg = XEXP (ev, 0);
 563               delete_insn (insn);
 564             }
 565           continue;
 566
 567         case CODE_LABEL:
 568           /* Never propagate across labels.  */
 569           ev = NULL_RTX;
 570           continue;
 571
 572         case JUMP_INSN:
 573           /* Look for simple conditional branches.  If we haven't got an
 574              expected value yet, no point going further.  */
 575           if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX
 576               || ! any_condjump_p (insn))
 577             continue;
 578           break;
 579
 580         default:
 581           /* Look for insns that clobber the EV register.  */
 582           if (ev && reg_set_p (ev_reg, insn))
 583             ev = NULL_RTX;
 584           continue;
 585         }
 586
 587       /* Collect the branch condition, hopefully relative to EV_REG.  */
 588       /* ???  At present we'll miss things like
 589                 (expected_value (eq r70 0))
 590                 (set r71 -1)
 591                 (set r80 (lt r70 r71))
 592                 (set pc (if_then_else (ne r80 0) ...))
 593          as canonicalize_condition will render this to us as
 594                 (lt r70, r71)
 595          Could use cselib to try and reduce this further.  */
 596       cond = XEXP (SET_SRC (pc_set (insn)), 0);
 597       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
 598       if (! cond || XEXP (cond, 0) != ev_reg
 599           || GET_CODE (XEXP (cond, 1)) != CONST_INT)
 600         continue;
 601
 602       /* Substitute and simplify.  Given that the expression we're
 603          building involves two constants, we should wind up with either
 604          true or false.  */
 605       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 606                              XEXP (ev, 1), XEXP (cond, 1));
 607       cond = simplify_rtx (cond);
 608
 609       /* Turn the condition into a scaled branch probability.  */
 610       if (cond != const_true_rtx && cond != const0_rtx)
 611         abort ();
 612       predict_insn_def (insn, PRED_BUILTIN_EXPECT,
 613                         cond == const_true_rtx ? TAKEN : NOT_TAKEN);
 614     }
 615 }
 616 \f
 617 /* This is used to carry information about basic blocks.  It is
 618    attached to the AUX field of the standard CFG block.  */
 619
 620 typedef struct block_info_def
 621 {
 622   /* Estimated frequency of execution of basic_block.  */
 623   volatile double frequency;
 624
 625   /* To keep queue of basic blocks to process.  */
 626   basic_block next;
 627
 628   /* True if block needs to be visited in prop_freqency.  */
 629   int tovisit:1;
 630
 631   /* Number of predecessors we need to visit first.  */
 632   int npredecessors;
 633 } *block_info;
 634
 635 /* Similar information for edges.  */
 636 typedef struct edge_info_def
 637 {
 638   /* In case edge is an loopback edge, the probability edge will be reached
 639      in case header is.  Estimated number of iterations of the loop can be
 640      then computed as 1 / (1 - back_edge_prob).
 641
 642      Volatile is needed to avoid differences in the optimized and unoptimized
 643      builds on machines where FP registers are wider than double.  */
 644   volatile double back_edge_prob;
 645   /* True if the edge is an loopback edge in the natural loop.  */
 646   int back_edge:1;
 647 } *edge_info;
 648
 649 #define BLOCK_INFO(B)   ((block_info) (B)->aux)
 650 #define EDGE_INFO(E)    ((edge_info) (E)->aux)
 651
 652 /* Helper function for estimate_bb_frequencies.
 653    Propagate the frequencies for loops headed by HEAD.  */
 654
 655 static void
 656 propagate_freq (head)
 657      basic_block head;
 658 {
 659   basic_block bb = head;
 660   basic_block last = bb;
 661   edge e;
 662   basic_block nextbb;
 663   int n;
 664
 665   /* For each basic block we need to visit count number of his predecessors
 666      we need to visit first.  */
 667   for (n = 0; n < n_basic_blocks; n++)
 668     {
 669       basic_block bb = BASIC_BLOCK (n);
 670       if (BLOCK_INFO (bb)->tovisit)
 671         {
 672           int count = 0;
 673
 674           for (e = bb->pred; e; e = e->pred_next)
 675             if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
 676               count++;
 677             else if (BLOCK_INFO (e->src)->tovisit
 678                      && rtl_dump_file && !EDGE_INFO (e)->back_edge)
 679               fprintf (rtl_dump_file,
 680                        "Irreducible region hit, ignoring edge to %i->%i\n",
 681                        e->src->index, bb->index);
 682           BLOCK_INFO (bb)->npredecessors = count;
 683         }
 684     }
 685
 686   BLOCK_INFO (head)->frequency = 1;
 687   for (; bb; bb = nextbb)
 688     {
 689       double cyclic_probability = 0, frequency = 0;
 690
 691       nextbb = BLOCK_INFO (bb)->next;
 692       BLOCK_INFO (bb)->next = NULL;
 693
 694       /* Compute frequency of basic block.  */
 695       if (bb != head)
 696         {
 697 #ifdef ENABLE_CHECKING
 698           for (e = bb->pred; e; e = e->pred_next)
 699             if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
 700               abort ();
 701 #endif
 702
 703           for (e = bb->pred; e; e = e->pred_next)
 704             if (EDGE_INFO (e)->back_edge)
 705               cyclic_probability += EDGE_INFO (e)->back_edge_prob;
 706             else if (!(e->flags & EDGE_DFS_BACK))
 707               frequency += (e->probability
 708                             * BLOCK_INFO (e->src)->frequency /
 709                             REG_BR_PROB_BASE);
 710
 711           if (cyclic_probability > 1.0 - 1.0 / REG_BR_PROB_BASE)
 712             cyclic_probability = 1.0 - 1.0 / REG_BR_PROB_BASE;
 713
 714           BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability);
 715         }
 716
 717       BLOCK_INFO (bb)->tovisit = 0;
 718
 719       /* Compute back edge frequencies.  */
 720       for (e = bb->succ; e; e = e->succ_next)
 721         if (e->dest == head)
 722           EDGE_INFO (e)->back_edge_prob
 723             = ((e->probability * BLOCK_INFO (bb)->frequency)
 724                / REG_BR_PROB_BASE);
 725
 726       /* Propagate to successor blocks.  */
 727       for (e = bb->succ; e; e = e->succ_next)
 728         if (!(e->flags & EDGE_DFS_BACK)
 729             && BLOCK_INFO (e->dest)->npredecessors)
 730           {
 731             BLOCK_INFO (e->dest)->npredecessors--;
 732             if (!BLOCK_INFO (e->dest)->npredecessors)
 733               {
 734                 if (!nextbb)
 735                   nextbb = e->dest;
 736                 else
 737                   BLOCK_INFO (last)->next = e->dest;
 738
 739                 last = e->dest;
 740               }
 741            }
 742     }
 743 }
 744
 745 /* Estimate probabilities of loopback edges in loops at same nest level.  */
 746
 747 static void
 748 estimate_loops_at_level (first_loop)
 749      struct loop *first_loop;
 750 {
 751   struct loop *l, *loop = first_loop;
 752
 753   for (loop = first_loop; loop; loop = loop->next)
 754     {
 755       int n;
 756       edge e;
 757
 758       estimate_loops_at_level (loop->inner);
 759
 760       /* Find current loop back edge and mark it.  */
 761       for (e = loop->latch->succ; e->dest != loop->header; e = e->succ_next)
 762         ;
 763
 764       EDGE_INFO (e)->back_edge = 1;
 765
 766       /* In case the loop header is shared, ensure that it is the last
 767          one sharing the same header, so we avoid redundant work.  */
 768       if (loop->shared)
 769         {
 770           for (l = loop->next; l; l = l->next)
 771             if (l->header == loop->header)
 772               break;
 773
 774           if (l)
 775             continue;
 776         }
 777
 778       /* Now merge all nodes of all loops with given header as not visited.  */
 779       for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next)
 780         if (loop->header == l->header)
 781           EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n,
 782                                      BLOCK_INFO (BASIC_BLOCK (n))->tovisit = 1
 783                                      );
 784
 785       propagate_freq (loop->header);
 786     }
 787 }
 788
 789 /* Convert counts measured by profile driven feedback to frequencies.  */
 790
 791 static void
 792 counts_to_freqs ()
 793 {
 794   HOST_WIDEST_INT count_max = 1;
 795   int i;
 796
 797   for (i = 0; i < n_basic_blocks; i++)
 798     count_max = MAX (BASIC_BLOCK (i)->count, count_max);
 799
 800   for (i = -2; i < n_basic_blocks; i++)
 801     {
 802       basic_block bb;
 803
 804       if (i == -2)
 805         bb = ENTRY_BLOCK_PTR;
 806       else if (i == -1)
 807         bb = EXIT_BLOCK_PTR;
 808       else
 809         bb = BASIC_BLOCK (i);
 810
 811       bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
 812     }
 813 }
 814
 815 /* Return true if function is likely to be expensive, so there is no point to
 816    optimize performance of prologue, epilogue or do inlining at the expense
 817    of code size growth.  THRESHOLD is the limit of number of isntructions
 818    function can execute at average to be still considered not expensive.  */
 819
 820 bool
 821 expensive_function_p (threshold)
 822         int threshold;
 823 {
 824   unsigned int sum = 0;
 825   int i;
 826   unsigned int limit;
 827
 828   /* We can not compute accurately for large thresholds due to scaled
 829      frequencies.  */
 830   if (threshold > BB_FREQ_MAX)
 831     abort ();
 832
 833   /* Frequencies are out of range.  This either means that function contains
 834      internal loop executing more than BB_FREQ_MAX times or profile feedback
 835      is available and function has not been executed at all.  */
 836   if (ENTRY_BLOCK_PTR->frequency == 0)
 837     return true;
 838
 839   /* Maximally BB_FREQ_MAX^2 so overflow won't happen.  */
 840   limit = ENTRY_BLOCK_PTR->frequency * threshold;
 841   for (i = 0; i < n_basic_blocks; i++)
 842     {
 843       basic_block bb = BASIC_BLOCK (i);
 844       rtx insn;
 845
 846       for (insn = bb->head; insn != NEXT_INSN (bb->end);
 847            insn = NEXT_INSN (insn))
 848         if (active_insn_p (insn))
 849           {
 850             sum += bb->frequency;
 851             if (sum > limit)
 852               return true;
 853         }
 854     }
 855
 856   return false;
 857 }
 858
 859 /* Estimate basic blocks frequency by given branch probabilities.  */
 860
 861 static void
 862 estimate_bb_frequencies (loops)
 863      struct loops *loops;
 864 {
 865   int i;
 866   double freq_max = 0;
 867
 868   mark_dfs_back_edges ();
 869   if (flag_branch_probabilities)
 870     {
 871       counts_to_freqs ();
 872       return;
 873     }
 874
 875   /* Fill in the probability values in flowgraph based on the REG_BR_PROB
 876      notes.  */
 877   for (i = 0; i < n_basic_blocks; i++)
 878     {
 879       rtx last_insn = BLOCK_END (i);
 880
 881       if (GET_CODE (last_insn) != JUMP_INSN || !any_condjump_p (last_insn)
 882           /* Avoid handling of conditional jumps jumping to fallthru edge.  */
 883           || BASIC_BLOCK (i)->succ->succ_next == NULL)
 884         {
 885           /* We can predict only conditional jumps at the moment.
 886              Expect each edge to be equally probable.
 887              ?? In the future we want to make abnormal edges improbable.  */
 888           int nedges = 0;
 889           edge e;
 890
 891           for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
 892             {
 893               nedges++;
 894               if (e->probability != 0)
 895                 break;
 896             }
 897           if (!e)
 898             for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
 899               e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
 900         }
 901     }
 902
 903   ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
 904
 905   /* Set up block info for each basic block.  */
 906   alloc_aux_for_blocks (sizeof (struct block_info_def));
 907   alloc_aux_for_edges (sizeof (struct edge_info_def));
 908   for (i = -2; i < n_basic_blocks; i++)
 909     {
 910       edge e;
 911       basic_block bb;
 912
 913       if (i == -2)
 914         bb = ENTRY_BLOCK_PTR;
 915       else if (i == -1)
 916         bb = EXIT_BLOCK_PTR;
 917       else
 918         bb = BASIC_BLOCK (i);
 919
 920       BLOCK_INFO (bb)->tovisit = 0;
 921       for (e = bb->succ; e; e = e->succ_next)
 922         EDGE_INFO (e)->back_edge_prob = ((double) e->probability
 923                                          / REG_BR_PROB_BASE);
 924     }
 925
 926   /* First compute probabilities locally for each loop from innermost
 927      to outermost to examine probabilities for back edges.  */
 928   estimate_loops_at_level (loops->tree_root);
 929
 930   /* Now fake loop around whole function to finalize probabilities.  */
 931   for (i = 0; i < n_basic_blocks; i++)
 932     BLOCK_INFO (BASIC_BLOCK (i))->tovisit = 1;
 933
 934   BLOCK_INFO (ENTRY_BLOCK_PTR)->tovisit = 1;
 935   BLOCK_INFO (EXIT_BLOCK_PTR)->tovisit = 1;
 936   propagate_freq (ENTRY_BLOCK_PTR);
 937
 938   for (i = 0; i < n_basic_blocks; i++)
 939     if (BLOCK_INFO (BASIC_BLOCK (i))->frequency > freq_max)
 940       freq_max = BLOCK_INFO (BASIC_BLOCK (i))->frequency;
 941
 942   for (i = -2; i < n_basic_blocks; i++)
 943     {
 944       basic_block bb;
 945       volatile double tmp;
 946
 947       if (i == -2)
 948         bb = ENTRY_BLOCK_PTR;
 949       else if (i == -1)
 950         bb = EXIT_BLOCK_PTR;
 951       else
 952         bb = BASIC_BLOCK (i);
 953
 954       /* ??? Prevent rounding differences due to optimization on x86.  */
 955       tmp = BLOCK_INFO (bb)->frequency * BB_FREQ_MAX;
 956       tmp /= freq_max;
 957       tmp += 0.5;
 958       bb->frequency = tmp;
 959     }
 960
 961   free_aux_for_blocks ();
 962   free_aux_for_edges ();
 963 }