1 | /* Definitions for the branch prediction routines in the GNU compiler. |
---|---|

2 | Copyright (C) 2001-2017 Free Software Foundation, Inc. |

3 | |

4 | This file is part of GCC. |

5 | |

6 | GCC is free software; you can redistribute it and/or modify it under |

7 | the terms of the GNU General Public License as published by the Free |

8 | Software Foundation; either version 3, or (at your option) any later |

9 | version. |

10 | |

11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |

12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |

13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |

14 | for more details. |

15 | |

16 | You should have received a copy of the GNU General Public License |

17 | along with GCC; see the file COPYING3. If not see |

18 | <http://www.gnu.org/licenses/>. */ |

19 | |

20 | /* Before including this file, you should define a macro: |

21 | |

22 | DEF_PREDICTOR (ENUM, NAME, HITRATE) |

23 | |

24 | This macro will be called once for each predictor. The ENUM will |

25 | be of type `enum predictor', and will enumerate all supported |

26 | predictors. The order of DEF_PREDICTOR calls is important, as |

27 | in the first match combining heuristics, the predictor appearing |

28 | first in this file will win. |

29 | |

30 | NAME is used in the debugging output to determine predictor type. |

31 | |

32 | HITRATE is the probability that edge predicted by predictor as taken |

33 | will be really taken (so it should be always above |

34 | REG_BR_PROB_BASE / 2). */ |

35 | |

36 | |

37 | /* A value used as final outcome of all heuristics. */ |

38 | DEF_PREDICTOR (PRED_COMBINED, "combined", PROB_ALWAYS, 0) |

39 | |

40 | /* An outcome estimated by Dempster-Shaffer theory. */ |

41 | DEF_PREDICTOR (PRED_DS_THEORY, "DS theory", PROB_ALWAYS, 0) |

42 | |

43 | /* A combined heuristics using probability determined by first |

44 | matching heuristics from this list. */ |

45 | DEF_PREDICTOR (PRED_FIRST_MATCH, "first match", PROB_ALWAYS, 0) |

46 | |

47 | /* Heuristic applying when no heuristic below applies. */ |

48 | DEF_PREDICTOR (PRED_NO_PREDICTION, "no prediction", PROB_ALWAYS, 0) |

49 | |

50 | /* Mark unconditional jump as taken. */ |

51 | DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS, |

52 | PRED_FLAG_FIRST_MATCH) |

53 | |

54 | /* Use number of loop iterations determined by # of iterations |

55 | analysis to set probability. We don't want to use Dempster-Shaffer |

56 | theory here, as the predictions is exact. */ |

57 | DEF_PREDICTOR (PRED_LOOP_ITERATIONS, "loop iterations", PROB_ALWAYS, |

58 | PRED_FLAG_FIRST_MATCH) |

59 | |

60 | /* Assume that any given atomic operation has low contention, |

61 | and thus the compare-and-swap operation succeeds. */ |

62 | DEF_PREDICTOR (PRED_COMPARE_AND_SWAP, "compare and swap", PROB_VERY_LIKELY, |

63 | PRED_FLAG_FIRST_MATCH) |

64 | |

65 | /* Hints dropped by user via __builtin_expect feature. Note: the |

66 | probability of PROB_VERY_LIKELY is now overwritten by param |

67 | builtin_expect_probability with a default value of HITRATE(90). |

68 | Refer to param.def for details. */ |

69 | DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY, |

70 | PRED_FLAG_FIRST_MATCH) |

71 | |

72 | /* Use number of loop iterations guessed by the contents of the loop. */ |

73 | DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations", |

74 | PROB_ALWAYS, PRED_FLAG_FIRST_MATCH) |

75 | |

76 | /* Use number of loop iterations guessed by the contents of the loop. */ |

77 | DEF_PREDICTOR (PRED_LOOP_ITERATIONS_MAX, "guessed loop iterations", |

78 | PROB_ALWAYS, PRED_FLAG_FIRST_MATCH) |

79 | |

80 | /* Branch containing goto is probably not taken. */ |

81 | DEF_PREDICTOR (PRED_CONTINUE, "continue", HITRATE ( 67), 0) |

82 | |

83 | /* Branch to basic block containing call marked by noreturn attribute. */ |

84 | DEF_PREDICTOR (PRED_NORETURN, "noreturn call", PROB_VERY_LIKELY, |

85 | PRED_FLAG_FIRST_MATCH) |

86 | |

87 | /* Branch to basic block containing call marked by cold function attribute. */ |

