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