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
  64 /* Information we hold about each branch predictor.
  65    Filled using information from predict.def.  */
  66 struct predictor_info
  67 {
  68   const char *name;     /* Name used in the debugging dumps.  */
  69   int hitrate;          /* Expected hitrate used by
  70                            predict_insn_def call.  */
  71 };
  72
  73 #define DEF_PREDICTOR(ENUM, NAME, HITRATE) {NAME, HITRATE},
  74 struct predictor_info predictor_info[] = {
  75 #include "predict.def"
  76
  77   /* Upper bound on non-language-specific builtins. */
  78   {NULL, 0}
  79 };
  80 #undef DEF_PREDICTOR
  81
  82 void
  83 predict_insn (insn, predictor, probability)
  84      rtx insn;
  85      int probability;
  86      enum br_predictor predictor;
  87 {
  88   if (!any_condjump_p (insn))
  89     abort ();
  90   REG_NOTES (insn)
  91     = gen_rtx_EXPR_LIST (REG_BR_PRED,
  92                          gen_rtx_CONCAT (VOIDmode,
  93                                          GEN_INT ((int) predictor),
  94                                          GEN_INT ((int) probability)),
  95                          REG_NOTES (insn));
  96 }
  97
  98 /* Predict insn by given predictor.  */
  99 void
 100 predict_insn_def (insn, predictor, taken)
 101      rtx insn;
 102      enum br_predictor predictor;
 103      enum prediction taken;
 104 {
 105    int probability = predictor_info[(int) predictor].hitrate;
 106    if (taken != TAKEN)
 107      probability = REG_BR_PROB_BASE - probability;
 108    predict_insn (insn, predictor, probability);
 109 }
 110
 111 /* Predict edge E with given probability if possible.  */
 112 void
 113 predict_edge (e, predictor, probability)
 114      edge e;
 115      int probability;
 116      enum br_predictor predictor;
 117 {
 118   rtx last_insn;
 119   last_insn = e->src->end;
 120
 121   /* We can store the branch prediction information only about
 122      conditional jumps.  */
 123   if (!any_condjump_p (last_insn))
 124     return;
 125
 126   /* We always store probability of branching.  */
 127   if (e->flags & EDGE_FALLTHRU)
 128     probability = REG_BR_PROB_BASE - probability;
 129
 130   predict_insn (last_insn, predictor, probability);
 131 }
 132
 133 /* Predict edge E by given predictor if possible.  */
 134 void
 135 predict_edge_def (e, predictor, taken)
 136      edge e;
 137      enum br_predictor predictor;
 138      enum prediction taken;
 139 {
 140    int probability = predictor_info[(int) predictor].hitrate;
 141
 142    if (taken != TAKEN)
 143      probability = REG_BR_PROB_BASE - probability;
 144    predict_edge (e, predictor, probability);
 145 }
 146
 147 /* Invert all branch predictions or probability notes in the INSN.  This needs
 148    to be done each time we invert the condition used by the jump.  */
 149 void
 150 invert_br_probabilities (insn)
 151      rtx insn;
 152 {
 153   rtx note = REG_NOTES (insn);
 154
 155   while (note)
 156     {
 157       if (REG_NOTE_KIND (note) == REG_BR_PROB)
 158         XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
 159       else if (REG_NOTE_KIND (note) == REG_BR_PRED)
 160         XEXP (XEXP (note, 0), 1)
 161           = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
 162       note = XEXP (note, 1);
 163     }
 164 }
 165
 166 /* Dump information about the branch prediction to the output file.  */
 167 static void
 168 dump_prediction (predictor, probability, bb)
 169      enum br_predictor predictor;
 170      int probability;
 171      basic_block bb;
 172 {
 173   edge e = bb->succ;
 174
 175   if (!rtl_dump_file)
 176     return;
 177
 178   while (e->flags & EDGE_FALLTHRU)
 179     e = e->succ_next;
 180
 181   fprintf (rtl_dump_file, "  %s heuristics: %.1f%%",
 182            predictor_info[predictor].name,
 183            probability * 100.0 / REG_BR_PROB_BASE);
 184
 185   if (bb->count)
 186     fprintf (rtl_dump_file, "  exec %i hit %i (%.1f%%)",
 187              bb->count, e->count, e->count * 100.0 / bb->count);
 188   fprintf (rtl_dump_file, "\n");
 189 }
 190
 191 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
 192    note if not already present.  Remove now useless REG_BR_PRED notes.  */
 193 static void
 194 combine_predictions_for_insn (insn, bb)
 195      rtx insn;
 196      basic_block bb;
 197 {
 198   rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0);
 199   rtx *pnote = &REG_NOTES (insn);
 200   int best_probability = PROB_EVEN;
 201   int best_predictor = END_PREDICTORS;
 202
 203   if (rtl_dump_file)
 204     fprintf (rtl_dump_file, "Predictions for insn %i\n", INSN_UID (insn));
 205
 206   /* We implement "first match" heuristics and use probability guessed
 207      by predictor with smallest index.  In future we will use better
 208      probability combination techniques.  */
 209   while (*pnote)
 210     {
 211       rtx *next_pnote = &XEXP (*pnote, 1);
 212       if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
 213         {
 214           int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
 215           int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
 216
 217           dump_prediction (predictor, probability, bb);
 218           if (best_predictor > predictor)
 219             best_probability = probability, best_predictor = predictor;
 220           *pnote = XEXP (*pnote, 1);
 221         }
 222       pnote = next_pnote;
 223     }
 224   dump_prediction (PRED_FIRST_MATCH, best_probability, bb);
 225   if (!prob_note)
 226     {
 227       REG_NOTES (insn)
 228         = gen_rtx_EXPR_LIST (REG_BR_PROB,
 229                              GEN_INT (best_probability), REG_NOTES (insn));
 230     }
 231 }
 232
 233 /* Statically estimate the probability that a branch will be taken.
 234    ??? In the next revision there will be a number of other predictors added
 235    from the above references. Further, each heuristic will be factored out
 236    into its own function for clarity (and to facilitate the combination of
 237    predictions).  */
 238
 239 void
 240 estimate_probability (loops_info)
 241      struct loops *loops_info;
 242 {
 243   sbitmap *dominators, *post_dominators;
 244   int i;
 245
 246   dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 247   post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 248   calculate_dominance_info (NULL, dominators, 0);
 249   calculate_dominance_info (NULL, post_dominators, 1);
 250
 251   /* Try to predict out blocks in a loop that are not part of a
 252      natural loop.  */
 253   for (i = 0; i < loops_info->num; i++)
 254     {
 255       int j;
 256
 257       for (j = loops_info->array[i].first->index;
 258            j <= loops_info->array[i].last->index;
 259            ++j)
 260         {
 261           if (TEST_BIT (loops_info->array[i].nodes, j))
 262             {
 263               int header_found = 0;
 264               edge e;
 265
 266               /* Loop branch heruistics - predict as taken an edge back to
 267                  a loop's head.  */
 268               for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
 269                 if (e->dest == loops_info->array[i].header)
 270                   {
 271                     header_found = 1;
 272                     predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
 273                   }
 274               /* Loop exit heruistics - predict as not taken an edge exiting
 275                  the loop if the conditinal has no loop header successors  */
 276               if (!header_found)
 277                 for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next)
 278                   if (e->dest->index <= 0
 279                       || !TEST_BIT (loops_info->array[i].nodes, e->dest->index))
 280                     predict_edge_def (e, PRED_LOOP_EXIT, NOT_TAKEN);
 281             }
 282         }
 283     }
 284
 285   /* Attempt to predict conditional jumps using a number of heuristics.
 286      For each conditional jump, we try each heuristic in a fixed order.
 287      If more than one heuristic applies to a particular branch, the first
 288      is used as the prediction for the branch.  */
 289   for (i = 0; i < n_basic_blocks - 1; i++)
 290     {
 291       basic_block bb = BASIC_BLOCK (i);
 292       rtx last_insn = bb->end;
 293       rtx cond, earliest;
 294       edge e;
 295
 296       /* If block has no sucessor, predict all possible paths to
 297          it as improbable, as the block contains a call to a noreturn
 298          function and thus can be executed only once.  */
 299       if (bb->succ == NULL)
 300         {
 301           int y;
 302           for (y = 0; y < n_basic_blocks; y++)
 303             if (!TEST_BIT (post_dominators[y], i))
 304               {
 305                 for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
 306                 if (e->dest->index >= 0
 307                     && TEST_BIT (post_dominators[e->dest->index], i))
 308                   predict_edge_def (e, PRED_NORETURN, NOT_TAKEN);
 309               }
 310         }
 311
 312       if (GET_CODE (last_insn) != JUMP_INSN
 313           || ! any_condjump_p (last_insn))
 314         continue;
 315
 316       if (find_reg_note (last_insn, REG_BR_PROB, 0))
 317         continue;
 318
 319       for (e = bb->succ; e; e = e->succ_next)
 320         {
 321           /* Predict edges to blocks that return immediately to be
 322              improbable.  These are usually used to signal error states.  */
 323           if (e->dest == EXIT_BLOCK_PTR
 324               || (e->dest->succ && !e->dest->succ->succ_next
 325                   && e->dest->succ->dest == EXIT_BLOCK_PTR))
 326             predict_edge_def (e, PRED_ERROR_RETURN, NOT_TAKEN);
 327
 328           /* Look for block we are guarding (ie we dominate it,
 329              but it doesn't postdominate us).  */
 330           if (e->dest != EXIT_BLOCK_PTR
 331               && e->dest != bb
 332               && TEST_BIT (dominators[e->dest->index], e->src->index)
 333               && !TEST_BIT (post_dominators[e->src->index], e->dest->index))
 334             {
 335               rtx insn;
 336               /* The call heuristic claims that a guarded function call
 337                  is improbable.  This is because such calls are often used
 338                  to signal exceptional situations such as printing error
 339                  messages.  */
 340               for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end);
 341                    insn = NEXT_INSN (insn))
 342                 if (GET_CODE (insn) == CALL_INSN
 343                     /* Constant and pure calls are hardly used to signalize
 344                        something exceptional.  */
 345                     && ! CONST_CALL_P (insn))
 346                   {
 347                     predict_edge_def (e, PRED_CALL, NOT_TAKEN);
 348                     break;
 349                   }
 350             }
 351         }
 352
 353       cond = get_condition (last_insn, &earliest);
 354       if (! cond)
 355         continue;
 356
 357       /* Try "pointer heuristic."
 358          A comparison ptr == 0 is predicted as false.
 359          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 360       switch (GET_CODE (cond))
 361         {
 362         case EQ:
 363           if (GET_CODE (XEXP (cond, 0)) == REG
 364               && REG_POINTER (XEXP (cond, 0))
 365               && (XEXP (cond, 1) == const0_rtx
 366                   || (GET_CODE (XEXP (cond, 1)) == REG
 367                       && REG_POINTER (XEXP (cond, 1)))))
 368
 369             predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
 370           break;
 371         case NE:
 372           if (GET_CODE (XEXP (cond, 0)) == REG
 373               && REG_POINTER (XEXP (cond, 0))
 374               && (XEXP (cond, 1) == const0_rtx
 375                   || (GET_CODE (XEXP (cond, 1)) == REG
 376                       && REG_POINTER (XEXP (cond, 1)))))
 377             predict_insn_def (last_insn, PRED_POINTER, TAKEN);
 378           break;
 379
 380         default:
 381           break;
 382         }
 383
 384       /* Try "opcode heuristic."
 385          EQ tests are usually false and NE tests are usually true. Also,
 386          most quantities are positive, so we can make the appropriate guesses
 387          about signed comparisons against zero.  */
 388       switch (GET_CODE (cond))
 389         {
 390         case CONST_INT:
 391           /* Unconditional branch.  */
 392           predict_insn_def (last_insn, PRED_UNCONDITIONAL,
 393                             cond == const0_rtx ? NOT_TAKEN : TAKEN);
 394           break;
 395
 396         case EQ:
 397         case UNEQ:
 398           predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
 399           break;
 400         case NE:
 401         case LTGT:
 402           predict_insn_def (last_insn, PRED_OPCODE, TAKEN);
 403           break;
 404         case ORDERED:
 405           predict_insn_def (last_insn, PRED_OPCODE, TAKEN);
 406           break;
 407         case UNORDERED:
 408           predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
 409           break;
 410         case LE:
 411         case LT:
 412           if (XEXP (cond, 1) == const0_rtx
 413               || (GET_CODE (XEXP (cond, 1)) == CONST_INT
 414                   && INTVAL (XEXP (cond, 1)) == -1))
 415             predict_insn_def (last_insn, PRED_OPCODE, NOT_TAKEN);
 416           break;
 417         case GE:
 418         case GT:
 419           if (XEXP (cond, 1) == const0_rtx
 420               || (GET_CODE (XEXP (cond, 1)) == CONST_INT
 421                   && INTVAL (XEXP (cond, 1)) == -1))
 422             predict_insn_def (last_insn, PRED_OPCODE, TAKEN);
 423           break;
 424
 425         default:
 426           break;
 427         }
 428     }
 429
 430   /* Attach the combined probability to each conditional jump.  */
 431   for (i = 0; i < n_basic_blocks - 1; i++)
 432     {
 433       rtx last_insn = BLOCK_END (i);
 434
 435       if (GET_CODE (last_insn) != JUMP_INSN
 436           || ! any_condjump_p (last_insn))
 437         continue;
 438       combine_predictions_for_insn (last_insn, BASIC_BLOCK (i));
 439     }
 440   sbitmap_vector_free (post_dominators);
 441   sbitmap_vector_free (dominators);
 442 }
 443 \f
 444 /* __builtin_expect dropped tokens into the insn stream describing
 445    expected values of registers.  Generate branch probabilities
 446    based off these values.  */
 447
 448 void
 449 expected_value_to_br_prob ()
 450 {
 451   rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
 452
 453   for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
 454     {
 455       switch (GET_CODE (insn))
 456         {
 457         case NOTE:
 458           /* Look for expected value notes.  */
 459           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
 460             {
 461               ev = NOTE_EXPECTED_VALUE (insn);
 462               ev_reg = XEXP (ev, 0);
 463             }
 464           continue;
 465
 466         case CODE_LABEL:
 467           /* Never propagate across labels.  */
 468           ev = NULL_RTX;
 469           continue;
 470
 471         default:
 472           /* Look for insns that clobber the EV register.  */
 473           if (ev && reg_set_p (ev_reg, insn))
 474             ev = NULL_RTX;
 475           continue;
 476
 477         case JUMP_INSN:
 478           /* Look for simple conditional branches.  If we havn't got an
 479              expected value yet, no point going further.  */
 480           if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX)
 481             continue;
 482           if (! any_condjump_p (insn))
 483             continue;
 484           break;
 485         }
 486
 487       /* Collect the branch condition, hopefully relative to EV_REG.  */
 488       /* ???  At present we'll miss things like
 489                 (expected_value (eq r70 0))
 490                 (set r71 -1)
 491                 (set r80 (lt r70 r71))
 492                 (set pc (if_then_else (ne r80 0) ...))
 493          as canonicalize_condition will render this to us as
 494                 (lt r70, r71)
 495          Could use cselib to try and reduce this further.  */
 496       cond = XEXP (SET_SRC (PATTERN (insn)), 0);
 497       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
 498       if (! cond
 499           || XEXP (cond, 0) != ev_reg
 500           || GET_CODE (XEXP (cond, 1)) != CONST_INT)
 501         continue;
 502
 503       /* Substitute and simplify.  Given that the expression we're
 504          building involves two constants, we should wind up with either
 505          true or false.  */
 506       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 507                              XEXP (ev, 1), XEXP (cond, 1));
 508       cond = simplify_rtx (cond);
 509
 510       /* Turn the condition into a scaled branch probability.  */
 511       if (cond != const1_rtx && cond != const0_rtx)
 512         abort ();
 513       predict_insn_def (insn, PRED_BUILTIN_EXPECT,
 514                         cond == const1_rtx ? TAKEN : NOT_TAKEN);
 515     }
 516 }