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

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

Show analyzer invocation

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.
 Copyright (C) 2000-2021 Free Software Foundation, Inc.

4This file is part of GCC.

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.

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.

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/>.  */

20/* References:

 [1] "Branch Prediction for Free"
     Ball and Larus; PLDI '93.
 [2] "Static Branch Frequency and Program Profile Analysis"
     Wu and Larus; MICRO-27.
 [3] "Corpus-based Static Branch Prediction"
     Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.  */


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"

64/* Enum with reasons why a predictor is ignored.  */

66enum predictor_reason
67{
REASON_NONE,
REASON_IGNORED,
REASON_SINGLE_EDGE_DUPLICATE,
REASON_EDGE_PAIR_DUPLICATE
72};

74/* String messages for the aforementioned enum.  */

76static const char *reason_messages[] = {"", " (ignored)",
  " (single edge duplicate)", " (edge pair duplicate)"};


80static void combine_predictions_for_insn (rtx_insn *, basic_block);
81static void dump_prediction (FILE *, enum br_predictor, int, basic_block,
	     enum predictor_reason, edge);
83static void predict_paths_leading_to (basic_block, enum br_predictor,
		      enum prediction,
		      class loop *in_loop = NULLnullptr);
86static void predict_paths_leading_to_edge (edge, enum br_predictor,
			   enum prediction,
			   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 ();

93/* Information we hold about each branch predictor.
 Filled using information from predict.def.  */

96struct predictor_info
97{
const char *const name;	/* Name used in the debugging dumps.  */
const int hitrate;		/* Expected hitrate used by
		   predict_insn_def call.  */
const int flags;
102};

104/* Use given predictor without Dempster-Shaffer theory if it matches
 using first_match heuristics.  */
106#define PRED_FLAG_FIRST_MATCH1 1

108/* Recompute hitrate in percent to our representation.  */

110#define HITRATE(VAL)((int) ((VAL) * 10000 + 50) / 100) ((int) ((VAL) * REG_BR_PROB_BASE10000 + 50) / 100)

112#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
113static const struct predictor_info predictor_info[]= {
114#include "predict.def"

/* Upper bound on predictors.  */
{NULLnullptr, 0, 0}
118};
119#undef DEF_PREDICTOR

121static gcov_type min_count = -1;

123/* Determine the threshold for hot BB counts.  */

125gcov_type
126get_hot_bb_threshold ()
127{
if (min_count == -1)
  {
    const int hot_frac = param_hot_bb_count_fractionglobal_options.x_param_hot_bb_count_fraction;
    const gcov_type min_hot_count
= hot_frac
 ? profile_info->sum_max / hot_frac
 : (gcov_type)profile_count::max_count;
    set_hot_bb_threshold (min_hot_count);
    if (dump_file)
fprintf (dump_file, "Setting hotness threshold to %" PRId64"l" "d" ".\n",
 min_hot_count);
  }
return min_count;
141}

143/* Set the threshold for hot BB counts.  */

145void
146set_hot_bb_threshold (gcov_type min)
147{
min_count = min;
149}

151/* Return TRUE if COUNT is considered to be hot in function FUN.  */

153bool
154maybe_hot_count_p (struct function *fun, profile_count count)
155{
if (!count.initialized_p ())
  return true;
if (count.ipa () == profile_count::zero ())
  return false;
if (!count.ipa_p ())
  {
    struct cgraph_node *node = cgraph_node::get (fun->decl);
    if (!profile_info || profile_status_for_fn (fun)((fun)->cfg->x_profile_status) != PROFILE_READ)
{
 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
   return false;
 if (node->frequency == NODE_FREQUENCY_HOT)
   return true;
}
    if (profile_status_for_fn (fun)((fun)->cfg->x_profile_status) == PROFILE_ABSENT)
return true;
    if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
 && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)((fun)->cfg->x_entry_block_ptr)->count.apply_scale (2, 3)))
return false;
    if (count.apply_scale (param_hot_bb_frequency_fractionglobal_options.x_param_hot_bb_frequency_fraction, 1)
 < ENTRY_BLOCK_PTR_FOR_FN (fun)((fun)->cfg->x_entry_block_ptr)->count)
return false;
    return true;
  }
/* Code executed at most once is not hot.  */
if (count <= MAX (profile_info ? profile_info->runs : 1, 1)((profile_info ? profile_info->runs : 1) > (1) ? (profile_info
 ? profile_info->runs : 1) : (1)))
  return false;
return (count >= get_hot_bb_threshold ());
184}

186/* Return true if basic block BB of function FUN can be CPU intensive
 and should thus be optimized for maximum performance.  */

189bool
190maybe_hot_bb_p (struct function *fun, const_basic_block bb)
191{
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));
return maybe_hot_count_p (fun, bb->count);
194}

196/* Return true if edge E can be CPU intensive and should thus be optimized
 for maximum performance.  */

199bool
200maybe_hot_edge_p (edge e)
201{
return maybe_hot_count_p (cfun(cfun + 0), e->count ());
203}

205/* Return true if COUNT is considered to be never executed in function FUN
 or if function FUN is considered so in the static profile.  */
 
208static bool
209probably_never_executed (struct function *fun, profile_count count)
210{
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));
if (count.ipa () == profile_count::zero ())
  return true;
/* Do not trust adjusted counts.  This will make us to drop int cold section
   code with low execution count as a result of inlining. These low counts
   are not safe even with read profile and may lead us to dropping
   code which actually gets executed into cold section of binary that is not
   desirable.  */
if (count.precise_p () && profile_status_for_fn (fun)((fun)->cfg->x_profile_status) == PROFILE_READ)
  {
    const int unlikely_frac = param_unlikely_bb_count_fractionglobal_options.x_param_unlikely_bb_count_fraction;
    if (count.apply_scale (unlikely_frac, 1) >= profile_info->runs)
return false;
    return true;
  }
if ((!profile_info || profile_status_for_fn (fun)((fun)->cfg->x_profile_status) != PROFILE_READ)
    && (cgraph_node::get (fun->decl)->frequency
 == NODE_FREQUENCY_UNLIKELY_EXECUTED))
  return true;
return false;
231}

233/* Return true if basic block BB of function FUN is probably never executed.  */

235bool
236probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
237{
return probably_never_executed (fun, bb->count);
239}

241/* Return true if edge E is unlikely executed for obvious reasons.  */

243static bool
244unlikely_executed_edge_p (edge e)
245{
return (e->src->count == profile_count::zero ()
 || e->probability == profile_probability::never ())
|| (e->flags & (EDGE_EH | EDGE_FAKE));
249}

251/* Return true if edge E of function FUN is probably never executed.  */

253bool
254probably_never_executed_edge_p (struct function *fun, edge e)
255{
if (unlikely_executed_edge_p (e))
  return true;
return probably_never_executed (fun, e->count ());
259}

261/* Return true if function FUN should always be optimized for size.  */

263optimize_size_level
264optimize_function_for_size_p (struct function *fun)
265{
if (!fun || !fun->decl)
  return optimize_sizeglobal_options.x_optimize_size ? OPTIMIZE_SIZE_MAX : OPTIMIZE_SIZE_NO;
cgraph_node *n = cgraph_node::get (fun->decl);
if (n)
  return n->optimize_for_size_p ();
return OPTIMIZE_SIZE_NO;
272}

274/* Return true if function FUN should always be optimized for speed.  */

276bool
277optimize_function_for_speed_p (struct function *fun)
278{
return !optimize_function_for_size_p (fun);
280}

282/* Return the optimization type that should be used for function FUN.  */

284optimization_type
285function_optimization_type (struct function *fun)
286{
return (optimize_function_for_speed_p (fun)
 ? OPTIMIZE_FOR_SPEED
 : OPTIMIZE_FOR_SIZE);
290}

292/* Return TRUE if basic block BB should be optimized for size.  */

294optimize_size_level
295optimize_bb_for_size_p (const_basic_block bb)
296{
enum optimize_size_level ret = optimize_function_for_size_p (cfun(cfun + 0));

if (bb && ret < OPTIMIZE_SIZE_MAX && bb->count == profile_count::zero ())
  ret = OPTIMIZE_SIZE_MAX;
if (bb && ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_bb_p (cfun(cfun + 0), bb))
  ret = OPTIMIZE_SIZE_BALANCED;
return ret;
304}

306/* Return TRUE if basic block BB should be optimized for speed.  */

308bool
309optimize_bb_for_speed_p (const_basic_block bb)
310{
return !optimize_bb_for_size_p (bb);
312}

314/* Return the optimization type that should be used for basic block BB.  */

316optimization_type
317bb_optimization_type (const_basic_block bb)
318{
return (optimize_bb_for_speed_p (bb)
 ? OPTIMIZE_FOR_SPEED
 : OPTIMIZE_FOR_SIZE);
322}

324/* Return TRUE if edge E should be optimized for size.  */

326optimize_size_level
327optimize_edge_for_size_p (edge e)
328{
enum optimize_size_level ret = optimize_function_for_size_p (cfun(cfun + 0));

if (ret < OPTIMIZE_SIZE_MAX && unlikely_executed_edge_p (e))
  ret = OPTIMIZE_SIZE_MAX;
if (ret < OPTIMIZE_SIZE_BALANCED && !maybe_hot_edge_p (e))
  ret = OPTIMIZE_SIZE_BALANCED;
return ret;
336}

338/* Return TRUE if edge E should be optimized for speed.  */

340bool
341optimize_edge_for_speed_p (edge e)
342{
return !optimize_edge_for_size_p (e);
344}

346/* Return TRUE if the current function is optimized for size.  */

348optimize_size_level
349optimize_insn_for_size_p (void)
350{
enum optimize_size_level ret = optimize_function_for_size_p (cfun(cfun + 0));
if (ret < OPTIMIZE_SIZE_BALANCED && !crtl(&x_rtl)->maybe_hot_insn_p)
  ret = OPTIMIZE_SIZE_BALANCED;
return ret;
355}

357/* Return TRUE if the current function is optimized for speed.  */

359bool
360optimize_insn_for_speed_p (void)
361{
return !optimize_insn_for_size_p ();
363}

365/* Return TRUE if LOOP should be optimized for size.  */

367optimize_size_level
368optimize_loop_for_size_p (class loop *loop)
369{
return optimize_bb_for_size_p (loop->header);
371}

373/* Return TRUE if LOOP should be optimized for speed.  */

375bool
376optimize_loop_for_speed_p (class loop *loop)
377{
return optimize_bb_for_speed_p (loop->header);
379}

381/* Return TRUE if nest rooted at LOOP should be optimized for speed.  */

383bool
384optimize_loop_nest_for_speed_p (class loop *loop)
385{
class loop *l = loop;
if (optimize_loop_for_speed_p (loop))
  return true;
l = loop->inner;
while (l && l != loop)
  {
    if (optimize_loop_for_speed_p (l))
      return true;
    if (l->inner)
      l = l->inner;
    else if (l->next)
      l = l->next;
    else
      {
 while (l != loop && !l->next)
   l = loop_outer (l);
 if (l != loop)
   l = l->next;
}
  }
return false;
407}

409/* Return TRUE if nest rooted at LOOP should be optimized for size.  */

411optimize_size_level
412optimize_loop_nest_for_size_p (class loop *loop)
413{
enum optimize_size_level ret = optimize_loop_for_size_p (loop);
class loop *l = loop;

l = loop->inner;
while (l && l != loop)
  {
    if (ret == OPTIMIZE_SIZE_NO)
break;
    ret = MIN (optimize_loop_for_size_p (l), ret)((optimize_loop_for_size_p (l)) < (ret) ? (optimize_loop_for_size_p
 (l)) : (ret));
    if (l->inner)
      l = l->inner;
    else if (l->next)
      l = l->next;
    else
      {
 while (l != loop && !l->next)
   l = loop_outer (l);
 if (l != loop)
   l = l->next;
}
  }
return ret;
436}

438/* Return true if edge E is likely to be well predictable by branch
 predictor.  */

441bool
442predictable_edge_p (edge e)
443{
if (!e->probability.initialized_p ())
  return false;
if ((e->probability.to_reg_br_prob_base ()
     <= param_predictable_branch_outcomeglobal_options.x_param_predictable_branch_outcome * REG_BR_PROB_BASE10000 / 100)
    || (REG_BR_PROB_BASE10000 - e->probability.to_reg_br_prob_base ()
 <= param_predictable_branch_outcomeglobal_options.x_param_predictable_branch_outcome * REG_BR_PROB_BASE10000 / 100))
  return true;
return false;
452}


455/* Set RTL expansion for BB profile.  */

457void
458rtl_profile_for_bb (basic_block bb)
459{
crtl(&x_rtl)->maybe_hot_insn_p = maybe_hot_bb_p (cfun(cfun + 0), bb);
461}

463/* Set RTL expansion for edge profile.  */

465void
466rtl_profile_for_edge (edge e)
467{
crtl(&x_rtl)->maybe_hot_insn_p = maybe_hot_edge_p (e);
469}

471/* Set RTL expansion to default mode (i.e. when profile info is not known).  */
472void
473default_rtl_profile (void)
474{
crtl(&x_rtl)->maybe_hot_insn_p = true;
476}

478/* Return true if the one of outgoing edges is already predicted by
 PREDICTOR.  */

481bool
482rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
483{
rtx note;
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)))
  return false;
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))
  if (REG_NOTE_KIND (note)((enum reg_note) ((machine_mode) (note)->mode)) == REG_BR_PRED
&& INTVAL (XEXP (XEXP (note, 0), 0))((((((((note)->u.fld[0]).rt_rtx))->u.fld[0]).rt_rtx))->
u.hwint[0]) == (int)predictor)
    return true;
return false;
492}

494/*  Structure representing predictions in tree level. */

496struct edge_prediction {
  struct edge_prediction *ep_next;
  edge ep_edge;
  enum br_predictor ep_predictor;
  int ep_probability;
501};

503/* This map contains for a basic block the list of predictions for the
 outgoing edges.  */

506static hash_map<const_basic_block, edge_prediction *> *bb_predictions;

508/* Return true if the one of outgoing edges is already predicted by
 PREDICTOR.  */

511bool
512gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
513{
struct edge_prediction *i;
edge_prediction **preds = bb_predictions->get (bb);

if (!preds)
  return false;

for (i = *preds; i; i = i->ep_next)
  if (i->ep_predictor == predictor)
    return true;
return false;
524}

526/* Return true if the one of outgoing edges is already predicted by
 PREDICTOR for edge E predicted as TAKEN.  */

529bool
530edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
531{
struct edge_prediction *i;
basic_block bb = e->src;
edge_prediction **preds = bb_predictions->get (bb);
if (!preds)
  return false;

int probability = predictor_info[(int) predictor].hitrate;

if (taken != TAKEN)
  probability = REG_BR_PROB_BASE10000 - probability;

for (i = *preds; i; i = i->ep_next)
  if (i->ep_predictor == predictor
&& i->ep_edge == e
&& i->ep_probability == probability)
    return true;
return false;
549}

551/* Same predicate as above, working on edges.  */
552bool
553edge_probability_reliable_p (const_edge e)
554{
return e->probability.probably_reliable_p ();
556}

558/* Same predicate as edge_probability_reliable_p, working on notes.  */
559bool
560br_prob_note_reliable_p (const_rtx note)
561{
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));
return profile_probability::from_reg_br_prob_note
 (XINT (note, 0)(((note)->u.fld[0]).rt_int)).probably_reliable_p ();
565}

567static void
568predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
569{
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));
if (!flag_guess_branch_probglobal_options.x_flag_guess_branch_prob)
  return;

add_reg_note (insn, REG_BR_PRED,
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
)))) )
		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
)))) )
		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}

580/* Predict insn by given predictor.  */

582void
583predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
  enum prediction taken)
585{
 int probability = predictor_info[(int) predictor].hitrate;
 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));

 if (taken != TAKEN)
   probability = REG_BR_PROB_BASE10000 - probability;

 predict_insn (insn, predictor, probability);
593}

595/* Predict edge E with given probability if possible.  */

597void
598rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
599{
rtx_insn *last_insn;
last_insn = BB_END (e->src)(e->src)->il.x.rtl->end_;

/* We can store the branch prediction information only about
   conditional jumps.  */
if (!any_condjump_p (last_insn))
  return;

/* We always store probability of branching.  */
if (e->flags & EDGE_FALLTHRU)
  probability = REG_BR_PROB_BASE10000 - probability;

predict_insn (last_insn, predictor, probability);
613}

615/* Predict edge E with the given PROBABILITY.  */
616void
617gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
618{
if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)
    && EDGE_COUNT (e->src->succs)vec_safe_length (e->src->succs) > 1
    && flag_guess_branch_probglobal_options.x_flag_guess_branch_prob
    && optimizeglobal_options.x_optimize)
  {
    struct edge_prediction *i = XNEW (struct edge_prediction)((struct edge_prediction *) xmalloc (sizeof (struct edge_prediction
)));
    edge_prediction *&preds = bb_predictions->get_or_insert (e->src);

    i->ep_next = preds;
    preds = i;
    i->ep_probability = probability;
    i->ep_predictor = predictor;
    i->ep_edge = e;
  }
633}

635/* Filter edge predictions PREDS by a function FILTER: if FILTER return false
 the prediction is removed.
 DATA are passed to the filter function.  */

