Bug Summary

File:build/gcc/predict.c
Warning:line 800, column 36
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name predict.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model static -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib64/clang/11.0.0 -D IN_GCC -D HAVE_CONFIG_H -I . -I . -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/. -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcpp/include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcody -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber/bid -I ../libdecnumber -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libbacktrace -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10 -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10/x86_64-suse-linux -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib64/clang/11.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-narrowing -Wwrite-strings -Wno-error=format-diag -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -fdeprecated-macro -fdebug-compilation-dir /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -ferror-limit 19 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=plist-html -analyzer-config silence-checkers=core.NullDereference -faddrsig -o /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/clang-static-analyzer/2021-01-16-135054-17580-1/report-Matnur.plist -x c++ /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/predict.c

/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/predict.c

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

/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/basic-block.h

1/* Define control flow data structures for the CFG.
2 Copyright (C) 1987-2021 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20#ifndef GCC_BASIC_BLOCK_H
21#define GCC_BASIC_BLOCK_H
22
23#include <profile-count.h>
24
25/* Control flow edge information. */
26class GTY((user)) edge_def {
27public:
28 /* The two blocks at the ends of the edge. */
29 basic_block src;
30 basic_block dest;
31
32 /* Instructions queued on the edge. */
33 union edge_def_insns {
34 gimple_seq g;
35 rtx_insn *r;
36 } insns;
37
38 /* Auxiliary info specific to a pass. */
39 PTRvoid * aux;
40
41 /* Location of any goto implicit in the edge. */
42 location_t goto_locus;
43
44 /* The index number corresponding to this edge in the edge vector
45 dest->preds. */
46 unsigned int dest_idx;
47
48 int flags; /* see cfg-flags.def */
49 profile_probability probability;
50
51 /* Return count of edge E. */
52 inline profile_count count () const;
53};
54
55/* Masks for edge.flags. */
56#define DEF_EDGE_FLAG(NAME,IDX) EDGE_##NAME = 1 << IDX ,
57enum cfg_edge_flags {
58#include "cfg-flags.def"
59 LAST_CFG_EDGE_FLAG /* this is only used for EDGE_ALL_FLAGS */
60};
61#undef DEF_EDGE_FLAG
62
63/* Bit mask for all edge flags. */
64#define EDGE_ALL_FLAGS((LAST_CFG_EDGE_FLAG - 1) * 2 - 1) ((LAST_CFG_EDGE_FLAG - 1) * 2 - 1)
65
66/* The following four flags all indicate something special about an edge.
67 Test the edge flags on EDGE_COMPLEX to detect all forms of "strange"
68 control flow transfers. */
69#define EDGE_COMPLEX(EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_PRESERVE
)
\
70 (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_PRESERVE)
71
72struct GTY(()) rtl_bb_info {
73 /* The first insn of the block is embedded into bb->il.x. */
74 /* The last insn of the block. */
75 rtx_insn *end_;
76
77 /* In CFGlayout mode points to insn notes/jumptables to be placed just before
78 and after the block. */
79 rtx_insn *header_;
80 rtx_insn *footer_;
81};
82
83struct GTY(()) gimple_bb_info {
84 /* Sequence of statements in this block. */
85 gimple_seq seq;
86
87 /* PHI nodes for this block. */
88 gimple_seq phi_nodes;
89};
90
91/* A basic block is a sequence of instructions with only one entry and
92 only one exit. If any one of the instructions are executed, they
93 will all be executed, and in sequence from first to last.
94
95 There may be COND_EXEC instructions in the basic block. The
96 COND_EXEC *instructions* will be executed -- but if the condition
97 is false the conditionally executed *expressions* will of course
98 not be executed. We don't consider the conditionally executed
99 expression (which might have side-effects) to be in a separate
100 basic block because the program counter will always be at the same
101 location after the COND_EXEC instruction, regardless of whether the
102 condition is true or not.
103
104 Basic blocks need not start with a label nor end with a jump insn.
105 For example, a previous basic block may just "conditionally fall"
106 into the succeeding basic block, and the last basic block need not
107 end with a jump insn. Block 0 is a descendant of the entry block.
108
109 A basic block beginning with two labels cannot have notes between
110 the labels.
111
112 Data for jump tables are stored in jump_insns that occur in no
113 basic block even though these insns can follow or precede insns in
114 basic blocks. */
115
116/* Basic block information indexed by block number. */
117struct GTY((chain_next ("%h.next_bb"), chain_prev ("%h.prev_bb"))) basic_block_def {
118 /* The edges into and out of the block. */
119 vec<edge, va_gc> *preds;
120 vec<edge, va_gc> *succs;
121
122 /* Auxiliary info specific to a pass. */
123 PTRvoid * GTY ((skip (""))) aux;
124
125 /* Innermost loop containing the block. */
126 class loop *loop_father;
127
128 /* The dominance and postdominance information node. */
129 struct et_node * GTY ((skip (""))) dom[2];
130
131 /* Previous and next blocks in the chain. */
132 basic_block prev_bb;
133 basic_block next_bb;
134
135 union basic_block_il_dependent {
136 struct gimple_bb_info GTY ((tag ("0"))) gimple;
137 struct {
138 rtx_insn *head_;
139 struct rtl_bb_info * rtl;
140 } GTY ((tag ("1"))) x;
141 } GTY ((desc ("((%1.flags & BB_RTL) != 0)"))) il;
142
143 /* Various flags. See cfg-flags.def. */
144 int flags;
145
146 /* The index of this block. */
147 int index;
148
149 /* Expected number of executions: calculated in profile.c. */
150 profile_count count;
151
152 /* The discriminator for this block. The discriminator distinguishes
153 among several basic blocks that share a common locus, allowing for
154 more accurate sample-based profiling. */
155 int discriminator;
156};
157
158/* This ensures that struct gimple_bb_info is smaller than
159 struct rtl_bb_info, so that inlining the former into basic_block_def
160 is the better choice. */
161typedef int __assert_gimple_bb_smaller_rtl_bb
162 [(int) sizeof (struct rtl_bb_info)
163 - (int) sizeof (struct gimple_bb_info)];
164
165
166#define BB_FREQ_MAX10000 10000
167
168/* Masks for basic_block.flags. */
169#define DEF_BASIC_BLOCK_FLAG(NAME,IDX) BB_##NAME = 1 << IDX ,
170enum cfg_bb_flags
171{
172#include "cfg-flags.def"
173 LAST_CFG_BB_FLAG /* this is only used for BB_ALL_FLAGS */
174};
175#undef DEF_BASIC_BLOCK_FLAG
176
177/* Bit mask for all basic block flags. */
178#define BB_ALL_FLAGS((LAST_CFG_BB_FLAG - 1) * 2 - 1) ((LAST_CFG_BB_FLAG - 1) * 2 - 1)
179
180/* Bit mask for all basic block flags that must be preserved. These are
181 the bit masks that are *not* cleared by clear_bb_flags. */
182#define BB_FLAGS_TO_PRESERVE(BB_DISABLE_SCHEDULE | BB_RTL | BB_NON_LOCAL_GOTO_TARGET | BB_HOT_PARTITION
| BB_COLD_PARTITION)
\
183 (BB_DISABLE_SCHEDULE | BB_RTL | BB_NON_LOCAL_GOTO_TARGET \
184 | BB_HOT_PARTITION | BB_COLD_PARTITION)
185
186/* Dummy bitmask for convenience in the hot/cold partitioning code. */
187#define BB_UNPARTITIONED0 0
188
189/* Partitions, to be used when partitioning hot and cold basic blocks into
190 separate sections. */
191#define BB_PARTITION(bb)((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION)) ((bb)->flags & (BB_HOT_PARTITION|BB_COLD_PARTITION))
192#define BB_SET_PARTITION(bb, part)do { basic_block bb_ = (bb); bb_->flags = ((bb_->flags &
~(BB_HOT_PARTITION|BB_COLD_PARTITION)) | (part)); } while (0
)
do { \
193 basic_block bb_ = (bb); \
194 bb_->flags = ((bb_->flags & ~(BB_HOT_PARTITION|BB_COLD_PARTITION)) \
195 | (part)); \
196} while (0)
197
198#define BB_COPY_PARTITION(dstbb, srcbb)do { basic_block bb_ = (dstbb); bb_->flags = ((bb_->flags
& ~(BB_HOT_PARTITION|BB_COLD_PARTITION)) | (((srcbb)->
flags & (BB_HOT_PARTITION|BB_COLD_PARTITION)))); } while (
0)
\
199 BB_SET_PARTITION (dstbb, BB_PARTITION (srcbb))do { basic_block bb_ = (dstbb); bb_->flags = ((bb_->flags
& ~(BB_HOT_PARTITION|BB_COLD_PARTITION)) | (((srcbb)->
flags & (BB_HOT_PARTITION|BB_COLD_PARTITION)))); } while (
0)
200
201/* Defines for accessing the fields of the CFG structure for function FN. */
202#define ENTRY_BLOCK_PTR_FOR_FN(FN)((FN)->cfg->x_entry_block_ptr) ((FN)->cfg->x_entry_block_ptr)
203#define EXIT_BLOCK_PTR_FOR_FN(FN)((FN)->cfg->x_exit_block_ptr) ((FN)->cfg->x_exit_block_ptr)
204#define basic_block_info_for_fn(FN)((FN)->cfg->x_basic_block_info) ((FN)->cfg->x_basic_block_info)
205#define n_basic_blocks_for_fn(FN)((FN)->cfg->x_n_basic_blocks) ((FN)->cfg->x_n_basic_blocks)
206#define n_edges_for_fn(FN)((FN)->cfg->x_n_edges) ((FN)->cfg->x_n_edges)
207#define last_basic_block_for_fn(FN)((FN)->cfg->x_last_basic_block) ((FN)->cfg->x_last_basic_block)
208#define label_to_block_map_for_fn(FN)((FN)->cfg->x_label_to_block_map) ((FN)->cfg->x_label_to_block_map)
209#define profile_status_for_fn(FN)((FN)->cfg->x_profile_status) ((FN)->cfg->x_profile_status)
210
211#define BASIC_BLOCK_FOR_FN(FN,N)((*((FN)->cfg->x_basic_block_info))[(N)]) \
212 ((*basic_block_info_for_fn (FN)((FN)->cfg->x_basic_block_info))[(N)])
213#define SET_BASIC_BLOCK_FOR_FN(FN,N,BB)((*((FN)->cfg->x_basic_block_info))[(N)] = (BB)) \
214 ((*basic_block_info_for_fn (FN)((FN)->cfg->x_basic_block_info))[(N)] = (BB))
215
216/* For iterating over basic blocks. */
217#define FOR_BB_BETWEEN(BB, FROM, TO, DIR)for (BB = FROM; BB != TO; BB = BB->DIR) \
218 for (BB = FROM; BB != TO; BB = BB->DIR)
219
220#define FOR_EACH_BB_FN(BB, FN)for (BB = (FN)->cfg->x_entry_block_ptr->next_bb; BB !=
(FN)->cfg->x_exit_block_ptr; BB = BB->next_bb)
\
221 FOR_BB_BETWEEN (BB, (FN)->cfg->x_entry_block_ptr->next_bb, (FN)->cfg->x_exit_block_ptr, next_bb)for (BB = (FN)->cfg->x_entry_block_ptr->next_bb; BB !=
(FN)->cfg->x_exit_block_ptr; BB = BB->next_bb)
222
223#define FOR_EACH_BB_REVERSE_FN(BB, FN)for (BB = (FN)->cfg->x_exit_block_ptr->prev_bb; BB !=
(FN)->cfg->x_entry_block_ptr; BB = BB->prev_bb)
\
224 FOR_BB_BETWEEN (BB, (FN)->cfg->x_exit_block_ptr->prev_bb, (FN)->cfg->x_entry_block_ptr, prev_bb)for (BB = (FN)->cfg->x_exit_block_ptr->prev_bb; BB !=
(FN)->cfg->x_entry_block_ptr; BB = BB->prev_bb)
225
226/* For iterating over insns in basic block. */
227#define FOR_BB_INSNS(BB, INSN)for ((INSN) = (BB)->il.x.head_; (INSN) && (INSN) !=
NEXT_INSN ((BB)->il.x.rtl->end_); (INSN) = NEXT_INSN (
INSN))
\
228 for ((INSN) = BB_HEAD (BB)(BB)->il.x.head_; \
229 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)(BB)->il.x.rtl->end_); \
230 (INSN) = NEXT_INSN (INSN))
231
232/* For iterating over insns in basic block when we might remove the
233 current insn. */
234#define FOR_BB_INSNS_SAFE(BB, INSN, CURR)for ((INSN) = (BB)->il.x.head_, (CURR) = (INSN) ? NEXT_INSN
((INSN)): nullptr; (INSN) && (INSN) != NEXT_INSN ((BB
)->il.x.rtl->end_); (INSN) = (CURR), (CURR) = (INSN) ? NEXT_INSN
((INSN)) : nullptr)
\
235 for ((INSN) = BB_HEAD (BB)(BB)->il.x.head_, (CURR) = (INSN) ? NEXT_INSN ((INSN)): NULLnullptr; \
236 (INSN) && (INSN) != NEXT_INSN (BB_END (BB)(BB)->il.x.rtl->end_); \
237 (INSN) = (CURR), (CURR) = (INSN) ? NEXT_INSN ((INSN)) : NULLnullptr)
238
239#define FOR_BB_INSNS_REVERSE(BB, INSN)for ((INSN) = (BB)->il.x.rtl->end_; (INSN) && (
INSN) != PREV_INSN ((BB)->il.x.head_); (INSN) = PREV_INSN (
INSN))
\
240 for ((INSN) = BB_END (BB)(BB)->il.x.rtl->end_; \
241 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)(BB)->il.x.head_); \
242 (INSN) = PREV_INSN (INSN))
243
244#define FOR_BB_INSNS_REVERSE_SAFE(BB, INSN, CURR)for ((INSN) = (BB)->il.x.rtl->end_,(CURR) = (INSN) ? PREV_INSN
((INSN)) : nullptr; (INSN) && (INSN) != PREV_INSN ((
BB)->il.x.head_); (INSN) = (CURR), (CURR) = (INSN) ? PREV_INSN
((INSN)) : nullptr)
\
245 for ((INSN) = BB_END (BB)(BB)->il.x.rtl->end_,(CURR) = (INSN) ? PREV_INSN ((INSN)) : NULLnullptr; \
246 (INSN) && (INSN) != PREV_INSN (BB_HEAD (BB)(BB)->il.x.head_); \
247 (INSN) = (CURR), (CURR) = (INSN) ? PREV_INSN ((INSN)) : NULLnullptr)
248
249/* Cycles through _all_ basic blocks, even the fake ones (entry and
250 exit block). */
251
252#define FOR_ALL_BB_FN(BB, FN)for (BB = ((FN)->cfg->x_entry_block_ptr); BB; BB = BB->
next_bb)
\
253 for (BB = ENTRY_BLOCK_PTR_FOR_FN (FN)((FN)->cfg->x_entry_block_ptr); BB; BB = BB->next_bb)
254
255
256/* Stuff for recording basic block info. */
257
258/* For now, these will be functions (so that they can include checked casts
259 to rtx_insn. Once the underlying fields are converted from rtx
260 to rtx_insn, these can be converted back to macros. */
261
262#define BB_HEAD(B)(B)->il.x.head_ (B)->il.x.head_
263#define BB_END(B)(B)->il.x.rtl->end_ (B)->il.x.rtl->end_
264#define BB_HEADER(B)(B)->il.x.rtl->header_ (B)->il.x.rtl->header_
265#define BB_FOOTER(B)(B)->il.x.rtl->footer_ (B)->il.x.rtl->footer_
266
267/* Special block numbers [markers] for entry and exit.
268 Neither of them is supposed to hold actual statements. */
269#define ENTRY_BLOCK(0) (0)
270#define EXIT_BLOCK(1) (1)
271
272/* The two blocks that are always in the cfg. */
273#define NUM_FIXED_BLOCKS(2) (2)
274
275/* This is the value which indicates no edge is present. */
276#define EDGE_INDEX_NO_EDGE-1 -1
277
278/* EDGE_INDEX returns an integer index for an edge, or EDGE_INDEX_NO_EDGE
279 if there is no edge between the 2 basic blocks. */
280#define EDGE_INDEX(el, pred, succ)(find_edge_index ((el), (pred), (succ))) (find_edge_index ((el), (pred), (succ)))
281
282/* INDEX_EDGE_PRED_BB and INDEX_EDGE_SUCC_BB return a pointer to the basic
283 block which is either the pred or succ end of the indexed edge. */
284#define INDEX_EDGE_PRED_BB(el, index)((el)->index_to_edge[(index)]->src) ((el)->index_to_edge[(index)]->src)
285#define INDEX_EDGE_SUCC_BB(el, index)((el)->index_to_edge[(index)]->dest) ((el)->index_to_edge[(index)]->dest)
286
287/* INDEX_EDGE returns a pointer to the edge. */
288#define INDEX_EDGE(el, index)((el)->index_to_edge[(index)]) ((el)->index_to_edge[(index)])
289
290/* Number of edges in the compressed edge list. */
291#define NUM_EDGES(el)((el)->num_edges) ((el)->num_edges)
292
293/* BB is assumed to contain conditional jump. Return the fallthru edge. */
294#define FALLTHRU_EDGE(bb)((*((bb))->succs)[(0)]->flags & EDGE_FALLTHRU ? (*(
(bb))->succs)[(0)] : (*((bb))->succs)[(1)])
(EDGE_SUCC ((bb), 0)(*((bb))->succs)[(0)]->flags & EDGE_FALLTHRU \
295 ? EDGE_SUCC ((bb), 0)(*((bb))->succs)[(0)] : EDGE_SUCC ((bb), 1)(*((bb))->succs)[(1)])
296
297/* BB is assumed to contain conditional jump. Return the branch edge. */
298#define BRANCH_EDGE(bb)((*((bb))->succs)[(0)]->flags & EDGE_FALLTHRU ? (*(
(bb))->succs)[(1)] : (*((bb))->succs)[(0)])
(EDGE_SUCC ((bb), 0)(*((bb))->succs)[(0)]->flags & EDGE_FALLTHRU \
299 ? EDGE_SUCC ((bb), 1)(*((bb))->succs)[(1)] : EDGE_SUCC ((bb), 0)(*((bb))->succs)[(0)])
300
301/* Return expected execution frequency of the edge E. */
302#define EDGE_FREQUENCY(e)e->count ().to_frequency ((cfun + 0)) e->count ().to_frequency (cfun(cfun + 0))
303
304/* Compute a scale factor (or probability) suitable for scaling of
305 gcov_type values via apply_probability() and apply_scale(). */
306#define GCOV_COMPUTE_SCALE(num,den)((den) ? ((((num) * 10000) + ((den)) / 2) / ((den))) : 10000) \
307 ((den) ? RDIV ((num) * REG_BR_PROB_BASE, (den))((((num) * 10000) + ((den)) / 2) / ((den))) : REG_BR_PROB_BASE10000)
308
309/* Return nonzero if edge is critical. */
310#define EDGE_CRITICAL_P(e)(vec_safe_length ((e)->src->succs) >= 2 && vec_safe_length
((e)->dest->preds) >= 2)
(EDGE_COUNT ((e)->src->succs)vec_safe_length ((e)->src->succs) >= 2 \
311 && EDGE_COUNT ((e)->dest->preds)vec_safe_length ((e)->dest->preds) >= 2)
312
313#define EDGE_COUNT(ev)vec_safe_length (ev) vec_safe_length (ev)
314#define EDGE_I(ev,i)(*ev)[(i)] (*ev)[(i)]
315#define EDGE_PRED(bb,i)(*(bb)->preds)[(i)] (*(bb)->preds)[(i)]
316#define EDGE_SUCC(bb,i)(*(bb)->succs)[(i)] (*(bb)->succs)[(i)]
317
318/* Returns true if BB has precisely one successor. */
319
320static inline bool
321single_succ_p (const_basic_block bb)
322{
323 return EDGE_COUNT (bb->succs)vec_safe_length (bb->succs) == 1;
324}
325
326/* Returns true if BB has precisely one predecessor. */
327
328static inline bool
329single_pred_p (const_basic_block bb)
330{
331 return EDGE_COUNT (bb->preds)vec_safe_length (bb->preds) == 1;
332}
333
334/* Returns the single successor edge of basic block BB. Aborts if
335 BB does not have exactly one successor. */
336
337static inline edge
338single_succ_edge (const_basic_block bb)
339{
340 gcc_checking_assert (single_succ_p (bb))((void)(!(single_succ_p (bb)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/basic-block.h"
, 340, __FUNCTION__), 0 : 0))
;
341 return EDGE_SUCC (bb, 0)(*(bb)->succs)[(0)];
342}
343
344/* Returns the single predecessor edge of basic block BB. Aborts
345 if BB does not have exactly one predecessor. */
346
347static inline edge
348single_pred_edge (const_basic_block bb)
349{
350 gcc_checking_assert (single_pred_p (bb))((void)(!(single_pred_p (bb)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/basic-block.h"
, 350, __FUNCTION__), 0 : 0))
;
351 return EDGE_PRED (bb, 0)(*(bb)->preds)[(0)];
352}
353
354/* Returns the single successor block of basic block BB. Aborts
355 if BB does not have exactly one successor. */
356
357static inline basic_block
358single_succ (const_basic_block bb)
359{
360 return single_succ_edge (bb)->dest;
361}
362
363/* Returns the single predecessor block of basic block BB. Aborts
364 if BB does not have exactly one predecessor.*/
365
366static inline basic_block
367single_pred (const_basic_block bb)
368{
369 return single_pred_edge (bb)->src;
370}
371
372/* Iterator object for edges. */
373
374struct edge_iterator {
375 unsigned index;
376 vec<edge, va_gc> **container;
377};
378
379static inline vec<edge, va_gc> *
380ei_container (edge_iterator i)
381{
382 gcc_checking_assert (i.container)((void)(!(i.container) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/basic-block.h"
, 382, __FUNCTION__), 0 : 0))
;
383 return *i.container;
384}
385
386#define ei_start(iter)ei_start_1 (&(iter)) ei_start_1 (&(iter))
387#define ei_last(iter)ei_last_1 (&(iter)) ei_last_1 (&(iter))
388
389/* Return an iterator pointing to the start of an edge vector. */
390static inline edge_iterator
391ei_start_1 (vec<edge, va_gc> **ev)
392{
393 edge_iterator i;
394
395 i.index = 0;
396 i.container = ev;
397
398 return i;
399}
400
401/* Return an iterator pointing to the last element of an edge
402 vector. */
403static inline edge_iterator
404ei_last_1 (vec<edge, va_gc> **ev)
405{
406 edge_iterator i;
407
408 i.index = EDGE_COUNT (*ev)vec_safe_length (*ev) - 1;
409 i.container = ev;
410
411 return i;
412}
413
414/* Is the iterator `i' at the end of the sequence? */
415static inline bool
416ei_end_p (edge_iterator i)
417{
418 return (i.index == EDGE_COUNT (ei_container (i))vec_safe_length (ei_container (i)));
18
Returning the value 1, which participates in a condition later
419}
420
421/* Is the iterator `i' at one position before the end of the
422 sequence? */
423static inline bool
424ei_one_before_end_p (edge_iterator i)
425{
426 return (i.index + 1 == EDGE_COUNT (ei_container (i))vec_safe_length (ei_container (i)));
427}
428
429/* Advance the iterator to the next element. */
430static inline void
431ei_next (edge_iterator *i)
432{
433 gcc_checking_assert (i->index < EDGE_COUNT (ei_container (*i)))((void)(!(i->index < vec_safe_length (ei_container (*i)
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/basic-block.h"
, 433, __FUNCTION__), 0 : 0))
;
434 i->index++;
435}
436
437/* Move the iterator to the previous element. */
438static inline void
439ei_prev (edge_iterator *i)
440{
441 gcc_checking_assert (i->index > 0)((void)(!(i->index > 0) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/basic-block.h"
, 441, __FUNCTION__), 0 : 0))
;
442 i->index--;
443}
444
445/* Return the edge pointed to by the iterator `i'. */
446static inline edge
447ei_edge (edge_iterator i)
448{
449 return EDGE_I (ei_container (i), i.index)(*ei_container (i))[(i.index)];
450}
451
452/* Return an edge pointed to by the iterator. Do it safely so that
453 NULL is returned when the iterator is pointing at the end of the
454 sequence. */
455static inline edge
456ei_safe_edge (edge_iterator i)
457{
458 return !ei_end_p (i) ? ei_edge (i) : NULLnullptr;
459}
460
461/* Return 1 if we should continue to iterate. Return 0 otherwise.
462 *Edge P is set to the next edge if we are to continue to iterate
463 and NULL otherwise. */
464
465static inline bool
466ei_cond (edge_iterator ei, edge *p)
467{
468 if (!ei_end_p (ei))
17
Calling 'ei_end_p'
19
Returning from 'ei_end_p'
20
Taking false branch
469 {
470 *p = ei_edge (ei);
471 return 1;
472 }
473 else
474 {
475 *p = NULLnullptr;
21
Null pointer value stored to 'e'
476 return 0;
477 }
478}
479
480/* This macro serves as a convenient way to iterate each edge in a
481 vector of predecessor or successor edges. It must not be used when
482 an element might be removed during the traversal, otherwise
483 elements will be missed. Instead, use a for-loop like that shown
484 in the following pseudo-code:
485
486 FOR (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
487 {
488 IF (e != taken_edge)
489 remove_edge (e);
490 ELSE
491 ei_next (&ei);
492 }
493*/
494
495#define FOR_EACH_EDGE(EDGE,ITER,EDGE_VEC)for ((ITER) = ei_start_1 (&((EDGE_VEC))); ei_cond ((ITER)
, &(EDGE)); ei_next (&(ITER)))
\
496 for ((ITER) = ei_start ((EDGE_VEC))ei_start_1 (&((EDGE_VEC))); \
497 ei_cond ((ITER), &(EDGE)); \
498 ei_next (&(ITER)))
499
500#define CLEANUP_EXPENSIVE1 1 /* Do relatively expensive optimizations
501 except for edge forwarding */
502#define CLEANUP_CROSSJUMP2 2 /* Do crossjumping. */
503#define CLEANUP_POST_REGSTACK4 4 /* We run after reg-stack and need
504 to care REG_DEAD notes. */
505#define CLEANUP_THREADING8 8 /* Do jump threading. */
506#define CLEANUP_NO_INSN_DEL16 16 /* Do not try to delete trivially dead
507 insns. */
508#define CLEANUP_CFGLAYOUT32 32 /* Do cleanup in cfglayout mode. */
509#define CLEANUP_CFG_CHANGED64 64 /* The caller changed the CFG. */
510#define CLEANUP_NO_PARTITIONING128 128 /* Do not try to fix partitions. */
511#define CLEANUP_FORCE_FAST_DCE0x100 0x100 /* Force run_fast_dce to be called
512 at least once. */
513
514/* Return true if BB is in a transaction. */
515
516static inline bool
517bb_in_transaction (basic_block bb)
518{
519 return bb->flags & BB_IN_TRANSACTION;
520}
521
522/* Return true when one of the predecessor edges of BB is marked with EDGE_EH. */
523static inline bool
524bb_has_eh_pred (basic_block bb)
525{
526 edge e;
527 edge_iterator ei;
528
529 FOR_EACH_EDGE (e, ei, bb->preds)for ((ei) = ei_start_1 (&((bb->preds))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
530 {
531 if (e->flags & EDGE_EH)
532 return true;
533 }
534 return false;
535}
536
537/* Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL. */
538static inline bool
539bb_has_abnormal_pred (basic_block bb)
540{
541 edge e;
542 edge_iterator ei;
543
544 FOR_EACH_EDGE (e, ei, bb->preds)for ((ei) = ei_start_1 (&((bb->preds))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
545 {
546 if (e->flags & EDGE_ABNORMAL)
547 return true;
548 }
549 return false;
550}
551
552/* Return the fallthru edge in EDGES if it exists, NULL otherwise. */
553static inline edge
554find_fallthru_edge (vec<edge, va_gc> *edges)
555{
556 edge e;
557 edge_iterator ei;
558
559 FOR_EACH_EDGE (e, ei, edges)for ((ei) = ei_start_1 (&((edges))); ei_cond ((ei), &
(e)); ei_next (&(ei)))
560 if (e->flags & EDGE_FALLTHRU)
561 break;
562
563 return e;
564}
565
566/* Check tha probability is sane. */
567
568static inline void
569check_probability (int prob)
570{
571 gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE)((void)(!(prob >= 0 && prob <= 10000) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/basic-block.h"
, 571, __FUNCTION__), 0 : 0))
;
572}
573
574/* Given PROB1 and PROB2, return PROB1*PROB2/REG_BR_PROB_BASE.
575 Used to combine BB probabilities. */
576
577static inline int
578combine_probabilities (int prob1, int prob2)
579{
580 check_probability (prob1);
581 check_probability (prob2);
582 return RDIV (prob1 * prob2, REG_BR_PROB_BASE)(((prob1 * prob2) + (10000) / 2) / (10000));
583}
584
585/* Apply scale factor SCALE on frequency or count FREQ. Use this
586 interface when potentially scaling up, so that SCALE is not
587 constrained to be < REG_BR_PROB_BASE. */
588
589static inline gcov_type
590apply_scale (gcov_type freq, gcov_type scale)
591{
592 return RDIV (freq * scale, REG_BR_PROB_BASE)(((freq * scale) + (10000) / 2) / (10000));
593}
594
595/* Apply probability PROB on frequency or count FREQ. */
596
597static inline gcov_type
598apply_probability (gcov_type freq, int prob)
599{
600 check_probability (prob);
601 return apply_scale (freq, prob);
602}
603
604/* Return inverse probability for PROB. */
605
606static inline int
607inverse_probability (int prob1)
608{
609 check_probability (prob1);
610 return REG_BR_PROB_BASE10000 - prob1;
611}
612
613/* Return true if BB has at least one abnormal outgoing edge. */
614
615static inline bool
616has_abnormal_or_eh_outgoing_edge_p (basic_block bb)
617{
618 edge e;
619 edge_iterator ei;
620
621 FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
622 if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
623 return true;
624
625 return false;
626}
627
628/* Return true when one of the predecessor edges of BB is marked with
629 EDGE_ABNORMAL_CALL or EDGE_EH. */
630
631static inline bool
632has_abnormal_call_or_eh_pred_edge_p (basic_block bb)
633{
634 edge e;
635 edge_iterator ei;
636
637 FOR_EACH_EDGE (e, ei, bb->preds)for ((ei) = ei_start_1 (&((bb->preds))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
638 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
639 return true;
640
641 return false;
642}
643
644/* Return count of edge E. */
645inline profile_count edge_def::count () const
646{
647 return src->count.apply_probability (probability);
648}
649
650#endif /* GCC_BASIC_BLOCK_H */

/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h

1/* Profile counter container type.
2 Copyright (C) 2017-2021 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21#ifndef GCC_PROFILE_COUNT_H
22#define GCC_PROFILE_COUNT_H
23
24struct function;
25struct profile_count;
26class sreal;
27
28/* Quality of the profile count. Because gengtype does not support enums
29 inside of classes, this is in global namespace. */
30enum profile_quality {
31 /* Uninitialized value. */
32 UNINITIALIZED_PROFILE,
33
34 /* Profile is based on static branch prediction heuristics and may
35 or may not match reality. It is local to function and cannot be compared
36 inter-procedurally. Never used by probabilities (they are always local).
37 */
38 GUESSED_LOCAL,
39
40 /* Profile was read by feedback and was 0, we used local heuristics to guess
41 better. This is the case of functions not run in profile feedback.
42 Never used by probabilities. */
43 GUESSED_GLOBAL0,
44
45 /* Same as GUESSED_GLOBAL0 but global count is adjusted 0. */
46 GUESSED_GLOBAL0_ADJUSTED,
47
48 /* Profile is based on static branch prediction heuristics. It may or may
49 not reflect the reality but it can be compared interprocedurally
50 (for example, we inlined function w/o profile feedback into function
51 with feedback and propagated from that).
52 Never used by probabilities. */
53 GUESSED,
54
55 /* Profile was determined by autofdo. */
56 AFDO,
57
58 /* Profile was originally based on feedback but it was adjusted
59 by code duplicating optimization. It may not precisely reflect the
60 particular code path. */
61 ADJUSTED,
62
63 /* Profile was read from profile feedback or determined by accurate static
64 method. */
65 PRECISE
66};
67
68extern const char *profile_quality_as_string (enum profile_quality);
69extern bool parse_profile_quality (const char *value,
70 profile_quality *quality);
71
72/* The base value for branch probability notes and edge probabilities. */
73#define REG_BR_PROB_BASE10000 10000
74
75#define RDIV(X,Y)(((X) + (Y) / 2) / (Y)) (((X) + (Y) / 2) / (Y))
76
77bool slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res);
78
79/* Compute RES=(a*b + c/2)/c capping and return false if overflow happened. */
80
81inline bool
82safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
83{
84#if (GCC_VERSION(4 * 1000 + 2) >= 5000)
85 uint64_t tmp;
86 if (!__builtin_mul_overflow (a, b, &tmp)
87 && !__builtin_add_overflow (tmp, c/2, &tmp))
88 {
89 *res = tmp / c;
90 return true;
91 }
92 if (c == 1)
93 {
94 *res = (uint64_t) -1;
95 return false;
96 }
97#else
98 if (a < ((uint64_t)1 << 31)
99 && b < ((uint64_t)1 << 31)
100 && c < ((uint64_t)1 << 31))
101 {
102 *res = (a * b + (c / 2)) / c;
103 return true;
104 }
105#endif
106 return slow_safe_scale_64bit (a, b, c, res);
107}
108
109/* Data type to hold probabilities. It implements fixed point arithmetics
110 with capping so probability is always in range [0,1] and scaling requiring
111 values greater than 1 needs to be represented otherwise.
112
113 In addition to actual value the quality of profile is tracked and propagated
114 through all operations. Special value UNINITIALIZED_PROFILE is used for probabilities
115 that has not been determined yet (for example because of
116 -fno-guess-branch-probability)
117
118 Typically probabilities are derived from profile feedback (via
119 probability_in_gcov_type), autoFDO or guessed statically and then propagated
120 thorough the compilation.
121
122 Named probabilities are available:
123 - never (0 probability)
124 - guessed_never
125 - very_unlikely (1/2000 probability)
126 - unlikely (1/5 probability)
127 - even (1/2 probability)
128 - likely (4/5 probability)
129 - very_likely (1999/2000 probability)
130 - guessed_always
131 - always
132
133 Named probabilities except for never/always are assumed to be statically
134 guessed and thus not necessarily accurate. The difference between never
135 and guessed_never is that the first one should be used only in case that
136 well behaving program will very likely not execute the "never" path.
137 For example if the path is going to abort () call or it exception handling.
138
139 Always and guessed_always probabilities are symmetric.
140
141 For legacy code we support conversion to/from REG_BR_PROB_BASE based fixpoint
142 integer arithmetics. Once the code is converted to branch probabilities,
143 these conversions will probably go away because they are lossy.
144*/
145
146class GTY((user)) profile_probability
147{
148 static const int n_bits = 29;
149 /* We can technically use ((uint32_t) 1 << (n_bits - 1)) - 2 but that
150 will lead to harder multiplication sequences. */
151 static const uint32_t max_probability = (uint32_t) 1 << (n_bits - 2);
152 static const uint32_t uninitialized_probability
153 = ((uint32_t) 1 << (n_bits - 1)) - 1;
154
155 uint32_t m_val : 29;
156 enum profile_quality m_quality : 3;
157
158 friend struct profile_count;
159public:
160 profile_probability (): m_val (uninitialized_probability),
161 m_quality (GUESSED)
162 {}
163
164 profile_probability (uint32_t val, profile_quality quality):
165 m_val (val), m_quality (quality)
166 {}
167
168 /* Named probabilities. */
169 static profile_probability never ()
170 {
171 profile_probability ret;
172 ret.m_val = 0;
173 ret.m_quality = PRECISE;
174 return ret;
175 }
176
177 static profile_probability guessed_never ()
178 {
179 profile_probability ret;
180 ret.m_val = 0;
181 ret.m_quality = GUESSED;
182 return ret;
183 }
184
185 static profile_probability very_unlikely ()
186 {
187 /* Be consistent with PROB_VERY_UNLIKELY in predict.h. */
188 profile_probability r = guessed_always ().apply_scale (1, 2000);
189 r.m_val--;
190 return r;
191 }
192
193 static profile_probability unlikely ()
194 {
195 /* Be consistent with PROB_VERY_LIKELY in predict.h. */
196 profile_probability r = guessed_always ().apply_scale (1, 5);
197 r.m_val--;
198 return r;
199 }
200
201 static profile_probability even ()
202 {
203 return guessed_always ().apply_scale (1, 2);
204 }
205
206 static profile_probability very_likely ()
207 {
208 return always () - very_unlikely ();
209 }
210
211 static profile_probability likely ()
212 {
213 return always () - unlikely ();
214 }
215
216 static profile_probability guessed_always ()
217 {
218 profile_probability ret;
219 ret.m_val = max_probability;
220 ret.m_quality = GUESSED;
221 return ret;
222 }
223
224 static profile_probability always ()
225 {
226 profile_probability ret;
227 ret.m_val = max_probability;
228 ret.m_quality = PRECISE;
229 return ret;
230 }
231
232 /* Probabilities which has not been initialized. Either because
233 initialization did not happen yet or because profile is unknown. */
234 static profile_probability uninitialized ()
235 {
236 profile_probability c;
237 c.m_val = uninitialized_probability;
238 c.m_quality = GUESSED;
239 return c;
240 }
241
242 /* Return true if value has been initialized. */
243 bool initialized_p () const
244 {
245 return m_val != uninitialized_probability;
246 }
247
248 /* Return true if value can be trusted. */
249 bool reliable_p () const
250 {
251 return m_quality >= ADJUSTED;
252 }
253
254 /* Conversion from and to REG_BR_PROB_BASE integer fixpoint arithmetics.
255 this is mostly to support legacy code and should go away. */
256 static profile_probability from_reg_br_prob_base (int v)
257 {
258 profile_probability ret;
259 gcc_checking_assert (v >= 0 && v <= REG_BR_PROB_BASE)((void)(!(v >= 0 && v <= 10000) ? fancy_abort (
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h"
, 259, __FUNCTION__), 0 : 0))
;
260 ret.m_val = RDIV (v * (uint64_t) max_probability, REG_BR_PROB_BASE)(((v * (uint64_t) max_probability) + (10000) / 2) / (10000));
261 ret.m_quality = GUESSED;
262 return ret;
263 }
264
265 /* Return THIS with quality set to ADJUSTED. */
266 profile_probability adjusted () const
267 {
268 profile_probability ret = *this;
269 if (!initialized_p ())
270 return *this;
271 ret.m_quality = ADJUSTED;
272 return ret;
273 }
274
275 int to_reg_br_prob_base () const
276 {
277 gcc_checking_assert (initialized_p ())((void)(!(initialized_p ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h"
, 277, __FUNCTION__), 0 : 0))
;
278 return RDIV (m_val * (uint64_t) REG_BR_PROB_BASE, max_probability)(((m_val * (uint64_t) 10000) + (max_probability) / 2) / (max_probability
))
;
279 }
280
281 /* Conversion to and from RTL representation of profile probabilities. */
282 static profile_probability from_reg_br_prob_note (int v)
283 {
284 profile_probability ret;
285 ret.m_val = ((unsigned int)v) / 8;
286 ret.m_quality = (enum profile_quality)(v & 7);
287 return ret;
288 }
289
290 int to_reg_br_prob_note () const
291 {
292 gcc_checking_assert (initialized_p ())((void)(!(initialized_p ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h"
, 292, __FUNCTION__), 0 : 0))
;
293 int ret = m_val * 8 + m_quality;
294 gcc_checking_assert (from_reg_br_prob_note (ret) == *this)((void)(!(from_reg_br_prob_note (ret) == *this) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h"
, 294, __FUNCTION__), 0 : 0))
;
295 return ret;
296 }
297
298 /* Return VAL1/VAL2. */
299 static profile_probability probability_in_gcov_type
300 (gcov_type val1, gcov_type val2)
301 {
302 profile_probability ret;
303 gcc_checking_assert (val1 >= 0 && val2 > 0)((void)(!(val1 >= 0 && val2 > 0) ? fancy_abort (
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h"
, 303, __FUNCTION__), 0 : 0))
;
304 if (val1 > val2)
305 ret.m_val = max_probability;
306 else
307 {
308 uint64_t tmp;
309 safe_scale_64bit (val1, max_probability, val2, &tmp);
310 gcc_checking_assert (tmp <= max_probability)((void)(!(tmp <= max_probability) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h"
, 310, __FUNCTION__), 0 : 0))
;
311 ret.m_val = tmp;
312 }
313 ret.m_quality = PRECISE;
314 return ret;
315 }
316
317 /* Basic operations. */
318 bool operator== (const profile_probability &other) const
319 {
320 return m_val == other.m_val && m_quality == other.m_quality;
321 }
322
323 profile_probability operator+ (const profile_probability &other) const
324 {
325 if (other == never ())
326 return *this;
327 if (*this == never ())
328 return other;
329 if (!initialized_p () || !other.initialized_p ())
330 return uninitialized ();
331
332 profile_probability ret;
333 ret.m_val = MIN ((uint32_t)(m_val + other.m_val), max_probability)(((uint32_t)(m_val + other.m_val)) < (max_probability) ? (
(uint32_t)(m_val + other.m_val)) : (max_probability))
;
334 ret.m_quality = MIN (m_quality, other.m_quality)((m_quality) < (other.m_quality) ? (m_quality) : (other.m_quality
))
;
335 return ret;
336 }
337
338 profile_probability &operator+= (const profile_probability &other)
339 {
340 if (other == never ())
341 return *this;
342 if (*this == never ())
343 {
344 *this = other;
345 return *this;
346 }
347 if (!initialized_p () || !other.initialized_p ())
348 return *this = uninitialized ();
349 else
350 {
351 m_val = MIN ((uint32_t)(m_val + other.m_val), max_probability)(((uint32_t)(m_val + other.m_val)) < (max_probability) ? (
(uint32_t)(m_val + other.m_val)) : (max_probability))
;
352 m_quality = MIN (m_quality, other.m_quality)((m_quality) < (other.m_quality) ? (m_quality) : (other.m_quality
))
;
353 }
354 return *this;
355 }
356
357 profile_probability operator- (const profile_probability &other) const
358 {
359 if (*this == never ()
360 || other == never ())
361 return *this;
362 if (!initialized_p () || !other.initialized_p ())
363 return uninitialized ();
364 profile_probability ret;
365 ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
366 ret.m_quality = MIN (m_quality, other.m_quality)((m_quality) < (other.m_quality) ? (m_quality) : (other.m_quality
))
;
367 return ret;
368 }
369
370 profile_probability &operator-= (const profile_probability &other)
371 {
372 if (*this == never ()
373 || other == never ())
374 return *this;
375 if (!initialized_p () || !other.initialized_p ())
376 return *this = uninitialized ();
377 else
378 {
379 m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
380 m_quality = MIN (m_quality, other.m_quality)((m_quality) < (other.m_quality) ? (m_quality) : (other.m_quality
))
;
381 }
382 return *this;
383 }
384
385 profile_probability operator* (const profile_probability &other) const
386 {
387 if (*this == never ()
388 || other == never ())
389 return never ();
390 if (!initialized_p () || !other.initialized_p ())
391 return uninitialized ();
392 profile_probability ret;
393 ret.m_val = RDIV ((uint64_t)m_val * other.m_val, max_probability)((((uint64_t)m_val * other.m_val) + (max_probability) / 2) / (
max_probability))
;
394 ret.m_quality = MIN (MIN (m_quality, other.m_quality), ADJUSTED)((((m_quality) < (other.m_quality) ? (m_quality) : (other.
m_quality))) < (ADJUSTED) ? (((m_quality) < (other.m_quality
) ? (m_quality) : (other.m_quality))) : (ADJUSTED))
;
395 return ret;
396 }
397
398 profile_probability &operator*= (const profile_probability &other)
399 {
400 if (*this == never ()
401 || other == never ())
402 return *this = never ();
403 if (!initialized_p () || !other.initialized_p ())
404 return *this = uninitialized ();
405 else
406 {
407 m_val = RDIV ((uint64_t)m_val * other.m_val, max_probability)((((uint64_t)m_val * other.m_val) + (max_probability) / 2) / (
max_probability))
;
408 m_quality = MIN (MIN (m_quality, other.m_quality), ADJUSTED)((((m_quality) < (other.m_quality) ? (m_quality) : (other.
m_quality))) < (ADJUSTED) ? (((m_quality) < (other.m_quality
) ? (m_quality) : (other.m_quality))) : (ADJUSTED))
;
409 }
410 return *this;
411 }
412
413 profile_probability operator/ (const profile_probability &other) const
414 {
415 if (*this == never ())
416 return never ();
417 if (!initialized_p () || !other.initialized_p ())
418 return uninitialized ();
419 profile_probability ret;
420 /* If we get probability above 1, mark it as unreliable and return 1. */
421 if (m_val >= other.m_val)
422 {
423 ret.m_val = max_probability;
424 ret.m_quality = MIN (MIN (m_quality, other.m_quality),((((m_quality) < (other.m_quality) ? (m_quality) : (other.
m_quality))) < (GUESSED) ? (((m_quality) < (other.m_quality
) ? (m_quality) : (other.m_quality))) : (GUESSED))
425 GUESSED)((((m_quality) < (other.m_quality) ? (m_quality) : (other.
m_quality))) < (GUESSED) ? (((m_quality) < (other.m_quality
) ? (m_quality) : (other.m_quality))) : (GUESSED))
;
426 return ret;
427 }
428 else if (!m_val)
429 ret.m_val = 0;
430 else
431 {
432 gcc_checking_assert (other.m_val)((void)(!(other.m_val) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h"
, 432, __FUNCTION__), 0 : 0))
;
433 ret.m_val = MIN (RDIV ((uint64_t)m_val * max_probability,((((((uint64_t)m_val * max_probability) + (other.m_val) / 2) /
(other.m_val))) < (max_probability) ? (((((uint64_t)m_val
* max_probability) + (other.m_val) / 2) / (other.m_val))) : (
max_probability))
434 other.m_val),((((((uint64_t)m_val * max_probability) + (other.m_val) / 2) /
(other.m_val))) < (max_probability) ? (((((uint64_t)m_val
* max_probability) + (other.m_val) / 2) / (other.m_val))) : (
max_probability))
435 max_probability)((((((uint64_t)m_val * max_probability) + (other.m_val) / 2) /
(other.m_val))) < (max_probability) ? (((((uint64_t)m_val
* max_probability) + (other.m_val) / 2) / (other.m_val))) : (
max_probability))
;
436 }
437 ret.m_quality = MIN (MIN (m_quality, other.m_quality), ADJUSTED)((((m_quality) < (other.m_quality) ? (m_quality) : (other.
m_quality))) < (ADJUSTED) ? (((m_quality) < (other.m_quality
) ? (m_quality) : (other.m_quality))) : (ADJUSTED))
;
438 return ret;
439 }
440
441 profile_probability &operator/= (const profile_probability &other)
442 {
443 if (*this == never ())
444 return *this = never ();
445 if (!initialized_p () || !other.initialized_p ())
446 return *this = uninitialized ();
447 else
448 {
449 /* If we get probability above 1, mark it as unreliable
450 and return 1. */
451 if (m_val > other.m_val)
452 {
453 m_val = max_probability;
454 m_quality = MIN (MIN (m_quality, other.m_quality),((((m_quality) < (other.m_quality) ? (m_quality) : (other.
m_quality))) < (GUESSED) ? (((m_quality) < (other.m_quality
) ? (m_quality) : (other.m_quality))) : (GUESSED))
455 GUESSED)((((m_quality) < (other.m_quality) ? (m_quality) : (other.
m_quality))) < (GUESSED) ? (((m_quality) < (other.m_quality
) ? (m_quality) : (other.m_quality))) : (GUESSED))
;
456 return *this;
457 }
458 else if (!m_val)
459 ;
460 else
461 {
462 gcc_checking_assert (other.m_val)((void)(!(other.m_val) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h"
, 462, __FUNCTION__), 0 : 0))
;
463 m_val = MIN (RDIV ((uint64_t)m_val * max_probability,((((((uint64_t)m_val * max_probability) + (other.m_val) / 2) /
(other.m_val))) < (max_probability) ? (((((uint64_t)m_val
* max_probability) + (other.m_val) / 2) / (other.m_val))) : (
max_probability))
464 other.m_val),((((((uint64_t)m_val * max_probability) + (other.m_val) / 2) /
(other.m_val))) < (max_probability) ? (((((uint64_t)m_val
* max_probability) + (other.m_val) / 2) / (other.m_val))) : (
max_probability))
465 max_probability)((((((uint64_t)m_val * max_probability) + (other.m_val) / 2) /
(other.m_val))) < (max_probability) ? (((((uint64_t)m_val
* max_probability) + (other.m_val) / 2) / (other.m_val))) : (
max_probability))
;
466 }
467 m_quality = MIN (MIN (m_quality, other.m_quality), ADJUSTED)((((m_quality) < (other.m_quality) ? (m_quality) : (other.
m_quality))) < (ADJUSTED) ? (((m_quality) < (other.m_quality
) ? (m_quality) : (other.m_quality))) : (ADJUSTED))
;
468 }
469 return *this;
470 }
471
472 /* Split *THIS (ORIG) probability into 2 probabilities, such that
473 the returned one (FIRST) is *THIS * CPROB and *THIS is
474 adjusted (SECOND) so that FIRST + FIRST.invert () * SECOND
475 == ORIG. This is useful e.g. when splitting a conditional
476 branch like:
477 if (cond)
478 goto lab; // ORIG probability
479 into
480 if (cond1)
481 goto lab; // FIRST = ORIG * CPROB probability
482 if (cond2)
483 goto lab; // SECOND probability
484 such that the overall probability of jumping to lab remains
485 the same. CPROB gives the relative probability between the
486 branches. */
487 profile_probability split (const profile_probability &cprob)
488 {
489 profile_probability ret = *this * cprob;
490 /* The following is equivalent to:
491 *this = cprob.invert () * *this / ret.invert ();
492 Avoid scaling when overall outcome is supposed to be always.
493 Without knowing that one is inverse of other, the result would be
494 conservative. */
495 if (!(*this == always ()))
496 *this = (*this - ret) / ret.invert ();
497 return ret;
498 }
499
500 gcov_type apply (gcov_type val) const
501 {
502 if (*this == uninitialized ())
503 return val / 2;
504 return RDIV (val * m_val, max_probability)(((val * m_val) + (max_probability) / 2) / (max_probability));
505 }
506
507 /* Return 1-*THIS. */
508 profile_probability invert () const
509 {
510 return always() - *this;
511 }
512
513 /* Return THIS with quality dropped to GUESSED. */
514 profile_probability guessed () const
515 {
516 profile_probability ret = *this;
517 ret.m_quality = GUESSED;
518 return ret;
519 }
520
521 /* Return THIS with quality dropped to AFDO. */
522 profile_probability afdo () const
523 {
524 profile_probability ret = *this;
525 ret.m_quality = AFDO;
526 return ret;
527 }
528
529 /* Return *THIS * NUM / DEN. */
530 profile_probability apply_scale (int64_t num, int64_t den) const
531 {
532 if (*this == never ())
533 return *this;
534 if (!initialized_p ())
535 return uninitialized ();
536 profile_probability ret;
537 uint64_t tmp;
538 safe_scale_64bit (m_val, num, den, &tmp);
539 ret.m_val = MIN (tmp, max_probability)((tmp) < (max_probability) ? (tmp) : (max_probability));
540 ret.m_quality = MIN (m_quality, ADJUSTED)((m_quality) < (ADJUSTED) ? (m_quality) : (ADJUSTED));
541 return ret;
542 }
543
544 /* Return true when the probability of edge is reliable.
545
546 The profile guessing code is good at predicting branch outcome (i.e.
547 taken/not taken), that is predicted right slightly over 75% of time.
548 It is however notoriously poor on predicting the probability itself.
549 In general the profile appear a lot flatter (with probabilities closer
550 to 50%) than the reality so it is bad idea to use it to drive optimization
551 such as those disabling dynamic branch prediction for well predictable
552 branches.
553
554 There are two exceptions - edges leading to noreturn edges and edges
555 predicted by number of iterations heuristics are predicted well. This macro
556 should be able to distinguish those, but at the moment it simply check for
557 noreturn heuristic that is only one giving probability over 99% or bellow
558 1%. In future we might want to propagate reliability information across the
559 CFG if we find this information useful on multiple places. */
560 bool probably_reliable_p () const
561 {
562 if (m_quality >= ADJUSTED)
563 return true;
564 if (!initialized_p ())
565 return false;
566 return m_val < max_probability / 100
567 || m_val > max_probability - max_probability / 100;
568 }
569
570 /* Return false if profile_probability is bogus. */
571 bool verify () const
572 {
573 gcc_checking_assert (m_quality != UNINITIALIZED_PROFILE)((void)(!(m_quality != UNINITIALIZED_PROFILE) ? fancy_abort (
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h"
, 573, __FUNCTION__), 0 : 0))
;
574 if (m_val == uninitialized_probability)
575 return m_quality == GUESSED;
576 else if (m_quality < GUESSED)
577 return false;
578 return m_val <= max_probability;
579 }
580
581 /* Comparisons are three-state and conservative. False is returned if
582 the inequality cannot be decided. */
583 bool operator< (const profile_probability &other) const
584 {
585 return initialized_p () && other.initialized_p () && m_val < other.m_val;
586 }
587
588 bool operator> (const profile_probability &other) const
589 {
590 return initialized_p () && other.initialized_p () && m_val > other.m_val;
591 }
592
593 bool operator<= (const profile_probability &other) const
594 {
595 return initialized_p () && other.initialized_p () && m_val <= other.m_val;
596 }
597
598 bool operator>= (const profile_probability &other) const
599 {
600 return initialized_p () && other.initialized_p () && m_val >= other.m_val;
601 }
602
603 /* Get the value of the count. */
604 uint32_t value () const { return m_val; }
605
606 /* Get the quality of the count. */
607 enum profile_quality quality () const { return m_quality; }
608
609 /* Output THIS to F. */
610 void dump (FILE *f) const;
611
612 /* Print THIS to stderr. */
613 void debug () const;
614
615 /* Return true if THIS is known to differ significantly from OTHER. */
616 bool differs_from_p (profile_probability other) const;
617
618 /* Return if difference is greater than 50%. */
619 bool differs_lot_from_p (profile_probability other) const;
620
621 /* COUNT1 times event happens with *THIS probability, COUNT2 times OTHER
622 happens with COUNT2 probability. Return probability that either *THIS or
623 OTHER happens. */
624 profile_probability combine_with_count (profile_count count1,
625 profile_probability other,
626 profile_count count2) const;
627
628 /* Return probability as sreal. */
629 sreal to_sreal () const;
630 /* LTO streaming support. */
631 static profile_probability stream_in (class lto_input_block *);
632 void stream_out (struct output_block *);
633 void stream_out (struct lto_output_stream *);
634};
635
636/* Main data type to hold profile counters in GCC. Profile counts originate
637 either from profile feedback, static profile estimation or both. We do not
638 perform whole program profile propagation and thus profile estimation
639 counters are often local to function, while counters from profile feedback
640 (or special cases of profile estimation) can be used inter-procedurally.
641
642 There are 3 basic types
643 1) local counters which are result of intra-procedural static profile
644 estimation.
645 2) ipa counters which are result of profile feedback or special case
646 of static profile estimation (such as in function main).
647 3) counters which counts as 0 inter-procedurally (because given function
648 was never run in train feedback) but they hold local static profile
649 estimate.
650
651 Counters of type 1 and 3 cannot be mixed with counters of different type
652 within operation (because whole function should use one type of counter)
653 with exception that global zero mix in most operations where outcome is
654 well defined.
655
656 To take local counter and use it inter-procedurally use ipa member function
657 which strips information irrelevant at the inter-procedural level.
658
659 Counters are 61bit integers representing number of executions during the
660 train run or normalized frequency within the function.
661
662 As the profile is maintained during the compilation, many adjustments are
663 made. Not all transformations can be made precisely, most importantly
664 when code is being duplicated. It also may happen that part of CFG has
665 profile counts known while other do not - for example when LTO optimizing
666 partly profiled program or when profile was lost due to COMDAT merging.
667
668 For this reason profile_count tracks more information than
669 just unsigned integer and it is also ready for profile mismatches.
670 The API of this data type represent operations that are natural
671 on profile counts - sum, difference and operation with scales and
672 probabilities. All operations are safe by never getting negative counts
673 and they do end up in uninitialized scale if any of the parameters is
674 uninitialized.
675
676 All comparisons that are three state and handling of probabilities. Thus
677 a < b is not equal to !(a >= b).
678
679 The following pre-defined counts are available:
680
681 profile_count::zero () for code that is known to execute zero times at
682 runtime (this can be detected statically i.e. for paths leading to
683 abort ();
684 profile_count::one () for code that is known to execute once (such as
685 main () function
686 profile_count::uninitialized () for unknown execution count.
687
688 */
689
690struct GTY(()) profile_count
691{
692public:
693 /* Use 62bit to hold basic block counters. Should be at least
694 64bit. Although a counter cannot be negative, we use a signed
695 type to hold various extra stages. */
696
697 static const int n_bits = 61;
698 static const uint64_t max_count = ((uint64_t) 1 << n_bits) - 2;
699private:
700 static const uint64_t uninitialized_count = ((uint64_t) 1 << n_bits) - 1;
701
702#if defined (__arm__) && (__GNUC__4 >= 6 && __GNUC__4 <= 8)
703 /* Work-around for PR88469. A bug in the gcc-6/7/8 PCS layout code
704 incorrectly detects the alignment of a structure where the only
705 64-bit aligned object is a bit-field. We force the alignment of
706 the entire field to mitigate this. */
707#define UINT64_BIT_FIELD_ALIGN __attribute__ ((aligned(8)))
708#else
709#define UINT64_BIT_FIELD_ALIGN
710#endif
711 uint64_t UINT64_BIT_FIELD_ALIGN m_val : n_bits;
712#undef UINT64_BIT_FIELD_ALIGN
713 enum profile_quality m_quality : 3;
714public:
715
716 /* Return true if both values can meaningfully appear in single function
717 body. We have either all counters in function local or global, otherwise
718 operations between them are not really defined well. */
719 bool compatible_p (const profile_count other) const
720 {
721 if (!initialized_p () || !other.initialized_p ())
722 return true;
723 if (*this == zero ()
724 || other == zero ())
725 return true;
726 /* Do not allow nonzero global profile together with local guesses
727 that are globally0. */
728 if (ipa ().nonzero_p ()
729 && !(other.ipa () == other))
730 return false;
731 if (other.ipa ().nonzero_p ()
732 && !(ipa () == *this))
733 return false;
734
735 return ipa_p () == other.ipa_p ();
736 }
737
738 /* Used for counters which are expected to be never executed. */
739 static profile_count zero ()
740 {
741 return from_gcov_type (0);
742 }
743
744 static profile_count adjusted_zero ()
745 {
746 profile_count c;
747 c.m_val = 0;
748 c.m_quality = ADJUSTED;
749 return c;
750 }
751
752 static profile_count guessed_zero ()
753 {
754 profile_count c;
755 c.m_val = 0;
756 c.m_quality = GUESSED;
757 return c;
758 }
759
760 static profile_count one ()
761 {
762 return from_gcov_type (1);
763 }
764
765 /* Value of counters which has not been initialized. Either because
766 initialization did not happen yet or because profile is unknown. */
767 static profile_count uninitialized ()
768 {
769 profile_count c;
770 c.m_val = uninitialized_count;
771 c.m_quality = GUESSED_LOCAL;
772 return c;
773 }
774
775 /* Conversion to gcov_type is lossy. */
776 gcov_type to_gcov_type () const
777 {
778 gcc_checking_assert (initialized_p ())((void)(!(initialized_p ()) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/profile-count.h"
, 778, __FUNCTION__), 0 : 0))
;
779 return m_val;
780 }
781
782 /* Return true if value has been initialized. */
783 bool initialized_p () const
784 {
785 return m_val != uninitialized_count;
786 }
787
788 /* Return true if value can be trusted. */
789 bool reliable_p () const
790 {
791 return m_quality >= ADJUSTED;
792 }
793
794 /* Return true if value can be operated inter-procedurally. */
795 bool ipa_p () const
796 {
797 return !initialized_p () || m_quality >= GUESSED_GLOBAL0;
798 }
799
800 /* Return true if quality of profile is precise. */
801 bool precise_p ()