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