639static void
640filter_predictions (edge_prediction **preds,
    bool (*filter) (edge_prediction *, void *), void *data)
642{
if (!bb_predictions)
  return;

if (preds)
  {
    struct edge_prediction **prediction = preds;
    struct edge_prediction *next;

    while (*prediction)
{
 if ((*filter) (*prediction, data))
   prediction = &((*prediction)->ep_next);
 else
   {
     next = (*prediction)->ep_next;
     free (*prediction);
     *prediction = next;
   }
}
  }
663}

665/* Filter function predicate that returns true for a edge predicate P
 if its edge is equal to DATA.  */

668static bool
669not_equal_edge_p (edge_prediction *p, void *data)
670{
return p->ep_edge != (edge)data;
672}

674/* Remove all predictions on given basic block that are attached
 to edge E.  */
676void
677remove_predictions_associated_with_edge (edge e)
678{
if (!bb_predictions)
  return;

edge_prediction **preds = bb_predictions->get (e->src);
filter_predictions (preds, not_equal_edge_p, e);
684}

686/* Clears the list of predictions stored for BB.  */

688static void
689clear_bb_predictions (basic_block bb)
690{
edge_prediction **preds = bb_predictions->get (bb);
struct edge_prediction *pred, *next;

if (!preds)
  return;

for (pred = *preds; pred; pred = next)
  {
    next = pred->ep_next;
    free (pred);
  }
*preds = NULLnullptr;
703}

705/* Return true when we can store prediction on insn INSN.
 At the moment we represent predictions only on conditional
 jumps, not at computed jump or other complicated cases.  */
708static bool
709can_predict_insn_p (const rtx_insn *insn)
710{
return (JUMP_P (insn)(((enum rtx_code) (insn)->code) == JUMP_INSN)
5
←
Returning the value 1, which participates in a condition later→
 && any_condjump_p (insn)
3
←
Assuming the condition is true→
 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs)vec_safe_length (BLOCK_FOR_INSN (insn)->succs) >= 2);
4
←
Assuming the condition is true→
714}

716/* Predict edge E by given predictor if possible.  */

718void
719predict_edge_def (edge e, enum br_predictor predictor,
  enum prediction taken)
721{
 int probability = predictor_info[(int) predictor].hitrate;

 if (taken != TAKEN)
   probability = REG_BR_PROB_BASE10000 - probability;

 predict_edge (e, predictor, probability);
728}

730/* Invert all branch predictions or probability notes in the INSN.  This needs
 to be done each time we invert the condition used by the jump.  */

733void
734invert_br_probabilities (rtx insn)
735{
rtx note;

for (note = REG_NOTES (insn)(((insn)->u.fld[6]).rt_rtx); note; note = XEXP (note, 1)(((note)->u.fld[1]).rt_rtx))
  if (REG_NOTE_KIND (note)((enum reg_note) ((machine_mode) (note)->mode)) == REG_BR_PROB)
    XINT (note, 0)(((note)->u.fld[0]).rt_int) = profile_probability::from_reg_br_prob_note
	 (XINT (note, 0)(((note)->u.fld[0]).rt_int)).invert ().to_reg_br_prob_note ();
  else if (REG_NOTE_KIND (note)((enum reg_note) ((machine_mode) (note)->mode)) == REG_BR_PRED)
    XEXP (XEXP (note, 0), 1)((((((note)->u.fld[0]).rt_rtx))->u.fld[1]).rt_rtx)
= 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}

747/* Dump information about the branch prediction to the output file.  */

749static void
750dump_prediction (FILE *file, enum br_predictor predictor, int probability,
 basic_block bb, enum predictor_reason reason = REASON_NONE,
 edge ep_edge = NULLnullptr)
753{
edge e = ep_edge;
edge_iterator ei;

if (!file13.1
'file' is non-null
1
'file' is non-null
1
'file' is non-null
)
14
←
Taking false branch→
  return;

if (e == NULLnullptr)
15
←
Taking true branch→
  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→
    if (! (e->flags & EDGE_FALLTHRU))
break;

char edge_info_str[128];
if (ep_edge23.1
'ep_edge' is null
1
'ep_edge' is null
1
'ep_edge' is null
)
24
←
Taking false branch→
  sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
    ep_edge->dest->index);
else
  edge_info_str[0] = '\0';

fprintf (file, "  %s heuristics%s%s: %.2f%%",
  predictor_info[predictor].name,
  edge_info_str, reason_messages[reason],
  probability * 100.0 / REG_BR_PROB_BASE10000);

if (bb->count.initialized_p ())
25
←
Taking true branch→
  {
    fprintf (file, "  exec ");
    bb->count.dump (file);
    if (e25.1
'e' is null
1
'e' is null
1
'e' is null
)
26
←
Taking false branch→
{
 fprintf (file, " hit ");
 e->count ().dump (file);
 fprintf (file, " (%.1f%%)", e->count ().to_gcov_type() * 100.0
   / bb->count.to_gcov_type ());
}
  }

fprintf (file, "\n");

/* Print output that be easily read by analyze_brprob.py script. We are
   interested only in counts that are read from GCDA files.  */
if (dump_file && (dump_flags & TDF_DETAILS)
27
←
Assuming 'dump_file' is non-null→
28
←
Assuming the condition is true→
33
←
Taking true branch→
    && bb->count.precise_p ()
29
←
Calling 'profile_count::precise_p'→
32
←
Returning from 'profile_count::precise_p'→
    && reason32.1
'reason' is equal to REASON_NONE
1
'reason' is equal to REASON_NONE
1
'reason' is equal to REASON_NONE
 == REASON_NONE)
  {
    fprintf (file, ";;heuristics;%s;%" PRId64"l" "d" ";%" PRId64"l" "d" ";%.1f;\n",
      predictor_info[predictor].name,
      bb->count.to_gcov_type (), e->count ().to_gcov_type (),
34
←
Called C++ object pointer is null
      probability * 100.0 / REG_BR_PROB_BASE10000);
  }
803}

805/* Return true if STMT is known to be unlikely executed.  */

807static bool
808unlikely_executed_stmt_p (gimple *stmt)
809{
if (!is_gimple_call (stmt))
  return false;
/* NORETURN attribute alone is not strong enough: exit() may be quite
   likely executed once during program run.  */
if (gimple_call_fntype (stmt)
    && lookup_attribute ("cold",
	   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))
    && !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)))
  return true;
tree decl = gimple_call_fndecl (stmt);
if (!decl)
  return false;
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))
    && !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)))
  return true;

cgraph_node *n = cgraph_node::get (decl);
if (!n)
  return false;

availability avail;
n = n->ultimate_alias_target (&avail);
if (avail < AVAIL_AVAILABLE)
  return false;
if (!n->analyzed
    || n->decl == current_function_decl)
  return false;
return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
838}

840/* Return true if BB is unlikely executed.  */

842static bool
843unlikely_executed_bb_p (basic_block bb)
844{
if (bb->count == profile_count::zero ())
  return true;
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))
  return false;
for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
     !gsi_end_p (gsi); gsi_next (&gsi))
  {
    if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
      return true;
    if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
return false;
  }
return false;
858}

860/* We cannot predict the probabilities of outgoing edges of bb.  Set them
 evenly and hope for the best.  If UNLIKELY_EDGES is not null, distribute
 even probability for all edges not mentioned in the set.  These edges
 are given PROB_VERY_UNLIKELY probability.  Similarly for LIKELY_EDGES,
 if we have exactly one likely edge, make the other edges predicted
 as not probable.  */

867static void
868set_even_probabilities (basic_block bb,
	hash_set<edge> *unlikely_edges = NULLnullptr,
	hash_set<edge_prediction *> *likely_edges = NULLnullptr)
871{
unsigned nedges = 0, unlikely_count = 0;
edge e = NULLnullptr;
edge_iterator ei;
profile_probability all = profile_probability::always ();

FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
  if (e->probability.initialized_p ())
    all -= e->probability;
  else if (!unlikely_executed_edge_p (e))
    {
nedges++;
      if (unlikely_edges != NULLnullptr && unlikely_edges->contains (e))
 {
   all -= profile_probability::very_unlikely ();
   unlikely_count++;
 }
    }

/* Make the distribution even if all edges are unlikely.  */
unsigned likely_count = likely_edges ? likely_edges->elements () : 0;
if (unlikely_count == nedges)
  {
    unlikely_edges = NULLnullptr;
    unlikely_count = 0;
  }

/* If we have one likely edge, then use its probability and distribute
   remaining probabilities as even.  */
if (likely_count == 1)
  {
    FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
if (e->probability.initialized_p ())
 ;
else if (!unlikely_executed_edge_p (e))
 {
   edge_prediction *prediction = *likely_edges->begin ();
   int p = prediction->ep_probability;
   profile_probability prob
     = profile_probability::from_reg_br_prob_base (p);

   if (prediction->ep_edge == e)
     e->probability = prob;
   else if (unlikely_edges != NULLnullptr && unlikely_edges->contains (e))
     e->probability = profile_probability::very_unlikely ();
   else
     {
profile_probability remainder = prob.invert ();
remainder -= profile_probability::very_unlikely ()
  .apply_scale (unlikely_count, 1);
int count = nedges - unlikely_count - 1;
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));

e->probability = remainder.apply_scale (1, count);
     }
 }
else
 e->probability = profile_probability::never ();
  }
else
  {
    /* Make all unlikely edges unlikely and the rest will have even
probability.  */
    unsigned scale = nedges - unlikely_count;
    FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
if (e->probability.initialized_p ())
 ;
else if (!unlikely_executed_edge_p (e))
 {
   if (unlikely_edges != NULLnullptr && unlikely_edges->contains (e))
     e->probability = profile_probability::very_unlikely ();
   else
     e->probability = all.apply_scale (1, scale);
 }
else
 e->probability = profile_probability::never ();
  }
948}

950/* Add REG_BR_PROB note to JUMP with PROB.  */

952void
953add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
954{
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));
add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
957}

959/* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
 note if not already present.  Remove now useless REG_BR_PRED notes.  */

962static void
963combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
964{
rtx prob_note;
rtx *pnote;
rtx note;
int best_probability = PROB_EVEN(10000 / 2);
enum br_predictor best_predictor = END_PREDICTORS;
int combined_probability = REG_BR_PROB_BASE10000 / 2;
int d;
bool first_match = false;
bool found = false;

if (!can_predict_insn_p (insn))
2
←
Calling 'can_predict_insn_p'→
6
←
Returning from 'can_predict_insn_p'→
7
←
Taking false branch→
  {
    set_even_probabilities (bb);
    return;
  }

prob_note = find_reg_note (insn, REG_BR_PROB, 0);
pnote = &REG_NOTES (insn)(((insn)->u.fld[6]).rt_rtx);
if (dump_file)
8
←
Assuming 'dump_file' is non-null→
9
←
Taking true branch→
  fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
    bb->index);

/* We implement "first match" heuristics and use probability guessed
   by predictor with smallest index.  */
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→
  if (REG_NOTE_KIND (note)((enum reg_note) ((machine_mode) (note)->mode)) == REG_BR_PRED)
    {
enum br_predictor predictor = ((enum br_predictor)
		       INTVAL (XEXP (XEXP (note, 0), 0))((((((((note)->u.fld[0]).rt_rtx))->u.fld[0]).rt_rtx))->
u.hwint[0]));
int probability = INTVAL (XEXP (XEXP (note, 0), 1))((((((((note)->u.fld[0]).rt_rtx))->u.fld[1]).rt_rtx))->
u.hwint[0]);

found = true;
if (best_predictor > predictor
   && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH1)
 best_probability = probability, best_predictor = predictor;

d = (combined_probability * probability
    + (REG_BR_PROB_BASE10000 - combined_probability)
    * (REG_BR_PROB_BASE10000 - probability));

/* Use FP math to avoid overflows of 32bit integers.  */
if (d == 0)
 /* If one probability is 0% and one 100%, avoid division by zero.  */
 combined_probability = REG_BR_PROB_BASE10000 / 2;
else
 combined_probability = (((double) combined_probability) * probability
		  * REG_BR_PROB_BASE10000 / d + 0.5);
    }

/* Decide which heuristic to use.  In case we didn't match anything,
   use no_prediction heuristic, in case we did match, use either
   first match or Dempster-Shaffer theory depending on the flags.  */

if (best_predictor10.1
'best_predictor' is equal to END_PREDICTORS
1
'best_predictor' is equal to END_PREDICTORS
1
'best_predictor' is equal to END_PREDICTORS
 != END_PREDICTORS)
11
←
Taking false branch→
  first_match = true;

if (!found11.1
'found' is false
1
'found' is false
1
'found' is false
)
12
←
Taking true branch→
  dump_prediction (dump_file, PRED_NO_PREDICTION,
13
←
Calling 'dump_prediction'→
     combined_probability, bb);
else
  {
    if (!first_match)
dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
	 bb, !first_match ? REASON_NONE : REASON_IGNORED);
    else
dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
	 bb, first_match ? REASON_NONE : REASON_IGNORED);
  }

if (first_match)
  combined_probability = best_probability;
dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);

while (*pnote)
  {
    if (REG_NOTE_KIND (*pnote)((enum reg_note) ((machine_mode) (*pnote)->mode)) == REG_BR_PRED)
{
 enum br_predictor predictor = ((enum br_predictor)
			 INTVAL (XEXP (XEXP (*pnote, 0), 0))((((((((*pnote)->u.fld[0]).rt_rtx))->u.fld[0]).rt_rtx))
->u.hwint[0]));
 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1))((((((((*pnote)->u.fld[0]).rt_rtx))->u.fld[1]).rt_rtx))
->u.hwint[0]);

 dump_prediction (dump_file, predictor, probability, bb,
	   (!first_match || best_predictor == predictor)
	   ? REASON_NONE : REASON_IGNORED);
 *pnote = XEXP (*pnote, 1)(((*pnote)->u.fld[1]).rt_rtx);
}
    else
pnote = &XEXP (*pnote, 1)(((*pnote)->u.fld[1]).rt_rtx);
  }

if (!prob_note)
  {
    profile_probability p
= profile_probability::from_reg_br_prob_base (combined_probability);
    add_reg_br_prob_note (insn, p);

    /* Save the prediction into CFG in case we are seeing non-degenerated
conditional jump.  */
    if (!single_succ_p (bb))
{
 BRANCH_EDGE (bb)((*((bb))->succs)[(0)]->flags & EDGE_FALLTHRU ? (*(
(bb))->succs)[(1)] : (*((bb))->succs)[(0)])->probability = p;
 FALLTHRU_EDGE (bb)((*((bb))->succs)[(0)]->flags & EDGE_FALLTHRU ? (*(
(bb))->succs)[(0)] : (*((bb))->succs)[(1)])->probability
   = BRANCH_EDGE (bb)((*((bb))->succs)[(0)]->flags & EDGE_FALLTHRU ? (*(
(bb))->succs)[(1)] : (*((bb))->succs)[(0)])->probability.invert ();
}
  }
else if (!single_succ_p (bb))
  {
    profile_probability prob = profile_probability::from_reg_br_prob_note
			(XINT (prob_note, 0)(((prob_note)->u.fld[0]).rt_int));

    BRANCH_EDGE (bb)((*((bb))->succs)[(0)]->flags & EDGE_FALLTHRU ? (*(
(bb))->succs)[(1)] : (*((bb))->succs)[(0)])->probability = prob;
    FALLTHRU_EDGE (bb)((*((bb))->succs)[(0)]->flags & EDGE_FALLTHRU ? (*(
(bb))->succs)[(0)] : (*((bb))->succs)[(1)])->probability = prob.invert ();
  }
else
  single_succ_edge (bb)->probability = profile_probability::always ();
1080}

1082/* Edge prediction hash traits.  */

1084struct predictor_hash: pointer_hash <edge_prediction>
1085{

static inline hashval_t hash (const edge_prediction *);
static inline bool equal (const edge_prediction *, const edge_prediction *);
1089};

1091/* Calculate hash value of an edge prediction P based on predictor and
 normalized probability.  */

1094inline hashval_t
1095predictor_hash::hash (const edge_prediction *p)
1096{
inchash::hash hstate;
hstate.add_int (p->ep_predictor);

int prob = p->ep_probability;
if (prob > REG_BR_PROB_BASE10000 / 2)
  prob = REG_BR_PROB_BASE10000 - prob;

hstate.add_int (prob);

return hstate.end ();
1107}

1109/* Return true whether edge predictions P1 and P2 use the same predictor and
 have equal (or opposed probability).  */

1112inline bool
1113predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1114{
return (p1->ep_predictor == p2->ep_predictor
 && (p1->ep_probability == p2->ep_probability
     || p1->ep_probability == REG_BR_PROB_BASE10000 - p2->ep_probability));
1118}

1120struct predictor_hash_traits: predictor_hash,
typed_noop_remove <edge_prediction *> {};

1123/* Return true if edge prediction P is not in DATA hash set.  */

1125static bool
1126not_removed_prediction_p (edge_prediction *p, void *data)
1127{
hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
return !remove->contains (p);
1130}

1132/* Prune predictions for a basic block BB.  Currently we do following
 clean-up steps:

 1) remove duplicate prediction that is guessed with the same probability
    (different than 1/2) to both edge
 2) remove duplicates for a prediction that belongs with the same probability
    to a single edge

*/

