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