1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 /* References:
22
23 [1] "Branch Prediction for Free"
24 Ball and Larus; PLDI '93.
25 [2] "Static Branch Frequency and Program Profile Analysis"
26 Wu and Larus; MICRO-27.
27 [3] "Corpus-based Static Branch Prediction"
28 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
29
30
31 #include "config.h"
32 #include "system.h"
33 #include "coretypes.h"
34 #include "tm.h"
35 #include "tree.h"
36 #include "rtl.h"
37 #include "tm_p.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
41 #include "regs.h"
42 #include "flags.h"
43 #include "output.h"
44 #include "function.h"
45 #include "except.h"
46 #include "diagnostic-core.h"
47 #include "recog.h"
48 #include "expr.h"
49 #include "predict.h"
50 #include "coverage.h"
51 #include "sreal.h"
52 #include "params.h"
53 #include "target.h"
54 #include "cfgloop.h"
55 #include "tree-flow.h"
56 #include "ggc.h"
57 #include "tree-dump.h"
58 #include "tree-pass.h"
59 #include "timevar.h"
60 #include "tree-scalar-evolution.h"
61 #include "cfgloop.h"
62 #include "pointer-set.h"
63
64 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
65 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
66 static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
67 real_inv_br_prob_base, real_one_half, real_bb_freq_max;
68
69 /* Random guesstimation given names.
70 PROV_VERY_UNLIKELY should be small enough so basic block predicted
71 by it gets bellow HOT_BB_FREQUENCY_FRANCTION. */
72 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1)
73 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
74 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
75 #define PROB_ALWAYS (REG_BR_PROB_BASE)
76
77 static void combine_predictions_for_insn (rtx, basic_block);
78 static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
79 static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
80 static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction);
81 static bool can_predict_insn_p (const_rtx);
82
83 /* Information we hold about each branch predictor.
84 Filled using information from predict.def. */
85
86 struct predictor_info
87 {
88 const char *const name; /* Name used in the debugging dumps. */
89 const int hitrate; /* Expected hitrate used by
90 predict_insn_def call. */
91 const int flags;
92 };
93
94 /* Use given predictor without Dempster-Shaffer theory if it matches
95 using first_match heuristics. */
96 #define PRED_FLAG_FIRST_MATCH 1
97
98 /* Recompute hitrate in percent to our representation. */
99
100 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
101
102 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
103 static const struct predictor_info predictor_info[]= {
104 #include "predict.def"
105
106 /* Upper bound on predictors. */
107 {NULL, 0, 0}
108 };
109 #undef DEF_PREDICTOR
110
111 /* Return TRUE if frequency FREQ is considered to be hot. */
112
113 static inline bool
maybe_hot_frequency_p(int freq)114 maybe_hot_frequency_p (int freq)
115 {
116 struct cgraph_node *node = cgraph_get_node (current_function_decl);
117 if (!profile_info || !flag_branch_probabilities)
118 {
119 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
120 return false;
121 if (node->frequency == NODE_FREQUENCY_HOT)
122 return true;
123 }
124 if (profile_status == PROFILE_ABSENT)
125 return true;
126 if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
127 && freq < (ENTRY_BLOCK_PTR->frequency * 2 / 3))
128 return false;
129 if (freq < ENTRY_BLOCK_PTR->frequency / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
130 return false;
131 return true;
132 }
133
134 /* Return TRUE if frequency FREQ is considered to be hot. */
135
136 static inline bool
maybe_hot_count_p(gcov_type count)137 maybe_hot_count_p (gcov_type count)
138 {
139 if (profile_status != PROFILE_READ)
140 return true;
141 /* Code executed at most once is not hot. */
142 if (profile_info->runs >= count)
143 return false;
144 return (count
145 > profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION));
146 }
147
148 /* Return true in case BB can be CPU intensive and should be optimized
149 for maximal performance. */
150
151 bool
maybe_hot_bb_p(const_basic_block bb)152 maybe_hot_bb_p (const_basic_block bb)
153 {
154 if (profile_status == PROFILE_READ)
155 return maybe_hot_count_p (bb->count);
156 return maybe_hot_frequency_p (bb->frequency);
157 }
158
159 /* Return true if the call can be hot. */
160
161 bool
cgraph_maybe_hot_edge_p(struct cgraph_edge * edge)162 cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
163 {
164 if (profile_info && flag_branch_probabilities
165 && (edge->count
166 <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
167 return false;
168 if (edge->caller->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED
169 || edge->callee->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
170 return false;
171 if (edge->caller->frequency > NODE_FREQUENCY_UNLIKELY_EXECUTED
172 && edge->callee->frequency <= NODE_FREQUENCY_EXECUTED_ONCE)
173 return false;
174 if (optimize_size)
175 return false;
176 if (edge->caller->frequency == NODE_FREQUENCY_HOT)
177 return true;
178 if (edge->caller->frequency == NODE_FREQUENCY_EXECUTED_ONCE
179 && edge->frequency < CGRAPH_FREQ_BASE * 3 / 2)
180 return false;
181 if (flag_guess_branch_prob
182 && edge->frequency <= (CGRAPH_FREQ_BASE
183 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
184 return false;
185 return true;
186 }
187
188 /* Return true in case BB can be CPU intensive and should be optimized
189 for maximal performance. */
190
191 bool
maybe_hot_edge_p(edge e)192 maybe_hot_edge_p (edge e)
193 {
194 if (profile_status == PROFILE_READ)
195 return maybe_hot_count_p (e->count);
196 return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
197 }
198
199
200 /* Return true in case BB is probably never executed. */
201
202 bool
probably_never_executed_bb_p(const_basic_block bb)203 probably_never_executed_bb_p (const_basic_block bb)
204 {
205 if (profile_info && flag_branch_probabilities)
206 return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
207 if ((!profile_info || !flag_branch_probabilities)
208 && (cgraph_get_node (current_function_decl)->frequency
209 == NODE_FREQUENCY_UNLIKELY_EXECUTED))
210 return true;
211 return false;
212 }
213
214 /* Return true if NODE should be optimized for size. */
215
216 bool
cgraph_optimize_for_size_p(struct cgraph_node * node)217 cgraph_optimize_for_size_p (struct cgraph_node *node)
218 {
219 if (optimize_size)
220 return true;
221 if (node && (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED))
222 return true;
223 else
224 return false;
225 }
226
227 /* Return true when current function should always be optimized for size. */
228
229 bool
optimize_function_for_size_p(struct function * fun)230 optimize_function_for_size_p (struct function *fun)
231 {
232 if (optimize_size)
233 return true;
234 if (!fun || !fun->decl)
235 return false;
236 return cgraph_optimize_for_size_p (cgraph_get_node (fun->decl));
237 }
238
239 /* Return true when current function should always be optimized for speed. */
240
241 bool
optimize_function_for_speed_p(struct function * fun)242 optimize_function_for_speed_p (struct function *fun)
243 {
244 return !optimize_function_for_size_p (fun);
245 }
246
247 /* Return TRUE when BB should be optimized for size. */
248
249 bool
optimize_bb_for_size_p(const_basic_block bb)250 optimize_bb_for_size_p (const_basic_block bb)
251 {
252 return optimize_function_for_size_p (cfun) || !maybe_hot_bb_p (bb);
253 }
254
255 /* Return TRUE when BB should be optimized for speed. */
256
257 bool
optimize_bb_for_speed_p(const_basic_block bb)258 optimize_bb_for_speed_p (const_basic_block bb)
259 {
260 return !optimize_bb_for_size_p (bb);
261 }
262
263 /* Return TRUE when BB should be optimized for size. */
264
265 bool
optimize_edge_for_size_p(edge e)266 optimize_edge_for_size_p (edge e)
267 {
268 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
269 }
270
271 /* Return TRUE when BB should be optimized for speed. */
272
273 bool
optimize_edge_for_speed_p(edge e)274 optimize_edge_for_speed_p (edge e)
275 {
276 return !optimize_edge_for_size_p (e);
277 }
278
279 /* Return TRUE when BB should be optimized for size. */
280
281 bool
optimize_insn_for_size_p(void)282 optimize_insn_for_size_p (void)
283 {
284 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
285 }
286
287 /* Return TRUE when BB should be optimized for speed. */
288
289 bool
optimize_insn_for_speed_p(void)290 optimize_insn_for_speed_p (void)
291 {
292 return !optimize_insn_for_size_p ();
293 }
294
295 /* Return TRUE when LOOP should be optimized for size. */
296
297 bool
optimize_loop_for_size_p(struct loop * loop)298 optimize_loop_for_size_p (struct loop *loop)
299 {
300 return optimize_bb_for_size_p (loop->header);
301 }
302
303 /* Return TRUE when LOOP should be optimized for speed. */
304
305 bool
optimize_loop_for_speed_p(struct loop * loop)306 optimize_loop_for_speed_p (struct loop *loop)
307 {
308 return optimize_bb_for_speed_p (loop->header);
309 }
310
311 /* Return TRUE when LOOP nest should be optimized for speed. */
312
313 bool
optimize_loop_nest_for_speed_p(struct loop * loop)314 optimize_loop_nest_for_speed_p (struct loop *loop)
315 {
316 struct loop *l = loop;
317 if (optimize_loop_for_speed_p (loop))
318 return true;
319 l = loop->inner;
320 while (l && l != loop)
321 {
322 if (optimize_loop_for_speed_p (l))
323 return true;
324 if (l->inner)
325 l = l->inner;
326 else if (l->next)
327 l = l->next;
328 else
329 {
330 while (l != loop && !l->next)
331 l = loop_outer (l);
332 if (l != loop)
333 l = l->next;
334 }
335 }
336 return false;
337 }
338
339 /* Return TRUE when LOOP nest should be optimized for size. */
340
341 bool
optimize_loop_nest_for_size_p(struct loop * loop)342 optimize_loop_nest_for_size_p (struct loop *loop)
343 {
344 return !optimize_loop_nest_for_speed_p (loop);
345 }
346
347 /* Return true when edge E is likely to be well predictable by branch
348 predictor. */
349
350 bool
predictable_edge_p(edge e)351 predictable_edge_p (edge e)
352 {
353 if (profile_status == PROFILE_ABSENT)
354 return false;
355 if ((e->probability
356 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
357 || (REG_BR_PROB_BASE - e->probability
358 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
359 return true;
360 return false;
361 }
362
363
364 /* Set RTL expansion for BB profile. */
365
366 void
rtl_profile_for_bb(basic_block bb)367 rtl_profile_for_bb (basic_block bb)
368 {
369 crtl->maybe_hot_insn_p = maybe_hot_bb_p (bb);
370 }
371
372 /* Set RTL expansion for edge profile. */
373
374 void
rtl_profile_for_edge(edge e)375 rtl_profile_for_edge (edge e)
376 {
377 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
378 }
379
380 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
381 void
default_rtl_profile(void)382 default_rtl_profile (void)
383 {
384 crtl->maybe_hot_insn_p = true;
385 }
386
387 /* Return true if the one of outgoing edges is already predicted by
388 PREDICTOR. */
389
390 bool
rtl_predicted_by_p(const_basic_block bb,enum br_predictor predictor)391 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
392 {
393 rtx note;
394 if (!INSN_P (BB_END (bb)))
395 return false;
396 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
397 if (REG_NOTE_KIND (note) == REG_BR_PRED
398 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
399 return true;
400 return false;
401 }
402
403 /* This map contains for a basic block the list of predictions for the
404 outgoing edges. */
405
406 static struct pointer_map_t *bb_predictions;
407
408 /* Structure representing predictions in tree level. */
409
410 struct edge_prediction {
411 struct edge_prediction *ep_next;
412 edge ep_edge;
413 enum br_predictor ep_predictor;
414 int ep_probability;
415 };
416
417 /* Return true if the one of outgoing edges is already predicted by
418 PREDICTOR. */
419
420 bool
gimple_predicted_by_p(const_basic_block bb,enum br_predictor predictor)421 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
422 {
423 struct edge_prediction *i;
424 void **preds = pointer_map_contains (bb_predictions, bb);
425
426 if (!preds)
427 return false;
428
429 for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
430 if (i->ep_predictor == predictor)
431 return true;
432 return false;
433 }
434
435 /* Return true when the probability of edge is reliable.
436
437 The profile guessing code is good at predicting branch outcome (ie.
438 taken/not taken), that is predicted right slightly over 75% of time.
439 It is however notoriously poor on predicting the probability itself.
440 In general the profile appear a lot flatter (with probabilities closer
441 to 50%) than the reality so it is bad idea to use it to drive optimization
442 such as those disabling dynamic branch prediction for well predictable
443 branches.
444
445 There are two exceptions - edges leading to noreturn edges and edges
446 predicted by number of iterations heuristics are predicted well. This macro
447 should be able to distinguish those, but at the moment it simply check for
448 noreturn heuristic that is only one giving probability over 99% or bellow
449 1%. In future we might want to propagate reliability information across the
450 CFG if we find this information useful on multiple places. */
451 static bool
probability_reliable_p(int prob)452 probability_reliable_p (int prob)
453 {
454 return (profile_status == PROFILE_READ
455 || (profile_status == PROFILE_GUESSED
456 && (prob <= HITRATE (1) || prob >= HITRATE (99))));
457 }
458
459 /* Same predicate as above, working on edges. */
460 bool
edge_probability_reliable_p(const_edge e)461 edge_probability_reliable_p (const_edge e)
462 {
463 return probability_reliable_p (e->probability);
464 }
465
466 /* Same predicate as edge_probability_reliable_p, working on notes. */
467 bool
br_prob_note_reliable_p(const_rtx note)468 br_prob_note_reliable_p (const_rtx note)
469 {
470 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
471 return probability_reliable_p (INTVAL (XEXP (note, 0)));
472 }
473
474 static void
predict_insn(rtx insn,enum br_predictor predictor,int probability)475 predict_insn (rtx insn, enum br_predictor predictor, int probability)
476 {
477 gcc_assert (any_condjump_p (insn));
478 if (!flag_guess_branch_prob)
479 return;
480
481 add_reg_note (insn, REG_BR_PRED,
482 gen_rtx_CONCAT (VOIDmode,
483 GEN_INT ((int) predictor),
484 GEN_INT ((int) probability)));
485 }
486
487 /* Predict insn by given predictor. */
488
489 void
predict_insn_def(rtx insn,enum br_predictor predictor,enum prediction taken)490 predict_insn_def (rtx insn, enum br_predictor predictor,
491 enum prediction taken)
492 {
493 int probability = predictor_info[(int) predictor].hitrate;
494
495 if (taken != TAKEN)
496 probability = REG_BR_PROB_BASE - probability;
497
498 predict_insn (insn, predictor, probability);
499 }
500
501 /* Predict edge E with given probability if possible. */
502
503 void
rtl_predict_edge(edge e,enum br_predictor predictor,int probability)504 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
505 {
506 rtx last_insn;
507 last_insn = BB_END (e->src);
508
509 /* We can store the branch prediction information only about
510 conditional jumps. */
511 if (!any_condjump_p (last_insn))
512 return;
513
514 /* We always store probability of branching. */
515 if (e->flags & EDGE_FALLTHRU)
516 probability = REG_BR_PROB_BASE - probability;
517
518 predict_insn (last_insn, predictor, probability);
519 }
520
521 /* Predict edge E with the given PROBABILITY. */
522 void
gimple_predict_edge(edge e,enum br_predictor predictor,int probability)523 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
524 {
525 gcc_assert (profile_status != PROFILE_GUESSED);
526 if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
527 && flag_guess_branch_prob && optimize)
528 {
529 struct edge_prediction *i = XNEW (struct edge_prediction);
530 void **preds = pointer_map_insert (bb_predictions, e->src);
531
532 i->ep_next = (struct edge_prediction *) *preds;
533 *preds = i;
534 i->ep_probability = probability;
535 i->ep_predictor = predictor;
536 i->ep_edge = e;
537 }
538 }
539
540 /* Remove all predictions on given basic block that are attached
541 to edge E. */
542 void
remove_predictions_associated_with_edge(edge e)543 remove_predictions_associated_with_edge (edge e)
544 {
545 void **preds;
546
547 if (!bb_predictions)
548 return;
549
550 preds = pointer_map_contains (bb_predictions, e->src);
551
552 if (preds)
553 {
554 struct edge_prediction **prediction = (struct edge_prediction **) preds;
555 struct edge_prediction *next;
556
557 while (*prediction)
558 {
559 if ((*prediction)->ep_edge == e)
560 {
561 next = (*prediction)->ep_next;
562 free (*prediction);
563 *prediction = next;
564 }
565 else
566 prediction = &((*prediction)->ep_next);
567 }
568 }
569 }
570
571 /* Clears the list of predictions stored for BB. */
572
573 static void
clear_bb_predictions(basic_block bb)574 clear_bb_predictions (basic_block bb)
575 {
576 void **preds = pointer_map_contains (bb_predictions, bb);
577 struct edge_prediction *pred, *next;
578
579 if (!preds)
580 return;
581
582 for (pred = (struct edge_prediction *) *preds; pred; pred = next)
583 {
584 next = pred->ep_next;
585 free (pred);
586 }
587 *preds = NULL;
588 }
589
590 /* Return true when we can store prediction on insn INSN.
591 At the moment we represent predictions only on conditional
592 jumps, not at computed jump or other complicated cases. */
593 static bool
can_predict_insn_p(const_rtx insn)594 can_predict_insn_p (const_rtx insn)
595 {
596 return (JUMP_P (insn)
597 && any_condjump_p (insn)
598 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
599 }
600
601 /* Predict edge E by given predictor if possible. */
602
603 void
predict_edge_def(edge e,enum br_predictor predictor,enum prediction taken)604 predict_edge_def (edge e, enum br_predictor predictor,
605 enum prediction taken)
606 {
607 int probability = predictor_info[(int) predictor].hitrate;
608
609 if (taken != TAKEN)
610 probability = REG_BR_PROB_BASE - probability;
611
612 predict_edge (e, predictor, probability);
613 }
614
615 /* Invert all branch predictions or probability notes in the INSN. This needs
616 to be done each time we invert the condition used by the jump. */
617
618 void
invert_br_probabilities(rtx insn)619 invert_br_probabilities (rtx insn)
620 {
621 rtx note;
622
623 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
624 if (REG_NOTE_KIND (note) == REG_BR_PROB)
625 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
626 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
627 XEXP (XEXP (note, 0), 1)
628 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
629 }
630
631 /* Dump information about the branch prediction to the output file. */
632
633 static void
dump_prediction(FILE * file,enum br_predictor predictor,int probability,basic_block bb,int used)634 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
635 basic_block bb, int used)
636 {
637 edge e;
638 edge_iterator ei;
639
640 if (!file)
641 return;
642
643 FOR_EACH_EDGE (e, ei, bb->succs)
644 if (! (e->flags & EDGE_FALLTHRU))
645 break;
646
647 fprintf (file, " %s heuristics%s: %.1f%%",
648 predictor_info[predictor].name,
649 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
650
651 if (bb->count)
652 {
653 fprintf (file, " exec ");
654 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
655 if (e)
656 {
657 fprintf (file, " hit ");
658 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
659 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
660 }
661 }
662
663 fprintf (file, "\n");
664 }
665
666 /* We can not predict the probabilities of outgoing edges of bb. Set them
667 evenly and hope for the best. */
668 static void
set_even_probabilities(basic_block bb)669 set_even_probabilities (basic_block bb)
670 {
671 int nedges = 0;
672 edge e;
673 edge_iterator ei;
674
675 FOR_EACH_EDGE (e, ei, bb->succs)
676 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
677 nedges ++;
678 FOR_EACH_EDGE (e, ei, bb->succs)
679 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
680 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
681 else
682 e->probability = 0;
683 }
684
685 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
686 note if not already present. Remove now useless REG_BR_PRED notes. */
687
688 static void
combine_predictions_for_insn(rtx insn,basic_block bb)689 combine_predictions_for_insn (rtx insn, basic_block bb)
690 {
691 rtx prob_note;
692 rtx *pnote;
693 rtx note;
694 int best_probability = PROB_EVEN;
695 enum br_predictor best_predictor = END_PREDICTORS;
696 int combined_probability = REG_BR_PROB_BASE / 2;
697 int d;
698 bool first_match = false;
699 bool found = false;
700
701 if (!can_predict_insn_p (insn))
702 {
703 set_even_probabilities (bb);
704 return;
705 }
706
707 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
708 pnote = ®_NOTES (insn);
709 if (dump_file)
710 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
711 bb->index);
712
713 /* We implement "first match" heuristics and use probability guessed
714 by predictor with smallest index. */
715 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
716 if (REG_NOTE_KIND (note) == REG_BR_PRED)
717 {
718 enum br_predictor predictor = ((enum br_predictor)
719 INTVAL (XEXP (XEXP (note, 0), 0)));
720 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
721
722 found = true;
723 if (best_predictor > predictor)
724 best_probability = probability, best_predictor = predictor;
725
726 d = (combined_probability * probability
727 + (REG_BR_PROB_BASE - combined_probability)
728 * (REG_BR_PROB_BASE - probability));
729
730 /* Use FP math to avoid overflows of 32bit integers. */
731 if (d == 0)
732 /* If one probability is 0% and one 100%, avoid division by zero. */
733 combined_probability = REG_BR_PROB_BASE / 2;
734 else
735 combined_probability = (((double) combined_probability) * probability
736 * REG_BR_PROB_BASE / d + 0.5);
737 }
738
739 /* Decide which heuristic to use. In case we didn't match anything,
740 use no_prediction heuristic, in case we did match, use either
741 first match or Dempster-Shaffer theory depending on the flags. */
742
743 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
744 first_match = true;
745
746 if (!found)
747 dump_prediction (dump_file, PRED_NO_PREDICTION,
748 combined_probability, bb, true);
749 else
750 {
751 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
752 bb, !first_match);
753 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
754 bb, first_match);
755 }
756
757 if (first_match)
758 combined_probability = best_probability;
759 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
760
761 while (*pnote)
762 {
763 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
764 {
765 enum br_predictor predictor = ((enum br_predictor)
766 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
767 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
768
769 dump_prediction (dump_file, predictor, probability, bb,
770 !first_match || best_predictor == predictor);
771 *pnote = XEXP (*pnote, 1);
772 }
773 else
774 pnote = &XEXP (*pnote, 1);
775 }
776
777 if (!prob_note)
778 {
779 add_reg_note (insn, REG_BR_PROB, GEN_INT (combined_probability));
780
781 /* Save the prediction into CFG in case we are seeing non-degenerated
782 conditional jump. */
783 if (!single_succ_p (bb))
784 {
785 BRANCH_EDGE (bb)->probability = combined_probability;
786 FALLTHRU_EDGE (bb)->probability
787 = REG_BR_PROB_BASE - combined_probability;
788 }
789 }
790 else if (!single_succ_p (bb))
791 {
792 int prob = INTVAL (XEXP (prob_note, 0));
793
794 BRANCH_EDGE (bb)->probability = prob;
795 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
796 }
797 else
798 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
799 }
800
801 /* Combine predictions into single probability and store them into CFG.
802 Remove now useless prediction entries. */
803
804 static void
combine_predictions_for_bb(basic_block bb)805 combine_predictions_for_bb (basic_block bb)
806 {
807 int best_probability = PROB_EVEN;
808 enum br_predictor best_predictor = END_PREDICTORS;
809 int combined_probability = REG_BR_PROB_BASE / 2;
810 int d;
811 bool first_match = false;
812 bool found = false;
813 struct edge_prediction *pred;
814 int nedges = 0;
815 edge e, first = NULL, second = NULL;
816 edge_iterator ei;
817 void **preds;
818
819 FOR_EACH_EDGE (e, ei, bb->succs)
820 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
821 {
822 nedges ++;
823 if (first && !second)
824 second = e;
825 if (!first)
826 first = e;
827 }
828
829 /* When there is no successor or only one choice, prediction is easy.
830
831 We are lazy for now and predict only basic blocks with two outgoing
832 edges. It is possible to predict generic case too, but we have to
833 ignore first match heuristics and do more involved combining. Implement
834 this later. */
835 if (nedges != 2)
836 {
837 if (!bb->count)
838 set_even_probabilities (bb);
839 clear_bb_predictions (bb);
840 if (dump_file)
841 fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
842 nedges, bb->index);
843 return;
844 }
845
846 if (dump_file)
847 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
848
849 preds = pointer_map_contains (bb_predictions, bb);
850 if (preds)
851 {
852 /* We implement "first match" heuristics and use probability guessed
853 by predictor with smallest index. */
854 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
855 {
856 enum br_predictor predictor = pred->ep_predictor;
857 int probability = pred->ep_probability;
858
859 if (pred->ep_edge != first)
860 probability = REG_BR_PROB_BASE - probability;
861
862 found = true;
863 /* First match heuristics would be widly confused if we predicted
864 both directions. */
865 if (best_predictor > predictor)
866 {
867 struct edge_prediction *pred2;
868 int prob = probability;
869
870 for (pred2 = (struct edge_prediction *) *preds; pred2; pred2 = pred2->ep_next)
871 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
872 {
873 int probability2 = pred->ep_probability;
874
875 if (pred2->ep_edge != first)
876 probability2 = REG_BR_PROB_BASE - probability2;
877
878 if ((probability < REG_BR_PROB_BASE / 2) !=
879 (probability2 < REG_BR_PROB_BASE / 2))
880 break;
881
882 /* If the same predictor later gave better result, go for it! */
883 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
884 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
885 prob = probability2;
886 }
887 if (!pred2)
888 best_probability = prob, best_predictor = predictor;
889 }
890
891 d = (combined_probability * probability
892 + (REG_BR_PROB_BASE - combined_probability)
893 * (REG_BR_PROB_BASE - probability));
894
895 /* Use FP math to avoid overflows of 32bit integers. */
896 if (d == 0)
897 /* If one probability is 0% and one 100%, avoid division by zero. */
898 combined_probability = REG_BR_PROB_BASE / 2;
899 else
900 combined_probability = (((double) combined_probability)
901 * probability
902 * REG_BR_PROB_BASE / d + 0.5);
903 }
904 }
905
906 /* Decide which heuristic to use. In case we didn't match anything,
907 use no_prediction heuristic, in case we did match, use either
908 first match or Dempster-Shaffer theory depending on the flags. */
909
910 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
911 first_match = true;
912
913 if (!found)
914 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
915 else
916 {
917 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
918 !first_match);
919 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
920 first_match);
921 }
922
923 if (first_match)
924 combined_probability = best_probability;
925 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
926
927 if (preds)
928 {
929 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
930 {
931 enum br_predictor predictor = pred->ep_predictor;
932 int probability = pred->ep_probability;
933
934 if (pred->ep_edge != EDGE_SUCC (bb, 0))
935 probability = REG_BR_PROB_BASE - probability;
936 dump_prediction (dump_file, predictor, probability, bb,
937 !first_match || best_predictor == predictor);
938 }
939 }
940 clear_bb_predictions (bb);
941
942 if (!bb->count)
943 {
944 first->probability = combined_probability;
945 second->probability = REG_BR_PROB_BASE - combined_probability;
946 }
947 }
948
949 /* Predict edge probabilities by exploiting loop structure. */
950
951 static void
predict_loops(void)952 predict_loops (void)
953 {
954 loop_iterator li;
955 struct loop *loop;
956
957 /* Try to predict out blocks in a loop that are not part of a
958 natural loop. */
959 FOR_EACH_LOOP (li, loop, 0)
960 {
961 basic_block bb, *bbs;
962 unsigned j, n_exits;
963 VEC (edge, heap) *exits;
964 struct tree_niter_desc niter_desc;
965 edge ex;
966
967 exits = get_loop_exit_edges (loop);
968 n_exits = VEC_length (edge, exits);
969
970 FOR_EACH_VEC_ELT (edge, exits, j, ex)
971 {
972 tree niter = NULL;
973 HOST_WIDE_INT nitercst;
974 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
975 int probability;
976 enum br_predictor predictor;
977
978 if (number_of_iterations_exit (loop, ex, &niter_desc, false))
979 niter = niter_desc.niter;
980 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
981 niter = loop_niter_by_eval (loop, ex);
982
983 if (TREE_CODE (niter) == INTEGER_CST)
984 {
985 if (host_integerp (niter, 1)
986 && max
987 && compare_tree_int (niter, max - 1) == -1)
988 nitercst = tree_low_cst (niter, 1) + 1;
989 else
990 nitercst = max;
991 predictor = PRED_LOOP_ITERATIONS;
992 }
993 /* If we have just one exit and we can derive some information about
994 the number of iterations of the loop from the statements inside
995 the loop, use it to predict this exit. */
996 else if (n_exits == 1)
997 {
998 nitercst = max_stmt_executions_int (loop, false);
999 if (nitercst < 0)
1000 continue;
1001 if (nitercst > max)
1002 nitercst = max;
1003
1004 predictor = PRED_LOOP_ITERATIONS_GUESSED;
1005 }
1006 else
1007 continue;
1008
1009 /* If the prediction for number of iterations is zero, do not
1010 predict the exit edges. */
1011 if (nitercst == 0)
1012 continue;
1013
1014 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
1015 predict_edge (ex, predictor, probability);
1016 }
1017 VEC_free (edge, heap, exits);
1018
1019 bbs = get_loop_body (loop);
1020
1021 for (j = 0; j < loop->num_nodes; j++)
1022 {
1023 int header_found = 0;
1024 edge e;
1025 edge_iterator ei;
1026
1027 bb = bbs[j];
1028
1029 /* Bypass loop heuristics on continue statement. These
1030 statements construct loops via "non-loop" constructs
1031 in the source language and are better to be handled
1032 separately. */
1033 if (predicted_by_p (bb, PRED_CONTINUE))
1034 continue;
1035
1036 /* Loop branch heuristics - predict an edge back to a
1037 loop's head as taken. */
1038 if (bb == loop->latch)
1039 {
1040 e = find_edge (loop->latch, loop->header);
1041 if (e)
1042 {
1043 header_found = 1;
1044 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
1045 }
1046 }
1047
1048 /* Loop exit heuristics - predict an edge exiting the loop if the
1049 conditional has no loop header successors as not taken. */
1050 if (!header_found
1051 /* If we already used more reliable loop exit predictors, do not
1052 bother with PRED_LOOP_EXIT. */
1053 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
1054 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
1055 {
1056 /* For loop with many exits we don't want to predict all exits
1057 with the pretty large probability, because if all exits are
1058 considered in row, the loop would be predicted to iterate
1059 almost never. The code to divide probability by number of
1060 exits is very rough. It should compute the number of exits
1061 taken in each patch through function (not the overall number
1062 of exits that might be a lot higher for loops with wide switch
1063 statements in them) and compute n-th square root.
1064
1065 We limit the minimal probability by 2% to avoid
1066 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1067 as this was causing regression in perl benchmark containing such
1068 a wide loop. */
1069
1070 int probability = ((REG_BR_PROB_BASE
1071 - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
1072 / n_exits);
1073 if (probability < HITRATE (2))
1074 probability = HITRATE (2);
1075 FOR_EACH_EDGE (e, ei, bb->succs)
1076 if (e->dest->index < NUM_FIXED_BLOCKS
1077 || !flow_bb_inside_loop_p (loop, e->dest))
1078 predict_edge (e, PRED_LOOP_EXIT, probability);
1079 }
1080 }
1081
1082 /* Free basic blocks from get_loop_body. */
1083 free (bbs);
1084 }
1085 }
1086
1087 /* Attempt to predict probabilities of BB outgoing edges using local
1088 properties. */
1089 static void
bb_estimate_probability_locally(basic_block bb)1090 bb_estimate_probability_locally (basic_block bb)
1091 {
1092 rtx last_insn = BB_END (bb);
1093 rtx cond;
1094
1095 if (! can_predict_insn_p (last_insn))
1096 return;
1097 cond = get_condition (last_insn, NULL, false, false);
1098 if (! cond)
1099 return;
1100
1101 /* Try "pointer heuristic."
1102 A comparison ptr == 0 is predicted as false.
1103 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1104 if (COMPARISON_P (cond)
1105 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
1106 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
1107 {
1108 if (GET_CODE (cond) == EQ)
1109 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
1110 else if (GET_CODE (cond) == NE)
1111 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
1112 }
1113 else
1114
1115 /* Try "opcode heuristic."
1116 EQ tests are usually false and NE tests are usually true. Also,
1117 most quantities are positive, so we can make the appropriate guesses
1118 about signed comparisons against zero. */
1119 switch (GET_CODE (cond))
1120 {
1121 case CONST_INT:
1122 /* Unconditional branch. */
1123 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
1124 cond == const0_rtx ? NOT_TAKEN : TAKEN);
1125 break;
1126
1127 case EQ:
1128 case UNEQ:
1129 /* Floating point comparisons appears to behave in a very
1130 unpredictable way because of special role of = tests in
1131 FP code. */
1132 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1133 ;
1134 /* Comparisons with 0 are often used for booleans and there is
1135 nothing useful to predict about them. */
1136 else if (XEXP (cond, 1) == const0_rtx
1137 || XEXP (cond, 0) == const0_rtx)
1138 ;
1139 else
1140 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
1141 break;
1142
1143 case NE:
1144 case LTGT:
1145 /* Floating point comparisons appears to behave in a very
1146 unpredictable way because of special role of = tests in
1147 FP code. */
1148 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1149 ;
1150 /* Comparisons with 0 are often used for booleans and there is
1151 nothing useful to predict about them. */
1152 else if (XEXP (cond, 1) == const0_rtx
1153 || XEXP (cond, 0) == const0_rtx)
1154 ;
1155 else
1156 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
1157 break;
1158
1159 case ORDERED:
1160 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
1161 break;
1162
1163 case UNORDERED:
1164 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
1165 break;
1166
1167 case LE:
1168 case LT:
1169 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1170 || XEXP (cond, 1) == constm1_rtx)
1171 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
1172 break;
1173
1174 case GE:
1175 case GT:
1176 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1177 || XEXP (cond, 1) == constm1_rtx)
1178 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
1179 break;
1180
1181 default:
1182 break;
1183 }
1184 }
1185
1186 /* Set edge->probability for each successor edge of BB. */
1187 void
guess_outgoing_edge_probabilities(basic_block bb)1188 guess_outgoing_edge_probabilities (basic_block bb)
1189 {
1190 bb_estimate_probability_locally (bb);
1191 combine_predictions_for_insn (BB_END (bb), bb);
1192 }
1193
1194 static tree expr_expected_value (tree, bitmap);
1195
1196 /* Helper function for expr_expected_value. */
1197
1198 static tree
expr_expected_value_1(tree type,tree op0,enum tree_code code,tree op1,bitmap visited)1199 expr_expected_value_1 (tree type, tree op0, enum tree_code code,
1200 tree op1, bitmap visited)
1201 {
1202 gimple def;
1203
1204 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1205 {
1206 if (TREE_CONSTANT (op0))
1207 return op0;
1208
1209 if (code != SSA_NAME)
1210 return NULL_TREE;
1211
1212 def = SSA_NAME_DEF_STMT (op0);
1213
1214 /* If we were already here, break the infinite cycle. */
1215 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
1216 return NULL;
1217
1218 if (gimple_code (def) == GIMPLE_PHI)
1219 {
1220 /* All the arguments of the PHI node must have the same constant
1221 length. */
1222 int i, n = gimple_phi_num_args (def);
1223 tree val = NULL, new_val;
1224
1225 for (i = 0; i < n; i++)
1226 {
1227 tree arg = PHI_ARG_DEF (def, i);
1228
1229 /* If this PHI has itself as an argument, we cannot
1230 determine the string length of this argument. However,
1231 if we can find an expected constant value for the other
1232 PHI args then we can still be sure that this is
1233 likely a constant. So be optimistic and just
1234 continue with the next argument. */
1235 if (arg == PHI_RESULT (def))
1236 continue;
1237
1238 new_val = expr_expected_value (arg, visited);
1239 if (!new_val)
1240 return NULL;
1241 if (!val)
1242 val = new_val;
1243 else if (!operand_equal_p (val, new_val, false))
1244 return NULL;
1245 }
1246 return val;
1247 }
1248 if (is_gimple_assign (def))
1249 {
1250 if (gimple_assign_lhs (def) != op0)
1251 return NULL;
1252
1253 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
1254 gimple_assign_rhs1 (def),
1255 gimple_assign_rhs_code (def),
1256 gimple_assign_rhs2 (def),
1257 visited);
1258 }
1259
1260 if (is_gimple_call (def))
1261 {
1262 tree decl = gimple_call_fndecl (def);
1263 if (!decl)
1264 return NULL;
1265 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
1266 switch (DECL_FUNCTION_CODE (decl))
1267 {
1268 case BUILT_IN_EXPECT:
1269 {
1270 tree val;
1271 if (gimple_call_num_args (def) != 2)
1272 return NULL;
1273 val = gimple_call_arg (def, 0);
1274 if (TREE_CONSTANT (val))
1275 return val;
1276 return gimple_call_arg (def, 1);
1277 }
1278
1279 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
1280 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
1281 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
1282 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
1283 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
1284 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
1285 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
1286 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
1287 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
1288 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
1289 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
1290 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
1291 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
1292 /* Assume that any given atomic operation has low contention,
1293 and thus the compare-and-swap operation succeeds. */
1294 return boolean_true_node;
1295 }
1296 }
1297
1298 return NULL;
1299 }
1300
1301 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
1302 {
1303 tree res;
1304 op0 = expr_expected_value (op0, visited);
1305 if (!op0)
1306 return NULL;
1307 op1 = expr_expected_value (op1, visited);
1308 if (!op1)
1309 return NULL;
1310 res = fold_build2 (code, type, op0, op1);
1311 if (TREE_CONSTANT (res))
1312 return res;
1313 return NULL;
1314 }
1315 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
1316 {
1317 tree res;
1318 op0 = expr_expected_value (op0, visited);
1319 if (!op0)
1320 return NULL;
1321 res = fold_build1 (code, type, op0);
1322 if (TREE_CONSTANT (res))
1323 return res;
1324 return NULL;
1325 }
1326 return NULL;
1327 }
1328
1329 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1330 The function is used by builtin_expect branch predictor so the evidence
1331 must come from this construct and additional possible constant folding.
1332
1333 We may want to implement more involved value guess (such as value range
1334 propagation based prediction), but such tricks shall go to new
1335 implementation. */
1336
1337 static tree
expr_expected_value(tree expr,bitmap visited)1338 expr_expected_value (tree expr, bitmap visited)
1339 {
1340 enum tree_code code;
1341 tree op0, op1;
1342
1343 if (TREE_CONSTANT (expr))
1344 return expr;
1345
1346 extract_ops_from_tree (expr, &code, &op0, &op1);
1347 return expr_expected_value_1 (TREE_TYPE (expr),
1348 op0, code, op1, visited);
1349 }
1350
1351
1352 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1353 we no longer need. */
1354 static unsigned int
strip_predict_hints(void)1355 strip_predict_hints (void)
1356 {
1357 basic_block bb;
1358 gimple ass_stmt;
1359 tree var;
1360
1361 FOR_EACH_BB (bb)
1362 {
1363 gimple_stmt_iterator bi;
1364 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
1365 {
1366 gimple stmt = gsi_stmt (bi);
1367
1368 if (gimple_code (stmt) == GIMPLE_PREDICT)
1369 {
1370 gsi_remove (&bi, true);
1371 continue;
1372 }
1373 else if (gimple_code (stmt) == GIMPLE_CALL)
1374 {
1375 tree fndecl = gimple_call_fndecl (stmt);
1376
1377 if (fndecl
1378 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1379 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
1380 && gimple_call_num_args (stmt) == 2)
1381 {
1382 var = gimple_call_lhs (stmt);
1383 if (var)
1384 {
1385 ass_stmt
1386 = gimple_build_assign (var, gimple_call_arg (stmt, 0));
1387 gsi_replace (&bi, ass_stmt, true);
1388 }
1389 else
1390 {
1391 gsi_remove (&bi, true);
1392 continue;
1393 }
1394 }
1395 }
1396 gsi_next (&bi);
1397 }
1398 }
1399 return 0;
1400 }
1401
1402 /* Predict using opcode of the last statement in basic block. */
1403 static void
tree_predict_by_opcode(basic_block bb)1404 tree_predict_by_opcode (basic_block bb)
1405 {
1406 gimple stmt = last_stmt (bb);
1407 edge then_edge;
1408 tree op0, op1;
1409 tree type;
1410 tree val;
1411 enum tree_code cmp;
1412 bitmap visited;
1413 edge_iterator ei;
1414
1415 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1416 return;
1417 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1418 if (then_edge->flags & EDGE_TRUE_VALUE)
1419 break;
1420 op0 = gimple_cond_lhs (stmt);
1421 op1 = gimple_cond_rhs (stmt);
1422 cmp = gimple_cond_code (stmt);
1423 type = TREE_TYPE (op0);
1424 visited = BITMAP_ALLOC (NULL);
1425 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited);
1426 BITMAP_FREE (visited);
1427 if (val)
1428 {
1429 if (integer_zerop (val))
1430 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1431 else
1432 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1433 return;
1434 }
1435 /* Try "pointer heuristic."
1436 A comparison ptr == 0 is predicted as false.
1437 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1438 if (POINTER_TYPE_P (type))
1439 {
1440 if (cmp == EQ_EXPR)
1441 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1442 else if (cmp == NE_EXPR)
1443 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1444 }
1445 else
1446
1447 /* Try "opcode heuristic."
1448 EQ tests are usually false and NE tests are usually true. Also,
1449 most quantities are positive, so we can make the appropriate guesses
1450 about signed comparisons against zero. */
1451 switch (cmp)
1452 {
1453 case EQ_EXPR:
1454 case UNEQ_EXPR:
1455 /* Floating point comparisons appears to behave in a very
1456 unpredictable way because of special role of = tests in
1457 FP code. */
1458 if (FLOAT_TYPE_P (type))
1459 ;
1460 /* Comparisons with 0 are often used for booleans and there is
1461 nothing useful to predict about them. */
1462 else if (integer_zerop (op0) || integer_zerop (op1))
1463 ;
1464 else
1465 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1466 break;
1467
1468 case NE_EXPR:
1469 case LTGT_EXPR:
1470 /* Floating point comparisons appears to behave in a very
1471 unpredictable way because of special role of = tests in
1472 FP code. */
1473 if (FLOAT_TYPE_P (type))
1474 ;
1475 /* Comparisons with 0 are often used for booleans and there is
1476 nothing useful to predict about them. */
1477 else if (integer_zerop (op0)
1478 || integer_zerop (op1))
1479 ;
1480 else
1481 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1482 break;
1483
1484 case ORDERED_EXPR:
1485 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1486 break;
1487
1488 case UNORDERED_EXPR:
1489 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1490 break;
1491
1492 case LE_EXPR:
1493 case LT_EXPR:
1494 if (integer_zerop (op1)
1495 || integer_onep (op1)
1496 || integer_all_onesp (op1)
1497 || real_zerop (op1)
1498 || real_onep (op1)
1499 || real_minus_onep (op1))
1500 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1501 break;
1502
1503 case GE_EXPR:
1504 case GT_EXPR:
1505 if (integer_zerop (op1)
1506 || integer_onep (op1)
1507 || integer_all_onesp (op1)
1508 || real_zerop (op1)
1509 || real_onep (op1)
1510 || real_minus_onep (op1))
1511 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1512 break;
1513
1514 default:
1515 break;
1516 }
1517 }
1518
1519 /* Try to guess whether the value of return means error code. */
1520
1521 static enum br_predictor
return_prediction(tree val,enum prediction * prediction)1522 return_prediction (tree val, enum prediction *prediction)
1523 {
1524 /* VOID. */
1525 if (!val)
1526 return PRED_NO_PREDICTION;
1527 /* Different heuristics for pointers and scalars. */
1528 if (POINTER_TYPE_P (TREE_TYPE (val)))
1529 {
1530 /* NULL is usually not returned. */
1531 if (integer_zerop (val))
1532 {
1533 *prediction = NOT_TAKEN;
1534 return PRED_NULL_RETURN;
1535 }
1536 }
1537 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1538 {
1539 /* Negative return values are often used to indicate
1540 errors. */
1541 if (TREE_CODE (val) == INTEGER_CST
1542 && tree_int_cst_sgn (val) < 0)
1543 {
1544 *prediction = NOT_TAKEN;
1545 return PRED_NEGATIVE_RETURN;
1546 }
1547 /* Constant return values seems to be commonly taken.
1548 Zero/one often represent booleans so exclude them from the
1549 heuristics. */
1550 if (TREE_CONSTANT (val)
1551 && (!integer_zerop (val) && !integer_onep (val)))
1552 {
1553 *prediction = TAKEN;
1554 return PRED_CONST_RETURN;
1555 }
1556 }
1557 return PRED_NO_PREDICTION;
1558 }
1559
1560 /* Find the basic block with return expression and look up for possible
1561 return value trying to apply RETURN_PREDICTION heuristics. */
1562 static void
apply_return_prediction(void)1563 apply_return_prediction (void)
1564 {
1565 gimple return_stmt = NULL;
1566 tree return_val;
1567 edge e;
1568 gimple phi;
1569 int phi_num_args, i;
1570 enum br_predictor pred;
1571 enum prediction direction;
1572 edge_iterator ei;
1573
1574 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1575 {
1576 return_stmt = last_stmt (e->src);
1577 if (return_stmt
1578 && gimple_code (return_stmt) == GIMPLE_RETURN)
1579 break;
1580 }
1581 if (!e)
1582 return;
1583 return_val = gimple_return_retval (return_stmt);
1584 if (!return_val)
1585 return;
1586 if (TREE_CODE (return_val) != SSA_NAME
1587 || !SSA_NAME_DEF_STMT (return_val)
1588 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
1589 return;
1590 phi = SSA_NAME_DEF_STMT (return_val);
1591 phi_num_args = gimple_phi_num_args (phi);
1592 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1593
1594 /* Avoid the degenerate case where all return values form the function
1595 belongs to same category (ie they are all positive constants)
1596 so we can hardly say something about them. */
1597 for (i = 1; i < phi_num_args; i++)
1598 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1599 break;
1600 if (i != phi_num_args)
1601 for (i = 0; i < phi_num_args; i++)
1602 {
1603 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1604 if (pred != PRED_NO_PREDICTION)
1605 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
1606 direction);
1607 }
1608 }
1609
1610 /* Look for basic block that contains unlikely to happen events
1611 (such as noreturn calls) and mark all paths leading to execution
1612 of this basic blocks as unlikely. */
1613
1614 static void
tree_bb_level_predictions(void)1615 tree_bb_level_predictions (void)
1616 {
1617 basic_block bb;
1618 bool has_return_edges = false;
1619 edge e;
1620 edge_iterator ei;
1621
1622 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1623 if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
1624 {
1625 has_return_edges = true;
1626 break;
1627 }
1628
1629 apply_return_prediction ();
1630
1631 FOR_EACH_BB (bb)
1632 {
1633 gimple_stmt_iterator gsi;
1634
1635 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1636 {
1637 gimple stmt = gsi_stmt (gsi);
1638 tree decl;
1639
1640 if (is_gimple_call (stmt))
1641 {
1642 if ((gimple_call_flags (stmt) & ECF_NORETURN)
1643 && has_return_edges)
1644 predict_paths_leading_to (bb, PRED_NORETURN,
1645 NOT_TAKEN);
1646 decl = gimple_call_fndecl (stmt);
1647 if (decl
1648 && lookup_attribute ("cold",
1649 DECL_ATTRIBUTES (decl)))
1650 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
1651 NOT_TAKEN);
1652 }
1653 else if (gimple_code (stmt) == GIMPLE_PREDICT)
1654 {
1655 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
1656 gimple_predict_outcome (stmt));
1657 /* Keep GIMPLE_PREDICT around so early inlining will propagate
1658 hints to callers. */
1659 }
1660 }
1661 }
1662 }
1663
1664 #ifdef ENABLE_CHECKING
1665
1666 /* Callback for pointer_map_traverse, asserts that the pointer map is
1667 empty. */
1668
1669 static bool
assert_is_empty(const void * key ATTRIBUTE_UNUSED,void ** value,void * data ATTRIBUTE_UNUSED)1670 assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
1671 void *data ATTRIBUTE_UNUSED)
1672 {
1673 gcc_assert (!*value);
1674 return false;
1675 }
1676 #endif
1677
1678 /* Predict branch probabilities and estimate profile for basic block BB. */
1679
1680 static void
tree_estimate_probability_bb(basic_block bb)1681 tree_estimate_probability_bb (basic_block bb)
1682 {
1683 edge e;
1684 edge_iterator ei;
1685 gimple last;
1686
1687 FOR_EACH_EDGE (e, ei, bb->succs)
1688 {
1689 /* Predict early returns to be probable, as we've already taken
1690 care for error returns and other cases are often used for
1691 fast paths through function.
1692
1693 Since we've already removed the return statements, we are
1694 looking for CFG like:
1695
1696 if (conditional)
1697 {
1698 ..
1699 goto return_block
1700 }
1701 some other blocks
1702 return_block:
1703 return_stmt. */
1704 if (e->dest != bb->next_bb
1705 && e->dest != EXIT_BLOCK_PTR
1706 && single_succ_p (e->dest)
1707 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
1708 && (last = last_stmt (e->dest)) != NULL
1709 && gimple_code (last) == GIMPLE_RETURN)
1710 {
1711 edge e1;
1712 edge_iterator ei1;
1713
1714 if (single_succ_p (bb))
1715 {
1716 FOR_EACH_EDGE (e1, ei1, bb->preds)
1717 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1718 && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1719 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
1720 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1721 }
1722 else
1723 if (!predicted_by_p (e->src, PRED_NULL_RETURN)
1724 && !predicted_by_p (e->src, PRED_CONST_RETURN)
1725 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
1726 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1727 }
1728
1729 /* Look for block we are guarding (ie we dominate it,
1730 but it doesn't postdominate us). */
1731 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1732 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1733 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1734 {
1735 gimple_stmt_iterator bi;
1736
1737 /* The call heuristic claims that a guarded function call
1738 is improbable. This is because such calls are often used
1739 to signal exceptional situations such as printing error
1740 messages. */
1741 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
1742 gsi_next (&bi))
1743 {
1744 gimple stmt = gsi_stmt (bi);
1745 if (is_gimple_call (stmt)
1746 /* Constant and pure calls are hardly used to signalize
1747 something exceptional. */
1748 && gimple_has_side_effects (stmt))
1749 {
1750 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1751 break;
1752 }
1753 }
1754 }
1755 }
1756 tree_predict_by_opcode (bb);
1757 }
1758
1759 /* Predict branch probabilities and estimate profile of the tree CFG.
1760 This function can be called from the loop optimizers to recompute
1761 the profile information. */
1762
1763 void
tree_estimate_probability(void)1764 tree_estimate_probability (void)
1765 {
1766 basic_block bb;
1767
1768 add_noreturn_fake_exit_edges ();
1769 connect_infinite_loops_to_exit ();
1770 /* We use loop_niter_by_eval, which requires that the loops have
1771 preheaders. */
1772 create_preheaders (CP_SIMPLE_PREHEADERS);
1773 calculate_dominance_info (CDI_POST_DOMINATORS);
1774
1775 bb_predictions = pointer_map_create ();
1776 tree_bb_level_predictions ();
1777 record_loop_exits ();
1778
1779 if (number_of_loops () > 1)
1780 predict_loops ();
1781
1782 FOR_EACH_BB (bb)
1783 tree_estimate_probability_bb (bb);
1784
1785 FOR_EACH_BB (bb)
1786 combine_predictions_for_bb (bb);
1787
1788 #ifdef ENABLE_CHECKING
1789 pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
1790 #endif
1791 pointer_map_destroy (bb_predictions);
1792 bb_predictions = NULL;
1793
1794 estimate_bb_frequencies ();
1795 free_dominance_info (CDI_POST_DOMINATORS);
1796 remove_fake_exit_edges ();
1797 }
1798
1799 /* Predict branch probabilities and estimate profile of the tree CFG.
1800 This is the driver function for PASS_PROFILE. */
1801
1802 static unsigned int
tree_estimate_probability_driver(void)1803 tree_estimate_probability_driver (void)
1804 {
1805 unsigned nb_loops;
1806
1807 loop_optimizer_init (0);
1808 if (dump_file && (dump_flags & TDF_DETAILS))
1809 flow_loops_dump (dump_file, NULL, 0);
1810
1811 mark_irreducible_loops ();
1812
1813 nb_loops = number_of_loops ();
1814 if (nb_loops > 1)
1815 scev_initialize ();
1816
1817 tree_estimate_probability ();
1818
1819 if (nb_loops > 1)
1820 scev_finalize ();
1821
1822 loop_optimizer_finalize ();
1823 if (dump_file && (dump_flags & TDF_DETAILS))
1824 gimple_dump_cfg (dump_file, dump_flags);
1825 if (profile_status == PROFILE_ABSENT)
1826 profile_status = PROFILE_GUESSED;
1827 return 0;
1828 }
1829
1830 /* Predict edges to successors of CUR whose sources are not postdominated by
1831 BB by PRED and recurse to all postdominators. */
1832
1833 static void
predict_paths_for_bb(basic_block cur,basic_block bb,enum br_predictor pred,enum prediction taken,bitmap visited)1834 predict_paths_for_bb (basic_block cur, basic_block bb,
1835 enum br_predictor pred,
1836 enum prediction taken,
1837 bitmap visited)
1838 {
1839 edge e;
1840 edge_iterator ei;
1841 basic_block son;
1842
1843 /* We are looking for all edges forming edge cut induced by
1844 set of all blocks postdominated by BB. */
1845 FOR_EACH_EDGE (e, ei, cur->preds)
1846 if (e->src->index >= NUM_FIXED_BLOCKS
1847 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
1848 {
1849 edge e2;
1850 edge_iterator ei2;
1851 bool found = false;
1852
1853 /* Ignore fake edges and eh, we predict them as not taken anyway. */
1854 if (e->flags & (EDGE_EH | EDGE_FAKE))
1855 continue;
1856 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
1857
1858 /* See if there is an edge from e->src that is not abnormal
1859 and does not lead to BB. */
1860 FOR_EACH_EDGE (e2, ei2, e->src->succs)
1861 if (e2 != e
1862 && !(e2->flags & (EDGE_EH | EDGE_FAKE))
1863 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
1864 {
1865 found = true;
1866 break;
1867 }
1868
1869 /* If there is non-abnormal path leaving e->src, predict edge
1870 using predictor. Otherwise we need to look for paths
1871 leading to e->src.
1872
1873 The second may lead to infinite loop in the case we are predicitng
1874 regions that are only reachable by abnormal edges. We simply
1875 prevent visiting given BB twice. */
1876 if (found)
1877 predict_edge_def (e, pred, taken);
1878 else if (bitmap_set_bit (visited, e->src->index))
1879 predict_paths_for_bb (e->src, e->src, pred, taken, visited);
1880 }
1881 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
1882 son;
1883 son = next_dom_son (CDI_POST_DOMINATORS, son))
1884 predict_paths_for_bb (son, bb, pred, taken, visited);
1885 }
1886
1887 /* Sets branch probabilities according to PREDiction and
1888 FLAGS. */
1889
1890 static void
predict_paths_leading_to(basic_block bb,enum br_predictor pred,enum prediction taken)1891 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
1892 enum prediction taken)
1893 {
1894 bitmap visited = BITMAP_ALLOC (NULL);
1895 predict_paths_for_bb (bb, bb, pred, taken, visited);
1896 BITMAP_FREE (visited);
1897 }
1898
1899 /* Like predict_paths_leading_to but take edge instead of basic block. */
1900
1901 static void
predict_paths_leading_to_edge(edge e,enum br_predictor pred,enum prediction taken)1902 predict_paths_leading_to_edge (edge e, enum br_predictor pred,
1903 enum prediction taken)
1904 {
1905 bool has_nonloop_edge = false;
1906 edge_iterator ei;
1907 edge e2;
1908
1909 basic_block bb = e->src;
1910 FOR_EACH_EDGE (e2, ei, bb->succs)
1911 if (e2->dest != e->src && e2->dest != e->dest
1912 && !(e->flags & (EDGE_EH | EDGE_FAKE))
1913 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
1914 {
1915 has_nonloop_edge = true;
1916 break;
1917 }
1918 if (!has_nonloop_edge)
1919 {
1920 bitmap visited = BITMAP_ALLOC (NULL);
1921 predict_paths_for_bb (bb, bb, pred, taken, visited);
1922 BITMAP_FREE (visited);
1923 }
1924 else
1925 predict_edge_def (e, pred, taken);
1926 }
1927
1928 /* This is used to carry information about basic blocks. It is
1929 attached to the AUX field of the standard CFG block. */
1930
1931 typedef struct block_info_def
1932 {
1933 /* Estimated frequency of execution of basic_block. */
1934 sreal frequency;
1935
1936 /* To keep queue of basic blocks to process. */
1937 basic_block next;
1938
1939 /* Number of predecessors we need to visit first. */
1940 int npredecessors;
1941 } *block_info;
1942
1943 /* Similar information for edges. */
1944 typedef struct edge_info_def
1945 {
1946 /* In case edge is a loopback edge, the probability edge will be reached
1947 in case header is. Estimated number of iterations of the loop can be
1948 then computed as 1 / (1 - back_edge_prob). */
1949 sreal back_edge_prob;
1950 /* True if the edge is a loopback edge in the natural loop. */
1951 unsigned int back_edge:1;
1952 } *edge_info;
1953
1954 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1955 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1956
1957 /* Helper function for estimate_bb_frequencies.
1958 Propagate the frequencies in blocks marked in
1959 TOVISIT, starting in HEAD. */
1960
1961 static void
propagate_freq(basic_block head,bitmap tovisit)1962 propagate_freq (basic_block head, bitmap tovisit)
1963 {
1964 basic_block bb;
1965 basic_block last;
1966 unsigned i;
1967 edge e;
1968 basic_block nextbb;
1969 bitmap_iterator bi;
1970
1971 /* For each basic block we need to visit count number of his predecessors
1972 we need to visit first. */
1973 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1974 {
1975 edge_iterator ei;
1976 int count = 0;
1977
1978 bb = BASIC_BLOCK (i);
1979
1980 FOR_EACH_EDGE (e, ei, bb->preds)
1981 {
1982 bool visit = bitmap_bit_p (tovisit, e->src->index);
1983
1984 if (visit && !(e->flags & EDGE_DFS_BACK))
1985 count++;
1986 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1987 fprintf (dump_file,
1988 "Irreducible region hit, ignoring edge to %i->%i\n",
1989 e->src->index, bb->index);
1990 }
1991 BLOCK_INFO (bb)->npredecessors = count;
1992 /* When function never returns, we will never process exit block. */
1993 if (!count && bb == EXIT_BLOCK_PTR)
1994 bb->count = bb->frequency = 0;
1995 }
1996
1997 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1998 last = head;
1999 for (bb = head; bb; bb = nextbb)
2000 {
2001 edge_iterator ei;
2002 sreal cyclic_probability, frequency;
2003
2004 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
2005 memcpy (&frequency, &real_zero, sizeof (real_zero));
2006
2007 nextbb = BLOCK_INFO (bb)->next;
2008 BLOCK_INFO (bb)->next = NULL;
2009
2010 /* Compute frequency of basic block. */
2011 if (bb != head)
2012 {
2013 #ifdef ENABLE_CHECKING
2014 FOR_EACH_EDGE (e, ei, bb->preds)
2015 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
2016 || (e->flags & EDGE_DFS_BACK));
2017 #endif
2018
2019 FOR_EACH_EDGE (e, ei, bb->preds)
2020 if (EDGE_INFO (e)->back_edge)
2021 {
2022 sreal_add (&cyclic_probability, &cyclic_probability,
2023 &EDGE_INFO (e)->back_edge_prob);
2024 }
2025 else if (!(e->flags & EDGE_DFS_BACK))
2026 {
2027 sreal tmp;
2028
2029 /* frequency += (e->probability
2030 * BLOCK_INFO (e->src)->frequency /
2031 REG_BR_PROB_BASE); */
2032
2033 sreal_init (&tmp, e->probability, 0);
2034 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
2035 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
2036 sreal_add (&frequency, &frequency, &tmp);
2037 }
2038
2039 if (sreal_compare (&cyclic_probability, &real_zero) == 0)
2040 {
2041 memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
2042 sizeof (frequency));
2043 }
2044 else
2045 {
2046 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
2047 {
2048 memcpy (&cyclic_probability, &real_almost_one,
2049 sizeof (real_almost_one));
2050 }
2051
2052 /* BLOCK_INFO (bb)->frequency = frequency
2053 / (1 - cyclic_probability) */
2054
2055 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
2056 sreal_div (&BLOCK_INFO (bb)->frequency,
2057 &frequency, &cyclic_probability);
2058 }
2059 }
2060
2061 bitmap_clear_bit (tovisit, bb->index);
2062
2063 e = find_edge (bb, head);
2064 if (e)
2065 {
2066 sreal tmp;
2067
2068 /* EDGE_INFO (e)->back_edge_prob
2069 = ((e->probability * BLOCK_INFO (bb)->frequency)
2070 / REG_BR_PROB_BASE); */
2071
2072 sreal_init (&tmp, e->probability, 0);
2073 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
2074 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2075 &tmp, &real_inv_br_prob_base);
2076 }
2077
2078 /* Propagate to successor blocks. */
2079 FOR_EACH_EDGE (e, ei, bb->succs)
2080 if (!(e->flags & EDGE_DFS_BACK)
2081 && BLOCK_INFO (e->dest)->npredecessors)
2082 {
2083 BLOCK_INFO (e->dest)->npredecessors--;
2084 if (!BLOCK_INFO (e->dest)->npredecessors)
2085 {
2086 if (!nextbb)
2087 nextbb = e->dest;
2088 else
2089 BLOCK_INFO (last)->next = e->dest;
2090
2091 last = e->dest;
2092 }
2093 }
2094 }
2095 }
2096
2097 /* Estimate probabilities of loopback edges in loops at same nest level. */
2098
2099 static void
estimate_loops_at_level(struct loop * first_loop)2100 estimate_loops_at_level (struct loop *first_loop)
2101 {
2102 struct loop *loop;
2103
2104 for (loop = first_loop; loop; loop = loop->next)
2105 {
2106 edge e;
2107 basic_block *bbs;
2108 unsigned i;
2109 bitmap tovisit = BITMAP_ALLOC (NULL);
2110
2111 estimate_loops_at_level (loop->inner);
2112
2113 /* Find current loop back edge and mark it. */
2114 e = loop_latch_edge (loop);
2115 EDGE_INFO (e)->back_edge = 1;
2116
2117 bbs = get_loop_body (loop);
2118 for (i = 0; i < loop->num_nodes; i++)
2119 bitmap_set_bit (tovisit, bbs[i]->index);
2120 free (bbs);
2121 propagate_freq (loop->header, tovisit);
2122 BITMAP_FREE (tovisit);
2123 }
2124 }
2125
2126 /* Propagates frequencies through structure of loops. */
2127
2128 static void
estimate_loops(void)2129 estimate_loops (void)
2130 {
2131 bitmap tovisit = BITMAP_ALLOC (NULL);
2132 basic_block bb;
2133
2134 /* Start by estimating the frequencies in the loops. */
2135 if (number_of_loops () > 1)
2136 estimate_loops_at_level (current_loops->tree_root->inner);
2137
2138 /* Now propagate the frequencies through all the blocks. */
2139 FOR_ALL_BB (bb)
2140 {
2141 bitmap_set_bit (tovisit, bb->index);
2142 }
2143 propagate_freq (ENTRY_BLOCK_PTR, tovisit);
2144 BITMAP_FREE (tovisit);
2145 }
2146
2147 /* Convert counts measured by profile driven feedback to frequencies.
2148 Return nonzero iff there was any nonzero execution count. */
2149
2150 int
counts_to_freqs(void)2151 counts_to_freqs (void)
2152 {
2153 gcov_type count_max, true_count_max = 0;
2154 basic_block bb;
2155
2156 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2157 true_count_max = MAX (bb->count, true_count_max);
2158
2159 count_max = MAX (true_count_max, 1);
2160 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2161 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
2162
2163 return true_count_max;
2164 }
2165
2166 /* Return true if function is likely to be expensive, so there is no point to
2167 optimize performance of prologue, epilogue or do inlining at the expense
2168 of code size growth. THRESHOLD is the limit of number of instructions
2169 function can execute at average to be still considered not expensive. */
2170
2171 bool
expensive_function_p(int threshold)2172 expensive_function_p (int threshold)
2173 {
2174 unsigned int sum = 0;
2175 basic_block bb;
2176 unsigned int limit;
2177
2178 /* We can not compute accurately for large thresholds due to scaled
2179 frequencies. */
2180 gcc_assert (threshold <= BB_FREQ_MAX);
2181
2182 /* Frequencies are out of range. This either means that function contains
2183 internal loop executing more than BB_FREQ_MAX times or profile feedback
2184 is available and function has not been executed at all. */
2185 if (ENTRY_BLOCK_PTR->frequency == 0)
2186 return true;
2187
2188 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2189 limit = ENTRY_BLOCK_PTR->frequency * threshold;
2190 FOR_EACH_BB (bb)
2191 {
2192 rtx insn;
2193
2194 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2195 insn = NEXT_INSN (insn))
2196 if (active_insn_p (insn))
2197 {
2198 sum += bb->frequency;
2199 if (sum > limit)
2200 return true;
2201 }
2202 }
2203
2204 return false;
2205 }
2206
2207 /* Estimate basic blocks frequency by given branch probabilities. */
2208
2209 void
estimate_bb_frequencies(void)2210 estimate_bb_frequencies (void)
2211 {
2212 basic_block bb;
2213 sreal freq_max;
2214
2215 if (profile_status != PROFILE_READ || !counts_to_freqs ())
2216 {
2217 static int real_values_initialized = 0;
2218
2219 if (!real_values_initialized)
2220 {
2221 real_values_initialized = 1;
2222 sreal_init (&real_zero, 0, 0);
2223 sreal_init (&real_one, 1, 0);
2224 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
2225 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
2226 sreal_init (&real_one_half, 1, -1);
2227 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
2228 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
2229 }
2230
2231 mark_dfs_back_edges ();
2232
2233 single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
2234
2235 /* Set up block info for each basic block. */
2236 alloc_aux_for_blocks (sizeof (struct block_info_def));
2237 alloc_aux_for_edges (sizeof (struct edge_info_def));
2238 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2239 {
2240 edge e;
2241 edge_iterator ei;
2242
2243 FOR_EACH_EDGE (e, ei, bb->succs)
2244 {
2245 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
2246 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2247 &EDGE_INFO (e)->back_edge_prob,
2248 &real_inv_br_prob_base);
2249 }
2250 }
2251
2252 /* First compute probabilities locally for each loop from innermost
2253 to outermost to examine probabilities for back edges. */
2254 estimate_loops ();
2255
2256 memcpy (&freq_max, &real_zero, sizeof (real_zero));
2257 FOR_EACH_BB (bb)
2258 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
2259 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
2260
2261 sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
2262 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2263 {
2264 sreal tmp;
2265
2266 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
2267 sreal_add (&tmp, &tmp, &real_one_half);
2268 bb->frequency = sreal_to_int (&tmp);
2269 }
2270
2271 free_aux_for_blocks ();
2272 free_aux_for_edges ();
2273 }
2274 compute_function_frequency ();
2275 }
2276
2277 /* Decide whether function is hot, cold or unlikely executed. */
2278 void
compute_function_frequency(void)2279 compute_function_frequency (void)
2280 {
2281 basic_block bb;
2282 struct cgraph_node *node = cgraph_get_node (current_function_decl);
2283 if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2284 || MAIN_NAME_P (DECL_NAME (current_function_decl)))
2285 node->only_called_at_startup = true;
2286 if (DECL_STATIC_DESTRUCTOR (current_function_decl))
2287 node->only_called_at_exit = true;
2288
2289 if (!profile_info || !flag_branch_probabilities)
2290 {
2291 int flags = flags_from_decl_or_type (current_function_decl);
2292 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
2293 != NULL)
2294 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2295 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
2296 != NULL)
2297 node->frequency = NODE_FREQUENCY_HOT;
2298 else if (flags & ECF_NORETURN)
2299 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2300 else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
2301 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2302 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2303 || DECL_STATIC_DESTRUCTOR (current_function_decl))
2304 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2305 return;
2306 }
2307 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2308 FOR_EACH_BB (bb)
2309 {
2310 if (maybe_hot_bb_p (bb))
2311 {
2312 node->frequency = NODE_FREQUENCY_HOT;
2313 return;
2314 }
2315 if (!probably_never_executed_bb_p (bb))
2316 node->frequency = NODE_FREQUENCY_NORMAL;
2317 }
2318 }
2319
2320 static bool
gate_estimate_probability(void)2321 gate_estimate_probability (void)
2322 {
2323 return flag_guess_branch_prob;
2324 }
2325
2326 /* Build PREDICT_EXPR. */
2327 tree
build_predict_expr(enum br_predictor predictor,enum prediction taken)2328 build_predict_expr (enum br_predictor predictor, enum prediction taken)
2329 {
2330 tree t = build1 (PREDICT_EXPR, void_type_node,
2331 build_int_cst (integer_type_node, predictor));
2332 SET_PREDICT_EXPR_OUTCOME (t, taken);
2333 return t;
2334 }
2335
2336 const char *
predictor_name(enum br_predictor predictor)2337 predictor_name (enum br_predictor predictor)
2338 {
2339 return predictor_info[predictor].name;
2340 }
2341
2342 struct gimple_opt_pass pass_profile =
2343 {
2344 {
2345 GIMPLE_PASS,
2346 "profile_estimate", /* name */
2347 gate_estimate_probability, /* gate */
2348 tree_estimate_probability_driver, /* execute */
2349 NULL, /* sub */
2350 NULL, /* next */
2351 0, /* static_pass_number */
2352 TV_BRANCH_PROB, /* tv_id */
2353 PROP_cfg, /* properties_required */
2354 0, /* properties_provided */
2355 0, /* properties_destroyed */
2356 0, /* todo_flags_start */
2357 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2358 }
2359 };
2360
2361 struct gimple_opt_pass pass_strip_predict_hints =
2362 {
2363 {
2364 GIMPLE_PASS,
2365 "*strip_predict_hints", /* name */
2366 NULL, /* gate */
2367 strip_predict_hints, /* execute */
2368 NULL, /* sub */
2369 NULL, /* next */
2370 0, /* static_pass_number */
2371 TV_BRANCH_PROB, /* tv_id */
2372 PROP_cfg, /* properties_required */
2373 0, /* properties_provided */
2374 0, /* properties_destroyed */
2375 0, /* todo_flags_start */
2376 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2377 }
2378 };
2379
2380 /* Rebuild function frequencies. Passes are in general expected to
2381 maintain profile by hand, however in some cases this is not possible:
2382 for example when inlining several functions with loops freuqencies might run
2383 out of scale and thus needs to be recomputed. */
2384
2385 void
rebuild_frequencies(void)2386 rebuild_frequencies (void)
2387 {
2388 timevar_push (TV_REBUILD_FREQUENCIES);
2389 if (profile_status == PROFILE_GUESSED)
2390 {
2391 loop_optimizer_init (0);
2392 add_noreturn_fake_exit_edges ();
2393 mark_irreducible_loops ();
2394 connect_infinite_loops_to_exit ();
2395 estimate_bb_frequencies ();
2396 remove_fake_exit_edges ();
2397 loop_optimizer_finalize ();
2398 }
2399 else if (profile_status == PROFILE_READ)
2400 counts_to_freqs ();
2401 else
2402 gcc_unreachable ();
2403 timevar_pop (TV_REBUILD_FREQUENCIES);
2404 }
2405