1142static void
1143prune_predictions_for_bb (basic_block bb)
1144{
edge_prediction **preds = bb_predictions->get (bb);

if (preds)
  {
    hash_table <predictor_hash_traits> s (13);
    hash_set <edge_prediction *> remove;

    /* Step 1: identify predictors that should be removed.  */
    for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
{
 edge_prediction *existing = s.find (pred);
 if (existing)
   {
     if (pred->ep_edge == existing->ep_edge
  && pred->ep_probability == existing->ep_probability)
{
  /* Remove a duplicate predictor.  */
  dump_prediction (dump_file, pred->ep_predictor,
		   pred->ep_probability, bb,
		   REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);

  remove.add (pred);
}
     else if (pred->ep_edge != existing->ep_edge
       && pred->ep_probability == existing->ep_probability
       && pred->ep_probability != REG_BR_PROB_BASE10000 / 2)
{
  /* Remove both predictors as they predict the same
     for both edges.  */
  dump_prediction (dump_file, existing->ep_predictor,
		   pred->ep_probability, bb,
		   REASON_EDGE_PAIR_DUPLICATE,
		   existing->ep_edge);
  dump_prediction (dump_file, pred->ep_predictor,
		   pred->ep_probability, bb,
		   REASON_EDGE_PAIR_DUPLICATE,
		   pred->ep_edge);

  remove.add (existing);
  remove.add (pred);
}
   }

 edge_prediction **slot2 = s.find_slot (pred, INSERT);
 *slot2 = pred;
}

    /* Step 2: Remove predictors.  */
    filter_predictions (preds, not_removed_prediction_p, &remove);
  }
1195}

1197/* Combine predictions into single probability and store them into CFG.
 Remove now useless prediction entries.
 If DRY_RUN is set, only produce dumps and do not modify profile.  */

1201static void
1202combine_predictions_for_bb (basic_block bb, bool dry_run)
1203{
int best_probability = PROB_EVEN(10000 / 2);
enum br_predictor best_predictor = END_PREDICTORS;
int combined_probability = REG_BR_PROB_BASE10000 / 2;
int d;
bool first_match = false;
bool found = false;
struct edge_prediction *pred;
int nedges = 0;
edge e, first = NULLnullptr, second = NULLnullptr;
edge_iterator ei;
int nzero = 0;
int nunknown = 0;

FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
  {
    if (!unlikely_executed_edge_p (e))
      {
 nedges ++;
 if (first && !second)
   second = e;
 if (!first)
   first = e;
      }
    else if (!e->probability.initialized_p ())
      e->probability = profile_probability::never ();
   if (!e->probability.initialized_p ())
      nunknown++;
   else if (e->probability == profile_probability::never ())
nzero++;
  }

/* When there is no successor or only one choice, prediction is easy.

   When we have a basic block with more than 2 successors, the situation
   is more complicated as DS theory cannot be used literally.
   More precisely, let's assume we predicted edge e1 with probability p1,
   thus: m1({b1}) = p1.  As we're going to combine more than 2 edges, we
   need to find probability of e.g. m1({b2}), which we don't know.
   The only approximation is to equally distribute 1-p1 to all edges
   different from b1.

   According to numbers we've got from SPEC2006 benchark, there's only
   one interesting reliable predictor (noreturn call), which can be
   handled with a bit easier approach.  */
if (nedges != 2)
  {
    hash_set<edge> unlikely_edges (4);
    hash_set<edge_prediction *> likely_edges (4);

    /* Identify all edges that have a probability close to very unlikely.
Doing the approach for very unlikely doesn't worth for doing as
there's no such probability in SPEC2006 benchmark.  */
    edge_prediction **preds = bb_predictions->get (bb);
    if (preds)
for (pred = *preds; pred; pred = pred->ep_next)
 {
   if (pred->ep_probability <= PROB_VERY_UNLIKELY(10000 / 2000 - 1)
|| pred->ep_predictor == PRED_COLD_LABEL)
     unlikely_edges.add (pred->ep_edge);
   else if (pred->ep_probability >= PROB_VERY_LIKELY(10000 - (10000 / 2000 - 1))
     || pred->ep_predictor == PRED_BUILTIN_EXPECT
     || pred->ep_predictor == PRED_HOT_LABEL)
     likely_edges.add (pred);
 }

    /* It can happen that an edge is both in likely_edges and unlikely_edges.
Clear both sets in that situation.  */
    for (hash_set<edge_prediction *>::iterator it = likely_edges.begin ();
  it != likely_edges.end (); ++it)
if (unlikely_edges.contains ((*it)->ep_edge))
 {
   likely_edges.empty ();
   unlikely_edges.empty ();
   break;
 }

    if (!dry_run)
set_even_probabilities (bb, &unlikely_edges, &likely_edges);
    clear_bb_predictions (bb);
    if (dump_file)
{
 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
 if (unlikely_edges.is_empty ())
   fprintf (dump_file,
     "%i edges in bb %i predicted to even probabilities\n",
     nedges, bb->index);
 else
   {
     fprintf (dump_file,
       "%i edges in bb %i predicted with some unlikely edges\n",
       nedges, bb->index);
     FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
if (!unlikely_executed_edge_p (e))
  dump_prediction (dump_file, PRED_COMBINED,
   e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
   }
}
    return;
  }

if (dump_file)
  fprintf (dump_file, "Predictions for bb %i\n", bb->index);

prune_predictions_for_bb (bb);

edge_prediction **preds = bb_predictions->get (bb);

if (preds)
  {
    /* We implement "first match" heuristics and use probability guessed
by predictor with smallest index.  */
    for (pred = *preds; pred; pred = pred->ep_next)
{
 enum br_predictor predictor = pred->ep_predictor;
 int probability = pred->ep_probability;

 if (pred->ep_edge != first)
   probability = REG_BR_PROB_BASE10000 - probability;

 found = true;
 /* First match heuristics would be widly confused if we predicted
    both directions.  */
 if (best_predictor > predictor
   && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH1)
   {
            struct edge_prediction *pred2;
     int prob = probability;

     for (pred2 = (struct edge_prediction *) *preds;
   pred2; pred2 = pred2->ep_next)
      if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
        {
   int probability2 = pred2->ep_probability;

   if (pred2->ep_edge != first)
     probability2 = REG_BR_PROB_BASE10000 - probability2;

   if ((probability < REG_BR_PROB_BASE10000 / 2) !=
       (probability2 < REG_BR_PROB_BASE10000 / 2))
     break;

   /* If the same predictor later gave better result, go for it! */
   if ((probability >= REG_BR_PROB_BASE10000 / 2 && (probability2 > probability))
       || (probability <= REG_BR_PROB_BASE10000 / 2 && (probability2 < probability)))
     prob = probability2;
 }
     if (!pred2)
       best_probability = prob, best_predictor = predictor;
   }

 d = (combined_probability * probability
      + (REG_BR_PROB_BASE10000 - combined_probability)
      * (REG_BR_PROB_BASE10000 - probability));

 /* Use FP math to avoid overflows of 32bit integers.  */
 if (d == 0)
   /* If one probability is 0% and one 100%, avoid division by zero.  */
   combined_probability = REG_BR_PROB_BASE10000 / 2;
 else
   combined_probability = (((double) combined_probability)
		    * probability
    		    * REG_BR_PROB_BASE10000 / d + 0.5);
}
  }

/* Decide which heuristic to use.  In case we didn't match anything,
   use no_prediction heuristic, in case we did match, use either
   first match or Dempster-Shaffer theory depending on the flags.  */

if (best_predictor != END_PREDICTORS)
  first_match = true;

if (!found)
  dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
else
  {
    if (!first_match)
dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
	 !first_match ? REASON_NONE : REASON_IGNORED);
    else
dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
	 first_match ? REASON_NONE : REASON_IGNORED);
  }

if (first_match)
  combined_probability = best_probability;
dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);

if (preds)
  {
    for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
{
 enum br_predictor predictor = pred->ep_predictor;
 int probability = pred->ep_probability;

 dump_prediction (dump_file, predictor, probability, bb,
	   (!first_match || best_predictor == predictor)
	   ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
}
  }
clear_bb_predictions (bb);


/* If we have only one successor which is unknown, we can compute missing
   probability.  */
if (nunknown == 1)
  {
    profile_probability prob = profile_probability::always ();
    edge missing = NULLnullptr;

    FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
if (e->probability.initialized_p ())
 prob -= e->probability;
else if (missing == NULLnullptr)
 missing = e;
else
 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/predict.c"
, 1420, __FUNCTION__));
     missing->probability = prob;
  }
/* If nothing is unknown, we have nothing to update.  */
else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs)vec_safe_length (bb->succs))
  ;
else if (!dry_run)
  {
    first->probability
= profile_probability::from_reg_br_prob_base (combined_probability);
    second->probability = first->probability.invert ();
  }
1432}

1434/* Check if T1 and T2 satisfy the IV_COMPARE condition.
 Return the SSA_NAME if the condition satisfies, NULL otherwise.

 T1 and T2 should be one of the following cases:
   1. T1 is SSA_NAME, T2 is NULL
   2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
   3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4]  */

1442static tree
1443strips_small_constant (tree t1, tree t2)
1444{
tree ret = NULLnullptr;
int value = 0;

if (!t1)
  return NULLnullptr;
else if (TREE_CODE (t1)((enum tree_code) (t1)->base.code) == SSA_NAME)
  ret = t1;
else if (tree_fits_shwi_p (t1))
  value = tree_to_shwi (t1);
else
  return NULLnullptr;

if (!t2)
  return ret;
else if (tree_fits_shwi_p (t2))
  value = tree_to_shwi (t2);
else if (TREE_CODE (t2)((enum tree_code) (t2)->base.code) == SSA_NAME)
  {
    if (ret)
      return NULLnullptr;
    else
      ret = t2;
  }

if (value <= 4 && value >= -4)
  return ret;
else
  return NULLnullptr;
1473}

1475/* Return the SSA_NAME in T or T's operands.
 Return NULL if SSA_NAME cannot be found.  */

1478static tree
1479get_base_value (tree t)
1480{
if (TREE_CODE (t)((enum tree_code) (t)->base.code) == SSA_NAME)
  return t;

if (!BINARY_CLASS_P (t)(tree_code_type[(int) (((enum tree_code) (t)->base.code))]
 == tcc_binary))
  return NULLnullptr;

switch (TREE_OPERAND_LENGTH (t)tree_operand_length (t))
  {
  case 1:
    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);
  case 2:
    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__))))),
		    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__))))));
  default:
    return NULLnullptr;
  }
1497}

1499/* Check the compare STMT in LOOP. If it compares an induction
 variable to a loop invariant, return true, and save
 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
 Otherwise return false and set LOOP_INVAIANT to NULL.  */

1504static bool
1505is_comparison_with_loop_invariant_p (gcond *stmt, class loop *loop,
		     tree *loop_invariant,
		     enum tree_code *compare_code,
		     tree *loop_step,
		     tree *loop_iv_base)
1510{
tree op0, op1, bound, base;
affine_iv iv0, iv1;
enum tree_code code;
tree step;

code = gimple_cond_code (stmt);
*loop_invariant = NULLnullptr;

switch (code)
  {
  case GT_EXPR:
  case GE_EXPR:
  case NE_EXPR:
  case LT_EXPR:
  case LE_EXPR:
  case EQ_EXPR:
    break;

  default:
    return false;
  }

op0 = gimple_cond_lhs (stmt);
op1 = gimple_cond_rhs (stmt);

if ((TREE_CODE (op0)((enum tree_code) (op0)->base.code) != SSA_NAME && TREE_CODE (op0)((enum tree_code) (op0)->base.code) != INTEGER_CST) 
     || (TREE_CODE (op1)((enum tree_code) (op1)->base.code) != SSA_NAME && TREE_CODE (op1)((enum tree_code) (op1)->base.code) != INTEGER_CST))
  return false;
if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
  return false;
if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
  return false;
if (TREE_CODE (iv0.step)((enum tree_code) (iv0.step)->base.code) != INTEGER_CST
    || TREE_CODE (iv1.step)((enum tree_code) (iv1.step)->base.code) != INTEGER_CST)
  return false;
if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
    || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
  return false;

if (integer_zerop (iv0.step))
  {
    if (code != NE_EXPR && code != EQ_EXPR)
code = invert_tree_comparison (code, false);
    bound = iv0.base;
    base = iv1.base;
    if (tree_fits_shwi_p (iv1.step))
step = iv1.step;
    else
return false;
  }
else
  {
    bound = iv1.base;
    base = iv0.base;
    if (tree_fits_shwi_p (iv0.step))
step = iv0.step;
    else
return false;
  }

if (TREE_CODE (bound)((enum tree_code) (bound)->base.code) != INTEGER_CST)
  bound = get_base_value (bound);
if (!bound)
  return false;
if (TREE_CODE (base)((enum tree_code) (base)->base.code) != INTEGER_CST)
  base = get_base_value (base);
if (!base)
  return false;

*loop_invariant = bound;
*compare_code = code;
*loop_step = step;
*loop_iv_base = base;
return true;
1585}

1587/* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent.  */

1589static bool
1590expr_coherent_p (tree t1, tree t2)
1591{
gimple *stmt;
tree ssa_name_1 = NULLnullptr;
tree ssa_name_2 = NULLnullptr;

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));
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));

if (t1 == t2)
  return true;

if (TREE_CODE (t1)((enum tree_code) (t1)->base.code) == INTEGER_CST && TREE_CODE (t2)((enum tree_code) (t2)->base.code) == INTEGER_CST)
  return true;
if (TREE_CODE (t1)((enum tree_code) (t1)->base.code) == INTEGER_CST || TREE_CODE (t2)((enum tree_code) (t2)->base.code) == INTEGER_CST)
  return false;

/* Check to see if t1 is expressed/defined with t2.  */
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;
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));
if (is_gimple_assign (stmt))
  {
    ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE)single_ssa_tree_operand (stmt, 0x01);
    if (ssa_name_1 && ssa_name_1 == t2)
return true;
  }

/* Check to see if t2 is expressed/defined with t1.  */
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;
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));
if (is_gimple_assign (stmt))
  {
    ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE)single_ssa_tree_operand (stmt, 0x01);
    if (ssa_name_2 && ssa_name_2 == t1)
return true;
  }

/* Compare if t1 and t2's def_stmts are identical.  */
if (ssa_name_2 != NULLnullptr && ssa_name_1 == ssa_name_2)
  return true;
else
  return false;
1632}

1634/* Return true if E is predicted by one of loop heuristics.  */

1636static bool
1637predicted_by_loop_heuristics_p (basic_block bb)
1638{
struct edge_prediction *i;
edge_prediction **preds = bb_predictions->get (bb);

if (!preds)
  return false;

for (i = *preds; i; i = i->ep_next)
  if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
|| i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
|| i->ep_predictor == PRED_LOOP_ITERATIONS
|| i->ep_predictor == PRED_LOOP_EXIT
|| i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
|| i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
    return true;
return false;
1654}

1656/* Predict branch probability of BB when BB contains a branch that compares
 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.

 E.g.
   for (int i = 0; i < bound; i++) {
     if (i < bound - 2)
computation_1();
     else
computation_2();
   }

In this loop, we will predict the branch inside the loop to be taken.  */

1670static void
1671predict_iv_comparison (class loop *loop, basic_block bb,
       tree loop_bound_var,
       tree loop_iv_base_var,
       enum tree_code loop_bound_code,
       int loop_bound_step)
1676{
gimple *stmt;
tree compare_var, compare_base;
enum tree_code compare_code;
tree compare_step_var;
edge then_edge;
edge_iterator ei;

if (predicted_by_loop_heuristics_p (bb))
  return;

stmt = last_stmt (bb);
if (!stmt || gimple_code (stmt) != GIMPLE_COND)
  return;
if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt),
			    loop, &compare_var,
			    &compare_code,
			    &compare_step_var,
			    &compare_base))
  return;

/* Find the taken edge.  */
FOR_EACH_EDGE (then_edge, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(then_edge)); ei_next (&(ei)))
  if (then_edge->flags & EDGE_TRUE_VALUE)
    break;

/* When comparing an IV to a loop invariant, NE is more likely to be
   taken while EQ is more likely to be not-taken.  */
if (compare_code == NE_EXPR)
  {
    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
    return;
  }
else if (compare_code == EQ_EXPR)
  {
    predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
    return;
  }

if (!expr_coherent_p (loop_iv_base_var, compare_base))
  return;

/* If loop bound, base and compare bound are all constants, we can
   calculate the probability directly.  */
