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