Branch data Line data Source code
1 : : /* Branch prediction routines for the GNU compiler.
2 : : Copyright (C) 2000-2024 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 : : /* References:
21 : :
22 : : [1] "Branch Prediction for Free"
23 : : Ball and Larus; PLDI '93.
24 : : [2] "Static Branch Frequency and Program Profile Analysis"
25 : : Wu and Larus; MICRO-27.
26 : : [3] "Corpus-based Static Branch Prediction"
27 : : Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
28 : :
29 : :
30 : : #include "config.h"
31 : : #include "system.h"
32 : : #include "coretypes.h"
33 : : #include "backend.h"
34 : : #include "rtl.h"
35 : : #include "tree.h"
36 : : #include "gimple.h"
37 : : #include "cfghooks.h"
38 : : #include "tree-pass.h"
39 : : #include "ssa.h"
40 : : #include "memmodel.h"
41 : : #include "emit-rtl.h"
42 : : #include "cgraph.h"
43 : : #include "coverage.h"
44 : : #include "diagnostic-core.h"
45 : : #include "gimple-predict.h"
46 : : #include "fold-const.h"
47 : : #include "calls.h"
48 : : #include "cfganal.h"
49 : : #include "profile.h"
50 : : #include "sreal.h"
51 : : #include "cfgloop.h"
52 : : #include "gimple-iterator.h"
53 : : #include "tree-cfg.h"
54 : : #include "tree-ssa-loop-niter.h"
55 : : #include "tree-ssa-loop.h"
56 : : #include "tree-scalar-evolution.h"
57 : : #include "ipa-utils.h"
58 : : #include "gimple-pretty-print.h"
59 : : #include "selftest.h"
60 : : #include "cfgrtl.h"
61 : : #include "stringpool.h"
62 : : #include "attribs.h"
63 : :
64 : : /* Enum with reasons why a predictor is ignored. */
65 : :
66 : : enum predictor_reason
67 : : {
68 : : REASON_NONE,
69 : : REASON_IGNORED,
70 : : REASON_SINGLE_EDGE_DUPLICATE,
71 : : REASON_EDGE_PAIR_DUPLICATE
72 : : };
73 : :
74 : : /* String messages for the aforementioned enum. */
75 : :
76 : : static const char *reason_messages[] = {"", " (ignored)",
77 : : " (single edge duplicate)", " (edge pair duplicate)"};
78 : :
79 : :
80 : : static void combine_predictions_for_insn (rtx_insn *, basic_block);
81 : : static void dump_prediction (FILE *, enum br_predictor, int, basic_block,
82 : : enum predictor_reason, edge);
83 : : static void predict_paths_leading_to (basic_block, enum br_predictor,
84 : : enum prediction,
85 : : class loop *in_loop = NULL);
86 : : static void predict_paths_leading_to_edge (edge, enum br_predictor,
87 : : enum prediction,
88 : : class loop *in_loop = NULL);
89 : : static bool can_predict_insn_p (const rtx_insn *);
90 : : static HOST_WIDE_INT get_predictor_value (br_predictor, HOST_WIDE_INT);
91 : : static void determine_unlikely_bbs ();
92 : : static void estimate_bb_frequencies ();
93 : :
94 : : /* Information we hold about each branch predictor.
95 : : Filled using information from predict.def. */
96 : :
97 : : struct predictor_info
98 : : {
99 : : const char *const name; /* Name used in the debugging dumps. */
100 : : const int hitrate; /* Expected hitrate used by
101 : : predict_insn_def call. */
102 : : const int flags;
103 : : };
104 : :
105 : : /* Use given predictor without Dempster-Shaffer theory if it matches
106 : : using first_match heuristics. */
107 : : #define PRED_FLAG_FIRST_MATCH 1
108 : :
109 : : /* Recompute hitrate in percent to our representation. */
110 : :
111 : : #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
112 : :
113 : : #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
114 : : static const struct predictor_info predictor_info[]= {
115 : : #include "predict.def"
116 : :
117 : : /* Upper bound on predictors. */
118 : : {NULL, 0, 0}
119 : : };
120 : : #undef DEF_PREDICTOR
121 : :
122 : : static gcov_type min_count = -1;
123 : :
124 : : /* Determine the threshold for hot BB counts. */
125 : :
126 : : gcov_type
127 : 49966 : get_hot_bb_threshold ()
128 : : {
129 : 49966 : if (min_count == -1)
130 : : {
131 : 93 : const int hot_frac = param_hot_bb_count_fraction;
132 : 186 : const gcov_type min_hot_count
133 : : = hot_frac
134 : 93 : ? profile_info->sum_max / hot_frac
135 : : : (gcov_type)profile_count::max_count;
136 : 93 : set_hot_bb_threshold (min_hot_count);
137 : 93 : if (dump_file)
138 : 18 : fprintf (dump_file, "Setting hotness threshold to %" PRId64 ".\n",
139 : : min_hot_count);
140 : : }
141 : 49966 : return min_count;
142 : : }
143 : :
144 : : /* Set the threshold for hot BB counts. */
145 : :
146 : : void
147 : 222 : set_hot_bb_threshold (gcov_type min)
148 : : {
149 : 222 : min_count = min;
150 : 222 : }
151 : :
152 : : /* Return TRUE if COUNT is considered to be hot in function FUN. */
153 : :
154 : : bool
155 : 822876595 : maybe_hot_count_p (struct function *fun, profile_count count)
156 : : {
157 : 822876595 : if (!count.initialized_p ())
158 : : return true;
159 : 730485039 : if (count.ipa () == profile_count::zero ())
160 : 4198664 : return false;
161 : 726286375 : if (!count.ipa_p ())
162 : : {
163 : 726200515 : struct cgraph_node *node = cgraph_node::get (fun->decl);
164 : 726200515 : if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
165 : : {
166 : 726200515 : if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
167 : : return false;
168 : 726164494 : if (node->frequency == NODE_FREQUENCY_HOT)
169 : : return true;
170 : : }
171 : 726161099 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
172 : : return true;
173 : 725966793 : if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
174 : 725966793 : && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
175 : 14571368 : return false;
176 : 711395425 : if (count * param_hot_bb_frequency_fraction
177 : 711395425 : < ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
178 : : return false;
179 : : return true;
180 : : }
181 : : /* Code executed at most once is not hot. */
182 : 85860 : if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
183 : : return false;
184 : 49799 : return (count >= get_hot_bb_threshold ());
185 : : }
186 : :
187 : : /* Return true if basic block BB of function FUN can be CPU intensive
188 : : and should thus be optimized for maximum performance. */
189 : :
190 : : bool
191 : 809420818 : maybe_hot_bb_p (struct function *fun, const_basic_block bb)
192 : : {
193 : 809420818 : gcc_checking_assert (fun);
194 : 809420818 : return maybe_hot_count_p (fun, bb->count);
195 : : }
196 : :
197 : : /* Return true if edge E can be CPU intensive and should thus be optimized
198 : : for maximum performance. */
199 : :
200 : : bool
201 : 8245420 : maybe_hot_edge_p (edge e)
202 : : {
203 : 8245420 : return maybe_hot_count_p (cfun, e->count ());
204 : : }
205 : :
206 : : /* Return true if COUNT is considered to be never executed in function FUN
207 : : or if function FUN is considered so in the static profile. */
208 : :
209 : : static bool
210 : 46213414 : probably_never_executed (struct function *fun, profile_count count)
211 : : {
212 : 46213414 : gcc_checking_assert (fun);
213 : 46213414 : if (count.ipa () == profile_count::zero ())
214 : 1421670 : return true;
215 : : /* Do not trust adjusted counts. This will make us to drop int cold section
216 : : code with low execution count as a result of inlining. These low counts
217 : : are not safe even with read profile and may lead us to dropping
218 : : code which actually gets executed into cold section of binary that is not
219 : : desirable. */
220 : 44791744 : if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
221 : : {
222 : 3404 : const int unlikely_frac = param_unlikely_bb_count_fraction;
223 : 3404 : if (count * unlikely_frac >= profile_info->runs)
224 : : return false;
225 : : return true;
226 : : }
227 : 2765 : if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
228 : 44788448 : && (cgraph_node::get (fun->decl)->frequency
229 : 44785683 : == NODE_FREQUENCY_UNLIKELY_EXECUTED))
230 : : return true;
231 : : return false;
232 : : }
233 : :
234 : : /* Return true if basic block BB of function FUN is probably never executed. */
235 : :
236 : : bool
237 : 15776877 : probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
238 : : {
239 : 15776877 : return probably_never_executed (fun, bb->count);
240 : : }
241 : :
242 : : /* Return true if edge E is unlikely executed for obvious reasons. */
243 : :
244 : : static bool
245 : 94355809 : unlikely_executed_edge_p (edge e)
246 : : {
247 : 95426316 : return (e->src->count == profile_count::zero ()
248 : 92789023 : || e->probability == profile_probability::never ())
249 : 87825654 : || (e->flags & (EDGE_EH | EDGE_FAKE));
250 : : }
251 : :
252 : : /* Return true if edge E of function FUN is probably never executed. */
253 : :
254 : : bool
255 : 32800281 : probably_never_executed_edge_p (struct function *fun, edge e)
256 : : {
257 : 32800281 : if (unlikely_executed_edge_p (e))
258 : : return true;
259 : 30436537 : return probably_never_executed (fun, e->count ());
260 : : }
261 : :
262 : : /* Return true if function FUN should always be optimized for size. */
263 : :
264 : : optimize_size_level
265 : 2030626925 : optimize_function_for_size_p (struct function *fun)
266 : : {
267 : 2030626925 : if (!fun || !fun->decl)
268 : 192997002 : return optimize_size ? OPTIMIZE_SIZE_MAX : OPTIMIZE_SIZE_NO;
269 : 1930904024 : cgraph_node *n = cgraph_node::get (fun->decl);
270 : 1930904024 : if (n)
271 : 1891682871 : return n->optimize_for_size_p ();
272 : : return OPTIMIZE_SIZE_NO;
273 : : }
274 : :
275 : : /* Return true if function FUN should always be optimized for speed. */
276 : :
277 : : bool
278 : 208795303 : optimize_function_for_speed_p (struct function *fun)
279 : : {
280 : 208795303 : return !optimize_function_for_size_p (fun);
281 : : }
282 : :
283 : : /* Return the optimization type that should be used for function FUN. */
284 : :
285 : : optimization_type
286 : 0 : function_optimization_type (struct function *fun)
287 : : {
288 : 0 : return (optimize_function_for_speed_p (fun)
289 : 0 : ? OPTIMIZE_FOR_SPEED
290 : 0 : : OPTIMIZE_FOR_SIZE);
291 : : }
292 : :
293 : : /* Return TRUE if basic block BB should be optimized for size. */
294 : :
295 : : optimize_size_level
296 : 783649824 : optimize_bb_for_size_p (const_basic_block bb)
297 : : {
298 : 783649824 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
299 : :
300 : 1559714350 : if (bb && ret < OPTIMIZE_SIZE_MAX && bb->count == profile_count::zero ())
301 : 19415442 : ret = OPTIMIZE_SIZE_MAX;
302 : 783649824 : if (bb && ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_bb_p (cfun, bb))
303 : : ret = OPTIMIZE_SIZE_BALANCED;
304 : 783649824 : return ret;
305 : : }
306 : :
307 : : /* Return TRUE if basic block BB should be optimized for speed. */
308 : :
309 : : bool
310 : 726940571 : optimize_bb_for_speed_p (const_basic_block bb)
311 : : {
312 : 726940571 : return !optimize_bb_for_size_p (bb);
313 : : }
314 : :
315 : : /* Return the optimization type that should be used for basic block BB. */
316 : :
317 : : optimization_type
318 : 4523350 : bb_optimization_type (const_basic_block bb)
319 : : {
320 : 4523350 : return (optimize_bb_for_speed_p (bb)
321 : 4523350 : ? OPTIMIZE_FOR_SPEED
322 : 4523350 : : OPTIMIZE_FOR_SIZE);
323 : : }
324 : :
325 : : /* Return TRUE if edge E should be optimized for size. */
326 : :
327 : : optimize_size_level
328 : 8853576 : optimize_edge_for_size_p (edge e)
329 : : {
330 : 8853576 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
331 : :
332 : 8853576 : if (ret < OPTIMIZE_SIZE_MAX && unlikely_executed_edge_p (e))
333 : : ret = OPTIMIZE_SIZE_MAX;
334 : 8420907 : if (ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_edge_p (e))
335 : : ret = OPTIMIZE_SIZE_BALANCED;
336 : 8853576 : return ret;
337 : : }
338 : :
339 : : /* Return TRUE if edge E should be optimized for speed. */
340 : :
341 : : bool
342 : 3674430 : optimize_edge_for_speed_p (edge e)
343 : : {
344 : 3674430 : return !optimize_edge_for_size_p (e);
345 : : }
346 : :
347 : : /* Return TRUE if the current function is optimized for size. */
348 : :
349 : : optimize_size_level
350 : 201438027 : optimize_insn_for_size_p (void)
351 : : {
352 : 201438027 : enum optimize_size_level ret = optimize_function_for_size_p (cfun);
353 : 201438027 : if (ret < OPTIMIZE_SIZE_BALANCED && !crtl->maybe_hot_insn_p)
354 : 201438027 : ret = OPTIMIZE_SIZE_BALANCED;
355 : 201438027 : return ret;
356 : : }
357 : :
358 : : /* Return TRUE if the current function is optimized for speed. */
359 : :
360 : : bool
361 : 78438630 : optimize_insn_for_speed_p (void)
362 : : {
363 : 78438630 : return !optimize_insn_for_size_p ();
364 : : }
365 : :
366 : : /* Return the optimization type that should be used for the current
367 : : instruction. */
368 : :
369 : : optimization_type
370 : 3892 : insn_optimization_type ()
371 : : {
372 : 3892 : return (optimize_insn_for_speed_p ()
373 : 3892 : ? OPTIMIZE_FOR_SPEED
374 : 3892 : : OPTIMIZE_FOR_SIZE);
375 : : }
376 : :
377 : : /* Return TRUE if LOOP should be optimized for size. */
378 : :
379 : : optimize_size_level
380 : 636321 : optimize_loop_for_size_p (class loop *loop)
381 : : {
382 : 636321 : return optimize_bb_for_size_p (loop->header);
383 : : }
384 : :
385 : : /* Return TRUE if LOOP should be optimized for speed. */
386 : :
387 : : bool
388 : 13003034 : optimize_loop_for_speed_p (class loop *loop)
389 : : {
390 : 13003034 : return optimize_bb_for_speed_p (loop->header);
391 : : }
392 : :
393 : : /* Return TRUE if nest rooted at LOOP should be optimized for speed. */
394 : :
395 : : bool
396 : 845244 : optimize_loop_nest_for_speed_p (class loop *loop)
397 : : {
398 : 845244 : class loop *l = loop;
399 : 845244 : if (optimize_loop_for_speed_p (loop))
400 : : return true;
401 : 32888 : l = loop->inner;
402 : 44857 : while (l && l != loop)
403 : : {
404 : 13281 : if (optimize_loop_for_speed_p (l))
405 : : return true;
406 : 11969 : if (l->inner)
407 : : l = l->inner;
408 : 7895 : else if (l->next)
409 : : l = l->next;
410 : : else
411 : : {
412 : 19117 : while (l != loop && !l->next)
413 : 11439 : l = loop_outer (l);
414 : 7678 : if (l != loop)
415 : 49 : l = l->next;
416 : : }
417 : : }
418 : : return false;
419 : : }
420 : :
421 : : /* Return TRUE if nest rooted at LOOP should be optimized for size. */
422 : :
423 : : optimize_size_level
424 : 13831 : optimize_loop_nest_for_size_p (class loop *loop)
425 : : {
426 : 13831 : enum optimize_size_level ret = optimize_loop_for_size_p (loop);
427 : 13831 : class loop *l = loop;
428 : :
429 : 13831 : l = loop->inner;
430 : 14098 : while (l && l != loop)
431 : : {
432 : 13333 : if (ret == OPTIMIZE_SIZE_NO)
433 : : break;
434 : 267 : ret = MIN (optimize_loop_for_size_p (l), ret);
435 : 267 : if (l->inner)
436 : : l = l->inner;
437 : 258 : else if (l->next)
438 : : l = l->next;
439 : : else
440 : : {
441 : 305 : while (l != loop && !l->next)
442 : 155 : l = loop_outer (l);
443 : 150 : if (l != loop)
444 : 4 : l = l->next;
445 : : }
446 : : }
447 : 13831 : return ret;
448 : : }
449 : :
450 : : /* Return true if edge E is likely to be well predictable by branch
451 : : predictor. */
452 : :
453 : : bool
454 : 5429811 : predictable_edge_p (edge e)
455 : : {
456 : 5429811 : if (!e->probability.initialized_p ())
457 : : return false;
458 : 5429038 : if ((e->probability.to_reg_br_prob_base ()
459 : 5429038 : <= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100)
460 : 5429038 : || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
461 : : <= param_predictable_branch_outcome * REG_BR_PROB_BASE / 100))
462 : 615021 : return true;
463 : : return false;
464 : : }
465 : :
466 : :
467 : : /* Set RTL expansion for BB profile. */
468 : :
469 : : void
470 : 72451143 : rtl_profile_for_bb (basic_block bb)
471 : : {
472 : 72451143 : crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
473 : 72451143 : }
474 : :
475 : : /* Set RTL expansion for edge profile. */
476 : :
477 : : void
478 : 9794 : rtl_profile_for_edge (edge e)
479 : : {
480 : 9794 : crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
481 : 9794 : }
482 : :
483 : : /* Set RTL expansion to default mode (i.e. when profile info is not known). */
484 : : void
485 : 13585369 : default_rtl_profile (void)
486 : : {
487 : 13585369 : crtl->maybe_hot_insn_p = true;
488 : 13585369 : }
489 : :
490 : : /* Return true if the one of outgoing edges is already predicted by
491 : : PREDICTOR. */
492 : :
493 : : bool
494 : 0 : rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
495 : : {
496 : 0 : rtx note;
497 : 0 : if (!INSN_P (BB_END (bb)))
498 : : return false;
499 : 0 : for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
500 : 0 : if (REG_NOTE_KIND (note) == REG_BR_PRED
501 : 0 : && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
502 : : return true;
503 : : return false;
504 : : }
505 : :
506 : : /* Structure representing predictions in tree level. */
507 : :
508 : : struct edge_prediction {
509 : : struct edge_prediction *ep_next;
510 : : edge ep_edge;
511 : : enum br_predictor ep_predictor;
512 : : int ep_probability;
513 : : };
514 : :
515 : : /* This map contains for a basic block the list of predictions for the
516 : : outgoing edges. */
517 : :
518 : : static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
519 : :
520 : : /* Return true if the one of outgoing edges is already predicted by
521 : : PREDICTOR. */
522 : :
523 : : bool
524 : 2895689 : gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
525 : : {
526 : 2895689 : struct edge_prediction *i;
527 : 2895689 : edge_prediction **preds = bb_predictions->get (bb);
528 : :
529 : 2895689 : if (!preds)
530 : : return false;
531 : :
532 : 1429111 : for (i = *preds; i; i = i->ep_next)
533 : 741924 : if (i->ep_predictor == predictor)
534 : : return true;
535 : : return false;
536 : : }
537 : :
538 : : /* Return true if the one of outgoing edges is already predicted by
539 : : PREDICTOR for edge E predicted as TAKEN. */
540 : :
541 : : bool
542 : 1024834 : edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
543 : : {
544 : 1024834 : struct edge_prediction *i;
545 : 1024834 : basic_block bb = e->src;
546 : 1024834 : edge_prediction **preds = bb_predictions->get (bb);
547 : 1024834 : if (!preds)
548 : : return false;
549 : :
550 : 127656 : int probability = predictor_info[(int) predictor].hitrate;
551 : :
552 : 127656 : if (taken != TAKEN)
553 : 127470 : probability = REG_BR_PROB_BASE - probability;
554 : :
555 : 4821114 : for (i = *preds; i; i = i->ep_next)
556 : 4697176 : if (i->ep_predictor == predictor
557 : 4572025 : && i->ep_edge == e
558 : 3718 : && i->ep_probability == probability)
559 : : return true;
560 : : return false;
561 : : }
562 : :
563 : : /* Same predicate as above, working on edges. */
564 : : bool
565 : 0 : edge_probability_reliable_p (const_edge e)
566 : : {
567 : 0 : return e->probability.probably_reliable_p ();
568 : : }
569 : :
570 : : /* Same predicate as edge_probability_reliable_p, working on notes. */
571 : : bool
572 : 0 : br_prob_note_reliable_p (const_rtx note)
573 : : {
574 : 0 : gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
575 : 0 : return profile_probability::from_reg_br_prob_note
576 : 0 : (XINT (note, 0)).probably_reliable_p ();
577 : : }
578 : :
579 : : static void
580 : 68708 : predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
581 : : {
582 : 68708 : gcc_assert (any_condjump_p (insn));
583 : 68708 : if (!flag_guess_branch_prob)
584 : : return;
585 : :
586 : 137336 : add_reg_note (insn, REG_BR_PRED,
587 : 68668 : gen_rtx_CONCAT (VOIDmode,
588 : : GEN_INT ((int) predictor),
589 : : GEN_INT ((int) probability)));
590 : : }
591 : :
592 : : /* Predict insn by given predictor. */
593 : :
594 : : void
595 : 68708 : predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
596 : : enum prediction taken)
597 : : {
598 : 68708 : int probability = predictor_info[(int) predictor].hitrate;
599 : 68708 : gcc_assert (probability != PROB_UNINITIALIZED);
600 : :
601 : 68708 : if (taken != TAKEN)
602 : 5813 : probability = REG_BR_PROB_BASE - probability;
603 : :
604 : 68708 : predict_insn (insn, predictor, probability);
605 : 68708 : }
606 : :
607 : : /* Predict edge E with given probability if possible. */
608 : :
609 : : void
610 : 0 : rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
611 : : {
612 : 0 : rtx_insn *last_insn;
613 : 0 : last_insn = BB_END (e->src);
614 : :
615 : : /* We can store the branch prediction information only about
616 : : conditional jumps. */
617 : 0 : if (!any_condjump_p (last_insn))
618 : : return;
619 : :
620 : : /* We always store probability of branching. */
621 : 0 : if (e->flags & EDGE_FALLTHRU)
622 : 0 : probability = REG_BR_PROB_BASE - probability;
623 : :
624 : 0 : predict_insn (last_insn, predictor, probability);
625 : : }
626 : :
627 : : /* Predict edge E with the given PROBABILITY. */
628 : : void
629 : 5651724 : gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
630 : : {
631 : 5651724 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
632 : 5651724 : && EDGE_COUNT (e->src->succs) > 1
633 : 5651724 : && flag_guess_branch_prob
634 : 11303448 : && optimize)
635 : : {
636 : 5651724 : struct edge_prediction *i = XNEW (struct edge_prediction);
637 : 5651724 : edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
638 : :
639 : 5651724 : i->ep_next = preds;
640 : 5651724 : preds = i;
641 : 5651724 : i->ep_probability = probability;
642 : 5651724 : i->ep_predictor = predictor;
643 : 5651724 : i->ep_edge = e;
644 : : }
645 : 5651724 : }
646 : :
647 : : /* Filter edge predictions PREDS by a function FILTER: if FILTER return false
648 : : the prediction is removed.
649 : : DATA are passed to the filter function. */
650 : :
651 : : static void
652 : 2601326 : filter_predictions (edge_prediction **preds,
653 : : bool (*filter) (edge_prediction *, void *), void *data)
654 : : {
655 : 2601326 : if (!bb_predictions)
656 : : return;
657 : :
658 : 2601326 : if (preds)
659 : : {
660 : : struct edge_prediction **prediction = preds;
661 : : struct edge_prediction *next;
662 : :
663 : 7171178 : while (*prediction)
664 : : {
665 : 4569852 : if ((*filter) (*prediction, data))
666 : 4131113 : prediction = &((*prediction)->ep_next);
667 : : else
668 : : {
669 : 438739 : next = (*prediction)->ep_next;
670 : 438739 : free (*prediction);
671 : 438739 : *prediction = next;
672 : : }
673 : : }
674 : : }
675 : : }
676 : :
677 : : /* Filter function predicate that returns true for a edge predicate P
678 : : if its edge is equal to DATA. */
679 : :
680 : : static bool
681 : 0 : not_equal_edge_p (edge_prediction *p, void *data)
682 : : {
683 : 0 : return p->ep_edge != (edge)data;
684 : : }
685 : :
686 : : /* Remove all predictions on given basic block that are attached
687 : : to edge E. */
688 : : void
689 : 72432388 : remove_predictions_associated_with_edge (edge e)
690 : : {
691 : 72432388 : if (!bb_predictions)
692 : : return;
693 : :
694 : 0 : edge_prediction **preds = bb_predictions->get (e->src);
695 : 0 : filter_predictions (preds, not_equal_edge_p, e);
696 : : }
697 : :
698 : : /* Clears the list of predictions stored for BB. */
699 : :
700 : : static void
701 : 10416415 : clear_bb_predictions (basic_block bb)
702 : : {
703 : 10416415 : edge_prediction **preds = bb_predictions->get (bb);
704 : 10416415 : struct edge_prediction *pred, *next;
705 : :
706 : 10416415 : if (!preds)
707 : : return;
708 : :
709 : 8496990 : for (pred = *preds; pred; pred = next)
710 : : {
711 : 5212985 : next = pred->ep_next;
712 : 5212985 : free (pred);
713 : : }
714 : 3284005 : *preds = NULL;
715 : : }
716 : :
717 : : /* Return true when we can store prediction on insn INSN.
718 : : At the moment we represent predictions only on conditional
719 : : jumps, not at computed jump or other complicated cases. */
720 : : static bool
721 : 978028 : can_predict_insn_p (const rtx_insn *insn)
722 : : {
723 : 978028 : return (JUMP_P (insn)
724 : 224894 : && any_condjump_p (insn)
725 : 1202424 : && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
726 : : }
727 : :
728 : : /* Predict edge E by given predictor if possible. */
729 : :
730 : : void
731 : 4627401 : predict_edge_def (edge e, enum br_predictor predictor,
732 : : enum prediction taken)
733 : : {
734 : 4627401 : int probability = predictor_info[(int) predictor].hitrate;
735 : :
736 : 4627401 : if (taken != TAKEN)
737 : 3698184 : probability = REG_BR_PROB_BASE - probability;
738 : :
739 : 4627401 : predict_edge (e, predictor, probability);
740 : 4627401 : }
741 : :
742 : : /* Invert all branch predictions or probability notes in the INSN. This needs
743 : : to be done each time we invert the condition used by the jump. */
744 : :
745 : : void
746 : 11470066 : invert_br_probabilities (rtx insn)
747 : : {
748 : 11470066 : rtx note;
749 : :
750 : 33898640 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
751 : 22428574 : if (REG_NOTE_KIND (note) == REG_BR_PROB)
752 : 22793508 : XINT (note, 0) = profile_probability::from_reg_br_prob_note
753 : 11396754 : (XINT (note, 0)).invert ().to_reg_br_prob_note ();
754 : 11031820 : else if (REG_NOTE_KIND (note) == REG_BR_PRED)
755 : 0 : XEXP (XEXP (note, 0), 1)
756 : 0 : = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
757 : 11470066 : }
758 : :
759 : : /* Dump information about the branch prediction to the output file. */
760 : :
761 : : static void
762 : 10872610 : dump_prediction (FILE *file, enum br_predictor predictor, int probability,
763 : : basic_block bb, enum predictor_reason reason = REASON_NONE,
764 : : edge ep_edge = NULL)
765 : : {
766 : 10872610 : edge e = ep_edge;
767 : 10872610 : edge_iterator ei;
768 : :
769 : 10872610 : if (!file)
770 : 10870763 : return;
771 : :
772 : 1847 : if (e == NULL)
773 : 1239 : FOR_EACH_EDGE (e, ei, bb->succs)
774 : 1239 : if (! (e->flags & EDGE_FALLTHRU))
775 : : break;
776 : :
777 : 1847 : char edge_info_str[128];
778 : 1847 : if (ep_edge)
779 : 608 : sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
780 : 608 : ep_edge->dest->index);
781 : : else
782 : 1239 : edge_info_str[0] = '\0';
783 : :
784 : 1847 : fprintf (file, " %s heuristics%s%s: %.2f%%",
785 : 1847 : predictor_info[predictor].name,
786 : 1847 : edge_info_str, reason_messages[reason],
787 : 1847 : probability * 100.0 / REG_BR_PROB_BASE);
788 : :
789 : 1847 : if (bb->count.initialized_p ())
790 : : {
791 : 225 : fprintf (file, " exec ");
792 : 225 : bb->count.dump (file);
793 : 225 : if (e && e->count ().initialized_p () && bb->count.to_gcov_type ())
794 : : {
795 : 144 : fprintf (file, " hit ");
796 : 144 : e->count ().dump (file);
797 : 288 : fprintf (file, " (%.1f%%)", e->count ().to_gcov_type() * 100.0
798 : 144 : / bb->count.to_gcov_type ());
799 : : }
800 : : }
801 : :
802 : 1847 : fprintf (file, "\n");
803 : :
804 : : /* Print output that be easily read by analyze_brprob.py script. We are
805 : : interested only in counts that are read from GCDA files. */
806 : 1847 : if (dump_file && (dump_flags & TDF_DETAILS)
807 : 1077 : && bb->count.precise_p ()
808 : 1860 : && reason == REASON_NONE)
809 : : {
810 : 9 : fprintf (file, ";;heuristics;%s;%" PRId64 ";%" PRId64 ";%.1f;\n",
811 : : predictor_info[predictor].name,
812 : 18 : bb->count.to_gcov_type (), e->count ().to_gcov_type (),
813 : : probability * 100.0 / REG_BR_PROB_BASE);
814 : : }
815 : : }
816 : :
817 : : /* Return true if STMT is known to be unlikely executed. */
818 : :
819 : : static bool
820 : 106076583 : unlikely_executed_stmt_p (gimple *stmt)
821 : : {
822 : 106076583 : if (!is_gimple_call (stmt))
823 : : return false;
824 : : /* NORETURN attribute alone is not strong enough: exit() may be quite
825 : : likely executed once during program run. */
826 : 8358735 : if (gimple_call_fntype (stmt)
827 : 8021680 : && lookup_attribute ("cold",
828 : 8021680 : TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
829 : 8358735 : && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
830 : : return true;
831 : 8358735 : tree decl = gimple_call_fndecl (stmt);
832 : 8358735 : if (!decl)
833 : : return false;
834 : 7866472 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
835 : 7866472 : && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
836 : : return true;
837 : :
838 : 7560053 : cgraph_node *n = cgraph_node::get (decl);
839 : 7560053 : if (!n)
840 : : return false;
841 : :
842 : 7557313 : availability avail;
843 : 7557313 : n = n->ultimate_alias_target (&avail);
844 : 7557313 : if (avail < AVAIL_AVAILABLE)
845 : : return false;
846 : 2446395 : if (!n->analyzed
847 : 2446395 : || n->decl == current_function_decl)
848 : : return false;
849 : 2433371 : return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
850 : : }
851 : :
852 : : /* Return true if BB is unlikely executed. */
853 : :
854 : : static bool
855 : 21587736 : unlikely_executed_bb_p (basic_block bb)
856 : : {
857 : 21587736 : if (bb->count == profile_count::zero ())
858 : 0 : return true;
859 : 21587736 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
860 : : return false;
861 : 43175472 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
862 : 120900974 : !gsi_end_p (gsi); gsi_next (&gsi))
863 : : {
864 : 106076583 : if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
865 : : return true;
866 : 105755561 : if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
867 : : return false;
868 : : }
869 : : return false;
870 : : }
871 : :
872 : : /* We cannot predict the probabilities of outgoing edges of bb. Set them
873 : : evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
874 : : even probability for all edges not mentioned in the set. These edges
875 : : are given PROB_VERY_UNLIKELY probability. Similarly for LIKELY_EDGES,
876 : : if we have exactly one likely edge, make the other edges predicted
877 : : as not probable. */
878 : :
879 : : static void
880 : 7788375 : set_even_probabilities (basic_block bb,
881 : : hash_set<edge> *unlikely_edges = NULL,
882 : : hash_set<edge_prediction *> *likely_edges = NULL)
883 : : {
884 : 7788375 : unsigned nedges = 0, unlikely_count = 0;
885 : 7788375 : edge e = NULL;
886 : 7788375 : edge_iterator ei;
887 : 7788375 : profile_probability all = profile_probability::always ();
888 : :
889 : 17087775 : FOR_EACH_EDGE (e, ei, bb->succs)
890 : 9299400 : if (e->probability.initialized_p ())
891 : 8315251 : all -= e->probability;
892 : 984149 : else if (!unlikely_executed_edge_p (e))
893 : : {
894 : 600969 : nedges++;
895 : 600969 : if (unlikely_edges != NULL && unlikely_edges->contains (e))
896 : : {
897 : 6065 : all -= profile_probability::very_unlikely ();
898 : 6065 : unlikely_count++;
899 : : }
900 : : }
901 : :
902 : : /* Make the distribution even if all edges are unlikely. */
903 : 7788375 : unsigned likely_count = likely_edges ? likely_edges->elements () : 0;
904 : 7788375 : if (unlikely_count == nedges)
905 : : {
906 : 7305366 : unlikely_edges = NULL;
907 : 7305366 : unlikely_count = 0;
908 : : }
909 : :
910 : : /* If we have one likely edge, then use its probability and distribute
911 : : remaining probabilities as even. */
912 : 7788375 : if (likely_count == 1)
913 : : {
914 : 2720 : FOR_EACH_EDGE (e, ei, bb->succs)
915 : 1818 : if (e->probability.initialized_p ())
916 : : ;
917 : 28 : else if (!unlikely_executed_edge_p (e))
918 : : {
919 : 28 : edge_prediction *prediction = *likely_edges->begin ();
920 : 28 : int p = prediction->ep_probability;
921 : 28 : profile_probability prob
922 : 28 : = profile_probability::from_reg_br_prob_base (p);
923 : :
924 : 28 : if (prediction->ep_edge == e)
925 : 7 : e->probability = prob;
926 : 21 : else if (unlikely_edges != NULL && unlikely_edges->contains (e))
927 : 1 : e->probability = profile_probability::very_unlikely ();
928 : : else
929 : : {
930 : 20 : profile_probability remainder = prob.invert ();
931 : 20 : remainder -= (profile_probability::very_unlikely ()
932 : 40 : * unlikely_count);
933 : 20 : int count = nedges - unlikely_count - 1;
934 : 20 : gcc_assert (count >= 0);
935 : :
936 : 20 : e->probability = remainder / count;
937 : : }
938 : : }
939 : : else
940 : 0 : e->probability = profile_probability::never ();
941 : : }
942 : : else
943 : : {
944 : : /* Make all unlikely edges unlikely and the rest will have even
945 : : probability. */
946 : 7787473 : unsigned scale = nedges - unlikely_count;
947 : 17085055 : FOR_EACH_EDGE (e, ei, bb->succs)
948 : 9297582 : if (e->probability.initialized_p ())
949 : : ;
950 : 984121 : else if (!unlikely_executed_edge_p (e))
951 : : {
952 : 600941 : if (unlikely_edges != NULL && unlikely_edges->contains (e))
953 : 6064 : e->probability = profile_probability::very_unlikely ();
954 : : else
955 : 594877 : e->probability = all / scale;
956 : : }
957 : : else
958 : 383180 : e->probability = profile_probability::never ();
959 : : }
960 : 7788375 : }
961 : :
962 : : /* Add REG_BR_PROB note to JUMP with PROB. */
963 : :
964 : : void
965 : 4668236 : add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
966 : : {
967 : 4668236 : gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
968 : 4668236 : add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
969 : 4668236 : }
970 : :
971 : : /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
972 : : note if not already present. Remove now useless REG_BR_PRED notes. */
973 : :
974 : : static void
975 : 489014 : combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
976 : : {
977 : 489014 : rtx prob_note;
978 : 489014 : rtx *pnote;
979 : 489014 : rtx note;
980 : 489014 : int best_probability = PROB_EVEN;
981 : 489014 : enum br_predictor best_predictor = END_PREDICTORS;
982 : 489014 : int combined_probability = REG_BR_PROB_BASE / 2;
983 : 489014 : int d;
984 : 489014 : bool first_match = false;
985 : 489014 : bool found = false;
986 : :
987 : 489014 : if (!can_predict_insn_p (insn))
988 : : {
989 : 376816 : set_even_probabilities (bb);
990 : 376816 : return;
991 : : }
992 : :
993 : 112198 : prob_note = find_reg_note (insn, REG_BR_PROB, 0);
994 : 112198 : pnote = ®_NOTES (insn);
995 : 112198 : if (dump_file)
996 : 36 : fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
997 : : bb->index);
998 : :
999 : : /* We implement "first match" heuristics and use probability guessed
1000 : : by predictor with smallest index. */
1001 : 180866 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1002 : 68668 : if (REG_NOTE_KIND (note) == REG_BR_PRED)
1003 : : {
1004 : 68668 : enum br_predictor predictor = ((enum br_predictor)
1005 : 68668 : INTVAL (XEXP (XEXP (note, 0), 0)));
1006 : 68668 : int probability = INTVAL (XEXP (XEXP (note, 0), 1));
1007 : :
1008 : 68668 : found = true;
1009 : 68668 : if (best_predictor > predictor
1010 : 68668 : && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1011 : 68668 : best_probability = probability, best_predictor = predictor;
1012 : :
1013 : 68668 : d = (combined_probability * probability
1014 : 68668 : + (REG_BR_PROB_BASE - combined_probability)
1015 : 68668 : * (REG_BR_PROB_BASE - probability));
1016 : :
1017 : : /* Use FP math to avoid overflows of 32bit integers. */
1018 : 68668 : if (d == 0)
1019 : : /* If one probability is 0% and one 100%, avoid division by zero. */
1020 : : combined_probability = REG_BR_PROB_BASE / 2;
1021 : : else
1022 : 68668 : combined_probability = (((double) combined_probability) * probability
1023 : 68668 : * REG_BR_PROB_BASE / d + 0.5);
1024 : : }
1025 : :
1026 : : /* Decide which heuristic to use. In case we didn't match anything,
1027 : : use no_prediction heuristic, in case we did match, use either
1028 : : first match or Dempster-Shaffer theory depending on the flags. */
1029 : :
1030 : 112198 : if (best_predictor != END_PREDICTORS)
1031 : 180 : first_match = true;
1032 : :
1033 : 112198 : if (!found)
1034 : 43530 : dump_prediction (dump_file, PRED_NO_PREDICTION,
1035 : : combined_probability, bb);
1036 : : else
1037 : : {
1038 : 68668 : if (!first_match)
1039 : 68488 : dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
1040 : : bb, !first_match ? REASON_NONE : REASON_IGNORED);
1041 : : else
1042 : 180 : dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
1043 : : bb, first_match ? REASON_NONE : REASON_IGNORED);
1044 : : }
1045 : :
1046 : 112198 : if (first_match)
1047 : 180 : combined_probability = best_probability;
1048 : 112198 : dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1049 : :
1050 : 293064 : while (*pnote)
1051 : : {
1052 : 68668 : if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
1053 : : {
1054 : 68668 : enum br_predictor predictor = ((enum br_predictor)
1055 : 68668 : INTVAL (XEXP (XEXP (*pnote, 0), 0)));
1056 : 68668 : int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
1057 : :
1058 : 68668 : dump_prediction (dump_file, predictor, probability, bb,
1059 : 68668 : (!first_match || best_predictor == predictor)
1060 : 68668 : ? REASON_NONE : REASON_IGNORED);
1061 : 68668 : *pnote = XEXP (*pnote, 1);
1062 : : }
1063 : : else
1064 : 0 : pnote = &XEXP (*pnote, 1);
1065 : : }
1066 : :
1067 : 112198 : if (!prob_note)
1068 : : {
1069 : 112198 : profile_probability p
1070 : 112198 : = profile_probability::from_reg_br_prob_base (combined_probability);
1071 : 112198 : add_reg_br_prob_note (insn, p);
1072 : :
1073 : : /* Save the prediction into CFG in case we are seeing non-degenerated
1074 : : conditional jump. */
1075 : 224396 : if (!single_succ_p (bb))
1076 : : {
1077 : 112198 : BRANCH_EDGE (bb)->probability = p;
1078 : 112198 : FALLTHRU_EDGE (bb)->probability
1079 : 224396 : = BRANCH_EDGE (bb)->probability.invert ();
1080 : : }
1081 : : }
1082 : 0 : else if (!single_succ_p (bb))
1083 : : {
1084 : 0 : profile_probability prob = profile_probability::from_reg_br_prob_note
1085 : 0 : (XINT (prob_note, 0));
1086 : :
1087 : 0 : BRANCH_EDGE (bb)->probability = prob;
1088 : 0 : FALLTHRU_EDGE (bb)->probability = prob.invert ();
1089 : : }
1090 : : else
1091 : 0 : single_succ_edge (bb)->probability = profile_probability::always ();
1092 : : }
1093 : :
1094 : : /* Edge prediction hash traits. */
1095 : :
1096 : : struct predictor_hash: pointer_hash <edge_prediction>
1097 : : {
1098 : :
1099 : : static inline hashval_t hash (const edge_prediction *);
1100 : : static inline bool equal (const edge_prediction *, const edge_prediction *);
1101 : : };
1102 : :
1103 : : /* Calculate hash value of an edge prediction P based on predictor and
1104 : : normalized probability. */
1105 : :
1106 : : inline hashval_t
1107 : 11585270 : predictor_hash::hash (const edge_prediction *p)
1108 : : {
1109 : 11585270 : inchash::hash hstate;
1110 : 11585270 : hstate.add_int (p->ep_predictor);
1111 : :
1112 : 11585270 : int prob = p->ep_probability;
1113 : 11585270 : if (prob > REG_BR_PROB_BASE / 2)
1114 : 1544144 : prob = REG_BR_PROB_BASE - prob;
1115 : :
1116 : 11585270 : hstate.add_int (prob);
1117 : :
1118 : 11585270 : return hstate.end ();
1119 : : }
1120 : :
1121 : : /* Return true whether edge predictions P1 and P2 use the same predictor and
1122 : : have equal (or opposed probability). */
1123 : :
1124 : : inline bool
1125 : 2632544 : predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1126 : : {
1127 : 2632544 : return (p1->ep_predictor == p2->ep_predictor
1128 : 2632544 : && (p1->ep_probability == p2->ep_probability
1129 : 0 : || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
1130 : : }
1131 : :
1132 : : struct predictor_hash_traits: predictor_hash,
1133 : : typed_noop_remove <edge_prediction *> {};
1134 : :
1135 : : /* Return true if edge prediction P is not in DATA hash set. */
1136 : :
1137 : : static bool
1138 : 4569844 : not_removed_prediction_p (edge_prediction *p, void *data)
1139 : : {
1140 : 4569844 : hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1141 : 4569844 : return !remove->contains (p);
1142 : : }
1143 : :
1144 : : /* Prune predictions for a basic block BB. Currently we do following
1145 : : clean-up steps:
1146 : :
1147 : : 1) remove duplicate prediction that is guessed with the same probability
1148 : : (different than 1/2) to both edge
1149 : : 2) remove duplicates for a prediction that belongs with the same probability
1150 : : to a single edge
1151 : :
1152 : : */
1153 : :
1154 : : static void
1155 : 3004821 : prune_predictions_for_bb (basic_block bb)
1156 : : {
1157 : 3004821 : edge_prediction **preds = bb_predictions->get (bb);
1158 : :
1159 : 3004821 : if (preds)
1160 : : {
1161 : 2601322 : hash_table <predictor_hash_traits> s (13);
1162 : 2601322 : hash_set <edge_prediction *> remove;
1163 : :
1164 : : /* Step 1: identify predictors that should be removed. */
1165 : 7171166 : for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1166 : : {
1167 : 4569844 : edge_prediction *existing = s.find (pred);
1168 : 4569844 : if (existing)
1169 : : {
1170 : 220648 : if (pred->ep_edge == existing->ep_edge
1171 : 0 : && pred->ep_probability == existing->ep_probability)
1172 : : {
1173 : : /* Remove a duplicate predictor. */
1174 : 0 : dump_prediction (dump_file, pred->ep_predictor,
1175 : : pred->ep_probability, bb,
1176 : : REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);
1177 : :
1178 : 0 : remove.add (pred);
1179 : : }
1180 : 220648 : else if (pred->ep_edge != existing->ep_edge
1181 : 220648 : && pred->ep_probability == existing->ep_probability
1182 : 220648 : && pred->ep_probability != REG_BR_PROB_BASE / 2)
1183 : : {
1184 : : /* Remove both predictors as they predict the same
1185 : : for both edges. */
1186 : 219395 : dump_prediction (dump_file, existing->ep_predictor,
1187 : : pred->ep_probability, bb,
1188 : : REASON_EDGE_PAIR_DUPLICATE,
1189 : : existing->ep_edge);
1190 : 219395 : dump_prediction (dump_file, pred->ep_predictor,
1191 : : pred->ep_probability, bb,
1192 : : REASON_EDGE_PAIR_DUPLICATE,
1193 : : pred->ep_edge);
1194 : :
1195 : 219395 : remove.add (existing);
1196 : 219395 : remove.add (pred);
1197 : : }
1198 : : }
1199 : :
1200 : 4569844 : edge_prediction **slot2 = s.find_slot (pred, INSERT);
1201 : 4569844 : *slot2 = pred;
1202 : : }
1203 : :
1204 : : /* Step 2: Remove predictors. */
1205 : 2601322 : filter_predictions (preds, not_removed_prediction_p, &remove);
1206 : 2601322 : }
1207 : 3004821 : }
1208 : :
1209 : : /* Combine predictions into single probability and store them into CFG.
1210 : : Remove now useless prediction entries.
1211 : : If DRY_RUN is set, only produce dumps and do not modify profile. */
1212 : :
1213 : : static void
1214 : 10416415 : combine_predictions_for_bb (basic_block bb, bool dry_run)
1215 : : {
1216 : 10416415 : int best_probability = PROB_EVEN;
1217 : 10416415 : enum br_predictor best_predictor = END_PREDICTORS;
1218 : 10416415 : int combined_probability = REG_BR_PROB_BASE / 2;
1219 : 10416415 : int d;
1220 : 10416415 : bool first_match = false;
1221 : 10416415 : bool found = false;
1222 : 10416415 : struct edge_prediction *pred;
1223 : 10416415 : int nedges = 0;
1224 : 10416415 : edge e, first = NULL, second = NULL;
1225 : 10416415 : edge_iterator ei;
1226 : 10416415 : int nzero = 0;
1227 : 10416415 : int nunknown = 0;
1228 : :
1229 : 24970530 : FOR_EACH_EDGE (e, ei, bb->succs)
1230 : : {
1231 : 14554115 : if (!unlikely_executed_edge_p (e))
1232 : : {
1233 : 12528705 : nedges ++;
1234 : 12528705 : if (first && !second)
1235 : 3028467 : second = e;
1236 : 12528705 : if (!first)
1237 : 9406857 : first = e;
1238 : : }
1239 : 2025410 : else if (!e->probability.initialized_p ())
1240 : 20980 : e->probability = profile_probability::never ();
1241 : 14554115 : if (!e->probability.initialized_p ())
1242 : 5672704 : nunknown++;
1243 : 16462197 : else if (e->probability == profile_probability::never ())
1244 : 1906241 : nzero++;
1245 : : }
1246 : :
1247 : : /* When there is no successor or only one choice, prediction is easy.
1248 : :
1249 : : When we have a basic block with more than 2 successors, the situation
1250 : : is more complicated as DS theory cannot be used literally.
1251 : : More precisely, let's assume we predicted edge e1 with probability p1,
1252 : : thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1253 : : need to find probability of e.g. m1({b2}), which we don't know.
1254 : : The only approximation is to equally distribute 1-p1 to all edges
1255 : : different from b1.
1256 : :
1257 : : According to numbers we've got from SPEC2006 benchark, there's only
1258 : : one interesting reliable predictor (noreturn call), which can be
1259 : : handled with a bit easier approach. */
1260 : 10416415 : if (nedges != 2)
1261 : : {
1262 : 7411594 : hash_set<edge> unlikely_edges (4);
1263 : 7411594 : hash_set<edge_prediction *> likely_edges (4);
1264 : :
1265 : : /* Identify all edges that have a probability close to very unlikely.
1266 : : Doing the approach for very unlikely doesn't worth for doing as
1267 : : there's no such probability in SPEC2006 benchmark. */
1268 : 7411594 : edge_prediction **preds = bb_predictions->get (bb);
1269 : 7411594 : if (preds)
1270 : 1764563 : for (pred = *preds; pred; pred = pred->ep_next)
1271 : : {
1272 : 1081880 : if (pred->ep_probability <= PROB_VERY_UNLIKELY
1273 : 1072297 : || pred->ep_predictor == PRED_COLD_LABEL)
1274 : 9586 : unlikely_edges.add (pred->ep_edge);
1275 : 1072294 : else if (pred->ep_probability >= PROB_VERY_LIKELY
1276 : 1071821 : || pred->ep_predictor == PRED_BUILTIN_EXPECT
1277 : 1071394 : || pred->ep_predictor == PRED_HOT_LABEL)
1278 : 903 : likely_edges.add (pred);
1279 : : }
1280 : :
1281 : : /* It can happen that an edge is both in likely_edges and unlikely_edges.
1282 : : Clear both sets in that situation. */
1283 : 7412496 : for (hash_set<edge_prediction *>::iterator it = likely_edges.begin ();
1284 : 7413398 : it != likely_edges.end (); ++it)
1285 : 903 : if (unlikely_edges.contains ((*it)->ep_edge))
1286 : : {
1287 : 1 : likely_edges.empty ();
1288 : 7411595 : unlikely_edges.empty ();
1289 : : break;
1290 : : }
1291 : :
1292 : 7411594 : if (!dry_run)
1293 : 7411559 : set_even_probabilities (bb, &unlikely_edges, &likely_edges);
1294 : 7411594 : clear_bb_predictions (bb);
1295 : 7411594 : if (dump_file)
1296 : : {
1297 : 1266 : fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1298 : 1266 : if (unlikely_edges.is_empty ())
1299 : 1264 : fprintf (dump_file,
1300 : : "%i edges in bb %i predicted to even probabilities\n",
1301 : : nedges, bb->index);
1302 : : else
1303 : : {
1304 : 2 : fprintf (dump_file,
1305 : : "%i edges in bb %i predicted with some unlikely edges\n",
1306 : : nedges, bb->index);
1307 : 11 : FOR_EACH_EDGE (e, ei, bb->succs)
1308 : 9 : if (!unlikely_executed_edge_p (e))
1309 : 9 : dump_prediction (dump_file, PRED_COMBINED,
1310 : : e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
1311 : : }
1312 : : }
1313 : 7411594 : return;
1314 : 7411594 : }
1315 : :
1316 : 3004821 : if (dump_file)
1317 : 579 : fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1318 : :
1319 : 3004821 : prune_predictions_for_bb (bb);
1320 : :
1321 : 3004821 : edge_prediction **preds = bb_predictions->get (bb);
1322 : :
1323 : 3004821 : if (preds)
1324 : : {
1325 : : /* We implement "first match" heuristics and use probability guessed
1326 : : by predictor with smallest index. */
1327 : 6732427 : for (pred = *preds; pred; pred = pred->ep_next)
1328 : : {
1329 : 4131105 : enum br_predictor predictor = pred->ep_predictor;
1330 : 4131105 : int probability = pred->ep_probability;
1331 : :
1332 : 4131105 : if (pred->ep_edge != first)
1333 : 1048548 : probability = REG_BR_PROB_BASE - probability;
1334 : :
1335 : 4131105 : found = true;
1336 : : /* First match heuristics would be widly confused if we predicted
1337 : : both directions. */
1338 : 4131105 : if (best_predictor > predictor
1339 : 3967521 : && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1340 : : {
1341 : : struct edge_prediction *pred2;
1342 : : int prob = probability;
1343 : :
1344 : 2587404 : for (pred2 = (struct edge_prediction *) *preds;
1345 : 3809887 : pred2; pred2 = pred2->ep_next)
1346 : 2587404 : if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
1347 : : {
1348 : 0 : int probability2 = pred2->ep_probability;
1349 : :
1350 : 0 : if (pred2->ep_edge != first)
1351 : 0 : probability2 = REG_BR_PROB_BASE - probability2;
1352 : :
1353 : 0 : if ((probability < REG_BR_PROB_BASE / 2) !=
1354 : 0 : (probability2 < REG_BR_PROB_BASE / 2))
1355 : : break;
1356 : :
1357 : : /* If the same predictor later gave better result, go for it! */
1358 : 0 : if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
1359 : 0 : || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
1360 : 2587404 : prob = probability2;
1361 : : }
1362 : 1222483 : if (!pred2)
1363 : 4131105 : best_probability = prob, best_predictor = predictor;
1364 : : }
1365 : :
1366 : 4131105 : d = (combined_probability * probability
1367 : 4131105 : + (REG_BR_PROB_BASE - combined_probability)
1368 : 4131105 : * (REG_BR_PROB_BASE - probability));
1369 : :
1370 : : /* Use FP math to avoid overflows of 32bit integers. */
1371 : 4131105 : if (d == 0)
1372 : : /* If one probability is 0% and one 100%, avoid division by zero. */
1373 : : combined_probability = REG_BR_PROB_BASE / 2;
1374 : : else
1375 : 4131105 : combined_probability = (((double) combined_probability)
1376 : 4131105 : * probability
1377 : 4131105 : * REG_BR_PROB_BASE / d + 0.5);
1378 : : }
1379 : : }
1380 : :
1381 : : /* Decide which heuristic to use. In case we didn't match anything,
1382 : : use no_prediction heuristic, in case we did match, use either
1383 : : first match or Dempster-Shaffer theory depending on the flags. */
1384 : :
1385 : 3004821 : if (best_predictor != END_PREDICTORS)
1386 : 1130675 : first_match = true;
1387 : :
1388 : 3004821 : if (!found)
1389 : 455680 : dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1390 : : else
1391 : : {
1392 : 2549141 : if (!first_match)
1393 : 1418466 : dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1394 : : !first_match ? REASON_NONE : REASON_IGNORED);
1395 : : else
1396 : 1130675 : dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1397 : : first_match ? REASON_NONE : REASON_IGNORED);
1398 : : }
1399 : :
1400 : 3004821 : if (first_match)
1401 : 1130675 : combined_probability = best_probability;
1402 : 3004821 : dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1403 : :
1404 : 3004821 : if (preds)
1405 : : {
1406 : 6732427 : for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1407 : : {
1408 : 4131105 : enum br_predictor predictor = pred->ep_predictor;
1409 : 4131105 : int probability = pred->ep_probability;
1410 : :
1411 : 4131105 : dump_prediction (dump_file, predictor, probability, bb,
1412 : 4131105 : (!first_match || best_predictor == predictor)
1413 : 4131105 : ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1414 : : }
1415 : : }
1416 : 3004821 : clear_bb_predictions (bb);
1417 : :
1418 : :
1419 : : /* If we have only one successor which is unknown, we can compute missing
1420 : : probability. */
1421 : 3004821 : if (nunknown == 1)
1422 : : {
1423 : 1216 : profile_probability prob = profile_probability::always ();
1424 : 1216 : edge missing = NULL;
1425 : :
1426 : 3648 : FOR_EACH_EDGE (e, ei, bb->succs)
1427 : 2432 : if (e->probability.initialized_p ())
1428 : 1216 : prob -= e->probability;
1429 : 1216 : else if (missing == NULL)
1430 : : missing = e;
1431 : : else
1432 : 0 : gcc_unreachable ();
1433 : 1216 : missing->probability = prob;
1434 : : }
1435 : : /* If nothing is unknown, we have nothing to update. */
1436 : 3295416 : else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1437 : : ;
1438 : 2711794 : else if (!dry_run)
1439 : : {
1440 : 2711794 : first->probability
1441 : 2711794 : = profile_probability::from_reg_br_prob_base (combined_probability);
1442 : 2711794 : second->probability = first->probability.invert ();
1443 : : }
1444 : : }
1445 : :
1446 : : /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1447 : : Return the SSA_NAME if the condition satisfies, NULL otherwise.
1448 : :
1449 : : T1 and T2 should be one of the following cases:
1450 : : 1. T1 is SSA_NAME, T2 is NULL
1451 : : 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1452 : : 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1453 : :
1454 : : static tree
1455 : 8870 : strips_small_constant (tree t1, tree t2)
1456 : : {
1457 : 8870 : tree ret = NULL;
1458 : 8870 : int value = 0;
1459 : :
1460 : 8870 : if (!t1)
1461 : : return NULL;
1462 : 8870 : else if (TREE_CODE (t1) == SSA_NAME)
1463 : : ret = t1;
1464 : 1029 : else if (tree_fits_shwi_p (t1))
1465 : 99 : value = tree_to_shwi (t1);
1466 : : else
1467 : : return NULL;
1468 : :
1469 : 7940 : if (!t2)
1470 : : return ret;
1471 : 7940 : else if (tree_fits_shwi_p (t2))
1472 : 7408 : value = tree_to_shwi (t2);
1473 : 532 : else if (TREE_CODE (t2) == SSA_NAME)
1474 : : {
1475 : 354 : if (ret)
1476 : : return NULL;
1477 : : else
1478 : : ret = t2;
1479 : : }
1480 : :
1481 : 7685 : if (value <= 4 && value >= -4)
1482 : : return ret;
1483 : : else
1484 : 480 : return NULL;
1485 : : }
1486 : :
1487 : : /* Return the SSA_NAME in T or T's operands.
1488 : : Return NULL if SSA_NAME cannot be found. */
1489 : :
1490 : : static tree
1491 : 209773 : get_base_value (tree t)
1492 : : {
1493 : 209773 : if (TREE_CODE (t) == SSA_NAME)
1494 : : return t;
1495 : :
1496 : 10786 : if (!BINARY_CLASS_P (t))
1497 : : return NULL;
1498 : :
1499 : 8870 : switch (TREE_OPERAND_LENGTH (t))
1500 : : {
1501 : 0 : case 1:
1502 : 0 : return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1503 : 8870 : case 2:
1504 : 8870 : return strips_small_constant (TREE_OPERAND (t, 0),
1505 : 17740 : TREE_OPERAND (t, 1));
1506 : : default:
1507 : : return NULL;
1508 : : }
1509 : : }
1510 : :
1511 : : /* Check the compare STMT in LOOP. If it compares an induction
1512 : : variable to a loop invariant, return true, and save
1513 : : LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1514 : : Otherwise return false and set LOOP_INVAIANT to NULL. */
1515 : :
1516 : : static bool
1517 : 766061 : is_comparison_with_loop_invariant_p (gcond *stmt, class loop *loop,
1518 : : tree *loop_invariant,
1519 : : enum tree_code *compare_code,
1520 : : tree *loop_step,
1521 : : tree *loop_iv_base)
1522 : : {
1523 : 766061 : tree op0, op1, bound, base;
1524 : 766061 : affine_iv iv0, iv1;
1525 : 766061 : enum tree_code code;
1526 : 766061 : tree step;
1527 : :
1528 : 766061 : code = gimple_cond_code (stmt);
1529 : 766061 : *loop_invariant = NULL;
1530 : :
1531 : 766061 : switch (code)
1532 : : {
1533 : 765219 : case GT_EXPR:
1534 : 765219 : case GE_EXPR:
1535 : 765219 : case NE_EXPR:
1536 : 765219 : case LT_EXPR:
1537 : 765219 : case LE_EXPR:
1538 : 765219 : case EQ_EXPR:
1539 : 765219 : break;
1540 : :
1541 : : default:
1542 : : return false;
1543 : : }
1544 : :
1545 : 765219 : op0 = gimple_cond_lhs (stmt);
1546 : 765219 : op1 = gimple_cond_rhs (stmt);
1547 : :
1548 : 765219 : if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1549 : 762842 : || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1550 : : return false;
1551 : 1505082 : if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1552 : : return false;
1553 : 893366 : if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1554 : : return false;
1555 : 430784 : if (TREE_CODE (iv0.step) != INTEGER_CST
1556 : 427904 : || TREE_CODE (iv1.step) != INTEGER_CST)
1557 : : return false;
1558 : 484934 : if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1559 : 472361 : || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1560 : 12969 : return false;
1561 : :
1562 : 408783 : if (integer_zerop (iv0.step))
1563 : : {
1564 : 50609 : if (code != NE_EXPR && code != EQ_EXPR)
1565 : 38138 : code = invert_tree_comparison (code, false);
1566 : 50609 : bound = iv0.base;
1567 : 50609 : base = iv1.base;
1568 : 50609 : if (tree_fits_shwi_p (iv1.step))
1569 : : step = iv1.step;
1570 : : else
1571 : : return false;
1572 : : }
1573 : : else
1574 : : {
1575 : 358174 : bound = iv1.base;
1576 : 358174 : base = iv0.base;
1577 : 358174 : if (tree_fits_shwi_p (iv0.step))
1578 : : step = iv0.step;
1579 : : else
1580 : : return false;
1581 : : }
1582 : :
1583 : 403386 : if (TREE_CODE (bound) != INTEGER_CST)
1584 : 141962 : bound = get_base_value (bound);
1585 : 141962 : if (!bound)
1586 : : return false;
1587 : 401850 : if (TREE_CODE (base) != INTEGER_CST)
1588 : 67811 : base = get_base_value (base);
1589 : 67811 : if (!base)
1590 : : return false;
1591 : :
1592 : 399805 : *loop_invariant = bound;
1593 : 399805 : *compare_code = code;
1594 : 399805 : *loop_step = step;
1595 : 399805 : *loop_iv_base = base;
1596 : 399805 : return true;
1597 : : }
1598 : :
1599 : : /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1600 : :
1601 : : static bool
1602 : 6860 : expr_coherent_p (tree t1, tree t2)
1603 : : {
1604 : 6860 : gimple *stmt;
1605 : 6860 : tree ssa_name_1 = NULL;
1606 : 6860 : tree ssa_name_2 = NULL;
1607 : :
1608 : 6860 : gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1609 : 6860 : gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1610 : :
1611 : 6860 : if (t1 == t2)
1612 : : return true;
1613 : :
1614 : 2934 : if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1615 : : return true;
1616 : 1708 : if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1617 : : return false;
1618 : :
1619 : : /* Check to see if t1 is expressed/defined with t2. */
1620 : 321 : stmt = SSA_NAME_DEF_STMT (t1);
1621 : 321 : gcc_assert (stmt != NULL);
1622 : 321 : if (is_gimple_assign (stmt))
1623 : : {
1624 : 193 : ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1625 : 193 : if (ssa_name_1 && ssa_name_1 == t2)
1626 : : return true;
1627 : : }
1628 : :
1629 : : /* Check to see if t2 is expressed/defined with t1. */
1630 : 321 : stmt = SSA_NAME_DEF_STMT (t2);
1631 : 321 : gcc_assert (stmt != NULL);
1632 : 321 : if (is_gimple_assign (stmt))
1633 : : {
1634 : 193 : ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1635 : 193 : if (ssa_name_2 && ssa_name_2 == t1)
1636 : : return true;
1637 : : }
1638 : :
1639 : : /* Compare if t1 and t2's def_stmts are identical. */
1640 : 321 : if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1641 : : return true;
1642 : : else
1643 : : return false;
1644 : : }
1645 : :
1646 : : /* Return true if E is predicted by one of loop heuristics. */
1647 : :
1648 : : static bool
1649 : 5492370 : predicted_by_loop_heuristics_p (basic_block bb)
1650 : : {
1651 : 5492370 : struct edge_prediction *i;
1652 : 5492370 : edge_prediction **preds = bb_predictions->get (bb);
1653 : :
1654 : 5492370 : if (!preds)
1655 : : return false;
1656 : :
1657 : 1950488 : for (i = *preds; i; i = i->ep_next)
1658 : 1657355 : if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1659 : 1657355 : || i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
1660 : : || i->ep_predictor == PRED_LOOP_ITERATIONS
1661 : : || i->ep_predictor == PRED_LOOP_EXIT
1662 : : || i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
1663 : : || i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
1664 : : return true;
1665 : : return false;
1666 : : }
1667 : :
1668 : : /* Predict branch probability of BB when BB contains a branch that compares
1669 : : an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1670 : : loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1671 : :
1672 : : E.g.
1673 : : for (int i = 0; i < bound; i++) {
1674 : : if (i < bound - 2)
1675 : : computation_1();
1676 : : else
1677 : : computation_2();
1678 : : }
1679 : :
1680 : : In this loop, we will predict the branch inside the loop to be taken. */
1681 : :
1682 : : static void
1683 : 1813959 : predict_iv_comparison (class loop *loop, basic_block bb,
1684 : : tree loop_bound_var,
1685 : : tree loop_iv_base_var,
1686 : : enum tree_code loop_bound_code,
1687 : : int loop_bound_step)
1688 : : {
1689 : 1813959 : tree compare_var, compare_base;
1690 : 1813959 : enum tree_code compare_code;
1691 : 1813959 : tree compare_step_var;
1692 : 1813959 : edge then_edge;
1693 : 1813959 : edge_iterator ei;
1694 : :
1695 : 1813959 : if (predicted_by_loop_heuristics_p (bb))
1696 : 1812377 : return;
1697 : :
1698 : 3786176 : gcond *stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (bb));
1699 : 227650 : if (!stmt)
1700 : : return;
1701 : 227650 : if (!is_comparison_with_loop_invariant_p (stmt,
1702 : : loop, &compare_var,
1703 : : &compare_code,
1704 : : &compare_step_var,
1705 : : &compare_base))
1706 : : return;
1707 : :
1708 : : /* Find the taken edge. */
1709 : 10268 : FOR_EACH_EDGE (then_edge, ei, bb->succs)
1710 : 10268 : if (then_edge->flags & EDGE_TRUE_VALUE)
1711 : : break;
1712 : :
1713 : : /* When comparing an IV to a loop invariant, NE is more likely to be
1714 : : taken while EQ is more likely to be not-taken. */
1715 : 10193 : if (compare_code == NE_EXPR)
1716 : : {
1717 : 1527 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1718 : 1527 : return;
1719 : : }
1720 : 8666 : else if (compare_code == EQ_EXPR)
1721 : : {
1722 : 4033 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1723 : 4033 : return;
1724 : : }
1725 : :
1726 : 4633 : if (!expr_coherent_p (loop_iv_base_var, compare_base))
1727 : : return;
1728 : :
1729 : : /* If loop bound, base and compare bound are all constants, we can
1730 : : calculate the probability directly. */
1731 : 4052 : if (tree_fits_shwi_p (loop_bound_var)
1732 : 2674 : && tree_fits_shwi_p (compare_var)
1733 : 2538 : && tree_fits_shwi_p (compare_base))
1734 : : {
1735 : 2470 : int probability;
1736 : 2470 : wi::overflow_type overflow;
1737 : 2470 : bool overall_overflow = false;
1738 : 2470 : widest_int compare_count, tem;
1739 : :
1740 : : /* (loop_bound - base) / compare_step */
1741 : 2470 : tem = wi::sub (wi::to_widest (loop_bound_var),
1742 : 4940 : wi::to_widest (compare_base), SIGNED, &overflow);
1743 : 2470 : overall_overflow |= overflow;
1744 : 2470 : widest_int loop_count = wi::div_trunc (tem,
1745 : 2470 : wi::to_widest (compare_step_var),
1746 : 2470 : SIGNED, &overflow);
1747 : 2470 : overall_overflow |= overflow;
1748 : :
1749 : 2470 : if (!wi::neg_p (wi::to_widest (compare_step_var))
1750 : 2470 : ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1751 : : {
1752 : : /* (loop_bound - compare_bound) / compare_step */
1753 : 330 : tem = wi::sub (wi::to_widest (loop_bound_var),
1754 : 660 : wi::to_widest (compare_var), SIGNED, &overflow);
1755 : 330 : overall_overflow |= overflow;
1756 : 330 : compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1757 : 330 : SIGNED, &overflow);
1758 : 330 : overall_overflow |= overflow;
1759 : : }
1760 : : else
1761 : : {
1762 : : /* (compare_bound - base) / compare_step */
1763 : 2140 : tem = wi::sub (wi::to_widest (compare_var),
1764 : 4280 : wi::to_widest (compare_base), SIGNED, &overflow);
1765 : 2140 : overall_overflow |= overflow;
1766 : 2140 : compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1767 : 2140 : SIGNED, &overflow);
1768 : 2140 : overall_overflow |= overflow;
1769 : : }
1770 : 2470 : if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1771 : 2122 : ++compare_count;
1772 : 2470 : if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1773 : 164 : ++loop_count;
1774 : 2470 : if (wi::neg_p (compare_count))
1775 : 761 : compare_count = 0;
1776 : 2470 : if (wi::neg_p (loop_count))
1777 : 797 : loop_count = 0;
1778 : 2470 : if (loop_count == 0)
1779 : : probability = 0;
1780 : 1665 : else if (wi::cmps (compare_count, loop_count) == 1)
1781 : : probability = REG_BR_PROB_BASE;
1782 : : else
1783 : : {
1784 : 1627 : tem = compare_count * REG_BR_PROB_BASE;
1785 : 1627 : tem = wi::udiv_trunc (tem, loop_count);
1786 : 1627 : probability = tem.to_uhwi ();
1787 : : }
1788 : :
1789 : : /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1790 : 2470 : if (!overall_overflow)
1791 : 2470 : predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1792 : :
1793 : 2470 : return;
1794 : 2470 : }
1795 : :
1796 : 1582 : if (expr_coherent_p (loop_bound_var, compare_var))
1797 : : {
1798 : 937 : if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1799 : 810 : && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1800 : 802 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1801 : 135 : else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1802 : 113 : && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1803 : 98 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1804 : 37 : else if (loop_bound_code == NE_EXPR)
1805 : : {
1806 : : /* If the loop backedge condition is "(i != bound)", we do
1807 : : the comparison based on the step of IV:
1808 : : * step < 0 : backedge condition is like (i > bound)
1809 : : * step > 0 : backedge condition is like (i < bound) */
1810 : 12 : gcc_assert (loop_bound_step != 0);
1811 : 12 : if (loop_bound_step > 0
1812 : 12 : && (compare_code == LT_EXPR
1813 : 12 : || compare_code == LE_EXPR))
1814 : 11 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1815 : 1 : else if (loop_bound_step < 0
1816 : 0 : && (compare_code == GT_EXPR
1817 : 0 : || compare_code == GE_EXPR))
1818 : 0 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1819 : : else
1820 : 1 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1821 : : }
1822 : : else
1823 : : /* The branch is predicted not-taken if loop_bound_code is
1824 : : opposite with compare_code. */
1825 : 25 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1826 : : }
1827 : 645 : else if (expr_coherent_p (loop_iv_base_var, compare_var))
1828 : : {
1829 : : /* For cases like:
1830 : : for (i = s; i < h; i++)
1831 : : if (i > s + 2) ....
1832 : : The branch should be predicted taken. */
1833 : 163 : if (loop_bound_step > 0
1834 : 153 : && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1835 : 67 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1836 : 96 : else if (loop_bound_step < 0
1837 : 10 : && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1838 : 10 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1839 : : else
1840 : 86 : predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1841 : : }
1842 : : }
1843 : :
1844 : : /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1845 : : exits are resulted from short-circuit conditions that will generate an
1846 : : if_tmp. E.g.:
1847 : :
1848 : : if (foo() || global > 10)
1849 : : break;
1850 : :
1851 : : This will be translated into:
1852 : :
1853 : : BB3:
1854 : : loop header...
1855 : : BB4:
1856 : : if foo() goto BB6 else goto BB5
1857 : : BB5:
1858 : : if global > 10 goto BB6 else goto BB7
1859 : : BB6:
1860 : : goto BB7
1861 : : BB7:
1862 : : iftmp = (PHI 0(BB5), 1(BB6))
1863 : : if iftmp == 1 goto BB8 else goto BB3
1864 : : BB8:
1865 : : outside of the loop...
1866 : :
1867 : : The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1868 : : From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1869 : : exits. This function takes BB7->BB8 as input, and finds out the extra loop
1870 : : exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1871 : :
1872 : : static void
1873 : 748183 : predict_extra_loop_exits (class loop *loop, edge exit_edge)
1874 : : {
1875 : 748183 : unsigned i;
1876 : 748183 : bool check_value_one;
1877 : 748183 : gimple *lhs_def_stmt;
1878 : 748183 : gphi *phi_stmt;
1879 : 748183 : tree cmp_rhs, cmp_lhs;
1880 : :
1881 : 1496366 : gcond *cmp_stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (exit_edge->src));
1882 : 734833 : if (!cmp_stmt)
1883 : : return;
1884 : :
1885 : 734833 : cmp_rhs = gimple_cond_rhs (cmp_stmt);
1886 : 734833 : cmp_lhs = gimple_cond_lhs (cmp_stmt);
1887 : 734833 : if (!TREE_CONSTANT (cmp_rhs)
1888 : 734833 : || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1889 : 532333 : return;
1890 : 202500 : if (TREE_CODE (cmp_lhs) != SSA_NAME)
1891 : : return;
1892 : :
1893 : : /* If check_value_one is true, only the phi_args with value '1' will lead
1894 : : to loop exit. Otherwise, only the phi_args with value '0' will lead to
1895 : : loop exit. */
1896 : 202492 : check_value_one = (((integer_onep (cmp_rhs))
1897 : 202492 : ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1898 : 202492 : ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1899 : :
1900 : 202492 : lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1901 : 202492 : if (!lhs_def_stmt)
1902 : : return;
1903 : :
1904 : 202492 : phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1905 : : if (!phi_stmt)
1906 : : return;
1907 : :
1908 : 210665 : for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1909 : : {
1910 : 141835 : edge e1;
1911 : 141835 : edge_iterator ei;
1912 : 141835 : tree val = gimple_phi_arg_def (phi_stmt, i);
1913 : 141835 : edge e = gimple_phi_arg_edge (phi_stmt, i);
1914 : :
1915 : 141835 : if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1916 : 129088 : continue;
1917 : 36525 : if ((check_value_one ^ integer_onep (val)) == 1)
1918 : 18222 : continue;
1919 : 18303 : if (EDGE_COUNT (e->src->succs) != 1)
1920 : : {
1921 : 5556 : predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
1922 : : loop);
1923 : 5556 : continue;
1924 : : }
1925 : :
1926 : 27672 : FOR_EACH_EDGE (e1, ei, e->src->preds)
1927 : 14925 : predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN,
1928 : : loop);
1929 : : }
1930 : : }
1931 : :
1932 : :
1933 : : /* Predict edge probabilities by exploiting loop structure. */
1934 : :
1935 : : static void
1936 : 246921 : predict_loops (void)
1937 : : {
1938 : 246921 : basic_block bb;
1939 : 246921 : hash_set <class loop *> with_recursion(10);
1940 : :
1941 : 5126820 : FOR_EACH_BB_FN (bb, cfun)
1942 : : {
1943 : 4879899 : gimple_stmt_iterator gsi;
1944 : 4879899 : tree decl;
1945 : :
1946 : 31678295 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1947 : 21918497 : if (is_gimple_call (gsi_stmt (gsi))
1948 : 2080458 : && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1949 : 23840532 : && recursive_call_p (current_function_decl, decl))
1950 : : {
1951 : 5585 : class loop *loop = bb->loop_father;
1952 : 11160 : while (loop && !with_recursion.add (loop))
1953 : 5575 : loop = loop_outer (loop);
1954 : : }
1955 : : }
1956 : :
1957 : : /* Try to predict out blocks in a loop that are not part of a
1958 : : natural loop. */
1959 : 1319206 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1960 : : {
1961 : 578443 : basic_block bb, *bbs;
1962 : 578443 : unsigned j, n_exits = 0;
1963 : 578443 : class tree_niter_desc niter_desc;
1964 : 578443 : edge ex;
1965 : 578443 : class nb_iter_bound *nb_iter;
1966 : 578443 : enum tree_code loop_bound_code = ERROR_MARK;
1967 : 578443 : tree loop_bound_step = NULL;
1968 : 578443 : tree loop_bound_var = NULL;
1969 : 578443 : tree loop_iv_base = NULL;
1970 : 578443 : gcond *stmt = NULL;
1971 : 578443 : bool recursion = with_recursion.contains (loop);
1972 : :
1973 : 578443 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1974 : 2157999 : FOR_EACH_VEC_ELT (exits, j, ex)
1975 : 1001113 : if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
1976 : 790567 : n_exits ++;
1977 : 578443 : if (!n_exits)
1978 : 15593 : continue;
1979 : :
1980 : 562850 : if (dump_file && (dump_flags & TDF_DETAILS))
1981 : 522 : fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
1982 : : loop->num, recursion ? " (with recursion)":"", n_exits);
1983 : 325 : if (dump_file && (dump_flags & TDF_DETAILS)
1984 : 563111 : && max_loop_iterations_int (loop) >= 0)
1985 : : {
1986 : 192 : fprintf (dump_file,
1987 : : "Loop %d iterates at most %i times.\n", loop->num,
1988 : 192 : (int)max_loop_iterations_int (loop));
1989 : : }
1990 : 325 : if (dump_file && (dump_flags & TDF_DETAILS)
1991 : 563111 : && likely_max_loop_iterations_int (loop) >= 0)
1992 : : {
1993 : 192 : fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
1994 : 192 : loop->num, (int)likely_max_loop_iterations_int (loop));
1995 : : }
1996 : :
1997 : 1548235 : FOR_EACH_VEC_ELT (exits, j, ex)
1998 : : {
1999 : 985385 : tree niter = NULL;
2000 : 985385 : HOST_WIDE_INT nitercst;
2001 : 985385 : int max = param_max_predicted_iterations;
2002 : 985385 : int probability;
2003 : 985385 : enum br_predictor predictor;
2004 : 985385 : widest_int nit;
2005 : :
2006 : 985385 : if (unlikely_executed_edge_p (ex)
2007 : 985385 : || (ex->flags & EDGE_ABNORMAL_CALL))
2008 : 194818 : continue;
2009 : : /* Loop heuristics do not expect exit conditional to be inside
2010 : : inner loop. We predict from innermost to outermost loop. */
2011 : 790567 : if (predicted_by_loop_heuristics_p (ex->src))
2012 : : {
2013 : 42384 : if (dump_file && (dump_flags & TDF_DETAILS))
2014 : 0 : fprintf (dump_file, "Skipping exit %i->%i because "
2015 : : "it is already predicted.\n",
2016 : 0 : ex->src->index, ex->dest->index);
2017 : 42384 : continue;
2018 : : }
2019 : 748183 : predict_extra_loop_exits (loop, ex);
2020 : :
2021 : 748183 : if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
2022 : 387290 : niter = niter_desc.niter;
2023 : 387290 : if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
2024 : 504375 : niter = loop_niter_by_eval (loop, ex);
2025 : 330 : if (dump_file && (dump_flags & TDF_DETAILS)
2026 : 748444 : && TREE_CODE (niter) == INTEGER_CST)
2027 : : {
2028 : 181 : fprintf (dump_file, "Exit %i->%i %d iterates ",
2029 : 181 : ex->src->index, ex->dest->index,
2030 : : loop->num);
2031 : 181 : print_generic_expr (dump_file, niter, TDF_SLIM);
2032 : 181 : fprintf (dump_file, " times.\n");
2033 : : }
2034 : :
2035 : 748183 : if (TREE_CODE (niter) == INTEGER_CST)
2036 : : {
2037 : 255199 : if (tree_fits_uhwi_p (niter)
2038 : 255199 : && max
2039 : 510392 : && compare_tree_int (niter, max - 1) == -1)
2040 : 173098 : nitercst = tree_to_uhwi (niter) + 1;
2041 : : else
2042 : 82101 : nitercst = max;
2043 : : predictor = PRED_LOOP_ITERATIONS;
2044 : : }
2045 : : /* If we have just one exit and we can derive some information about
2046 : : the number of iterations of the loop from the statements inside
2047 : : the loop, use it to predict this exit. */
2048 : 492984 : else if (n_exits == 1
2049 : 492984 : && estimated_stmt_executions (loop, &nit))
2050 : : {
2051 : 11 : if (wi::gtu_p (nit, max))
2052 : 1 : nitercst = max;
2053 : : else
2054 : 10 : nitercst = nit.to_shwi ();
2055 : : predictor = PRED_LOOP_ITERATIONS_GUESSED;
2056 : : }
2057 : : /* If we have likely upper bound, trust it for very small iteration
2058 : : counts. Such loops would otherwise get mispredicted by standard
2059 : : LOOP_EXIT heuristics. */
2060 : 981979 : else if (n_exits == 1
2061 : 225626 : && likely_max_stmt_executions (loop, &nit)
2062 : 619137 : && wi::ltu_p (nit,
2063 : 251894 : RDIV (REG_BR_PROB_BASE,
2064 : : REG_BR_PROB_BASE
2065 : : - predictor_info
2066 : : [recursion
2067 : : ? PRED_LOOP_EXIT_WITH_RECURSION
2068 : : : PRED_LOOP_EXIT].hitrate)))
2069 : : {
2070 : 3967 : nitercst = nit.to_shwi ();
2071 : 3967 : predictor = PRED_LOOP_ITERATIONS_MAX;
2072 : : }
2073 : : else
2074 : : {
2075 : 489006 : if (dump_file && (dump_flags & TDF_DETAILS))
2076 : 78 : fprintf (dump_file, "Nothing known about exit %i->%i.\n",
2077 : 78 : ex->src->index, ex->dest->index);
2078 : 489006 : continue;
2079 : : }
2080 : :
2081 : 259177 : if (dump_file && (dump_flags & TDF_DETAILS))
2082 : 183 : fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
2083 : 183 : (int)nitercst, predictor_info[predictor].name);
2084 : : /* If the prediction for number of iterations is zero, do not
2085 : : predict the exit edges. */
2086 : 259177 : if (nitercst == 0)
2087 : 6 : continue;
2088 : :
2089 : 259171 : probability = RDIV (REG_BR_PROB_BASE, nitercst);
2090 : 259171 : predict_edge (ex, predictor, probability);
2091 : 985385 : }
2092 : :
2093 : : /* Find information about loop bound variables. */
2094 : 791513 : for (nb_iter = loop->bounds; nb_iter;
2095 : 228663 : nb_iter = nb_iter->next)
2096 : 341034 : if (nb_iter->stmt
2097 : 341034 : && gimple_code (nb_iter->stmt) == GIMPLE_COND)
2098 : : {
2099 : 112371 : stmt = as_a <gcond *> (nb_iter->stmt);
2100 : 112371 : break;
2101 : : }
2102 : 562850 : if (!stmt)
2103 : 900958 : stmt = safe_dyn_cast <gcond *> (*gsi_last_bb (loop->header));
2104 : : if (stmt)
2105 : 538411 : is_comparison_with_loop_invariant_p (stmt, loop,
2106 : : &loop_bound_var,
2107 : : &loop_bound_code,
2108 : : &loop_bound_step,
2109 : : &loop_iv_base);
2110 : :
2111 : 562850 : bbs = get_loop_body (loop);
2112 : :
2113 : 3458539 : for (j = 0; j < loop->num_nodes; j++)
2114 : : {
2115 : 2895689 : edge e;
2116 : 2895689 : edge_iterator ei;
2117 : :
2118 : 2895689 : bb = bbs[j];
2119 : :
2120 : : /* Bypass loop heuristics on continue statement. These
2121 : : statements construct loops via "non-loop" constructs
2122 : : in the source language and are better to be handled
2123 : : separately. */
2124 : 2895689 : if (predicted_by_p (bb, PRED_CONTINUE))
2125 : : {
2126 : 7845 : if (dump_file && (dump_flags & TDF_DETAILS))
2127 : 0 : fprintf (dump_file, "BB %i predicted by continue.\n",
2128 : : bb->index);
2129 : 7845 : continue;
2130 : : }
2131 : :
2132 : : /* If we already used more reliable loop exit predictors, do not
2133 : : bother with PRED_LOOP_EXIT. */
2134 : 2887844 : if (!predicted_by_loop_heuristics_p (bb))
2135 : : {
2136 : : /* For loop with many exits we don't want to predict all exits
2137 : : with the pretty large probability, because if all exits are
2138 : : considered in row, the loop would be predicted to iterate
2139 : : almost never. The code to divide probability by number of
2140 : : exits is very rough. It should compute the number of exits
2141 : : taken in each patch through function (not the overall number
2142 : : of exits that might be a lot higher for loops with wide switch
2143 : : statements in them) and compute n-th square root.
2144 : :
2145 : : We limit the minimal probability by 2% to avoid
2146 : : EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2147 : : as this was causing regression in perl benchmark containing such
2148 : : a wide loop. */
2149 : :
2150 : 4706468 : int probability = ((REG_BR_PROB_BASE
2151 : 2353234 : - predictor_info
2152 : : [recursion
2153 : 2353234 : ? PRED_LOOP_EXIT_WITH_RECURSION
2154 : 2353234 : : PRED_LOOP_EXIT].hitrate)
2155 : 2353234 : / n_exits);
2156 : 2353234 : if (probability < HITRATE (2))
2157 : : probability = HITRATE (2);
2158 : 5761230 : FOR_EACH_EDGE (e, ei, bb->succs)
2159 : 3407996 : if (e->dest->index < NUM_FIXED_BLOCKS
2160 : 3407996 : || !flow_bb_inside_loop_p (loop, e->dest))
2161 : : {
2162 : 650044 : if (dump_file && (dump_flags & TDF_DETAILS))
2163 : 88 : fprintf (dump_file,
2164 : : "Predicting exit %i->%i with prob %i.\n",
2165 : 88 : e->src->index, e->dest->index, probability);
2166 : 1293278 : predict_edge (e,
2167 : : recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2168 : : : PRED_LOOP_EXIT, probability);
2169 : : }
2170 : : }
2171 : 2887844 : if (loop_bound_var)
2172 : 1813959 : predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
2173 : : loop_bound_code,
2174 : 1813959 : tree_to_shwi (loop_bound_step));
2175 : : }
2176 : :
2177 : : /* In the following code
2178 : : for (loop1)
2179 : : if (cond)
2180 : : for (loop2)
2181 : : body;
2182 : : guess that cond is unlikely. */
2183 : 562850 : if (loop_outer (loop)->num)
2184 : : {
2185 : 114239 : basic_block bb = NULL;
2186 : 114239 : edge preheader_edge = loop_preheader_edge (loop);
2187 : :
2188 : 114239 : if (single_pred_p (preheader_edge->src)
2189 : 208324 : && single_succ_p (preheader_edge->src))
2190 : 94085 : preheader_edge = single_pred_edge (preheader_edge->src);
2191 : :
2192 : : /* Pattern match fortran loop preheader:
2193 : : _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2194 : : _17 = (logical(kind=4)) _16;
2195 : : if (_17 != 0)
2196 : : goto <bb 11>;
2197 : : else
2198 : : goto <bb 13>;
2199 : :
2200 : : Loop guard branch prediction says nothing about duplicated loop
2201 : : headers produced by fortran frontend and in this case we want
2202 : : to predict paths leading to this preheader. */
2203 : :
2204 : 114239 : gcond *stmt
2205 : 228478 : = safe_dyn_cast <gcond *> (*gsi_last_bb (preheader_edge->src));
2206 : 91290 : if (stmt
2207 : 91290 : && gimple_cond_code (stmt) == NE_EXPR
2208 : 31163 : && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2209 : 31119 : && integer_zerop (gimple_cond_rhs (stmt)))
2210 : : {
2211 : 11703 : gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2212 : 11703 : if (gimple_code (call_stmt) == GIMPLE_ASSIGN
2213 : 4483 : && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (call_stmt))
2214 : 11853 : && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2215 : 150 : call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2216 : 11703 : if (gimple_call_internal_p (call_stmt, IFN_BUILTIN_EXPECT)
2217 : 122 : && TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
2218 : 122 : && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
2219 : 11825 : && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
2220 : : == PRED_FORTRAN_LOOP_PREHEADER)
2221 : 18 : bb = preheader_edge->src;
2222 : : }
2223 : 18 : if (!bb)
2224 : : {
2225 : 114221 : if (!dominated_by_p (CDI_DOMINATORS,
2226 : 114221 : loop_outer (loop)->latch, loop->header))
2227 : 46885 : predict_paths_leading_to_edge (loop_preheader_edge (loop),
2228 : : recursion
2229 : : ? PRED_LOOP_GUARD_WITH_RECURSION
2230 : : : PRED_LOOP_GUARD,
2231 : : NOT_TAKEN,
2232 : : loop_outer (loop));
2233 : : }
2234 : : else
2235 : : {
2236 : 18 : if (!dominated_by_p (CDI_DOMINATORS,
2237 : 18 : loop_outer (loop)->latch, bb))
2238 : 0 : predict_paths_leading_to (bb,
2239 : : recursion
2240 : : ? PRED_LOOP_GUARD_WITH_RECURSION
2241 : : : PRED_LOOP_GUARD,
2242 : : NOT_TAKEN,
2243 : : loop_outer (loop));
2244 : : }
2245 : : }
2246 : :
2247 : : /* Free basic blocks from get_loop_body. */
2248 : 562850 : free (bbs);
2249 : 825364 : }
2250 : 246921 : }
2251 : :
2252 : : /* Attempt to predict probabilities of BB outgoing edges using local
2253 : : properties. */
2254 : : static void
2255 : 489014 : bb_estimate_probability_locally (basic_block bb)
2256 : : {
2257 : 489014 : rtx_insn *last_insn = BB_END (bb);
2258 : 489014 : rtx cond;
2259 : :
2260 : 489014 : if (! can_predict_insn_p (last_insn))
2261 : : return;
2262 : 112198 : cond = get_condition (last_insn, NULL, false, false);
2263 : 112198 : if (! cond)
2264 : : return;
2265 : :
2266 : : /* Try "pointer heuristic."
2267 : : A comparison ptr == 0 is predicted as false.
2268 : : Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2269 : 102924 : if (COMPARISON_P (cond)
2270 : 102924 : && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2271 : 102857 : || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2272 : : {
2273 : 67 : if (GET_CODE (cond) == EQ)
2274 : 23 : predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2275 : 44 : else if (GET_CODE (cond) == NE)
2276 : 39 : predict_insn_def (last_insn, PRED_POINTER, TAKEN);
2277 : : }
2278 : : else
2279 : :
2280 : : /* Try "opcode heuristic."
2281 : : EQ tests are usually false and NE tests are usually true. Also,
2282 : : most quantities are positive, so we can make the appropriate guesses
2283 : : about signed comparisons against zero. */
2284 : 102857 : switch (GET_CODE (cond))
2285 : : {
2286 : 0 : case CONST_INT:
2287 : : /* Unconditional branch. */
2288 : 0 : predict_insn_def (last_insn, PRED_UNCONDITIONAL,
2289 : 0 : cond == const0_rtx ? NOT_TAKEN : TAKEN);
2290 : 0 : break;
2291 : :
2292 : 19047 : case EQ:
2293 : 19047 : case UNEQ:
2294 : : /* Floating point comparisons appears to behave in a very
2295 : : unpredictable way because of special role of = tests in
2296 : : FP code. */
2297 : 19047 : if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2298 : : ;
2299 : : /* Comparisons with 0 are often used for booleans and there is
2300 : : nothing useful to predict about them. */
2301 : 19047 : else if (XEXP (cond, 1) == const0_rtx
2302 : 529 : || XEXP (cond, 0) == const0_rtx)
2303 : : ;
2304 : : else
2305 : 529 : predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2306 : : break;
2307 : :
2308 : 65356 : case NE:
2309 : 65356 : case LTGT:
2310 : : /* Floating point comparisons appears to behave in a very
2311 : : unpredictable way because of special role of = tests in
2312 : : FP code. */
2313 : 65356 : if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2314 : : ;
2315 : : /* Comparisons with 0 are often used for booleans and there is
2316 : : nothing useful to predict about them. */
2317 : 65356 : else if (XEXP (cond, 1) == const0_rtx
2318 : 60464 : || XEXP (cond, 0) == const0_rtx)
2319 : : ;
2320 : : else
2321 : 60464 : predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
2322 : : break;
2323 : :
2324 : 0 : case ORDERED:
2325 : 0 : predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
2326 : 0 : break;
2327 : :
2328 : 56 : case UNORDERED:
2329 : 56 : predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
2330 : 56 : break;
2331 : :
2332 : 5205 : case LE:
2333 : 5205 : case LT:
2334 : 5205 : if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2335 : 0 : || XEXP (cond, 1) == constm1_rtx)
2336 : 5205 : predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2337 : : break;
2338 : :
2339 : 5473 : case GE:
2340 : 5473 : case GT:
2341 : 5473 : if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2342 : 5410 : || XEXP (cond, 1) == constm1_rtx)
2343 : 2172 : predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
2344 : : break;
2345 : :
2346 : : default:
2347 : : break;
2348 : : }
2349 : : }
2350 : :
2351 : : /* Set edge->probability for each successor edge of BB. */
2352 : : void
2353 : 489014 : guess_outgoing_edge_probabilities (basic_block bb)
2354 : : {
2355 : 489014 : bb_estimate_probability_locally (bb);
2356 : 489014 : combine_predictions_for_insn (BB_END (bb), bb);
2357 : 489014 : }
2358 : :
2359 : : static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor,
2360 : : HOST_WIDE_INT *probability);
2361 : :
2362 : : /* Helper function for expr_expected_value. */
2363 : :
2364 : : static tree
2365 : 12737476 : expr_expected_value_1 (tree type, tree op0, enum tree_code code,
2366 : : tree op1, bitmap visited, enum br_predictor *predictor,
2367 : : HOST_WIDE_INT *probability)
2368 : : {
2369 : 18352359 : gimple *def;
2370 : :
2371 : : /* Reset returned probability value. */
2372 : 18352359 : *probability = -1;
2373 : 18352359 : *predictor = PRED_UNCONDITIONAL;
2374 : :
2375 : 18352359 : if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2376 : : {
2377 : 11983627 : if (TREE_CONSTANT (op0))
2378 : : return op0;
2379 : :
2380 : 11980161 : if (code == IMAGPART_EXPR)
2381 : : {
2382 : 51569 : if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2383 : : {
2384 : 49996 : def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2385 : 49996 : if (is_gimple_call (def)
2386 : 47352 : && gimple_call_internal_p (def)
2387 : 97297 : && (gimple_call_internal_fn (def)
2388 : : == IFN_ATOMIC_COMPARE_EXCHANGE))
2389 : : {
2390 : : /* Assume that any given atomic operation has low contention,
2391 : : and thus the compare-and-swap operation succeeds. */
2392 : 5417 : *predictor = PRED_COMPARE_AND_SWAP;
2393 : 5417 : return build_one_cst (TREE_TYPE (op0));
2394 : : }
2395 : : }
2396 : : }
2397 : :
2398 : 11974744 : if (code != SSA_NAME)
2399 : : return NULL_TREE;
2400 : :
2401 : 9269888 : def = SSA_NAME_DEF_STMT (op0);
2402 : :
2403 : : /* If we were already here, break the infinite cycle. */
2404 : 9269888 : if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
2405 : : return NULL;
2406 : :
2407 : 8329302 : if (gphi *phi = dyn_cast <gphi *> (def))
2408 : : {
2409 : : /* All the arguments of the PHI node must have the same constant
2410 : : length. */
2411 : 1251282 : int i, n = gimple_phi_num_args (phi);
2412 : 1251282 : tree val = NULL;
2413 : 1251282 : bool has_nonzero_edge = false;
2414 : :
2415 : : /* If we already proved that given edge is unlikely, we do not need
2416 : : to handle merging of the probabilities. */
2417 : 2509312 : for (i = 0; i < n && !has_nonzero_edge; i++)
2418 : : {
2419 : 1258030 : tree arg = PHI_ARG_DEF (phi, i);
2420 : 1258030 : if (arg == PHI_RESULT (phi))
2421 : 0 : continue;
2422 : 1258030 : profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2423 : 2516060 : if (!cnt.initialized_p () || cnt.nonzero_p ())
2424 : : has_nonzero_edge = true;
2425 : : }
2426 : :
2427 : 1945324 : for (i = 0; i < n; i++)
2428 : : {
2429 : 1941050 : tree arg = PHI_ARG_DEF (phi, i);
2430 : 1941050 : enum br_predictor predictor2;
2431 : :
2432 : : /* Skip self-referring parameters, since they does not change
2433 : : expected value. */
2434 : 1941050 : if (arg == PHI_RESULT (phi))
2435 : 694035 : continue;
2436 : :
2437 : : /* Skip edges which we already predicted as executing
2438 : : zero times. */
2439 : 1941050 : if (has_nonzero_edge)
2440 : : {
2441 : 1936969 : profile_count cnt = gimple_phi_arg_edge (phi, i)->count ();
2442 : 1937334 : if (cnt.initialized_p () && !cnt.nonzero_p ())
2443 : 227 : continue;
2444 : : }
2445 : 1940823 : HOST_WIDE_INT probability2;
2446 : 1940823 : tree new_val = expr_expected_value (arg, visited, &predictor2,
2447 : : &probability2);
2448 : : /* If we know nothing about value, give up. */
2449 : 1940823 : if (!new_val)
2450 : 1247008 : return NULL;
2451 : :
2452 : : /* If this is a first edge, trust its prediction. */
2453 : 767917 : if (!val)
2454 : : {
2455 : 679259 : val = new_val;
2456 : 679259 : *predictor = predictor2;
2457 : 679259 : *probability = probability2;
2458 : 679259 : continue;
2459 : : }
2460 : : /* If there are two different values, give up. */
2461 : 88658 : if (!operand_equal_p (val, new_val, false))
2462 : : return NULL;
2463 : :
2464 : 14556 : int p1 = get_predictor_value (*predictor, *probability);
2465 : 14556 : int p2 = get_predictor_value (predictor2, probability2);
2466 : : /* If both predictors agree, it does not matter from which
2467 : : edge we enter the basic block. */
2468 : 14556 : if (*predictor == predictor2 && p1 == p2)
2469 : 14549 : continue;
2470 : : /* The general case has no precise solution, since we do not
2471 : : know probabilities of incomming edges, yet.
2472 : : Still if value is predicted over all incomming edges, we
2473 : : can hope it will be indeed the case. Conservatively
2474 : : downgrade prediction quality (so first match merging is not
2475 : : performed) and take least successful prediction. */
2476 : :
2477 : 7 : *predictor = PRED_COMBINED_VALUE_PREDICTIONS_PHI;
2478 : 7 : *probability = MIN (p1, p2);
2479 : : }
2480 : 4274 : return val;
2481 : : }
2482 : 7078020 : if (is_gimple_assign (def))
2483 : : {
2484 : 5614883 : if (gimple_assign_lhs (def) != op0)
2485 : : return NULL;
2486 : :
2487 : 5614883 : return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2488 : : gimple_assign_rhs1 (def),
2489 : : gimple_assign_rhs_code (def),
2490 : : gimple_assign_rhs2 (def),
2491 : 5614883 : visited, predictor, probability);
2492 : : }
2493 : :
2494 : 1463137 : if (is_gimple_call (def))
2495 : : {
2496 : 923260 : tree decl = gimple_call_fndecl (def);
2497 : 923260 : if (!decl)
2498 : : {
2499 : 82905 : if (gimple_call_internal_p (def)
2500 : 82905 : && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2501 : : {
2502 : 23714 : gcc_assert (gimple_call_num_args (def) == 3);
2503 : 23714 : tree val = gimple_call_arg (def, 0);
2504 : 23714 : if (TREE_CONSTANT (val))
2505 : : return val;
2506 : 23714 : tree val2 = gimple_call_arg (def, 2);
2507 : 23714 : gcc_assert (TREE_CODE (val2) == INTEGER_CST
2508 : : && tree_fits_uhwi_p (val2)
2509 : : && tree_to_uhwi (val2) < END_PREDICTORS);
2510 : 23714 : *predictor = (enum br_predictor) tree_to_uhwi (val2);
2511 : 23714 : if (*predictor == PRED_BUILTIN_EXPECT)
2512 : 3300 : *probability
2513 : 3300 : = HITRATE (param_builtin_expect_probability);
2514 : 23714 : return gimple_call_arg (def, 1);
2515 : : }
2516 : : return NULL;
2517 : : }
2518 : :
2519 : 840355 : if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW_P (decl))
2520 : : {
2521 : 11832 : if (predictor)
2522 : 11832 : *predictor = PRED_MALLOC_NONNULL;
2523 : : /* FIXME: This is wrong and we need to convert the logic
2524 : : to value ranges. This makes predictor to assume that
2525 : : malloc always returns (size_t)1 which is not the same
2526 : : as returning non-NULL. */
2527 : 11832 : return fold_convert (type, boolean_true_node);
2528 : : }
2529 : :
2530 : 828523 : if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2531 : 474405 : switch (DECL_FUNCTION_CODE (decl))
2532 : : {
2533 : 67220 : case BUILT_IN_EXPECT:
2534 : 67220 : {
2535 : 67220 : tree val;
2536 : 67220 : if (gimple_call_num_args (def) != 2)
2537 : : return NULL;
2538 : 67220 : val = gimple_call_arg (def, 0);
2539 : 67220 : if (TREE_CONSTANT (val))
2540 : : return val;
2541 : 67220 : *predictor = PRED_BUILTIN_EXPECT;
2542 : 67220 : *probability
2543 : 67220 : = HITRATE (param_builtin_expect_probability);
2544 : 67220 : return gimple_call_arg (def, 1);
2545 : : }
2546 : 19 : case BUILT_IN_EXPECT_WITH_PROBABILITY:
2547 : 19 : {
2548 : 19 : tree val;
2549 : 19 : if (gimple_call_num_args (def) != 3)
2550 : : return NULL;
2551 : 19 : val = gimple_call_arg (def, 0);
2552 : 19 : if (TREE_CONSTANT (val))
2553 : : return val;
2554 : : /* Compute final probability as:
2555 : : probability * REG_BR_PROB_BASE. */
2556 : 19 : tree prob = gimple_call_arg (def, 2);
2557 : 19 : tree t = TREE_TYPE (prob);
2558 : 38 : tree base = build_int_cst (integer_type_node,
2559 : 19 : REG_BR_PROB_BASE);
2560 : 19 : base = build_real_from_int_cst (t, base);
2561 : 19 : tree r = fold_build2_initializer_loc (UNKNOWN_LOCATION,
2562 : : MULT_EXPR, t, prob, base);
2563 : 19 : if (TREE_CODE (r) != REAL_CST)
2564 : : {
2565 : 1 : error_at (gimple_location (def),
2566 : : "probability %qE must be "
2567 : : "constant floating-point expression", prob);
2568 : 1 : return NULL;
2569 : : }
2570 : 18 : HOST_WIDE_INT probi
2571 : 18 : = real_to_integer (TREE_REAL_CST_PTR (r));
2572 : 18 : if (probi >= 0 && probi <= REG_BR_PROB_BASE)
2573 : : {
2574 : 17 : *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
2575 : 17 : *probability = probi;
2576 : : }
2577 : : else
2578 : 1 : error_at (gimple_location (def),
2579 : : "probability %qE is outside "
2580 : : "the range [0.0, 1.0]", prob);
2581 : :
2582 : 18 : return gimple_call_arg (def, 1);
2583 : : }
2584 : :
2585 : 5261 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2586 : 5261 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2587 : 5261 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2588 : 5261 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2589 : 5261 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2590 : 5261 : case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2591 : 5261 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2592 : 5261 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2593 : 5261 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2594 : 5261 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2595 : 5261 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2596 : 5261 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2597 : 5261 : case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2598 : : /* Assume that any given atomic operation has low contention,
2599 : : and thus the compare-and-swap operation succeeds. */
2600 : 5261 : *predictor = PRED_COMPARE_AND_SWAP;
2601 : 5261 : return boolean_true_node;
2602 : 2081 : case BUILT_IN_REALLOC:
2603 : 2081 : case BUILT_IN_GOMP_REALLOC:
2604 : 2081 : if (predictor)
2605 : 2081 : *predictor = PRED_MALLOC_NONNULL;
2606 : : /* FIXME: This is wrong and we need to convert the logic
2607 : : to value ranges. */
2608 : 2081 : return fold_convert (type, boolean_true_node);
2609 : : default:
2610 : : break;
2611 : : }
2612 : : }
2613 : :
2614 : 1293819 : return NULL;
2615 : : }
2616 : :
2617 : 6368732 : if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2618 : : {
2619 : 5810244 : tree res;
2620 : 5810244 : tree nop0 = op0;
2621 : 5810244 : tree nop1 = op1;
2622 : :
2623 : : /* First handle situation where single op is enough to determine final
2624 : : value. In this case we can do better job by avoiding the prediction
2625 : : merging. */
2626 : 5810244 : if (TREE_CODE (op0) != INTEGER_CST)
2627 : : {
2628 : : /* See if expected value of op0 is good enough to determine the result. */
2629 : 5769431 : nop0 = expr_expected_value (op0, visited, predictor, probability);
2630 : 5769431 : if (nop0
2631 : 123832 : && (res = fold_build2 (code, type, nop0, op1)) != NULL
2632 : 5893263 : && TREE_CODE (res) == INTEGER_CST)
2633 : : /* We are now getting conservative probability. Consider for
2634 : : example:
2635 : : op0 * op1
2636 : : If op0 is 0 with probability p, then we will ignore the
2637 : : posibility that op0 != 0 and op1 == 0. It does not seem to be
2638 : : worthwhile to downgrade prediciton quality for this. */
2639 : : return res;
2640 : 5654904 : if (!nop0)
2641 : 5686412 : nop0 = op0;
2642 : : }
2643 : 5695717 : enum br_predictor predictor2 = PRED_UNCONDITIONAL;
2644 : 5695717 : HOST_WIDE_INT probability2 = -1;
2645 : 5695717 : if (TREE_CODE (op1) != INTEGER_CST)
2646 : : {
2647 : : /* See if expected value of op1 is good enough to determine the result. */
2648 : 2016790 : nop1 = expr_expected_value (op1, visited, &predictor2, &probability2);
2649 : 2016790 : if (nop1
2650 : 233200 : && (res = fold_build2 (code, type, op0, nop1)) != NULL
2651 : 2249990 : && TREE_CODE (res) == INTEGER_CST)
2652 : : {
2653 : : /* Similarly as above we now get conservative probability. */
2654 : 38 : *predictor = predictor2;
2655 : 38 : *probability = probability2;
2656 : 38 : return res;
2657 : : }
2658 : 2016752 : if (!nop1)
2659 : 5462517 : nop1 = op1;
2660 : : }
2661 : : /* We already checked if folding one of arguments to constant is good
2662 : : enough. Consequently failing to fold both means that we will not
2663 : : succeed determining the value. */
2664 : 5695679 : if (nop0 == op0 || nop1 == op1)
2665 : : return NULL;
2666 : : /* Finally see if we have two known values. */
2667 : 234 : res = fold_build2 (code, type, nop0, nop1);
2668 : 234 : if (TREE_CODE (res) == INTEGER_CST)
2669 : : {
2670 : 160 : HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
2671 : 160 : HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
2672 : :
2673 : : /* If one of predictions is sure, such as PRED_UNCONDITIONAL, we
2674 : : can ignore it. */
2675 : 160 : if (p2 == PROB_ALWAYS)
2676 : : return res;
2677 : 142 : if (p1 == PROB_ALWAYS)
2678 : : {
2679 : 1 : *predictor = predictor2;
2680 : 1 : *probability = probability2;
2681 : 1 : return res;
2682 : : }
2683 : : /* Combine binary predictions.
2684 : : Since we do not know about independence of predictors, we
2685 : : can not determine value precisely. */
2686 : 141 : *probability = RDIV (p1 * p2, REG_BR_PROB_BASE);
2687 : : /* If we no longer track useful information, give up. */
2688 : 141 : if (!*probability)
2689 : : return NULL;
2690 : : /* Otherwise mark that prediction is a result of combining
2691 : : different heuristics, since we do not want it to participate
2692 : : in first match merging. It is no longer reliable since
2693 : : we do not know if the probabilities are indpenendet. */
2694 : 141 : *predictor = PRED_COMBINED_VALUE_PREDICTIONS;
2695 : :
2696 : 141 : return res;
2697 : : }
2698 : : return NULL;
2699 : : }
2700 : 558488 : if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2701 : : {
2702 : 557181 : tree res;
2703 : 557181 : op0 = expr_expected_value (op0, visited, predictor, probability);
2704 : 557181 : if (!op0)
2705 : : return NULL;
2706 : 29819 : res = fold_build1 (code, type, op0);
2707 : 29819 : if (TREE_CONSTANT (res))
2708 : : return res;
2709 : : return NULL;
2710 : : }
2711 : : return NULL;
2712 : : }
2713 : :
2714 : : /* Return constant EXPR will likely have at execution time, NULL if unknown.
2715 : : The function is used by builtin_expect branch predictor so the evidence
2716 : : must come from this construct and additional possible constant folding.
2717 : :
2718 : : We may want to implement more involved value guess (such as value range
2719 : : propagation based prediction), but such tricks shall go to new
2720 : : implementation. */
2721 : :
2722 : : static tree
2723 : 10310617 : expr_expected_value (tree expr, bitmap visited,
2724 : : enum br_predictor *predictor,
2725 : : HOST_WIDE_INT *probability)
2726 : : {
2727 : 10310617 : enum tree_code code;
2728 : 10310617 : tree op0, op1;
2729 : :
2730 : 10310617 : if (TREE_CONSTANT (expr))
2731 : : {
2732 : 999579 : *predictor = PRED_UNCONDITIONAL;
2733 : 999579 : *probability = -1;
2734 : 999579 : return expr;
2735 : : }
2736 : :
2737 : 9311038 : extract_ops_from_tree (expr, &code, &op0, &op1);
2738 : 9311038 : return expr_expected_value_1 (TREE_TYPE (expr),
2739 : : op0, code, op1, visited, predictor,
2740 : 9311038 : probability);
2741 : : }
2742 : :
2743 : :
2744 : : /* Return probability of a PREDICTOR. If the predictor has variable
2745 : : probability return passed PROBABILITY. */
2746 : :
2747 : : static HOST_WIDE_INT
2748 : 142065 : get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
2749 : : {
2750 : 142065 : switch (predictor)
2751 : : {
2752 : 70669 : case PRED_BUILTIN_EXPECT:
2753 : 70669 : case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
2754 : 70669 : case PRED_COMBINED_VALUE_PREDICTIONS_PHI:
2755 : 70669 : case PRED_COMBINED_VALUE_PREDICTIONS:
2756 : 70669 : gcc_assert (probability != -1);
2757 : : return probability;
2758 : 71396 : default:
2759 : 71396 : gcc_assert (probability == -1);
2760 : 71396 : return predictor_info[(int) predictor].hitrate;
2761 : : }
2762 : : }
2763 : :
2764 : : /* Predict using opcode of the last statement in basic block. */
2765 : : static void
2766 : 10416415 : tree_predict_by_opcode (basic_block bb)
2767 : : {
2768 : 10416415 : edge then_edge;
2769 : 10416415 : tree op0, op1;
2770 : 10416415 : tree type;
2771 : 10416415 : tree val;
2772 : 10416415 : enum tree_code cmp;
2773 : 10416415 : edge_iterator ei;
2774 : 10416415 : enum br_predictor predictor;
2775 : 10416415 : HOST_WIDE_INT probability;
2776 : :
2777 : 10416415 : gimple *stmt = *gsi_last_bb (bb);
2778 : 10416415 : if (!stmt)
2779 : 6989977 : return;
2780 : :
2781 : 9933181 : if (gswitch *sw = dyn_cast <gswitch *> (stmt))
2782 : : {
2783 : 26392 : tree index = gimple_switch_index (sw);
2784 : 26392 : tree val = expr_expected_value (index, auto_bitmap (),
2785 : : &predictor, &probability);
2786 : 26392 : if (val && TREE_CODE (val) == INTEGER_CST)
2787 : : {
2788 : 5 : edge e = find_taken_edge_switch_expr (sw, val);
2789 : 5 : if (predictor == PRED_BUILTIN_EXPECT)
2790 : : {
2791 : 5 : int percent = param_builtin_expect_probability;
2792 : 5 : gcc_assert (percent >= 0 && percent <= 100);
2793 : 5 : predict_edge (e, PRED_BUILTIN_EXPECT,
2794 : 5 : HITRATE (percent));
2795 : : }
2796 : : else
2797 : 0 : predict_edge_def (e, predictor, TAKEN);
2798 : : }
2799 : : }
2800 : :
2801 : 9933181 : if (gimple_code (stmt) != GIMPLE_COND)
2802 : : return;
2803 : 3556566 : FOR_EACH_EDGE (then_edge, ei, bb->succs)
2804 : 3556566 : if (then_edge->flags & EDGE_TRUE_VALUE)
2805 : : break;
2806 : 3426438 : op0 = gimple_cond_lhs (stmt);
2807 : 3426438 : op1 = gimple_cond_rhs (stmt);
2808 : 3426438 : cmp = gimple_cond_code (stmt);
2809 : 3426438 : type = TREE_TYPE (op0);
2810 : 3426438 : val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
2811 : : &predictor, &probability);
2812 : 3426438 : if (val && TREE_CODE (val) == INTEGER_CST)
2813 : : {
2814 : 112633 : HOST_WIDE_INT prob = get_predictor_value (predictor, probability);
2815 : 112633 : if (integer_zerop (val))
2816 : 90170 : prob = REG_BR_PROB_BASE - prob;
2817 : 112633 : predict_edge (then_edge, predictor, prob);
2818 : : }
2819 : : /* Try "pointer heuristic."
2820 : : A comparison ptr == 0 is predicted as false.
2821 : : Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2822 : 3426438 : if (POINTER_TYPE_P (type))
2823 : : {
2824 : 508653 : if (cmp == EQ_EXPR)
2825 : 200774 : predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2826 : 307879 : else if (cmp == NE_EXPR)
2827 : 292130 : predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
2828 : : }
2829 : : else
2830 : :
2831 : : /* Try "opcode heuristic."
2832 : : EQ tests are usually false and NE tests are usually true. Also,
2833 : : most quantities are positive, so we can make the appropriate guesses
2834 : : about signed comparisons against zero. */
2835 : 2917785 : switch (cmp)
2836 : : {
2837 : 804469 : case EQ_EXPR:
2838 : 804469 : case UNEQ_EXPR:
2839 : : /* Floating point comparisons appears to behave in a very
2840 : : unpredictable way because of special role of = tests in
2841 : : FP code. */
2842 : 804469 : if (FLOAT_TYPE_P (type))
2843 : : ;
2844 : : /* Comparisons with 0 are often used for booleans and there is
2845 : : nothing useful to predict about them. */
2846 : 795762 : else if (integer_zerop (op0) || integer_zerop (op1))
2847 : : ;
2848 : : else
2849 : 284518 : predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2850 : : break;
2851 : :
2852 : 1448948 : case NE_EXPR:
2853 : 1448948 : case LTGT_EXPR:
2854 : : /* Floating point comparisons appears to behave in a very
2855 : : unpredictable way because of special role of = tests in
2856 : : FP code. */
2857 : 1448948 : if (FLOAT_TYPE_P (type))
2858 : : ;
2859 : : /* Comparisons with 0 are often used for booleans and there is
2860 : : nothing useful to predict about them. */
2861 : 1333270 : else if (integer_zerop (op0)
2862 : 1333270 : || integer_zerop (op1))
2863 : : ;
2864 : : else
2865 : 508604 : predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2866 : : break;
2867 : :
2868 : 2671 : case ORDERED_EXPR:
2869 : 2671 : predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2870 : 2671 : break;
2871 : :
2872 : 2003 : case UNORDERED_EXPR:
2873 : 2003 : predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2874 : 2003 : break;
2875 : :
2876 : 286404 : case LE_EXPR:
2877 : 286404 : case LT_EXPR:
2878 : 286404 : if (integer_zerop (op1)
2879 : 246139 : || integer_onep (op1)
2880 : 239604 : || integer_all_onesp (op1)
2881 : 239539 : || real_zerop (op1)
2882 : 236470 : || real_onep (op1)
2883 : 522464 : || real_minus_onep (op1))
2884 : 50348 : predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2885 : : break;
2886 : :
2887 : 365776 : case GE_EXPR:
2888 : 365776 : case GT_EXPR:
2889 : 365776 : if (integer_zerop (op1)
2890 : 304991 : || integer_onep (op1)
2891 : 294414 : || integer_all_onesp (op1)
2892 : 294143 : || real_zerop (op1)
2893 : 292614 : || real_onep (op1)
2894 : 657547 : || real_minus_onep (op1))
2895 : 74047 : predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2896 : : break;
2897 : :
2898 : : default:
2899 : : break;
2900 : : }
2901 : : }
2902 : :
2903 : : /* Returns TRUE if the STMT is exit(0) like statement. */
2904 : :
2905 : : static bool
2906 : 653741 : is_exit_with_zero_arg (const gimple *stmt)
2907 : : {
2908 : : /* This is not exit, _exit or _Exit. */
2909 : 653741 : if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2910 : 650549 : && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2911 : 1304268 : && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2912 : : return false;
2913 : :
2914 : : /* Argument is an interger zero. */
2915 : 3214 : return integer_zerop (gimple_call_arg (stmt, 0));
2916 : : }
2917 : :
2918 : : /* Try to guess whether the value of return means error code. */
2919 : :
2920 : : static enum br_predictor
2921 : 594077 : return_prediction (tree val, enum prediction *prediction)
2922 : : {
2923 : : /* VOID. */
2924 : 594077 : if (!val)
2925 : : return PRED_NO_PREDICTION;
2926 : : /* Different heuristics for pointers and scalars. */
2927 : 594077 : if (POINTER_TYPE_P (TREE_TYPE (val)))
2928 : : {
2929 : : /* NULL is usually not returned. */
2930 : 118903 : if (integer_zerop (val))
2931 : : {
2932 : 24230 : *prediction = NOT_TAKEN;
2933 : 24230 : return PRED_NULL_RETURN;
2934 : : }
2935 : : }
2936 : 475174 : else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2937 : : {
2938 : : /* Negative return values are often used to indicate
2939 : : errors. */
2940 : 370832 : if (TREE_CODE (val) == INTEGER_CST
2941 : 370832 : && tree_int_cst_sgn (val) < 0)
2942 : : {
2943 : 10337 : *prediction = NOT_TAKEN;
2944 : 10337 : return PRED_NEGATIVE_RETURN;
2945 : : }
2946 : : /* Constant return values seems to be commonly taken.
2947 : : Zero/one often represent booleans so exclude them from the
2948 : : heuristics. */
2949 : 360495 : if (TREE_CONSTANT (val)
2950 : 360495 : && (!integer_zerop (val) && !integer_onep (val)))
2951 : : {
2952 : 69121 : *prediction = NOT_TAKEN;
2953 : 69121 : return PRED_CONST_RETURN;
2954 : : }
2955 : : }
2956 : : return PRED_NO_PREDICTION;
2957 : : }
2958 : :
2959 : : /* Return zero if phi result could have values other than -1, 0 or 1,
2960 : : otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2961 : : values are used or likely. */
2962 : :
2963 : : static int
2964 : 58646 : zero_one_minusone (gphi *phi, int limit)
2965 : : {
2966 : 58646 : int phi_num_args = gimple_phi_num_args (phi);
2967 : 58646 : int ret = 0;
2968 : 176926 : for (int i = 0; i < phi_num_args; i++)
2969 : : {
2970 : 128222 : tree t = PHI_ARG_DEF (phi, i);
2971 : 128222 : if (TREE_CODE (t) != INTEGER_CST)
2972 : 63784 : continue;
2973 : 64438 : wide_int w = wi::to_wide (t);
2974 : 64438 : if (w == -1)
2975 : 3830 : ret |= 1;
2976 : 60608 : else if (w == 0)
2977 : 30809 : ret |= 2;
2978 : 29799 : else if (w == 1)
2979 : 19857 : ret |= 4;
2980 : : else
2981 : 9942 : return 0;
2982 : 64438 : }
2983 : 99285 : for (int i = 0; i < phi_num_args; i++)
2984 : : {
2985 : 83409 : tree t = PHI_ARG_DEF (phi, i);
2986 : 83409 : if (TREE_CODE (t) == INTEGER_CST)
2987 : 48814 : continue;
2988 : 34595 : if (TREE_CODE (t) != SSA_NAME)
2989 : : return 0;
2990 : 34595 : gimple *g = SSA_NAME_DEF_STMT (t);
2991 : 34595 : if (gimple_code (g) == GIMPLE_PHI && limit > 0)
2992 : 11201 : if (int r = zero_one_minusone (as_a <gphi *> (g), limit - 1))
2993 : : {
2994 : 447 : ret |= r;
2995 : 447 : continue;
2996 : : }
2997 : 34148 : if (!is_gimple_assign (g))
2998 : : return 0;
2999 : 13166 : if (gimple_assign_cast_p (g))
3000 : : {
3001 : 3780 : tree rhs1 = gimple_assign_rhs1 (g);
3002 : 3780 : if (TREE_CODE (rhs1) != SSA_NAME
3003 : 3779 : || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
3004 : 3701 : || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
3005 : 5101 : || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
3006 : : return 0;
3007 : 1320 : ret |= (2 | 4);
3008 : 1320 : continue;
3009 : 1320 : }
3010 : 9386 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (g)) != tcc_comparison)
3011 : : return 0;
3012 : 0 : ret |= (2 | 4);
3013 : : }
3014 : : return ret;
3015 : : }
3016 : :
3017 : : /* Find the basic block with return expression and look up for possible
3018 : : return value trying to apply RETURN_PREDICTION heuristics. */
3019 : : static void
3020 : 2224504 : apply_return_prediction (void)
3021 : : {
3022 : 2224504 : greturn *return_stmt = NULL;
3023 : 2224504 : tree return_val;
3024 : 2224504 : edge e;
3025 : 2224504 : gphi *phi;
3026 : 2224504 : int phi_num_args, i;
3027 : 2224504 : enum br_predictor pred;
3028 : 2224504 : enum prediction direction;
3029 : 2224504 : edge_iterator ei;
3030 : :
3031 : 2290507 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3032 : : {
3033 : 6776545 : if (greturn *last = safe_dyn_cast <greturn *> (*gsi_last_bb (e->src)))
3034 : : {
3035 : : return_stmt = last;
3036 : : break;
3037 : : }
3038 : : }
3039 : 2224504 : if (!e)
3040 : 2063657 : return;
3041 : 2193080 : return_val = gimple_return_retval (return_stmt);
3042 : 2193080 : if (!return_val)
3043 : : return;
3044 : 1216067 : if (TREE_CODE (return_val) != SSA_NAME
3045 : 900095 : || !SSA_NAME_DEF_STMT (return_val)
3046 : 2116162 : || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
3047 : : return;
3048 : 161417 : phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
3049 : 161417 : phi_num_args = gimple_phi_num_args (phi);
3050 : 161417 : pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
3051 : :
3052 : : /* Avoid the case where the function returns -1, 0 and 1 values and
3053 : : nothing else. Those could be qsort etc. comparison functions
3054 : : where the negative return isn't less probable than positive.
3055 : : For this require that the function returns at least -1 or 1
3056 : : or -1 and a boolean value or comparison result, so that functions
3057 : : returning just -1 and 0 are treated as if -1 represents error value. */
3058 : 321741 : if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
3059 : 114732 : && !TYPE_UNSIGNED (TREE_TYPE (return_val))
3060 : 208862 : && TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
3061 : 47445 : if (int r = zero_one_minusone (phi, 3))
3062 : 15429 : if ((r & (1 | 4)) == (1 | 4))
3063 : : return;
3064 : :
3065 : : /* Avoid the degenerate case where all return values form the function
3066 : : belongs to same category (ie they are all positive constants)
3067 : : so we can hardly say something about them. */
3068 : 485459 : for (i = 1; i < phi_num_args; i++)
3069 : 353880 : if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
3070 : : break;
3071 : 160847 : if (i != phi_num_args)
3072 : 108048 : for (i = 0; i < phi_num_args; i++)
3073 : : {
3074 : 78780 : pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
3075 : 78780 : if (pred != PRED_NO_PREDICTION)
3076 : 37886 : predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
3077 : : direction);
3078 : : }
3079 : : }
3080 : :
3081 : : /* Look for basic block that contains unlikely to happen events
3082 : : (such as noreturn calls) and mark all paths leading to execution
3083 : : of this basic blocks as unlikely. */
3084 : :
3085 : : static void
3086 : 2224504 : tree_bb_level_predictions (void)
3087 : : {
3088 : 2224504 : basic_block bb;
3089 : 2224504 : bool has_return_edges = false;
3090 : 2224504 : edge e;
3091 : 2224504 : edge_iterator ei;
3092 : :
3093 : 2295232 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
3094 : 2262606 : if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
3095 : : {
3096 : : has_return_edges = true;
3097 : : break;
3098 : : }
3099 : :
3100 : 2224504 : apply_return_prediction ();
3101 : :
3102 : 12503133 : FOR_EACH_BB_FN (bb, cfun)
3103 : : {
3104 : 10278629 : gimple_stmt_iterator gsi;
3105 : :
3106 : 79814281 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3107 : : {
3108 : 59257023 : gimple *stmt = gsi_stmt (gsi);
3109 : 59257023 : tree decl;
3110 : :
3111 : 59257023 : if (is_gimple_call (stmt))
3112 : : {
3113 : 5551203 : if (gimple_call_noreturn_p (stmt)
3114 : 719648 : && has_return_edges
3115 : 6204944 : && !is_exit_with_zero_arg (stmt))
3116 : 651496 : predict_paths_leading_to (bb, PRED_NORETURN,
3117 : : NOT_TAKEN);
3118 : 5551203 : decl = gimple_call_fndecl (stmt);
3119 : 5551203 : if (decl
3120 : 10771089 : && lookup_attribute ("cold",
3121 : 5219886 : DECL_ATTRIBUTES (decl)))
3122 : 365069 : predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
3123 : : NOT_TAKEN);
3124 : 5551203 : if (decl && recursive_call_p (current_function_decl, decl))
3125 : 8876 : predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
3126 : : NOT_TAKEN);
3127 : : }
3128 : 53705820 : else if (gimple_code (stmt) == GIMPLE_PREDICT)
3129 : : {
3130 : 438075 : predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
3131 : : gimple_predict_outcome (stmt));
3132 : : /* Keep GIMPLE_PREDICT around so early inlining will propagate
3133 : : hints to callers. */
3134 : : }
3135 : : }
3136 : : }
3137 : 2224504 : }
3138 : :
3139 : : /* Callback for hash_map::traverse, asserts that the pointer map is
3140 : : empty. */
3141 : :
3142 : : bool
3143 : 3283980 : assert_is_empty (const_basic_block const &, edge_prediction *const &value,
3144 : : void *)
3145 : : {
3146 : 3283980 : gcc_assert (!value);
3147 : 3283980 : return true;
3148 : : }
3149 : :
3150 : : /* Predict branch probabilities and estimate profile for basic block BB.
3151 : : When LOCAL_ONLY is set do not use any global properties of CFG. */
3152 : :
3153 : : static void
3154 : 10416415 : tree_estimate_probability_bb (basic_block bb, bool local_only)
3155 : : {
3156 : 10416415 : edge e;
3157 : 10416415 : edge_iterator ei;
3158 : :
3159 : 24970530 : FOR_EACH_EDGE (e, ei, bb->succs)
3160 : : {
3161 : : /* Look for block we are guarding (ie we dominate it,
3162 : : but it doesn't postdominate us). */
3163 : 11583171 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
3164 : 11583156 : && !local_only
3165 : 11416423 : && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
3166 : 22018926 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
3167 : : {
3168 : 5802692 : gimple_stmt_iterator bi;
3169 : :
3170 : : /* The call heuristic claims that a guarded function call
3171 : : is improbable. This is because such calls are often used
3172 : : to signal exceptional situations such as printing error
3173 : : messages. */
3174 : 31860747 : for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
3175 : 20255363 : gsi_next (&bi))
3176 : : {
3177 : 22463246 : gimple *stmt = gsi_stmt (bi);
3178 : 22463246 : if (is_gimple_call (stmt)
3179 : 2684462 : && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
3180 : : /* Constant and pure calls are hardly used to signalize
3181 : : something exceptional. */
3182 : 25004849 : && gimple_has_side_effects (stmt))
3183 : : {
3184 : 2207883 : if (gimple_call_fndecl (stmt))
3185 : 2148215 : predict_edge_def (e, PRED_CALL, NOT_TAKEN);
3186 : 59668 : else if (virtual_method_call_p (gimple_call_fn (stmt)))
3187 : 12552 : predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
3188 : : else
3189 : 47116 : predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
3190 : : break;
3191 : : }
3192 : : }
3193 : : }
3194 : : }
3195 : 10416415 : tree_predict_by_opcode (bb);
3196 : 10416415 : }
3197 : :
3198 : : /* Predict branch probabilities and estimate profile of the tree CFG.
3199 : : This function can be called from the loop optimizers to recompute
3200 : : the profile information.
3201 : : If DRY_RUN is set, do not modify CFG and only produce dump files. */
3202 : :
3203 : : void
3204 : 2224504 : tree_estimate_probability (bool dry_run)
3205 : : {
3206 : 2224504 : basic_block bb;
3207 : :
3208 : 2224504 : connect_infinite_loops_to_exit ();
3209 : : /* We use loop_niter_by_eval, which requires that the loops have
3210 : : preheaders. */
3211 : 2224504 : create_preheaders (CP_SIMPLE_PREHEADERS);
3212 : 2224504 : calculate_dominance_info (CDI_POST_DOMINATORS);
3213 : : /* Decide which edges are known to be unlikely. This improves later
3214 : : branch prediction. */
3215 : 2224504 : determine_unlikely_bbs ();
3216 : :
3217 : 2224504 : bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3218 : 2224504 : tree_bb_level_predictions ();
3219 : 2224504 : record_loop_exits ();
3220 : :
3221 : 4449008 : if (number_of_loops (cfun) > 1)
3222 : 246921 : predict_loops ();
3223 : :
3224 : 12503133 : FOR_EACH_BB_FN (bb, cfun)
3225 : 10278629 : tree_estimate_probability_bb (bb, false);
3226 : :
3227 : 12503133 : FOR_EACH_BB_FN (bb, cfun)
3228 : 10278629 : combine_predictions_for_bb (bb, dry_run);
3229 : :
3230 : 2224504 : if (flag_checking)
3231 : 2224469 : bb_predictions->traverse<void *, assert_is_empty> (NULL);
3232 : :
3233 : 4449008 : delete bb_predictions;
3234 : 2224504 : bb_predictions = NULL;
3235 : :
3236 : 2224504 : if (!dry_run
3237 : 2224499 : && profile_status_for_fn (cfun) != PROFILE_READ)
3238 : 2224499 : estimate_bb_frequencies ();
3239 : 2224504 : free_dominance_info (CDI_POST_DOMINATORS);
3240 : 2224504 : remove_fake_exit_edges ();
3241 : 2224504 : }
3242 : :
3243 : : /* Set edge->probability for each successor edge of BB. */
3244 : : void
3245 : 137786 : tree_guess_outgoing_edge_probabilities (basic_block bb)
3246 : : {
3247 : 137786 : bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3248 : 137786 : tree_estimate_probability_bb (bb, true);
3249 : 137786 : combine_predictions_for_bb (bb, false);
3250 : 137786 : if (flag_checking)
3251 : 137786 : bb_predictions->traverse<void *, assert_is_empty> (NULL);
3252 : 275572 : delete bb_predictions;
3253 : 137786 : bb_predictions = NULL;
3254 : 137786 : }
3255 : :
3256 : : /* Filter function predicate that returns true for a edge predicate P
3257 : : if its edge is equal to DATA. */
3258 : :
3259 : : static bool
3260 : 8 : not_loop_guard_equal_edge_p (edge_prediction *p, void *data)
3261 : : {
3262 : 8 : return p->ep_edge != (edge)data || p->ep_predictor != PRED_LOOP_GUARD;
3263 : : }
3264 : :
3265 : : /* Predict edge E with PRED unless it is already predicted by some predictor
3266 : : considered equivalent. */
3267 : :
3268 : : static void
3269 : 1001481 : maybe_predict_edge (edge e, enum br_predictor pred, enum prediction taken)
3270 : : {
3271 : 1001481 : if (edge_predicted_by_p (e, pred, taken))
3272 : : return;
3273 : 997771 : if (pred == PRED_LOOP_GUARD
3274 : 997771 : && edge_predicted_by_p (e, PRED_LOOP_GUARD_WITH_RECURSION, taken))
3275 : : return;
3276 : : /* Consider PRED_LOOP_GUARD_WITH_RECURSION superrior to LOOP_GUARD. */
3277 : 997763 : if (pred == PRED_LOOP_GUARD_WITH_RECURSION)
3278 : : {
3279 : 15 : edge_prediction **preds = bb_predictions->get (e->src);
3280 : 15 : if (preds)
3281 : 4 : filter_predictions (preds, not_loop_guard_equal_edge_p, e);
3282 : : }
3283 : 997763 : predict_edge_def (e, pred, taken);
3284 : : }
3285 : : /* Predict edges to successors of CUR whose sources are not postdominated by
3286 : : BB by PRED and recurse to all postdominators. */
3287 : :
3288 : : static void
3289 : 2004729 : predict_paths_for_bb (basic_block cur, basic_block bb,
3290 : : enum br_predictor pred,
3291 : : enum prediction taken,
3292 : : bitmap visited, class loop *in_loop = NULL)
3293 : : {
3294 : 2004729 : edge e;
3295 : 2004729 : edge_iterator ei;
3296 : 2004729 : basic_block son;
3297 : :
3298 : : /* If we exited the loop or CUR is unconditional in the loop, there is
3299 : : nothing to do. */
3300 : 2004729 : if (in_loop
3301 : 2004729 : && (!flow_bb_inside_loop_p (in_loop, cur)
3302 : 64973 : || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
3303 : 9695 : return;
3304 : :
3305 : : /* We are looking for all edges forming edge cut induced by
3306 : : set of all blocks postdominated by BB. */
3307 : 4480373 : FOR_EACH_EDGE (e, ei, cur->preds)
3308 : 2485339 : if (e->src->index >= NUM_FIXED_BLOCKS
3309 : 2485339 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
3310 : : {
3311 : 1839830 : edge e2;
3312 : 1839830 : edge_iterator ei2;
3313 : 1839830 : bool found = false;
3314 : :
3315 : : /* Ignore fake edges and eh, we predict them as not taken anyway. */
3316 : 1839830 : if (unlikely_executed_edge_p (e))
3317 : 831518 : continue;
3318 : 1008312 : gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
3319 : :
3320 : : /* See if there is an edge from e->src that is not abnormal
3321 : : and does not lead to BB and does not exit the loop. */
3322 : 1879764 : FOR_EACH_EDGE (e2, ei2, e->src->succs)
3323 : 1847209 : if (e2 != e
3324 : 1015004 : && !unlikely_executed_edge_p (e2)
3325 : 984693 : && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
3326 : 2825723 : && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
3327 : : {
3328 : : found = true;
3329 : : break;
3330 : : }
3331 : :
3332 : : /* If there is non-abnormal path leaving e->src, predict edge
3333 : : using predictor. Otherwise we need to look for paths
3334 : : leading to e->src.
3335 : :
3336 : : The second may lead to infinite loop in the case we are predicitng
3337 : : regions that are only reachable by abnormal edges. We simply
3338 : : prevent visiting given BB twice. */
3339 : 1008312 : if (found)
3340 : 975757 : maybe_predict_edge (e, pred, taken);
3341 : 32555 : else if (bitmap_set_bit (visited, e->src->index))
3342 : 32514 : predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
3343 : : }
3344 : 1995034 : for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
3345 : 2447640 : son;
3346 : 452606 : son = next_dom_son (CDI_POST_DOMINATORS, son))
3347 : 452606 : predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
3348 : : }
3349 : :
3350 : : /* Sets branch probabilities according to PREDiction and
3351 : : FLAGS. */
3352 : :
3353 : : static void
3354 : 1463516 : predict_paths_leading_to (basic_block bb, enum br_predictor pred,
3355 : : enum prediction taken, class loop *in_loop)
3356 : : {
3357 : 1463516 : predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3358 : 1463516 : }
3359 : :
3360 : : /* Like predict_paths_leading_to but take edge instead of basic block. */
3361 : :
3362 : : static void
3363 : 81817 : predict_paths_leading_to_edge (edge e, enum br_predictor pred,
3364 : : enum prediction taken, class loop *in_loop)
3365 : : {
3366 : 81817 : bool has_nonloop_edge = false;
3367 : 81817 : edge_iterator ei;
3368 : 81817 : edge e2;
3369 : :
3370 : 81817 : basic_block bb = e->src;
3371 : 154928 : FOR_EACH_EDGE (e2, ei, bb->succs)
3372 : 98835 : if (e2->dest != e->src && e2->dest != e->dest
3373 : 35385 : && !unlikely_executed_edge_p (e2)
3374 : 132646 : && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
3375 : : {
3376 : : has_nonloop_edge = true;
3377 : : break;
3378 : : }
3379 : :
3380 : 81817 : if (!has_nonloop_edge)
3381 : 56093 : predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3382 : : else
3383 : 25724 : maybe_predict_edge (e, pred, taken);
3384 : 81817 : }
3385 : :
3386 : : /* This is used to carry information about basic blocks. It is
3387 : : attached to the AUX field of the standard CFG block. */
3388 : :
3389 : : class block_info
3390 : : {
3391 : : public:
3392 : : /* Estimated frequency of execution of basic_block. */
3393 : : sreal frequency;
3394 : :
3395 : : /* To keep queue of basic blocks to process. */
3396 : : basic_block next;
3397 : :
3398 : : /* Number of predecessors we need to visit first. */
3399 : : int npredecessors;
3400 : : };
3401 : :
3402 : : /* Similar information for edges. */
3403 : : class edge_prob_info
3404 : : {
3405 : : public:
3406 : : /* In case edge is a loopback edge, the probability edge will be reached
3407 : : in case header is. Estimated number of iterations of the loop can be
3408 : : then computed as 1 / (1 - back_edge_prob). */
3409 : : sreal back_edge_prob;
3410 : : /* True if the edge is a loopback edge in the natural loop. */
3411 : : unsigned int back_edge:1;
3412 : : };
3413 : :
3414 : : #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3415 : : #undef EDGE_INFO
3416 : : #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3417 : :
3418 : : /* Helper function for estimate_bb_frequencies.
3419 : : Propagate the frequencies in blocks marked in
3420 : : TOVISIT, starting in HEAD. */
3421 : :
3422 : : static void
3423 : 2959417 : propagate_freq (basic_block head, bitmap tovisit,
3424 : : sreal max_cyclic_prob)
3425 : : {
3426 : 2959417 : basic_block bb;
3427 : 2959417 : basic_block last;
3428 : 2959417 : unsigned i;
3429 : 2959417 : edge e;
3430 : 2959417 : basic_block nextbb;
3431 : 2959417 : bitmap_iterator bi;
3432 : :
3433 : : /* For each basic block we need to visit count number of his predecessors
3434 : : we need to visit first. */
3435 : 23365761 : EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3436 : : {
3437 : 20406344 : edge_iterator ei;
3438 : 20406344 : int count = 0;
3439 : :
3440 : 20406344 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
3441 : :
3442 : 45128434 : FOR_EACH_EDGE (e, ei, bb->preds)
3443 : : {
3444 : 24722090 : bool visit = bitmap_bit_p (tovisit, e->src->index);
3445 : :
3446 : 24722090 : if (visit && !(e->flags & EDGE_DFS_BACK))
3447 : 22410922 : count++;
3448 : 1626710 : else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
3449 : 3 : fprintf (dump_file,
3450 : : "Irreducible region hit, ignoring edge to %i->%i\n",
3451 : 3 : e->src->index, bb->index);
3452 : : }
3453 : 20406344 : BLOCK_INFO (bb)->npredecessors = count;
3454 : : /* When function never returns, we will never process exit block. */
3455 : 20406344 : if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3456 : 0 : bb->count = profile_count::zero ();
3457 : : }
3458 : :
3459 : 2959417 : BLOCK_INFO (head)->frequency = 1;
3460 : 2959417 : last = head;
3461 : 23365761 : for (bb = head; bb; bb = nextbb)
3462 : : {
3463 : 20406344 : edge_iterator ei;
3464 : 20406344 : sreal cyclic_probability = 0;
3465 : 20406344 : sreal frequency = 0;
3466 : :
3467 : 20406344 : nextbb = BLOCK_INFO (bb)->next;
3468 : 20406344 : BLOCK_INFO (bb)->next = NULL;
3469 : :
3470 : : /* Compute frequency of basic block. */
3471 : 20406344 : if (bb != head)
3472 : : {
3473 : 17446927 : if (flag_checking)
3474 : 40799268 : FOR_EACH_EDGE (e, ei, bb->preds)
3475 : 23352748 : gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3476 : : || (e->flags & EDGE_DFS_BACK));
3477 : :
3478 : 40800255 : FOR_EACH_EDGE (e, ei, bb->preds)
3479 : 23353328 : if (EDGE_INFO (e)->back_edge)
3480 : 937928 : cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3481 : 22415400 : else if (!(e->flags & EDGE_DFS_BACK))
3482 : : {
3483 : : /* FIXME: Graphite is producing edges with no profile. Once
3484 : : this is fixed, drop this. */
3485 : 22410922 : sreal tmp = e->probability.initialized_p () ?
3486 : 22410922 : e->probability.to_sreal () : 0;
3487 : 22410922 : frequency += tmp * BLOCK_INFO (e->src)->frequency;
3488 : : }
3489 : :
3490 : 17446927 : if (cyclic_probability == 0)
3491 : : {
3492 : 16534579 : BLOCK_INFO (bb)->frequency = frequency;
3493 : : }
3494 : : else
3495 : : {
3496 : 912348 : if (cyclic_probability > max_cyclic_prob)
3497 : : {
3498 : 9638 : if (dump_file)
3499 : 247 : fprintf (dump_file,
3500 : : "cyclic probability of bb %i is %f (capped to %f)"
3501 : : "; turning freq %f",
3502 : : bb->index, cyclic_probability.to_double (),
3503 : : max_cyclic_prob.to_double (),
3504 : : frequency.to_double ());
3505 : :
3506 : 9638 : cyclic_probability = max_cyclic_prob;
3507 : : }
3508 : 902710 : else if (dump_file)
3509 : 108 : fprintf (dump_file,
3510 : : "cyclic probability of bb %i is %f; turning freq %f",
3511 : : bb->index, cyclic_probability.to_double (),
3512 : : frequency.to_double ());
3513 : :
3514 : 912348 : BLOCK_INFO (bb)->frequency = frequency
3515 : 912348 : / (sreal (1) - cyclic_probability);
3516 : 912348 : if (dump_file)
3517 : 355 : fprintf (dump_file, " to %f\n",
3518 : 355 : BLOCK_INFO (bb)->frequency.to_double ());
3519 : : }
3520 : : }
3521 : :
3522 : 20406344 : bitmap_clear_bit (tovisit, bb->index);
3523 : :
3524 : 20406344 : e = find_edge (bb, head);
3525 : 20406344 : if (e)
3526 : : {
3527 : : /* FIXME: Graphite is producing edges with no profile. Once
3528 : : this is fixed, drop this. */
3529 : 684304 : sreal tmp = e->probability.initialized_p () ?
3530 : 684304 : e->probability.to_sreal () : 0;
3531 : 684304 : EDGE_INFO (e)->back_edge_prob = tmp * BLOCK_INFO (bb)->frequency;
3532 : : }
3533 : :
3534 : : /* Propagate to successor blocks. */
3535 : 45675560 : FOR_EACH_EDGE (e, ei, bb->succs)
3536 : 25269216 : if (!(e->flags & EDGE_DFS_BACK)
3537 : 23641754 : && BLOCK_INFO (e->dest)->npredecessors)
3538 : : {
3539 : 22410922 : BLOCK_INFO (e->dest)->npredecessors--;
3540 : 22410922 : if (!BLOCK_INFO (e->dest)->npredecessors)
3541 : : {
3542 : 17446927 : if (!nextbb)
3543 : : nextbb = e->dest;
3544 : : else
3545 : 6349220 : BLOCK_INFO (last)->next = e->dest;
3546 : :
3547 : : last = e->dest;
3548 : : }
3549 : : }
3550 : : }
3551 : 2959417 : }
3552 : :
3553 : : /* Estimate frequencies in loops at same nest level. */
3554 : :
3555 : : static void
3556 : 959657 : estimate_loops_at_level (class loop *first_loop, sreal max_cyclic_prob)
3557 : : {
3558 : 959657 : class loop *loop;
3559 : :
3560 : 1643961 : for (loop = first_loop; loop; loop = loop->next)
3561 : : {
3562 : 684304 : edge e;
3563 : 684304 : basic_block *bbs;
3564 : 684304 : unsigned i;
3565 : 684304 : auto_bitmap tovisit;
3566 : :
3567 : 684304 : estimate_loops_at_level (loop->inner, max_cyclic_prob);
3568 : :
3569 : : /* Find current loop back edge and mark it. */
3570 : 684304 : e = loop_latch_edge (loop);
3571 : 684304 : EDGE_INFO (e)->back_edge = 1;
3572 : :
3573 : 684304 : bbs = get_loop_body (loop);
3574 : 5105754 : for (i = 0; i < loop->num_nodes; i++)
3575 : 3737146 : bitmap_set_bit (tovisit, bbs[i]->index);
3576 : 684304 : free (bbs);
3577 : 684304 : propagate_freq (loop->header, tovisit, max_cyclic_prob);
3578 : 684304 : }
3579 : 959657 : }
3580 : :
3581 : : /* Propagates frequencies through structure of loops. */
3582 : :
3583 : : static void
3584 : 2275113 : estimate_loops (void)
3585 : : {
3586 : 2275113 : auto_bitmap tovisit;
3587 : 2275113 : basic_block bb;
3588 : 6825339 : sreal max_cyclic_prob = (sreal)1
3589 : 2275113 : - (sreal)1 / (param_max_predicted_iterations + 1);
3590 : :
3591 : : /* Start by estimating the frequencies in the loops. */
3592 : 4550226 : if (number_of_loops (cfun) > 1)
3593 : 275353 : estimate_loops_at_level (current_loops->tree_root->inner, max_cyclic_prob);
3594 : :
3595 : : /* Now propagate the frequencies through all the blocks. */
3596 : 18944311 : FOR_ALL_BB_FN (bb, cfun)
3597 : : {
3598 : 16669198 : bitmap_set_bit (tovisit, bb->index);
3599 : : }
3600 : 2275113 : propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit, max_cyclic_prob);
3601 : 2275113 : }
3602 : :
3603 : : /* Drop the profile for NODE to guessed, and update its frequency based on
3604 : : whether it is expected to be hot given the CALL_COUNT. */
3605 : :
3606 : : static void
3607 : 0 : drop_profile (struct cgraph_node *node, profile_count call_count)
3608 : : {
3609 : 0 : struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3610 : : /* In the case where this was called by another function with a
3611 : : dropped profile, call_count will be 0. Since there are no
3612 : : non-zero call counts to this function, we don't know for sure
3613 : : whether it is hot, and therefore it will be marked normal below. */
3614 : 0 : bool hot = maybe_hot_count_p (NULL, call_count);
3615 : :
3616 : 0 : if (dump_file)
3617 : 0 : fprintf (dump_file,
3618 : : "Dropping 0 profile for %s. %s based on calls.\n",
3619 : : node->dump_name (),
3620 : : hot ? "Function is hot" : "Function is normal");
3621 : : /* We only expect to miss profiles for functions that are reached
3622 : : via non-zero call edges in cases where the function may have
3623 : : been linked from another module or library (COMDATs and extern
3624 : : templates). See the comments below for handle_missing_profiles.
3625 : : Also, only warn in cases where the missing counts exceed the
3626 : : number of training runs. In certain cases with an execv followed
3627 : : by a no-return call the profile for the no-return call is not
3628 : : dumped and there can be a mismatch. */
3629 : 0 : if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3630 : 0 : && call_count > profile_info->runs)
3631 : : {
3632 : 0 : if (flag_profile_correction)
3633 : : {
3634 : 0 : if (dump_file)
3635 : 0 : fprintf (dump_file,
3636 : : "Missing counts for called function %s\n",
3637 : : node->dump_name ());
3638 : : }
3639 : : else
3640 : 0 : warning (0, "Missing counts for called function %s",
3641 : : node->dump_name ());
3642 : : }
3643 : :
3644 : 0 : basic_block bb;
3645 : 0 : if (opt_for_fn (node->decl, flag_guess_branch_prob))
3646 : : {
3647 : 0 : bool clear_zeros
3648 : 0 : = !ENTRY_BLOCK_PTR_FOR_FN (fn)->count.nonzero_p ();
3649 : 0 : FOR_ALL_BB_FN (bb, fn)
3650 : 0 : if (clear_zeros || !(bb->count == profile_count::zero ()))
3651 : 0 : bb->count = bb->count.guessed_local ();
3652 : 0 : fn->cfg->count_max = fn->cfg->count_max.guessed_local ();
3653 : : }
3654 : : else
3655 : : {
3656 : 0 : FOR_ALL_BB_FN (bb, fn)
3657 : 0 : bb->count = profile_count::uninitialized ();
3658 : 0 : fn->cfg->count_max = profile_count::uninitialized ();
3659 : : }
3660 : :
3661 : 0 : struct cgraph_edge *e;
3662 : 0 : for (e = node->callees; e; e = e->next_callee)
3663 : 0 : e->count = gimple_bb (e->call_stmt)->count;
3664 : 0 : for (e = node->indirect_calls; e; e = e->next_callee)
3665 : 0 : e->count = gimple_bb (e->call_stmt)->count;
3666 : 0 : node->count = ENTRY_BLOCK_PTR_FOR_FN (fn)->count;
3667 : :
3668 : 0 : profile_status_for_fn (fn)
3669 : 0 : = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3670 : 0 : node->frequency
3671 : 0 : = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3672 : 0 : }
3673 : :
3674 : : /* In the case of COMDAT routines, multiple object files will contain the same
3675 : : function and the linker will select one for the binary. In that case
3676 : : all the other copies from the profile instrument binary will be missing
3677 : : profile counts. Look for cases where this happened, due to non-zero
3678 : : call counts going to 0-count functions, and drop the profile to guessed
3679 : : so that we can use the estimated probabilities and avoid optimizing only
3680 : : for size.
3681 : :
3682 : : The other case where the profile may be missing is when the routine
3683 : : is not going to be emitted to the object file, e.g. for "extern template"
3684 : : class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3685 : : all other cases of non-zero calls to 0-count functions. */
3686 : :
3687 : : void
3688 : 583 : handle_missing_profiles (void)
3689 : : {
3690 : 583 : const int unlikely_frac = param_unlikely_bb_count_fraction;
3691 : 583 : struct cgraph_node *node;
3692 : 583 : auto_vec<struct cgraph_node *, 64> worklist;
3693 : :
3694 : : /* See if 0 count function has non-0 count callers. In this case we
3695 : : lost some profile. Drop its function profile to PROFILE_GUESSED. */
3696 : 3095 : FOR_EACH_DEFINED_FUNCTION (node)
3697 : : {
3698 : 2512 : struct cgraph_edge *e;
3699 : 2512 : profile_count call_count = profile_count::zero ();
3700 : 2512 : gcov_type max_tp_first_run = 0;
3701 : 2512 : struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3702 : :
3703 : 2512 : if (node->count.ipa ().nonzero_p ())
3704 : 340 : continue;
3705 : 4140 : for (e = node->callers; e; e = e->next_caller)
3706 : 1968 : if (e->count.ipa ().initialized_p () && e->count.ipa () > 0)
3707 : : {
3708 : 8 : call_count = call_count + e->count.ipa ();
3709 : :
3710 : 8 : if (e->caller->tp_first_run > max_tp_first_run)
3711 : 1968 : max_tp_first_run = e->caller->tp_first_run;
3712 : : }
3713 : :
3714 : : /* If time profile is missing, let assign the maximum that comes from
3715 : : caller functions. */
3716 : 2172 : if (!node->tp_first_run && max_tp_first_run)
3717 : 4 : node->tp_first_run = max_tp_first_run + 1;
3718 : :
3719 : 2172 : if (call_count > 0
3720 : 6 : && fn && fn->cfg
3721 : 2178 : && call_count * unlikely_frac >= profile_info->runs)
3722 : : {
3723 : 0 : drop_profile (node, call_count);
3724 : 0 : worklist.safe_push (node);
3725 : : }
3726 : : }
3727 : :
3728 : : /* Propagate the profile dropping to other 0-count COMDATs that are
3729 : : potentially called by COMDATs we already dropped the profile on. */
3730 : 583 : while (worklist.length () > 0)
3731 : : {
3732 : 0 : struct cgraph_edge *e;
3733 : :
3734 : 0 : node = worklist.pop ();
3735 : 0 : for (e = node->callees; e; e = e->next_caller)
3736 : : {
3737 : 0 : struct cgraph_node *callee = e->callee;
3738 : 0 : struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3739 : :
3740 : 0 : if (!(e->count.ipa () == profile_count::zero ())
3741 : 0 : && callee->count.ipa ().nonzero_p ())
3742 : 0 : continue;
3743 : 0 : if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
3744 : 0 : && fn && fn->cfg
3745 : 0 : && profile_status_for_fn (fn) == PROFILE_READ)
3746 : : {
3747 : 0 : drop_profile (node, profile_count::zero ());
3748 : 0 : worklist.safe_push (callee);
3749 : : }
3750 : : }
3751 : : }
3752 : 583 : }
3753 : :
3754 : : /* Convert counts measured by profile driven feedback to frequencies.
3755 : : Return nonzero iff there was any nonzero execution count. */
3756 : :
3757 : : bool
3758 : 1484827 : update_max_bb_count (void)
3759 : : {
3760 : 1484827 : profile_count true_count_max = profile_count::uninitialized ();
3761 : 1484827 : basic_block bb;
3762 : :
3763 : 29669794 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3764 : 28184967 : true_count_max = true_count_max.max (bb->count);
3765 : :
3766 : 1484827 : cfun->cfg->count_max = true_count_max;
3767 : :
3768 : 1484827 : return true_count_max.ipa ().nonzero_p ();
3769 : : }
3770 : :
3771 : : /* Return true if function is likely to be expensive, so there is no point to
3772 : : optimize performance of prologue, epilogue or do inlining at the expense
3773 : : of code size growth. THRESHOLD is the limit of number of instructions
3774 : : function can execute at average to be still considered not expensive. */
3775 : :
3776 : : bool
3777 : 282683 : expensive_function_p (int threshold)
3778 : : {
3779 : 282683 : basic_block bb;
3780 : :
3781 : : /* If profile was scaled in a way entry block has count 0, then the function
3782 : : is deifnitly taking a lot of time. */
3783 : 425092 : if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3784 : : return true;
3785 : :
3786 : 241796 : profile_count limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count * threshold;
3787 : 241796 : profile_count sum = profile_count::zero ();
3788 : 2924914 : FOR_EACH_BB_FN (bb, cfun)
3789 : : {
3790 : 2825527 : rtx_insn *insn;
3791 : :
3792 : 2825527 : if (!bb->count.initialized_p ())
3793 : : {
3794 : 8 : if (dump_file)
3795 : 0 : fprintf (dump_file, "Function is considered expensive because"
3796 : : " count of bb %i is not initialized\n", bb->index);
3797 : 8 : return true;
3798 : : }
3799 : :
3800 : 40960499 : FOR_BB_INSNS (bb, insn)
3801 : 38277381 : if (active_insn_p (insn))
3802 : : {
3803 : 16384065 : sum += bb->count;
3804 : 16384065 : if (sum > limit)
3805 : : return true;
3806 : : }
3807 : : }
3808 : :
3809 : : return false;
3810 : : }
3811 : :
3812 : : /* All basic blocks that are reachable only from unlikely basic blocks are
3813 : : unlikely. */
3814 : :
3815 : : void
3816 : 5741657 : propagate_unlikely_bbs_forward (void)
3817 : : {
3818 : 5741657 : auto_vec<basic_block, 64> worklist;
3819 : 5741657 : basic_block bb;
3820 : 5741657 : edge_iterator ei;
3821 : 5741657 : edge e;
3822 : :
3823 : 5756631 : if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3824 : : {
3825 : 5726683 : ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3826 : 5726683 : worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3827 : :
3828 : 59841887 : while (worklist.length () > 0)
3829 : : {
3830 : 48388521 : bb = worklist.pop ();
3831 : 107049591 : FOR_EACH_EDGE (e, ei, bb->succs)
3832 : 59779491 : if (!(e->count () == profile_count::zero ())
3833 : 70428455 : && !(e->dest->count == profile_count::zero ())
3834 : 53870946 : && !e->dest->aux)
3835 : : {
3836 : 42661838 : e->dest->aux = (void *)(size_t) 1;
3837 : 42661838 : worklist.safe_push (e->dest);
3838 : : }
3839 : : }
3840 : : }
3841 : :
3842 : 56765796 : FOR_ALL_BB_FN (bb, cfun)
3843 : : {
3844 : 51024139 : if (!bb->aux)
3845 : : {
3846 : 5270505 : if (!(bb->count == profile_count::zero ())
3847 : 376336 : && (dump_file && (dump_flags & TDF_DETAILS)))
3848 : 731 : fprintf (dump_file,
3849 : : "Basic block %i is marked unlikely by forward prop\n",
3850 : : bb->index);
3851 : 2635618 : bb->count = profile_count::zero ();
3852 : : }
3853 : : else
3854 : 48388521 : bb->aux = NULL;
3855 : : }
3856 : 5741657 : }
3857 : :
3858 : : /* Determine basic blocks/edges that are known to be unlikely executed and set
3859 : : their counters to zero.
3860 : : This is done with first identifying obviously unlikely BBs/edges and then
3861 : : propagating in both directions. */
3862 : :
3863 : : static void
3864 : 4499617 : determine_unlikely_bbs ()
3865 : : {
3866 : 4499617 : basic_block bb;
3867 : 4499617 : auto_vec<basic_block, 64> worklist;
3868 : 4499617 : edge_iterator ei;
3869 : 4499617 : edge e;
3870 : :
3871 : 26897218 : FOR_EACH_BB_FN (bb, cfun)
3872 : : {
3873 : 44474180 : if (!(bb->count == profile_count::zero ())
3874 : 21587736 : && unlikely_executed_bb_p (bb))
3875 : : {
3876 : 321022 : if (dump_file && (dump_flags & TDF_DETAILS))
3877 : 0 : fprintf (dump_file, "Basic block %i is locally unlikely\n",
3878 : : bb->index);
3879 : 321022 : bb->count = profile_count::zero ();
3880 : : }
3881 : :
3882 : 53959683 : FOR_EACH_EDGE (e, ei, bb->succs)
3883 : 63124164 : if (!(e->probability == profile_probability::never ())
3884 : 29223362 : && unlikely_executed_edge_p (e))
3885 : : {
3886 : 1636345 : if (dump_file && (dump_flags & TDF_DETAILS))
3887 : 40 : fprintf (dump_file, "Edge %i->%i is locally unlikely\n",
3888 : 40 : bb->index, e->dest->index);
3889 : 1636345 : e->probability = profile_probability::never ();
3890 : : }
3891 : :
3892 : 22397601 : gcc_checking_assert (!bb->aux);
3893 : : }
3894 : 4499617 : propagate_unlikely_bbs_forward ();
3895 : :
3896 : 4499617 : auto_vec<int, 64> nsuccs;
3897 : 4499617 : nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
3898 : 35896452 : FOR_ALL_BB_FN (bb, cfun)
3899 : 37293503 : if (!(bb->count == profile_count::zero ())
3900 : 29922998 : && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3901 : : {
3902 : 25500167 : nsuccs[bb->index] = 0;
3903 : 60057567 : FOR_EACH_EDGE (e, ei, bb->succs)
3904 : 34570647 : if (!(e->probability == profile_probability::never ())
3905 : 35011858 : && !(e->dest->count == profile_count::zero ()))
3906 : 31480613 : nsuccs[bb->index]++;
3907 : 25500167 : if (!nsuccs[bb->index])
3908 : 917465 : worklist.safe_push (bb);
3909 : : }
3910 : 5418699 : while (worklist.length () > 0)
3911 : : {
3912 : 919082 : bb = worklist.pop ();
3913 : 919082 : if (bb->count == profile_count::zero ())
3914 : 0 : continue;
3915 : 919082 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3916 : : {
3917 : 907384 : bool found = false;
3918 : 1814768 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
3919 : 1521247 : !gsi_end_p (gsi); gsi_next (&gsi))
3920 : 1518190 : if (stmt_can_terminate_bb_p (gsi_stmt (gsi))
3921 : : /* stmt_can_terminate_bb_p special cases noreturns because it
3922 : : assumes that fake edges are created. We want to know that
3923 : : noreturn alone does not imply BB to be unlikely. */
3924 : 1518190 : || (is_gimple_call (gsi_stmt (gsi))
3925 : 382561 : && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
3926 : : {
3927 : : found = true;
3928 : : break;
3929 : : }
3930 : 907384 : if (found)
3931 : 904327 : continue;
3932 : : }
3933 : 14755 : if (dump_file && (dump_flags & TDF_DETAILS))
3934 : 0 : fprintf (dump_file,
3935 : : "Basic block %i is marked unlikely by backward prop\n",
3936 : : bb->index);
3937 : 14755 : bb->count = profile_count::zero ();
3938 : 18827 : FOR_EACH_EDGE (e, ei, bb->preds)
3939 : 8144 : if (!(e->probability == profile_probability::never ()))
3940 : : {
3941 : 3273 : if (!(e->src->count == profile_count::zero ()))
3942 : : {
3943 : 3273 : gcc_checking_assert (nsuccs[e->src->index] > 0);
3944 : 3273 : nsuccs[e->src->index]--;
3945 : 3273 : if (!nsuccs[e->src->index])
3946 : 1617 : worklist.safe_push (e->src);
3947 : : }
3948 : : }
3949 : : }
3950 : : /* Finally all edges from non-0 regions to 0 are unlikely. */
3951 : 35896452 : FOR_ALL_BB_FN (bb, cfun)
3952 : : {
3953 : 32885427 : if (!(bb->count == profile_count::zero ()))
3954 : 64448392 : FOR_EACH_EDGE (e, ei, bb->succs)
3955 : 34553389 : if (!(e->probability == profile_probability::never ())
3956 : 34602349 : && e->dest->count == profile_count::zero ())
3957 : : {
3958 : 440627 : if (dump_file && (dump_flags & TDF_DETAILS))
3959 : 0 : fprintf (dump_file, "Edge %i->%i is unlikely because "
3960 : : "it enters unlikely block\n",
3961 : : bb->index, e->dest->index);
3962 : 440627 : e->probability = profile_probability::never ();
3963 : : }
3964 : :
3965 : 31396835 : edge other = NULL;
3966 : :
3967 : 60531154 : FOR_EACH_EDGE (e, ei, bb->succs)
3968 : 64979322 : if (e->probability == profile_probability::never ())
3969 : : ;
3970 : 31440998 : else if (other)
3971 : : {
3972 : : other = NULL;
3973 : : break;
3974 : : }
3975 : : else
3976 : : other = e;
3977 : 31396835 : if (other
3978 : 49416465 : && !(other->probability == profile_probability::always ()))
3979 : : {
3980 : 7688685 : if (dump_file && (dump_flags & TDF_DETAILS))
3981 : 6 : fprintf (dump_file, "Edge %i->%i is locally likely\n",
3982 : 6 : bb->index, other->dest->index);
3983 : 7688685 : other->probability = profile_probability::always ();
3984 : : }
3985 : : }
3986 : 4499617 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
3987 : 23281 : cgraph_node::get (current_function_decl)->count = profile_count::zero ();
3988 : 4499617 : }
3989 : :
3990 : : /* Estimate and propagate basic block frequencies using the given branch
3991 : : probabilities. */
3992 : :
3993 : : static void
3994 : 2275113 : estimate_bb_frequencies ()
3995 : : {
3996 : 2275113 : basic_block bb;
3997 : 2275113 : sreal freq_max;
3998 : :
3999 : 2275113 : determine_unlikely_bbs ();
4000 : :
4001 : 2275113 : mark_dfs_back_edges ();
4002 : :
4003 : 2275113 : single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
4004 : : profile_probability::always ();
4005 : :
4006 : : /* Set up block info for each basic block. */
4007 : 2275113 : alloc_aux_for_blocks (sizeof (block_info));
4008 : 2275113 : alloc_aux_for_edges (sizeof (edge_prob_info));
4009 : 18944311 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4010 : : {
4011 : 16669198 : edge e;
4012 : 16669198 : edge_iterator ei;
4013 : :
4014 : 36119011 : FOR_EACH_EDGE (e, ei, bb->succs)
4015 : : {
4016 : : /* FIXME: Graphite is producing edges with no profile. Once
4017 : : this is fixed, drop this. */
4018 : 19449813 : if (e->probability.initialized_p ())
4019 : 19449781 : EDGE_INFO (e)->back_edge_prob
4020 : 19449781 : = e->probability.to_sreal ();
4021 : : else
4022 : : /* back_edge_prob = 0.5 */
4023 : 32 : EDGE_INFO (e)->back_edge_prob = sreal (1, -1);
4024 : : }
4025 : : }
4026 : :
4027 : : /* First compute frequencies locally for each loop from innermost
4028 : : to outermost to examine frequencies for back edges. */
4029 : 2275113 : estimate_loops ();
4030 : :
4031 : 2275113 : freq_max = 0;
4032 : 14394085 : FOR_EACH_BB_FN (bb, cfun)
4033 : 12118972 : if (freq_max < BLOCK_INFO (bb)->frequency)
4034 : 2860561 : freq_max = BLOCK_INFO (bb)->frequency;
4035 : :
4036 : : /* Scaling frequencies up to maximal profile count may result in
4037 : : frequent overflows especially when inlining loops.
4038 : : Small scaling results in unnecesary precision loss. Stay in
4039 : : the half of the (exponential) range. */
4040 : 2275113 : freq_max = (sreal (1) << (profile_count::n_bits / 2)) / freq_max;
4041 : 2275113 : if (freq_max < 16)
4042 : 62 : freq_max = 16;
4043 : 2275113 : profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
4044 : 2275113 : cfun->cfg->count_max = profile_count::uninitialized ();
4045 : 18944311 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4046 : : {
4047 : 16669198 : sreal tmp = BLOCK_INFO (bb)->frequency;
4048 : 16669198 : if (tmp >= 1)
4049 : : {
4050 : 10066538 : gimple_stmt_iterator gsi;
4051 : 10066538 : tree decl;
4052 : :
4053 : : /* Self recursive calls can not have frequency greater than 1
4054 : : or program will never terminate. This will result in an
4055 : : inconsistent bb profile but it is better than greatly confusing
4056 : : IPA cost metrics. */
4057 : 62333992 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4058 : 42205835 : if (is_gimple_call (gsi_stmt (gsi))
4059 : 2755413 : && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
4060 : 44696128 : && recursive_call_p (current_function_decl, decl))
4061 : : {
4062 : 4919 : if (dump_file)
4063 : 0 : fprintf (dump_file, "Dropping frequency of recursive call"
4064 : : " in bb %i from %f\n", bb->index,
4065 : : tmp.to_double ());
4066 : 4919 : tmp = (sreal)9 / (sreal)10;
4067 : 4919 : break;
4068 : : }
4069 : : }
4070 : 16669198 : tmp = tmp * freq_max;
4071 : 16669198 : profile_count count = profile_count::from_gcov_type (tmp.to_nearest_int ());
4072 : :
4073 : : /* If we have profile feedback in which this function was never
4074 : : executed, then preserve this info. */
4075 : 17513847 : if (!(bb->count == profile_count::zero ()))
4076 : 15824549 : bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
4077 : 16669198 : cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
4078 : : }
4079 : :
4080 : 2275113 : free_aux_for_blocks ();
4081 : 2275113 : free_aux_for_edges ();
4082 : 2275113 : compute_function_frequency ();
4083 : 2275113 : }
4084 : :
4085 : : /* Decide whether function is hot, cold or unlikely executed. */
4086 : : void
4087 : 2297262 : compute_function_frequency (void)
4088 : : {
4089 : 2297262 : basic_block bb;
4090 : 2297262 : struct cgraph_node *node = cgraph_node::get (current_function_decl);
4091 : :
4092 : 2297262 : if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4093 : 2297262 : || MAIN_NAME_P (DECL_NAME (current_function_decl)))
4094 : 83657 : node->only_called_at_startup = true;
4095 : 2297262 : if (DECL_STATIC_DESTRUCTOR (current_function_decl))
4096 : 1127 : node->only_called_at_exit = true;
4097 : :
4098 : 2297262 : if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ())
4099 : : {
4100 : 2285090 : int flags = flags_from_decl_or_type (current_function_decl);
4101 : 2285090 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
4102 : : != NULL)
4103 : 291 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4104 : 2284799 : else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
4105 : : != NULL)
4106 : 60 : node->frequency = NODE_FREQUENCY_HOT;
4107 : 2284739 : else if (flags & ECF_NORETURN)
4108 : 2525 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4109 : 2282214 : else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
4110 : 71530 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4111 : 2210684 : else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
4112 : 2210684 : || DECL_STATIC_DESTRUCTOR (current_function_decl))
4113 : 12591 : node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
4114 : 2285090 : return;
4115 : : }
4116 : :
4117 : 12172 : node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
4118 : 12172 : if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
4119 : : == NULL)
4120 : 12167 : warn_function_cold (current_function_decl);
4121 : 12172 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
4122 : 11830 : return;
4123 : 922 : FOR_EACH_BB_FN (bb, cfun)
4124 : : {
4125 : 811 : if (maybe_hot_bb_p (cfun, bb))
4126 : : {
4127 : 231 : node->frequency = NODE_FREQUENCY_HOT;
4128 : 231 : return;
4129 : : }
4130 : 580 : if (!probably_never_executed_bb_p (cfun, bb))
4131 : 525 : node->frequency = NODE_FREQUENCY_NORMAL;
4132 : : }
4133 : : }
4134 : :
4135 : : /* Build PREDICT_EXPR. */
4136 : : tree
4137 : 484814 : build_predict_expr (enum br_predictor predictor, enum prediction taken)
4138 : : {
4139 : 484814 : tree t = build1 (PREDICT_EXPR, void_type_node,
4140 : : build_int_cst (integer_type_node, predictor));
4141 : 484814 : SET_PREDICT_EXPR_OUTCOME (t, taken);
4142 : 484814 : return t;
4143 : : }
4144 : :
4145 : : const char *
4146 : 473 : predictor_name (enum br_predictor predictor)
4147 : : {
4148 : 473 : return predictor_info[predictor].name;
4149 : : }
4150 : :
4151 : : /* Predict branch probabilities and estimate profile of the tree CFG. */
4152 : :
4153 : : namespace {
4154 : :
4155 : : const pass_data pass_data_profile =
4156 : : {
4157 : : GIMPLE_PASS, /* type */
4158 : : "profile_estimate", /* name */
4159 : : OPTGROUP_NONE, /* optinfo_flags */
4160 : : TV_BRANCH_PROB, /* tv_id */
4161 : : PROP_cfg, /* properties_required */
4162 : : 0, /* properties_provided */
4163 : : 0, /* properties_destroyed */
4164 : : 0, /* todo_flags_start */
4165 : : 0, /* todo_flags_finish */
4166 : : };
4167 : :
4168 : : class pass_profile : public gimple_opt_pass
4169 : : {
4170 : : public:
4171 : 281914 : pass_profile (gcc::context *ctxt)
4172 : 563828 : : gimple_opt_pass (pass_data_profile, ctxt)
4173 : : {}
4174 : :
4175 : : /* opt_pass methods: */
4176 : 2225453 : bool gate (function *) final override { return flag_guess_branch_prob; }
4177 : : unsigned int execute (function *) final override;
4178 : :
4179 : : }; // class pass_profile
4180 : :
4181 : : unsigned int
4182 : 2224393 : pass_profile::execute (function *fun)
4183 : : {
4184 : 2224393 : unsigned nb_loops;
4185 : :
4186 : 2224393 : if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4187 : : return 0;
4188 : :
4189 : 2224350 : loop_optimizer_init (LOOPS_NORMAL);
4190 : 2224350 : if (dump_file && (dump_flags & TDF_DETAILS))
4191 : 2 : flow_loops_dump (dump_file, NULL, 0);
4192 : :
4193 : 2224350 : nb_loops = number_of_loops (fun);
4194 : 2224350 : if (nb_loops > 1)
4195 : 246769 : scev_initialize ();
4196 : :
4197 : 2224350 : tree_estimate_probability (false);
4198 : 2224350 : cfun->cfg->full_profile = true;
4199 : :
4200 : 2224350 : if (nb_loops > 1)
4201 : 246769 : scev_finalize ();
4202 : :
4203 : 2224350 : loop_optimizer_finalize ();
4204 : 2224350 : if (dump_file && (dump_flags & TDF_DETAILS))
4205 : 2 : gimple_dump_cfg (dump_file, dump_flags);
4206 : 2224350 : if (profile_status_for_fn (fun) == PROFILE_ABSENT)
4207 : 2224350 : profile_status_for_fn (fun) = PROFILE_GUESSED;
4208 : 2224350 : if (dump_file && (dump_flags & TDF_DETAILS))
4209 : : {
4210 : 2 : sreal iterations;
4211 : 7 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
4212 : 1 : if (expected_loop_iterations_by_profile (loop, &iterations))
4213 : 1 : fprintf (dump_file, "Loop got predicted %d to iterate %f times.\n",
4214 : 2 : loop->num, iterations.to_double ());
4215 : : }
4216 : : return 0;
4217 : : }
4218 : :
4219 : : } // anon namespace
4220 : :
4221 : : gimple_opt_pass *
4222 : 281914 : make_pass_profile (gcc::context *ctxt)
4223 : : {
4224 : 281914 : return new pass_profile (ctxt);
4225 : : }
4226 : :
4227 : : /* Return true when PRED predictor should be removed after early
4228 : : tree passes. Most of the predictors are beneficial to survive
4229 : : as early inlining can also distribute then into caller's bodies. */
4230 : :
4231 : : static bool
4232 : 347637 : strip_predictor_early (enum br_predictor pred)
4233 : : {
4234 : 0 : switch (pred)
4235 : : {
4236 : : case PRED_TREE_EARLY_RETURN:
4237 : : return true;
4238 : 0 : default:
4239 : 0 : return false;
4240 : : }
4241 : : }
4242 : :
4243 : : /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4244 : : we no longer need. EARLY is set to true when called from early
4245 : : optimizations. */
4246 : :
4247 : : unsigned int
4248 : 3213397 : strip_predict_hints (function *fun, bool early)
4249 : : {
4250 : 3213397 : basic_block bb;
4251 : 3213397 : gimple *ass_stmt;
4252 : 3213397 : tree var;
4253 : 3213397 : bool changed = false;
4254 : :
4255 : 23624599 : FOR_EACH_BB_FN (bb, fun)
4256 : : {
4257 : 20411202 : gimple_stmt_iterator bi;
4258 : 172886261 : for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
4259 : : {
4260 : 132063857 : gimple *stmt = gsi_stmt (bi);
4261 : :
4262 : 132063857 : if (gimple_code (stmt) == GIMPLE_PREDICT)
4263 : : {
4264 : 1038018 : if (!early
4265 : 547721 : || strip_predictor_early (gimple_predict_predictor (stmt)))
4266 : : {
4267 : 490297 : gsi_remove (&bi, true);
4268 : 490297 : changed = true;
4269 : 490297 : continue;
4270 : : }
4271 : : }
4272 : 131516136 : else if (is_gimple_call (stmt))
4273 : : {
4274 : 10897820 : tree fndecl = gimple_call_fndecl (stmt);
4275 : :
4276 : 10897820 : if (!early
4277 : 10897820 : && ((fndecl != NULL_TREE
4278 : 5181579 : && fndecl_built_in_p (fndecl, BUILT_IN_EXPECT)
4279 : 100177 : && gimple_call_num_args (stmt) == 2)
4280 : : || (fndecl != NULL_TREE
4281 : 5081402 : && fndecl_built_in_p (fndecl,
4282 : : BUILT_IN_EXPECT_WITH_PROBABILITY)
4283 : 18 : && gimple_call_num_args (stmt) == 3)
4284 : 5385260 : || (gimple_call_internal_p (stmt)
4285 : 129049 : && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)))
4286 : : {
4287 : 123891 : var = gimple_call_lhs (stmt);
4288 : 123891 : changed = true;
4289 : 123891 : if (var)
4290 : : {
4291 : 123890 : ass_stmt
4292 : 123890 : = gimple_build_assign (var, gimple_call_arg (stmt, 0));
4293 : 123890 : gsi_replace (&bi, ass_stmt, true);
4294 : : }
4295 : : else
4296 : : {
4297 : 1 : gsi_remove (&bi, true);
4298 : 1 : continue;
4299 : : }
4300 : : }
4301 : : }
4302 : 131573559 : gsi_next (&bi);
4303 : : }
4304 : : }
4305 : 3213397 : return changed ? TODO_cleanup_cfg : 0;
4306 : : }
4307 : :
4308 : : namespace {
4309 : :
4310 : : const pass_data pass_data_strip_predict_hints =
4311 : : {
4312 : : GIMPLE_PASS, /* type */
4313 : : "*strip_predict_hints", /* name */
4314 : : OPTGROUP_NONE, /* optinfo_flags */
4315 : : TV_BRANCH_PROB, /* tv_id */
4316 : : PROP_cfg, /* properties_required */
4317 : : 0, /* properties_provided */
4318 : : 0, /* properties_destroyed */
4319 : : 0, /* todo_flags_start */
4320 : : 0, /* todo_flags_finish */
4321 : : };
4322 : :
4323 : : class pass_strip_predict_hints : public gimple_opt_pass
4324 : : {
4325 : : public:
4326 : 845742 : pass_strip_predict_hints (gcc::context *ctxt)
4327 : 1691484 : : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
4328 : : {}
4329 : :
4330 : : /* opt_pass methods: */
4331 : 563828 : opt_pass * clone () final override
4332 : : {
4333 : 563828 : return new pass_strip_predict_hints (m_ctxt);
4334 : : }
4335 : 845742 : void set_pass_param (unsigned int n, bool param) final override
4336 : : {
4337 : 845742 : gcc_assert (n == 0);
4338 : 845742 : early_p = param;
4339 : 845742 : }
4340 : :
4341 : : unsigned int execute (function *) final override;
4342 : :
4343 : : private:
4344 : : bool early_p;
4345 : :
4346 : : }; // class pass_strip_predict_hints
4347 : :
4348 : : unsigned int
4349 : 3213397 : pass_strip_predict_hints::execute (function *fun)
4350 : : {
4351 : 3213397 : return strip_predict_hints (fun, early_p);
4352 : : }
4353 : :
4354 : : } // anon namespace
4355 : :
4356 : : gimple_opt_pass *
4357 : 281914 : make_pass_strip_predict_hints (gcc::context *ctxt)
4358 : : {
4359 : 281914 : return new pass_strip_predict_hints (ctxt);
4360 : : }
4361 : :
4362 : : /* Rebuild function frequencies. Passes are in general expected to
4363 : : maintain profile by hand, however in some cases this is not possible:
4364 : : for example when inlining several functions with loops freuqencies might run
4365 : : out of scale and thus needs to be recomputed. */
4366 : :
4367 : : void
4368 : 1031504 : rebuild_frequencies (void)
4369 : : {
4370 : : /* If we have no profile, do nothing. Note that after inlining
4371 : : profile_status_for_fn may not represent the actual presence/absence of
4372 : : profile. */
4373 : 1031504 : if (profile_status_for_fn (cfun) == PROFILE_ABSENT
4374 : 1031504 : && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
4375 : : return;
4376 : :
4377 : :
4378 : : /* See if everything is OK and update count_max. */
4379 : 1031255 : basic_block bb;
4380 : 1031255 : bool inconsistency_found = false;
4381 : 1031255 : bool uninitialized_probablity_found = false;
4382 : 1031255 : bool uninitialized_count_found = false;
4383 : :
4384 : 1031255 : cfun->cfg->count_max = profile_count::uninitialized ();
4385 : 13488049 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4386 : : {
4387 : 12456794 : cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
4388 : : /* Uninitialized count may be result of inlining or an omision in an
4389 : : optimization pass. */
4390 : 12456794 : if (!bb->count.initialized_p ())
4391 : : {
4392 : 22 : uninitialized_count_found = true;
4393 : 22 : if (dump_file)
4394 : 0 : fprintf (dump_file, "BB %i has uninitialized count\n",
4395 : : bb->index);
4396 : : }
4397 : 12456794 : if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4398 : : && (!uninitialized_probablity_found || !inconsistency_found))
4399 : : {
4400 : 11425539 : profile_count sum = profile_count::zero ();
4401 : 11425539 : edge e;
4402 : 11425539 : edge_iterator ei;
4403 : :
4404 : 26929545 : FOR_EACH_EDGE (e, ei, bb->preds)
4405 : : {
4406 : 15504006 : sum += e->count ();
4407 : : /* Uninitialized probability may be result of inlining or an
4408 : : omision in an optimization pass. */
4409 : 15504006 : if (!e->probability.initialized_p ())
4410 : : {
4411 : 36 : if (dump_file)
4412 : 0 : fprintf (dump_file,
4413 : : "Edge %i->%i has uninitialized probability\n",
4414 : 0 : e->src->index, e->dest->index);
4415 : : }
4416 : : }
4417 : 11425539 : if (sum.differs_from_p (bb->count))
4418 : : {
4419 : 145860 : if (dump_file)
4420 : 18 : fprintf (dump_file,
4421 : : "BB %i has invalid sum of incomming counts\n",
4422 : : bb->index);
4423 : : inconsistency_found = true;
4424 : : }
4425 : : }
4426 : : }
4427 : :
4428 : : /* If everything is OK, do not re-propagate frequencies. */
4429 : 1031255 : if (!inconsistency_found
4430 : 980650 : && (!uninitialized_count_found || uninitialized_probablity_found)
4431 : 2011905 : && !cfun->cfg->count_max.very_large_p ())
4432 : : {
4433 : 980633 : if (dump_file)
4434 : 31 : fprintf (dump_file, "Profile is consistent\n");
4435 : 980633 : return;
4436 : : }
4437 : : /* Do not re-propagate if we have profile feedback. Even if the profile is
4438 : : inconsistent from previous transofrmations, it is probably more realistic
4439 : : for hot part of the program than result of repropagating.
4440 : :
4441 : : Consider example where we previously has
4442 : :
4443 : : if (test)
4444 : : then [large probability for true]
4445 : :
4446 : : and we later proved that test is always 0. In this case, if profile was
4447 : : read correctly, we must have duplicated the conditional (for example by
4448 : : inlining) in to a context where test is false. From profile feedback
4449 : : we know that most executions if the conditionals were true, so the
4450 : : important copy is not the one we look on.
4451 : :
4452 : : Propagating from probabilities would make profile look consistent, but
4453 : : because probablities after code duplication may not be representative
4454 : : for a given run, we would only propagate the error further. */
4455 : 50622 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().nonzero_p ()
4456 : 8 : && !uninitialized_count_found)
4457 : : {
4458 : 8 : if (dump_file)
4459 : 0 : fprintf (dump_file,
4460 : : "Profile is inconsistent but read from profile feedback;"
4461 : : " not rebuilding\n");
4462 : 8 : return;
4463 : : }
4464 : :
4465 : 50614 : loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
4466 : 50614 : connect_infinite_loops_to_exit ();
4467 : 50614 : estimate_bb_frequencies ();
4468 : 50614 : remove_fake_exit_edges ();
4469 : 50614 : loop_optimizer_finalize ();
4470 : 50614 : if (dump_file)
4471 : 5 : fprintf (dump_file, "Rebuilt basic block counts\n");
4472 : :
4473 : : return;
4474 : : }
4475 : :
4476 : : namespace {
4477 : :
4478 : : const pass_data pass_data_rebuild_frequencies =
4479 : : {
4480 : : GIMPLE_PASS, /* type */
4481 : : "rebuild_frequencies", /* name */
4482 : : OPTGROUP_NONE, /* optinfo_flags */
4483 : : TV_REBUILD_FREQUENCIES, /* tv_id */
4484 : : PROP_cfg, /* properties_required */
4485 : : 0, /* properties_provided */
4486 : : 0, /* properties_destroyed */
4487 : : 0, /* todo_flags_start */
4488 : : 0, /* todo_flags_finish */
4489 : : };
4490 : :
4491 : : class pass_rebuild_frequencies : public gimple_opt_pass
4492 : : {
4493 : : public:
4494 : 563828 : pass_rebuild_frequencies (gcc::context *ctxt)
4495 : 1127656 : : gimple_opt_pass (pass_data_rebuild_frequencies, ctxt)
4496 : : {}
4497 : :
4498 : : /* opt_pass methods: */
4499 : 281914 : opt_pass * clone () final override
4500 : : {
4501 : 281914 : return new pass_rebuild_frequencies (m_ctxt);
4502 : : }
4503 : 0 : void set_pass_param (unsigned int n, bool param) final override
4504 : : {
4505 : 0 : gcc_assert (n == 0);
4506 : 0 : early_p = param;
4507 : 0 : }
4508 : :
4509 : 987998 : unsigned int execute (function *) final override
4510 : : {
4511 : 987998 : rebuild_frequencies ();
4512 : 987998 : return 0;
4513 : : }
4514 : :
4515 : : private:
4516 : : bool early_p;
4517 : :
4518 : : }; // class pass_rebuild_frequencies
4519 : :
4520 : : } // anon namespace
4521 : :
4522 : : gimple_opt_pass *
4523 : 281914 : make_pass_rebuild_frequencies (gcc::context *ctxt)
4524 : : {
4525 : 281914 : return new pass_rebuild_frequencies (ctxt);
4526 : : }
4527 : :
4528 : : /* Perform a dry run of the branch prediction pass and report comparsion of
4529 : : the predicted and real profile into the dump file. */
4530 : :
4531 : : void
4532 : 5 : report_predictor_hitrates (void)
4533 : : {
4534 : 5 : unsigned nb_loops;
4535 : :
4536 : 5 : loop_optimizer_init (LOOPS_NORMAL);
4537 : 5 : if (dump_file && (dump_flags & TDF_DETAILS))
4538 : 5 : flow_loops_dump (dump_file, NULL, 0);
4539 : :
4540 : 5 : nb_loops = number_of_loops (cfun);
4541 : 5 : if (nb_loops > 1)
4542 : 3 : scev_initialize ();
4543 : :
4544 : 5 : tree_estimate_probability (true);
4545 : :
4546 : 5 : if (nb_loops > 1)
4547 : 3 : scev_finalize ();
4548 : :
4549 : 5 : loop_optimizer_finalize ();
4550 : 5 : }
4551 : :
4552 : : /* Force edge E to be cold.
4553 : : If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4554 : : keep low probability to represent possible error in a guess. This is used
4555 : : i.e. in case we predict loop to likely iterate given number of times but
4556 : : we are not 100% sure.
4557 : :
4558 : : This function locally updates profile without attempt to keep global
4559 : : consistency which cannot be reached in full generality without full profile
4560 : : rebuild from probabilities alone. Doing so is not necessarily a good idea
4561 : : because frequencies and counts may be more realistic then probabilities.
4562 : :
4563 : : In some cases (such as for elimination of early exits during full loop
4564 : : unrolling) the caller can ensure that profile will get consistent
4565 : : afterwards. */
4566 : :
4567 : : void
4568 : 457063 : force_edge_cold (edge e, bool impossible)
4569 : : {
4570 : 457063 : profile_count count_sum = profile_count::zero ();
4571 : 457063 : profile_probability prob_sum = profile_probability::never ();
4572 : 457063 : edge_iterator ei;
4573 : 457063 : edge e2;
4574 : 457063 : bool uninitialized_exit = false;
4575 : :
4576 : : /* When branch probability guesses are not known, then do nothing. */
4577 : 457298 : if (!impossible && !e->count ().initialized_p ())
4578 : 1956 : return;
4579 : :
4580 : 457063 : profile_probability goal = (impossible ? profile_probability::never ()
4581 : 235 : : profile_probability::very_unlikely ());
4582 : :
4583 : : /* If edge is already improbably or cold, just return. */
4584 : 457063 : if (e->probability <= goal
4585 : 42460 : && (!impossible || e->count () == profile_count::zero ()))
4586 : 1063 : return;
4587 : 1367582 : FOR_EACH_EDGE (e2, ei, e->src->succs)
4588 : 911582 : if (e2 != e)
4589 : : {
4590 : 455582 : if (e->flags & EDGE_FAKE)
4591 : 0 : continue;
4592 : 455582 : if (e2->count ().initialized_p ())
4593 : 455358 : count_sum += e2->count ();
4594 : 455582 : if (e2->probability.initialized_p ())
4595 : 455358 : prob_sum += e2->probability;
4596 : : else
4597 : : uninitialized_exit = true;
4598 : : }
4599 : :
4600 : : /* If we are not guessing profiles but have some other edges out,
4601 : : just assume the control flow goes elsewhere. */
4602 : 456000 : if (uninitialized_exit)
4603 : 224 : e->probability = goal;
4604 : : /* If there are other edges out of e->src, redistribute probabilitity
4605 : : there. */
4606 : 455776 : else if (prob_sum > profile_probability::never ())
4607 : : {
4608 : 454608 : if (dump_file && (dump_flags & TDF_DETAILS))
4609 : : {
4610 : 1086 : fprintf (dump_file, "Making edge %i->%i %s by redistributing "
4611 : : "probability to other edges. Original probability: ",
4612 : 1086 : e->src->index, e->dest->index,
4613 : : impossible ? "impossible" : "cold");
4614 : 1086 : e->probability.dump (dump_file);
4615 : 1086 : fprintf (dump_file, "\n");
4616 : : }
4617 : 454608 : set_edge_probability_and_rescale_others (e, goal);
4618 : 454608 : if (current_ir_type () != IR_GIMPLE
4619 : 454608 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4620 : 126487 : update_br_prob_note (e->src);
4621 : : }
4622 : : /* If all edges out of e->src are unlikely, the basic block itself
4623 : : is unlikely. */
4624 : : else
4625 : : {
4626 : 1168 : if (prob_sum == profile_probability::never ())
4627 : 959 : e->probability = profile_probability::always ();
4628 : : else
4629 : : {
4630 : 209 : if (impossible)
4631 : 209 : e->probability = profile_probability::never ();
4632 : : /* If BB has some edges out that are not impossible, we cannot
4633 : : assume that BB itself is. */
4634 : : impossible = false;
4635 : : }
4636 : 1168 : if (current_ir_type () != IR_GIMPLE
4637 : 1168 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4638 : 52 : update_br_prob_note (e->src);
4639 : 1168 : if (e->src->count == profile_count::zero ())
4640 : 143 : return;
4641 : 2050 : if (count_sum == profile_count::zero () && impossible)
4642 : : {
4643 : 796 : bool found = false;
4644 : 796 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4645 : : ;
4646 : 765 : else if (current_ir_type () == IR_GIMPLE)
4647 : 1530 : for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
4648 : 2831 : !gsi_end_p (gsi); gsi_next (&gsi))
4649 : : {
4650 : 2112 : if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
4651 : : {
4652 : : found = true;
4653 : : break;
4654 : : }
4655 : : }
4656 : : /* FIXME: Implement RTL path. */
4657 : : else
4658 : : found = true;
4659 : 765 : if (!found)
4660 : : {
4661 : 750 : if (dump_file && (dump_flags & TDF_DETAILS))
4662 : 0 : fprintf (dump_file,
4663 : : "Making bb %i impossible and dropping count to 0.\n",
4664 : 0 : e->src->index);
4665 : 750 : e->src->count = profile_count::zero ();
4666 : 1557 : FOR_EACH_EDGE (e2, ei, e->src->preds)
4667 : 807 : force_edge_cold (e2, impossible);
4668 : : return;
4669 : : }
4670 : : }
4671 : :
4672 : : /* If we did not adjusting, the source basic block has no likely edeges
4673 : : leaving other direction. In that case force that bb cold, too.
4674 : : This in general is difficult task to do, but handle special case when
4675 : : BB has only one predecestor. This is common case when we are updating
4676 : : after loop transforms. */
4677 : 550 : if (!(prob_sum > profile_probability::never ())
4678 : 275 : && count_sum == profile_count::zero ()
4679 : 118 : && single_pred_p (e->src) && e->src->count.to_frequency (cfun)
4680 : 50 : > (impossible ? 0 : 1))
4681 : : {
4682 : 50 : int old_frequency = e->src->count.to_frequency (cfun);
4683 : 50 : if (dump_file && (dump_flags & TDF_DETAILS))
4684 : 0 : fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
4685 : : impossible ? "impossible" : "cold");
4686 : 50 : int new_frequency = MIN (e->src->count.to_frequency (cfun),
4687 : : impossible ? 0 : 1);
4688 : 0 : if (impossible)
4689 : 28 : e->src->count = profile_count::zero ();
4690 : : else
4691 : 22 : e->src->count = e->count ().apply_scale (new_frequency,
4692 : : old_frequency);
4693 : 50 : force_edge_cold (single_pred_edge (e->src), impossible);
4694 : : }
4695 : 2 : else if (dump_file && (dump_flags & TDF_DETAILS)
4696 : 225 : && maybe_hot_bb_p (cfun, e->src))
4697 : 0 : fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
4698 : : impossible ? "impossible" : "cold");
4699 : : }
4700 : : }
4701 : :
4702 : : #if CHECKING_P
4703 : :
4704 : : namespace selftest {
4705 : :
4706 : : /* Test that value range of predictor values defined in predict.def is
4707 : : within range (50, 100]. */
4708 : :
4709 : : struct branch_predictor
4710 : : {
4711 : : const char *name;
4712 : : int probability;
4713 : : };
4714 : :
4715 : : #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4716 : :
4717 : : static void
4718 : 4 : test_prediction_value_range ()
4719 : : {
4720 : 4 : branch_predictor predictors[] = {
4721 : : #include "predict.def"
4722 : : { NULL, PROB_UNINITIALIZED }
4723 : : };
4724 : :
4725 : 216 : for (unsigned i = 0; predictors[i].name != NULL; i++)
4726 : : {
4727 : 212 : if (predictors[i].probability == PROB_UNINITIALIZED)
4728 : 28 : continue;
4729 : :
4730 : 184 : unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
4731 : 212 : ASSERT_TRUE (p >= 50 && p <= 100);
4732 : : }
4733 : 4 : }
4734 : :
4735 : : #undef DEF_PREDICTOR
4736 : :
4737 : : /* Run all of the selfests within this file. */
4738 : :
4739 : : void
4740 : 4 : predict_cc_tests ()
4741 : : {
4742 : 4 : test_prediction_value_range ();
4743 : 4 : }
4744 : :
4745 : : } // namespace selftest
4746 : : #endif /* CHECKING_P. */
|