if (tree_fits_shwi_p (loop_bound_var)
    && tree_fits_shwi_p (compare_var)
    && tree_fits_shwi_p (compare_base))
  {
    int probability;
    wi::overflow_type overflow;
    bool overall_overflow = false;
    widest_int compare_count, tem;

    /* (loop_bound - base) / compare_step */
    tem = wi::sub (wi::to_widest (loop_bound_var),
     wi::to_widest (compare_base), SIGNED, &overflow);
    overall_overflow |= overflow;
    widest_int loop_count = wi::div_trunc (tem,
			     wi::to_widest (compare_step_var),
			     SIGNED, &overflow);
    overall_overflow |= overflow;

    if (!wi::neg_p (wi::to_widest (compare_step_var))
        ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
{
 /* (loop_bound - compare_bound) / compare_step */
 tem = wi::sub (wi::to_widest (loop_bound_var),
	 wi::to_widest (compare_var), SIGNED, &overflow);
 overall_overflow |= overflow;
 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
			 SIGNED, &overflow);
 overall_overflow |= overflow;
}
    else
      {
 /* (compare_bound - base) / compare_step */
 tem = wi::sub (wi::to_widest (compare_var),
	 wi::to_widest (compare_base), SIGNED, &overflow);
 overall_overflow |= overflow;
        compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
			 SIGNED, &overflow);
 overall_overflow |= overflow;
}
    if (compare_code == LE_EXPR || compare_code == GE_EXPR)
++compare_count;
    if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
++loop_count;
    if (wi::neg_p (compare_count))
      compare_count = 0;
    if (wi::neg_p (loop_count))
      loop_count = 0;
    if (loop_count == 0)
probability = 0;
    else if (wi::cmps (compare_count, loop_count) == 1)
probability = REG_BR_PROB_BASE10000;
    else
      {
 tem = compare_count * REG_BR_PROB_BASE10000;
 tem = wi::udiv_trunc (tem, loop_count);
 probability = tem.to_uhwi ();
}

    /* FIXME: The branch prediction seems broken. It has only 20% hitrate.  */
    if (!overall_overflow)
      predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);

    return;
  }

if (expr_coherent_p (loop_bound_var, compare_var))
  {
    if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
    else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
      && (compare_code == GT_EXPR || compare_code == GE_EXPR))
predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
    else if (loop_bound_code == NE_EXPR)
{
 /* If the loop backedge condition is "(i != bound)", we do
    the comparison based on the step of IV:
    * step < 0 : backedge condition is like (i > bound)
    * step > 0 : backedge condition is like (i < bound)  */
 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));
 if (loop_bound_step > 0
     && (compare_code == LT_EXPR
  || compare_code == LE_EXPR))
   predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
 else if (loop_bound_step < 0
   && (compare_code == GT_EXPR
       || compare_code == GE_EXPR))
   predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
 else
   predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
}
    else
/* The branch is predicted not-taken if loop_bound_code is
  opposite with compare_code.  */
predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
  }
else if (expr_coherent_p (loop_iv_base_var, compare_var))
  {
    /* For cases like:
  for (i = s; i < h; i++)
    if (i > s + 2) ....
The branch should be predicted taken.  */
    if (loop_bound_step > 0
 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
    else if (loop_bound_step < 0
      && (compare_code == LT_EXPR || compare_code == LE_EXPR))
predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
    else
predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
  }
1831}

1833/* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
 exits are resulted from short-circuit conditions that will generate an
 if_tmp. E.g.:

 if (foo() || global > 10)
   break;

 This will be translated into:

 BB3:
   loop header...
 BB4:
   if foo() goto BB6 else goto BB5
 BB5:
   if global > 10 goto BB6 else goto BB7
 BB6:
   goto BB7
 BB7:
   iftmp = (PHI 0(BB5), 1(BB6))
   if iftmp == 1 goto BB8 else goto BB3
 BB8:
   outside of the loop...

 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
 exits. This function takes BB7->BB8 as input, and finds out the extra loop
 exits to predict them using PRED_LOOP_EXTRA_EXIT.  */

1861static void
1862predict_extra_loop_exits (edge exit_edge)
1863{
unsigned i;
bool check_value_one;
gimple *lhs_def_stmt;
gphi *phi_stmt;
tree cmp_rhs, cmp_lhs;
gimple *last;
gcond *cmp_stmt;

last = last_stmt (exit_edge->src);
if (!last)
  return;
cmp_stmt = dyn_cast <gcond *> (last);
if (!cmp_stmt)
  return;

cmp_rhs = gimple_cond_rhs (cmp_stmt);
cmp_lhs = gimple_cond_lhs (cmp_stmt);
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)
    || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
  return;
if (TREE_CODE (cmp_lhs)((enum tree_code) (cmp_lhs)->base.code) != SSA_NAME)
  return;

/* If check_value_one is true, only the phi_args with value '1' will lead
   to loop exit. Otherwise, only the phi_args with value '0' will lead to
   loop exit.  */
check_value_one = (((integer_onep (cmp_rhs))
    ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
    ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));

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;
if (!lhs_def_stmt)
  return;

phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
if (!phi_stmt)
  return;

for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
  {
    edge e1;
    edge_iterator ei;
    tree val = gimple_phi_arg_def (phi_stmt, i);
    edge e = gimple_phi_arg_edge (phi_stmt, i);

    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)))
continue;
    if ((check_value_one ^ integer_onep (val)) == 1)
continue;
    if (EDGE_COUNT (e->src->succs)vec_safe_length (e->src->succs) != 1)
{
 predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
 continue;
}

    FOR_EACH_EDGE (e1, ei, e->src->preds)for ((ei) = ei_start_1 (&((e->src->preds))); ei_cond
 ((ei), &(e1)); ei_next (&(ei)))
predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
  }
1922}


1925/* Predict edge probabilities by exploiting loop structure.  */

1927static void
1928predict_loops (void)
1929{
class loop *loop;
basic_block bb;
hash_set <class loop *> with_recursion(10);

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)
  {
    gimple_stmt_iterator gsi;
    tree decl;

    for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
if (is_gimple_call (gsi_stmt (gsi))
   && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULLnullptr
   && recursive_call_p (current_function_decl, decl))
 {
   loop = bb->loop_father;
   while (loop && !with_recursion.add (loop))
     loop = loop_outer (loop);
 }
  }

/* Try to predict out blocks in a loop that are not part of a
   natural loop.  */
FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)for (loop_iterator li((cfun + 0), &(loop), LI_FROM_INNERMOST
); (loop); (loop) = li.next ())
  {
    basic_block bb, *bbs;
    unsigned j, n_exits = 0;
    class tree_niter_desc niter_desc;
    edge ex;
    class nb_iter_bound *nb_iter;
    enum tree_code loop_bound_code = ERROR_MARK;
    tree loop_bound_step = NULLnullptr;
    tree loop_bound_var = NULLnullptr;
    tree loop_iv_base = NULLnullptr;
    gcond *stmt = NULLnullptr;
    bool recursion = with_recursion.contains (loop);

    auto_vec<edge> exits = get_loop_exit_edges (loop);
    FOR_EACH_VEC_ELT (exits, j, ex)for (j = 0; (exits).iterate ((j), &(ex)); ++(j))
if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
 n_exits ++;
    if (!n_exits)
continue;

    if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
 loop->num, recursion ? " (with recursion)":"", n_exits);
    if (dump_file && (dump_flags & TDF_DETAILS)
 && max_loop_iterations_int (loop) >= 0)
{
 fprintf (dump_file,
   "Loop %d iterates at most %i times.\n", loop->num,
   (int)max_loop_iterations_int (loop));
}
    if (dump_file && (dump_flags & TDF_DETAILS)
 && likely_max_loop_iterations_int (loop) >= 0)
{
 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
   loop->num, (int)likely_max_loop_iterations_int (loop));
}

    FOR_EACH_VEC_ELT (exits, j, ex)for (j = 0; (exits).iterate ((j), &(ex)); ++(j))
{
 tree niter = NULLnullptr;
 HOST_WIDE_INTlong nitercst;
 int max = param_max_predicted_iterationsglobal_options.x_param_max_predicted_iterations;
 int probability;
 enum br_predictor predictor;
 widest_int nit;

 if (unlikely_executed_edge_p (ex)
     || (ex->flags & EDGE_ABNORMAL_CALL))
   continue;
 /* Loop heuristics do not expect exit conditional to be inside
    inner loop.  We predict from innermost to outermost loop.  */
 if (predicted_by_loop_heuristics_p (ex->src))
   {
     if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Skipping exit %i->%i because "
	 "it is already predicted.\n",
	 ex->src->index, ex->dest->index);
     continue;
   }
 predict_extra_loop_exits (ex);

 if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
   niter = niter_desc.niter;
 if (!niter || TREE_CODE (niter_desc.niter)((enum tree_code) (niter_desc.niter)->base.code) != INTEGER_CST)
   niter = loop_niter_by_eval (loop, ex);
 if (dump_file && (dump_flags & TDF_DETAILS)
     && TREE_CODE (niter)((enum tree_code) (niter)->base.code) == INTEGER_CST)
   {
     fprintf (dump_file, "Exit %i->%i %d iterates ",
       ex->src->index, ex->dest->index,
       loop->num);
     print_generic_expr (dump_file, niter, TDF_SLIM);
     fprintf (dump_file, " times.\n");
   }

 if (TREE_CODE (niter)((enum tree_code) (niter)->base.code) == INTEGER_CST)
   {
     if (tree_fits_uhwi_p (niter)
  && max
  && compare_tree_int (niter, max - 1) == -1)
nitercst = tree_to_uhwi (niter) + 1;
     else
nitercst = max;
     predictor = PRED_LOOP_ITERATIONS;
   }
 /* If we have just one exit and we can derive some information about
    the number of iterations of the loop from the statements inside
    the loop, use it to predict this exit.  */
 else if (n_exits == 1
   && estimated_stmt_executions (loop, &nit))
   {
     if (wi::gtu_p (nit, max))
nitercst = max;
     else
nitercst = nit.to_shwi ();
     predictor = PRED_LOOP_ITERATIONS_GUESSED;
   }
 /* If we have likely upper bound, trust it for very small iteration
    counts.  Such loops would otherwise get mispredicted by standard
    LOOP_EXIT heuristics.  */
 else if (n_exits == 1
   && likely_max_stmt_executions (loop, &nit)
   && wi::ltu_p (nit,
		 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))
		       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))
			 - 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))
				 [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))
				  ? 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))
				  : 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))))
   {
     nitercst = nit.to_shwi ();
     predictor = PRED_LOOP_ITERATIONS_MAX;
   }
 else
   {
     if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Nothing known about exit %i->%i.\n",
	 ex->src->index, ex->dest->index);
     continue;
   }

 if (dump_file && (dump_flags & TDF_DETAILS))
   fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
     (int)nitercst, predictor_info[predictor].name);
 /* If the prediction for number of iterations is zero, do not
    predict the exit edges.  */
 if (nitercst == 0)
   continue;

 probability = RDIV (REG_BR_PROB_BASE, nitercst)(((10000) + (nitercst) / 2) / (nitercst));
 predict_edge (ex, predictor, probability);
}

    /* Find information about loop bound variables.  */
    for (nb_iter = loop->bounds; nb_iter;
  nb_iter = nb_iter->next)
if (nb_iter->stmt
   && gimple_code (nb_iter->stmt) == GIMPLE_COND)
 {
   stmt = as_a <gcond *> (nb_iter->stmt);
   break;
 }
    if (!stmt && last_stmt (loop->header)
 && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
stmt = as_a <gcond *> (last_stmt (loop->header));
    if (stmt)
is_comparison_with_loop_invariant_p (stmt, loop,
			     &loop_bound_var,
			     &loop_bound_code,
			     &loop_bound_step,
			     &loop_iv_base);

    bbs = get_loop_body (loop);

    for (j = 0; j < loop->num_nodes; j++)
{
 edge e;
 edge_iterator ei;

 bb = bbs[j];

 /* Bypass loop heuristics on continue statement.  These
    statements construct loops via "non-loop" constructs
    in the source language and are better to be handled
    separately.  */
 if (predicted_by_p (bb, PRED_CONTINUE))
   {
     if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "BB %i predicted by continue.\n",
	 bb->index);
     continue;
   }

 /* If we already used more reliable loop exit predictors, do not
    bother with PRED_LOOP_EXIT.  */
 if (!predicted_by_loop_heuristics_p (bb))
   {
     /* For loop with many exits we don't want to predict all exits
        with the pretty large probability, because if all exits are
 considered in row, the loop would be predicted to iterate
 almost never.  The code to divide probability by number of
 exits is very rough.  It should compute the number of exits
 taken in each patch through function (not the overall number
 of exits that might be a lot higher for loops with wide switch
 statements in them) and compute n-th square root.

 We limit the minimal probability by 2% to avoid
 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
 as this was causing regression in perl benchmark containing such
 a wide loop.  */

     int probability = ((REG_BR_PROB_BASE10000
                  - predictor_info
		     [recursion
		      ? PRED_LOOP_EXIT_WITH_RECURSION
		      : PRED_LOOP_EXIT].hitrate)
		 / n_exits);
     if (probability < HITRATE (2)((int) ((2) * 10000 + 50) / 100))
probability = HITRATE (2)((int) ((2) * 10000 + 50) / 100);
     FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
if (e->dest->index < NUM_FIXED_BLOCKS(2)
    || !flow_bb_inside_loop_p (loop, e->dest))
  {
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file,
	       "Predicting exit %i->%i with prob %i.\n",
	       e->src->index, e->dest->index, probability);
    predict_edge (e,
		  recursion ? PRED_LOOP_EXIT_WITH_RECURSION
	          : PRED_LOOP_EXIT, probability);
  }
   }
 if (loop_bound_var)
   predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
		   loop_bound_code,
		   tree_to_shwi (loop_bound_step));
}

    /* In the following code
for (loop1)
  if (cond)
    for (loop2)
      body;
guess that cond is unlikely.  */
    if (loop_outer (loop)->num)
{
 basic_block bb = NULLnullptr;
 edge preheader_edge = loop_preheader_edge (loop);

 if (single_pred_p (preheader_edge->src)
     && single_succ_p (preheader_edge->src))
   preheader_edge = single_pred_edge (preheader_edge->src);

 gimple *stmt = last_stmt (preheader_edge->src);
 /* Pattern match fortran loop preheader:
    _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
    _17 = (logical(kind=4)) _16;
    if (_17 != 0)
      goto <bb 11>;
    else
      goto <bb 13>;

    Loop guard branch prediction says nothing about duplicated loop
    headers produced by fortran frontend and in this case we want
    to predict paths leading to this preheader.  */

 if (stmt
     && gimple_code (stmt) == GIMPLE_COND
     && gimple_cond_code (stmt) == NE_EXPR
     && TREE_CODE (gimple_cond_lhs (stmt))((enum tree_code) (gimple_cond_lhs (stmt))->base.code) == SSA_NAME
     && integer_zerop (gimple_cond_rhs (stmt)))
    {
      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;
      if (gimple_code (call_stmt) == GIMPLE_ASSIGN
   && 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)
   && TREE_CODE (gimple_assign_rhs1 (call_stmt))((enum tree_code) (gimple_assign_rhs1 (call_stmt))->base.code
) == SSA_NAME)
 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;
      if (gimple_call_internal_p (call_stmt, IFN_BUILTIN_EXPECT)
   && TREE_CODE (gimple_call_arg (call_stmt, 2))((enum tree_code) (gimple_call_arg (call_stmt, 2))->base.code
) == INTEGER_CST
   && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
   && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
	== PRED_FORTRAN_LOOP_PREHEADER)
 bb = preheader_edge->src;
    }
 if (!bb)
   {
     if (!dominated_by_p (CDI_DOMINATORS,
		   loop_outer (loop)->latch, loop->header))
predict_paths_leading_to_edge (loop_preheader_edge (loop),
			       recursion
			       ? PRED_LOOP_GUARD_WITH_RECURSION
			       : PRED_LOOP_GUARD,
			       NOT_TAKEN,
			       loop_outer (loop));
   }
 else
   {
     if (!dominated_by_p (CDI_DOMINATORS,
		   loop_outer (loop)->latch, bb))
predict_paths_leading_to (bb,
			  recursion
			  ? PRED_LOOP_GUARD_WITH_RECURSION
			  : PRED_LOOP_GUARD,
			  NOT_TAKEN,
			  loop_outer (loop));
   }
}

    /* Free basic blocks from get_loop_body.  */
    free (bbs);
  }
2244}

2246/* Attempt to predict probabilities of BB outgoing edges using local
 properties.  */
2248static void
2249bb_estimate_probability_locally (basic_block bb)
2250{
rtx_insn *last_insn = BB_END (bb)(bb)->il.x.rtl->end_;
rtx cond;

if (! can_predict_insn_p (last_insn))
  return;
cond = get_condition (last_insn, NULLnullptr, false, false);
if (! cond)
  return;

/* Try "pointer heuristic."
   A comparison ptr == 0 is predicted as false.
   Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
if (COMPARISON_P (cond)(((rtx_class[(int) (((enum rtx_code) (cond)->code))]) &
 (~1)) == (RTX_COMPARE & (~1)))
    && ((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))
 || (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))))
  {
    if (GET_CODE (cond)((enum rtx_code) (cond)->code) == EQ)
predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
    else if (GET_CODE (cond)((enum rtx_code) (cond)->code) == NE)
predict_insn_def (last_insn, PRED_POINTER, TAKEN);
  }
else

/* Try "opcode heuristic."
   EQ tests are usually false and NE tests are usually true. Also,
   most quantities are positive, so we can make the appropriate guesses
   about signed comparisons against zero.  */
  switch (GET_CODE (cond)((enum rtx_code) (cond)->code))
    {
    case CONST_INT:
/* Unconditional branch.  */
predict_insn_def (last_insn, PRED_UNCONDITIONAL,
	  cond == const0_rtx(const_int_rtx[64]) ? NOT_TAKEN : TAKEN);
break;

    case EQ:
    case UNEQ:
/* Floating point comparisons appears to behave in a very
  unpredictable way because of special role of = tests in
  FP code.  */
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
))
 ;
