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;
 107       edge e;
 108
 109       if (GET_CODE (last_insn) != JUMP_INSN
 110           || ! condjump_p (last_insn) || simplejump_p (last_insn))
 111         continue;
 112
 113       if (find_reg_note (last_insn, REG_BR_PROB, 0))
 114         continue;
 115
 116       cond = get_condition (last_insn, &earliest);
 117       if (! cond)
 118         continue;
 119
 120       /* If one of the successor blocks has no successors, predict
 121          that side not taken.  */
 122       /* ??? Ought to do the same for any subgraph with no exit.  */
 123       for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
 124         if (e->dest->succ == NULL)
 125           {
 126             if (e->flags & EDGE_FALLTHRU)
 127               prob = REG_BR_PROB_BASE;
 128             else
 129               prob = 0;
 130             goto emitnote;
 131           }
 132
 133       /* Try "pointer heuristic."
 134          A comparison ptr == 0 is predicted as false.
 135          Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
 136       switch (GET_CODE (cond))
 137         {
 138         case EQ:
 139           if (GET_CODE (XEXP (cond, 0)) == REG
 140               && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 0)))
 141               && (XEXP (cond, 1) == const0_rtx
 142                   || (GET_CODE (XEXP (cond, 1)) == REG
 143                       && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
 144             {
 145               prob = REG_BR_PROB_BASE / 10;
 146               goto emitnote;
 147             }
 148           break;
 149         case NE:
 150           if (GET_CODE (XEXP (cond, 0)) == REG
 151               && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 0)))
 152               && (XEXP (cond, 1) == const0_rtx
 153                   || (GET_CODE (XEXP (cond, 1)) == REG
 154                       && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
 155             {
 156               prob = REG_BR_PROB_BASE - (REG_BR_PROB_BASE / 10);
 157               goto emitnote;
 158             }
 159           break;
 160
 161         default:
 162           break;
 163         }
 164
 165       /* Try "opcode heuristic."
 166          EQ tests are usually false and NE tests are usually true. Also,
 167          most quantities are positive, so we can make the appropriate guesses
 168          about signed comparisons against zero.  */
 169       switch (GET_CODE (cond))
 170         {
 171         case CONST_INT:
 172           /* Unconditional branch.  */
 173           prob = (cond == const0_rtx ? 0 : REG_BR_PROB_BASE);
 174           goto emitnote;
 175
 176         case EQ:
 177           prob = REG_BR_PROB_BASE / 10;
 178           goto emitnote;
 179         case NE:
 180           prob = REG_BR_PROB_BASE - (REG_BR_PROB_BASE / 10);
 181           goto emitnote;
 182         case LE:
 183         case LT:
 184           if (XEXP (cond, 1) == const0_rtx)
 185             {
 186               prob = REG_BR_PROB_BASE / 10;
 187               goto emitnote;
 188             }
 189           break;
 190         case GE:
 191         case GT:
 192           if (XEXP (cond, 1) == const0_rtx
 193               || (GET_CODE (XEXP (cond, 1)) == CONST_INT
 194                   && INTVAL (XEXP (cond, 1)) == -1))
 195             {
 196               prob = REG_BR_PROB_BASE - (REG_BR_PROB_BASE / 10);
 197               goto emitnote;
 198             }
 199           break;
 200
 201         default:
 202           break;
 203         }
 204
 205       /* If we havn't chosen something by now, predict 50-50.  */
 206       prob = REG_BR_PROB_BASE / 2;
 207
 208     emitnote:
 209       REG_NOTES (last_insn)
 210         = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 211                              REG_NOTES (last_insn));
 212     }
 213 }
 214 \f
 215 /* __builtin_expect dropped tokens into the insn stream describing
 216    expected values of registers.  Generate branch probabilities
 217    based off these values.  */
 218
 219 static rtx find_expected_value          PARAMS ((rtx, rtx));
 220
 221 void
 222 expected_value_to_br_prob ()
 223 {
 224   rtx insn, cond, ev = NULL_RTX, ev_reg;
 225
 226   for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
 227     {
 228       switch (GET_CODE (insn))
 229         {
 230         case NOTE:
 231           /* Look for expected value notes.  */
 232           if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
 233             {
 234               ev = NOTE_EXPECTED_VALUE (insn);
 235               ev_reg = XEXP (ev, 0);
 236             }
 237           continue;
 238
 239         case CODE_LABEL:
 240           /* Never propagate across labels.  */
 241           ev = NULL_RTX;
 242           continue;
 243
 244         default:
 245           /* Look for insns that clobber the EV register.  */
 246           if (ev && reg_set_p (ev_reg, insn))
 247             ev = NULL_RTX;
 248           continue;
 249
 250         case JUMP_INSN:
 251           /* Look for simple conditional branches.  If we havn't got an
 252              expected value yet, no point going further.  */
 253           if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX)
 254             continue;
 255           if (! condjump_p (insn) || simplejump_p (insn))
 256             continue;
 257           break;
 258         }
 259
 260       /* Collect the branch condition, hopefully relative to EV_REG.  */
 261       /* ???  At present we'll miss things like
 262                 (expected_value (eq r70 0))
 263                 (set r71 -1)
 264                 (set r80 (lt r70 r71))
 265                 (set pc (if_then_else (ne r80 0) ...))
 266          as canonicalize_condition will render this to us as
 267                 (lt r70, r71)
 268          Could use cselib to try and reduce this further.  */
 269       cond = XEXP (SET_SRC (PATTERN (insn)), 0);
 270       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
 271       if (! cond
 272           || XEXP (cond, 0) != ev_reg
 273           || GET_CODE (XEXP (cond, 1)) != CONST_INT)
 274         continue;
 275
 276       /* Substitute and simplify.  Given that the expression we're
 277          building involves two constants, we should wind up with either
 278          true or false.  */
 279       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 280                              XEXP (ev, 1), XEXP (cond, 1));
 281       cond = simplify_rtx (cond);
 282
 283       /* Turn the condition into a scaled branch probability.  */
 284       if (cond == const1_rtx)
 285         cond = GEN_INT (REG_BR_PROB_BASE);
 286       else if (cond != const0_rtx)
 287         abort ();
 288       REG_NOTES (insn) = alloc_EXPR_LIST (REG_BR_PROB, cond, REG_NOTES (insn));
 289     }
 290 }