]>
Commit | Line | Data |
---|---|---|
f1ebdfc5 | 1 | /* Branch prediction routines for the GNU compiler. |
3ef42a0c | 2 | Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc. |
f1ebdfc5 | 3 | |
bfdade77 | 4 | This file is part of GCC. |
f1ebdfc5 | 5 | |
bfdade77 RK |
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 2, or (at your option) any later | |
9 | version. | |
f1ebdfc5 | 10 | |
bfdade77 RK |
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. | |
f1ebdfc5 | 15 | |
bfdade77 RK |
16 | You should have received a copy of the GNU General Public License |
17 | along with GCC; see the file COPYING. If not, write to the Free | |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
f1ebdfc5 JE |
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" | |
3ef42a0c | 28 | Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */ |
f1ebdfc5 JE |
29 | |
30 | ||
31 | #include "config.h" | |
32 | #include "system.h" | |
33 | #include "tree.h" | |
34 | #include "rtl.h" | |
35 | #include "tm_p.h" | |
efc9bd41 | 36 | #include "hard-reg-set.h" |
f1ebdfc5 JE |
37 | #include "basic-block.h" |
38 | #include "insn-config.h" | |
39 | #include "regs.h" | |
f1ebdfc5 JE |
40 | #include "flags.h" |
41 | #include "output.h" | |
42 | #include "function.h" | |
43 | #include "except.h" | |
44 | #include "toplev.h" | |
45 | #include "recog.h" | |
f1ebdfc5 | 46 | #include "expr.h" |
4db384c9 | 47 | #include "predict.h" |
f1ebdfc5 | 48 | |
c66f079e RH |
49 | /* Random guesstimation given names. */ |
50 | #define PROB_NEVER (0) | |
51 | #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1) | |
52 | #define PROB_UNLIKELY (REG_BR_PROB_BASE * 4 / 10 - 1) | |
53 | #define PROB_EVEN (REG_BR_PROB_BASE / 2) | |
54 | #define PROB_LIKELY (REG_BR_PROB_BASE - PROB_UNLIKELY) | |
55 | #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY) | |
56 | #define PROB_ALWAYS (REG_BR_PROB_BASE) | |
f1ebdfc5 | 57 | |
4db384c9 JH |
58 | static void combine_predictions_for_insn PARAMS ((rtx, basic_block)); |
59 | static void dump_prediction PARAMS ((enum br_predictor, int, | |
b213a5ca | 60 | basic_block, int)); |
861f9cd0 JH |
61 | static void estimate_loops_at_level PARAMS ((struct loop *loop)); |
62 | static void propagate_freq PARAMS ((basic_block)); | |
63 | static void estimate_bb_frequencies PARAMS ((struct loops *)); | |
64 | static void counts_to_freqs PARAMS ((void)); | |
ee92cb46 | 65 | |
4db384c9 JH |
66 | /* Information we hold about each branch predictor. |
67 | Filled using information from predict.def. */ | |
bfdade77 | 68 | |
4db384c9 | 69 | struct predictor_info |
ee92cb46 | 70 | { |
8b60264b KG |
71 | const char *const name; /* Name used in the debugging dumps. */ |
72 | const int hitrate; /* Expected hitrate used by | |
73 | predict_insn_def call. */ | |
74 | const int flags; | |
4db384c9 | 75 | }; |
ee92cb46 | 76 | |
134d3a2e JH |
77 | /* Use given predictor without Dempster-Shaffer theory if it matches |
78 | using first_match heuristics. */ | |
79 | #define PRED_FLAG_FIRST_MATCH 1 | |
80 | ||
81 | /* Recompute hitrate in percent to our representation. */ | |
82 | ||
bfdade77 | 83 | #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100) |
134d3a2e JH |
84 | |
85 | #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS}, | |
bfdade77 | 86 | static const struct predictor_info predictor_info[]= { |
4db384c9 JH |
87 | #include "predict.def" |
88 | ||
dc297297 | 89 | /* Upper bound on predictors. */ |
134d3a2e | 90 | {NULL, 0, 0} |
4db384c9 JH |
91 | }; |
92 | #undef DEF_PREDICTOR | |
ee92cb46 | 93 | |
4db384c9 JH |
94 | void |
95 | predict_insn (insn, predictor, probability) | |
96 | rtx insn; | |
97 | int probability; | |
98 | enum br_predictor predictor; | |
99 | { | |
ee92cb46 JH |
100 | if (!any_condjump_p (insn)) |
101 | abort (); | |
bfdade77 | 102 | |
ee92cb46 | 103 | REG_NOTES (insn) |
4db384c9 JH |
104 | = gen_rtx_EXPR_LIST (REG_BR_PRED, |
105 | gen_rtx_CONCAT (VOIDmode, | |
106 | GEN_INT ((int) predictor), | |
107 | GEN_INT ((int) probability)), | |
108 | REG_NOTES (insn)); | |
109 | } | |
110 | ||
111 | /* Predict insn by given predictor. */ | |
bfdade77 | 112 | |
4db384c9 JH |
113 | void |
114 | predict_insn_def (insn, predictor, taken) | |
115 | rtx insn; | |
116 | enum br_predictor predictor; | |
117 | enum prediction taken; | |
118 | { | |
119 | int probability = predictor_info[(int) predictor].hitrate; | |
bfdade77 | 120 | |
4db384c9 JH |
121 | if (taken != TAKEN) |
122 | probability = REG_BR_PROB_BASE - probability; | |
bfdade77 | 123 | |
4db384c9 | 124 | predict_insn (insn, predictor, probability); |
ee92cb46 JH |
125 | } |
126 | ||
127 | /* Predict edge E with given probability if possible. */ | |
bfdade77 | 128 | |
4db384c9 JH |
129 | void |
130 | predict_edge (e, predictor, probability) | |
ee92cb46 JH |
131 | edge e; |
132 | int probability; | |
4db384c9 | 133 | enum br_predictor predictor; |
ee92cb46 JH |
134 | { |
135 | rtx last_insn; | |
136 | last_insn = e->src->end; | |
137 | ||
138 | /* We can store the branch prediction information only about | |
139 | conditional jumps. */ | |
140 | if (!any_condjump_p (last_insn)) | |
141 | return; | |
142 | ||
143 | /* We always store probability of branching. */ | |
144 | if (e->flags & EDGE_FALLTHRU) | |
145 | probability = REG_BR_PROB_BASE - probability; | |
146 | ||
4db384c9 JH |
147 | predict_insn (last_insn, predictor, probability); |
148 | } | |
149 | ||
150 | /* Predict edge E by given predictor if possible. */ | |
bfdade77 | 151 | |
4db384c9 JH |
152 | void |
153 | predict_edge_def (e, predictor, taken) | |
154 | edge e; | |
155 | enum br_predictor predictor; | |
156 | enum prediction taken; | |
157 | { | |
158 | int probability = predictor_info[(int) predictor].hitrate; | |
159 | ||
160 | if (taken != TAKEN) | |
161 | probability = REG_BR_PROB_BASE - probability; | |
bfdade77 | 162 | |
4db384c9 JH |
163 | predict_edge (e, predictor, probability); |
164 | } | |
165 | ||
166 | /* Invert all branch predictions or probability notes in the INSN. This needs | |
167 | to be done each time we invert the condition used by the jump. */ | |
bfdade77 | 168 | |
4db384c9 JH |
169 | void |
170 | invert_br_probabilities (insn) | |
171 | rtx insn; | |
172 | { | |
bfdade77 RK |
173 | rtx note; |
174 | ||
175 | for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) | |
176 | if (REG_NOTE_KIND (note) == REG_BR_PROB) | |
177 | XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0))); | |
178 | else if (REG_NOTE_KIND (note) == REG_BR_PRED) | |
179 | XEXP (XEXP (note, 0), 1) | |
180 | = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1))); | |
4db384c9 JH |
181 | } |
182 | ||
183 | /* Dump information about the branch prediction to the output file. */ | |
bfdade77 | 184 | |
4db384c9 | 185 | static void |
d195b46f | 186 | dump_prediction (predictor, probability, bb, used) |
4db384c9 JH |
187 | enum br_predictor predictor; |
188 | int probability; | |
189 | basic_block bb; | |
b213a5ca | 190 | int used; |
4db384c9 JH |
191 | { |
192 | edge e = bb->succ; | |
193 | ||
194 | if (!rtl_dump_file) | |
195 | return; | |
196 | ||
fbc2782e | 197 | while (e && (e->flags & EDGE_FALLTHRU)) |
4db384c9 JH |
198 | e = e->succ_next; |
199 | ||
d195b46f | 200 | fprintf (rtl_dump_file, " %s heuristics%s: %.1f%%", |
4db384c9 | 201 | predictor_info[predictor].name, |
bfdade77 | 202 | used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE); |
4db384c9 JH |
203 | |
204 | if (bb->count) | |
25c3a4ef | 205 | { |
35d6d8c1 | 206 | fprintf (rtl_dump_file, " exec "); |
bfdade77 | 207 | fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, bb->count); |
fbc2782e DD |
208 | if (e) |
209 | { | |
210 | fprintf (rtl_dump_file, " hit "); | |
211 | fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, e->count); | |
212 | fprintf (rtl_dump_file, " (%.1f%%)", e->count * 100.0 / bb->count); | |
213 | } | |
25c3a4ef | 214 | } |
bfdade77 | 215 | |
4db384c9 JH |
216 | fprintf (rtl_dump_file, "\n"); |
217 | } | |
218 | ||
219 | /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB | |
220 | note if not already present. Remove now useless REG_BR_PRED notes. */ | |
bfdade77 | 221 | |
4db384c9 JH |
222 | static void |
223 | combine_predictions_for_insn (insn, bb) | |
224 | rtx insn; | |
225 | basic_block bb; | |
226 | { | |
227 | rtx prob_note = find_reg_note (insn, REG_BR_PROB, 0); | |
228 | rtx *pnote = ®_NOTES (insn); | |
bfdade77 | 229 | rtx note; |
4db384c9 JH |
230 | int best_probability = PROB_EVEN; |
231 | int best_predictor = END_PREDICTORS; | |
134d3a2e JH |
232 | int combined_probability = REG_BR_PROB_BASE / 2; |
233 | int d; | |
d195b46f JH |
234 | bool first_match = false; |
235 | bool found = false; | |
4db384c9 JH |
236 | |
237 | if (rtl_dump_file) | |
44f49863 JH |
238 | fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn), |
239 | bb->index); | |
4db384c9 JH |
240 | |
241 | /* We implement "first match" heuristics and use probability guessed | |
57cb6d52 | 242 | by predictor with smallest index. In the future we will use better |
4db384c9 | 243 | probability combination techniques. */ |
bfdade77 RK |
244 | for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) |
245 | if (REG_NOTE_KIND (note) == REG_BR_PRED) | |
246 | { | |
247 | int predictor = INTVAL (XEXP (XEXP (note, 0), 0)); | |
248 | int probability = INTVAL (XEXP (XEXP (note, 0), 1)); | |
249 | ||
250 | found = true; | |
251 | if (best_predictor > predictor) | |
252 | best_probability = probability, best_predictor = predictor; | |
253 | ||
254 | d = (combined_probability * probability | |
255 | + (REG_BR_PROB_BASE - combined_probability) | |
256 | * (REG_BR_PROB_BASE - probability)); | |
257 | ||
258 | /* Use FP math to avoid overflows of 32bit integers. */ | |
571a03b8 JJ |
259 | if (d == 0) |
260 | /* If one probability is 0% and one 100%, avoid division by zero. */ | |
261 | combined_probability = REG_BR_PROB_BASE / 2; | |
262 | else | |
263 | combined_probability = (((double) combined_probability) * probability | |
264 | * REG_BR_PROB_BASE / d + 0.5); | |
bfdade77 RK |
265 | } |
266 | ||
267 | /* Decide which heuristic to use. In case we didn't match anything, | |
268 | use no_prediction heuristic, in case we did match, use either | |
d195b46f JH |
269 | first match or Dempster-Shaffer theory depending on the flags. */ |
270 | ||
134d3a2e | 271 | if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH) |
d195b46f JH |
272 | first_match = true; |
273 | ||
274 | if (!found) | |
275 | dump_prediction (PRED_NO_PREDICTION, combined_probability, bb, true); | |
276 | else | |
277 | { | |
bfdade77 | 278 | dump_prediction (PRED_DS_THEORY, combined_probability, bb, !first_match); |
d195b46f JH |
279 | dump_prediction (PRED_FIRST_MATCH, best_probability, bb, first_match); |
280 | } | |
281 | ||
282 | if (first_match) | |
134d3a2e | 283 | combined_probability = best_probability; |
d195b46f JH |
284 | dump_prediction (PRED_COMBINED, combined_probability, bb, true); |
285 | ||
286 | while (*pnote) | |
287 | { | |
288 | if (REG_NOTE_KIND (*pnote) == REG_BR_PRED) | |
289 | { | |
290 | int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0)); | |
291 | int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1)); | |
292 | ||
293 | dump_prediction (predictor, probability, bb, | |
294 | !first_match || best_predictor == predictor); | |
295 | *pnote = XEXP (*pnote, 1); | |
296 | } | |
297 | else | |
298 | pnote = &XEXP (*pnote, 1); | |
299 | } | |
bfdade77 | 300 | |
4db384c9 JH |
301 | if (!prob_note) |
302 | { | |
303 | REG_NOTES (insn) | |
304 | = gen_rtx_EXPR_LIST (REG_BR_PROB, | |
134d3a2e | 305 | GEN_INT (combined_probability), REG_NOTES (insn)); |
bfdade77 | 306 | |
134d3a2e JH |
307 | /* Save the prediction into CFG in case we are seeing non-degenerated |
308 | conditional jump. */ | |
309 | if (bb->succ->succ_next) | |
310 | { | |
311 | BRANCH_EDGE (bb)->probability = combined_probability; | |
bfdade77 RK |
312 | FALLTHRU_EDGE (bb)->probability |
313 | = REG_BR_PROB_BASE - combined_probability; | |
134d3a2e | 314 | } |
4db384c9 | 315 | } |
ee92cb46 JH |
316 | } |
317 | ||
f1ebdfc5 JE |
318 | /* Statically estimate the probability that a branch will be taken. |
319 | ??? In the next revision there will be a number of other predictors added | |
320 | from the above references. Further, each heuristic will be factored out | |
321 | into its own function for clarity (and to facilitate the combination of | |
65169dcf | 322 | predictions). */ |
f1ebdfc5 JE |
323 | |
324 | void | |
325 | estimate_probability (loops_info) | |
326 | struct loops *loops_info; | |
327 | { | |
0b92ff33 | 328 | sbitmap *dominators, *post_dominators; |
f1ebdfc5 | 329 | int i; |
c4f81e4a | 330 | int found_noreturn = 0; |
f1ebdfc5 | 331 | |
0b92ff33 JH |
332 | dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); |
333 | post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); | |
a4e11a5c GS |
334 | calculate_dominance_info (NULL, dominators, CDI_DOMINATORS); |
335 | calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS); | |
0b92ff33 | 336 | |
65169dcf JE |
337 | /* Try to predict out blocks in a loop that are not part of a |
338 | natural loop. */ | |
f1ebdfc5 JE |
339 | for (i = 0; i < loops_info->num; i++) |
340 | { | |
341 | int j; | |
0dd0e980 JH |
342 | int exits; |
343 | struct loop *loop = &loops_info->array[i]; | |
f1ebdfc5 | 344 | |
0dd0e980 JH |
345 | flow_loop_scan (loops_info, loop, LOOP_EXIT_EDGES); |
346 | exits = loop->num_exits; | |
347 | ||
bfdade77 RK |
348 | for (j = loop->first->index; j <= loop->last->index; ++j) |
349 | if (TEST_BIT (loop->nodes, j)) | |
350 | { | |
351 | int header_found = 0; | |
352 | edge e; | |
353 | ||
354 | /* Loop branch heuristics - predict an edge back to a | |
355 | loop's head as taken. */ | |
356 | for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next) | |
357 | if (e->dest == loop->header | |
358 | && e->src == loop->latch) | |
359 | { | |
360 | header_found = 1; | |
361 | predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN); | |
362 | } | |
363 | ||
364 | /* Loop exit heuristics - predict an edge exiting the loop if the | |
365 | conditinal has no loop header successors as not taken. */ | |
366 | if (!header_found) | |
ee92cb46 | 367 | for (e = BASIC_BLOCK(j)->succ; e; e = e->succ_next) |
bfdade77 RK |
368 | if (e->dest->index < 0 |
369 | || !TEST_BIT (loop->nodes, e->dest->index)) | |
370 | predict_edge | |
371 | (e, PRED_LOOP_EXIT, | |
372 | (REG_BR_PROB_BASE | |
cf403648 | 373 | - predictor_info [(int) PRED_LOOP_EXIT].hitrate) |
bfdade77 RK |
374 | / exits); |
375 | } | |
f1ebdfc5 JE |
376 | } |
377 | ||
134d3a2e | 378 | /* Attempt to predict conditional jumps using a number of heuristics. */ |
86e5b1b9 | 379 | for (i = 0; i < n_basic_blocks; i++) |
f1ebdfc5 | 380 | { |
0b92ff33 JH |
381 | basic_block bb = BASIC_BLOCK (i); |
382 | rtx last_insn = bb->end; | |
f1ebdfc5 | 383 | rtx cond, earliest; |
152897b1 | 384 | edge e; |
f1ebdfc5 | 385 | |
bfdade77 RK |
386 | /* If block has no successor, predict all possible paths to it as |
387 | improbable, as the block contains a call to a noreturn function and | |
388 | thus can be executed only once. */ | |
c4f81e4a | 389 | if (bb->succ == NULL && !found_noreturn) |
0b92ff33 JH |
390 | { |
391 | int y; | |
c4f81e4a JH |
392 | |
393 | /* ??? Postdominator claims each noreturn block to be postdominated | |
394 | by each, so we need to run only once. This needs to be changed | |
bfdade77 | 395 | once postdominace algorithm is updated to say something more |
23d1aac4 | 396 | sane. */ |
c4f81e4a | 397 | found_noreturn = 1; |
0b92ff33 JH |
398 | for (y = 0; y < n_basic_blocks; y++) |
399 | if (!TEST_BIT (post_dominators[y], i)) | |
bfdade77 | 400 | for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next) |
0b92ff33 JH |
401 | if (e->dest->index >= 0 |
402 | && TEST_BIT (post_dominators[e->dest->index], i)) | |
403 | predict_edge_def (e, PRED_NORETURN, NOT_TAKEN); | |
0b92ff33 JH |
404 | } |
405 | ||
bfdade77 | 406 | if (GET_CODE (last_insn) != JUMP_INSN || ! any_condjump_p (last_insn)) |
f1ebdfc5 | 407 | continue; |
9bcbfc52 | 408 | |
0b92ff33 JH |
409 | for (e = bb->succ; e; e = e->succ_next) |
410 | { | |
411 | /* Predict edges to blocks that return immediately to be | |
412 | improbable. These are usually used to signal error states. */ | |
413 | if (e->dest == EXIT_BLOCK_PTR | |
414 | || (e->dest->succ && !e->dest->succ->succ_next | |
415 | && e->dest->succ->dest == EXIT_BLOCK_PTR)) | |
416 | predict_edge_def (e, PRED_ERROR_RETURN, NOT_TAKEN); | |
417 | ||
418 | /* Look for block we are guarding (ie we dominate it, | |
419 | but it doesn't postdominate us). */ | |
bfdade77 | 420 | if (e->dest != EXIT_BLOCK_PTR && e->dest != bb |
0b92ff33 JH |
421 | && TEST_BIT (dominators[e->dest->index], e->src->index) |
422 | && !TEST_BIT (post_dominators[e->src->index], e->dest->index)) | |
423 | { | |
424 | rtx insn; | |
bfdade77 | 425 | |
0b92ff33 JH |
426 | /* The call heuristic claims that a guarded function call |
427 | is improbable. This is because such calls are often used | |
428 | to signal exceptional situations such as printing error | |
429 | messages. */ | |
430 | for (insn = e->dest->head; insn != NEXT_INSN (e->dest->end); | |
431 | insn = NEXT_INSN (insn)) | |
432 | if (GET_CODE (insn) == CALL_INSN | |
433 | /* Constant and pure calls are hardly used to signalize | |
434 | something exceptional. */ | |
24a28584 | 435 | && ! CONST_OR_PURE_CALL_P (insn)) |
0b92ff33 JH |
436 | { |
437 | predict_edge_def (e, PRED_CALL, NOT_TAKEN); | |
438 | break; | |
439 | } | |
440 | } | |
441 | } | |
ee92cb46 JH |
442 | |
443 | cond = get_condition (last_insn, &earliest); | |
444 | if (! cond) | |
445 | continue; | |
152897b1 | 446 | |
24c3bf68 JE |
447 | /* Try "pointer heuristic." |
448 | A comparison ptr == 0 is predicted as false. | |
449 | Similarly, a comparison ptr1 == ptr2 is predicted as false. */ | |
0dd0e980 JH |
450 | if (GET_RTX_CLASS (GET_CODE (cond)) == '<' |
451 | && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0))) | |
452 | || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1))))) | |
bfdade77 RK |
453 | { |
454 | if (GET_CODE (cond) == EQ) | |
4db384c9 | 455 | predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN); |
bfdade77 | 456 | else if (GET_CODE (cond) == NE) |
4db384c9 | 457 | predict_insn_def (last_insn, PRED_POINTER, TAKEN); |
bfdade77 | 458 | } |
0dd0e980 | 459 | else |
bfdade77 | 460 | |
24c3bf68 JE |
461 | /* Try "opcode heuristic." |
462 | EQ tests are usually false and NE tests are usually true. Also, | |
f1ebdfc5 JE |
463 | most quantities are positive, so we can make the appropriate guesses |
464 | about signed comparisons against zero. */ | |
0dd0e980 JH |
465 | switch (GET_CODE (cond)) |
466 | { | |
467 | case CONST_INT: | |
468 | /* Unconditional branch. */ | |
469 | predict_insn_def (last_insn, PRED_UNCONDITIONAL, | |
470 | cond == const0_rtx ? NOT_TAKEN : TAKEN); | |
471 | break; | |
472 | ||
473 | case EQ: | |
474 | case UNEQ: | |
475 | /* Floating point comparisons appears to behave in a very | |
476 | inpredictable way because of special role of = tests in | |
477 | FP code. */ | |
478 | if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) | |
479 | ; | |
480 | /* Comparisons with 0 are often used for booleans and there is | |
481 | nothing usefull to predict about them. */ | |
bfdade77 RK |
482 | else if (XEXP (cond, 1) == const0_rtx |
483 | || XEXP (cond, 0) == const0_rtx) | |
0dd0e980 JH |
484 | ; |
485 | else | |
486 | predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN); | |
487 | break; | |
bfdade77 | 488 | |
0dd0e980 JH |
489 | case NE: |
490 | case LTGT: | |
491 | /* Floating point comparisons appears to behave in a very | |
492 | inpredictable way because of special role of = tests in | |
493 | FP code. */ | |
494 | if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0)))) | |
495 | ; | |
496 | /* Comparisons with 0 are often used for booleans and there is | |
497 | nothing usefull to predict about them. */ | |
bfdade77 RK |
498 | else if (XEXP (cond, 1) == const0_rtx |
499 | || XEXP (cond, 0) == const0_rtx) | |
0dd0e980 JH |
500 | ; |
501 | else | |
502 | predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN); | |
503 | break; | |
bfdade77 | 504 | |
0dd0e980 JH |
505 | case ORDERED: |
506 | predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN); | |
507 | break; | |
bfdade77 | 508 | |
0dd0e980 JH |
509 | case UNORDERED: |
510 | predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN); | |
511 | break; | |
bfdade77 | 512 | |
0dd0e980 JH |
513 | case LE: |
514 | case LT: | |
515 | if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx | |
516 | || XEXP (cond, 1) == constm1_rtx) | |
517 | predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN); | |
518 | break; | |
bfdade77 | 519 | |
0dd0e980 JH |
520 | case GE: |
521 | case GT: | |
522 | if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx | |
523 | || XEXP (cond, 1) == constm1_rtx) | |
524 | predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN); | |
525 | break; | |
526 | ||
527 | default: | |
528 | break; | |
529 | } | |
f1ebdfc5 | 530 | } |
4db384c9 JH |
531 | |
532 | /* Attach the combined probability to each conditional jump. */ | |
86e5b1b9 | 533 | for (i = 0; i < n_basic_blocks; i++) |
bfdade77 RK |
534 | if (GET_CODE (BLOCK_END (i)) == JUMP_INSN |
535 | && any_condjump_p (BLOCK_END (i))) | |
536 | combine_predictions_for_insn (BLOCK_END (i), BASIC_BLOCK (i)); | |
4db384c9 | 537 | |
0b92ff33 JH |
538 | sbitmap_vector_free (post_dominators); |
539 | sbitmap_vector_free (dominators); | |
861f9cd0 JH |
540 | |
541 | estimate_bb_frequencies (loops_info); | |
f1ebdfc5 | 542 | } |
994a57cd | 543 | \f |
bfdade77 RK |
544 | /* __builtin_expect dropped tokens into the insn stream describing expected |
545 | values of registers. Generate branch probabilities based off these | |
546 | values. */ | |
f1ebdfc5 | 547 | |
994a57cd RH |
548 | void |
549 | expected_value_to_br_prob () | |
550 | { | |
36244024 | 551 | rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX; |
994a57cd RH |
552 | |
553 | for (insn = get_insns (); insn ; insn = NEXT_INSN (insn)) | |
554 | { | |
10f13594 RH |
555 | switch (GET_CODE (insn)) |
556 | { | |
557 | case NOTE: | |
558 | /* Look for expected value notes. */ | |
559 | if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE) | |
560 | { | |
561 | ev = NOTE_EXPECTED_VALUE (insn); | |
562 | ev_reg = XEXP (ev, 0); | |
49778644 | 563 | delete_insn (insn); |
10f13594 RH |
564 | } |
565 | continue; | |
566 | ||
567 | case CODE_LABEL: | |
568 | /* Never propagate across labels. */ | |
569 | ev = NULL_RTX; | |
570 | continue; | |
994a57cd | 571 | |
10f13594 | 572 | case JUMP_INSN: |
a1f300c0 | 573 | /* Look for simple conditional branches. If we haven't got an |
10f13594 | 574 | expected value yet, no point going further. */ |
bfdade77 RK |
575 | if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX |
576 | || ! any_condjump_p (insn)) | |
10f13594 RH |
577 | continue; |
578 | break; | |
bfdade77 RK |
579 | |
580 | default: | |
581 | /* Look for insns that clobber the EV register. */ | |
582 | if (ev && reg_set_p (ev_reg, insn)) | |
583 | ev = NULL_RTX; | |
584 | continue; | |
10f13594 RH |
585 | } |
586 | ||
587 | /* Collect the branch condition, hopefully relative to EV_REG. */ | |
d9490f2f RH |
588 | /* ??? At present we'll miss things like |
589 | (expected_value (eq r70 0)) | |
590 | (set r71 -1) | |
591 | (set r80 (lt r70 r71)) | |
592 | (set pc (if_then_else (ne r80 0) ...)) | |
57cb6d52 | 593 | as canonicalize_condition will render this to us as |
d9490f2f RH |
594 | (lt r70, r71) |
595 | Could use cselib to try and reduce this further. */ | |
24ee7cae | 596 | cond = XEXP (SET_SRC (pc_set (insn)), 0); |
10f13594 | 597 | cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg); |
bfdade77 | 598 | if (! cond || XEXP (cond, 0) != ev_reg |
d9490f2f | 599 | || GET_CODE (XEXP (cond, 1)) != CONST_INT) |
994a57cd RH |
600 | continue; |
601 | ||
57cb6d52 | 602 | /* Substitute and simplify. Given that the expression we're |
994a57cd RH |
603 | building involves two constants, we should wind up with either |
604 | true or false. */ | |
605 | cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode, | |
606 | XEXP (ev, 1), XEXP (cond, 1)); | |
607 | cond = simplify_rtx (cond); | |
608 | ||
609 | /* Turn the condition into a scaled branch probability. */ | |
1b28186a | 610 | if (cond != const_true_rtx && cond != const0_rtx) |
994a57cd | 611 | abort (); |
4db384c9 | 612 | predict_insn_def (insn, PRED_BUILTIN_EXPECT, |
1b28186a | 613 | cond == const_true_rtx ? TAKEN : NOT_TAKEN); |
994a57cd RH |
614 | } |
615 | } | |
861f9cd0 | 616 | \f |
57cb6d52 | 617 | /* This is used to carry information about basic blocks. It is |
861f9cd0 JH |
618 | attached to the AUX field of the standard CFG block. */ |
619 | ||
620 | typedef struct block_info_def | |
621 | { | |
622 | /* Estimated frequency of execution of basic_block. */ | |
7fcd7218 | 623 | volatile double frequency; |
861f9cd0 JH |
624 | |
625 | /* To keep queue of basic blocks to process. */ | |
626 | basic_block next; | |
627 | ||
247a370b JH |
628 | /* True if block needs to be visited in prop_freqency. */ |
629 | int tovisit:1; | |
630 | ||
eaec9b3d | 631 | /* Number of predecessors we need to visit first. */ |
754d9299 | 632 | int npredecessors; |
861f9cd0 JH |
633 | } *block_info; |
634 | ||
635 | /* Similar information for edges. */ | |
636 | typedef struct edge_info_def | |
637 | { | |
638 | /* In case edge is an loopback edge, the probability edge will be reached | |
639 | in case header is. Estimated number of iterations of the loop can be | |
7fcd7218 JH |
640 | then computed as 1 / (1 - back_edge_prob). |
641 | ||
642 | Volatile is needed to avoid differences in the optimized and unoptimized | |
643 | builds on machines where FP registers are wider than double. */ | |
644 | volatile double back_edge_prob; | |
861f9cd0 JH |
645 | /* True if the edge is an loopback edge in the natural loop. */ |
646 | int back_edge:1; | |
647 | } *edge_info; | |
648 | ||
649 | #define BLOCK_INFO(B) ((block_info) (B)->aux) | |
650 | #define EDGE_INFO(E) ((edge_info) (E)->aux) | |
651 | ||
652 | /* Helper function for estimate_bb_frequencies. | |
653 | Propagate the frequencies for loops headed by HEAD. */ | |
bfdade77 | 654 | |
861f9cd0 JH |
655 | static void |
656 | propagate_freq (head) | |
657 | basic_block head; | |
658 | { | |
659 | basic_block bb = head; | |
660 | basic_block last = bb; | |
661 | edge e; | |
662 | basic_block nextbb; | |
247a370b JH |
663 | int n; |
664 | ||
eaec9b3d | 665 | /* For each basic block we need to visit count number of his predecessors |
247a370b JH |
666 | we need to visit first. */ |
667 | for (n = 0; n < n_basic_blocks; n++) | |
668 | { | |
669 | basic_block bb = BASIC_BLOCK (n); | |
670 | if (BLOCK_INFO (bb)->tovisit) | |
671 | { | |
672 | int count = 0; | |
bfdade77 | 673 | |
247a370b JH |
674 | for (e = bb->pred; e; e = e->pred_next) |
675 | if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK)) | |
676 | count++; | |
677 | else if (BLOCK_INFO (e->src)->tovisit | |
678 | && rtl_dump_file && !EDGE_INFO (e)->back_edge) | |
679 | fprintf (rtl_dump_file, | |
680 | "Irreducible region hit, ignoring edge to %i->%i\n", | |
681 | e->src->index, bb->index); | |
754d9299 | 682 | BLOCK_INFO (bb)->npredecessors = count; |
247a370b JH |
683 | } |
684 | } | |
861f9cd0 JH |
685 | |
686 | BLOCK_INFO (head)->frequency = 1; | |
687 | for (; bb; bb = nextbb) | |
688 | { | |
bfdade77 | 689 | double cyclic_probability = 0, frequency = 0; |
861f9cd0 JH |
690 | |
691 | nextbb = BLOCK_INFO (bb)->next; | |
692 | BLOCK_INFO (bb)->next = NULL; | |
693 | ||
694 | /* Compute frequency of basic block. */ | |
695 | if (bb != head) | |
696 | { | |
247a370b | 697 | #ifdef ENABLE_CHECKING |
861f9cd0 | 698 | for (e = bb->pred; e; e = e->pred_next) |
247a370b JH |
699 | if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK)) |
700 | abort (); | |
701 | #endif | |
861f9cd0 JH |
702 | |
703 | for (e = bb->pred; e; e = e->pred_next) | |
704 | if (EDGE_INFO (e)->back_edge) | |
705 | cyclic_probability += EDGE_INFO (e)->back_edge_prob; | |
247a370b | 706 | else if (!(e->flags & EDGE_DFS_BACK)) |
861f9cd0 JH |
707 | frequency += (e->probability |
708 | * BLOCK_INFO (e->src)->frequency / | |
709 | REG_BR_PROB_BASE); | |
710 | ||
711 | if (cyclic_probability > 1.0 - 1.0 / REG_BR_PROB_BASE) | |
712 | cyclic_probability = 1.0 - 1.0 / REG_BR_PROB_BASE; | |
713 | ||
714 | BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability); | |
715 | } | |
716 | ||
247a370b | 717 | BLOCK_INFO (bb)->tovisit = 0; |
861f9cd0 JH |
718 | |
719 | /* Compute back edge frequencies. */ | |
720 | for (e = bb->succ; e; e = e->succ_next) | |
721 | if (e->dest == head) | |
bfdade77 RK |
722 | EDGE_INFO (e)->back_edge_prob |
723 | = ((e->probability * BLOCK_INFO (bb)->frequency) | |
724 | / REG_BR_PROB_BASE); | |
861f9cd0 | 725 | |
57cb6d52 | 726 | /* Propagate to successor blocks. */ |
861f9cd0 | 727 | for (e = bb->succ; e; e = e->succ_next) |
247a370b | 728 | if (!(e->flags & EDGE_DFS_BACK) |
754d9299 | 729 | && BLOCK_INFO (e->dest)->npredecessors) |
861f9cd0 | 730 | { |
754d9299 JM |
731 | BLOCK_INFO (e->dest)->npredecessors--; |
732 | if (!BLOCK_INFO (e->dest)->npredecessors) | |
247a370b JH |
733 | { |
734 | if (!nextbb) | |
735 | nextbb = e->dest; | |
736 | else | |
737 | BLOCK_INFO (last)->next = e->dest; | |
bfdade77 | 738 | |
247a370b JH |
739 | last = e->dest; |
740 | } | |
741 | } | |
861f9cd0 JH |
742 | } |
743 | } | |
744 | ||
57cb6d52 | 745 | /* Estimate probabilities of loopback edges in loops at same nest level. */ |
bfdade77 | 746 | |
861f9cd0 JH |
747 | static void |
748 | estimate_loops_at_level (first_loop) | |
749 | struct loop *first_loop; | |
750 | { | |
751 | struct loop *l, *loop = first_loop; | |
752 | ||
753 | for (loop = first_loop; loop; loop = loop->next) | |
754 | { | |
755 | int n; | |
756 | edge e; | |
757 | ||
758 | estimate_loops_at_level (loop->inner); | |
759 | ||
57cb6d52 | 760 | /* Find current loop back edge and mark it. */ |
bfdade77 RK |
761 | for (e = loop->latch->succ; e->dest != loop->header; e = e->succ_next) |
762 | ; | |
861f9cd0 JH |
763 | |
764 | EDGE_INFO (e)->back_edge = 1; | |
765 | ||
57cb6d52 AJ |
766 | /* In case the loop header is shared, ensure that it is the last |
767 | one sharing the same header, so we avoid redundant work. */ | |
861f9cd0 JH |
768 | if (loop->shared) |
769 | { | |
770 | for (l = loop->next; l; l = l->next) | |
771 | if (l->header == loop->header) | |
772 | break; | |
bfdade77 | 773 | |
861f9cd0 JH |
774 | if (l) |
775 | continue; | |
776 | } | |
777 | ||
778 | /* Now merge all nodes of all loops with given header as not visited. */ | |
779 | for (l = loop->shared ? first_loop : loop; l != loop->next; l = l->next) | |
780 | if (loop->header == l->header) | |
781 | EXECUTE_IF_SET_IN_SBITMAP (l->nodes, 0, n, | |
247a370b JH |
782 | BLOCK_INFO (BASIC_BLOCK (n))->tovisit = 1 |
783 | ); | |
bfdade77 | 784 | |
861f9cd0 JH |
785 | propagate_freq (loop->header); |
786 | } | |
787 | } | |
788 | ||
789 | /* Convert counts measured by profile driven feedback to frequencies. */ | |
bfdade77 | 790 | |
861f9cd0 JH |
791 | static void |
792 | counts_to_freqs () | |
793 | { | |
794 | HOST_WIDEST_INT count_max = 1; | |
795 | int i; | |
796 | ||
797 | for (i = 0; i < n_basic_blocks; i++) | |
bfdade77 | 798 | count_max = MAX (BASIC_BLOCK (i)->count, count_max); |
861f9cd0 JH |
799 | |
800 | for (i = -2; i < n_basic_blocks; i++) | |
801 | { | |
802 | basic_block bb; | |
bfdade77 | 803 | |
861f9cd0 JH |
804 | if (i == -2) |
805 | bb = ENTRY_BLOCK_PTR; | |
806 | else if (i == -1) | |
807 | bb = EXIT_BLOCK_PTR; | |
808 | else | |
809 | bb = BASIC_BLOCK (i); | |
bfdade77 RK |
810 | |
811 | bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max; | |
861f9cd0 JH |
812 | } |
813 | } | |
814 | ||
bfdade77 RK |
815 | /* Return true if function is likely to be expensive, so there is no point to |
816 | optimize performance of prologue, epilogue or do inlining at the expense | |
817 | of code size growth. THRESHOLD is the limit of number of isntructions | |
818 | function can execute at average to be still considered not expensive. */ | |
819 | ||
6ab16dd9 JH |
820 | bool |
821 | expensive_function_p (threshold) | |
822 | int threshold; | |
823 | { | |
824 | unsigned int sum = 0; | |
825 | int i; | |
5197bd50 | 826 | unsigned int limit; |
6ab16dd9 JH |
827 | |
828 | /* We can not compute accurately for large thresholds due to scaled | |
829 | frequencies. */ | |
830 | if (threshold > BB_FREQ_MAX) | |
831 | abort (); | |
832 | ||
eaec9b3d | 833 | /* Frequencies are out of range. This either means that function contains |
6ab16dd9 JH |
834 | internal loop executing more than BB_FREQ_MAX times or profile feedback |
835 | is available and function has not been executed at all. */ | |
836 | if (ENTRY_BLOCK_PTR->frequency == 0) | |
837 | return true; | |
838 | ||
839 | /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */ | |
840 | limit = ENTRY_BLOCK_PTR->frequency * threshold; | |
841 | for (i = 0; i < n_basic_blocks; i++) | |
842 | { | |
843 | basic_block bb = BASIC_BLOCK (i); | |
844 | rtx insn; | |
845 | ||
846 | for (insn = bb->head; insn != NEXT_INSN (bb->end); | |
847 | insn = NEXT_INSN (insn)) | |
bfdade77 RK |
848 | if (active_insn_p (insn)) |
849 | { | |
850 | sum += bb->frequency; | |
851 | if (sum > limit) | |
852 | return true; | |
6ab16dd9 JH |
853 | } |
854 | } | |
bfdade77 | 855 | |
6ab16dd9 JH |
856 | return false; |
857 | } | |
858 | ||
861f9cd0 | 859 | /* Estimate basic blocks frequency by given branch probabilities. */ |
bfdade77 | 860 | |
861f9cd0 JH |
861 | static void |
862 | estimate_bb_frequencies (loops) | |
863 | struct loops *loops; | |
864 | { | |
861f9cd0 JH |
865 | int i; |
866 | double freq_max = 0; | |
867 | ||
cc10816d | 868 | mark_dfs_back_edges (); |
861f9cd0 JH |
869 | if (flag_branch_probabilities) |
870 | { | |
871 | counts_to_freqs (); | |
872 | return; | |
873 | } | |
874 | ||
875 | /* Fill in the probability values in flowgraph based on the REG_BR_PROB | |
876 | notes. */ | |
877 | for (i = 0; i < n_basic_blocks; i++) | |
878 | { | |
879 | rtx last_insn = BLOCK_END (i); | |
861f9cd0 | 880 | |
25c3a4ef | 881 | if (GET_CODE (last_insn) != JUMP_INSN || !any_condjump_p (last_insn) |
57cb6d52 | 882 | /* Avoid handling of conditional jumps jumping to fallthru edge. */ |
25c3a4ef | 883 | || BASIC_BLOCK (i)->succ->succ_next == NULL) |
861f9cd0 JH |
884 | { |
885 | /* We can predict only conditional jumps at the moment. | |
57cb6d52 AJ |
886 | Expect each edge to be equally probable. |
887 | ?? In the future we want to make abnormal edges improbable. */ | |
861f9cd0 JH |
888 | int nedges = 0; |
889 | edge e; | |
890 | ||
891 | for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next) | |
892 | { | |
893 | nedges++; | |
894 | if (e->probability != 0) | |
895 | break; | |
896 | } | |
897 | if (!e) | |
898 | for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next) | |
899 | e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges; | |
900 | } | |
861f9cd0 | 901 | } |
bfdade77 | 902 | |
861f9cd0 JH |
903 | ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE; |
904 | ||
905 | /* Set up block info for each basic block. */ | |
ca6c03ca JH |
906 | alloc_aux_for_blocks (sizeof (struct block_info_def)); |
907 | alloc_aux_for_edges (sizeof (struct edge_info_def)); | |
861f9cd0 JH |
908 | for (i = -2; i < n_basic_blocks; i++) |
909 | { | |
910 | edge e; | |
911 | basic_block bb; | |
912 | ||
913 | if (i == -2) | |
914 | bb = ENTRY_BLOCK_PTR; | |
915 | else if (i == -1) | |
916 | bb = EXIT_BLOCK_PTR; | |
917 | else | |
918 | bb = BASIC_BLOCK (i); | |
bfdade77 | 919 | |
247a370b | 920 | BLOCK_INFO (bb)->tovisit = 0; |
861f9cd0 | 921 | for (e = bb->succ; e; e = e->succ_next) |
ca6c03ca JH |
922 | EDGE_INFO (e)->back_edge_prob = ((double) e->probability |
923 | / REG_BR_PROB_BASE); | |
861f9cd0 | 924 | } |
bfdade77 | 925 | |
861f9cd0 JH |
926 | /* First compute probabilities locally for each loop from innermost |
927 | to outermost to examine probabilities for back edges. */ | |
2b1d9dc0 | 928 | estimate_loops_at_level (loops->tree_root); |
861f9cd0 JH |
929 | |
930 | /* Now fake loop around whole function to finalize probabilities. */ | |
931 | for (i = 0; i < n_basic_blocks; i++) | |
247a370b | 932 | BLOCK_INFO (BASIC_BLOCK (i))->tovisit = 1; |
bfdade77 | 933 | |
247a370b JH |
934 | BLOCK_INFO (ENTRY_BLOCK_PTR)->tovisit = 1; |
935 | BLOCK_INFO (EXIT_BLOCK_PTR)->tovisit = 1; | |
861f9cd0 JH |
936 | propagate_freq (ENTRY_BLOCK_PTR); |
937 | ||
938 | for (i = 0; i < n_basic_blocks; i++) | |
939 | if (BLOCK_INFO (BASIC_BLOCK (i))->frequency > freq_max) | |
940 | freq_max = BLOCK_INFO (BASIC_BLOCK (i))->frequency; | |
bfdade77 | 941 | |
861f9cd0 JH |
942 | for (i = -2; i < n_basic_blocks; i++) |
943 | { | |
944 | basic_block bb; | |
39002160 | 945 | volatile double tmp; |
bfdade77 | 946 | |
861f9cd0 JH |
947 | if (i == -2) |
948 | bb = ENTRY_BLOCK_PTR; | |
949 | else if (i == -1) | |
950 | bb = EXIT_BLOCK_PTR; | |
951 | else | |
952 | bb = BASIC_BLOCK (i); | |
39002160 RH |
953 | |
954 | /* ??? Prevent rounding differences due to optimization on x86. */ | |
955 | tmp = BLOCK_INFO (bb)->frequency * BB_FREQ_MAX; | |
956 | tmp /= freq_max; | |
957 | tmp += 0.5; | |
958 | bb->frequency = tmp; | |
861f9cd0 JH |
959 | } |
960 | ||
ca6c03ca JH |
961 | free_aux_for_blocks (); |
962 | free_aux_for_edges (); | |
861f9cd0 | 963 | } |