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