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   /* Try to predict condjumps using same algorithm as mostly_true_jump.  */
  99   for (i = 0; i < n_basic_blocks - 1; i++)
 100     {
 101       rtx last_insn = BLOCK_END (i);
 102       rtx cond, earliest;
 103       int prob = 0;
 104
 105       if (GET_CODE (last_insn) != JUMP_INSN
 106           || ! condjump_p (last_insn) || simplejump_p (last_insn))
 107         continue;
 108       cond = get_condition (last_insn, &earliest);
 109       if (! cond)
 110         continue;
 111       /* EQ tests are usually false and NE tests are usually true.  Also,
 112          most quantities are positive, so we can make the appropriate guesses
 113          about signed comparisons against zero.  */
 114       switch (GET_CODE (cond))
 115         {
 116         case CONST_INT:
 117           /* Unconditional branch.  */
 118           prob = REG_BR_PROB_BASE / 2;
 119           break;
 120         case EQ:
 121           prob = REG_BR_PROB_BASE / 10;
 122           break;
 123         case NE:
 124           prob = REG_BR_PROB_BASE / 2;
 125           break;
 126         case LE:
 127         case LT:
 128           if (XEXP (cond, 1) == const0_rtx)
 129             prob = REG_BR_PROB_BASE / 10;
 130           break;
 131         case GE:
 132         case GT:
 133           if (XEXP (cond, 1) == const0_rtx
 134               || (GET_CODE (XEXP (cond, 1)) == CONST_INT
 135                   && INTVAL (XEXP (cond, 1)) == -1))
 136             prob = REG_BR_PROB_BASE / 2;
 137           break;
 138
 139         default:
 140           prob = 0;
 141         }
 142       if (! find_reg_note (last_insn, REG_BR_PROB, 0))
 143         REG_NOTES (last_insn)
 144           = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 145                                REG_NOTES (last_insn));
 146     }
 147 }
 148