/* Comparisons with 0 are often used for booleans and there is
  nothing useful to predict about them.  */
else if (XEXP (cond, 1)(((cond)->u.fld[1]).rt_rtx) == const0_rtx(const_int_rtx[64])
 || XEXP (cond, 0)(((cond)->u.fld[0]).rt_rtx) == const0_rtx(const_int_rtx[64]))
 ;
else
 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
break;

    case NE:
    case LTGT:
/* Floating point comparisons appears to behave in a very
  unpredictable way because of special role of = tests in
  FP code.  */
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
))
 ;
/* Comparisons with 0 are often used for booleans and there is
  nothing useful to predict about them.  */
else if (XEXP (cond, 1)(((cond)->u.fld[1]).rt_rtx) == const0_rtx(const_int_rtx[64])
 || XEXP (cond, 0)(((cond)->u.fld[0]).rt_rtx) == const0_rtx(const_int_rtx[64]))
 ;
else
 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
break;

    case ORDERED:
predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
break;

    case UNORDERED:
predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
break;

    case LE:
    case LT:
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])
   || XEXP (cond, 1)(((cond)->u.fld[1]).rt_rtx) == constm1_rtx(const_int_rtx[64 -1]))
 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
break;

    case GE:
    case GT:
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])
   || XEXP (cond, 1)(((cond)->u.fld[1]).rt_rtx) == constm1_rtx(const_int_rtx[64 -1]))
 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
break;

    default:
break;
    }
2343}

2345/* Set edge->probability for each successor edge of BB.  */
2346void
2347guess_outgoing_edge_probabilities (basic_block bb)
2348{
bb_estimate_probability_locally (bb);
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,
		 HOST_WIDE_INTlong *probability);

2356/* Helper function for expr_expected_value.  */

2358static tree
2359expr_expected_value_1 (tree type, tree op0, enum tree_code code,
       tree op1, bitmap visited, enum br_predictor *predictor,
       HOST_WIDE_INTlong *probability)
2362{
gimple *def;

/* Reset returned probability value.  */
*probability = -1;
*predictor = PRED_UNCONDITIONAL;

if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
  {
    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))
return op0;

    if (code == IMAGPART_EXPR)
{
 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)
   {
     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;
     if (is_gimple_call (def)
  && gimple_call_internal_p (def)
  && (gimple_call_internal_fn (def)
      == IFN_ATOMIC_COMPARE_EXCHANGE))
{
  /* Assume that any given atomic operation has low contention,
     and thus the compare-and-swap operation succeeds.  */
  *predictor = PRED_COMPARE_AND_SWAP;
  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));
}
   }
}

    if (code != SSA_NAME)
return NULL_TREE(tree) nullptr;

    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;

    /* If we were already here, break the infinite cycle.  */
    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))
return NULLnullptr;

    if (gimple_code (def) == GIMPLE_PHI)
{
 /* All the arguments of the PHI node must have the same constant
    length.  */
 int i, n = gimple_phi_num_args (def);
 tree val = NULLnullptr, new_val;

 for (i = 0; i < n; i++)
   {
     tree arg = PHI_ARG_DEF (def, i)gimple_phi_arg_def ((def), (i));
     enum br_predictor predictor2;

     /* If this PHI has itself as an argument, we cannot
 determine the string length of this argument.  However,
 if we can find an expected constant value for the other
 PHI args then we can still be sure that this is
 likely a constant.  So be optimistic and just
 continue with the next argument.  */
     if (arg == PHI_RESULT (def)get_def_from_ptr (gimple_phi_result_ptr (def)))
continue;

     HOST_WIDE_INTlong probability2;
     new_val = expr_expected_value (arg, visited, &predictor2,
			     &probability2);

     /* It is difficult to combine value predictors.  Simply assume
 that later predictor is weaker and take its prediction.  */
     if (*predictor < predictor2)
{
  *predictor = predictor2;
  *probability = probability2;
}
     if (!new_val)
return NULLnullptr;
     if (!val)
val = new_val;
     else if (!operand_equal_p (val, new_val, false))
return NULLnullptr;
   }
 return val;
}
    if (is_gimple_assign (def))
{
 if (gimple_assign_lhs (def) != op0)
   return NULLnullptr;

 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),
			gimple_assign_rhs1 (def),
			gimple_assign_rhs_code (def),
			gimple_assign_rhs2 (def),
			visited, predictor, probability);
}

    if (is_gimple_call (def))
{
 tree decl = gimple_call_fndecl (def);
 if (!decl)
   {
     if (gimple_call_internal_p (def)
  && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
{
  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));
  tree val = gimple_call_arg (def, 0);
  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))
    return val;
  tree val2 = gimple_call_arg (def, 2);
  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))
	      && 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))
	      && 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));
  *predictor = (enum br_predictor) tree_to_uhwi (val2);
  if (*predictor == PRED_BUILTIN_EXPECT)
    *probability
      = HITRATE (param_builtin_expect_probability)((int) ((global_options.x_param_builtin_expect_probability) *
+ 50) / 100);
  return gimple_call_arg (def, 1);
}
     return NULLnullptr;
   }

 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))
   {
     if (predictor)
*predictor = PRED_MALLOC_NONNULL;
     return boolean_true_nodeglobal_trees[TI_BOOLEAN_TRUE];
   }

 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)
   switch (DECL_FUNCTION_CODE (decl))
     {
     case BUILT_IN_EXPECT:
{
  tree val;
  if (gimple_call_num_args (def) != 2)
    return NULLnullptr;
  val = gimple_call_arg (def, 0);
  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))
    return val;
  *predictor = PRED_BUILTIN_EXPECT;
  *probability
    = HITRATE (param_builtin_expect_probability)((int) ((global_options.x_param_builtin_expect_probability) *
+ 50) / 100);
  return gimple_call_arg (def, 1);
}
     case BUILT_IN_EXPECT_WITH_PROBABILITY:
{
  tree val;
  if (gimple_call_num_args (def) != 3)
    return NULLnullptr;
  val = gimple_call_arg (def, 0);
  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))
    return val;
  /* Compute final probability as:
     probability * REG_BR_PROB_BASE.  */
  tree prob = gimple_call_arg (def, 2);
  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);
  tree base = build_int_cst (integer_type_nodeinteger_types[itk_int],
			     REG_BR_PROB_BASE10000);
  base = build_real_from_int_cst (t, base);
  tree r = fold_build2_initializer_loc (UNKNOWN_LOCATION((location_t) 0),
					MULT_EXPR, t, prob, base);
  if (TREE_CODE (r)((enum tree_code) (r)->base.code) != REAL_CST)
    {
      error_at (gimple_location (def),
		"probability %qE must be "
		"constant floating-point expression", prob);
      return NULLnullptr;
    }
  HOST_WIDE_INTlong probi
    = 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));
  if (probi >= 0 && probi <= REG_BR_PROB_BASE10000)
    {
      *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
      *probability = probi;
    }
  else
    error_at (gimple_location (def),
	      "probability %qE is outside "
	      "the range [0.0, 1.0]", prob);

  return gimple_call_arg (def, 1);
}

     case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
     case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
     case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
     case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
     case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
     case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
     case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
     case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
     case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
     case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
     case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
     case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
     case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
/* Assume that any given atomic operation has low contention,
   and thus the compare-and-swap operation succeeds.  */
*predictor = PRED_COMPARE_AND_SWAP;
return boolean_true_nodeglobal_trees[TI_BOOLEAN_TRUE];
     case BUILT_IN_REALLOC:
if (predictor)
  *predictor = PRED_MALLOC_NONNULL;
return boolean_true_nodeglobal_trees[TI_BOOLEAN_TRUE];
     default:
break;
   }
}

    return NULLnullptr;
  }

if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
  {
    tree res;
    enum br_predictor predictor2;
    HOST_WIDE_INTlong probability2;
    op0 = expr_expected_value (op0, visited, predictor, probability);
    if (!op0)
return NULLnullptr;
    op1 = expr_expected_value (op1, visited, &predictor2, &probability2);
    if (!op1)
return NULLnullptr;
    res = fold_build2 (code, type, op0, op1)fold_build2_loc (((location_t) 0), code, type, op0, op1 );
    if (TREE_CODE (res)((enum tree_code) (res)->base.code) == INTEGER_CST
 && TREE_CODE (op0)((enum tree_code) (op0)->base.code) == INTEGER_CST
 && TREE_CODE (op1)((enum tree_code) (op1)->base.code) == INTEGER_CST)
{
 /* Combine binary predictions.  */
 if (*probability != -1 || probability2 != -1)
   {
     HOST_WIDE_INTlong p1 = get_predictor_value (*predictor, *probability);
     HOST_WIDE_INTlong p2 = get_predictor_value (predictor2, probability2);
     *probability = RDIV (p1 * p2, REG_BR_PROB_BASE)(((p1 * p2) + (10000) / 2) / (10000));
   }

 if (*predictor < predictor2)
   *predictor = predictor2;

 return res;
}
    return NULLnullptr;
  }
if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
  {
    tree res;
    op0 = expr_expected_value (op0, visited, predictor, probability);
    if (!op0)
return NULLnullptr;
    res = fold_build1 (code, type, op0)fold_build1_loc (((location_t) 0), code, type, op0 );
    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))
return res;
    return NULLnullptr;
  }
return NULLnullptr;
2613}

2615/* Return constant EXPR will likely have at execution time, NULL if unknown.
 The function is used by builtin_expect branch predictor so the evidence
 must come from this construct and additional possible constant folding.

 We may want to implement more involved value guess (such as value range
 propagation based prediction), but such tricks shall go to new
 implementation.  */

2623static tree
2624expr_expected_value (tree expr, bitmap visited,
     enum br_predictor *predictor,
     HOST_WIDE_INTlong *probability)
2627{
enum tree_code code;
tree op0, op1;

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))
  {
    *predictor = PRED_UNCONDITIONAL;
    *probability = -1;
    return expr;
  }

extract_ops_from_tree (expr, &code, &op0, &op1);
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),
		op0, code, op1, visited, predictor,
		probability);
2642}
2643

2645/* Return probability of a PREDICTOR.  If the predictor has variable
 probability return passed PROBABILITY.  */

2648static HOST_WIDE_INTlong
2649get_predictor_value (br_predictor predictor, HOST_WIDE_INTlong probability)
2650{
switch (predictor)
  {
  case PRED_BUILTIN_EXPECT:
  case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
    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));
    return probability;
  default:
    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));
    return predictor_info[(int) predictor].hitrate;
  }
2661}

2663/* Predict using opcode of the last statement in basic block.  */
2664static void
2665tree_predict_by_opcode (basic_block bb)
2666{
gimple *stmt = last_stmt (bb);
edge then_edge;
tree op0, op1;
tree type;
tree val;
enum tree_code cmp;
edge_iterator ei;
enum br_predictor predictor;
HOST_WIDE_INTlong probability;

if (!stmt)
  return;

if (gswitch *sw = dyn_cast <gswitch *> (stmt))
  {
    tree index = gimple_switch_index (sw);
    tree val = expr_expected_value (index, auto_bitmap (),
		      &predictor, &probability);
    if (val && TREE_CODE (val)((enum tree_code) (val)->base.code) == INTEGER_CST)
{
 edge e = find_taken_edge_switch_expr (sw, val);
 if (predictor == PRED_BUILTIN_EXPECT)
   {
     int percent = param_builtin_expect_probabilityglobal_options.x_param_builtin_expect_probability;
     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));
     predict_edge (e, PRED_BUILTIN_EXPECT,
	    HITRATE (percent)((int) ((percent) * 10000 + 50) / 100));
   }
 else
   predict_edge_def (e, predictor, TAKEN);
}
  }

if (gimple_code (stmt) != GIMPLE_COND)
  return;
FOR_EACH_EDGE (then_edge, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(then_edge)); ei_next (&(ei)))
  if (then_edge->flags & EDGE_TRUE_VALUE)
    break;
op0 = gimple_cond_lhs (stmt);
op1 = gimple_cond_rhs (stmt);
cmp = gimple_cond_code (stmt);
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);
val = expr_expected_value_1 (boolean_type_nodeglobal_trees[TI_BOOLEAN_TYPE], op0, cmp, op1, auto_bitmap (),
	       &predictor, &probability);
if (val && TREE_CODE (val)((enum tree_code) (val)->base.code) == INTEGER_CST)
  {
    HOST_WIDE_INTlong prob = get_predictor_value (predictor, probability);
    if (integer_zerop (val))
prob = REG_BR_PROB_BASE10000 - prob;
    predict_edge (then_edge, predictor, prob);
  }
/* Try "pointer heuristic."
   A comparison ptr == 0 is predicted as false.
   Similarly, a comparison ptr1 == ptr2 is predicted as false.  */
if (POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE))
  {
    if (cmp == EQ_EXPR)
predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
    else if (cmp == NE_EXPR)
predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
  }
else

/* Try "opcode heuristic."
   EQ tests are usually false and NE tests are usually true. Also,
   most quantities are positive, so we can make the appropriate guesses
   about signed comparisons against zero.  */
  switch (cmp)
    {
    case EQ_EXPR:
    case UNEQ_EXPR:
/* Floating point comparisons appears to behave in a very
  unpredictable way because of special role of = tests in
  FP code.  */
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
))))
 ;
/* Comparisons with 0 are often used for booleans and there is
  nothing useful to predict about them.  */
else if (integer_zerop (op0) || integer_zerop (op1))
 ;
else
 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
break;

    case NE_EXPR:
    case LTGT_EXPR:
/* Floating point comparisons appears to behave in a very
  unpredictable way because of special role of = tests in
  FP code.  */
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
))))
 ;
/* Comparisons with 0 are often used for booleans and there is
  nothing useful to predict about them.  */
else if (integer_zerop (op0)
 || integer_zerop (op1))
 ;
else
 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
break;

    case ORDERED_EXPR:
predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
break;

    case UNORDERED_EXPR:
predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
break;

    case LE_EXPR:
    case LT_EXPR:
if (integer_zerop (op1)
   || integer_onep (op1)
   || integer_all_onesp (op1)
   || real_zerop (op1)
   || real_onep (op1)
   || real_minus_onep (op1))
 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
break;

    case GE_EXPR:
    case GT_EXPR:
if (integer_zerop (op1)
   || integer_onep (op1)
   || integer_all_onesp (op1)
   || real_zerop (op1)
   || real_onep (op1)
   || real_minus_onep (op1))
 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
break;

    default:
break;
    }
2800}

2802/* Returns TRUE if the STMT is exit(0) like statement. */

2804static bool
2805is_exit_with_zero_arg (const gimple *stmt)
2806{
/* This is not exit, _exit or _Exit. */
if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
    && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
    && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
  return false;

/* Argument is an interger zero. */
return integer_zerop (gimple_call_arg (stmt, 0));
2815}

2817/* Try to guess whether the value of return means error code.  */

2819static enum br_predictor
2820return_prediction (tree val, enum prediction *prediction)
2821{
/* VOID.  */
if (!val)
  return PRED_NO_PREDICTION;
/* Different heuristics for pointers and scalars.  */
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
))
  {
    /* NULL is usually not returned.  */
    if (integer_zerop (val))
{
 *prediction = NOT_TAKEN;
 return PRED_NULL_RETURN;
}
  }
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
))
  {
    /* Negative return values are often used to indicate
       errors.  */
    if (TREE_CODE (val)((enum tree_code) (val)->base.code) == INTEGER_CST
 && tree_int_cst_sgn (val) < 0)
{
 *prediction = NOT_TAKEN;
 return PRED_NEGATIVE_RETURN;
}
    /* Constant return values seems to be commonly taken.
       Zero/one often represent booleans so exclude them from the
heuristics.  */
    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)
 && (!integer_zerop (val) && !integer_onep (val)))
{
 *prediction = NOT_TAKEN;
 return PRED_CONST_RETURN;
}
  }
return PRED_NO_PREDICTION;
2856}

2858/* Return zero if phi result could have values other than -1, 0 or 1,
 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
 values are used or likely.  */

2862static int
2863zero_one_minusone (gphi *phi, int limit)
2864{
int phi_num_args = gimple_phi_num_args (phi);
int ret = 0;
for (int i = 0; i < phi_num_args; i++)
  {
    tree t = PHI_ARG_DEF (phi, i)gimple_phi_arg_def ((phi), (i));
    if (TREE_CODE (t)((enum tree_code) (t)->base.code) != INTEGER_CST)
continue;
    wide_int w = wi::to_wide (t);
    if (w == -1)
ret |= 1;
    else if (w == 0)
ret |= 2;
    else if (w == 1)
ret |= 4;
    else
return 0;
  }
for (int i = 0; i < phi_num_args; i++)
  {
    tree t = PHI_ARG_DEF (phi, i)gimple_phi_arg_def ((phi), (i));
    if (TREE_CODE (t)((enum tree_code) (t)->base.code) == INTEGER_CST)
continue;
    if (TREE_CODE (t)((enum tree_code) (t)->base.code) != SSA_NAME)
return 0;
    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;
    if (gimple_code (g) == GIMPLE_PHI && limit > 0)
if (int r = zero_one_minusone (as_a <gphi *> (g), limit - 1))
 {
   ret |= r;
   continue;
 }
    if (!is_gimple_assign (g))
return 0;
    if (gimple_assign_cast_p (g))
{
 tree rhs1 = gimple_assign_rhs1 (g);
 if (TREE_CODE (rhs1)((enum tree_code) (rhs1)->base.code) != SSA_NAME
     || !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
)
     || 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
     || !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))
   return 0;
 ret |= (2 | 4);
 continue;
}
    if (TREE_CODE_CLASS (gimple_assign_rhs_code (g))tree_code_type[(int) (gimple_assign_rhs_code (g))] != tcc_comparison)
