LCOV - code coverage report
Current view: top level - gcc - predict.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1887 2021 93.4 %
Date: 2020-04-04 11:58:09 Functions: 97 105 92.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

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

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.