1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
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)
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.
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. */
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.
37 #include "basic-block.h"
38 #include "insn-config.h"
40 #include "hard-reg-set.h"
47 #include "insn-flags.h"
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
59 estimate_probability (loops_info)
60 struct loops *loops_info;
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++)
69 for (j = loops_info->array[i].header->index;
70 j <= loops_info->array[i].latch->index;
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))
79 rtx last_insn = BLOCK_END (e->src->index);
82 if (GET_CODE (last_insn) != JUMP_INSN
83 || ! condjump_p (last_insn) || simplejump_p (last_insn))
85 cond = get_condition (last_insn, &earliest);
88 if (! find_reg_note (last_insn, REG_BR_PROB, 0))
90 = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (REG_BR_PROB_BASE),
91 REG_NOTES (last_insn));
96 /* Try to predict condjumps using same algorithm as mostly_true_jump */
97 for (i = 0; i < n_basic_blocks - 1; i++)
99 rtx last_insn = BLOCK_END (i);
103 if (GET_CODE (last_insn) != JUMP_INSN
104 || ! condjump_p (last_insn) || simplejump_p (last_insn))
106 cond = get_condition (last_insn, &earliest);
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))
115 /* Unconditional branch. */
116 prob = REG_BR_PROB_BASE / 2;
118 prob = REG_BR_PROB_BASE / 10;
120 prob = REG_BR_PROB_BASE / 2;
123 if (XEXP (cond, 1) == const0_rtx)
124 prob = REG_BR_PROB_BASE / 10;
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;
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));