return 0;
    ret |= (2 | 4);
  }
return ret;
2914}

2916/* Find the basic block with return expression and look up for possible
 return value trying to apply RETURN_PREDICTION heuristics.  */
2918static void
2919apply_return_prediction (void)
2920{
greturn *return_stmt = NULLnullptr;
tree return_val;
edge e;
gphi *phi;
int phi_num_args, i;
enum br_predictor pred;
enum prediction direction;
edge_iterator ei;

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))
)
  {
    gimple *last = last_stmt (e->src);
    if (last
 && gimple_code (last) == GIMPLE_RETURN)
{
 return_stmt = as_a <greturn *> (last);
 break;
}
  }
if (!e)
  return;
return_val = gimple_return_retval (return_stmt);
if (!return_val)
  return;
if (TREE_CODE (return_val)((enum tree_code) (return_val)->base.code) != SSA_NAME
    || !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
    || 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)
  return;
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);
phi_num_args = gimple_phi_num_args (phi);
pred = return_prediction (PHI_ARG_DEF (phi, 0)gimple_phi_arg_def ((phi), (0)), &direction);

/* Avoid the case where the function returns -1, 0 and 1 values and
   nothing else.  Those could be qsort etc. comparison functions
   where the negative return isn't less probable than positive.
   For this require that the function returns at least -1 or 1
   or -1 and a boolean value or comparison result, so that functions
   returning just -1 and 0 are treated as if -1 represents error value.  */
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
)
    && !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)
    && 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)
  if (int r = zero_one_minusone (phi, 3))
    if ((r & (1 | 4)) == (1 | 4))
return;

/* Avoid the degenerate case where all return values form the function
   belongs to same category (ie they are all positive constants)
   so we can hardly say something about them.  */
for (i = 1; i < phi_num_args; i++)
  if (pred != return_prediction (PHI_ARG_DEF (phi, i)gimple_phi_arg_def ((phi), (i)), &direction))
    break;
if (i != phi_num_args)
  for (i = 0; i < phi_num_args; i++)
    {
pred = return_prediction (PHI_ARG_DEF (phi, i)gimple_phi_arg_def ((phi), (i)), &direction);
if (pred != PRED_NO_PREDICTION)
 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
		         direction);
    }
2980}

2982/* Look for basic block that contains unlikely to happen events
 (such as noreturn calls) and mark all paths leading to execution
 of this basic blocks as unlikely.  */

2986static void
2987tree_bb_level_predictions (void)
2988{
basic_block bb;
bool has_return_edges = false;
edge e;
edge_iterator ei;

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))
)
  if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
    {
      has_return_edges = true;
break;
    }

apply_return_prediction ();

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)
  {
    gimple_stmt_iterator gsi;

    for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
 gimple *stmt = gsi_stmt (gsi);
 tree decl;

 if (is_gimple_call (stmt))
   {
     if (gimple_call_noreturn_p (stmt)
  && has_return_edges
  && !is_exit_with_zero_arg (stmt))
predict_paths_leading_to (bb, PRED_NORETURN,
			  NOT_TAKEN);
     decl = gimple_call_fndecl (stmt);
     if (decl
  && 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"
, 3022, __FUNCTION__))->decl_common.attributes)))
predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
			  NOT_TAKEN);
     if (decl && recursive_call_p (current_function_decl, decl))
predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
			  NOT_TAKEN);
   }
 else if (gimple_code (stmt) == GIMPLE_PREDICT)
   {
     predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
			gimple_predict_outcome (stmt));
     /* Keep GIMPLE_PREDICT around so early inlining will propagate
        hints to callers.  */
   }
}
  }
3038}

3040/* Callback for hash_map::traverse, asserts that the pointer map is
 empty.  */

3043bool
3044assert_is_empty (const_basic_block const &, edge_prediction *const &value,
 void *)
3046{
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));
return false;
3049}

3051/* Predict branch probabilities and estimate profile for basic block BB.
 When LOCAL_ONLY is set do not use any global properties of CFG.  */

3054static void
3055tree_estimate_probability_bb (basic_block bb, bool local_only)
3056{
edge e;
edge_iterator ei;

FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
  {
    /* Look for block we are guarding (ie we dominate it,
but it doesn't postdominate us).  */
    if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_exit_block_ptr) && e->dest != bb
 && !local_only
 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
{
 gimple_stmt_iterator bi;

 /* The call heuristic claims that a guarded function call
    is improbable.  This is because such calls are often used
    to signal exceptional situations such as printing error
    messages.  */
 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
      gsi_next (&bi))
   {
     gimple *stmt = gsi_stmt (bi);
     if (is_gimple_call (stmt)
  && !gimple_inexpensive_call_p (as_a <gcall *>  (stmt))
  /* Constant and pure calls are hardly used to signalize
     something exceptional.  */
  && gimple_has_side_effects (stmt))
{
  if (gimple_call_fndecl (stmt))
    predict_edge_def (e, PRED_CALL, NOT_TAKEN);
  else if (virtual_method_call_p (gimple_call_fn (stmt)))
    predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
  else
    predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
  break;
}
   }
}
  }
tree_predict_by_opcode (bb);
3097}

3099/* Predict branch probabilities and estimate profile of the tree CFG.
 This function can be called from the loop optimizers to recompute
 the profile information.
 If DRY_RUN is set, do not modify CFG and only produce dump files.  */

3104void
3105tree_estimate_probability (bool dry_run)
3106{
basic_block bb;

add_noreturn_fake_exit_edges ();
connect_infinite_loops_to_exit ();
/* We use loop_niter_by_eval, which requires that the loops have
   preheaders.  */
create_preheaders (CP_SIMPLE_PREHEADERS);
calculate_dominance_info (CDI_POST_DOMINATORS);
/* Decide which edges are known to be unlikely.  This improves later
   branch prediction. */
determine_unlikely_bbs ();

bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
tree_bb_level_predictions ();
record_loop_exits ();

if (number_of_loops (cfun(cfun + 0)) > 1)
  predict_loops ();

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)
  tree_estimate_probability_bb (bb, false);

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)
  combine_predictions_for_bb (bb, dry_run);

if (flag_checkingglobal_options.x_flag_checking)
  bb_predictions->traverse<void *, assert_is_empty> (NULLnullptr);

delete bb_predictions;
bb_predictions = NULLnullptr;

if (!dry_run)
  estimate_bb_frequencies (false);
free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_exit_edges ();
3142}

3144/* Set edge->probability for each successor edge of BB.  */
3145void
3146tree_guess_outgoing_edge_probabilities (basic_block bb)
3147{
bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
tree_estimate_probability_bb (bb, true);
combine_predictions_for_bb (bb, false);
if (flag_checkingglobal_options.x_flag_checking)
  bb_predictions->traverse<void *, assert_is_empty> (NULLnullptr);
delete bb_predictions;
bb_predictions = NULLnullptr;
3155}
3156
3157/* Filter function predicate that returns true for a edge predicate P
 if its edge is equal to DATA.  */

3160static bool
3161not_loop_guard_equal_edge_p (edge_prediction *p, void *data)
3162{
return p->ep_edge != (edge)data || p->ep_predictor != PRED_LOOP_GUARD;
3164}

3166/* Predict edge E with PRED unless it is already predicted by some predictor
 considered equivalent.  */

3169static void
3170maybe_predict_edge (edge e, enum br_predictor pred, enum prediction taken)
3171{
if (edge_predicted_by_p (e, pred, taken))
  return;
if (pred == PRED_LOOP_GUARD
    && edge_predicted_by_p (e, PRED_LOOP_GUARD_WITH_RECURSION, taken))
  return;
/* Consider PRED_LOOP_GUARD_WITH_RECURSION superrior to LOOP_GUARD.  */
if (pred == PRED_LOOP_GUARD_WITH_RECURSION)
  {
    edge_prediction **preds = bb_predictions->get (e->src);
    if (preds)
filter_predictions (preds, not_loop_guard_equal_edge_p, e);
  }
predict_edge_def (e, pred, taken);
3185}
3186/* Predict edges to successors of CUR whose sources are not postdominated by
 BB by PRED and recurse to all postdominators.  */

3189static void
3190predict_paths_for_bb (basic_block cur, basic_block bb,
      enum br_predictor pred,
      enum prediction taken,
      bitmap visited, class loop *in_loop = NULLnullptr)
3194{
edge e;
edge_iterator ei;
basic_block son;

/* If we exited the loop or CUR is unconditional in the loop, there is
   nothing to do.  */
if (in_loop
    && (!flow_bb_inside_loop_p (in_loop, cur)
 || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
  return;

/* We are looking for all edges forming edge cut induced by
   set of all blocks postdominated by BB.  */
FOR_EACH_EDGE (e, ei, cur->preds)for ((ei) = ei_start_1 (&((cur->preds))); ei_cond ((ei
), &(e)); ei_next (&(ei)))
  if (e->src->index >= NUM_FIXED_BLOCKS(2)
&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
  {
    edge e2;
    edge_iterator ei2;
    bool found = false;

    /* Ignore fake edges and eh, we predict them as not taken anyway.  */
    if (unlikely_executed_edge_p (e))
continue;
    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));

    /* See if there is an edge from e->src that is not abnormal
and does not lead to BB and does not exit the loop.  */
    FOR_EACH_EDGE (e2, ei2, e->src->succs)for ((ei2) = ei_start_1 (&((e->src->succs))); ei_cond
 ((ei2), &(e2)); ei_next (&(ei2)))
if (e2 != e
   && !unlikely_executed_edge_p (e2)
   && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
   && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
 {
   found = true;
   break;
 }

    /* If there is non-abnormal path leaving e->src, predict edge
using predictor.  Otherwise we need to look for paths
leading to e->src.

The second may lead to infinite loop in the case we are predicitng
regions that are only reachable by abnormal edges.  We simply
prevent visiting given BB twice.  */
    if (found)
maybe_predict_edge (e, pred, taken);
    else if (bitmap_set_bit (visited, e->src->index))
predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
  }
for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
     son;
     son = next_dom_son (CDI_POST_DOMINATORS, son))
  predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
3249}

3251/* Sets branch probabilities according to PREDiction and
 FLAGS.  */

3254static void
3255predict_paths_leading_to (basic_block bb, enum br_predictor pred,
	  enum prediction taken, class loop *in_loop)
3257{
predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3259}

3261/* Like predict_paths_leading_to but take edge instead of basic block.  */

3263static void
3264predict_paths_leading_to_edge (edge e, enum br_predictor pred,
	       enum prediction taken, class loop *in_loop)
3266{
bool has_nonloop_edge = false;
edge_iterator ei;
edge e2;

basic_block bb = e->src;
FOR_EACH_EDGE (e2, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e2)); ei_next (&(ei)))
  if (e2->dest != e->src && e2->dest != e->dest
&& !unlikely_executed_edge_p (e2)
&& !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
    {
has_nonloop_edge = true;
break;
    }

if (!has_nonloop_edge)
  predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
else
  maybe_predict_edge (e, pred, taken);
3285}
3286
3287/* This is used to carry information about basic blocks.  It is
 attached to the AUX field of the standard CFG block.  */

3290class block_info
3291{
3292public:
/* Estimated frequency of execution of basic_block.  */
sreal frequency;

/* To keep queue of basic blocks to process.  */
basic_block next;

/* Number of predecessors we need to visit first.  */
int npredecessors;
3301};

3303/* Similar information for edges.  */
3304class edge_prob_info
3305{
3306public:
/* In case edge is a loopback edge, the probability edge will be reached
   in case header is.  Estimated number of iterations of the loop can be
   then computed as 1 / (1 - back_edge_prob).  */
sreal back_edge_prob;
/* True if the edge is a loopback edge in the natural loop.  */
unsigned int back_edge:1;
3313};

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)

3319/* Helper function for estimate_bb_frequencies.
 Propagate the frequencies in blocks marked in
 TOVISIT, starting in HEAD.  */

3323static void
3324propagate_freq (basic_block head, bitmap tovisit,
sreal max_cyclic_prob)
3326{
basic_block bb;
basic_block last;
unsigned i;
edge e;
basic_block nextbb;
bitmap_iterator bi;

/* For each basic block we need to visit count number of his predecessors
   we need to visit first.  */
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)))
  {
    edge_iterator ei;
    int count = 0;

    bb = BASIC_BLOCK_FOR_FN (cfun, i)((*(((cfun + 0))->cfg->x_basic_block_info))[(i)]);

    FOR_EACH_EDGE (e, ei, bb->preds)for ((ei) = ei_start_1 (&((bb->preds))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
{
 bool visit = bitmap_bit_p (tovisit, e->src->index);

 if (visit && !(e->flags & EDGE_DFS_BACK))
   count++;
 else if (visit && dump_file && !EDGE_INFO (e)((edge_prob_info *) (e)->aux)->back_edge)
   fprintf (dump_file,
     "Irreducible region hit, ignoring edge to %i->%i\n",
     e->src->index, bb->index);
}
    BLOCK_INFO (bb)((block_info *) (bb)->aux)->npredecessors = count;
    /* When function never returns, we will never process exit block.  */
    if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_exit_block_ptr))
bb->count = profile_count::zero ();
  }

BLOCK_INFO (head)((block_info *) (head)->aux)->frequency = 1;
last = head;
for (bb = head; bb; bb = nextbb)
  {
    edge_iterator ei;
    sreal cyclic_probability = 0;
    sreal frequency = 0;

    nextbb = BLOCK_INFO (bb)((block_info *) (bb)->aux)->next;
    BLOCK_INFO (bb)((block_info *) (bb)->aux)->next = NULLnullptr;

    /* Compute frequency of basic block.  */
    if (bb != head)
{
 if (flag_checkingglobal_options.x_flag_checking)
   FOR_EACH_EDGE (e, ei, bb->preds)for ((ei) = ei_start_1 (&((bb->preds))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
     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))
	  || (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));

 FOR_EACH_EDGE (e, ei, bb->preds)for ((ei) = ei_start_1 (&((bb->preds))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
   if (EDGE_INFO (e)((edge_prob_info *) (e)->aux)->back_edge)
     cyclic_probability += EDGE_INFO (e)((edge_prob_info *) (e)->aux)->back_edge_prob;
   else if (!(e->flags & EDGE_DFS_BACK))
     {
/* FIXME: Graphite is producing edges with no profile. Once
   this is fixed, drop this.  */
sreal tmp = e->probability.initialized_p () ?
	    e->probability.to_sreal () : 0;
frequency += tmp * BLOCK_INFO (e->src)((block_info *) (e->src)->aux)->frequency;
     }

 if (cyclic_probability == 0)
   {
     BLOCK_INFO (bb)((block_info *) (bb)->aux)->frequency = frequency;
   }
 else
   {
     if (cyclic_probability > max_cyclic_prob)
{
  if (dump_file)
    fprintf (dump_file,
	     "cyclic probability of bb %i is %f (capped to %f)"
	     "; turning freq %f",
	     bb->index, cyclic_probability.to_double (),
	     max_cyclic_prob.to_double (),
	     frequency.to_double ());
	
  cyclic_probability = max_cyclic_prob;
}
     else if (dump_file)
fprintf (dump_file,
	 "cyclic probability of bb %i is %f; turning freq %f",
	 bb->index, cyclic_probability.to_double (),
	 frequency.to_double ());

     BLOCK_INFO (bb)((block_info *) (bb)->aux)->frequency = frequency
		 / (sreal (1) - cyclic_probability);
     if (dump_file)
fprintf (dump_file, " to %f\n",
	 BLOCK_INFO (bb)((block_info *) (bb)->aux)->frequency.to_double ());
   }
}

    bitmap_clear_bit (tovisit, bb->index);

    e = find_edge (bb, head);
    if (e)
{
 /* FIXME: Graphite is producing edges with no profile. Once
    this is fixed, drop this.  */
 sreal tmp = e->probability.initialized_p () ?
      e->probability.to_sreal () : 0;
 EDGE_INFO (e)((edge_prob_info *) (e)->aux)->back_edge_prob = tmp * BLOCK_INFO (bb)((block_info *) (bb)->aux)->frequency;
}

    /* Propagate to successor blocks.  */
    FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
if (!(e->flags & EDGE_DFS_BACK)
   && BLOCK_INFO (e->dest)((block_info *) (e->dest)->aux)->npredecessors)
 {
   BLOCK_INFO (e->dest)((block_info *) (e->dest)->aux)->npredecessors--;
   if (!BLOCK_INFO (e->dest)((block_info *) (e->dest)->aux)->npredecessors)
     {
if (!nextbb)
  nextbb = e->dest;
else
  BLOCK_INFO (last)((block_info *) (last)->aux)->next = e->dest;

last = e->dest;
     }
 }
  }
3452}

