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