gcc/predict.c

   1 /* Branch prediction routines for the GNU compiler.
   2    Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 /* References:
  22
  23    [1] "Branch Prediction for Free"
  24        Ball and Larus; PLDI '93.
  25    [2] "Static Branch Frequency and Program Profile Analysis"
  26        Wu and Larus; MICRO-27.
  27    [3] "Corpus-based Static Branch Prediction"
  28        Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.  */
  29
  30
  31 #include "config.h"
  32 #include "system.h"
  33 #include "tree.h"
  34 #include "rtl.h"
  35 #include "tm_p.h"
  36 #include "hard-reg-set.h"
  37 #include "basic-block.h"
  38 #include "insn-config.h"
  39 #include "regs.h"
  40 #include "flags.h"
  41 #include "output.h"
  42 #include "function.h"
  43 #include "except.h"
  44 #include "toplev.h"
  45 #include "recog.h"
  46 #include "expr.h"
  47 #include "predict.h"
  48 #include "profile.h"
  49 #include "real.h"
  50 #include "params.h"
  51 #include "target.h"
  52
  53 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 0.5,
  54                    REAL_BB_FREQ_MAX.  */
  55 static REAL_VALUE_TYPE real_zero, real_one, real_almost_one, real_br_prob_base,
  56                        real_one_half, real_bb_freq_max;
  57
  58 /* Random guesstimation given names.  */
  59 #define PROB_NEVER              (0)
  60 #define PROB_VERY_UNLIKELY      (REG_BR_PROB_BASE / 10 - 1)
  61 #define PROB_UNLIKELY           (REG_BR_PROB_BASE * 4 / 10 - 1)
  62 #define PROB_EVEN               (REG_BR_PROB_BASE / 2)
  63 #define PROB_LIKELY             (REG_BR_PROB_BASE - PROB_UNLIKELY)
  64 #define PROB_VERY_LIKELY        (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
  65 #define PROB_ALWAYS             (REG_BR_PROB_BASE)
  66
  67 static bool predicted_by_p               PARAMS ((basic_block,
  68                                                   enum br_predictor));
  69 static void combine_predictions_for_insn PARAMS ((rtx, basic_block));
  70 static void dump_prediction              PARAMS ((enum br_predictor, int,
  71                                                   basic_block, int));
  72 static void estimate_loops_at_level      PARAMS ((struct loop *loop));
  73 static void propagate_freq               PARAMS ((struct loop *));
  74 static void estimate_bb_frequencies      PARAMS ((struct loops *));
  75 static void counts_to_freqs              PARAMS ((void));
  76 static void process_note_predictions     PARAMS ((basic_block, int *, int *,
  77                                                   sbitmap *));
  78 static void process_note_prediction      PARAMS ((basic_block, int *, int *,
  79                                                   sbitmap *, int, int));
  80 static bool last_basic_block_p           PARAMS ((basic_block));
  81 static void compute_function_frequency   PARAMS ((void));
  82 static void choose_function_section      PARAMS ((void));
  83
  84 /* Information we hold about each branch predictor.
  85    Filled using information from predict.def.  */
  86
  87 struct predictor_info
  88 {
  89   const char *const name;       /* Name used in the debugging dumps.  */
  90   const int hitrate;            /* Expected hitrate used by
  91                                    predict_insn_def call.  */
  92   const int flags;
  93 };
  94
  95 /* Use given predictor without Dempster-Shaffer theory if it matches
  96    using first_match heuristics.  */
  97 #define PRED_FLAG_FIRST_MATCH 1
  98
  99 /* Recompute hitrate in percent to our representation.  */
 100
 101 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
 102
 103 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
 104 static const struct predictor_info predictor_info[]= {
 105 #include "predict.def"
 106
 107   /* Upper bound on predictors.  */
 108   {NULL, 0, 0}
 109 };
 110 #undef DEF_PREDICTOR
 111
 112 /* Return true in case BB can be CPU intensive and should be optimized
 113    for maximal perofmrance.  */
 114
 115 bool
 116 maybe_hot_bb_p (bb)
 117      basic_block bb;
 118 {
 119   if (profile_info.count_profiles_merged
 120       && flag_branch_probabilities
 121       && (bb->count
 122           < profile_info.max_counter_in_program
 123           / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
 124     return false;
 125   if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
 126     return false;
 127   return true;
 128 }
 129
 130 /* Return true in case BB is cold and should be optimized for size.  */
 131
 132 bool
 133 probably_cold_bb_p (bb)
 134      basic_block bb;
 135 {
 136   if (profile_info.count_profiles_merged
 137       && flag_branch_probabilities
 138       && (bb->count
 139           < profile_info.max_counter_in_program
 140           / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
 141     return true;
 142   if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
 143     return true;
 144   return false;
 145 }
 146
 147 /* Return true in case BB is probably never executed.  */
 148 bool
 149 probably_never_executed_bb_p (bb)
 150         basic_block bb;
 151 {
 152   if (profile_info.count_profiles_merged
 153       && flag_branch_probabilities)
 154     return ((bb->count + profile_info.count_profiles_merged / 2)
 155             / profile_info.count_profiles_merged) == 0;
 156   return false;
 157 }
 158
 159 /* Return true if the one of outgoing edges is already predicted by
 160    PREDICTOR.  */
 161
 162 static bool
 163 predicted_by_p (bb, predictor)
 164      basic_block bb;
 165      enum br_predictor predictor;
 166 {
 167   rtx note;
 168   if (!INSN_P (bb->end))
 169     return false;
 170   for (note = REG_NOTES (bb->end); note; note = XEXP (note, 1))
 171     if (REG_NOTE_KIND (note) == REG_BR_PRED
 172         && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
 173       return true;
 174   return false;
 175 }
 176
 177 void
 178 predict_insn (insn, predictor, probability)
 179      rtx insn;
 180      int probability;
 181      enum br_predictor predictor;
 182 {
 183   if (!any_condjump_p (insn))
 184     abort ();
 185
 186   REG_NOTES (insn)
 187     = gen_rtx_EXPR_LIST (REG_BR_PRED,
 188                          gen_rtx_CONCAT (VOIDmode,
 189                                          GEN_INT ((int) predictor),
 190                                          GEN_INT ((int) probability)),
 191                          REG_NOTES (insn));
 192 }
 193
 194 /* Predict insn by given predictor.  */
 195
 196 void
 197 predict_insn_def (insn, predictor, taken)
 198      rtx insn;
 199      enum br_predictor predictor;
 200      enum prediction taken;
 201 {
 202    int probability = predictor_info[(int) predictor].hitrate;
 203
 204    if (taken != TAKEN)
 205      probability = REG_BR_PROB_BASE - probability;
 206
 207    predict_insn (insn, predictor, probability);
 208 }
 209
 210 /* Predict edge E with given probability if possible.  */
 211
 212 void
 213 predict_edge (e, predictor, probability)
 214      edge e;
 215      int probability;
 216      enum br_predictor predictor;
 217 {
 218   rtx last_insn;
 219   last_insn = e->src->end;
 220
 221   /* We can store the branch prediction information only about
 222      conditional jumps.  */
 223   if (!any_condjump_p (last_insn))
 224     return;
 225
 226   /* We always store probability of branching.  */
 227   if (e->flags & EDGE_FALLTHRU)
 228     probability = REG_BR_PROB_BASE - probability;
 229
 230   predict_insn (last_insn, predictor, probability);
 231 }
 232
 233 /* Predict edge E by given predictor if possible.  */
 234
 235 void
 236 predict_edge_def (e, predictor, taken)
 237      edge e;
 238      enum br_predictor predictor;
 239      enum prediction taken;
 240 {
 241    int probability = predictor_info[(int) predictor].hitrate;
 242
 243    if (taken != TAKEN)
 244      probability = REG_BR_PROB_BASE - probability;
 245
 246    predict_edge (e, predictor, probability);
 247 }
 248
 249 /* Invert all branch predictions or probability notes in the INSN.  This needs
 250    to be done each time we invert the condition used by the jump.  */
 251
 252 void
 253 invert_br_probabilities (insn)
 254      rtx insn;
 255 {
 256   rtx note;
 257
 258   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 259     if (REG_NOTE_KIND (note) == REG_BR_PROB)
 260       XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
 261     else if (REG_NOTE_KIND (note) == REG_BR_PRED)
 262       XEXP (XEXP (note, 0), 1)
 263         = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
 264 }
 265
 266 /* Dump information about the branch prediction to the output file.  */
 267
 268 static void
 269 dump_prediction (predictor, probability, bb, used)
 270      enum br_predictor predictor;
 271      int probability;
 272      basic_block bb;
 273      int used;
 274 {
 275   edge e = bb->succ;
 276
 277   if (!rtl_dump_file)
 278     return;
 279
 280   while (e && (e->flags & EDGE_FALLTHRU))
 281     e = e->succ_next;
 282
 283   fprintf (rtl_dump_file, "  %s heuristics%s: %.1f%%",
 284            predictor_info[predictor].name,
 285            used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
 286
 287   if (bb->count)
 288     {
 289       fprintf (rtl_dump_file, "  exec ");
 290       fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 291       if (e)
 292         {
 293           fprintf (rtl_dump_file, " hit ");
 294           fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 295           fprintf (rtl_dump_file, " (%.1f%%)", e->count * 100.0 / bb->count);
 296         }
 297     }
 298
 299   fprintf (rtl_dump_file, "\n");
 300 }
 301
 302 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
 303    note if not already present.  Remove now useless REG_BR_PRED notes.  */
 304
 305 static void
 306 combine_predictions_for_insn (insn, bb)
 307      rtx insn;
 308      basic_block bb;
 309 {
 310   rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
 311   rtx *pnote = &REG_NOTES (insn);
 312   rtx note;
 313   int best_probability = PROB_EVEN;
 314   int best_predictor = END_PREDICTORS;
 315   int combined_probability = REG_BR_PROB_BASE / 2;
 316   int d;
 317   bool first_match = false;
 318   bool found = false;
 319
 320   if (rtl_dump_file)
 321     fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
 322              bb->index);
 323
 324   /* We implement "first match" heuristics and use probability guessed
 325      by predictor with smallest index.  In the future we will use better
 326      probability combination techniques.  */
 327   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 328     if (REG_NOTE_KIND (note) == REG_BR_PRED)
 329       {
 330         int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
 331         int probability = INTVAL (XEXP (XEXP (note, 0), 1));
 332
 333         found = true;
 334         if (best_predictor > predictor)
 335           best_probability = probability, best_predictor = predictor;
 336
 337         d = (combined_probability * probability
 338              + (REG_BR_PROB_BASE - combined_probability)
 339              * (REG_BR_PROB_BASE - probability));
 340
 341         /* Use FP math to avoid overflows of 32bit integers.  */
 342         if (d == 0)
 343           /* If one probability is 0% and one 100%, avoid division by zero.  */
 344           combined_probability = REG_BR_PROB_BASE / 2;
 345         else
 346           combined_probability = (((double) combined_probability) * probability
 347                                   * REG_BR_PROB_BASE / d + 0.5);
 348       }
 349
 350   /* Decide which heuristic to use.  In case we didn't match anything,
 351      use no_prediction heuristic, in case we did match, use either
 352      first match or Dempster-Shaffer theory depending on the flags.  */
 353
 354   if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
 355     first_match = true;
 356
 357   if (!found)
 358     dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true);
 359   else
 360     {
 361       dump_prediction (PRED_DS_THEORY, combined_probability, bb, !first_match);
 362       dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match);
 363     }
 364
 365   if (first_match)
 366     combined_probability = best_probability;
 367   dump_prediction (PRED_COMBINED, combined_probability, bb, true);
 368
 369   while (*pnote)
 370     {
 371       if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
 372         {
 373           int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
 374           int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
 375
 376           dump_prediction (predictor, probability, bb,
 377                            !first_match || best_predictor == predictor);
 378           *pnote = XEXP (*pnote, 1);
 379         }
 380       else
 381         pnote = &XEXP (*pnote, 1);
 382     }
 383
 384   if (!prob_note)
 385     {
 386       REG_NOTES (insn)
 387         = gen_rtx_EXPR_LIST (REG_BR_PROB,
 388                              GEN_INT (combined_probability), REG_NOTES (insn));
 389
 390       /* Save the prediction into CFG in case we are seeing non-degenerated
 391          conditional jump.  */
 392       if (bb->succ->succ_next)
 393         {
 394           BRANCH_EDGE (bb)->probability = combined_probability;
 395           FALLTHRU_EDGE (bb)->probability
 396             = REG_BR_PROB_BASE - combined_probability;
 397         }
 398     }
 399 }
 400
 401 /* Statically estimate the probability that a branch will be taken.
 402    ??? In the next revision there will be a number of other predictors added
 403    from the above references. Further, each heuristic will be factored out
 404    into its own function for clarity (and to facilitate the combination of
 405    predictions).  */
 406
 407 void
 408 estimate_probability (loops_info)
 409      struct loops *loops_info;
 410 {
 411   sbitmap *dominators, *post_dominators;
 412   basic_block bb;
 413   int i;
 414
 415   dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
 416   post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
 417   calculate_dominance_info (NULL, dominators, CDI_DOMINATORS);
 418   calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
 419
 420   /* Try to predict out blocks in a loop that are not part of a
 421      natural loop.  */
 422   for (i = 1; i < loops_info->num; i++)
 423     {
 424       basic_block bb, *bbs;
 425       int j;
 426       int exits;
 427       struct loop *loop = loops_info->parray[i];
 428
 429       flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES);
 430       exits = loop->num_exits;
 431
 432       bbs = get_loop_body (loop);
 433       for (j = 0; j < loop->num_nodes; j++)
 434         {
 435           int header_found = 0;
 436           edge e;
 437
 438           bb = bbs[j];
 439
 440           /* Bypass loop heuristics on continue statement.  These
 441              statements construct loops via "non-loop" constructs
 442              in the source language and are better to be handled
 443              separately.  */
 444           if (predicted_by_p (bb, PRED_CONTINUE))
 445             continue;
 446
 447           /* Loop branch heuristics - predict an edge back to a
 448              loop's head as taken.  */
 449           for (e = bb->succ; e; e = e->succ_next)
 450             if (e->dest == loop->header
 451                 && e->src == loop->latch)
 452               {
 453                 header_found = 1;
 454                 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
 455               }
 456
 457           /* Loop exit heuristics - predict an edge exiting the loop if the
 458              conditinal has no loop header successors as not taken.  */
 459           if (!header_found)
 460             for (e = bb->succ; e; e = e->succ_next)
 461               if (e->dest->index < 0
 462                   || !flow_bb_inside_loop_p (loop, e->dest))
 463                 predict_edge
 464                   (e, PRED_LOOP_EXIT,
 465                    (REG_BR_PROB_BASE
 466                     - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
 467                    / exits);
 468         }
 469     }
 470
 471   /* Attempt to predict conditional jumps using a number of heuristics.  */
 472   FOR_EACH_BB (bb)
 473     {
 474       rtx last_insn = bb->end;
 475       rtx cond, earliest;
 476       edge e;
 477
 478       if (GET_CODE (last_insn) != JUMP_INSN || ! any_condjump_p (last_insn))
 479         continue;
 480
 481       for (e = bb->succ; e; e = e->succ_next)
 482         {
 483           /* Predict early returns to be probable, as we've already taken
 484              care for error returns and other are often used for fast paths
 485              trought function.  */
 486           if ((e->dest == EXIT_BLOCK_PTR
 487                || (e->dest->succ && !e->dest->succ->succ_next
 488                    && e->dest->succ->dest == EXIT_BLOCK_PTR))
 489                && !predicted_by_p (bb, PRED_NULL_RETURN)
 490                && !predicted_by_p (bb, PRED_CONST_RETURN)
 491                && !predicted_by_p (bb, PRED_NEGATIVE_RETURN)
 492                && !last_basic_block_p (e->dest))
 493             predict_edge_def (e, PRED_EARLY_RETURN, TAKEN);
 494
 495           /* Look for block we are guarding (ie we dominate it,
 496              but it doesn't postdominate us).  */
 497           if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
 498               && TEST_BIT (dominators[e->dest->index], e->src->index)
 499               && !TEST_BIT (post_dominators[e->src->index], e->dest->index))
 500             {
 501               rtx insn;
 502
 503               /* The call heuristic claims that a guarded function call
 504                  is improbable.  This is because such calls are often used
 505                  to signal exceptional situations such as printing error
 506                  messages.  */
 507               for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end);
 508                    insn = NEXT_INSN (insn))
 509                 if (GET_CODE (insn) == CALL_INSN
 510                     /* Constant and pure calls are hardly used to signalize
 511                        something exceptional.  */
 512                     && ! CONST_OR_PURE_CALL_P (insn))
 513                   {
 514                     predict_edge_def (e, PRED_CALL, NOT_TAKEN);
 515                     break;
 516                   }
 517             }
 518         }
 519
 520       cond = get_condition (last_insn, &earliest);
 521       if (! cond)
 522         continue;
 523
 524       /* Try "pointer heuristic."
 525          A comparison ptr == 0 is predicted as false.
 526          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 527       if (GET_RTX_CLASS (GET_CODE (cond)) == '<'
 528           && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
 529               || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
 530         {
 531           if (GET_CODE (cond) == EQ)
 532             predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
 533           else if (GET_CODE (cond) == NE)
 534             predict_insn_def (last_insn, PRED_POINTER, TAKEN);
 535         }
 536       else
 537
 538       /* Try "opcode heuristic."
 539          EQ tests are usually false and NE tests are usually true. Also,
 540          most quantities are positive, so we can make the appropriate guesses
 541          about signed comparisons against zero.  */
 542         switch (GET_CODE (cond))
 543           {
 544           case CONST_INT:
 545             /* Unconditional branch.  */
 546             predict_insn_def (last_insn, PRED_UNCONDITIONAL,
 547                               cond == const0_rtx ? NOT_TAKEN : TAKEN);
 548             break;
 549
 550           case EQ:
 551           case UNEQ:
 552             /* Floating point comparisons appears to behave in a very
 553                inpredictable way because of special role of = tests in
 554                FP code.  */
 555             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 556               ;
 557             /* Comparisons with 0 are often used for booleans and there is
 558                nothing usefull to predict about them.  */
 559             else if (XEXP (cond, 1) == const0_rtx
 560                      || XEXP (cond, 0) == const0_rtx)
 561               ;
 562             else
 563               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
 564             break;
 565
 566           case NE:
 567           case LTGT:
 568             /* Floating point comparisons appears to behave in a very
 569                inpredictable way because of special role of = tests in
 570                FP code.  */
 571             if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
 572               ;
 573             /* Comparisons with 0 are often used for booleans and there is
 574                nothing usefull to predict about them.  */
 575             else if (XEXP (cond, 1) == const0_rtx
 576                      || XEXP (cond, 0) == const0_rtx)
 577               ;
 578             else
 579               predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
 580             break;
 581
 582           case ORDERED:
 583             predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
 584             break;
 585
 586           case UNORDERED:
 587             predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
 588             break;
 589
 590           case LE:
 591           case LT:
 592             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 593                 || XEXP (cond, 1) == constm1_rtx)
 594               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
 595             break;
 596
 597           case GE:
 598           case GT:
 599             if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
 600                 || XEXP (cond, 1) == constm1_rtx)
 601               predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
 602             break;
 603
 604           default:
 605             break;
 606           }
 607     }
 608
 609   /* Attach the combined probability to each conditional jump.  */
 610   FOR_EACH_BB (bb)
 611     if (GET_CODE (bb->end) == JUMP_INSN
 612         && any_condjump_p (bb->end)
 613         && bb->succ->succ_next != NULL)
 614       combine_predictions_for_insn (bb->end, bb);
 615
 616   sbitmap_vector_free (post_dominators);
 617   sbitmap_vector_free (dominators);
 618
 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      int *dominators;
 721      sbitmap *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       int ai = bb->index;
 737       int next_ai = dominators[bb->index];
 738       int head;
 739
 740       while (heads[next_ai] < 0)
 741         {
 742           if (!TEST_BIT (post_dominators[next_ai], bb->index))
 743             break;
 744           heads[next_ai] = ai;
 745           ai = next_ai;
 746           next_ai = dominators[next_ai];
 747         }
 748       if (!TEST_BIT (post_dominators[next_ai], bb->index))
 749         head = next_ai;
 750       else
 751         head = heads[next_ai];
 752       while (next_ai != bb->index)
 753         {
 754           next_ai = ai;
 755           ai = heads[ai];
 756           heads[next_ai] = head;
 757         }
 758     }
 759   y = heads[bb->index];
 760
 761   /* Now find the edge that leads to our branch and aply the prediction.  */
 762
 763   if (y == last_basic_block)
 764     return;
 765   for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
 766     if (e->dest->index >= 0
 767         && TEST_BIT (post_dominators[e->dest->index], bb->index))
 768       predict_edge_def (e, pred, taken);
 769 }
 770
 771 /* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them
 772    into branch probabilities.  For description of heads array, see
 773    process_note_prediction.  */
 774
 775 static void
 776 process_note_predictions (bb, heads, dominators, post_dominators)
 777      basic_block bb;
 778      int *heads;
 779      int *dominators;
 780      sbitmap *post_dominators;
 781 {
 782   rtx insn;
 783   edge e;
 784
 785   /* Additionaly, we check here for blocks with no successors.  */
 786   int contained_noreturn_call = 0;
 787   int was_bb_head = 0;
 788   int noreturn_block = 1;
 789
 790   for (insn = bb->end; insn;
 791        was_bb_head |= (insn == bb->head), insn = PREV_INSN (insn))
 792     {
 793       if (GET_CODE (insn) != NOTE)
 794         {
 795           if (was_bb_head)
 796             break;
 797           else
 798             {
 799               /* Noreturn calls cause program to exit, therefore they are
 800                  always predicted as not taken.  */
 801               if (GET_CODE (insn) == CALL_INSN
 802                   && find_reg_note (insn, REG_NORETURN, NULL))
 803                 contained_noreturn_call = 1;
 804               continue;
 805             }
 806         }
 807       if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION)
 808         {
 809           int alg = (int) NOTE_PREDICTION_ALG (insn);
 810           /* Process single prediction note.  */
 811           process_note_prediction (bb,
 812                                    heads,
 813                                    dominators,
 814                                    post_dominators,
 815                                    alg, (int) NOTE_PREDICTION_FLAGS (insn));
 816           delete_insn (insn);
 817         }
 818     }
 819   for (e = bb->succ; e; e = e->succ_next)
 820     if (!(e->flags & EDGE_FAKE))
 821       noreturn_block = 0;
 822   if (contained_noreturn_call)
 823     {
 824       /* This block ended from other reasons than because of return.
 825          If it is because of noreturn call, this should certainly not
 826          be taken.  Otherwise it is probably some error recovery.  */
 827       process_note_prediction (bb,
 828                                heads,
 829                                dominators,
 830                                post_dominators, PRED_NORETURN, NOT_TAKEN);
 831     }
 832 }
 833
 834 /* Gathers NOTE_INSN_PREDICTIONs and turns them into
 835    branch probabilities.  */
 836
 837 void
 838 note_prediction_to_br_prob ()
 839 {
 840   basic_block bb;
 841   sbitmap *post_dominators;
 842   int *dominators, *heads;
 843
 844   /* To enable handling of noreturn blocks.  */
 845   add_noreturn_fake_exit_edges ();
 846   connect_infinite_loops_to_exit ();
 847
 848   dominators = xmalloc (sizeof (int) * last_basic_block);
 849   memset (dominators, -1, sizeof (int) * last_basic_block);
 850   post_dominators = sbitmap_vector_alloc (last_basic_block, last_basic_block);
 851   calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
 852   calculate_dominance_info (dominators, NULL, 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   sbitmap_vector_free (post_dominators);
 864   free (dominators);
 865   free (heads);
 866
 867   remove_fake_edges ();
 868 }
 869 \f
 870 /* This is used to carry information about basic blocks.  It is
 871    attached to the AUX field of the standard CFG block.  */
 872
 873 typedef struct block_info_def
 874 {
 875   /* Estimated frequency of execution of basic_block.  */
 876   REAL_VALUE_TYPE frequency;
 877
 878   /* To keep queue of basic blocks to process.  */
 879   basic_block next;
 880
 881   /* True if block needs to be visited in prop_freqency.  */
 882   int tovisit:1;
 883
 884   /* Number of predecessors we need to visit first.  */
 885   int npredecessors;
 886 } *block_info;
 887
 888 /* Similar information for edges.  */
 889 typedef struct edge_info_def
 890 {
 891   /* In case edge is an loopback edge, the probability edge will be reached
 892      in case header is.  Estimated number of iterations of the loop can be
 893      then computed as 1 / (1 - back_edge_prob).  */
 894   REAL_VALUE_TYPE back_edge_prob;
 895   /* True if the edge is an loopback edge in the natural loop.  */
 896   int back_edge:1;
 897 } *edge_info;
 898
 899 #define BLOCK_INFO(B)   ((block_info) (B)->aux)
 900 #define EDGE_INFO(E)    ((edge_info) (E)->aux)
 901
 902 /* Helper function for estimate_bb_frequencies.
 903    Propagate the frequencies for 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 }