3454/* Estimate frequencies in loops at same nest level.  */

3456static void
3457estimate_loops_at_level (class loop *first_loop, sreal max_cyclic_prob)
3458{
class loop *loop;

for (loop = first_loop; loop; loop = loop->next)
  {
    edge e;
    basic_block *bbs;
    unsigned i;
    auto_bitmap tovisit;

    estimate_loops_at_level (loop->inner, max_cyclic_prob);

    /* Find current loop back edge and mark it.  */
    e = loop_latch_edge (loop);
    EDGE_INFO (e)((edge_prob_info *) (e)->aux)->back_edge = 1;

    bbs = get_loop_body (loop);
    for (i = 0; i < loop->num_nodes; i++)
bitmap_set_bit (tovisit, bbs[i]->index);
    free (bbs);
    propagate_freq (loop->header, tovisit, max_cyclic_prob);
  }
3480}

3482/* Propagates frequencies through structure of loops.  */

3484static void
3485estimate_loops (void)
3486{
auto_bitmap tovisit;
basic_block bb;
sreal max_cyclic_prob = (sreal)1
	   - (sreal)1 / (param_max_predicted_iterationsglobal_options.x_param_max_predicted_iterations + 1);

/* Start by estimating the frequencies in the loops.  */
if (number_of_loops (cfun(cfun + 0)) > 1)
  estimate_loops_at_level (current_loops((cfun + 0)->x_current_loops)->tree_root->inner, max_cyclic_prob);

/* Now propagate the frequencies through all the blocks.  */
FOR_ALL_BB_FN (bb, cfun)for (bb = (((cfun + 0))->cfg->x_entry_block_ptr); bb; bb
 = bb->next_bb)
  {
    bitmap_set_bit (tovisit, bb->index);
  }
propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr), tovisit, max_cyclic_prob);
3502}

3504/* Drop the profile for NODE to guessed, and update its frequency based on
 whether it is expected to be hot given the CALL_COUNT.  */

3507static void
3508drop_profile (struct cgraph_node *node, profile_count call_count)
3509{
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);
/* In the case where this was called by another function with a
   dropped profile, call_count will be 0. Since there are no
   non-zero call counts to this function, we don't know for sure
   whether it is hot, and therefore it will be marked normal below.  */
bool hot = maybe_hot_count_p (NULLnullptr, call_count);

if (dump_file)
  fprintf (dump_file,
    "Dropping 0 profile for %s. %s based on calls.\n",
    node->dump_name (),
    hot ? "Function is hot" : "Function is normal");
/* We only expect to miss profiles for functions that are reached
   via non-zero call edges in cases where the function may have
   been linked from another module or library (COMDATs and extern
   templates). See the comments below for handle_missing_profiles.
   Also, only warn in cases where the missing counts exceed the
   number of training runs. In certain cases with an execv followed
   by a no-return call the profile for the no-return call is not
   dumped and there can be a mismatch.  */
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)
    && call_count > profile_info->runs)
  {
    if (flag_profile_correctionglobal_options.x_flag_profile_correction)
      {
        if (dump_file)
          fprintf (dump_file,
     "Missing counts for called function %s\n",
     node->dump_name ());
      }
    else
warning (0, "Missing counts for called function %s",
 node->dump_name ());
  }

basic_block bb;
if (opt_for_fn (node->decl, flag_guess_branch_prob)(opts_for_fn (node->decl)->x_flag_guess_branch_prob))
  {
    bool clear_zeros
= !ENTRY_BLOCK_PTR_FOR_FN (fn)((fn)->cfg->x_entry_block_ptr)->count.nonzero_p ();
    FOR_ALL_BB_FN (bb, fn)for (bb = ((fn)->cfg->x_entry_block_ptr); bb; bb = bb->
next_bb)
if (clear_zeros || !(bb->count == profile_count::zero ()))
 bb->count = bb->count.guessed_local ();
    fn->cfg->count_max = fn->cfg->count_max.guessed_local ();
  }
else
  {
    FOR_ALL_BB_FN (bb, fn)for (bb = ((fn)->cfg->x_entry_block_ptr); bb; bb = bb->
next_bb)
bb->count = profile_count::uninitialized ();
    fn->cfg->count_max = profile_count::uninitialized ();
  }

struct cgraph_edge *e;
for (e = node->callees; e; e = e->next_callee)
  e->count = gimple_bb (e->call_stmt)->count;
for (e = node->indirect_calls; e; e = e->next_callee)
  e->count = gimple_bb (e->call_stmt)->count;
node->count = ENTRY_BLOCK_PTR_FOR_FN (fn)((fn)->cfg->x_entry_block_ptr)->count;

profile_status_for_fn (fn)((fn)->cfg->x_profile_status)
    = (flag_guess_branch_probglobal_options.x_flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
node->frequency
    = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3573}

3575/* In the case of COMDAT routines, multiple object files will contain the same
 function and the linker will select one for the binary. In that case
 all the other copies from the profile instrument binary will be missing
 profile counts. Look for cases where this happened, due to non-zero
 call counts going to 0-count functions, and drop the profile to guessed
 so that we can use the estimated probabilities and avoid optimizing only
 for size.
 
 The other case where the profile may be missing is when the routine
 is not going to be emitted to the object file, e.g. for "extern template"
 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
 all other cases of non-zero calls to 0-count functions.  */

3588void
3589handle_missing_profiles (void)
3590{
const int unlikely_frac = param_unlikely_bb_count_fractionglobal_options.x_param_unlikely_bb_count_fraction;
struct cgraph_node *node;
auto_vec<struct cgraph_node *, 64> worklist;

/* See if 0 count function has non-0 count callers.  In this case we
   lost some profile.  Drop its function profile to PROFILE_GUESSED.  */
FOR_EACH_DEFINED_FUNCTION (node)for ((node) = symtab->first_defined_function (); (node); (
node) = symtab->next_defined_function ((node)))
  {
    struct cgraph_edge *e;
    profile_count call_count = profile_count::zero ();
    gcov_type max_tp_first_run = 0;
    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);

    if (node->count.ipa ().nonzero_p ())
      continue;
    for (e = node->callers; e; e = e->next_caller)
if (e->count.ipa ().initialized_p () && e->count.ipa () > 0)
 {
          call_count = call_count + e->count.ipa ();

   if (e->caller->tp_first_run > max_tp_first_run)
     max_tp_first_run = e->caller->tp_first_run;
 }

    /* If time profile is missing, let assign the maximum that comes from
caller functions.  */
    if (!node->tp_first_run && max_tp_first_run)
node->tp_first_run = max_tp_first_run + 1;

    if (call_count > 0
        && fn && fn->cfg
        && call_count.apply_scale (unlikely_frac, 1) >= profile_info->runs)
      {
        drop_profile (node, call_count);
        worklist.safe_push (node);
      }
  }

/* Propagate the profile dropping to other 0-count COMDATs that are
   potentially called by COMDATs we already dropped the profile on.  */
while (worklist.length () > 0)
  {
    struct cgraph_edge *e;

    node = worklist.pop ();
    for (e = node->callees; e; e = e->next_caller)
      {
        struct cgraph_node *callee = e->callee;
        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);

        if (!(e->count.ipa () == profile_count::zero ())
     && callee->count.ipa ().nonzero_p ())
          continue;
        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))
     && fn && fn->cfg
            && profile_status_for_fn (fn)((fn)->cfg->x_profile_status) == PROFILE_READ)
          {
            drop_profile (node, profile_count::zero ());
            worklist.safe_push (callee);
          }
      }
  }
3653}

3655/* Convert counts measured by profile driven feedback to frequencies.
 Return nonzero iff there was any nonzero execution count.  */

3658bool
3659update_max_bb_count (void)
3660{
profile_count true_count_max = profile_count::uninitialized ();
basic_block bb;

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)
  true_count_max = true_count_max.max (bb->count);

cfun(cfun + 0)->cfg->count_max = true_count_max;

return true_count_max.ipa ().nonzero_p ();
3670}

3672/* Return true if function is likely to be expensive, so there is no point to
 optimize performance of prologue, epilogue or do inlining at the expense
 of code size growth.  THRESHOLD is the limit of number of instructions
 function can execute at average to be still considered not expensive.  */

3677bool
3678expensive_function_p (int threshold)
3679{
basic_block bb;

/* If profile was scaled in a way entry block has count 0, then the function
   is deifnitly taking a lot of time.  */
if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)->count.nonzero_p ())
  return true;

profile_count limit = ENTRY_BLOCK_PTR_FOR_FN(((cfun + 0))->cfg->x_entry_block_ptr)
	   (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)->count.apply_scale (threshold, 1);
profile_count sum = profile_count::zero ();
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)
  {
    rtx_insn *insn;

    if (!bb->count.initialized_p ())
{
 if (dump_file)
   fprintf (dump_file, "Function is considered expensive because"
     " count of bb %i is not initialized\n", bb->index);
 return true;
}

    FOR_BB_INSNS (bb, insn)for ((insn) = (bb)->il.x.head_; (insn) && (insn) !=
 NEXT_INSN ((bb)->il.x.rtl->end_); (insn) = NEXT_INSN (
insn))
if (active_insn_p (insn))
 {
   sum += bb->count;
   if (sum > limit)
     return true;
}
  }

return false;
3712}

3714/* All basic blocks that are reachable only from unlikely basic blocks are
 unlikely.  */

3717void
3718propagate_unlikely_bbs_forward (void)
3719{
auto_vec<basic_block, 64> worklist;
basic_block bb;
edge_iterator ei;
edge e;

if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)->count == profile_count::zero ()))
  {
    ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)->aux = (void *)(size_t) 1;
    worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr));

    while (worklist.length () > 0)
{
 bb = worklist.pop ();
 FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
   if (!(e->count () == profile_count::zero ())
&& !(e->dest->count == profile_count::zero ())
&& !e->dest->aux)
     {
e->dest->aux = (void *)(size_t) 1;
worklist.safe_push (e->dest);
     }
}
  }

FOR_ALL_BB_FN (bb, cfun)for (bb = (((cfun + 0))->cfg->x_entry_block_ptr); bb; bb
 = bb->next_bb)
  {
    if (!bb->aux)
{
 if (!(bb->count == profile_count::zero ())
     && (dump_file && (dump_flags & TDF_DETAILS)))
   fprintf (dump_file,
     "Basic block %i is marked unlikely by forward prop\n",
     bb->index);
 bb->count = profile_count::zero ();
}
    else
      bb->aux = NULLnullptr;
  }
3758}

3760/* Determine basic blocks/edges that are known to be unlikely executed and set
 their counters to zero.
 This is done with first identifying obviously unlikely BBs/edges and then
 propagating in both directions.  */

3765static void
3766determine_unlikely_bbs ()
3767{
basic_block bb;
auto_vec<basic_block, 64> worklist;
edge_iterator ei;
edge e;

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)
  {
    if (!(bb->count == profile_count::zero ())
 && unlikely_executed_bb_p (bb))
{
        if (dump_file && (dump_flags & TDF_DETAILS))
   fprintf (dump_file, "Basic block %i is locally unlikely\n",
     bb->index);
 bb->count = profile_count::zero ();
}

    FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
if (!(e->probability == profile_probability::never ())
   && unlikely_executed_edge_p (e))
 {
          if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Edge %i->%i is locally unlikely\n",
       bb->index, e->dest->index);
   e->probability = profile_probability::never ();
 }

    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));
  }
propagate_unlikely_bbs_forward ();

auto_vec<int, 64> nsuccs;
nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun)(((cfun + 0))->cfg->x_last_basic_block), true);
FOR_ALL_BB_FN (bb, cfun)for (bb = (((cfun + 0))->cfg->x_entry_block_ptr); bb; bb
 = bb->next_bb)
  if (!(bb->count == profile_count::zero ())
&& bb != EXIT_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_exit_block_ptr))
    {
nsuccs[bb->index] = 0;
      FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
 if (!(e->probability == profile_probability::never ())
     && !(e->dest->count == profile_count::zero ()))
   nsuccs[bb->index]++;
if (!nsuccs[bb->index])
 worklist.safe_push (bb);
    }
while (worklist.length () > 0)
  {
    bb = worklist.pop ();
    if (bb->count == profile_count::zero ())
continue;
    if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr))
{
 bool found = false;
        for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
             !gsi_end_p (gsi); gsi_next (&gsi))
   if (stmt_can_terminate_bb_p (gsi_stmt (gsi))
/* stmt_can_terminate_bb_p special cases noreturns because it
   assumes that fake edges are created.  We want to know that
   noreturn alone does not imply BB to be unlikely.  */
|| (is_gimple_call (gsi_stmt (gsi))
    && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN(1 << 3))))
     {
found = true;
break;
     }
 if (found)
   continue;
}
    if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
 "Basic block %i is marked unlikely by backward prop\n",
 bb->index);
    bb->count = profile_count::zero ();
    FOR_EACH_EDGE (e, ei, bb->preds)for ((ei) = ei_start_1 (&((bb->preds))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
if (!(e->probability == profile_probability::never ()))
 {
   if (!(e->src->count == profile_count::zero ()))
     {
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));
       nsuccs[e->src->index]--;
       if (!nsuccs[e->src->index])
  worklist.safe_push (e->src);
     }
 }
  }
/* Finally all edges from non-0 regions to 0 are unlikely.  */
FOR_ALL_BB_FN (bb, cfun)for (bb = (((cfun + 0))->cfg->x_entry_block_ptr); bb; bb
 = bb->next_bb)
  {
    if (!(bb->count == profile_count::zero ()))
FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
 if (!(e->probability == profile_probability::never ())
     && e->dest->count == profile_count::zero ())
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
 fprintf (dump_file, "Edge %i->%i is unlikely because "
	  "it enters unlikely block\n",
	  bb->index, e->dest->index);
      e->probability = profile_probability::never ();
    }

    edge other = NULLnullptr;

    FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
if (e->probability == profile_probability::never ())
 ;
else if (other)
 {
   other = NULLnullptr;
   break;
 }
else
 other = e;
    if (other
 && !(other->probability == profile_probability::always ()))
{
          if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Edge %i->%i is locally likely\n",
       bb->index, other->dest->index);
 other->probability = profile_probability::always ();
}
  }
if (ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)->count == profile_count::zero ())
  cgraph_node::get (current_function_decl)->count = profile_count::zero ();
3890}

3892/* Estimate and propagate basic block frequencies using the given branch
 probabilities.  If FORCE is true, the frequencies are used to estimate
 the counts even when there are already non-zero profile counts.  */

3896void
3897estimate_bb_frequencies (bool force)
3898{
basic_block bb;
sreal freq_max;

determine_unlikely_bbs ();

if (force || profile_status_for_fn (cfun)(((cfun + 0))->cfg->x_profile_status) != PROFILE_READ
    || !update_max_bb_count ())
  {

    mark_dfs_back_edges ();

    single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr))->probability =
profile_probability::always ();

    /* Set up block info for each basic block.  */
    alloc_aux_for_blocks (sizeof (block_info));
    alloc_aux_for_edges (sizeof (edge_prob_info));
    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)
{
 edge e;
 edge_iterator ei;

 FOR_EACH_EDGE (e, ei, bb->succs)for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei)
, &(e)); ei_next (&(ei)))
   {
     /* FIXME: Graphite is producing edges with no profile. Once
 this is fixed, drop this.  */
     if (e->probability.initialized_p ())
       EDGE_INFO (e)((edge_prob_info *) (e)->aux)->back_edge_prob
   = e->probability.to_sreal ();
     else
/* back_edge_prob = 0.5 */
EDGE_INFO (e)((edge_prob_info *) (e)->aux)->back_edge_prob = sreal (1, -1);
   }
}

    /* First compute frequencies locally for each loop from innermost
       to outermost to examine frequencies for back edges.  */
    estimate_loops ();

    freq_max = 0;
    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)
if (freq_max < BLOCK_INFO (bb)((block_info *) (bb)->aux)->frequency)
 freq_max = BLOCK_INFO (bb)((block_info *) (bb)->aux)->frequency;

    /* Scaling frequencies up to maximal profile count may result in
frequent overflows especially when inlining loops.
Small scalling results in unnecesary precision loss.  Stay in
the half of the (exponential) range.  */
    freq_max = (sreal (1) << (profile_count::n_bits / 2)) / freq_max;
    if (freq_max < 16)
