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
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    GCC is distributed in the hope that it will be useful, but WITHOUT
  12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  14    License 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
  32
  33 #include "config.h"
  34 #include "system.h"
  35 #include "tree.h"
  36 #include "rtl.h"
  37 #include "tm_p.h"
  38 #include "hard-reg-set.h"
  39 #include "basic-block.h"
  40 #include "insn-config.h"
  41 #include "regs.h"
  42 #include "flags.h"
  43 #include "output.h"
  44 #include "function.h"
  45 #include "except.h"
  46 #include "toplev.h"
  47 #include "recog.h"
  48 #include "expr.h"
  49 #include "predict.h"
  50
  51 /* Random guesstimation given names.  */
  52 #define PROB_NEVER              (0)
  53 #define PROB_VERY_UNLIKELY      (REG_BR_PROB_BASE / 10 - 1)
  54 #define PROB_UNLIKELY           (REG_BR_PROB_BASE * 4 / 10 - 1)
  55 #define PROB_EVEN               (REG_BR_PROB_BASE / 2)
  56 #define PROB_LIKELY             (REG_BR_PROB_BASE - PROB_UNLIKELY)
  57 #define PROB_VERY_LIKELY        (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
  58 #define PROB_ALWAYS             (REG_BR_PROB_BASE)
  59
  60 static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
  61 static void dump_prediction              PARAMS ((enum br_predictor, int,
  62                                                   basic_block, int));
  63 static void estimate_loops_at_level      PARAMS ((struct loop *loop));
  64 static void propagate_freq               PARAMS ((basic_block));
  65 static void estimate_bb_frequencies      PARAMS ((struct loops *));
  66 static void counts_to_freqs              PARAMS ((void));
  67
  68 /* Information we hold about each branch predictor.
  69    Filled using information from predict.def.  */
  70 struct predictor_info
  71 {
  72   const char *const name;       /* Name used in the debugging dumps.  */
  73   const int hitrate;            /* Expected hitrate used by
  74                                    predict_insn_def call.  */
  75   const int flags;
  76 };
  77
  78 /* Use given predictor without Dempster-Shaffer theory if it matches
  79    using first_match heuristics.  */
  80 #define PRED_FLAG_FIRST_MATCH 1
  81
  82 /* Recompute hitrate in percent to our representation.  */
  83
  84 #define HITRATE(VAL) ((int)((VAL) * REG_BR_PROB_BASE + 50) / 100)
  85
  86 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
  87 static const struct predictor_info predictor_info[] = {
  88 #include "predict.def"
  89
  90   /* Upper bound on predictors.  */
  91   {NULL, 0, 0}
  92 };
  93 #undef DEF_PREDICTOR
  94
  95 void
  96 predict_insn (insn, predictor, probability)
  97      rtx insn;
  98      int probability;
  99      enum br_predictor predictor;
 100 {
 101   if (!any_condjump_p (insn))
 102     abort ();
 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 void
 113 predict_insn_def (insn, predictor, taken)
 114      rtx insn;
 115      enum br_predictor predictor;
 116      enum prediction taken;
 117 {
 118    int probability = predictor_info[(int) predictor].hitrate;
 119    if (taken != TAKEN)
 120      probability = REG_BR_PROB_BASE - probability;
 121    predict_insn (insn, predictor, probability);
 122 }
 123
 124 /* Predict edge E with given probability if possible.  */
 125 void
 126 predict_edge (e, predictor, probability)
 127      edge e;
 128      int probability;
 129      enum br_predictor predictor;
 130 {
 131   rtx last_insn;
 132   last_insn = e->src->end;
 133
 134   /* We can store the branch prediction information only about
 135      conditional jumps.  */
 136   if (!any_condjump_p (last_insn))
 137     return;
 138
 139   /* We always store probability of branching.  */
 140   if (e->flags & EDGE_FALLTHRU)
 141     probability = REG_BR_PROB_BASE - probability;
 142
 143   predict_insn (last_insn, predictor, probability);
 144 }
 145
 146 /* Predict edge E by given predictor if possible.  */
 147 void
 148 predict_edge_def (e, predictor, taken)
 149      edge e;
 150      enum br_predictor predictor;
 151      enum prediction taken;
 152 {
 153    int probability = predictor_info[(int) predictor].hitrate;
 154
 155    if (taken != TAKEN)
 156      probability = REG_BR_PROB_BASE - probability;
 157    predict_edge (e, predictor, probability);
 158 }
 159
 160 /* Invert all branch predictions or probability notes in the INSN.  This needs
 161    to be done each time we invert the condition used by the jump.  */
 162 void
 163 invert_br_probabilities (insn)
 164      rtx insn;
 165 {
 166   rtx note = REG_NOTES (insn);
 167
 168   while (note)
 169     {
 170       if (REG_NOTE_KIND (note) == REG_BR_PROB)
 171         XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
 172       else if (REG_NOTE_KIND (note) == REG_BR_PRED)
 173         XEXP (XEXP (note, 0), 1)
 174           = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
 175       note = XEXP (note, 1);
 176     }
 177 }
 178
 179 /* Dump information about the branch prediction to the output file.  */
 180 static void
 181 dump_prediction (predictor, probability, bb, used)
 182      enum br_predictor predictor;
 183      int probability;
 184      basic_block bb;
 185      int used;
 186 {
 187   edge e = bb->succ;
 188
 189   if (!rtl_dump_file)
 190     return;
 191
 192   while (e->flags & EDGE_FALLTHRU)
 193     e = e->succ_next;
 194
 195   fprintf (rtl_dump_file, "  %s heuristics%s: %.1f%%",
 196            predictor_info[predictor].name,
 197            used ? "" : " (ignored)",
 198            probability * 100.0 / REG_BR_PROB_BASE);
 199
 200   if (bb->count)
 201     {
 202       fprintf (rtl_dump_file, "  exec ");
 203       fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
 204                (HOST_WIDEST_INT) bb->count);
 205       fprintf (rtl_dump_file, " hit ");
 206       fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
 207                (HOST_WIDEST_INT) e->count);
 208       fprintf (rtl_dump_file, " (%.1f%%)",
 209                e->count * 100.0 / bb->count);
 210     }
 211   fprintf (rtl_dump_file, "\n");
 212 }
 213
 214 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
 215    note if not already present.  Remove now useless REG_BR_PRED notes.  */
 216 static void
 217 combine_predictions_for_insn (insn, bb)
 218      rtx insn;
 219      basic_block bb;
 220 {
 221   rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
 222   rtx *pnote = &REG_NOTES (insn);
 223   rtx note = REG_NOTES (insn);
 224   int best_probability = PROB_EVEN;
 225   int best_predictor = END_PREDICTORS;
 226   int combined_probability = REG_BR_PROB_BASE / 2;
 227   int d;
 228   bool first_match = false;
 229   bool found = false;
 230
 231   if (rtl_dump_file)
 232     fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
 233              bb->index);
 234
 235   /* We implement "first match" heuristics and use probability guessed
 236      by predictor with smallest index.  In the future we will use better
 237      probability combination techniques.  */
 238   while (note)
 239     {
 240       if (REG_NOTE_KIND (note) == REG_BR_PRED)
 241         {
 242           int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
 243           int probability = INTVAL (XEXP (XEXP (note, 0), 1));
 244
 245           found = true;
 246           if (best_predictor > predictor)
 247             best_probability = probability, best_predictor = predictor;
 248
 249           d = (combined_probability * probability
 250                + (REG_BR_PROB_BASE - combined_probability)
 251                * (REG_BR_PROB_BASE - probability));
 252           /* An FP math to avoid overflows of 32bit integers.  */
 253           combined_probability = (((double)combined_probability) * probability
 254                                   * REG_BR_PROB_BASE / d + 0.5);
 255         }
 256       note = XEXP (note, 1);
 257     }
 258
 259   /* Decide heuristic to use.  In case we didn't match anything, use
 260      no_prediction heuristic, in case we did match, use either
 261      first match or Dempster-Shaffer theory depending on the flags.  */
 262
 263   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
 264     first_match = true;
 265
 266   if (!found)
 267     dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true);
 268   else
 269     {
 270       dump_prediction (PRED_DS_THEORY, combined_probability, bb,
 271                        !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   if (!prob_note)
 294     {
 295       REG_NOTES (insn)
 296         = gen_rtx_EXPR_LIST (REG_BR_PROB,
 297                              GEN_INT (combined_probability), REG_NOTES (insn));
 298       /* Save the prediction into CFG in case we are seeing non-degenerated
 299          conditional jump.  */
 300       if (bb->succ->succ_next)
 301         {
 302           BRANCH_EDGE (bb)->probability = combined_probability;
 303           FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - combined_probability;
 304         }
 305     }
 306 }
 307
 308 /* Statically estimate the probability that a branch will be taken.
 309    ??? In the next revision there will be a number of other predictors added
 310    from the above references. Further, each heuristic will be factored out
 311    into its own function for clarity (and to facilitate the combination of
 312    predictions).  */
 313
 314 void
 315 estimate_probability (loops_info)
 316      struct loops *loops_info;
 317 {
 318   sbitmap *dominators, *post_dominators;
 319   int i;
 320   int found_noreturn = 0;
 321
 322   dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 323   post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 324   calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
 325   calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
 326
 327   /* Try to predict out blocks in a loop that are not part of a
 328      natural loop.  */
 329   for (i = 0; i < loops_info->num; i++)
 330     {
 331       int j;
 332       int exits;
 333       struct loop *loop = &loops_info->array[i];
 334
 335       flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
 336       exits = loop->num_exits;
 337
 338       for (j = loop->first->index;
 339            j <= loop->last->index;
 340            ++j)
 341         {
 342           if (TEST_BIT (loop->nodes, j))
 343             {
 344               int header_found = 0;
 345               edge e;
 346
 347               /* Loop branch heuristics - predict as taken an edge back to
 348                  a loop's head.  */
 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               /* Loop exit heuristics - predict as not taken an edge
 357                  exiting the loop if the conditinal has no loop header
 358                  successors.  */
 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 (e, PRED_LOOP_EXIT,
 364                                   (REG_BR_PROB_BASE
 365                                    - predictor_info [(int)PRED_LOOP_EXIT].hitrate)
 366                                   / exits);
 367             }
 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
 380          it as improbable, as the block contains a call to a noreturn
 381          function and 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 sane.
 389              */
 390           found_noreturn = 1;
 391           for (y = 0; y < n_basic_blocks; y++)
 392             if (!TEST_BIT (post_dominators[y], i))
 393               {
 394                 for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
 395                 if (e->dest->index >= 0
 396                     && TEST_BIT (post_dominators[e->dest->index], i))
 397                   predict_edge_def (e, PRED_NORETURN, NOT_TAKEN);
 398               }
 399         }
 400
 401       if (GET_CODE (last_insn) != JUMP_INSN
 402           || ! any_condjump_p (last_insn))
 403         continue;
 404
 405       for (e = bb->succ; e; e = e->succ_next)
 406         {
 407           /* Predict edges to blocks that return immediately to be
 408              improbable.  These are usually used to signal error states.  */
 409           if (e->dest == EXIT_BLOCK_PTR
 410               || (e->dest->succ && !e->dest->succ->succ_next
 411                   && e->dest->succ->dest == EXIT_BLOCK_PTR))
 412             predict_edge_def (e, PRED_ERROR_RETURN, NOT_TAKEN);
 413
 414           /* Look for block we are guarding (ie we dominate it,
 415              but it doesn't postdominate us).  */
 416           if (e->dest != EXIT_BLOCK_PTR
 417               && 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               /* The call heuristic claims that a guarded function call
 423                  is improbable.  This is because such calls are often used
 424                  to signal exceptional situations such as printing error
 425                  messages.  */
 426               for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end);
 427                    insn = NEXT_INSN (insn))
 428                 if (GET_CODE (insn) == CALL_INSN
 429                     /* Constant and pure calls are hardly used to signalize
 430                        something exceptional.  */
 431                     && ! CONST_OR_PURE_CALL_P (insn))
 432                   {
 433                     predict_edge_def (e, PRED_CALL, NOT_TAKEN);
 434                     break;
 435                   }
 436             }
 437         }
 438
 439       cond = get_condition (last_insn, &earliest);
 440       if (! cond)
 441         continue;
 442
 443       /* Try "pointer heuristic."
 444          A comparison ptr == 0 is predicted as false.
 445          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 446       if (GET_RTX_CLASS (GET_CODE (cond)) == '<'
 447           && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
 448               || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
 449         switch (GET_CODE (cond))
 450           {
 451           case EQ:
 452             predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
 453             break;
 454           case NE:
 455             predict_insn_def (last_insn, PRED_POINTER, TAKEN);
 456             break;
 457           default:
 458             break;
 459           }
 460       else
 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 || XEXP (cond, 0) == const0_rtx)
 483               ;
 484             else
 485               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
 486             break;
 487           case NE:
 488           case LTGT:
 489             /* Floating point comparisons appears to behave in a very
 490                inpredictable way because of special role of = tests in
 491                FP code.  */
 492             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 493               ;
 494             /* Comparisons with 0 are often used for booleans and there is
 495                nothing usefull to predict about them.  */
 496             else if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 0) == const0_rtx)
 497               ;
 498             else
 499               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
 500             break;
 501           case ORDERED:
 502             predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
 503             break;
 504           case UNORDERED:
 505             predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
 506             break;
 507           case LE:
 508           case LT:
 509             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 510                 || XEXP (cond, 1) == constm1_rtx)
 511               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
 512             break;
 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     {
 528       rtx last_insn = BLOCK_END (i);
 529
 530       if (GET_CODE (last_insn) != JUMP_INSN
 531           || ! any_condjump_p (last_insn))
 532         continue;
 533       combine_predictions_for_insn (last_insn, 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
 542    expected values of registers.  Generate branch probabilities
 543    based off these 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         default:
 570           /* Look for insns that clobber the EV register.  */
 571           if (ev && reg_set_p (ev_reg, insn))
 572             ev = NULL_RTX;
 573           continue;
 574
 575         case JUMP_INSN:
 576           /* Look for simple conditional branches.  If we haven't got an
 577              expected value yet, no point going further.  */
 578           if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX)
 579             continue;
 580           if (! any_condjump_p (insn))
 581             continue;
 582           break;
 583         }
 584
 585       /* Collect the branch condition, hopefully relative to EV_REG.  */
 586       /* ???  At present we'll miss things like
 587                 (expected_value (eq r70 0))
 588                 (set r71 -1)
 589                 (set r80 (lt r70 r71))
 590                 (set pc (if_then_else (ne r80 0) ...))
 591          as canonicalize_condition will render this to us as
 592                 (lt r70, r71)
 593          Could use cselib to try and reduce this further.  */
 594       cond = XEXP (SET_SRC (pc_set (insn)), 0);
 595       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
 596       if (! cond
 597           || XEXP (cond, 0) != ev_reg
 598           || GET_CODE (XEXP (cond, 1)) != CONST_INT)
 599         continue;
 600
 601       /* Substitute and simplify.  Given that the expression we're
 602          building involves two constants, we should wind up with either
 603          true or false.  */
 604       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 605                              XEXP (ev, 1), XEXP (cond, 1));
 606       cond = simplify_rtx (cond);
 607
 608       /* Turn the condition into a scaled branch probability.  */
 609       if (cond != const_true_rtx && cond != const0_rtx)
 610         abort ();
 611       predict_insn_def (insn, PRED_BUILTIN_EXPECT,
 612                         cond == const_true_rtx ? TAKEN : NOT_TAKEN);
 613     }
 614 }
 615 \f
 616 /* This is used to carry information about basic blocks.  It is
 617    attached to the AUX field of the standard CFG block.  */
 618
 619 typedef struct block_info_def
 620 {
 621   /* Estimated frequency of execution of basic_block.  */
 622   volatile double frequency;
 623
 624   /* To keep queue of basic blocks to process.  */
 625   basic_block next;
 626
 627   /* True if block needs to be visited in prop_freqency.  */
 628   int tovisit:1;
 629
 630   /* Number of predecessors we need to visit first.  */
 631   int npredecessors;
 632 } *block_info;
 633
 634 /* Similar information for edges.  */
 635 typedef struct edge_info_def
 636 {
 637   /* In case edge is an loopback edge, the probability edge will be reached
 638      in case header is.  Estimated number of iterations of the loop can be
 639      then computed as 1 / (1 - back_edge_prob).
 640
 641      Volatile is needed to avoid differences in the optimized and unoptimized
 642      builds on machines where FP registers are wider than double.  */
 643   volatile double back_edge_prob;
 644   /* True if the edge is an loopback edge in the natural loop.  */
 645   int back_edge:1;
 646 } *edge_info;
 647
 648 #define BLOCK_INFO(B)   ((block_info) (B)->aux)
 649 #define EDGE_INFO(E)    ((edge_info) (E)->aux)
 650
 651 /* Helper function for estimate_bb_frequencies.
 652    Propagate the frequencies for loops headed by HEAD.  */
 653 static void
 654 propagate_freq (head)
 655      basic_block head;
 656 {
 657   basic_block bb = head;
 658   basic_block last = bb;
 659   edge e;
 660   basic_block nextbb;
 661   int n;
 662
 663   /* For each basic block we need to visit count number of his predecessors
 664      we need to visit first.  */
 665   for (n = 0; n < n_basic_blocks; n++)
 666     {
 667       basic_block bb = BASIC_BLOCK (n);
 668       if (BLOCK_INFO (bb)->tovisit)
 669         {
 670           int count = 0;
 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       volatile 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 = (e->probability
 720                                            * 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                 last = e->dest;
 736               }
 737            }
 738     }
 739 }
 740
 741 /* Estimate probabilities of loopback edges in loops at same nest level.  */
 742 static void
 743 estimate_loops_at_level (first_loop)
 744      struct loop *first_loop;
 745 {
 746   struct loop *l, *loop = first_loop;
 747
 748   for (loop = first_loop; loop; loop = loop->next)
 749     {
 750       int n;
 751       edge e;
 752
 753       estimate_loops_at_level (loop->inner);
 754
 755       /* Find current loop back edge and mark it.  */
 756       for (e = loop->latch->succ; e->dest != loop->header; e = e->succ_next);
 757
 758       EDGE_INFO (e)->back_edge = 1;
 759
 760       /* In case the loop header is shared, ensure that it is the last
 761          one sharing the same header, so we avoid redundant work.  */
 762       if (loop->shared)
 763         {
 764           for (l = loop->next; l; l = l->next)
 765             if (l->header == loop->header)
 766               break;
 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       propagate_freq (loop->header);
 778     }
 779 }
 780
 781 /* Convert counts measured by profile driven feedback to frequencies.  */
 782 static void
 783 counts_to_freqs ()
 784 {
 785   HOST_WIDEST_INT count_max = 1;
 786   int i;
 787
 788   for (i = 0; i < n_basic_blocks; i++)
 789     if (BASIC_BLOCK (i)->count > count_max)
 790       count_max = BASIC_BLOCK (i)->count;
 791
 792   for (i = -2; i < n_basic_blocks; i++)
 793     {
 794       basic_block bb;
 795       if (i == -2)
 796         bb = ENTRY_BLOCK_PTR;
 797       else if (i == -1)
 798         bb = EXIT_BLOCK_PTR;
 799       else
 800         bb = BASIC_BLOCK (i);
 801       bb->frequency = ((bb->count * BB_FREQ_MAX + count_max / 2)
 802                        / count_max);
 803     }
 804 }
 805
 806 /* Return true if function is likely to be expensive, so there is no point
 807    to optimizer performance of prologue, epilogue or do inlining at the
 808    expense of code size growth.  THRESHOLD is the limit of number
 809    of isntructions function can execute at average to be still considered
 810    not expensive.  */
 811 bool
 812 expensive_function_p (threshold)
 813         int threshold;
 814 {
 815   unsigned int sum = 0;
 816   int i;
 817   unsigned int limit;
 818
 819   /* We can not compute accurately for large thresholds due to scaled
 820      frequencies.  */
 821   if (threshold > BB_FREQ_MAX)
 822     abort ();
 823
 824   /* Frequencies are out of range.  This either means that function contains
 825      internal loop executing more than BB_FREQ_MAX times or profile feedback
 826      is available and function has not been executed at all.  */
 827   if (ENTRY_BLOCK_PTR->frequency == 0)
 828     return true;
 829
 830   /* Maximally BB_FREQ_MAX^2 so overflow won't happen.  */
 831   limit = ENTRY_BLOCK_PTR->frequency * threshold;
 832   for (i = 0; i < n_basic_blocks; i++)
 833     {
 834       basic_block bb = BASIC_BLOCK (i);
 835       rtx insn;
 836
 837       for (insn = bb->head; insn != NEXT_INSN (bb->end);
 838            insn = NEXT_INSN (insn))
 839         {
 840           if (active_insn_p (insn))
 841             {
 842               sum += bb->frequency;
 843               if (sum > limit)
 844                 return true;
 845             }
 846         }
 847     }
 848   return false;
 849 }
 850
 851 /* Estimate basic blocks frequency by given branch probabilities.  */
 852 static void
 853 estimate_bb_frequencies (loops)
 854      struct loops *loops;
 855 {
 856   int i;
 857   double freq_max = 0;
 858
 859   mark_dfs_back_edges ();
 860   if (flag_branch_probabilities)
 861     {
 862       counts_to_freqs ();
 863       return;
 864     }
 865
 866   /* Fill in the probability values in flowgraph based on the REG_BR_PROB
 867      notes.  */
 868   for (i = 0; i < n_basic_blocks; i++)
 869     {
 870       rtx last_insn = BLOCK_END (i);
 871       int probability;
 872       edge fallthru, branch;
 873
 874       if (GET_CODE (last_insn) != JUMP_INSN || !any_condjump_p (last_insn)
 875           /* Avoid handling of conditional jumps jumping to fallthru edge.  */
 876           || BASIC_BLOCK (i)->succ->succ_next == NULL)
 877         {
 878           /* We can predict only conditional jumps at the moment.
 879              Expect each edge to be equally probable.
 880              ?? In the future we want to make abnormal edges improbable.  */
 881           int nedges = 0;
 882           edge e;
 883
 884           for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
 885             {
 886               nedges++;
 887               if (e->probability != 0)
 888                 break;
 889             }
 890           if (!e)
 891             for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
 892               e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
 893         }
 894       else
 895         {
 896           probability = INTVAL (XEXP (find_reg_note (last_insn,
 897                                                      REG_BR_PROB, 0), 0));
 898           fallthru = BASIC_BLOCK (i)->succ;
 899           if (!fallthru->flags & EDGE_FALLTHRU)
 900             fallthru = fallthru->succ_next;
 901           branch = BASIC_BLOCK (i)->succ;
 902           if (branch->flags & EDGE_FALLTHRU)
 903             branch = branch->succ_next;
 904
 905           branch->probability = probability;
 906           fallthru->probability = REG_BR_PROB_BASE - probability;
 907         }
 908     }
 909   ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
 910
 911   /* Set up block info for each basic block.  */
 912   alloc_aux_for_blocks (sizeof (struct block_info_def));
 913   alloc_aux_for_edges (sizeof (struct edge_info_def));
 914   for (i = -2; i < n_basic_blocks; i++)
 915     {
 916       edge e;
 917       basic_block bb;
 918
 919       if (i == -2)
 920         bb = ENTRY_BLOCK_PTR;
 921       else if (i == -1)
 922         bb = EXIT_BLOCK_PTR;
 923       else
 924         bb = BASIC_BLOCK (i);
 925       BLOCK_INFO (bb)->tovisit = 0;
 926       for (e = bb->succ; e; e = e->succ_next)
 927         EDGE_INFO (e)->back_edge_prob = ((double) e->probability
 928                                          / REG_BR_PROB_BASE);
 929     }
 930   /* First compute probabilities locally for each loop from innermost
 931      to outermost to examine probabilities for back edges.  */
 932   estimate_loops_at_level (loops->tree_root);
 933
 934   /* Now fake loop around whole function to finalize probabilities.  */
 935   for (i = 0; i < n_basic_blocks; i++)
 936     BLOCK_INFO (BASIC_BLOCK (i))->tovisit = 1;
 937   BLOCK_INFO (ENTRY_BLOCK_PTR)->tovisit = 1;
 938   BLOCK_INFO (EXIT_BLOCK_PTR)->tovisit = 1;
 939   propagate_freq (ENTRY_BLOCK_PTR);
 940
 941   for (i = 0; i < n_basic_blocks; i++)
 942     if (BLOCK_INFO (BASIC_BLOCK (i))->frequency > freq_max)
 943       freq_max = BLOCK_INFO (BASIC_BLOCK (i))->frequency;
 944   for (i = -2; i < n_basic_blocks; i++)
 945     {
 946       basic_block bb;
 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       bb->frequency = (BLOCK_INFO (bb)->frequency * BB_FREQ_MAX / freq_max
 954                        + 0.5);
 955     }
 956
 957   free_aux_for_blocks ();
 958   free_aux_for_edges ();
 959 }