gcc/predict.c

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