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 "profile.h"
  49 #include "real.h"
  50 #include "params.h"
  51 #include "target.h"
  52
  53 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 0.5,
  54                    REAL_BB_FREQ_MAX.  */
  55 static REAL_VALUE_TYPE real_zero, real_one, real_almost_one, real_br_prob_base,
  56                        real_one_half, real_bb_freq_max;
  57
  58 /* Random guesstimation given names.  */
  59 #define PROB_NEVER              (0)
  60 #define PROB_VERY_UNLIKELY      (REG_BR_PROB_BASE / 10 - 1)
  61 #define PROB_UNLIKELY           (REG_BR_PROB_BASE * 4 / 10 - 1)
  62 #define PROB_EVEN               (REG_BR_PROB_BASE / 2)
  63 #define PROB_LIKELY             (REG_BR_PROB_BASE - PROB_UNLIKELY)
  64 #define PROB_VERY_LIKELY        (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
  65 #define PROB_ALWAYS             (REG_BR_PROB_BASE)
  66
  67 static bool predicted_by_p               PARAMS ((basic_block,
  68                                                   enum br_predictor));
  69 static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
  70 static void dump_prediction              PARAMS ((enum br_predictor, int,
  71                                                   basic_block, int));
  72 static void estimate_loops_at_level      PARAMS ((struct loop *loop));
  73 static void propagate_freq               PARAMS ((basic_block));
  74 static void estimate_bb_frequencies      PARAMS ((struct loops *));
  75 static void counts_to_freqs              PARAMS ((void));
  76 static void process_note_predictions     PARAMS ((basic_block, int *, int *,
  77                                                   sbitmap *));
  78 static void process_note_prediction      PARAMS ((basic_block, int *, int *,
  79                                                   sbitmap *, int, int));
  80 static bool last_basic_block_p           PARAMS ((basic_block));
  81 static void compute_function_frequency   PARAMS ((void));
  82 static void choose_function_section      PARAMS ((void));
  83
  84 /* Information we hold about each branch predictor.
  85    Filled using information from predict.def.  */
  86
  87 struct predictor_info
  88 {
  89   const char *const name;       /* Name used in the debugging dumps.  */
  90   const int hitrate;            /* Expected hitrate used by
  91                                    predict_insn_def call.  */
  92   const int flags;
  93 };
  94
  95 /* Use given predictor without Dempster-Shaffer theory if it matches
  96    using first_match heuristics.  */
  97 #define PRED_FLAG_FIRST_MATCH 1
  98
  99 /* Recompute hitrate in percent to our representation.  */
 100
 101 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
 102
 103 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
 104 static const struct predictor_info predictor_info[]= {
 105 #include "predict.def"
 106
 107   /* Upper bound on predictors.  */
 108   {NULL, 0, 0}
 109 };
 110 #undef DEF_PREDICTOR
 111
 112 /* Return true in case BB can be CPU intensive and should be optimized
 113    for maximal perofmrance.  */
 114
 115 bool
 116 maybe_hot_bb_p (bb)
 117      basic_block bb;
 118 {
 119   if (profile_info.count_profiles_merged
 120       && flag_branch_probabilities
 121       && (bb->count
 122           < profile_info.max_counter_in_program
 123           / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
 124     return false;
 125   if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
 126     return false;
 127   return true;
 128 }
 129
 130 /* Return true in case BB is cold and should be optimized for size.  */
 131
 132 bool
 133 probably_cold_bb_p (bb)
 134      basic_block bb;
 135 {
 136   if (profile_info.count_profiles_merged
 137       && flag_branch_probabilities
 138       && (bb->count
 139           < profile_info.max_counter_in_program
 140           / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
 141     return true;
 142   if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
 143     return true;
 144   return false;
 145 }
 146
 147 /* Return true in case BB is probably never executed.  */
 148 bool
 149 probably_never_executed_bb_p (bb)
 150         basic_block bb;
 151 {
 152   if (profile_info.count_profiles_merged
 153       && flag_branch_probabilities)
 154     return ((bb->count + profile_info.count_profiles_merged / 2)
 155             / profile_info.count_profiles_merged) == 0;
 156   return false;
 157 }
 158
 159 /* Return true if the one of outgoing edges is already predicted by
 160    PREDICTOR.  */
 161
 162 static bool
 163 predicted_by_p (bb, predictor)
 164      basic_block bb;
 165      enum br_predictor predictor;
 166 {
 167   rtx note;
 168   if (!INSN_P (bb->end))
 169     return false;
 170   for (note = REG_NOTES (bb->end); note; note = XEXP (note, 1))
 171     if (REG_NOTE_KIND (note) == REG_BR_PRED
 172         && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
 173       return true;
 174   return false;
 175 }
 176
 177 void
 178 predict_insn (insn, predictor, probability)
 179      rtx insn;
 180      int probability;
 181      enum br_predictor predictor;
 182 {
 183   if (!any_condjump_p (insn))
 184     abort ();
 185
 186   REG_NOTES (insn)
 187     = gen_rtx_EXPR_LIST (REG_BR_PRED,
 188                          gen_rtx_CONCAT (VOIDmode,
 189                                          GEN_INT ((int) predictor),
 190                                          GEN_INT ((int) probability)),
 191                          REG_NOTES (insn));
 192 }
 193
 194 /* Predict insn by given predictor.  */
 195
 196 void
 197 predict_insn_def (insn, predictor, taken)
 198      rtx insn;
 199      enum br_predictor predictor;
 200      enum prediction taken;
 201 {
 202    int probability = predictor_info[(int) predictor].hitrate;
 203
 204    if (taken != TAKEN)
 205      probability = REG_BR_PROB_BASE - probability;
 206
 207    predict_insn (insn, predictor, probability);
 208 }
 209
 210 /* Predict edge E with given probability if possible.  */
 211
 212 void
 213 predict_edge (e, predictor, probability)
 214      edge e;
 215      int probability;
 216      enum br_predictor predictor;
 217 {
 218   rtx last_insn;
 219   last_insn = e->src->end;
 220
 221   /* We can store the branch prediction information only about
 222      conditional jumps.  */
 223   if (!any_condjump_p (last_insn))
 224     return;
 225
 226   /* We always store probability of branching.  */
 227   if (e->flags & EDGE_FALLTHRU)
 228     probability = REG_BR_PROB_BASE - probability;
 229
 230   predict_insn (last_insn, predictor, probability);
 231 }
 232
 233 /* Predict edge E by given predictor if possible.  */
 234
 235 void
 236 predict_edge_def (e, predictor, taken)
 237      edge e;
 238      enum br_predictor predictor;
 239      enum prediction taken;
 240 {
 241    int probability = predictor_info[(int) predictor].hitrate;
 242
 243    if (taken != TAKEN)
 244      probability = REG_BR_PROB_BASE - probability;
 245
 246    predict_edge (e, predictor, probability);
 247 }
 248
 249 /* Invert all branch predictions or probability notes in the INSN.  This needs
 250    to be done each time we invert the condition used by the jump.  */
 251
 252 void
 253 invert_br_probabilities (insn)
 254      rtx insn;
 255 {
 256   rtx note;
 257
 258   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 259     if (REG_NOTE_KIND (note) == REG_BR_PROB)
 260       XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
 261     else if (REG_NOTE_KIND (note) == REG_BR_PRED)
 262       XEXP (XEXP (note, 0), 1)
 263         = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
 264 }
 265
 266 /* Dump information about the branch prediction to the output file.  */
 267
 268 static void
 269 dump_prediction (predictor, probability, bb, used)
 270      enum br_predictor predictor;
 271      int probability;
 272      basic_block bb;
 273      int used;
 274 {
 275   edge e = bb->succ;
 276
 277   if (!rtl_dump_file)
 278     return;
 279
 280   while (e && (e->flags & EDGE_FALLTHRU))
 281     e = e->succ_next;
 282
 283   fprintf (rtl_dump_file, "  %s heuristics%s: %.1f%%",
 284            predictor_info[predictor].name,
 285            used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
 286
 287   if (bb->count)
 288     {
 289       fprintf (rtl_dump_file, "  exec ");
 290       fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 291       if (e)
 292         {
 293           fprintf (rtl_dump_file, " hit ");
 294           fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 295           fprintf (rtl_dump_file, " (%.1f%%)", e->count * 100.0 / bb->count);
 296         }
 297     }
 298
 299   fprintf (rtl_dump_file, "\n");
 300 }
 301
 302 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
 303    note if not already present.  Remove now useless REG_BR_PRED notes.  */
 304
 305 static void
 306 combine_predictions_for_insn (insn, bb)
 307      rtx insn;
 308      basic_block bb;
 309 {
 310   rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
 311   rtx *pnote = &REG_NOTES (insn);
 312   rtx note;
 313   int best_probability = PROB_EVEN;
 314   int best_predictor = END_PREDICTORS;
 315   int combined_probability = REG_BR_PROB_BASE / 2;
 316   int d;
 317   bool first_match = false;
 318   bool found = false;
 319
 320   if (rtl_dump_file)
 321     fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
 322              bb->index);
 323
 324   /* We implement "first match" heuristics and use probability guessed
 325      by predictor with smallest index.  In the future we will use better
 326      probability combination techniques.  */
 327   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 328     if (REG_NOTE_KIND (note) == REG_BR_PRED)
 329       {
 330         int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
 331         int probability = INTVAL (XEXP (XEXP (note, 0), 1));
 332
 333         found = true;
 334         if (best_predictor > predictor)
 335           best_probability = probability, best_predictor = predictor;
 336
 337         d = (combined_probability * probability
 338              + (REG_BR_PROB_BASE - combined_probability)
 339              * (REG_BR_PROB_BASE - probability));
 340
 341         /* Use FP math to avoid overflows of 32bit integers.  */
 342         if (d == 0)
 343           /* If one probability is 0% and one 100%, avoid division by zero.  */
 344           combined_probability = REG_BR_PROB_BASE / 2;
 345         else
 346           combined_probability = (((double) combined_probability) * probability
 347                                   * REG_BR_PROB_BASE / d + 0.5);
 348       }
 349
 350   /* Decide which heuristic to use.  In case we didn't match anything,
 351      use no_prediction heuristic, in case we did match, use either
 352      first match or Dempster-Shaffer theory depending on the flags.  */
 353
 354   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
 355     first_match = true;
 356
 357   if (!found)
 358     dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true);
 359   else
 360     {
 361       dump_prediction (PRED_DS_THEORY, combined_probability, bb, !first_match);
 362       dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match);
 363     }
 364
 365   if (first_match)
 366     combined_probability = best_probability;
 367   dump_prediction (PRED_COMBINED, combined_probability, bb, true);
 368
 369   while (*pnote)
 370     {
 371       if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
 372         {
 373           int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
 374           int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
 375
 376           dump_prediction (predictor, probability, bb,
 377                            !first_match || best_predictor == predictor);
 378           *pnote = XEXP (*pnote, 1);
 379         }
 380       else
 381         pnote = &XEXP (*pnote, 1);
 382     }
 383
 384   if (!prob_note)
 385     {
 386       REG_NOTES (insn)
 387         = gen_rtx_EXPR_LIST (REG_BR_PROB,
 388                              GEN_INT (combined_probability), REG_NOTES (insn));
 389
 390       /* Save the prediction into CFG in case we are seeing non-degenerated
 391          conditional jump.  */
 392       if (bb->succ->succ_next)
 393         {
 394           BRANCH_EDGE (bb)->probability = combined_probability;
 395           FALLTHRU_EDGE (bb)->probability
 396             = REG_BR_PROB_BASE - combined_probability;
 397         }
 398     }
 399 }
 400
 401 /* Statically estimate the probability that a branch will be taken.
 402    ??? In the next revision there will be a number of other predictors added
 403    from the above references. Further, each heuristic will be factored out
 404    into its own function for clarity (and to facilitate the combination of
 405    predictions).  */
 406
 407 void
 408 estimate_probability (loops_info)
 409      struct loops *loops_info;
 410 {
 411   sbitmap *dominators, *post_dominators;
 412   int i;
 413
 414   dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 415   post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 416   calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
 417   calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
 418
 419   /* Try to predict out blocks in a loop that are not part of a
 420      natural loop.  */
 421   for (i = 0; i < loops_info->num; i++)
 422     {
 423       int j;
 424       int exits;
 425       struct loop *loop = &loops_info->array[i];
 426
 427       flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
 428       exits = loop->num_exits;
 429
 430       for (j = loop->first->index; j <= loop->last->index; ++j)
 431         if (TEST_BIT (loop->nodes, j))
 432           {
 433             int header_found = 0;
 434             edge e;
 435
 436           /* Bypass loop heuristics on continue statement.  These
 437              statements construct loops via "non-loop" constructs
 438              in the source language and are better to be handled
 439              separately.  */
 440           if (predicted_by_p (BASIC_BLOCK (j), PRED_CONTINUE))
 441             continue;
 442
 443             /* Loop branch heuristics - predict an edge back to a
 444                loop's head as taken.  */
 445             for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
 446               if (e->dest == loop->header
 447                   && e->src == loop->latch)
 448                 {
 449                   header_found = 1;
 450                   predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
 451                 }
 452
 453             /* Loop exit heuristics - predict an edge exiting the loop if the
 454                conditinal has no loop header successors as not taken.  */
 455             if (!header_found)
 456               for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
 457                 if (e->dest->index < 0
 458                     || !TEST_BIT (loop->nodes, e->dest->index))
 459                   predict_edge
 460                     (e, PRED_LOOP_EXIT,
 461                      (REG_BR_PROB_BASE
 462                       - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
 463                      / exits);
 464           }
 465     }
 466
 467   /* Attempt to predict conditional jumps using a number of heuristics.  */
 468   for (i = 0; i < n_basic_blocks; i++)
 469     {
 470       basic_block bb = BASIC_BLOCK (i);
 471       rtx last_insn = bb->end;
 472       rtx cond, earliest;
 473       edge e;
 474
 475       if (GET_CODE (last_insn) != JUMP_INSN || ! any_condjump_p (last_insn))
 476         continue;
 477
 478       for (e = bb->succ; e; e = e->succ_next)
 479         {
 480           /* Predict early returns to be probable, as we've already taken
 481              care for error returns and other are often used for fast paths
 482              trought function.  */
 483           if ((e->dest == EXIT_BLOCK_PTR
 484                || (e->dest->succ && !e->dest->succ->succ_next
 485                    && e->dest->succ->dest == EXIT_BLOCK_PTR))
 486                && !predicted_by_p (bb, PRED_NULL_RETURN)
 487                && !predicted_by_p (bb, PRED_CONST_RETURN)
 488                && !predicted_by_p (bb, PRED_NEGATIVE_RETURN)
 489                && !last_basic_block_p (e->dest))
 490             predict_edge_def (e, PRED_EARLY_RETURN, TAKEN);
 491
 492           /* Look for block we are guarding (ie we dominate it,
 493              but it doesn't postdominate us).  */
 494           if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
 495               && TEST_BIT (dominators[e->dest->index], e->src->index)
 496               && !TEST_BIT (post_dominators[e->src->index], e->dest->index))
 497             {
 498               rtx insn;
 499
 500               /* The call heuristic claims that a guarded function call
 501                  is improbable.  This is because such calls are often used
 502                  to signal exceptional situations such as printing error
 503                  messages.  */
 504               for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end);
 505                    insn = NEXT_INSN (insn))
 506                 if (GET_CODE (insn) == CALL_INSN
 507                     /* Constant and pure calls are hardly used to signalize
 508                        something exceptional.  */
 509                     && ! CONST_OR_PURE_CALL_P (insn))
 510                   {
 511                     predict_edge_def (e, PRED_CALL, NOT_TAKEN);
 512                     break;
 513                   }
 514             }
 515         }
 516
 517       cond = get_condition (last_insn, &earliest);
 518       if (! cond)
 519         continue;
 520
 521       /* Try "pointer heuristic."
 522          A comparison ptr == 0 is predicted as false.
 523          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 524       if (GET_RTX_CLASS (GET_CODE (cond)) == '<'
 525           && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
 526               || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
 527         {
 528           if (GET_CODE (cond) == EQ)
 529             predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
 530           else if (GET_CODE (cond) == NE)
 531             predict_insn_def (last_insn, PRED_POINTER, TAKEN);
 532         }
 533       else
 534
 535       /* Try "opcode heuristic."
 536          EQ tests are usually false and NE tests are usually true. Also,
 537          most quantities are positive, so we can make the appropriate guesses
 538          about signed comparisons against zero.  */
 539         switch (GET_CODE (cond))
 540           {
 541           case CONST_INT:
 542             /* Unconditional branch.  */
 543             predict_insn_def (last_insn, PRED_UNCONDITIONAL,
 544                               cond == const0_rtx ? NOT_TAKEN : TAKEN);
 545             break;
 546
 547           case EQ:
 548           case UNEQ:
 549             /* Floating point comparisons appears to behave in a very
 550                inpredictable way because of special role of = tests in
 551                FP code.  */
 552             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 553               ;
 554             /* Comparisons with 0 are often used for booleans and there is
 555                nothing usefull to predict about them.  */
 556             else if (XEXP (cond, 1) == const0_rtx
 557                      || XEXP (cond, 0) == const0_rtx)
 558               ;
 559             else
 560               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
 561             break;
 562
 563           case NE:
 564           case LTGT:
 565             /* Floating point comparisons appears to behave in a very
 566                inpredictable way because of special role of = tests in
 567                FP code.  */
 568             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 569               ;
 570             /* Comparisons with 0 are often used for booleans and there is
 571                nothing usefull to predict about them.  */
 572             else if (XEXP (cond, 1) == const0_rtx
 573                      || XEXP (cond, 0) == const0_rtx)
 574               ;
 575             else
 576               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
 577             break;
 578
 579           case ORDERED:
 580             predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
 581             break;
 582
 583           case UNORDERED:
 584             predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
 585             break;
 586
 587           case LE:
 588           case LT:
 589             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 590                 || XEXP (cond, 1) == constm1_rtx)
 591               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
 592             break;
 593
 594           case GE:
 595           case GT:
 596             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 597                 || XEXP (cond, 1) == constm1_rtx)
 598               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
 599             break;
 600
 601           default:
 602             break;
 603           }
 604     }
 605
 606   /* Attach the combined probability to each conditional jump.  */
 607   for (i = 0; i < n_basic_blocks; i++)
 608     if (GET_CODE (BLOCK_END (i)) == JUMP_INSN
 609         && any_condjump_p (BLOCK_END (i))
 610         && BASIC_BLOCK (i)->succ->succ_next != NULL)
 611       combine_predictions_for_insn (BLOCK_END (i), BASIC_BLOCK (i));
 612
 613   sbitmap_vector_free (post_dominators);
 614   sbitmap_vector_free (dominators);
 615
 616   estimate_bb_frequencies (loops_info);
 617 }
 618 \f
 619 /* __builtin_expect dropped tokens into the insn stream describing expected
 620    values of registers.  Generate branch probabilities based off these
 621    values.  */
 622
 623 void
 624 expected_value_to_br_prob ()
 625 {
 626   rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
 627
 628   for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
 629     {
 630       switch (GET_CODE (insn))
 631         {
 632         case NOTE:
 633           /* Look for expected value notes.  */
 634           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
 635             {
 636               ev = NOTE_EXPECTED_VALUE (insn);
 637               ev_reg = XEXP (ev, 0);
 638               delete_insn (insn);
 639             }
 640           continue;
 641
 642         case CODE_LABEL:
 643           /* Never propagate across labels.  */
 644           ev = NULL_RTX;
 645           continue;
 646
 647         case JUMP_INSN:
 648           /* Look for simple conditional branches.  If we haven't got an
 649              expected value yet, no point going further.  */
 650           if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX
 651               || ! any_condjump_p (insn))
 652             continue;
 653           break;
 654
 655         default:
 656           /* Look for insns that clobber the EV register.  */
 657           if (ev && reg_set_p (ev_reg, insn))
 658             ev = NULL_RTX;
 659           continue;
 660         }
 661
 662       /* Collect the branch condition, hopefully relative to EV_REG.  */
 663       /* ???  At present we'll miss things like
 664                 (expected_value (eq r70 0))
 665                 (set r71 -1)
 666                 (set r80 (lt r70 r71))
 667                 (set pc (if_then_else (ne r80 0) ...))
 668          as canonicalize_condition will render this to us as
 669                 (lt r70, r71)
 670          Could use cselib to try and reduce this further.  */
 671       cond = XEXP (SET_SRC (pc_set (insn)), 0);
 672       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
 673       if (! cond || XEXP (cond, 0) != ev_reg
 674           || GET_CODE (XEXP (cond, 1)) != CONST_INT)
 675         continue;
 676
 677       /* Substitute and simplify.  Given that the expression we're
 678          building involves two constants, we should wind up with either
 679          true or false.  */
 680       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 681                              XEXP (ev, 1), XEXP (cond, 1));
 682       cond = simplify_rtx (cond);
 683
 684       /* Turn the condition into a scaled branch probability.  */
 685       if (cond != const_true_rtx && cond != const0_rtx)
 686         abort ();
 687       predict_insn_def (insn, PRED_BUILTIN_EXPECT,
 688                         cond == const_true_rtx ? TAKEN : NOT_TAKEN);
 689     }
 690 }
 691 \f
 692 /* Check whether this is the last basic block of function.  Commonly tehre
 693    is one extra common cleanup block.  */
 694 static bool
 695 last_basic_block_p (bb)
 696      basic_block bb;
 697 {
 698   if (bb == EXIT_BLOCK_PTR)
 699     return false;
 700
 701   return (bb->next_bb == EXIT_BLOCK_PTR
 702           || (bb->next_bb->next_bb == EXIT_BLOCK_PTR
 703               && bb->succ && !bb->succ->succ_next
 704               && bb->succ->dest->next_bb == EXIT_BLOCK_PTR));
 705 }
 706
 707 /* Sets branch probabilities according to PREDiction and FLAGS. HEADS[bb->index]
 708    should be index of basic block in that we need to alter branch predictions
 709    (i.e. the first of our dominators such that we do not post-dominate it)
 710    (but we fill this information on demand, so -1 may be there in case this
 711    was not needed yet).  */
 712
 713 static void
 714 process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
 715      basic_block bb;
 716      int *heads;
 717      int *dominators;
 718      sbitmap *post_dominators;
 719      int pred;
 720      int flags;
 721 {
 722   edge e;
 723   int y;
 724   bool taken;
 725
 726   taken = flags & IS_TAKEN;
 727
 728   if (heads[bb->index] < 0)
 729     {
 730       /* This is first time we need this field in heads array; so
 731          find first dominator that we do not post-dominate (we are
 732          using already known members of heads array).  */
 733       int ai = bb->index;
 734       int next_ai = dominators[bb->index];
 735       int head;
 736
 737       while (heads[next_ai] < 0)
 738         {
 739           if (!TEST_BIT (post_dominators[next_ai], bb->index))
 740             break;
 741           heads[next_ai] = ai;
 742           ai = next_ai;
 743           next_ai = dominators[next_ai];
 744         }
 745       if (!TEST_BIT (post_dominators[next_ai], bb->index))
 746         head = next_ai;
 747       else
 748         head = heads[next_ai];
 749       while (next_ai != bb->index)
 750         {
 751           next_ai = ai;
 752           ai = heads[ai];
 753           heads[next_ai] = head;
 754         }
 755     }
 756   y = heads[bb->index];
 757
 758   /* Now find the edge that leads to our branch and aply the prediction.  */
 759
 760   if (y == n_basic_blocks)
 761     return;
 762   for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
 763     if (e->dest->index >= 0
 764         && TEST_BIT (post_dominators[e->dest->index], bb->index))
 765       predict_edge_def (e, pred, taken);
 766 }
 767
 768 /* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them
 769    into branch probabilities.  For description of heads array, see
 770    process_note_prediction.  */
 771
 772 static void
 773 process_note_predictions (bb, heads, dominators, post_dominators)
 774      basic_block bb;
 775      int *heads;
 776      int *dominators;
 777      sbitmap *post_dominators;
 778 {
 779   rtx insn;
 780   edge e;
 781
 782   /* Additionaly, we check here for blocks with no successors.  */
 783   int contained_noreturn_call = 0;
 784   int was_bb_head = 0;
 785   int noreturn_block = 1;
 786
 787   for (insn = bb->end; insn;
 788        was_bb_head |= (insn == bb->head), insn = PREV_INSN (insn))
 789     {
 790       if (GET_CODE (insn) != NOTE)
 791         {
 792           if (was_bb_head)
 793             break;
 794           else
 795             {
 796               /* Noreturn calls cause program to exit, therefore they are
 797                  always predicted as not taken.  */
 798               if (GET_CODE (insn) == CALL_INSN
 799                   && find_reg_note (insn, REG_NORETURN, NULL))
 800                 contained_noreturn_call = 1;
 801               continue;
 802             }
 803         }
 804       if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION)
 805         {
 806           int alg = (int) NOTE_PREDICTION_ALG (insn);
 807           /* Process single prediction note.  */
 808           process_note_prediction (bb,
 809                                    heads,
 810                                    dominators,
 811                                    post_dominators,
 812                                    alg, (int) NOTE_PREDICTION_FLAGS (insn));
 813           delete_insn (insn);
 814         }
 815     }
 816   for (e = bb->succ; e; e = e->succ_next)
 817     if (!(e->flags & EDGE_FAKE))
 818       noreturn_block = 0;
 819   if (contained_noreturn_call)
 820     {
 821       /* This block ended from other reasons than because of return.
 822          If it is because of noreturn call, this should certainly not
 823          be taken.  Otherwise it is probably some error recovery.  */
 824       process_note_prediction (bb,
 825                                heads,
 826                                dominators,
 827                                post_dominators, PRED_NORETURN, NOT_TAKEN);
 828     }
 829 }
 830
 831 /* Gathers NOTE_INSN_PREDICTIONs and turns them into
 832    branch probabilities.  */
 833
 834 void
 835 note_prediction_to_br_prob ()
 836 {
 837   int i;
 838   sbitmap *post_dominators;
 839   int *dominators, *heads;
 840
 841   /* To enable handling of noreturn blocks.  */
 842   add_noreturn_fake_exit_edges ();
 843   connect_infinite_loops_to_exit ();
 844
 845   dominators = xmalloc (sizeof (int) * n_basic_blocks);
 846   memset (dominators, -1, sizeof (int) * n_basic_blocks);
 847   post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 848   calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
 849   calculate_dominance_info (dominators, NULL, CDI_DOMINATORS);
 850
 851   heads = xmalloc (sizeof (int) * n_basic_blocks);
 852   memset (heads, -1, sizeof (int) * n_basic_blocks);
 853   heads[ENTRY_BLOCK_PTR->next_bb->index] = n_basic_blocks;
 854
 855   /* Process all prediction notes.  */
 856
 857   for (i = 0; i < n_basic_blocks; ++i)
 858     {
 859       basic_block bb = BASIC_BLOCK (i);
 860       process_note_predictions (bb, heads, dominators, post_dominators);
 861     }
 862
 863   sbitmap_vector_free (post_dominators);
 864   free (dominators);
 865   free (heads);
 866
 867   remove_fake_edges ();
 868 }
 869 \f
 870 /* This is used to carry information about basic blocks.  It is
 871    attached to the AUX field of the standard CFG block.  */
 872
 873 typedef struct block_info_def
 874 {
 875   /* Estimated frequency of execution of basic_block.  */
 876   REAL_VALUE_TYPE frequency;
 877
 878   /* To keep queue of basic blocks to process.  */
 879   basic_block next;
 880
 881   /* True if block needs to be visited in prop_freqency.  */
 882   int tovisit:1;
 883
 884   /* Number of predecessors we need to visit first.  */
 885   int npredecessors;
 886 } *block_info;
 887
 888 /* Similar information for edges.  */
 889 typedef struct edge_info_def
 890 {
 891   /* In case edge is an loopback edge, the probability edge will be reached
 892      in case header is.  Estimated number of iterations of the loop can be
 893      then computed as 1 / (1 - back_edge_prob).  */
 894   REAL_VALUE_TYPE back_edge_prob;
 895   /* True if the edge is an loopback edge in the natural loop.  */
 896   int back_edge:1;
 897 } *edge_info;
 898
 899 #define BLOCK_INFO(B)   ((block_info) (B)->aux)
 900 #define EDGE_INFO(E)    ((edge_info) (E)->aux)
 901
 902 /* Helper function for estimate_bb_frequencies.
 903    Propagate the frequencies for loops headed by HEAD.  */
 904
 905 static void
 906 propagate_freq (head)
 907      basic_block head;
 908 {
 909   basic_block bb = head;
 910   basic_block last = bb;
 911   edge e;
 912   basic_block nextbb;
 913   int n;
 914
 915   /* For each basic block we need to visit count number of his predecessors
 916      we need to visit first.  */
 917   for (n = 0; n < n_basic_blocks; n++)
 918     {
 919       basic_block bb = BASIC_BLOCK (n);
 920       if (BLOCK_INFO (bb)->tovisit)
 921         {
 922           int count = 0;
 923
 924           for (e = bb->pred; e; e = e->pred_next)
 925             if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
 926               count++;
 927             else if (BLOCK_INFO (e->src)->tovisit
 928                      && rtl_dump_file && !EDGE_INFO (e)->back_edge)
 929               fprintf (rtl_dump_file,
 930                        "Irreducible region hit, ignoring edge to %i->%i\n",
 931                        e->src->index, bb->index);
 932           BLOCK_INFO (bb)->npredecessors = count;
 933         }
 934     }
 935
 936   memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
 937   for (; bb; bb = nextbb)
 938     {
 939       REAL_VALUE_TYPE cyclic_probability, frequency;
 940
 941       memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
 942       memcpy (&frequency, &real_zero, sizeof (real_zero));
 943
 944       nextbb = BLOCK_INFO (bb)->next;
 945       BLOCK_INFO (bb)->next = NULL;
 946
 947       /* Compute frequency of basic block.  */
 948       if (bb != head)
 949         {
 950 #ifdef ENABLE_CHECKING
 951           for (e = bb->pred; e; e = e->pred_next)
 952             if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
 953               abort ();
 954 #endif
 955
 956           for (e = bb->pred; e; e = e->pred_next)
 957             if (EDGE_INFO (e)->back_edge)
 958               {
 959                 REAL_ARITHMETIC (cyclic_probability, PLUS_EXPR,
 960                                  cyclic_probability,
 961                                  EDGE_INFO (e)->back_edge_prob);
 962               }
 963             else if (!(e->flags & EDGE_DFS_BACK))
 964               {
 965                 REAL_VALUE_TYPE tmp;
 966
 967                 /*  frequency += (e->probability
 968                                   * BLOCK_INFO (e->src)->frequency /
 969                                   REG_BR_PROB_BASE);  */
 970
 971                 REAL_VALUE_FROM_INT (tmp, e->probability, 0,
 972                                      TYPE_MODE (double_type_node));
 973                 REAL_ARITHMETIC (tmp, MULT_EXPR, tmp,
 974                                  BLOCK_INFO (e->src)->frequency);
 975                 REAL_ARITHMETIC (tmp, RDIV_EXPR, tmp, real_br_prob_base);
 976                 REAL_ARITHMETIC (frequency, PLUS_EXPR, frequency, tmp);
 977               }
 978
 979           if (REAL_VALUES_LESS (real_almost_one, cyclic_probability))
 980             memcpy (&cyclic_probability, &real_almost_one, sizeof (real_zero));
 981
 982           /* BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability)
 983            */
 984
 985           REAL_ARITHMETIC (cyclic_probability, MINUS_EXPR, real_one,
 986                            cyclic_probability);
 987           REAL_ARITHMETIC (BLOCK_INFO (bb)->frequency,
 988                            RDIV_EXPR, frequency, cyclic_probability);
 989         }
 990
 991       BLOCK_INFO (bb)->tovisit = 0;
 992
 993       /* Compute back edge frequencies.  */
 994       for (e = bb->succ; e; e = e->succ_next)
 995         if (e->dest == head)
 996           {
 997             REAL_VALUE_TYPE tmp;
 998
 999             /* EDGE_INFO (e)->back_edge_prob
1000                   = ((e->probability * BLOCK_INFO (bb)->frequency)
1001                      / REG_BR_PROB_BASE); */
1002             REAL_VALUE_FROM_INT (tmp, e->probability, 0,
1003                                  TYPE_MODE (double_type_node));
1004             REAL_ARITHMETIC (tmp, MULT_EXPR, tmp,
1005                              BLOCK_INFO (bb)->frequency);
1006             REAL_ARITHMETIC (EDGE_INFO (e)->back_edge_prob,
1007                              RDIV_EXPR, tmp, real_br_prob_base);
1008
1009           }
1010
1011       /* Propagate to successor blocks.  */
1012       for (e = bb->succ; e; e = e->succ_next)
1013         if (!(e->flags & EDGE_DFS_BACK)
1014             && BLOCK_INFO (e->dest)->npredecessors)
1015           {
1016             BLOCK_INFO (e->dest)->npredecessors--;
1017             if (!BLOCK_INFO (e->dest)->npredecessors)
1018               {
1019                 if (!nextbb)
1020                   nextbb = e->dest;
1021                 else
1022                   BLOCK_INFO (last)->next = e->dest;
1023
1024                 last = e->dest;
1025               }
1026            }
1027     }
1028 }
1029
1030 /* Estimate probabilities of loopback edges in loops at same nest level.  */
1031
1032 static void
1033 estimate_loops_at_level (first_loop)
1034      struct loop *first_loop;
1035 {
1036   struct loop *l, *loop = first_loop;
1037
1038   for (loop = first_loop; loop; loop = loop->next)
1039     {
1040       int n;
1041       edge e;
1042
1043       estimate_loops_at_level (loop->inner);
1044
1045       /* Find current loop back edge and mark it.  */
1046       for (e = loop->latch->succ; e->dest != loop->header; e = e->succ_next)
1047         ;
1048
1049       EDGE_INFO (e)->back_edge = 1;
1050
1051       /* In case the loop header is shared, ensure that it is the last
1052          one sharing the same header, so we avoid redundant work.  */
1053       if (loop->shared)
1054         {
1055           for (l = loop->next; l; l = l->next)
1056             if (l->header == loop->header)
1057               break;
1058
1059           if (l)
1060             continue;
1061         }
1062
1063       /* Now merge all nodes of all loops with given header as not visited.  */
1064       for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next)
1065         if (loop->header == l->header)
1066           EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n,
1067                                      BLOCK_INFO (BASIC_BLOCK (n))->tovisit = 1
1068                                      );
1069
1070       propagate_freq (loop->header);
1071     }
1072 }
1073
1074 /* Convert counts measured by profile driven feedback to frequencies.  */
1075
1076 static void
1077 counts_to_freqs ()
1078 {
1079   HOST_WIDEST_INT count_max = 1;
1080   int i;
1081
1082   for (i = 0; i < n_basic_blocks; i++)
1083     count_max = MAX (BASIC_BLOCK (i)->count, count_max);
1084
1085   for (i = -2; i < n_basic_blocks; i++)
1086     {
1087       basic_block bb;
1088
1089       if (i == -2)
1090         bb = ENTRY_BLOCK_PTR;
1091       else if (i == -1)
1092         bb = EXIT_BLOCK_PTR;
1093       else
1094         bb = BASIC_BLOCK (i);
1095
1096       bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1097     }
1098 }
1099
1100 /* Return true if function is likely to be expensive, so there is no point to
1101    optimize performance of prologue, epilogue or do inlining at the expense
1102    of code size growth.  THRESHOLD is the limit of number of isntructions
1103    function can execute at average to be still considered not expensive.  */
1104
1105 bool
1106 expensive_function_p (threshold)
1107         int threshold;
1108 {
1109   unsigned int sum = 0;
1110   int i;
1111   unsigned int limit;
1112
1113   /* We can not compute accurately for large thresholds due to scaled
1114      frequencies.  */
1115   if (threshold > BB_FREQ_MAX)
1116     abort ();
1117
1118   /* Frequencies are out of range.  This either means that function contains
1119      internal loop executing more than BB_FREQ_MAX times or profile feedback
1120      is available and function has not been executed at all.  */
1121   if (ENTRY_BLOCK_PTR->frequency == 0)
1122     return true;
1123
1124   /* Maximally BB_FREQ_MAX^2 so overflow won't happen.  */
1125   limit = ENTRY_BLOCK_PTR->frequency * threshold;
1126   for (i = 0; i < n_basic_blocks; i++)
1127     {
1128       basic_block bb = BASIC_BLOCK (i);
1129       rtx insn;
1130
1131       for (insn = bb->head; insn != NEXT_INSN (bb->end);
1132            insn = NEXT_INSN (insn))
1133         if (active_insn_p (insn))
1134           {
1135             sum += bb->frequency;
1136             if (sum > limit)
1137               return true;
1138         }
1139     }
1140
1141   return false;
1142 }
1143
1144 /* Estimate basic blocks frequency by given branch probabilities.  */
1145
1146 static void
1147 estimate_bb_frequencies (loops)
1148      struct loops *loops;
1149 {
1150   int i;
1151   REAL_VALUE_TYPE freq_max;
1152   enum machine_mode double_mode = TYPE_MODE (double_type_node);
1153
1154   if (flag_branch_probabilities)
1155     counts_to_freqs ();
1156   else
1157     {
1158       REAL_VALUE_FROM_INT (real_zero, 0, 0, double_mode);
1159       REAL_VALUE_FROM_INT (real_one, 1, 0, double_mode);
1160       REAL_VALUE_FROM_INT (real_br_prob_base, REG_BR_PROB_BASE, 0, double_mode);
1161       REAL_VALUE_FROM_INT (real_bb_freq_max, BB_FREQ_MAX, 0, double_mode);
1162       REAL_VALUE_FROM_INT (real_one_half, 2, 0, double_mode);
1163
1164       REAL_ARITHMETIC (real_one_half, RDIV_EXPR, real_one, real_one_half);
1165
1166       REAL_ARITHMETIC (real_almost_one, RDIV_EXPR, real_one, real_br_prob_base);
1167       REAL_ARITHMETIC (real_almost_one, MINUS_EXPR, real_one, real_almost_one);
1168
1169       mark_dfs_back_edges ();
1170       /* Fill in the probability values in flowgraph based on the REG_BR_PROB
1171          notes.  */
1172       for (i = 0; i < n_basic_blocks; i++)
1173         {
1174           rtx last_insn = BLOCK_END (i);
1175
1176           if (GET_CODE (last_insn) != JUMP_INSN || !any_condjump_p (last_insn)
1177               /* Avoid handling of conditional jumps jumping to fallthru edge.  */
1178               || BASIC_BLOCK (i)->succ->succ_next == NULL)
1179             {
1180               /* We can predict only conditional jumps at the moment.
1181                  Expect each edge to be equally probable.
1182                  ?? In the future we want to make abnormal edges improbable.  */
1183               int nedges = 0;
1184               edge e;
1185
1186               for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
1187                 {
1188                   nedges++;
1189                   if (e->probability != 0)
1190                     break;
1191                 }
1192               if (!e)
1193                 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
1194                   e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
1195             }
1196         }
1197
1198       ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
1199
1200       /* Set up block info for each basic block.  */
1201       alloc_aux_for_blocks (sizeof (struct block_info_def));
1202       alloc_aux_for_edges (sizeof (struct edge_info_def));
1203       for (i = -2; i < n_basic_blocks; i++)
1204         {
1205           edge e;
1206           basic_block bb;
1207
1208           if (i == -2)
1209             bb = ENTRY_BLOCK_PTR;
1210           else if (i == -1)
1211             bb = EXIT_BLOCK_PTR;
1212           else
1213             bb = BASIC_BLOCK (i);
1214
1215           BLOCK_INFO (bb)->tovisit = 0;
1216           for (e = bb->succ; e; e = e->succ_next)
1217             {
1218
1219               REAL_VALUE_FROM_INT (EDGE_INFO (e)->back_edge_prob,
1220                                    e->probability, 0, double_mode);
1221               REAL_ARITHMETIC (EDGE_INFO (e)->back_edge_prob,
1222                                RDIV_EXPR, EDGE_INFO (e)->back_edge_prob,
1223                                real_br_prob_base);
1224             }
1225         }
1226
1227       /* First compute probabilities locally for each loop from innermost
1228          to outermost to examine probabilities for back edges.  */
1229       estimate_loops_at_level (loops->tree_root);
1230
1231       /* Now fake loop around whole function to finalize probabilities.  */
1232       for (i = 0; i < n_basic_blocks; i++)
1233         BLOCK_INFO (BASIC_BLOCK (i))->tovisit = 1;
1234
1235       BLOCK_INFO (ENTRY_BLOCK_PTR)->tovisit = 1;
1236       BLOCK_INFO (EXIT_BLOCK_PTR)->tovisit = 1;
1237       propagate_freq (ENTRY_BLOCK_PTR);
1238
1239       memcpy (&freq_max, &real_zero, sizeof (real_zero));
1240       for (i = 0; i < n_basic_blocks; i++)
1241         if (REAL_VALUES_LESS
1242             (freq_max, BLOCK_INFO (BASIC_BLOCK (i))->frequency))
1243           memcpy (&freq_max, &BLOCK_INFO (BASIC_BLOCK (i))->frequency,
1244                   sizeof (freq_max));
1245
1246       for (i = -2; i < n_basic_blocks; i++)
1247         {
1248           basic_block bb;
1249           REAL_VALUE_TYPE tmp;
1250
1251           if (i == -2)
1252             bb = ENTRY_BLOCK_PTR;
1253           else if (i == -1)
1254             bb = EXIT_BLOCK_PTR;
1255           else
1256             bb = BASIC_BLOCK (i);
1257
1258           REAL_ARITHMETIC (tmp, MULT_EXPR, BLOCK_INFO (bb)->frequency,
1259                            real_bb_freq_max);
1260           REAL_ARITHMETIC (tmp, RDIV_EXPR, tmp, freq_max);
1261           REAL_ARITHMETIC (tmp, PLUS_EXPR, tmp, real_one_half);
1262           bb->frequency = REAL_VALUE_UNSIGNED_FIX (tmp);
1263         }
1264
1265       free_aux_for_blocks ();
1266       free_aux_for_edges ();
1267     }
1268   compute_function_frequency ();
1269   if (flag_reorder_functions)
1270     choose_function_section ();
1271 }
1272
1273 /* Decide whether function is hot, cold or unlikely executed.  */
1274 static void
1275 compute_function_frequency ()
1276 {
1277   int i;
1278   if (!profile_info.count_profiles_merged
1279       || !flag_branch_probabilities)
1280     return;
1281   cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1282   for (i = 0; i < n_basic_blocks; i++)
1283     {
1284       basic_block bb = BASIC_BLOCK (i);
1285       if (maybe_hot_bb_p (bb))
1286         {
1287           cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
1288           return;
1289         }
1290       if (!probably_never_executed_bb_p (bb))
1291         cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
1292     }
1293 }
1294
1295 /* Choose appropriate section for the function.  */
1296 static void
1297 choose_function_section ()
1298 {
1299   if (DECL_SECTION_NAME (current_function_decl)
1300       || !targetm.have_named_sections)
1301     return;
1302   if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
1303     DECL_SECTION_NAME (current_function_decl) =
1304       build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
1305   if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
1306     DECL_SECTION_NAME (current_function_decl) =
1307       build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
1308                     UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
1309 }