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       cond = XEXP (SET_SRC (PATTERN (insn)), 0);
 252       cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
 253       if (! cond || XEXP (cond, 0) != ev_reg)
 254         continue;
 255
 256       /* Substitute and simplify.  Given that the expression we're
 257          building involves two constants, we should wind up with either
 258          true or false.  */
 259       cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
 260                              XEXP (ev, 1), XEXP (cond, 1));
 261       cond = simplify_rtx (cond);
 262
 263       /* Turn the condition into a scaled branch probability.  */
 264       if (cond == const1_rtx)
 265         cond = GEN_INT (REG_BR_PROB_BASE);
 266       else if (cond != const0_rtx)
 267         abort ();
 268       REG_NOTES (insn) = alloc_EXPR_LIST (REG_BR_PROB, cond, REG_NOTES (insn));
 269     }
 270 }