gcc/predict.c

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