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