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 "insn-flags.h"
  49 #include "expr.h"
  50
  51
  52 /* Random guesstimation given names.  */
  53 #define PROB_NEVER              (0)
  54 #define PROB_VERY_UNLIKELY      (REG_BR_PROB_BASE / 10 - 1)
  55 #define PROB_UNLIKELY           (REG_BR_PROB_BASE * 4 / 10 - 1)
  56 #define PROB_EVEN               (REG_BR_PROB_BASE / 2)
  57 #define PROB_LIKELY             (REG_BR_PROB_BASE - PROB_UNLIKELY)
  58 #define PROB_VERY_LIKELY        (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
  59 #define PROB_ALWAYS             (REG_BR_PROB_BASE)
  60
  61 /* Statically estimate the probability that a branch will be taken.
  62    ??? In the next revision there will be a number of other predictors added
  63    from the above references. Further, each heuristic will be factored out
  64    into its own function for clarity (and to facilitate the combination of
  65    predictions).  */
  66
  67 void
  68 estimate_probability (loops_info)
  69      struct loops *loops_info;
  70 {
  71   int i;
  72
  73   /* Try to predict out blocks in a loop that are not part of a
  74      natural loop.  */
  75   for (i = 0; i < loops_info->num; i++)
  76     {
  77       int j;
  78
  79       for (j = loops_info->array[i].first->index;
  80            j <= loops_info->array[i].last->index;
  81            ++j)
  82         {
  83           edge e;
  84
  85           if (! TEST_BIT (loops_info->array[i].nodes, j))
  86             for (e = BASIC_BLOCK(j)->pred; e; e = e->pred_next)
  87               if (TEST_BIT (loops_info->array[i].nodes, e->src->index))
  88                 {
  89                   rtx last_insn = BLOCK_END (e->src->index);
  90                   rtx cond, earliest;
  91
  92                   if (GET_CODE (last_insn) != JUMP_INSN
  93                       || ! condjump_p (last_insn) || simplejump_p (last_insn))
  94                     continue;
  95                   cond = get_condition (last_insn, &earliest);
  96                   if (! cond)
  97                     continue;
  98                   if (! find_reg_note (last_insn, REG_BR_PROB, 0))
  99                     REG_NOTES (last_insn)
 100                       = gen_rtx_EXPR_LIST (REG_BR_PROB,
 101                                            GEN_INT (PROB_VERY_LIKELY),
 102                                            REG_NOTES (last_insn));
 103                 }
 104         }
 105     }
 106
 107   /* Attempt to predict conditional jumps using a number of heuristics.
 108      For each conditional jump, we try each heuristic in a fixed order.
 109      If more than one heuristic applies to a particular branch, the first
 110      is used as the prediction for the branch.  */
 111   for (i = 0; i < n_basic_blocks - 1; i++)
 112     {
 113       rtx last_insn = BLOCK_END (i);
 114       rtx cond, earliest;
 115       int prob;
 116       edge e;
 117
 118       if (GET_CODE (last_insn) != JUMP_INSN
 119           || ! condjump_p (last_insn) || simplejump_p (last_insn))
 120         continue;
 121
 122       if (find_reg_note (last_insn, REG_BR_PROB, 0))
 123         continue;
 124
 125       cond = get_condition (last_insn, &earliest);
 126       if (! cond)
 127         continue;
 128
 129       /* If one of the successor blocks has no successors, predict
 130          that side not taken.  */
 131       /* ??? Ought to do the same for any subgraph with no exit.  */
 132       for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
 133         if (e->dest->succ == NULL)
 134           {
 135             if (e->flags & EDGE_FALLTHRU)
 136               prob = PROB_ALWAYS;
 137             else
 138               prob = PROB_NEVER;
 139             goto emitnote;
 140           }
 141
 142       /* Try "pointer heuristic."
 143          A comparison ptr == 0 is predicted as false.
 144          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 145       switch (GET_CODE (cond))
 146         {
 147         case EQ:
 148           if (GET_CODE (XEXP (cond, 0)) == REG
 149               && REG_POINTER (XEXP (cond, 0))
 150               && (XEXP (cond, 1) == const0_rtx
 151                   || (GET_CODE (XEXP (cond, 1)) == REG
 152                       && REG_POINTER (XEXP (cond, 1)))))
 153             {
 154               prob = PROB_UNLIKELY;
 155               goto emitnote;
 156             }
 157           break;
 158         case NE:
 159           if (GET_CODE (XEXP (cond, 0)) == REG
 160               && REG_POINTER (XEXP (cond, 0))
 161               && (XEXP (cond, 1) == const0_rtx
 162                   || (GET_CODE (XEXP (cond, 1)) == REG
 163                       && REG_POINTER (XEXP (cond, 1)))))
 164             {
 165               prob = PROB_LIKELY;
 166               goto emitnote;
 167             }
 168           break;
 169
 170         default:
 171           break;
 172         }
 173
 174       /* Try "opcode heuristic."
 175          EQ tests are usually false and NE tests are usually true. Also,
 176          most quantities are positive, so we can make the appropriate guesses
 177          about signed comparisons against zero.  */
 178       switch (GET_CODE (cond))
 179         {
 180         case CONST_INT:
 181           /* Unconditional branch.  */
 182           prob = (cond == const0_rtx ? PROB_NEVER : PROB_ALWAYS);
 183           goto emitnote;
 184
 185         case EQ:
 186         case UNEQ:
 187           prob = PROB_UNLIKELY;
 188           goto emitnote;
 189         case NE:
 190         case LTGT:
 191           prob = PROB_LIKELY;
 192           goto emitnote;
 193         case ORDERED:
 194           prob = PROB_LIKELY;
 195           goto emitnote;
 196         case UNORDERED:
 197           prob = PROB_UNLIKELY;
 198           goto emitnote;
 199         case LE:
 200         case LT:
 201           if (XEXP (cond, 1) == const0_rtx)
 202             {
 203               prob = PROB_UNLIKELY;
 204               goto emitnote;
 205             }
 206           break;
 207         case GE:
 208         case GT:
 209           if (XEXP (cond, 1) == const0_rtx
 210               || (GET_CODE (XEXP (cond, 1)) == CONST_INT
 211                   && INTVAL (XEXP (cond, 1)) == -1))
 212             {
 213               prob = PROB_LIKELY;
 214               goto emitnote;
 215             }
 216           break;
 217
 218         default:
 219           break;
 220         }
 221
 222       /* If we havn't chosen something by now, predict 50-50.  */
 223       prob = PROB_EVEN;
 224
 225     emitnote:
 226       REG_NOTES (last_insn)
 227         = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 228                              REG_NOTES (last_insn));
 229     }
 230 }
 231 \f
 232 /* __builtin_expect dropped tokens into the insn stream describing
 233    expected values of registers.  Generate branch probabilities
 234    based off these values.  */
 235
 236 void
 237 expected_value_to_br_prob ()
 238 {
 239   rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
 240
 241   for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
 242     {
 243       switch (GET_CODE (insn))
 244         {
 245         case NOTE:
 246           /* Look for expected value notes.  */
 247           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
 248             {
 249               ev = NOTE_EXPECTED_VALUE (insn);
 250               ev_reg = XEXP (ev, 0);
 251             }
 252           continue;
 253
 254         case CODE_LABEL:
 255           /* Never propagate across labels.  */
 256           ev = NULL_RTX;
 257           continue;
 258
 259         default:
 260           /* Look for insns that clobber the EV register.  */
 261           if (ev && reg_set_p (ev_reg, insn))
 262             ev = NULL_RTX;
 263           continue;
 264
 265         case JUMP_INSN:
 266           /* Look for simple conditional branches.  If we havn't got an
 267              expected value yet, no point going further.  */
 268           if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX)
 269             continue;
 270           if (! condjump_p (insn) || simplejump_p (insn))
 271             continue;
 272           break;
 273         }
 274
 275       /* Collect the branch condition, hopefully relative to EV_REG.  */
 276       /* ???  At present we'll miss things like
 277                 (expected_value (eq r70 0))
 278                 (set r71 -1)
 279                 (set r80 (lt r70 r71))
 280                 (set pc (if_then_else (ne r80 0) ...))
 281          as canonicalize_condition will render this to us as
 282                 (lt r70, r71)
 283          Could use cselib to try and reduce this further.  */
 284       cond = XEXP (SET_SRC (PATTERN (insn)), 0);
 285       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
 286       if (! cond
 287           || XEXP (cond, 0) != ev_reg
 288           || GET_CODE (XEXP (cond, 1)) != CONST_INT)
 289         continue;
 290
 291       /* Substitute and simplify.  Given that the expression we're
 292          building involves two constants, we should wind up with either
 293          true or false.  */
 294       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 295                              XEXP (ev, 1), XEXP (cond, 1));
 296       cond = simplify_rtx (cond);
 297
 298       /* Turn the condition into a scaled branch probability.  */
 299       if (cond == const1_rtx)
 300         cond = GEN_INT (PROB_VERY_LIKELY);
 301       else if (cond == const0_rtx)
 302         cond = GEN_INT (PROB_VERY_UNLIKELY);
 303       else
 304         abort ();
 305       REG_NOTES (insn) = alloc_EXPR_LIST (REG_BR_PROB, cond, REG_NOTES (insn));
 306     }
 307 }