88 | DEF_PREDICTOR (PRED_COLD_FUNCTION, "cold function call", PROB_VERY_LIKELY, |

89 | PRED_FLAG_FIRST_MATCH) |

90 | |

91 | /* Edge causing loop to terminate is probably not taken. */ |

92 | DEF_PREDICTOR (PRED_LOOP_EXIT, "loop exit", HITRATE ( 85), |

93 | PRED_FLAG_FIRST_MATCH) |

94 | |

95 | /* Same as LOOP_EXIT but for loops containing recursive call. */ |

96 | DEF_PREDICTOR (PRED_LOOP_EXIT_WITH_RECURSION, "loop exit with recursion", |

97 | HITRATE (72), PRED_FLAG_FIRST_MATCH) |

98 | |

99 | /* Edge causing loop to terminate by computing value used by later |

100 | conditional. */ |

101 | DEF_PREDICTOR (PRED_LOOP_EXTRA_EXIT, "extra loop exit", HITRATE ( 83), |

102 | PRED_FLAG_FIRST_MATCH) |

103 | |

104 | /* Pointers are usually not NULL. */ |

105 | DEF_PREDICTOR (PRED_POINTER, "pointer", HITRATE ( 70), 0) |

106 | DEF_PREDICTOR (PRED_TREE_POINTER, "pointer (on trees)", HITRATE ( 70), 0) |

107 | |

108 | /* NE is probable, EQ not etc... */ |

109 | DEF_PREDICTOR (PRED_OPCODE_POSITIVE, "opcode values positive", HITRATE ( 64), 0) |

110 | DEF_PREDICTOR (PRED_OPCODE_NONEQUAL, "opcode values nonequal", HITRATE ( 66), 0) |

111 | DEF_PREDICTOR (PRED_FPOPCODE, "fp_opcode", HITRATE ( 90), 0) |

112 | DEF_PREDICTOR (PRED_TREE_OPCODE_POSITIVE, "opcode values positive (on trees)", |

113 | HITRATE (64), 0) |

114 | DEF_PREDICTOR (PRED_TREE_OPCODE_NONEQUAL, "opcode values nonequal (on trees)", |

115 | HITRATE (66), 0) |

116 | DEF_PREDICTOR (PRED_TREE_FPOPCODE, "fp_opcode (on trees)", HITRATE ( 90), 0) |

117 | |

118 | /* Branch guarding call is probably taken. */ |

119 | DEF_PREDICTOR (PRED_CALL, "call", HITRATE ( 67), 0) |

120 | |

121 | /* PRED_CALL is not very reliable predictor and it turns out to be even |

122 | less reliable for indirect calls and polymorphic calls. For spec2k6 |

123 | the predictio nis slightly in the direction of taking the call. */ |

124 | DEF_PREDICTOR (PRED_INDIR_CALL, "indirect call", HITRATE ( 86), 0) |

125 | DEF_PREDICTOR (PRED_POLYMORPHIC_CALL, "polymorphic call", HITRATE ( 59), 0) |

126 | |

127 | /* Recursive calls are usually not taken or the function will recurse |

128 | indefinitely. */ |

129 | DEF_PREDICTOR (PRED_RECURSIVE_CALL, "recursive call", HITRATE ( 75), 0) |

130 | |

131 | /* Branch causing function to terminate is probably not taken. */ |

132 | DEF_PREDICTOR (PRED_TREE_EARLY_RETURN, "early return (on trees)", HITRATE ( 66), |

133 | 0) |

134 | |

135 | /* Branch containing goto is probably not taken. */ |

136 | DEF_PREDICTOR (PRED_GOTO, "goto", HITRATE ( 66), 0) |

137 | |

138 | /* Branch ending with return constant is probably not taken. */ |

139 | DEF_PREDICTOR (PRED_CONST_RETURN, "const return", HITRATE ( 69), 0) |

140 | |

141 | /* Branch ending with return negative constant is probably not taken. */ |

142 | DEF_PREDICTOR (PRED_NEGATIVE_RETURN, "negative return", HITRATE ( 98), 0) |

143 | |

144 | /* Branch ending with return; is probably not taken */ |

145 | DEF_PREDICTOR (PRED_NULL_RETURN, "null return", HITRATE ( 91), 0) |

146 | |

147 | /* Branches to compare induction variable to a loop bound is |

148 | extremely likely. */ |

149 | DEF_PREDICTOR (PRED_LOOP_IV_COMPARE_GUESS, "guess loop iv compare", |

150 | HITRATE (98), 0) |

151 | |

