gcc/predict.c

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