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