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 #include "loop.h"
  53
  54 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 0.5,
  55                    REAL_BB_FREQ_MAX.  */
  56 static REAL_VALUE_TYPE real_zero, real_one, real_almost_one, real_br_prob_base,
  57                        real_one_half, real_bb_freq_max;
  58
  59 /* Random guesstimation given names.  */
  60 #define PROB_VERY_UNLIKELY      (REG_BR_PROB_BASE / 10 - 1)
  61 #define PROB_EVEN               (REG_BR_PROB_BASE / 2)
  62 #define PROB_VERY_LIKELY        (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
  63 #define PROB_ALWAYS             (REG_BR_PROB_BASE)
  64
  65 static bool predicted_by_p               PARAMS ((basic_block,
  66                                                   enum br_predictor));
  67 static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
  68 static void dump_prediction              PARAMS ((enum br_predictor, int,
  69                                                   basic_block, int));
  70 static void estimate_loops_at_level      PARAMS ((struct loop *loop));
  71 static void propagate_freq               PARAMS ((struct loop *));
  72 static void estimate_bb_frequencies      PARAMS ((struct loops *));
  73 static void counts_to_freqs              PARAMS ((void));
  74 static void process_note_predictions     PARAMS ((basic_block, int *,
  75                                                   dominance_info,
  76                                                   dominance_info));
  77 static void process_note_prediction      PARAMS ((basic_block, int *,
  78                                                   dominance_info,
  79                                                   dominance_info, 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   dominance_info dominators, post_dominators;
 412   basic_block bb;
 413   int i;
 414
 415   connect_infinite_loops_to_exit ();
 416   dominators = calculate_dominance_info (CDI_DOMINATORS);
 417   post_dominators = calculate_dominance_info (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 = 1; i < loops_info->num; i++)
 422     {
 423       basic_block bb, *bbs;
 424       int j;
 425       int exits;
 426       struct loop *loop = loops_info->parray[i];
 427
 428       flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
 429       exits = loop->num_exits;
 430
 431       bbs = get_loop_body (loop);
 432       for (j = 0; j < loop->num_nodes; j++)
 433         {
 434           int header_found = 0;
 435           edge e;
 436
 437           bb = bbs[j];
 438
 439           /* Bypass loop heuristics on continue statement.  These
 440              statements construct loops via "non-loop" constructs
 441              in the source language and are better to be handled
 442              separately.  */
 443           if (predicted_by_p (bb, PRED_CONTINUE))
 444             continue;
 445
 446           /* Loop branch heuristics - predict an edge back to a
 447              loop's head as taken.  */
 448           for (e = bb->succ; e; e = e->succ_next)
 449             if (e->dest == loop->header
 450                 && e->src == loop->latch)
 451               {
 452                 header_found = 1;
 453                 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
 454               }
 455
 456           /* Loop exit heuristics - predict an edge exiting the loop if the
 457              conditinal has no loop header successors as not taken.  */
 458           if (!header_found)
 459             for (e = bb->succ; e; e = e->succ_next)
 460               if (e->dest->index < 0
 461                   || !flow_bb_inside_loop_p (loop, e->dest))
 462                 predict_edge
 463                   (e, PRED_LOOP_EXIT,
 464                    (REG_BR_PROB_BASE
 465                     - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
 466                    / exits);
 467         }
 468     }
 469
 470   /* Attempt to predict conditional jumps using a number of heuristics.  */
 471   FOR_EACH_BB (bb)
 472     {
 473       rtx last_insn = bb->end;
 474       rtx cond, earliest;
 475       edge e;
 476
 477       if (GET_CODE (last_insn) != JUMP_INSN || ! any_condjump_p (last_insn))
 478         continue;
 479
 480       for (e = bb->succ; e; e = e->succ_next)
 481         {
 482           /* Predict early returns to be probable, as we've already taken
 483              care for error returns and other are often used for fast paths
 484              trought function.  */
 485           if ((e->dest == EXIT_BLOCK_PTR
 486                || (e->dest->succ && !e->dest->succ->succ_next
 487                    && e->dest->succ->dest == EXIT_BLOCK_PTR))
 488                && !predicted_by_p (bb, PRED_NULL_RETURN)
 489                && !predicted_by_p (bb, PRED_CONST_RETURN)
 490                && !predicted_by_p (bb, PRED_NEGATIVE_RETURN)
 491                && !last_basic_block_p (e->dest))
 492             predict_edge_def (e, PRED_EARLY_RETURN, TAKEN);
 493
 494           /* Look for block we are guarding (ie we dominate it,
 495              but it doesn't postdominate us).  */
 496           if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
 497               && dominated_by_p (dominators, e->dest, e->src)
 498               && !dominated_by_p (post_dominators, e->src, e->dest))
 499             {
 500               rtx insn;
 501
 502               /* The call heuristic claims that a guarded function call
 503                  is improbable.  This is because such calls are often used
 504                  to signal exceptional situations such as printing error
 505                  messages.  */
 506               for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end);
 507                    insn = NEXT_INSN (insn))
 508                 if (GET_CODE (insn) == CALL_INSN
 509                     /* Constant and pure calls are hardly used to signalize
 510                        something exceptional.  */
 511                     && ! CONST_OR_PURE_CALL_P (insn))
 512                   {
 513                     predict_edge_def (e, PRED_CALL, NOT_TAKEN);
 514                     break;
 515                   }
 516             }
 517         }
 518
 519       cond = get_condition (last_insn, &earliest);
 520       if (! cond)
 521         continue;
 522
 523       /* Try "pointer heuristic."
 524          A comparison ptr == 0 is predicted as false.
 525          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 526       if (GET_RTX_CLASS (GET_CODE (cond)) == '<'
 527           && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
 528               || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
 529         {
 530           if (GET_CODE (cond) == EQ)
 531             predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
 532           else if (GET_CODE (cond) == NE)
 533             predict_insn_def (last_insn, PRED_POINTER, TAKEN);
 534         }
 535       else
 536
 537       /* Try "opcode heuristic."
 538          EQ tests are usually false and NE tests are usually true. Also,
 539          most quantities are positive, so we can make the appropriate guesses
 540          about signed comparisons against zero.  */
 541         switch (GET_CODE (cond))
 542           {
 543           case CONST_INT:
 544             /* Unconditional branch.  */
 545             predict_insn_def (last_insn, PRED_UNCONDITIONAL,
 546                               cond == const0_rtx ? NOT_TAKEN : TAKEN);
 547             break;
 548
 549           case EQ:
 550           case UNEQ:
 551             /* Floating point comparisons appears to behave in a very
 552                inpredictable way because of special role of = tests in
 553                FP code.  */
 554             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 555               ;
 556             /* Comparisons with 0 are often used for booleans and there is
 557                nothing usefull to predict about them.  */
 558             else if (XEXP (cond, 1) == const0_rtx
 559                      || XEXP (cond, 0) == const0_rtx)
 560               ;
 561             else
 562               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
 563             break;
 564
 565           case NE:
 566           case LTGT:
 567             /* Floating point comparisons appears to behave in a very
 568                inpredictable way because of special role of = tests in
 569                FP code.  */
 570             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 571               ;
 572             /* Comparisons with 0 are often used for booleans and there is
 573                nothing usefull to predict about them.  */
 574             else if (XEXP (cond, 1) == const0_rtx
 575                      || XEXP (cond, 0) == const0_rtx)
 576               ;
 577             else
 578               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
 579             break;
 580
 581           case ORDERED:
 582             predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
 583             break;
 584
 585           case UNORDERED:
 586             predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
 587             break;
 588
 589           case LE:
 590           case LT:
 591             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 592                 || XEXP (cond, 1) == constm1_rtx)
 593               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
 594             break;
 595
 596           case GE:
 597           case GT:
 598             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 599                 || XEXP (cond, 1) == constm1_rtx)
 600               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
 601             break;
 602
 603           default:
 604             break;
 605           }
 606     }
 607
 608   /* Attach the combined probability to each conditional jump.  */
 609   FOR_EACH_BB (bb)
 610     if (GET_CODE (bb->end) == JUMP_INSN
 611         && any_condjump_p (bb->end)
 612         && bb->succ->succ_next != NULL)
 613       combine_predictions_for_insn (bb->end, bb);
 614
 615   free_dominance_info (post_dominators);
 616   free_dominance_info (dominators);
 617
 618   remove_fake_edges ();
 619   estimate_bb_frequencies (loops_info);
 620 }
 621 \f
 622 /* __builtin_expect dropped tokens into the insn stream describing expected
 623    values of registers.  Generate branch probabilities based off these
 624    values.  */
 625
 626 void
 627 expected_value_to_br_prob ()
 628 {
 629   rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
 630
 631   for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
 632     {
 633       switch (GET_CODE (insn))
 634         {
 635         case NOTE:
 636           /* Look for expected value notes.  */
 637           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
 638             {
 639               ev = NOTE_EXPECTED_VALUE (insn);
 640               ev_reg = XEXP (ev, 0);
 641               delete_insn (insn);
 642             }
 643           continue;
 644
 645         case CODE_LABEL:
 646           /* Never propagate across labels.  */
 647           ev = NULL_RTX;
 648           continue;
 649
 650         case JUMP_INSN:
 651           /* Look for simple conditional branches.  If we haven't got an
 652              expected value yet, no point going further.  */
 653           if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX
 654               || ! any_condjump_p (insn))
 655             continue;
 656           break;
 657
 658         default:
 659           /* Look for insns that clobber the EV register.  */
 660           if (ev && reg_set_p (ev_reg, insn))
 661             ev = NULL_RTX;
 662           continue;
 663         }
 664
 665       /* Collect the branch condition, hopefully relative to EV_REG.  */
 666       /* ???  At present we'll miss things like
 667                 (expected_value (eq r70 0))
 668                 (set r71 -1)
 669                 (set r80 (lt r70 r71))
 670                 (set pc (if_then_else (ne r80 0) ...))
 671          as canonicalize_condition will render this to us as
 672                 (lt r70, r71)
 673          Could use cselib to try and reduce this further.  */
 674       cond = XEXP (SET_SRC (pc_set (insn)), 0);
 675       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
 676       if (! cond || XEXP (cond, 0) != ev_reg
 677           || GET_CODE (XEXP (cond, 1)) != CONST_INT)
 678         continue;
 679
 680       /* Substitute and simplify.  Given that the expression we're
 681          building involves two constants, we should wind up with either
 682          true or false.  */
 683       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 684                              XEXP (ev, 1), XEXP (cond, 1));
 685       cond = simplify_rtx (cond);
 686
 687       /* Turn the condition into a scaled branch probability.  */
 688       if (cond != const_true_rtx && cond != const0_rtx)
 689         abort ();
 690       predict_insn_def (insn, PRED_BUILTIN_EXPECT,
 691                         cond == const_true_rtx ? TAKEN : NOT_TAKEN);
 692     }
 693 }
 694 \f
 695 /* Check whether this is the last basic block of function.  Commonly tehre
 696    is one extra common cleanup block.  */
 697 static bool
 698 last_basic_block_p (bb)
 699      basic_block bb;
 700 {
 701   if (bb == EXIT_BLOCK_PTR)
 702     return false;
 703
 704   return (bb->next_bb == EXIT_BLOCK_PTR
 705           || (bb->next_bb->next_bb == EXIT_BLOCK_PTR
 706               && bb->succ && !bb->succ->succ_next
 707               && bb->succ->dest->next_bb == EXIT_BLOCK_PTR));
 708 }
 709
 710 /* Sets branch probabilities according to PREDiction and FLAGS. HEADS[bb->index]
 711    should be index of basic block in that we need to alter branch predictions
 712    (i.e. the first of our dominators such that we do not post-dominate it)
 713    (but we fill this information on demand, so -1 may be there in case this
 714    was not needed yet).  */
 715
 716 static void
 717 process_note_prediction (bb, heads, dominators, post_dominators, pred, flags)
 718      basic_block bb;
 719      int *heads;
 720      dominance_info dominators;
 721      dominance_info post_dominators;
 722      int pred;
 723      int flags;
 724 {
 725   edge e;
 726   int y;
 727   bool taken;
 728
 729   taken = flags & IS_TAKEN;
 730
 731   if (heads[bb->index] < 0)
 732     {
 733       /* This is first time we need this field in heads array; so
 734          find first dominator that we do not post-dominate (we are
 735          using already known members of heads array).  */
 736       basic_block ai = bb;
 737       basic_block next_ai = get_immediate_dominator (dominators, bb);
 738       int head;
 739
 740       while (heads[next_ai->index] < 0)
 741         {
 742           if (!dominated_by_p (post_dominators, next_ai, bb))
 743             break;
 744           heads[next_ai->index] = ai->index;
 745           ai = next_ai;
 746           next_ai = get_immediate_dominator (dominators, next_ai);
 747         }
 748       if (!dominated_by_p (post_dominators, next_ai, bb))
 749         head = next_ai->index;
 750       else
 751         head = heads[next_ai->index];
 752       while (next_ai != bb)
 753         {
 754           next_ai = ai;
 755           if (heads[ai->index] == ENTRY_BLOCK)
 756             ai = ENTRY_BLOCK_PTR;
 757           else
 758             ai = BASIC_BLOCK (heads[ai->index]);
 759           heads[next_ai->index] = head;
 760         }
 761     }
 762   y = heads[bb->index];
 763
 764   /* Now find the edge that leads to our branch and aply the prediction.  */
 765
 766   if (y == last_basic_block)
 767     return;
 768   for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
 769     if (e->dest->index >= 0
 770         && dominated_by_p (post_dominators, e->dest, bb))
 771       predict_edge_def (e, pred, taken);
 772 }
 773
 774 /* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them
 775    into branch probabilities.  For description of heads array, see
 776    process_note_prediction.  */
 777
 778 static void
 779 process_note_predictions (bb, heads, dominators, post_dominators)
 780      basic_block bb;
 781      int *heads;
 782      dominance_info dominators;
 783      dominance_info post_dominators;
 784 {
 785   rtx insn;
 786   edge e;
 787
 788   /* Additionaly, we check here for blocks with no successors.  */
 789   int contained_noreturn_call = 0;
 790   int was_bb_head = 0;
 791   int noreturn_block = 1;
 792
 793   for (insn = bb->end; insn;
 794        was_bb_head |= (insn == bb->head), insn = PREV_INSN (insn))
 795     {
 796       if (GET_CODE (insn) != NOTE)
 797         {
 798           if (was_bb_head)
 799             break;
 800           else
 801             {
 802               /* Noreturn calls cause program to exit, therefore they are
 803                  always predicted as not taken.  */
 804               if (GET_CODE (insn) == CALL_INSN
 805                   && find_reg_note (insn, REG_NORETURN, NULL))
 806                 contained_noreturn_call = 1;
 807               continue;
 808             }
 809         }
 810       if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION)
 811         {
 812           int alg = (int) NOTE_PREDICTION_ALG (insn);
 813           /* Process single prediction note.  */
 814           process_note_prediction (bb,
 815                                    heads,
 816                                    dominators,
 817                                    post_dominators,
 818                                    alg, (int) NOTE_PREDICTION_FLAGS (insn));
 819           delete_insn (insn);
 820         }
 821     }
 822   for (e = bb->succ; e; e = e->succ_next)
 823     if (!(e->flags & EDGE_FAKE))
 824       noreturn_block = 0;
 825   if (contained_noreturn_call)
 826     {
 827       /* This block ended from other reasons than because of return.
 828          If it is because of noreturn call, this should certainly not
 829          be taken.  Otherwise it is probably some error recovery.  */
 830       process_note_prediction (bb,
 831                                heads,
 832                                dominators,
 833                                post_dominators, PRED_NORETURN, NOT_TAKEN);
 834     }
 835 }
 836
 837 /* Gathers NOTE_INSN_PREDICTIONs and turns them into
 838    branch probabilities.  */
 839
 840 void
 841 note_prediction_to_br_prob ()
 842 {
 843   basic_block bb;
 844   dominance_info post_dominators, dominators;
 845   int *heads;
 846
 847   /* To enable handling of noreturn blocks.  */
 848   add_noreturn_fake_exit_edges ();
 849   connect_infinite_loops_to_exit ();
 850
 851   post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
 852   dominators = calculate_dominance_info (CDI_DOMINATORS);
 853
 854   heads = xmalloc (sizeof (int) * last_basic_block);
 855   memset (heads, -1, sizeof (int) * last_basic_block);
 856   heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
 857
 858   /* Process all prediction notes.  */
 859
 860   FOR_EACH_BB (bb)
 861     process_note_predictions (bb, heads, dominators, post_dominators);
 862
 863   free_dominance_info (post_dominators);
 864   free_dominance_info (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 LOOP.  */
 904
 905 static void
 906 propagate_freq (loop)
 907      struct loop *loop;
 908 {
 909   basic_block head = loop->header;
 910   basic_block bb;
 911   basic_block last;
 912   edge e;
 913   basic_block nextbb;
 914
 915   /* For each basic block we need to visit count number of his predecessors
 916      we need to visit first.  */
 917   FOR_EACH_BB (bb)
 918     {
 919       if (BLOCK_INFO (bb)->tovisit)
 920         {
 921           int count = 0;
 922
 923           for (e = bb->pred; e; e = e->pred_next)
 924             if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
 925               count++;
 926             else if (BLOCK_INFO (e->src)->tovisit
 927                      && rtl_dump_file && !EDGE_INFO (e)->back_edge)
 928               fprintf (rtl_dump_file,
 929                        "Irreducible region hit, ignoring edge to %i->%i\n",
 930                        e->src->index, bb->index);
 931           BLOCK_INFO (bb)->npredecessors = count;
 932         }
 933     }
 934
 935   memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
 936   last = head;
 937   for (bb = head; 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 *loop;
1037
1038   for (loop = first_loop; loop; loop = loop->next)
1039     {
1040       edge e;
1041       basic_block *bbs;
1042       int i;
1043
1044       estimate_loops_at_level (loop->inner);
1045
1046       if (loop->latch->succ)  /* Do not do this for dummy function loop.  */
1047         {
1048           /* Find current loop back edge and mark it.  */
1049           e = loop_latch_edge (loop);
1050           EDGE_INFO (e)->back_edge = 1;
1051        }
1052
1053       bbs = get_loop_body (loop);
1054       for (i = 0; i < loop->num_nodes; i++)
1055         BLOCK_INFO (bbs[i])->tovisit = 1;
1056       free (bbs);
1057       propagate_freq (loop);
1058     }
1059 }
1060
1061 /* Convert counts measured by profile driven feedback to frequencies.  */
1062
1063 static void
1064 counts_to_freqs ()
1065 {
1066   HOST_WIDEST_INT count_max = 1;
1067   basic_block bb;
1068
1069   FOR_EACH_BB (bb)
1070     count_max = MAX (bb->count, count_max);
1071
1072   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1073     bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1074 }
1075
1076 /* Return true if function is likely to be expensive, so there is no point to
1077    optimize performance of prologue, epilogue or do inlining at the expense
1078    of code size growth.  THRESHOLD is the limit of number of isntructions
1079    function can execute at average to be still considered not expensive.  */
1080
1081 bool
1082 expensive_function_p (threshold)
1083         int threshold;
1084 {
1085   unsigned int sum = 0;
1086   basic_block bb;
1087   unsigned int limit;
1088
1089   /* We can not compute accurately for large thresholds due to scaled
1090      frequencies.  */
1091   if (threshold > BB_FREQ_MAX)
1092     abort ();
1093
1094   /* Frequencies are out of range.  This either means that function contains
1095      internal loop executing more than BB_FREQ_MAX times or profile feedback
1096      is available and function has not been executed at all.  */
1097   if (ENTRY_BLOCK_PTR->frequency == 0)
1098     return true;
1099
1100   /* Maximally BB_FREQ_MAX^2 so overflow won't happen.  */
1101   limit = ENTRY_BLOCK_PTR->frequency * threshold;
1102   FOR_EACH_BB (bb)
1103     {
1104       rtx insn;
1105
1106       for (insn = bb->head; insn != NEXT_INSN (bb->end);
1107            insn = NEXT_INSN (insn))
1108         if (active_insn_p (insn))
1109           {
1110             sum += bb->frequency;
1111             if (sum > limit)
1112               return true;
1113         }
1114     }
1115
1116   return false;
1117 }
1118
1119 /* Estimate basic blocks frequency by given branch probabilities.  */
1120
1121 static void
1122 estimate_bb_frequencies (loops)
1123      struct loops *loops;
1124 {
1125   basic_block bb;
1126   REAL_VALUE_TYPE freq_max;
1127   enum machine_mode double_mode = TYPE_MODE (double_type_node);
1128
1129   if (flag_branch_probabilities)
1130     counts_to_freqs ();
1131   else
1132     {
1133       REAL_VALUE_FROM_INT (real_zero, 0, 0, double_mode);
1134       REAL_VALUE_FROM_INT (real_one, 1, 0, double_mode);
1135       REAL_VALUE_FROM_INT (real_br_prob_base, REG_BR_PROB_BASE, 0, double_mode);
1136       REAL_VALUE_FROM_INT (real_bb_freq_max, BB_FREQ_MAX, 0, double_mode);
1137       REAL_VALUE_FROM_INT (real_one_half, 2, 0, double_mode);
1138
1139       REAL_ARITHMETIC (real_one_half, RDIV_EXPR, real_one, real_one_half);
1140
1141       REAL_ARITHMETIC (real_almost_one, RDIV_EXPR, real_one, real_br_prob_base);
1142       REAL_ARITHMETIC (real_almost_one, MINUS_EXPR, real_one, real_almost_one);
1143
1144       mark_dfs_back_edges ();
1145       /* Fill in the probability values in flowgraph based on the REG_BR_PROB
1146          notes.  */
1147       FOR_EACH_BB (bb)
1148         {
1149           rtx last_insn = bb->end;
1150
1151           if (GET_CODE (last_insn) != JUMP_INSN || !any_condjump_p (last_insn)
1152               /* Avoid handling of conditional jumps jumping to fallthru edge.  */
1153               || bb->succ->succ_next == NULL)
1154             {
1155               /* We can predict only conditional jumps at the moment.
1156                  Expect each edge to be equally probable.
1157                  ?? In the future we want to make abnormal edges improbable.  */
1158               int nedges = 0;
1159               edge e;
1160
1161               for (e = bb->succ; e; e = e->succ_next)
1162                 {
1163                   nedges++;
1164                   if (e->probability != 0)
1165                     break;
1166                 }
1167               if (!e)
1168                 for (e = bb->succ; e; e = e->succ_next)
1169                   e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
1170             }
1171         }
1172
1173       ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
1174
1175       /* Set up block info for each basic block.  */
1176       alloc_aux_for_blocks (sizeof (struct block_info_def));
1177       alloc_aux_for_edges (sizeof (struct edge_info_def));
1178       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1179         {
1180           edge e;
1181
1182           BLOCK_INFO (bb)->tovisit = 0;
1183           for (e = bb->succ; e; e = e->succ_next)
1184             {
1185               REAL_VALUE_FROM_INT (EDGE_INFO (e)->back_edge_prob,
1186                                    e->probability, 0, double_mode);
1187               REAL_ARITHMETIC (EDGE_INFO (e)->back_edge_prob,
1188                                RDIV_EXPR, EDGE_INFO (e)->back_edge_prob,
1189                                real_br_prob_base);
1190             }
1191         }
1192
1193       /* First compute probabilities locally for each loop from innermost
1194          to outermost to examine probabilities for back edges.  */
1195       estimate_loops_at_level (loops->tree_root);
1196
1197       memcpy (&freq_max, &real_zero, sizeof (real_zero));
1198       FOR_EACH_BB (bb)
1199         if (REAL_VALUES_LESS
1200             (freq_max, BLOCK_INFO (bb)->frequency))
1201           memcpy (&freq_max, &BLOCK_INFO (bb)->frequency,
1202                   sizeof (freq_max));
1203
1204       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1205         {
1206           REAL_VALUE_TYPE tmp;
1207
1208           REAL_ARITHMETIC (tmp, MULT_EXPR, BLOCK_INFO (bb)->frequency,
1209                            real_bb_freq_max);
1210           REAL_ARITHMETIC (tmp, RDIV_EXPR, tmp, freq_max);
1211           REAL_ARITHMETIC (tmp, PLUS_EXPR, tmp, real_one_half);
1212           bb->frequency = REAL_VALUE_UNSIGNED_FIX (tmp);
1213         }
1214
1215       free_aux_for_blocks ();
1216       free_aux_for_edges ();
1217     }
1218   compute_function_frequency ();
1219   if (flag_reorder_functions)
1220     choose_function_section ();
1221 }
1222
1223 /* Decide whether function is hot, cold or unlikely executed.  */
1224 static void
1225 compute_function_frequency ()
1226 {
1227   basic_block bb;
1228
1229   if (!profile_info.count_profiles_merged
1230       || !flag_branch_probabilities)
1231     return;
1232   cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1233   FOR_EACH_BB (bb)
1234     {
1235       if (maybe_hot_bb_p (bb))
1236         {
1237           cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
1238           return;
1239         }
1240       if (!probably_never_executed_bb_p (bb))
1241         cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
1242     }
1243 }
1244
1245 /* Choose appropriate section for the function.  */
1246 static void
1247 choose_function_section ()
1248 {
1249   if (DECL_SECTION_NAME (current_function_decl)
1250       || !targetm.have_named_sections)
1251     return;
1252   if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
1253     DECL_SECTION_NAME (current_function_decl) =
1254       build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
1255   if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
1256     DECL_SECTION_NAME (current_function_decl) =
1257       build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
1258                     UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
1259 }