152 | /* Use number of loop iterations determined by # of iterations analysis |

153 | to set probability of branches that compares IV to loop bound variable. */ |

154 | DEF_PREDICTOR (PRED_LOOP_IV_COMPARE, "loop iv compare", PROB_VERY_LIKELY, |

155 | PRED_FLAG_FIRST_MATCH) |

156 | |

157 | /* In the following code |

158 | for (loop1) |

159 | if (cond) |

160 | for (loop2) |

161 | body; |

162 | guess that cond is unlikely. */ |

163 | DEF_PREDICTOR (PRED_LOOP_GUARD, "loop guard", HITRATE ( 66), 0) |

164 | |

165 | /* Same but for loops containing recursion. */ |

166 | DEF_PREDICTOR (PRED_LOOP_GUARD_WITH_RECURSION, "loop guard with recursion", |

167 | HITRATE (85), 0) |

168 | |

169 | /* Branches to hot labels are likely. */ |

170 | DEF_PREDICTOR (PRED_HOT_LABEL, "hot label", HITRATE ( 85), 0) |

171 | |

172 | /* Branches to cold labels are extremely unlikely. */ |

173 | DEF_PREDICTOR (PRED_COLD_LABEL, "cold label", PROB_VERY_LIKELY, |

174 | PRED_FLAG_FIRST_MATCH) |

175 | |

176 | |

177 | /* The following predictors are used in Fortran. */ |

178 | |

179 | /* Branch leading to an integer overflow are extremely unlikely. */ |

180 | DEF_PREDICTOR (PRED_FORTRAN_OVERFLOW, "Fortran overflow", PROB_ALWAYS, |

181 | PRED_FLAG_FIRST_MATCH) |

182 | |

183 | /* Branch leading to a failure status are unlikely. This can occur for out |

184 | of memory. This predictor only occurs when the user explicitly asked |

185 | for a return status. By default, the code aborts, |

186 | which is handled via PRED_NORETURN. */ |

187 | DEF_PREDICTOR (PRED_FORTRAN_FAIL_ALLOC, "Fortran fail alloc", |

188 | PROB_VERY_LIKELY, 0) |

189 | |

190 | /* Predictor is used for an allocation of an already allocated memory or |

191 | deallocating an already deallocated allocatable. */ |

192 | DEF_PREDICTOR (PRED_FORTRAN_REALLOC, "Fortran repeated allocation/deallocation", |

193 | PROB_LIKELY, 0) |

194 | |

195 | /* Branch leading to an I/O failure status are unlikely. This predictor is |

196 | used for I/O failures such as for invalid unit numbers. This predictor |

197 | only occurs when the user explicitly asked for a return status. By default, |

198 | the code aborts, which is handled via PRED_NORETURN. */ |

199 | DEF_PREDICTOR (PRED_FORTRAN_FAIL_IO, "Fortran fail IO", HITRATE ( 85), 0) |

200 | |

201 | /* Branch leading to a run-time warning message which is printed only once |

202 | are unlikely. The print-warning branch itself can be likely or unlikely. */ |

203 | DEF_PREDICTOR (PRED_FORTRAN_WARN_ONCE, "Fortran warn once", HITRATE ( 75), 0) |

204 | |

205 | /* Branch belonging to a zero-sized array. */ |

206 | DEF_PREDICTOR (PRED_FORTRAN_SIZE_ZERO, "Fortran zero-sized array", \ |

207 | HITRATE (99), 0) |

208 | |

209 | /* Branch belonging to an invalid bound index, in a context where it is |

210 | standard conform and well defined but rather pointless and, hence, rather |

211 | unlikely to occur. */ |

212 | DEF_PREDICTOR (PRED_FORTRAN_INVALID_BOUND, "Fortran invalid bound", \ |

213 | HITRATE (90), 0) |

214 | |

215 | /* Branch belonging to the handling of absent optional arguments. This |

216 | predictor is used when an optional dummy argument, associated with an |

217 | absent argument, is passed on as actual argument to another procedure, |

218 | which in turn has an optional argument. */ |

219 | DEF_PREDICTOR (PRED_FORTRAN_ABSENT_DUMMY, "Fortran absent dummy", \ |

220 | HITRATE (60), 0) |

221 | |

222 | /* Fortran DO statement generates a pre-header guard: |

223 | empty = (step > 0 ? to < from : to > from), which can be predicted |

224 | to be very likely. */ |

225 | DEF_PREDICTOR (PRED_FORTRAN_LOOP_PREHEADER, "Fortran loop preheader", \ |

226 | HITRATE (99), 0) |

227 |