gcc/predict.c

   1 /* Branch prediction routines for the GNU compiler.
   2    Copyright (C) 2000 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 #include "config.h"
  33 #include "system.h"
  34 #include "tree.h"
  35 #include "rtl.h"
  36 #include "tm_p.h"
  37 #include "basic-block.h"
  38 #include "insn-config.h"
  39 #include "regs.h"
  40 #include "hard-reg-set.h"
  41 #include "flags.h"
  42 #include "output.h"
  43 #include "function.h"
  44 #include "except.h"
  45 #include "toplev.h"
  46 #include "recog.h"
  47 #include "insn-flags.h"
  48 #include "expr.h"
  49
  50
  51
  52 /* Statically estimate the probability that a branch will be taken.
  53    ??? In the next revision there will be a number of other predictors added
  54    from the above references. Further, each heuristic will be factored out
  55    into its own function for clarity (and to facilitate the combination of
  56    predictions).  */
  57
  58 void
  59 estimate_probability (loops_info)
  60      struct loops *loops_info;
  61 {
  62   int i;
  63
  64   /* Try to predict out blocks in a loop that are not part of a
  65      natural loop.  */
  66   for (i = 0; i < loops_info->num; i++)
  67     {
  68       int j;
  69
  70       for (j = loops_info->array[i].first->index;
  71            j <= loops_info->array[i].last->index;
  72            ++j)
  73         {
  74           edge e;
  75
  76           if (! TEST_BIT (loops_info->array[i].nodes, j))
  77             for (e = BASIC_BLOCK(j)->pred; e; e = e->pred_next)
  78               if (TEST_BIT (loops_info->array[i].nodes, e->src->index))
  79                 {
  80                   rtx last_insn = BLOCK_END (e->src->index);
  81                   rtx cond, earliest;
  82
  83                   if (GET_CODE (last_insn) != JUMP_INSN
  84                       || ! condjump_p (last_insn) || simplejump_p (last_insn))
  85                     continue;
  86                   cond = get_condition (last_insn, &earliest);
  87                   if (! cond)
  88                     continue;
  89                   if (! find_reg_note (last_insn, REG_BR_PROB, 0))
  90                     REG_NOTES (last_insn)
  91                       = gen_rtx_EXPR_LIST (REG_BR_PROB,
  92                                            GEN_INT (REG_BR_PROB_BASE),
  93                                            REG_NOTES (last_insn));
  94                 }
  95         }
  96     }
  97
  98   /* Attempt to predict conditional jumps using a number of heuristics.
  99      For each conditional jump, we try each heuristic in a fixed order.
 100      If more than one heuristic applies to a particular branch, the first
 101      is used as the prediction for the branch.  */
 102   for (i = 0; i < n_basic_blocks - 1; i++)
 103     {
 104       rtx last_insn = BLOCK_END (i);
 105       rtx cond, earliest;
 106       int prob = 0;
 107
 108       if (GET_CODE (last_insn) != JUMP_INSN
 109           || ! condjump_p (last_insn) || simplejump_p (last_insn))
 110         continue;
 111       cond = get_condition (last_insn, &earliest);
 112       if (! cond)
 113         continue;
 114
 115       /* Try "pointer heuristic."
 116          A comparison ptr == 0 is predicted as false.
 117          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 118       prob = 0;
 119       switch (GET_CODE (cond))
 120         {
 121         case EQ:
 122           if (GET_CODE (XEXP (cond, 0)) == REG
 123               && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 0)))
 124               && (XEXP (cond, 1) == const0_rtx
 125                   || (GET_CODE (XEXP (cond, 1)) == REG
 126                       && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
 127             prob = REG_BR_PROB_BASE / 10;
 128           break;
 129         case NE:
 130           if (GET_CODE (XEXP (cond, 0)) == REG
 131               && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 0)))
 132               && (XEXP (cond, 1) == const0_rtx
 133                   || (GET_CODE (XEXP (cond, 1)) == REG
 134                       && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
 135             prob = REG_BR_PROB_BASE / 2;
 136           break;
 137         default:
 138           prob = 0;
 139         }
 140         if (prob && ! find_reg_note (last_insn, REG_BR_PROB, 0))
 141           REG_NOTES (last_insn)
 142             = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 143                                  REG_NOTES (last_insn));
 144
 145       /* Try "opcode heuristic."
 146          EQ tests are usually false and NE tests are usually true. Also,
 147          most quantities are positive, so we can make the appropriate guesses
 148          about signed comparisons against zero.  */
 149       switch (GET_CODE (cond))
 150         {
 151         case CONST_INT:
 152           /* Unconditional branch.  */
 153           prob = REG_BR_PROB_BASE / 2;
 154           break;
 155         case EQ:
 156           prob = REG_BR_PROB_BASE / 10;
 157           break;
 158         case NE:
 159           prob = REG_BR_PROB_BASE / 2;
 160           break;
 161         case LE:
 162         case LT:
 163           if (XEXP (cond, 1) == const0_rtx)
 164             prob = REG_BR_PROB_BASE / 10;
 165           break;
 166         case GE:
 167         case GT:
 168           if (XEXP (cond, 1) == const0_rtx
 169               || (GET_CODE (XEXP (cond, 1)) == CONST_INT
 170                   && INTVAL (XEXP (cond, 1)) == -1))
 171             prob = REG_BR_PROB_BASE / 2;
 172           break;
 173
 174         default:
 175           prob = 0;
 176         }
 177       if (! find_reg_note (last_insn, REG_BR_PROB, 0))
 178         REG_NOTES (last_insn)
 179           = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 180                                REG_NOTES (last_insn));
 181     }
 182 }
 183 \f
 184 /* __builtin_expect dropped tokens into the insn stream describing
 185    expected values of registers.  Generate branch probabilities
 186    based off these values.  */
 187
 188 static rtx find_expected_value          PARAMS ((rtx, rtx));
 189
 190 void
 191 expected_value_to_br_prob ()
 192 {
 193   rtx insn, cond, ev = NULL_RTX, ev_reg;
 194
 195   for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
 196     {
 197       switch (GET_CODE (insn))
 198         {
 199         case NOTE:
 200           /* Look for expected value notes.  */
 201           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
 202             {
 203               ev = NOTE_EXPECTED_VALUE (insn);
 204               ev_reg = XEXP (ev, 0);
 205             }
 206           continue;
 207
 208         case CODE_LABEL:
 209           /* Never propagate across labels.  */
 210           ev = NULL_RTX;
 211           continue;
 212
 213         default:
 214           /* Look for insns that clobber the EV register.  */
 215           if (ev && reg_set_p (ev_reg, insn))
 216             ev = NULL_RTX;
 217           continue;
 218
 219         case JUMP_INSN:
 220           /* Look for simple conditional branches.  If we havn't got an
 221              expected value yet, no point going further.  */
 222           if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX)
 223             continue;
 224           if (! condjump_p (insn) || simplejump_p (insn))
 225             continue;
 226           break;
 227         }
 228
 229       /* Collect the branch condition, hopefully relative to EV_REG.  */
 230       cond = XEXP (SET_SRC (PATTERN (insn)), 0);
 231       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
 232       if (! cond || XEXP (cond, 0) != ev_reg)
 233         continue;
 234
 235       /* Substitute and simplify.  Given that the expression we're
 236          building involves two constants, we should wind up with either
 237          true or false.  */
 238       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 239                              XEXP (ev, 1), XEXP (cond, 1));
 240       cond = simplify_rtx (cond);
 241
 242       /* Turn the condition into a scaled branch probability.  */
 243       if (cond == const1_rtx)
 244         cond = GEN_INT (REG_BR_PROB_BASE);
 245       else if (cond != const0_rtx)
 246         abort ();
 247       REG_NOTES (insn) = alloc_EXPR_LIST (REG_BR_PROB, cond, REG_NOTES (insn));
 248     }
 249 }