freq_max = 16;
    profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)->count.ipa ();
    cfun(cfun + 0)->cfg->count_max = profile_count::uninitialized ();
    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)
{
 sreal tmp = BLOCK_INFO (bb)((block_info *) (bb)->aux)->frequency;
 if (tmp >= 1)
   {
     gimple_stmt_iterator gsi;
     tree decl;

     /* Self recursive calls can not have frequency greater than 1
 or program will never terminate.  This will result in an
 inconsistent bb profile but it is better than greatly confusing
 IPA cost metrics.  */
     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
if (is_gimple_call (gsi_stmt (gsi))
    && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULLnullptr
    && recursive_call_p (current_function_decl, decl))
  {
    if (dump_file)
      fprintf (dump_file, "Dropping frequency of recursive call"
	       " in bb %i from %f\n", bb->index,
	       tmp.to_double ());
    tmp = (sreal)9 / (sreal)10;
    break;
  }
   }
 tmp = tmp * freq_max + sreal (1, -1);
 profile_count count = profile_count::from_gcov_type (tmp.to_int ());	

 /* If we have profile feedback in which this function was never
    executed, then preserve this info.  */
 if (!(bb->count == profile_count::zero ()))
   bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
        cfun(cfun + 0)->cfg->count_max = cfun(cfun + 0)->cfg->count_max.max (bb->count);
}

    free_aux_for_blocks ();
    free_aux_for_edges ();
  }
compute_function_frequency ();
3991}

3993/* Decide whether function is hot, cold or unlikely executed.  */
3994void
3995compute_function_frequency (void)
3996{
basic_block bb;
struct cgraph_node *node = cgraph_node::get (current_function_decl);

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
)
    || 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
]))
  node->only_called_at_startup = true;
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
))
  node->only_called_at_exit = true;

if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)->count.ipa_p ())
  {
    int flags = flags_from_decl_or_type (current_function_decl);
    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))
 != NULLnullptr)
node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
    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))
      != NULLnullptr)
      node->frequency = NODE_FREQUENCY_HOT;
    else if (flags & ECF_NORETURN(1 << 3))
      node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
    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
]))
      node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
    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
)
      || 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
))
      node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
    return;
  }

node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
warn_function_cold (current_function_decl);
if (ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr)->count.ipa() == profile_count::zero ())
  return;
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)
  {
    if (maybe_hot_bb_p (cfun(cfun + 0), bb))
{
 node->frequency = NODE_FREQUENCY_HOT;
 return;
}
    if (!probably_never_executed_bb_p (cfun(cfun + 0), bb))
node->frequency = NODE_FREQUENCY_NORMAL;
  }
4039}

4041/* Build PREDICT_EXPR.  */
4042tree
4043build_predict_expr (enum br_predictor predictor, enum prediction taken)
4044{
tree t = build1 (PREDICT_EXPR, void_type_nodeglobal_trees[TI_VOID_TYPE],
   build_int_cst (integer_type_nodeinteger_types[itk_int], predictor));
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);
return t;
4049}

4051const char *
4052predictor_name (enum br_predictor predictor)
4053{
return predictor_info[predictor].name;
4055}

4057/* Predict branch probabilities and estimate profile of the tree CFG. */

4059namespace {

4061const pass_data pass_data_profile =
4062{
GIMPLE_PASS, /* type */
"profile_estimate", /* name */
OPTGROUP_NONE, /* optinfo_flags */
TV_BRANCH_PROB, /* tv_id */
PROP_cfg(1 << 3), /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
0, /* todo_flags_finish */
4072};

4074class pass_profile : public gimple_opt_pass
4075{
4076public:
pass_profile (gcc::context *ctxt)
  : gimple_opt_pass (pass_data_profile, ctxt)
{}

/* opt_pass methods: */
virtual bool gate (function *) { return flag_guess_branch_probglobal_options.x_flag_guess_branch_prob; }
virtual unsigned int execute (function *);

4085}; // class pass_profile

4087unsigned int
4088pass_profile::execute (function *fun)
4089{
unsigned nb_loops;

if (profile_status_for_fn (cfun)(((cfun + 0))->cfg->x_profile_status) == PROFILE_GUESSED)
  return 0;

loop_optimizer_init (LOOPS_NORMAL(LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
));
if (dump_file && (dump_flags & TDF_DETAILS))
  flow_loops_dump (dump_file, NULLnullptr, 0);

mark_irreducible_loops ();

nb_loops = number_of_loops (fun);
if (nb_loops > 1)
  scev_initialize ();

tree_estimate_probability (false);

if (nb_loops > 1)
  scev_finalize ();

loop_optimizer_finalize ();
if (dump_file && (dump_flags & TDF_DETAILS))
  gimple_dump_cfg (dump_file, dump_flags);
if (profile_status_for_fn (fun)((fun)->cfg->x_profile_status) == PROFILE_ABSENT)
  profile_status_for_fn (fun)((fun)->cfg->x_profile_status) = PROFILE_GUESSED;
if (dump_file && (dump_flags & TDF_DETAILS))
 {
   class loop *loop;
   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)for (loop_iterator li((cfun + 0), &(loop), LI_FROM_INNERMOST
); (loop); (loop) = li.next ())
     if (loop->header->count.initialized_p ())
       fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
     	   loop->num,
     	   (int)expected_loop_iterations_unbounded (loop));
 }
return 0;
4125}

4127} // anon namespace

4129gimple_opt_pass *
4130make_pass_profile (gcc::context *ctxt)
4131{
return new pass_profile (ctxt);
4133}

4135/* Return true when PRED predictor should be removed after early
 tree passes.  Most of the predictors are beneficial to survive
 as early inlining can also distribute then into caller's bodies.  */

4139static bool
4140strip_predictor_early (enum br_predictor pred)
4141{
switch (pred)
  {
  case PRED_TREE_EARLY_RETURN:
    return true;
  default:
    return false;
  }
4149}

4151/* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
 we no longer need.  EARLY is set to true when called from early
 optimizations.  */

4155unsigned int
4156strip_predict_hints (function *fun, bool early)
4157{
basic_block bb;
gimple *ass_stmt;
tree var;
bool changed = false;

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)
  {
    gimple_stmt_iterator bi;
    for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
{
 gimple *stmt = gsi_stmt (bi);

 if (gimple_code (stmt) == GIMPLE_PREDICT)
   {
     if (!early
  || strip_predictor_early (gimple_predict_predictor (stmt)))
{
  gsi_remove (&bi, true);
  changed = true;
  continue;
}
   }
 else if (is_gimple_call (stmt))
   {
     tree fndecl = gimple_call_fndecl (stmt);

     if (!early
  && ((fndecl != NULL_TREE(tree) nullptr
       && fndecl_built_in_p (fndecl, BUILT_IN_EXPECT)
       && gimple_call_num_args (stmt) == 2)
      || (fndecl != NULL_TREE(tree) nullptr
	  && fndecl_built_in_p (fndecl,
				BUILT_IN_EXPECT_WITH_PROBABILITY)
	  && gimple_call_num_args (stmt) == 3)
      || (gimple_call_internal_p (stmt)
	  && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)))
{
  var = gimple_call_lhs (stmt);
         changed = true;
  if (var)
    {
      ass_stmt
	= gimple_build_assign (var, gimple_call_arg (stmt, 0));
      gsi_replace (&bi, ass_stmt, true);
    }
  else
    {
      gsi_remove (&bi, true);
      continue;
    }
}
   }
 gsi_next (&bi);
}
  }
return changed ? TODO_cleanup_cfg(1 << 5) : 0;
4214}

4216namespace {

4218const pass_data pass_data_strip_predict_hints =
4219{
GIMPLE_PASS, /* type */
"*strip_predict_hints", /* name */
OPTGROUP_NONE, /* optinfo_flags */
TV_BRANCH_PROB, /* tv_id */
PROP_cfg(1 << 3), /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
0, /* todo_flags_finish */
4229};

4231class pass_strip_predict_hints : public gimple_opt_pass
4232{
4233public:
pass_strip_predict_hints (gcc::context *ctxt)
  : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
{}

/* opt_pass methods: */
opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
void set_pass_param (unsigned int n, bool param)
  {
    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));
    early_p = param;
  }

virtual unsigned int execute (function *);

4248private:
bool early_p;

4251}; // class pass_strip_predict_hints

4253unsigned int
4254pass_strip_predict_hints::execute (function *fun)
4255{
return strip_predict_hints (fun, early_p);
4257}

4259} // anon namespace

4261gimple_opt_pass *
4262make_pass_strip_predict_hints (gcc::context *ctxt)
4263{
return new pass_strip_predict_hints (ctxt);
4265}

4267/* Rebuild function frequencies.  Passes are in general expected to
 maintain profile by hand, however in some cases this is not possible:
 for example when inlining several functions with loops freuqencies might run
 out of scale and thus needs to be recomputed.  */

4272void
4273rebuild_frequencies (void)
4274{
timevar_push (TV_REBUILD_FREQUENCIES);

/* When the max bb count in the function is small, there is a higher
   chance that there were truncation errors in the integer scaling
   of counts by inlining and other optimizations. This could lead
   to incorrect classification of code as being cold when it isn't.
   In that case, force the estimation of bb counts/frequencies from the
   branch probabilities, rather than computing frequencies from counts,
   which may also lead to frequencies incorrectly reduced to 0. There
   is less precision in the probabilities, so we only do this for small
   max counts.  */
cfun(cfun + 0)->cfg->count_max = profile_count::uninitialized ();
basic_block bb;
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)
  cfun(cfun + 0)->cfg->count_max = cfun(cfun + 0)->cfg->count_max.max (bb->count);

if (profile_status_for_fn (cfun)(((cfun + 0))->cfg->x_profile_status) == PROFILE_GUESSED)
  {
    loop_optimizer_init (0);
    add_noreturn_fake_exit_edges ();
    mark_irreducible_loops ();
    connect_infinite_loops_to_exit ();
    estimate_bb_frequencies (true);
    remove_fake_exit_edges ();
    loop_optimizer_finalize ();
  }
else if (profile_status_for_fn (cfun)(((cfun + 0))->cfg->x_profile_status) == PROFILE_READ)
  update_max_bb_count ();
else if (profile_status_for_fn (cfun)(((cfun + 0))->cfg->x_profile_status) == PROFILE_ABSENT
  && !flag_guess_branch_probglobal_options.x_flag_guess_branch_prob)
  ;
else
  gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/predict.c"
, 4307, __FUNCTION__));
timevar_pop (TV_REBUILD_FREQUENCIES);
4309}

4311/* Perform a dry run of the branch prediction pass and report comparsion of
 the predicted and real profile into the dump file.  */

4314void
4315report_predictor_hitrates (void)
4316{
unsigned nb_loops;

loop_optimizer_init (LOOPS_NORMAL(LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
));
if (dump_file && (dump_flags & TDF_DETAILS))
  flow_loops_dump (dump_file, NULLnullptr, 0);

mark_irreducible_loops ();

nb_loops = number_of_loops (cfun(cfun + 0));
if (nb_loops > 1)
  scev_initialize ();

tree_estimate_probability (true);

if (nb_loops > 1)
  scev_finalize ();

loop_optimizer_finalize ();
4335}

4337/* Force edge E to be cold.
 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
 keep low probability to represent possible error in a guess.  This is used
 i.e. in case we predict loop to likely iterate given number of times but
 we are not 100% sure.

 This function locally updates profile without attempt to keep global
 consistency which cannot be reached in full generality without full profile
 rebuild from probabilities alone.  Doing so is not necessarily a good idea
 because frequencies and counts may be more realistic then probabilities.

 In some cases (such as for elimination of early exits during full loop
 unrolling) the caller can ensure that profile will get consistent
 afterwards.  */

4352void
4353force_edge_cold (edge e, bool impossible)
4354{
profile_count count_sum = profile_count::zero ();
profile_probability prob_sum = profile_probability::never ();
edge_iterator ei;
edge e2;
bool uninitialized_exit = false;

/* When branch probability guesses are not known, then do nothing.  */
if (!impossible && !e->count ().initialized_p ())
  return;

profile_probability goal = (impossible ? profile_probability::never ()
	      : profile_probability::very_unlikely ());

/* If edge is already improbably or cold, just return.  */
if (e->probability <= goal
    && (!impossible || e->count () == profile_count::zero ()))
  return;
FOR_EACH_EDGE (e2, ei, e->src->succs)for ((ei) = ei_start_1 (&((e->src->succs))); ei_cond
 ((ei), &(e2)); ei_next (&(ei)))
  if (e2 != e)
    {
if (e->flags & EDGE_FAKE)
 continue;
if (e2->count ().initialized_p ())
 count_sum += e2->count ();
if (e2->probability.initialized_p ())
 prob_sum += e2->probability;
else 
 uninitialized_exit = true;
    }

/* If we are not guessing profiles but have some other edges out,
   just assume the control flow goes elsewhere.  */
if (uninitialized_exit)
  e->probability = goal;
/* If there are other edges out of e->src, redistribute probabilitity
   there.  */
else if (prob_sum > profile_probability::never ())
  {
    if (!(e->probability < goal))
e->probability = goal;

    profile_probability prob_comp = prob_sum / e->probability.invert ();

    if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Making edge %i->%i %s by redistributing "
 "probability to other edges.\n",
 e->src->index, e->dest->index,
 impossible ? "impossible" : "cold");
    FOR_EACH_EDGE (e2, ei, e->src->succs)for ((ei) = ei_start_1 (&((e->src->succs))); ei_cond
 ((ei), &(e2)); ei_next (&(ei)))
if (e2 != e)
 {
   e2->probability /= prob_comp;
 }
    if (current_ir_type () != IR_GIMPLE
 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr))
update_br_prob_note (e->src);
  }
/* If all edges out of e->src are unlikely, the basic block itself
   is unlikely.  */
else
  {
    if (prob_sum == profile_probability::never ())
      e->probability = profile_probability::always ();
    else
{
 if (impossible)
   e->probability = profile_probability::never ();
 /* If BB has some edges out that are not impossible, we cannot
    assume that BB itself is.  */
 impossible = false;
}
    if (current_ir_type () != IR_GIMPLE
 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr))
update_br_prob_note (e->src);
    if (e->src->count == profile_count::zero ())
return;
    if (count_sum == profile_count::zero () && impossible)
{
 bool found = false;
 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)(((cfun + 0))->cfg->x_entry_block_ptr))
   ;
 else if (current_ir_type () == IR_GIMPLE)
   for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
        !gsi_end_p (gsi); gsi_next (&gsi))
     {
       if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
  {
    found = true;
           break;
  }
     }
 /* FIXME: Implement RTL path.  */
 else 
   found = true;
 if (!found)
   {
     if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
	 "Making bb %i impossible and dropping count to 0.\n",
	 e->src->index);
     e->src->count = profile_count::zero ();
     FOR_EACH_EDGE (e2, ei, e->src->preds)for ((ei) = ei_start_1 (&((e->src->preds))); ei_cond
 ((ei), &(e2)); ei_next (&(ei)))
force_edge_cold (e2, impossible);
     return;
   }
}

    /* If we did not adjusting, the source basic block has no likely edeges
 leaving other direction. In that case force that bb cold, too.
This in general is difficult task to do, but handle special case when
BB has only one predecestor.  This is common case when we are updating
after loop transforms.  */
    if (!(prob_sum > profile_probability::never ())
 && count_sum == profile_count::zero ()
 && single_pred_p (e->src) && e->src->count.to_frequency (cfun(cfun + 0))
    > (impossible ? 0 : 1))
{
 int old_frequency = e->src->count.to_frequency (cfun(cfun + 0));
 if (dump_file && (dump_flags & TDF_DETAILS))
   fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
     impossible ? "impossible" : "cold");
 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))
		   impossible ? 0 : 1)((e->src->count.to_frequency ((cfun + 0))) < (impossible
 ? 0 : 1) ? (e->src->count.to_frequency ((cfun + 0))) :
 (impossible ? 0 : 1));
 if (impossible)
   e->src->count = profile_count::zero ();
 else
   e->src->count = e->count ().apply_scale (new_frequency,
				     old_frequency);
 force_edge_cold (single_pred_edge (e->src), impossible);
}
    else if (dump_file && (dump_flags & TDF_DETAILS)
      && maybe_hot_bb_p (cfun(cfun + 0), e->src))
fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
 impossible ? "impossible" : "cold");
  }
4490}

4492#if CHECKING_P1

4494namespace selftest {

4496/* Test that value range of predictor values defined in predict.def is
 within range (50, 100].  */

4499struct branch_predictor
4500{
const char *name;
int probability;
4503};

4505#define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },

4507static void
4508test_prediction_value_range ()
4509{
branch_predictor predictors[] = {
4511#include "predict.def"
  { NULLnullptr, PROB_UNINITIALIZED(-1) }
};

for (unsigned i = 0; predictors[i].name != NULLnullptr; i++)
  {
    if (predictors[i].probability == PROB_UNINITIALIZED(-1))
continue;

    unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE10000;
    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);
  }
4523}

4525#undef DEF_PREDICTOR

4527/* Run all of the selfests within this file.  */

4529void
4530predict_c_tests ()
4531{
test_prediction_value_range ();
4533}

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
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21	#ifndef GCC_PROFILE_COUNT_H
22	#define GCC_PROFILE_COUNT_H
23
24	struct function;
25	struct profile_count;
26	class sreal;
27
28	/* Quality of the profile count. Because gengtype does not support enums
29	inside of classes, this is in global namespace. */
30	enum 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
68	extern const char *profile_quality_as_string (enum profile_quality);
69	extern 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
77	bool slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res);
78
79	/* Compute RES=(ab + c/2)/c capping and return false if overflow happened. /
80
81	inline bool
82	safe_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
146	class 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;
159	public:
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
690	struct GTY(()) profile_count
691	{
692	public:
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;
699	private:
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;
714	public:
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 ()