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 natural loop */
  65   for (i = 0; i < loops_info->num; i++)
  66     {
  67       int j;
  68
  69       for (j = loops_info->array[i].header->index;
  70            j <= loops_info->array[i].latch->index;
  71            ++j)
  72         {
  73           edge e;
  74
  75           if (! TEST_BIT (loops_info->array[i].nodes, j))
  76             for (e = BASIC_BLOCK(j)->pred; e; e = e->pred_next)
  77               if (TEST_BIT (loops_info->array[i].nodes, e->src->index))
  78                 {
  79                   rtx last_insn = BLOCK_END (e->src->index);
  80                   rtx cond, earliest;
  81
  82                   if (GET_CODE (last_insn) != JUMP_INSN
  83                       || ! condjump_p (last_insn) || simplejump_p (last_insn))
  84                     continue;
  85                   cond = get_condition (last_insn, &earliest);
  86                   if (!cond)
  87                     continue;
  88                   if (! find_reg_note (last_insn, REG_BR_PROB, 0))
  89                     REG_NOTES (last_insn)
  90                       = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (REG_BR_PROB_BASE),
  91                                            REG_NOTES (last_insn));
  92                 }
  93         }
  94     }
  95
  96   /* Try to predict condjumps using same algorithm as mostly_true_jump */
  97   for (i = 0; i < n_basic_blocks - 1; i++)
  98     {
  99       rtx last_insn = BLOCK_END (i);
 100       rtx cond, earliest;
 101       int prob = 0;
 102
 103       if (GET_CODE (last_insn) != JUMP_INSN
 104           || ! condjump_p (last_insn) || simplejump_p (last_insn))
 105         continue;
 106       cond = get_condition (last_insn, &earliest);
 107       if (! cond)
 108         continue;
 109       /* EQ tests are usually false and NE tests are usually true.  Also,
 110          most quantities are positive, so we can make the appropriate guesses
 111          about signed comparisons against zero.  */
 112       switch (GET_CODE (cond))
 113         {
 114         case CONST_INT:
 115           /* Unconditional branch.  */
 116           prob = REG_BR_PROB_BASE / 2;
 117         case EQ:
 118           prob = REG_BR_PROB_BASE / 10;
 119         case NE:
 120           prob = REG_BR_PROB_BASE / 2;
 121         case LE:
 122         case LT:
 123           if (XEXP (cond, 1) == const0_rtx)
 124             prob = REG_BR_PROB_BASE / 10;
 125           break;
 126         case GE:
 127         case GT:
 128           if (XEXP (cond, 1) == const0_rtx
 129               || (GET_CODE (XEXP (cond, 1)) == CONST_INT
 130                   && INTVAL (XEXP (cond, 1)) == -1))
 131             prob = REG_BR_PROB_BASE / 2;
 132           break;
 133
 134         default:
 135           prob = 0;
 136         }
 137       if (! find_reg_note (last_insn, REG_BR_PROB, 0))
 138         REG_NOTES (last_insn)
 139           = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
 140                                REG_NOTES (last_insn));
 141     }
 142 }
 143