LCOV - code coverage report
Current view: top level - gcc - value-prof.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 82.7 % 970 802
Test Date: 2024-03-23 14:05:01 Functions: 93.0 % 43 40
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Transformations based on profile information for values.
       2                 :             :    Copyright (C) 2003-2024 Free Software Foundation, Inc.
       3                 :             : 
       4                 :             : This file is part of GCC.
       5                 :             : 
       6                 :             : GCC is free software; you can redistribute it and/or modify it under
       7                 :             : the terms of the GNU General Public License as published by the Free
       8                 :             : Software Foundation; either version 3, or (at your option) any later
       9                 :             : version.
      10                 :             : 
      11                 :             : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :             : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :             : for more details.
      15                 :             : 
      16                 :             : You should have received a copy of the GNU General Public License
      17                 :             : along with GCC; see the file COPYING3.  If not see
      18                 :             : <http://www.gnu.org/licenses/>.  */
      19                 :             : 
      20                 :             : #include "config.h"
      21                 :             : #include "system.h"
      22                 :             : #include "coretypes.h"
      23                 :             : #include "backend.h"
      24                 :             : #include "rtl.h"
      25                 :             : #include "tree.h"
      26                 :             : #include "gimple.h"
      27                 :             : #include "cfghooks.h"
      28                 :             : #include "ssa.h"
      29                 :             : #include "cgraph.h"
      30                 :             : #include "coverage.h"
      31                 :             : #include "data-streamer.h"
      32                 :             : #include "diagnostic.h"
      33                 :             : #include "fold-const.h"
      34                 :             : #include "tree-nested.h"
      35                 :             : #include "calls.h"
      36                 :             : #include "expr.h"
      37                 :             : #include "value-prof.h"
      38                 :             : #include "tree-eh.h"
      39                 :             : #include "gimplify.h"
      40                 :             : #include "gimple-iterator.h"
      41                 :             : #include "tree-cfg.h"
      42                 :             : #include "gimple-pretty-print.h"
      43                 :             : #include "dumpfile.h"
      44                 :             : #include "builtins.h"
      45                 :             : 
      46                 :             : /* In this file value profile based optimizations are placed.  Currently the
      47                 :             :    following optimizations are implemented (for more detailed descriptions
      48                 :             :    see comments at value_profile_transformations):
      49                 :             : 
      50                 :             :    1) Division/modulo specialization.  Provided that we can determine that the
      51                 :             :       operands of the division have some special properties, we may use it to
      52                 :             :       produce more effective code.
      53                 :             : 
      54                 :             :    2) Indirect/virtual call specialization. If we can determine most
      55                 :             :       common function callee in indirect/virtual call. We can use this
      56                 :             :       information to improve code effectiveness (especially info for
      57                 :             :       the inliner).
      58                 :             : 
      59                 :             :    3) Speculative prefetching.  If we are able to determine that the difference
      60                 :             :       between addresses accessed by a memory reference is usually constant, we
      61                 :             :       may add the prefetch instructions.
      62                 :             :       FIXME: This transformation was removed together with RTL based value
      63                 :             :       profiling.
      64                 :             : 
      65                 :             : 
      66                 :             :    Value profiling internals
      67                 :             :    ==========================
      68                 :             : 
      69                 :             :    Every value profiling transformation starts with defining what values
      70                 :             :    to profile.  There are different histogram types (see HIST_TYPE_* in
      71                 :             :    value-prof.h) and each transformation can request one or more histogram
      72                 :             :    types per GIMPLE statement.  The function gimple_find_values_to_profile()
      73                 :             :    collects the values to profile in a vec, and adds the number of counters
      74                 :             :    required for the different histogram types.
      75                 :             : 
      76                 :             :    For a -fprofile-generate run, the statements for which values should be
      77                 :             :    recorded, are instrumented in instrument_values().  The instrumentation
      78                 :             :    is done by helper functions that can be found in tree-profile.cc, where
      79                 :             :    new types of histograms can be added if necessary.
      80                 :             : 
      81                 :             :    After a -fprofile-use, the value profiling data is read back in by
      82                 :             :    compute_value_histograms() that translates the collected data to
      83                 :             :    histograms and attaches them to the profiled statements via
      84                 :             :    gimple_add_histogram_value().  Histograms are stored in a hash table
      85                 :             :    that is attached to every intrumented function, see VALUE_HISTOGRAMS
      86                 :             :    in function.h.
      87                 :             :    
      88                 :             :    The value-profile transformations driver is the function
      89                 :             :    gimple_value_profile_transformations().  It traverses all statements in
      90                 :             :    the to-be-transformed function, and looks for statements with one or
      91                 :             :    more histograms attached to it.  If a statement has histograms, the
      92                 :             :    transformation functions are called on the statement.
      93                 :             : 
      94                 :             :    Limitations / FIXME / TODO:
      95                 :             :    * Only one histogram of each type can be associated with a statement.
      96                 :             :    * Some value profile transformations are done in builtins.cc (?!)
      97                 :             :    * Updating of histograms needs some TLC.
      98                 :             :    * The value profiling code could be used to record analysis results
      99                 :             :      from non-profiling (e.g. VRP).
     100                 :             :    * Adding new profilers should be simplified, starting with a cleanup
     101                 :             :      of what-happens-where and with making gimple_find_values_to_profile
     102                 :             :      and gimple_value_profile_transformations table-driven, perhaps...
     103                 :             : */
     104                 :             : 
     105                 :             : static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);
     106                 :             : static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);
     107                 :             : static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);
     108                 :             : static bool gimple_stringops_transform (gimple_stmt_iterator *);
     109                 :             : static void dump_ic_profile (gimple_stmt_iterator *gsi);
     110                 :             : 
     111                 :             : /* Allocate histogram value.  */
     112                 :             : 
     113                 :             : histogram_value
     114                 :        1265 : gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
     115                 :             :                               enum hist_type type, gimple *stmt, tree value)
     116                 :             : {
     117                 :        1265 :    histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
     118                 :        1265 :    hist->hvalue.value = value;
     119                 :        1265 :    hist->hvalue.stmt = stmt;
     120                 :        1265 :    hist->type = type;
     121                 :        1265 :    return hist;
     122                 :             : }
     123                 :             : 
     124                 :             : /* Hash value for histogram.  */
     125                 :             : 
     126                 :             : static hashval_t
     127                 :           0 : histogram_hash (const void *x)
     128                 :             : {
     129                 :           0 :   return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt);
     130                 :             : }
     131                 :             : 
     132                 :             : /* Return nonzero if statement for histogram_value X is Y.  */
     133                 :             : 
     134                 :             : static int
     135                 :       52949 : histogram_eq (const void *x, const void *y)
     136                 :             : {
     137                 :       52949 :   return ((const_histogram_value) x)->hvalue.stmt == (const gimple *) y;
     138                 :             : }
     139                 :             : 
     140                 :             : /* Set histogram for STMT.  */
     141                 :             : 
     142                 :             : static void
     143                 :         526 : set_histogram_value (struct function *fun, gimple *stmt, histogram_value hist)
     144                 :             : {
     145                 :         526 :   void **loc;
     146                 :         526 :   if (!hist && !VALUE_HISTOGRAMS (fun))
     147                 :             :     return;
     148                 :         526 :   if (!VALUE_HISTOGRAMS (fun))
     149                 :         312 :     VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
     150                 :             :                                            histogram_eq, NULL);
     151                 :         597 :   loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
     152                 :             :                                   htab_hash_pointer (stmt),
     153                 :             :                                   hist ? INSERT : NO_INSERT);
     154                 :         526 :   if (!hist)
     155                 :             :     {
     156                 :          71 :       if (loc)
     157                 :          71 :         htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
     158                 :          71 :       return;
     159                 :             :     }
     160                 :         455 :   *loc = hist;
     161                 :             : }
     162                 :             : 
     163                 :             : /* Get histogram list for STMT.  */
     164                 :             : 
     165                 :             : histogram_value
     166                 : 10668588675 : gimple_histogram_value (struct function *fun, gimple *stmt)
     167                 :             : {
     168                 : 10668588675 :   if (!VALUE_HISTOGRAMS (fun))
     169                 :             :     return NULL;
     170                 :      313471 :   return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
     171                 :      313471 :                                                 htab_hash_pointer (stmt));
     172                 :             : }
     173                 :             : 
     174                 :             : /* Add histogram for STMT.  */
     175                 :             : 
     176                 :             : void
     177                 :         439 : gimple_add_histogram_value (struct function *fun, gimple *stmt,
     178                 :             :                             histogram_value hist)
     179                 :             : {
     180                 :         439 :   hist->hvalue.next = gimple_histogram_value (fun, stmt);
     181                 :         439 :   set_histogram_value (fun, stmt, hist);
     182                 :         439 :   hist->fun = fun;
     183                 :         439 : }
     184                 :             : 
     185                 :             : /* Remove histogram HIST from STMT's histogram list.  */
     186                 :             : 
     187                 :             : void
     188                 :         122 : gimple_remove_histogram_value (struct function *fun, gimple *stmt,
     189                 :             :                                histogram_value hist)
     190                 :             : {
     191                 :         122 :   histogram_value hist2 = gimple_histogram_value (fun, stmt);
     192                 :         122 :   if (hist == hist2)
     193                 :             :     {
     194                 :          87 :       set_histogram_value (fun, stmt, hist->hvalue.next);
     195                 :             :     }
     196                 :             :   else
     197                 :             :     {
     198                 :          53 :       while (hist2->hvalue.next != hist)
     199                 :             :         hist2 = hist2->hvalue.next;
     200                 :          35 :       hist2->hvalue.next = hist->hvalue.next;
     201                 :             :     }
     202                 :         122 :   free (hist->hvalue.counters);
     203                 :         122 :   if (flag_checking)
     204                 :             :     memset (hist, 0xab, sizeof (*hist));
     205                 :         122 :   free (hist);
     206                 :         122 : }
     207                 :             : 
     208                 :             : /* Lookup histogram of type TYPE in the STMT.  */
     209                 :             : 
     210                 :             : histogram_value
     211                 :      255686 : gimple_histogram_value_of_type (struct function *fun, gimple *stmt,
     212                 :             :                                 enum hist_type type)
     213                 :             : {
     214                 :      255686 :   histogram_value hist;
     215                 :      255745 :   for (hist = gimple_histogram_value (fun, stmt); hist;
     216                 :          59 :        hist = hist->hvalue.next)
     217                 :         178 :     if (hist->type == type)
     218                 :         119 :       return hist;
     219                 :             :   return NULL;
     220                 :             : }
     221                 :             : 
     222                 :             : /* Dump information about HIST to DUMP_FILE.  */
     223                 :             : 
     224                 :             : static void
     225                 :         256 : dump_histogram_value (FILE *dump_file, histogram_value hist)
     226                 :             : {
     227                 :         256 :   switch (hist->type)
     228                 :             :     {
     229                 :          13 :     case HIST_TYPE_INTERVAL:
     230                 :          13 :       if (hist->hvalue.counters)
     231                 :             :         {
     232                 :           5 :           fprintf (dump_file, "Interval counter range [%d,%d]: [",
     233                 :             :                    hist->hdata.intvl.int_start,
     234                 :           5 :                    (hist->hdata.intvl.int_start
     235                 :           5 :                     + hist->hdata.intvl.steps - 1));
     236                 :             : 
     237                 :           5 :           unsigned int i;
     238                 :          20 :           for (i = 0; i < hist->hdata.intvl.steps; i++)
     239                 :             :             {
     240                 :          10 :               fprintf (dump_file, "%d:%" PRId64,
     241                 :          10 :                        hist->hdata.intvl.int_start + i,
     242                 :          10 :                        (int64_t) hist->hvalue.counters[i]);
     243                 :          10 :               if (i != hist->hdata.intvl.steps - 1)
     244                 :           5 :                 fprintf (dump_file, ", ");
     245                 :             :             }
     246                 :           5 :           fprintf (dump_file, "] outside range: %" PRId64 ".\n",
     247                 :           5 :                    (int64_t) hist->hvalue.counters[i]);
     248                 :             :         }
     249                 :             :       break;
     250                 :             : 
     251                 :          16 :     case HIST_TYPE_POW2:
     252                 :          16 :       if (hist->hvalue.counters)
     253                 :           8 :         fprintf (dump_file, "Pow2 counter pow2:%" PRId64
     254                 :             :                  " nonpow2:%" PRId64 ".\n",
     255                 :             :                  (int64_t) hist->hvalue.counters[1],
     256                 :             :                  (int64_t) hist->hvalue.counters[0]);
     257                 :             :       break;
     258                 :             : 
     259                 :         109 :     case HIST_TYPE_TOPN_VALUES:
     260                 :         109 :     case HIST_TYPE_INDIR_CALL:
     261                 :         109 :       if (hist->hvalue.counters)
     262                 :             :         {
     263                 :          67 :           fprintf (dump_file,
     264                 :             :                    (hist->type == HIST_TYPE_TOPN_VALUES
     265                 :             :                     ? "Top N value counter" : "Indirect call counter"));
     266                 :          47 :           if (hist->hvalue.counters)
     267                 :             :             {
     268                 :          47 :               unsigned count = hist->hvalue.counters[1];
     269                 :          47 :               fprintf (dump_file, " all: %" PRId64 ", %" PRId64 " values: ",
     270                 :             :                        (int64_t) hist->hvalue.counters[0], (int64_t) count);
     271                 :         115 :               for (unsigned i = 0; i < count; i++)
     272                 :             :                 {
     273                 :          68 :                   fprintf (dump_file, "[%" PRId64 ":%" PRId64 "]",
     274                 :          68 :                            (int64_t) hist->hvalue.counters[2 * i + 2],
     275                 :          68 :                            (int64_t) hist->hvalue.counters[2 * i + 3]);
     276                 :          68 :                   if (i != count - 1)
     277                 :          25 :                     fprintf (dump_file, ", ");
     278                 :             :                 }
     279                 :          47 :               fprintf (dump_file, ".\n");
     280                 :             :             }
     281                 :             :         }
     282                 :             :       break;
     283                 :             : 
     284                 :          59 :     case HIST_TYPE_AVERAGE:
     285                 :          59 :       if (hist->hvalue.counters)
     286                 :          31 :         fprintf (dump_file, "Average value sum:%" PRId64
     287                 :             :                  " times:%" PRId64 ".\n",
     288                 :             :                  (int64_t) hist->hvalue.counters[0],
     289                 :             :                  (int64_t) hist->hvalue.counters[1]);
     290                 :             :       break;
     291                 :             : 
     292                 :          59 :     case HIST_TYPE_IOR:
     293                 :          59 :       if (hist->hvalue.counters)
     294                 :          31 :         fprintf (dump_file, "IOR value ior:%" PRId64 ".\n",
     295                 :             :                  (int64_t) hist->hvalue.counters[0]);
     296                 :             :       break;
     297                 :             : 
     298                 :           0 :     case HIST_TYPE_TIME_PROFILE:
     299                 :           0 :       if (hist->hvalue.counters)
     300                 :           0 :         fprintf (dump_file, "Time profile time:%" PRId64 ".\n",
     301                 :             :                  (int64_t) hist->hvalue.counters[0]);
     302                 :             :       break;
     303                 :           0 :     default:
     304                 :           0 :       gcc_unreachable ();
     305                 :             :    }
     306                 :         256 : }
     307                 :             : 
     308                 :             : /* Dump information about HIST to DUMP_FILE.  */
     309                 :             : 
     310                 :             : void
     311                 :           1 : stream_out_histogram_value (struct output_block *ob, histogram_value hist)
     312                 :             : {
     313                 :           2 :   struct bitpack_d bp;
     314                 :           2 :   unsigned int i;
     315                 :             : 
     316                 :           2 :   bp = bitpack_create (ob->main_stream);
     317                 :           2 :   bp_pack_enum (&bp, hist_type, HIST_TYPE_MAX, hist->type);
     318                 :           2 :   bp_pack_value (&bp, hist->hvalue.next != NULL, 1);
     319                 :           2 :   streamer_write_bitpack (&bp);
     320                 :           2 :   switch (hist->type)
     321                 :             :     {
     322                 :           0 :     case HIST_TYPE_INTERVAL:
     323                 :           0 :       streamer_write_hwi (ob, hist->hdata.intvl.int_start);
     324                 :           0 :       streamer_write_uhwi (ob, hist->hdata.intvl.steps);
     325                 :           0 :       break;
     326                 :             :     default:
     327                 :             :       break;
     328                 :             :     }
     329                 :           8 :   for (i = 0; i < hist->n_counters; i++)
     330                 :             :     {
     331                 :             :       /* When user uses an unsigned type with a big value, constant converted
     332                 :             :          to gcov_type (a signed type) can be negative.  */
     333                 :           6 :       gcov_type value = hist->hvalue.counters[i];
     334                 :           6 :       streamer_write_gcov_count (ob, value);
     335                 :             :     }
     336                 :           2 :   if (hist->hvalue.next)
     337                 :             :     stream_out_histogram_value (ob, hist->hvalue.next);
     338                 :           1 : }
     339                 :             : 
     340                 :             : /* Dump information about HIST to DUMP_FILE.  */
     341                 :             : 
     342                 :             : void
     343                 :           1 : stream_in_histogram_value (class lto_input_block *ib, gimple *stmt)
     344                 :             : {
     345                 :           1 :   enum hist_type type;
     346                 :           1 :   unsigned int ncounters = 0;
     347                 :           1 :   struct bitpack_d bp;
     348                 :           1 :   unsigned int i;
     349                 :           1 :   histogram_value new_val;
     350                 :           1 :   bool next;
     351                 :           1 :   histogram_value *next_p = NULL;
     352                 :             : 
     353                 :           4 :   do
     354                 :             :     {
     355                 :           2 :       bp = streamer_read_bitpack (ib);
     356                 :           2 :       type = bp_unpack_enum (&bp, hist_type, HIST_TYPE_MAX);
     357                 :           2 :       next = bp_unpack_value (&bp, 1);
     358                 :           2 :       new_val = gimple_alloc_histogram_value (cfun, type, stmt);
     359                 :           2 :       switch (type)
     360                 :             :         {
     361                 :           0 :         case HIST_TYPE_INTERVAL:
     362                 :           0 :           new_val->hdata.intvl.int_start = streamer_read_hwi (ib);
     363                 :           0 :           new_val->hdata.intvl.steps = streamer_read_uhwi (ib);
     364                 :           0 :           ncounters = new_val->hdata.intvl.steps + 2;
     365                 :           0 :           break;
     366                 :             : 
     367                 :           1 :         case HIST_TYPE_POW2:
     368                 :           1 :         case HIST_TYPE_AVERAGE:
     369                 :           1 :           ncounters = 2;
     370                 :           1 :           break;
     371                 :             : 
     372                 :             :         case HIST_TYPE_TOPN_VALUES:
     373                 :             :         case HIST_TYPE_INDIR_CALL:
     374                 :             :           break;
     375                 :             : 
     376                 :           0 :         case HIST_TYPE_IOR:
     377                 :           0 :         case HIST_TYPE_TIME_PROFILE:
     378                 :           0 :           ncounters = 1;
     379                 :           0 :           break;
     380                 :             : 
     381                 :           0 :         default:
     382                 :           0 :           gcc_unreachable ();
     383                 :             :         }
     384                 :             : 
     385                 :             :       /* TOP N counters have variable number of counters.  */
     386                 :           2 :       if (type == HIST_TYPE_INDIR_CALL || type == HIST_TYPE_TOPN_VALUES)
     387                 :             :         {
     388                 :           1 :           gcov_type total = streamer_read_gcov_count (ib);
     389                 :           1 :           gcov_type ncounters = streamer_read_gcov_count (ib);
     390                 :           1 :           new_val->hvalue.counters = XNEWVAR (gcov_type,
     391                 :             :                                               sizeof (*new_val->hvalue.counters)
     392                 :             :                                               * (2 + 2 * ncounters));
     393                 :           1 :           new_val->hvalue.counters[0] = total;
     394                 :           1 :           new_val->hvalue.counters[1] = ncounters;
     395                 :           1 :           new_val->n_counters = 2 + 2 * ncounters;
     396                 :           3 :           for (i = 0; i < 2 * ncounters; i++)
     397                 :           2 :             new_val->hvalue.counters[2 + i] = streamer_read_gcov_count (ib);
     398                 :             :         }
     399                 :             :       else
     400                 :             :         {
     401                 :           1 :           new_val->hvalue.counters = XNEWVAR (gcov_type,
     402                 :             :                                               sizeof (*new_val->hvalue.counters)
     403                 :             :                                               * ncounters);
     404                 :           1 :           new_val->n_counters = ncounters;
     405                 :           3 :           for (i = 0; i < ncounters; i++)
     406                 :           2 :             new_val->hvalue.counters[i] = streamer_read_gcov_count (ib);
     407                 :             :         }
     408                 :             : 
     409                 :           2 :       if (!next_p)
     410                 :           1 :         gimple_add_histogram_value (cfun, stmt, new_val);
     411                 :             :       else
     412                 :           1 :         *next_p = new_val;
     413                 :           2 :       next_p = &new_val->hvalue.next;
     414                 :             :     }
     415                 :             :   while (next);
     416                 :           1 : }
     417                 :             : 
     418                 :             : /* Dump all histograms attached to STMT to DUMP_FILE.  */
     419                 :             : 
     420                 :             : void
     421                 :     1023647 : dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple *stmt)
     422                 :             : {
     423                 :     1023647 :   histogram_value hist;
     424                 :     1023769 :   for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
     425                 :         122 :     dump_histogram_value (dump_file, hist);
     426                 :     1023647 : }
     427                 :             : 
     428                 :             : /* Remove all histograms associated with STMT.  */
     429                 :             : 
     430                 :             : void
     431                 :    98567501 : gimple_remove_stmt_histograms (struct function *fun, gimple *stmt)
     432                 :             : {
     433                 :    98567501 :   histogram_value val;
     434                 :    98567520 :   while ((val = gimple_histogram_value (fun, stmt)) != NULL)
     435                 :          19 :     gimple_remove_histogram_value (fun, stmt, val);
     436                 :    98567501 : }
     437                 :             : 
     438                 :             : /* Duplicate all histograms associates with OSTMT to STMT.  */
     439                 :             : 
     440                 :             : void
     441                 :    79991123 : gimple_duplicate_stmt_histograms (struct function *fun, gimple *stmt,
     442                 :             :                                   struct function *ofun, gimple *ostmt)
     443                 :             : {
     444                 :    79991123 :   histogram_value val;
     445                 :    79991131 :   for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
     446                 :             :     {
     447                 :           8 :       histogram_value new_val = gimple_alloc_histogram_value (fun, val->type);
     448                 :           8 :       memcpy (new_val, val, sizeof (*val));
     449                 :           8 :       new_val->hvalue.stmt = stmt;
     450                 :           8 :       new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
     451                 :           8 :       memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
     452                 :           8 :       gimple_add_histogram_value (fun, stmt, new_val);
     453                 :             :     }
     454                 :    79991123 : }
     455                 :             : 
     456                 :             : /* Move all histograms associated with OSTMT to STMT.  */
     457                 :             : 
     458                 :             : void
     459                 :           0 : gimple_move_stmt_histograms (struct function *fun, gimple *stmt, gimple *ostmt)
     460                 :             : {
     461                 :           0 :   histogram_value val = gimple_histogram_value (fun, ostmt);
     462                 :           0 :   if (val)
     463                 :             :     {
     464                 :             :       /* The following three statements can't be reordered,
     465                 :             :          because histogram hashtab relies on stmt field value
     466                 :             :          for finding the exact slot. */
     467                 :           0 :       set_histogram_value (fun, ostmt, NULL);
     468                 :           0 :       for (; val != NULL; val = val->hvalue.next)
     469                 :           0 :         val->hvalue.stmt = stmt;
     470                 :           0 :       set_histogram_value (fun, stmt, val);
     471                 :             :     }
     472                 :           0 : }
     473                 :             : 
     474                 :             : static bool error_found = false;
     475                 :             : 
     476                 :             : /* Helper function for verify_histograms.  For each histogram reachable via htab
     477                 :             :    walk verify that it was reached via statement walk.  */
     478                 :             : 
     479                 :             : static int
     480                 :       32551 : visit_hist (void **slot, void *data)
     481                 :             : {
     482                 :       32551 :   hash_set<histogram_value> *visited = (hash_set<histogram_value> *) data;
     483                 :       32551 :   histogram_value hist = *(histogram_value *) slot;
     484                 :             : 
     485                 :       32551 :   if (!visited->contains (hist)
     486                 :       32551 :       && hist->type != HIST_TYPE_TIME_PROFILE)
     487                 :             :     {
     488                 :           0 :       error ("dead histogram");
     489                 :           0 :       dump_histogram_value (stderr, hist);
     490                 :           0 :       debug_gimple_stmt (hist->hvalue.stmt);
     491                 :           0 :       error_found = true;
     492                 :             :     }
     493                 :       32551 :   return 1;
     494                 :             : }
     495                 :             : 
     496                 :             : /* Verify sanity of the histograms.  */
     497                 :             : 
     498                 :             : DEBUG_FUNCTION void
     499                 :   223371093 : verify_histograms (void)
     500                 :             : {
     501                 :   223371093 :   basic_block bb;
     502                 :   223371093 :   gimple_stmt_iterator gsi;
     503                 :   223371093 :   histogram_value hist;
     504                 :             : 
     505                 :   223371093 :   error_found = false;
     506                 :   223371093 :   hash_set<histogram_value> visited_hists;
     507                 :  1958574536 :   FOR_EACH_BB_FN (bb, cfun)
     508                 : 13957527262 :     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     509                 :             :       {
     510                 : 10487120376 :         gimple *stmt = gsi_stmt (gsi);
     511                 :             : 
     512                 : 10487125411 :         for (hist = gimple_histogram_value (cfun, stmt); hist;
     513                 :        5035 :              hist = hist->hvalue.next)
     514                 :             :           {
     515                 :        5035 :             if (hist->hvalue.stmt != stmt)
     516                 :             :               {
     517                 :           0 :                 error ("histogram value statement does not correspond to "
     518                 :             :                        "the statement it is associated with");
     519                 :           0 :                 debug_gimple_stmt (stmt);
     520                 :           0 :                 dump_histogram_value (stderr, hist);
     521                 :           0 :                 error_found = true;
     522                 :             :               }
     523                 :        5035 :             visited_hists.add (hist);
     524                 :             :           }
     525                 :             :       }
     526                 :   223371093 :   if (VALUE_HISTOGRAMS (cfun))
     527                 :       30203 :     htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, &visited_hists);
     528                 :   223371093 :   if (error_found)
     529                 :           0 :     internal_error ("%qs failed", __func__);
     530                 :   223371093 : }
     531                 :             : 
     532                 :             : /* Helper function for verify_histograms.  For each histogram reachable via htab
     533                 :             :    walk verify that it was reached via statement walk.  */
     534                 :             : 
     535                 :             : static int
     536                 :         300 : free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
     537                 :             : {
     538                 :         300 :   histogram_value hist = *(histogram_value *) slot;
     539                 :         300 :   free (hist->hvalue.counters);
     540                 :         300 :   free (hist);
     541                 :         300 :   return 1;
     542                 :             : }
     543                 :             : 
     544                 :             : void
     545                 :     1420357 : free_histograms (struct function *fn)
     546                 :             : {
     547                 :     1420357 :   if (VALUE_HISTOGRAMS (fn))
     548                 :             :     {
     549                 :         297 :       htab_traverse (VALUE_HISTOGRAMS (fn), free_hist, NULL);
     550                 :         297 :       htab_delete (VALUE_HISTOGRAMS (fn));
     551                 :         297 :       VALUE_HISTOGRAMS (fn) = NULL;
     552                 :             :     }
     553                 :     1420357 : }
     554                 :             : 
     555                 :             : /* The overall number of invocations of the counter should match
     556                 :             :    execution count of basic block.  Report it as error rather than
     557                 :             :    internal error as it might mean that user has misused the profile
     558                 :             :    somehow.  */
     559                 :             : 
     560                 :             : static bool
     561                 :          41 : check_counter (gimple *stmt, const char * name,
     562                 :             :                gcov_type *count, gcov_type *all, profile_count bb_count_d)
     563                 :             : {
     564                 :          41 :   gcov_type bb_count = bb_count_d.ipa ().to_gcov_type ();
     565                 :          41 :   if (*all != bb_count || *count > *all)
     566                 :             :     {
     567                 :           0 :       dump_user_location_t locus;
     568                 :           0 :       locus = ((stmt != NULL)
     569                 :           0 :                ? dump_user_location_t (stmt)
     570                 :             :                : dump_user_location_t::from_function_decl
     571                 :           0 :                    (current_function_decl));
     572                 :           0 :       if (flag_profile_correction)
     573                 :             :         {
     574                 :           0 :           if (dump_enabled_p ())
     575                 :           0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, locus,
     576                 :             :                              "correcting inconsistent value profile: %s "
     577                 :             :                              "profiler overall count (%d) does not match BB "
     578                 :           0 :                              "count (%d)\n", name, (int)*all, (int)bb_count);
     579                 :           0 :           *all = bb_count;
     580                 :           0 :           if (*count > *all)
     581                 :           0 :             *count = *all;
     582                 :           0 :           return false;
     583                 :             :         }
     584                 :             :       else
     585                 :             :         {
     586                 :           0 :           error_at (locus.get_location_t (), "corrupted value profile: %s "
     587                 :             :                     "profile counter (%d out of %d) inconsistent with "
     588                 :             :                     "basic-block count (%d)",
     589                 :             :                     name,
     590                 :           0 :                     (int) *count,
     591                 :           0 :                     (int) *all,
     592                 :             :                     (int) bb_count);
     593                 :           0 :           return true;
     594                 :             :         }
     595                 :             :     }
     596                 :             : 
     597                 :             :   return false;
     598                 :             : }
     599                 :             : 
     600                 :             : /* GIMPLE based transformations. */
     601                 :             : 
     602                 :             : bool
     603                 :         327 : gimple_value_profile_transformations (void)
     604                 :             : {
     605                 :         327 :   basic_block bb;
     606                 :         327 :   gimple_stmt_iterator gsi;
     607                 :         327 :   bool changed = false;
     608                 :             : 
     609                 :        1753 :   FOR_EACH_BB_FN (bb, cfun)
     610                 :             :     {
     611                 :        5163 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     612                 :             :         {
     613                 :        2311 :           gimple *stmt = gsi_stmt (gsi);
     614                 :        2311 :           histogram_value th = gimple_histogram_value (cfun, stmt);
     615                 :        2311 :           if (!th)
     616                 :        2241 :             continue;
     617                 :             : 
     618                 :          70 :           if (dump_file)
     619                 :             :             {
     620                 :          31 :               fprintf (dump_file, "Trying transformations on stmt ");
     621                 :          31 :               print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
     622                 :          31 :               dump_histograms_for_stmt (cfun, dump_file, stmt);
     623                 :             :             }
     624                 :             : 
     625                 :             :           /* Transformations:  */
     626                 :             :           /* The order of things in this conditional controls which
     627                 :             :              transformation is used when more than one is applicable.  */
     628                 :             :           /* It is expected that any code added by the transformations
     629                 :             :              will be added before the current statement, and that the
     630                 :             :              current statement remain valid (although possibly
     631                 :             :              modified) upon return.  */
     632                 :          70 :           if (gimple_mod_subtract_transform (&gsi)
     633                 :          66 :               || gimple_divmod_fixed_value_transform (&gsi)
     634                 :          62 :               || gimple_mod_pow2_value_transform (&gsi)
     635                 :         132 :               || gimple_stringops_transform (&gsi))
     636                 :             :             {
     637                 :          19 :               stmt = gsi_stmt (gsi);
     638                 :          19 :               changed = true;
     639                 :             :               /* Original statement may no longer be in the same block. */
     640                 :          19 :               if (bb != gimple_bb (stmt))
     641                 :             :                 {
     642                 :          19 :                   bb = gimple_bb (stmt);
     643                 :          19 :                   gsi = gsi_for_stmt (stmt);
     644                 :             :                 }
     645                 :             :             }
     646                 :             : 
     647                 :             :           /* The function never thansforms a GIMPLE statement.  */
     648                 :          70 :           if (dump_enabled_p ())
     649                 :          31 :             dump_ic_profile (&gsi);
     650                 :             :         }
     651                 :             :     }
     652                 :             : 
     653                 :         327 :   return changed;
     654                 :             : }
     655                 :             : 
     656                 :             : /* Generate code for transformation 1 (with parent gimple assignment
     657                 :             :    STMT and probability of taking the optimal path PROB, which is
     658                 :             :    equivalent to COUNT/ALL within roundoff error).  This generates the
     659                 :             :    result into a temp and returns the temp; it does not replace or
     660                 :             :    alter the original STMT.  */
     661                 :             : 
     662                 :             : static tree
     663                 :           4 : gimple_divmod_fixed_value (gassign *stmt, tree value, profile_probability prob,
     664                 :             :                            gcov_type count, gcov_type all)
     665                 :             : {
     666                 :           4 :   gassign *stmt1, *stmt2;
     667                 :           4 :   gcond *stmt3;
     668                 :           4 :   tree tmp0, tmp1, tmp2;
     669                 :           4 :   gimple *bb1end, *bb2end, *bb3end;
     670                 :           4 :   basic_block bb, bb2, bb3, bb4;
     671                 :           4 :   tree optype, op1, op2;
     672                 :           4 :   edge e12, e13, e23, e24, e34;
     673                 :           4 :   gimple_stmt_iterator gsi;
     674                 :             : 
     675                 :           8 :   gcc_assert (is_gimple_assign (stmt)
     676                 :             :               && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
     677                 :             :                   || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR));
     678                 :             : 
     679                 :           4 :   optype = TREE_TYPE (gimple_assign_lhs (stmt));
     680                 :           4 :   op1 = gimple_assign_rhs1 (stmt);
     681                 :           4 :   op2 = gimple_assign_rhs2 (stmt);
     682                 :             : 
     683                 :           4 :   bb = gimple_bb (stmt);
     684                 :           4 :   gsi = gsi_for_stmt (stmt);
     685                 :             : 
     686                 :           4 :   tmp0 = make_temp_ssa_name (optype, NULL, "PROF");
     687                 :           4 :   tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
     688                 :           4 :   stmt1 = gimple_build_assign (tmp0, fold_convert (optype, value));
     689                 :           4 :   stmt2 = gimple_build_assign (tmp1, op2);
     690                 :           4 :   stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
     691                 :           4 :   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
     692                 :           4 :   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
     693                 :           4 :   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
     694                 :           4 :   bb1end = stmt3;
     695                 :             : 
     696                 :           4 :   tmp2 = create_tmp_reg (optype, "PROF");
     697                 :           4 :   stmt1 = gimple_build_assign (tmp2, gimple_assign_rhs_code (stmt), op1, tmp0);
     698                 :           4 :   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
     699                 :           4 :   bb2end = stmt1;
     700                 :             : 
     701                 :           4 :   stmt1 = gimple_build_assign (tmp2, gimple_assign_rhs_code (stmt), op1, op2);
     702                 :           4 :   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
     703                 :           4 :   bb3end = stmt1;
     704                 :             : 
     705                 :             :   /* Fix CFG. */
     706                 :             :   /* Edge e23 connects bb2 to bb3, etc. */
     707                 :           4 :   e12 = split_block (bb, bb1end);
     708                 :           4 :   bb2 = e12->dest;
     709                 :           4 :   bb2->count = profile_count::from_gcov_type (count);
     710                 :           4 :   e23 = split_block (bb2, bb2end);
     711                 :           4 :   bb3 = e23->dest;
     712                 :           4 :   bb3->count = profile_count::from_gcov_type (all - count);
     713                 :           4 :   e34 = split_block (bb3, bb3end);
     714                 :           4 :   bb4 = e34->dest;
     715                 :           4 :   bb4->count = profile_count::from_gcov_type (all);
     716                 :             : 
     717                 :           4 :   e12->flags &= ~EDGE_FALLTHRU;
     718                 :           4 :   e12->flags |= EDGE_FALSE_VALUE;
     719                 :           4 :   e12->probability = prob;
     720                 :             : 
     721                 :           4 :   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
     722                 :           4 :   e13->probability = prob.invert ();
     723                 :             : 
     724                 :           4 :   remove_edge (e23);
     725                 :             : 
     726                 :           4 :   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
     727                 :           4 :   e24->probability = profile_probability::always ();
     728                 :             : 
     729                 :           4 :   e34->probability = profile_probability::always ();
     730                 :             : 
     731                 :           4 :   return tmp2;
     732                 :             : }
     733                 :             : 
     734                 :             : /* Return the n-th value count of TOPN_VALUE histogram.  If
     735                 :             :    there's a value, return true and set VALUE and COUNT
     736                 :             :    arguments.
     737                 :             : 
     738                 :             :    Counters have the following meaning.
     739                 :             : 
     740                 :             :    abs (counters[0]) is the number of executions
     741                 :             :    for i in 0 ... TOPN-1
     742                 :             :      counters[2 * i + 2] is target
     743                 :             :      counters[2 * i + 3] is corresponding hitrate counter.
     744                 :             : 
     745                 :             :    Value of counters[0] negative when counter became
     746                 :             :    full during merging and some values are lost.  */
     747                 :             : 
     748                 :             : bool
     749                 :        1328 : get_nth_most_common_value (gimple *stmt, const char *counter_type,
     750                 :             :                            histogram_value hist, gcov_type *value,
     751                 :             :                            gcov_type *count, gcov_type *all, unsigned n)
     752                 :             : {
     753                 :        1328 :   unsigned counters = hist->hvalue.counters[1];
     754                 :        1328 :   if (n >= counters)
     755                 :             :     return false;
     756                 :             : 
     757                 :          84 :   *count = 0;
     758                 :          84 :   *value = 0;
     759                 :             : 
     760                 :          84 :   gcov_type read_all = abs_hwi (hist->hvalue.counters[0]);
     761                 :          84 :   gcov_type covered = 0;
     762                 :         252 :   for (unsigned i = 0; i < counters; ++i)
     763                 :         168 :     covered += hist->hvalue.counters[2 * i + 3];
     764                 :             : 
     765                 :          84 :   gcov_type v = hist->hvalue.counters[2 * n + 2];
     766                 :          84 :   gcov_type c = hist->hvalue.counters[2 * n + 3];
     767                 :             : 
     768                 :          84 :   if (hist->hvalue.counters[0] < 0
     769                 :           0 :       && flag_profile_reproducible == PROFILE_REPRODUCIBILITY_PARALLEL_RUNS)
     770                 :             :     {
     771                 :           0 :       if (dump_file)
     772                 :           0 :         fprintf (dump_file, "Histogram value dropped in '%s' mode\n",
     773                 :             :                  "-fprofile-reproducible=parallel-runs");
     774                 :           0 :       return false;
     775                 :             :     }
     776                 :          84 :   else if (covered != read_all
     777                 :           1 :            && flag_profile_reproducible == PROFILE_REPRODUCIBILITY_MULTITHREADED)
     778                 :             :     {
     779                 :           0 :       if (dump_file)
     780                 :           0 :         fprintf (dump_file, "Histogram value dropped in '%s' mode\n",
     781                 :             :                  "-fprofile-reproducible=multithreaded");
     782                 :           0 :       return false;
     783                 :             :     }
     784                 :             : 
     785                 :             :   /* Indirect calls can't be verified.  */
     786                 :          84 :   if (stmt
     787                 :         105 :       && check_counter (stmt, counter_type, &c, &read_all,
     788                 :          21 :                         gimple_bb (stmt)->count))
     789                 :             :     return false;
     790                 :             : 
     791                 :          84 :   *all = read_all;
     792                 :             : 
     793                 :          84 :   *value = v;
     794                 :          84 :   *count = c;
     795                 :          84 :   return true;
     796                 :             : }
     797                 :             : 
     798                 :             : /* Do transform 1) on INSN if applicable.  */
     799                 :             : 
     800                 :             : static bool
     801                 :          66 : gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
     802                 :             : {
     803                 :          66 :   histogram_value histogram;
     804                 :          66 :   enum tree_code code;
     805                 :          66 :   gcov_type val, count, all;
     806                 :          66 :   tree result, value, tree_val;
     807                 :          66 :   profile_probability prob;
     808                 :          66 :   gassign *stmt;
     809                 :             : 
     810                 :          68 :   stmt = dyn_cast <gassign *> (gsi_stmt (*si));
     811                 :           6 :   if (!stmt)
     812                 :             :     return false;
     813                 :             : 
     814                 :           6 :   if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
     815                 :             :     return false;
     816                 :             : 
     817                 :           6 :   code = gimple_assign_rhs_code (stmt);
     818                 :             : 
     819                 :           6 :   if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
     820                 :             :     return false;
     821                 :             : 
     822                 :           6 :   histogram = gimple_histogram_value_of_type (cfun, stmt,
     823                 :             :                                               HIST_TYPE_TOPN_VALUES);
     824                 :           6 :   if (!histogram)
     825                 :             :     return false;
     826                 :             : 
     827                 :           6 :   if (!get_nth_most_common_value (stmt, "divmod", histogram, &val, &count,
     828                 :             :                                   &all))
     829                 :             :     return false;
     830                 :             : 
     831                 :           4 :   value = histogram->hvalue.value;
     832                 :           4 :   gimple_remove_histogram_value (cfun, stmt, histogram);
     833                 :             : 
     834                 :             :   /* We require that count is at least half of all.  */
     835                 :           8 :   if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
     836                 :           4 :       || 2 * count < all
     837                 :           8 :       || optimize_bb_for_size_p (gimple_bb (stmt)))
     838                 :           0 :     return false;
     839                 :             : 
     840                 :             :   /* Compute probability of taking the optimal path.  */
     841                 :           4 :   if (all > 0)
     842                 :           4 :     prob = profile_probability::probability_in_gcov_type (count, all);
     843                 :             :   else
     844                 :           0 :     prob = profile_probability::never ();
     845                 :             : 
     846                 :           4 :   if (sizeof (gcov_type) == sizeof (HOST_WIDE_INT))
     847                 :           4 :     tree_val = build_int_cst (get_gcov_type (), val);
     848                 :             :   else
     849                 :             :     {
     850                 :             :       HOST_WIDE_INT a[2];
     851                 :             :       a[0] = (unsigned HOST_WIDE_INT) val;
     852                 :             :       a[1] = val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1;
     853                 :             : 
     854                 :             :       tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2,
     855                 :             :         TYPE_PRECISION (get_gcov_type ()), false));
     856                 :             :     }
     857                 :           4 :   result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all);
     858                 :             : 
     859                 :           4 :   if (dump_enabled_p ())
     860                 :           3 :     dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
     861                 :             :                      "Transformation done: div/mod by constant %T\n", tree_val);
     862                 :             : 
     863                 :           4 :   gimple_assign_set_rhs_from_tree (si, result);
     864                 :           4 :   update_stmt (gsi_stmt (*si));
     865                 :             : 
     866                 :           4 :   return true;
     867                 :             : }
     868                 :             : 
     869                 :             : /* Generate code for transformation 2 (with parent gimple assign STMT and
     870                 :             :    probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
     871                 :             :    within roundoff error).  This generates the result into a temp and returns
     872                 :             :    the temp; it does not replace or alter the original STMT.  */
     873                 :             : 
     874                 :             : static tree
     875                 :           0 : gimple_mod_pow2 (gassign *stmt, profile_probability prob, gcov_type count, gcov_type all)
     876                 :             : {
     877                 :           0 :   gassign *stmt1, *stmt2, *stmt3;
     878                 :           0 :   gcond *stmt4;
     879                 :           0 :   tree tmp2, tmp3;
     880                 :           0 :   gimple *bb1end, *bb2end, *bb3end;
     881                 :           0 :   basic_block bb, bb2, bb3, bb4;
     882                 :           0 :   tree optype, op1, op2;
     883                 :           0 :   edge e12, e13, e23, e24, e34;
     884                 :           0 :   gimple_stmt_iterator gsi;
     885                 :           0 :   tree result;
     886                 :             : 
     887                 :           0 :   gcc_assert (is_gimple_assign (stmt)
     888                 :             :               && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
     889                 :             : 
     890                 :           0 :   optype = TREE_TYPE (gimple_assign_lhs (stmt));
     891                 :           0 :   op1 = gimple_assign_rhs1 (stmt);
     892                 :           0 :   op2 = gimple_assign_rhs2 (stmt);
     893                 :             : 
     894                 :           0 :   bb = gimple_bb (stmt);
     895                 :           0 :   gsi = gsi_for_stmt (stmt);
     896                 :             : 
     897                 :           0 :   result = create_tmp_reg (optype, "PROF");
     898                 :           0 :   tmp2 = make_temp_ssa_name (optype, NULL, "PROF");
     899                 :           0 :   tmp3 = make_temp_ssa_name (optype, NULL, "PROF");
     900                 :           0 :   stmt2 = gimple_build_assign (tmp2, PLUS_EXPR, op2,
     901                 :           0 :                                build_int_cst (optype, -1));
     902                 :           0 :   stmt3 = gimple_build_assign (tmp3, BIT_AND_EXPR, tmp2, op2);
     903                 :           0 :   stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0),
     904                 :             :                              NULL_TREE, NULL_TREE);
     905                 :           0 :   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
     906                 :           0 :   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
     907                 :           0 :   gsi_insert_before (&gsi, stmt4, GSI_SAME_STMT);
     908                 :           0 :   bb1end = stmt4;
     909                 :             : 
     910                 :             :   /* tmp2 == op2-1 inherited from previous block.  */
     911                 :           0 :   stmt1 = gimple_build_assign (result, BIT_AND_EXPR, op1, tmp2);
     912                 :           0 :   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
     913                 :           0 :   bb2end = stmt1;
     914                 :             : 
     915                 :           0 :   stmt1 = gimple_build_assign (result, gimple_assign_rhs_code (stmt),
     916                 :             :                                op1, op2);
     917                 :           0 :   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
     918                 :           0 :   bb3end = stmt1;
     919                 :             : 
     920                 :             :   /* Fix CFG. */
     921                 :             :   /* Edge e23 connects bb2 to bb3, etc. */
     922                 :           0 :   e12 = split_block (bb, bb1end);
     923                 :           0 :   bb2 = e12->dest;
     924                 :           0 :   bb2->count = profile_count::from_gcov_type (count);
     925                 :           0 :   e23 = split_block (bb2, bb2end);
     926                 :           0 :   bb3 = e23->dest;
     927                 :           0 :   bb3->count = profile_count::from_gcov_type (all - count);
     928                 :           0 :   e34 = split_block (bb3, bb3end);
     929                 :           0 :   bb4 = e34->dest;
     930                 :           0 :   bb4->count = profile_count::from_gcov_type (all);
     931                 :             : 
     932                 :           0 :   e12->flags &= ~EDGE_FALLTHRU;
     933                 :           0 :   e12->flags |= EDGE_FALSE_VALUE;
     934                 :           0 :   e12->probability = prob;
     935                 :             : 
     936                 :           0 :   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
     937                 :           0 :   e13->probability = prob.invert ();
     938                 :             : 
     939                 :           0 :   remove_edge (e23);
     940                 :             : 
     941                 :           0 :   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
     942                 :           0 :   e24->probability = profile_probability::always ();
     943                 :             : 
     944                 :           0 :   e34->probability = profile_probability::always ();
     945                 :             : 
     946                 :           0 :   return result;
     947                 :             : }
     948                 :             : 
     949                 :             : /* Do transform 2) on INSN if applicable.  */
     950                 :             : 
     951                 :             : static bool
     952                 :          62 : gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
     953                 :             : {
     954                 :          62 :   histogram_value histogram;
     955                 :          62 :   enum tree_code code;
     956                 :          62 :   gcov_type count, wrong_values, all;
     957                 :          62 :   tree lhs_type, result, value;
     958                 :          62 :   profile_probability prob;
     959                 :          62 :   gassign *stmt;
     960                 :             : 
     961                 :          64 :   stmt = dyn_cast <gassign *> (gsi_stmt (*si));
     962                 :           2 :   if (!stmt)
     963                 :             :     return false;
     964                 :             : 
     965                 :           2 :   lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
     966                 :           2 :   if (!INTEGRAL_TYPE_P (lhs_type))
     967                 :             :     return false;
     968                 :             : 
     969                 :           2 :   code = gimple_assign_rhs_code (stmt);
     970                 :             : 
     971                 :           2 :   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
     972                 :             :     return false;
     973                 :             : 
     974                 :           0 :   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
     975                 :           0 :   if (!histogram)
     976                 :             :     return false;
     977                 :             : 
     978                 :           0 :   value = histogram->hvalue.value;
     979                 :           0 :   wrong_values = histogram->hvalue.counters[0];
     980                 :           0 :   count = histogram->hvalue.counters[1];
     981                 :             : 
     982                 :           0 :   gimple_remove_histogram_value (cfun, stmt, histogram);
     983                 :             : 
     984                 :             :   /* We require that we hit a power of 2 at least half of all evaluations.  */
     985                 :           0 :   if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
     986                 :           0 :       || count < wrong_values
     987                 :           0 :       || optimize_bb_for_size_p (gimple_bb (stmt)))
     988                 :           0 :     return false;
     989                 :             : 
     990                 :             :   /* Compute probability of taking the optimal path.  */
     991                 :           0 :   all = count + wrong_values;
     992                 :             : 
     993                 :           0 :   if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count))
     994                 :             :     return false;
     995                 :             : 
     996                 :           0 :   if (dump_enabled_p ())
     997                 :           0 :     dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
     998                 :             :                      "Transformation done: mod power of 2\n");
     999                 :             : 
    1000                 :           0 :   if (all > 0)
    1001                 :           0 :     prob = profile_probability::probability_in_gcov_type (count, all);
    1002                 :             :   else
    1003                 :           0 :     prob = profile_probability::never ();
    1004                 :             : 
    1005                 :           0 :   result = gimple_mod_pow2 (stmt, prob, count, all);
    1006                 :             : 
    1007                 :           0 :   gimple_assign_set_rhs_from_tree (si, result);
    1008                 :           0 :   update_stmt (gsi_stmt (*si));
    1009                 :             : 
    1010                 :           0 :   return true;
    1011                 :             : }
    1012                 :             : 
    1013                 :             : /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
    1014                 :             :    NCOUNTS the number of cases to support.  Currently only NCOUNTS==0 or 1 is
    1015                 :             :    supported and this is built into this interface.  The probabilities of taking
    1016                 :             :    the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
    1017                 :             :    COUNT2/ALL respectively within roundoff error).  This generates the
    1018                 :             :    result into a temp and returns the temp; it does not replace or alter
    1019                 :             :    the original STMT.  */
    1020                 :             : /* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
    1021                 :             : 
    1022                 :             : static tree
    1023                 :           4 : gimple_mod_subtract (gassign *stmt, profile_probability prob1,
    1024                 :             :                      profile_probability prob2, int ncounts,
    1025                 :             :                      gcov_type count1, gcov_type count2, gcov_type all)
    1026                 :             : {
    1027                 :           4 :   gassign *stmt1;
    1028                 :           4 :   gimple *stmt2;
    1029                 :           4 :   gcond *stmt3;
    1030                 :           4 :   tree tmp1;
    1031                 :           4 :   gimple *bb1end, *bb2end = NULL, *bb3end;
    1032                 :           4 :   basic_block bb, bb2, bb3, bb4;
    1033                 :           4 :   tree optype, op1, op2;
    1034                 :           4 :   edge e12, e23 = 0, e24, e34, e14;
    1035                 :           4 :   gimple_stmt_iterator gsi;
    1036                 :           4 :   tree result;
    1037                 :             : 
    1038                 :           8 :   gcc_assert (is_gimple_assign (stmt)
    1039                 :             :               && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
    1040                 :             : 
    1041                 :           4 :   optype = TREE_TYPE (gimple_assign_lhs (stmt));
    1042                 :           4 :   op1 = gimple_assign_rhs1 (stmt);
    1043                 :           4 :   op2 = gimple_assign_rhs2 (stmt);
    1044                 :             : 
    1045                 :           4 :   bb = gimple_bb (stmt);
    1046                 :           4 :   gsi = gsi_for_stmt (stmt);
    1047                 :             : 
    1048                 :           4 :   result = create_tmp_reg (optype, "PROF");
    1049                 :           4 :   tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
    1050                 :           4 :   stmt1 = gimple_build_assign (result, op1);
    1051                 :           4 :   stmt2 = gimple_build_assign (tmp1, op2);
    1052                 :           4 :   stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
    1053                 :           4 :   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
    1054                 :           4 :   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
    1055                 :           4 :   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
    1056                 :           4 :   bb1end = stmt3;
    1057                 :             : 
    1058                 :           4 :   if (ncounts)  /* Assumed to be 0 or 1 */
    1059                 :             :     {
    1060                 :           1 :       stmt1 = gimple_build_assign (result, MINUS_EXPR, result, tmp1);
    1061                 :           1 :       stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
    1062                 :           1 :       gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
    1063                 :           1 :       gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
    1064                 :           1 :       bb2end = stmt2;
    1065                 :             :     }
    1066                 :             : 
    1067                 :             :   /* Fallback case. */
    1068                 :           4 :   stmt1 = gimple_build_assign (result, gimple_assign_rhs_code (stmt),
    1069                 :             :                                result, tmp1);
    1070                 :           4 :   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
    1071                 :           4 :   bb3end = stmt1;
    1072                 :             : 
    1073                 :             :   /* Fix CFG. */
    1074                 :             :   /* Edge e23 connects bb2 to bb3, etc. */
    1075                 :             :   /* However block 3 is optional; if it is not there, references
    1076                 :             :      to 3 really refer to block 2. */
    1077                 :           4 :   e12 = split_block (bb, bb1end);
    1078                 :           4 :   bb2 = e12->dest;
    1079                 :           4 :   bb2->count = profile_count::from_gcov_type (all - count1);
    1080                 :             : 
    1081                 :           4 :   if (ncounts)  /* Assumed to be 0 or 1.  */
    1082                 :             :     {
    1083                 :           1 :       e23 = split_block (bb2, bb2end);
    1084                 :           1 :       bb3 = e23->dest;
    1085                 :           1 :       bb3->count = profile_count::from_gcov_type (all - count1 - count2);
    1086                 :             :     }
    1087                 :             : 
    1088                 :           7 :   e34 = split_block (ncounts ? bb3 : bb2, bb3end);
    1089                 :           4 :   bb4 = e34->dest;
    1090                 :           4 :   bb4->count = profile_count::from_gcov_type (all);
    1091                 :             : 
    1092                 :           4 :   e12->flags &= ~EDGE_FALLTHRU;
    1093                 :           4 :   e12->flags |= EDGE_FALSE_VALUE;
    1094                 :           4 :   e12->probability = prob1.invert ();
    1095                 :             : 
    1096                 :           4 :   e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
    1097                 :           4 :   e14->probability = prob1;
    1098                 :             : 
    1099                 :           4 :   if (ncounts)  /* Assumed to be 0 or 1.  */
    1100                 :             :     {
    1101                 :           1 :       e23->flags &= ~EDGE_FALLTHRU;
    1102                 :           1 :       e23->flags |= EDGE_FALSE_VALUE;
    1103                 :           1 :       e23->probability = prob2.invert ();
    1104                 :             : 
    1105                 :           1 :       e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
    1106                 :           1 :       e24->probability = prob2;
    1107                 :             :     }
    1108                 :             : 
    1109                 :           4 :   e34->probability = profile_probability::always ();
    1110                 :             : 
    1111                 :           4 :   return result;
    1112                 :             : }
    1113                 :             : 
    1114                 :             : /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable.  */
    1115                 :             : 
    1116                 :             : static bool
    1117                 :          70 : gimple_mod_subtract_transform (gimple_stmt_iterator *si)
    1118                 :             : {
    1119                 :          70 :   histogram_value histogram;
    1120                 :          70 :   enum tree_code code;
    1121                 :          70 :   gcov_type count, wrong_values, all;
    1122                 :          70 :   tree lhs_type, result;
    1123                 :          70 :   profile_probability prob1, prob2;
    1124                 :          70 :   unsigned int i, steps;
    1125                 :          70 :   gcov_type count1, count2;
    1126                 :          70 :   gassign *stmt;
    1127                 :          76 :   stmt = dyn_cast <gassign *> (gsi_stmt (*si));
    1128                 :          10 :   if (!stmt)
    1129                 :             :     return false;
    1130                 :             : 
    1131                 :          10 :   lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
    1132                 :          10 :   if (!INTEGRAL_TYPE_P (lhs_type))
    1133                 :             :     return false;
    1134                 :             : 
    1135                 :          10 :   code = gimple_assign_rhs_code (stmt);
    1136                 :             : 
    1137                 :          10 :   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
    1138                 :             :     return false;
    1139                 :             : 
    1140                 :           5 :   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
    1141                 :           5 :   if (!histogram)
    1142                 :             :     return false;
    1143                 :             : 
    1144                 :           5 :   all = 0;
    1145                 :           5 :   wrong_values = 0;
    1146                 :          15 :   for (i = 0; i < histogram->hdata.intvl.steps; i++)
    1147                 :          10 :     all += histogram->hvalue.counters[i];
    1148                 :             : 
    1149                 :           5 :   wrong_values += histogram->hvalue.counters[i];
    1150                 :           5 :   wrong_values += histogram->hvalue.counters[i+1];
    1151                 :           5 :   steps = histogram->hdata.intvl.steps;
    1152                 :           5 :   all += wrong_values;
    1153                 :           5 :   count1 = histogram->hvalue.counters[0];
    1154                 :           5 :   count2 = histogram->hvalue.counters[1];
    1155                 :             : 
    1156                 :           5 :   if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count))
    1157                 :             :     {
    1158                 :           0 :       gimple_remove_histogram_value (cfun, stmt, histogram);
    1159                 :           0 :       return false;
    1160                 :             :     }
    1161                 :             : 
    1162                 :           5 :   if (flag_profile_correction && count1 + count2 > all)
    1163                 :           0 :       all = count1 + count2;
    1164                 :             : 
    1165                 :           5 :   gcc_assert (count1 + count2 <= all);
    1166                 :             : 
    1167                 :             :   /* We require that we use just subtractions in at least 50% of all
    1168                 :             :      evaluations.  */
    1169                 :             :   count = 0;
    1170                 :           8 :   for (i = 0; i < histogram->hdata.intvl.steps; i++)
    1171                 :             :     {
    1172                 :           7 :       count += histogram->hvalue.counters[i];
    1173                 :           7 :       if (count * 2 >= all)
    1174                 :             :         break;
    1175                 :             :     }
    1176                 :           5 :   if (i == steps
    1177                 :           5 :       || optimize_bb_for_size_p (gimple_bb (stmt)))
    1178                 :           1 :     return false;
    1179                 :             : 
    1180                 :           4 :   gimple_remove_histogram_value (cfun, stmt, histogram);
    1181                 :           4 :   if (dump_enabled_p ())
    1182                 :           3 :     dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
    1183                 :             :                      "Transformation done: mod subtract\n");
    1184                 :             : 
    1185                 :             :   /* Compute probability of taking the optimal path(s).  */
    1186                 :           4 :   if (all > 0)
    1187                 :             :     {
    1188                 :           4 :       prob1 = profile_probability::probability_in_gcov_type (count1, all);
    1189                 :           4 :       if (all == count1)
    1190                 :           3 :         prob2 = profile_probability::even ();
    1191                 :             :       else
    1192                 :           1 :         prob2 = profile_probability::probability_in_gcov_type (count2, all
    1193                 :             :                                                                - count1);
    1194                 :             :     }
    1195                 :             :   else
    1196                 :             :     {
    1197                 :           0 :       prob1 = prob2 = profile_probability::never ();
    1198                 :             :     }
    1199                 :             : 
    1200                 :             :   /* In practice, "steps" is always 2.  This interface reflects this,
    1201                 :             :      and will need to be changed if "steps" can change.  */
    1202                 :           4 :   result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all);
    1203                 :             : 
    1204                 :           4 :   gimple_assign_set_rhs_from_tree (si, result);
    1205                 :           4 :   update_stmt (gsi_stmt (*si));
    1206                 :             : 
    1207                 :           4 :   return true;
    1208                 :             : }
    1209                 :             : 
    1210                 :             : typedef int_hash <unsigned int, 0, UINT_MAX> profile_id_hash;
    1211                 :             : 
    1212                 :             : static hash_map<profile_id_hash, cgraph_node *> *cgraph_node_map = 0;
    1213                 :             : 
    1214                 :             : /* Returns true if node graph is initialized. This
    1215                 :             :    is used to test if profile_id has been created
    1216                 :             :    for cgraph_nodes.  */
    1217                 :             : 
    1218                 :             : bool
    1219                 :        3176 : coverage_node_map_initialized_p (void)
    1220                 :             : {
    1221                 :        3176 :   return cgraph_node_map != 0;
    1222                 :             : }
    1223                 :             : 
    1224                 :             : /* Initialize map from PROFILE_ID to CGRAPH_NODE.
    1225                 :             :    When LOCAL is true, the PROFILE_IDs are computed.  when it is false we assume
    1226                 :             :    that the PROFILE_IDs was already assigned.  */
    1227                 :             : 
    1228                 :             : void
    1229                 :         617 : init_node_map (bool local)
    1230                 :             : {
    1231                 :         617 :   struct cgraph_node *n;
    1232                 :         617 :   cgraph_node_map = new hash_map<profile_id_hash, cgraph_node *>;
    1233                 :             : 
    1234                 :        3127 :   FOR_EACH_DEFINED_FUNCTION (n)
    1235                 :        2510 :     if (n->has_gimple_body_p () || n->thunk)
    1236                 :             :       {
    1237                 :        2298 :         cgraph_node **val;
    1238                 :        2298 :         dump_user_location_t loc
    1239                 :        2298 :           = dump_user_location_t::from_function_decl (n->decl);
    1240                 :        2298 :         if (local)
    1241                 :             :           {
    1242                 :        2131 :             n->profile_id = coverage_compute_profile_id (n);
    1243                 :        2131 :             while ((val = cgraph_node_map->get (n->profile_id))
    1244                 :        2131 :                    || !n->profile_id)
    1245                 :             :               {
    1246                 :           0 :                 if (dump_enabled_p ())
    1247                 :           0 :                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
    1248                 :             :                                    "Local profile-id %i conflict"
    1249                 :             :                                    " with nodes %s %s\n",
    1250                 :             :                                    n->profile_id,
    1251                 :             :                                    n->dump_name (),
    1252                 :             :                                    (*val)->dump_name ());
    1253                 :           0 :                 n->profile_id = (n->profile_id + 1) & 0x7fffffff;
    1254                 :             :               }
    1255                 :             :           }
    1256                 :         167 :         else if (!n->profile_id)
    1257                 :             :           {
    1258                 :          47 :             if (dump_enabled_p ())
    1259                 :          46 :               dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
    1260                 :             :                                "Node %s has no profile-id"
    1261                 :             :                                " (profile feedback missing?)\n",
    1262                 :             :                                n->dump_name ());
    1263                 :          47 :             continue;
    1264                 :             :           }
    1265                 :         120 :         else if ((val = cgraph_node_map->get (n->profile_id)))
    1266                 :             :           {
    1267                 :           0 :             if (dump_enabled_p ())
    1268                 :           0 :               dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
    1269                 :             :                                "Node %s has IP profile-id %i conflict. "
    1270                 :             :                                "Giving up.\n",
    1271                 :             :                                n->dump_name (), n->profile_id);
    1272                 :           0 :             *val = NULL;
    1273                 :           0 :             continue;
    1274                 :             :           }
    1275                 :        2251 :         cgraph_node_map->put (n->profile_id, n);
    1276                 :             :       }
    1277                 :         617 : }
    1278                 :             : 
    1279                 :             : /* Delete the CGRAPH_NODE_MAP.  */
    1280                 :             : 
    1281                 :             : void
    1282                 :         617 : del_node_map (void)
    1283                 :             : {
    1284                 :        1234 :   delete cgraph_node_map;
    1285                 :         617 : }
    1286                 :             : 
    1287                 :             : /* Return cgraph node for function with pid */
    1288                 :             : 
    1289                 :             : struct cgraph_node*
    1290                 :          71 : find_func_by_profile_id (int profile_id)
    1291                 :             : {
    1292                 :          71 :   cgraph_node **val = cgraph_node_map->get (profile_id);
    1293                 :          71 :   if (val)
    1294                 :          69 :     return *val;
    1295                 :             :   else
    1296                 :             :     return NULL;
    1297                 :             : }
    1298                 :             : 
    1299                 :             : /* Do transformation
    1300                 :             : 
    1301                 :             :   if (actual_callee_address == address_of_most_common_function/method)
    1302                 :             :     do direct call
    1303                 :             :   else
    1304                 :             :     old call
    1305                 :             :  */
    1306                 :             : 
    1307                 :             : gcall *
    1308                 :       12423 : gimple_ic (gcall *icall_stmt, struct cgraph_node *direct_call,
    1309                 :             :            profile_probability prob)
    1310                 :             : {
    1311                 :       12423 :   gcall *dcall_stmt;
    1312                 :       12423 :   gassign *load_stmt;
    1313                 :       12423 :   gcond *cond_stmt;
    1314                 :       12423 :   tree tmp0, tmp1, tmp;
    1315                 :       12423 :   basic_block cond_bb, dcall_bb, icall_bb, join_bb = NULL;
    1316                 :       12423 :   edge e_cd, e_ci, e_di, e_dj = NULL, e_ij;
    1317                 :       12423 :   gimple_stmt_iterator gsi;
    1318                 :       12423 :   int lp_nr, dflags;
    1319                 :       12423 :   edge e_eh, e;
    1320                 :       12423 :   edge_iterator ei;
    1321                 :             : 
    1322                 :       12423 :   cond_bb = gimple_bb (icall_stmt);
    1323                 :       12423 :   gsi = gsi_for_stmt (icall_stmt);
    1324                 :             : 
    1325                 :       12423 :   tmp0 = make_temp_ssa_name (ptr_type_node, NULL, "PROF");
    1326                 :       12423 :   tmp1 = make_temp_ssa_name (ptr_type_node, NULL, "PROF");
    1327                 :       12423 :   tmp = unshare_expr (gimple_call_fn (icall_stmt));
    1328                 :       12423 :   load_stmt = gimple_build_assign (tmp0, tmp);
    1329                 :       12423 :   gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
    1330                 :             : 
    1331                 :       12423 :   tmp = fold_convert (ptr_type_node, build_addr (direct_call->decl));
    1332                 :       12423 :   load_stmt = gimple_build_assign (tmp1, tmp);
    1333                 :       12423 :   gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
    1334                 :             : 
    1335                 :       12423 :   cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
    1336                 :       12423 :   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
    1337                 :             : 
    1338                 :       24846 :   if (TREE_CODE (gimple_vdef (icall_stmt)) == SSA_NAME)
    1339                 :             :     {
    1340                 :        2196 :       unlink_stmt_vdef (icall_stmt);
    1341                 :        4392 :       release_ssa_name (gimple_vdef (icall_stmt));
    1342                 :             :     }
    1343                 :       12423 :   gimple_set_vdef (icall_stmt, NULL_TREE);
    1344                 :       12423 :   gimple_set_vuse (icall_stmt, NULL_TREE);
    1345                 :       12423 :   update_stmt (icall_stmt);
    1346                 :       12423 :   dcall_stmt = as_a <gcall *> (gimple_copy (icall_stmt));
    1347                 :       12423 :   gimple_call_set_fndecl (dcall_stmt, direct_call->decl);
    1348                 :       12423 :   dflags = flags_from_decl_or_type (direct_call->decl);
    1349                 :       12423 :   if ((dflags & ECF_NORETURN) != 0
    1350                 :       12423 :       && should_remove_lhs_p (gimple_call_lhs (dcall_stmt)))
    1351                 :           4 :     gimple_call_set_lhs (dcall_stmt, NULL_TREE);
    1352                 :       12423 :   gsi_insert_before (&gsi, dcall_stmt, GSI_SAME_STMT);
    1353                 :             : 
    1354                 :             :   /* Fix CFG. */
    1355                 :             :   /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
    1356                 :       12423 :   e_cd = split_block (cond_bb, cond_stmt);
    1357                 :       12423 :   dcall_bb = e_cd->dest;
    1358                 :       12423 :   dcall_bb->count = cond_bb->count.apply_probability (prob);
    1359                 :             : 
    1360                 :       12423 :   e_di = split_block (dcall_bb, dcall_stmt);
    1361                 :       12423 :   icall_bb = e_di->dest;
    1362                 :       12423 :   icall_bb->count = cond_bb->count - dcall_bb->count;
    1363                 :             : 
    1364                 :             :   /* Do not disturb existing EH edges from the indirect call.  */
    1365                 :       12423 :   if (!stmt_ends_bb_p (icall_stmt))
    1366                 :        8056 :     e_ij = split_block (icall_bb, icall_stmt);
    1367                 :             :   else
    1368                 :             :     {
    1369                 :        4367 :       e_ij = find_fallthru_edge (icall_bb->succs);
    1370                 :             :       /* The indirect call might be noreturn.  */
    1371                 :        4367 :       if (e_ij != NULL)
    1372                 :             :         {
    1373                 :        4367 :           e_ij->probability = profile_probability::always ();
    1374                 :        4367 :           e_ij = single_pred_edge (split_edge (e_ij));
    1375                 :             :         }
    1376                 :             :     }
    1377                 :       12423 :   if (e_ij != NULL)
    1378                 :             :     {
    1379                 :       12423 :       join_bb = e_ij->dest;
    1380                 :       12423 :       join_bb->count = cond_bb->count;
    1381                 :             :     }
    1382                 :             : 
    1383                 :       12423 :   e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
    1384                 :       12423 :   e_cd->probability = prob;
    1385                 :             : 
    1386                 :       12423 :   e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE);
    1387                 :       12423 :   e_ci->probability = prob.invert ();
    1388                 :             : 
    1389                 :       12423 :   remove_edge (e_di);
    1390                 :             : 
    1391                 :       12423 :   if (e_ij != NULL)
    1392                 :             :     {
    1393                 :       12423 :       if ((dflags & ECF_NORETURN) == 0)
    1394                 :             :         {
    1395                 :       12419 :           e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU);
    1396                 :       12419 :           e_dj->probability = profile_probability::always ();
    1397                 :             :         }
    1398                 :       12423 :       e_ij->probability = profile_probability::always ();
    1399                 :             :     }
    1400                 :             : 
    1401                 :             :   /* Insert PHI node for the call result if necessary.  */
    1402                 :       12423 :   if (gimple_call_lhs (icall_stmt)
    1403                 :        9166 :       && TREE_CODE (gimple_call_lhs (icall_stmt)) == SSA_NAME
    1404                 :       20831 :       && (dflags & ECF_NORETURN) == 0)
    1405                 :             :     {
    1406                 :        8404 :       tree result = gimple_call_lhs (icall_stmt);
    1407                 :        8404 :       gphi *phi = create_phi_node (result, join_bb);
    1408                 :        8404 :       gimple_call_set_lhs (icall_stmt,
    1409                 :             :                            duplicate_ssa_name (result, icall_stmt));
    1410                 :        8404 :       add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
    1411                 :        8404 :       gimple_call_set_lhs (dcall_stmt,
    1412                 :             :                            duplicate_ssa_name (result, dcall_stmt));
    1413                 :        8404 :       add_phi_arg (phi, gimple_call_lhs (dcall_stmt), e_dj, UNKNOWN_LOCATION);
    1414                 :             :     }
    1415                 :             : 
    1416                 :             :   /* Build an EH edge for the direct call if necessary.  */
    1417                 :       12423 :   lp_nr = lookup_stmt_eh_lp (icall_stmt);
    1418                 :       12423 :   if (lp_nr > 0 && stmt_could_throw_p (cfun, dcall_stmt))
    1419                 :             :     {
    1420                 :         525 :       add_stmt_to_eh_lp (dcall_stmt, lp_nr);
    1421                 :             :     }
    1422                 :             : 
    1423                 :       29213 :   FOR_EACH_EDGE (e_eh, ei, icall_bb->succs)
    1424                 :       16790 :     if (e_eh->flags & (EDGE_EH | EDGE_ABNORMAL))
    1425                 :             :       {
    1426                 :        4367 :         e = make_edge (dcall_bb, e_eh->dest, e_eh->flags);
    1427                 :        4367 :         e->probability = e_eh->probability;
    1428                 :        4367 :         for (gphi_iterator psi = gsi_start_phis (e_eh->dest);
    1429                 :        8640 :              !gsi_end_p (psi); gsi_next (&psi))
    1430                 :             :           {
    1431                 :        4273 :             gphi *phi = psi.phi ();
    1432                 :        4273 :             SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e),
    1433                 :             :                      PHI_ARG_DEF_FROM_EDGE (phi, e_eh));
    1434                 :             :           }
    1435                 :             :        }
    1436                 :       12423 :   if (!stmt_could_throw_p (cfun, dcall_stmt))
    1437                 :       10596 :     gimple_purge_dead_eh_edges (dcall_bb);
    1438                 :       12423 :   return dcall_stmt;
    1439                 :             : }
    1440                 :             : 
    1441                 :             : /* Dump info about indirect call profile.  */
    1442                 :             : 
    1443                 :             : static void
    1444                 :          31 : dump_ic_profile (gimple_stmt_iterator *gsi)
    1445                 :             : {
    1446                 :          31 :   gcall *stmt;
    1447                 :          31 :   histogram_value histogram;
    1448                 :          31 :   gcov_type val, count, all;
    1449                 :          31 :   struct cgraph_node *direct_call;
    1450                 :             : 
    1451                 :          31 :   stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
    1452                 :          24 :   if (!stmt)
    1453                 :          31 :     return;
    1454                 :             : 
    1455                 :          24 :   if (gimple_call_fndecl (stmt) != NULL_TREE)
    1456                 :             :     return;
    1457                 :             : 
    1458                 :          10 :   if (gimple_call_internal_p (stmt))
    1459                 :             :     return;
    1460                 :             : 
    1461                 :          10 :   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
    1462                 :          10 :   if (!histogram)
    1463                 :             :     return;
    1464                 :             : 
    1465                 :          10 :   count = 0;
    1466                 :          10 :   all = histogram->hvalue.counters[0];
    1467                 :             : 
    1468                 :          22 :   for (unsigned j = 0; j < GCOV_TOPN_MAXIMUM_TRACKED_VALUES; j++)
    1469                 :             :     {
    1470                 :          22 :       if (!get_nth_most_common_value (NULL, "indirect call", histogram, &val,
    1471                 :             :                                       &count, &all, j))
    1472                 :             :         return;
    1473                 :          12 :       if (!count)
    1474                 :           0 :         continue;
    1475                 :             : 
    1476                 :          12 :       direct_call = find_func_by_profile_id ((int) val);
    1477                 :             : 
    1478                 :          12 :       if (direct_call == NULL)
    1479                 :           1 :         dump_printf_loc (
    1480                 :             :           MSG_MISSED_OPTIMIZATION, stmt,
    1481                 :             :           "Indirect call -> direct call from other "
    1482                 :             :           "module %T=> %i (will resolve by ipa-profile only with LTO)\n",
    1483                 :             :           gimple_call_fn (stmt), (int) val);
    1484                 :             :       else
    1485                 :          11 :         dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
    1486                 :             :                          "Indirect call -> direct call "
    1487                 :             :                          "%T => %T (will resolve by ipa-profile)\n",
    1488                 :             :                          gimple_call_fn (stmt), direct_call->decl);
    1489                 :          12 :       dump_printf_loc (MSG_NOTE, stmt,
    1490                 :             :                        "hist->count %" PRId64 " hist->all %" PRId64 "\n",
    1491                 :             :                        count, all);
    1492                 :             :     }
    1493                 :             : }
    1494                 :             : 
    1495                 :             : /* Return true if the stringop CALL shall be profiled.  SIZE_ARG be
    1496                 :             :    set to the argument index for the size of the string operation.  */
    1497                 :             : 
    1498                 :             : static bool
    1499                 :         421 : interesting_stringop_to_profile_p (gcall *call, int *size_arg)
    1500                 :             : {
    1501                 :         421 :   enum built_in_function fcode;
    1502                 :             : 
    1503                 :         421 :   fcode = DECL_FUNCTION_CODE (gimple_call_fndecl (call));
    1504                 :         421 :   switch (fcode)
    1505                 :             :     {
    1506                 :          61 :      case BUILT_IN_MEMCPY:
    1507                 :          61 :      case BUILT_IN_MEMPCPY:
    1508                 :          61 :      case BUILT_IN_MEMMOVE:
    1509                 :          61 :        *size_arg = 2;
    1510                 :          61 :        return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
    1511                 :          61 :                                        INTEGER_TYPE, VOID_TYPE);
    1512                 :          29 :      case BUILT_IN_MEMSET:
    1513                 :          29 :        *size_arg = 2;
    1514                 :          29 :        return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
    1515                 :          29 :                                       INTEGER_TYPE, VOID_TYPE);
    1516                 :           0 :      case BUILT_IN_BZERO:
    1517                 :           0 :        *size_arg = 1;
    1518                 :           0 :        return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
    1519                 :           0 :                                        VOID_TYPE);
    1520                 :             :      default:
    1521                 :             :        return false;
    1522                 :             :     }
    1523                 :             : }
    1524                 :             : 
    1525                 :             : /* Convert stringop (..., vcall_size)
    1526                 :             :    into
    1527                 :             :    if (vcall_size == icall_size)
    1528                 :             :      stringop (..., icall_size);
    1529                 :             :    else
    1530                 :             :      stringop (..., vcall_size);
    1531                 :             :    assuming we'll propagate a true constant into ICALL_SIZE later.  */
    1532                 :             : 
    1533                 :             : static void
    1534                 :          11 : gimple_stringop_fixed_value (gcall *vcall_stmt, tree icall_size, profile_probability prob,
    1535                 :             :                              gcov_type count, gcov_type all)
    1536                 :             : {
    1537                 :          11 :   gassign *tmp_stmt;
    1538                 :          11 :   gcond *cond_stmt;
    1539                 :          11 :   gcall *icall_stmt;
    1540                 :          11 :   tree tmp0, tmp1, vcall_size, optype;
    1541                 :          11 :   basic_block cond_bb, icall_bb, vcall_bb, join_bb;
    1542                 :          11 :   edge e_ci, e_cv, e_iv, e_ij, e_vj;
    1543                 :          11 :   gimple_stmt_iterator gsi;
    1544                 :          11 :   int size_arg;
    1545                 :             : 
    1546                 :          11 :   if (!interesting_stringop_to_profile_p (vcall_stmt, &size_arg))
    1547                 :           0 :     gcc_unreachable ();
    1548                 :             : 
    1549                 :          11 :   cond_bb = gimple_bb (vcall_stmt);
    1550                 :          11 :   gsi = gsi_for_stmt (vcall_stmt);
    1551                 :             : 
    1552                 :          11 :   vcall_size = gimple_call_arg (vcall_stmt, size_arg);
    1553                 :          11 :   optype = TREE_TYPE (vcall_size);
    1554                 :             : 
    1555                 :          11 :   tmp0 = make_temp_ssa_name (optype, NULL, "PROF");
    1556                 :          11 :   tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
    1557                 :          11 :   tmp_stmt = gimple_build_assign (tmp0, fold_convert (optype, icall_size));
    1558                 :          11 :   gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
    1559                 :             : 
    1560                 :          11 :   tmp_stmt = gimple_build_assign (tmp1, vcall_size);
    1561                 :          11 :   gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
    1562                 :             : 
    1563                 :          11 :   cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
    1564                 :          11 :   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
    1565                 :             : 
    1566                 :          22 :   if (TREE_CODE (gimple_vdef (vcall_stmt)) == SSA_NAME)
    1567                 :             :     {
    1568                 :          11 :       unlink_stmt_vdef (vcall_stmt);
    1569                 :          22 :       release_ssa_name (gimple_vdef (vcall_stmt));
    1570                 :             :     }
    1571                 :          11 :   gimple_set_vdef (vcall_stmt, NULL);
    1572                 :          11 :   gimple_set_vuse (vcall_stmt, NULL);
    1573                 :          11 :   update_stmt (vcall_stmt);
    1574                 :          11 :   icall_stmt = as_a <gcall *> (gimple_copy (vcall_stmt));
    1575                 :          11 :   gimple_call_set_arg (icall_stmt, size_arg,
    1576                 :             :                        fold_convert (optype, icall_size));
    1577                 :          11 :   gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT);
    1578                 :             : 
    1579                 :             :   /* Fix CFG. */
    1580                 :             :   /* Edge e_ci connects cond_bb to icall_bb, etc. */
    1581                 :          11 :   e_ci = split_block (cond_bb, cond_stmt);
    1582                 :          11 :   icall_bb = e_ci->dest;
    1583                 :          11 :   icall_bb->count = profile_count::from_gcov_type (count);
    1584                 :             : 
    1585                 :          11 :   e_iv = split_block (icall_bb, icall_stmt);
    1586                 :          11 :   vcall_bb = e_iv->dest;
    1587                 :          11 :   vcall_bb->count = profile_count::from_gcov_type (all - count);
    1588                 :             : 
    1589                 :          11 :   e_vj = split_block (vcall_bb, vcall_stmt);
    1590                 :          11 :   join_bb = e_vj->dest;
    1591                 :          11 :   join_bb->count = profile_count::from_gcov_type (all);
    1592                 :             : 
    1593                 :          11 :   e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
    1594                 :          11 :   e_ci->probability = prob;
    1595                 :             : 
    1596                 :          11 :   e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE);
    1597                 :          11 :   e_cv->probability = prob.invert ();
    1598                 :             : 
    1599                 :          11 :   remove_edge (e_iv);
    1600                 :             : 
    1601                 :          11 :   e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU);
    1602                 :          11 :   e_ij->probability = profile_probability::always ();
    1603                 :             : 
    1604                 :          11 :   e_vj->probability = profile_probability::always ();
    1605                 :             : 
    1606                 :             :   /* Insert PHI node for the call result if necessary.  */
    1607                 :          11 :   if (gimple_call_lhs (vcall_stmt)
    1608                 :          11 :       && TREE_CODE (gimple_call_lhs (vcall_stmt)) == SSA_NAME)
    1609                 :             :     {
    1610                 :           0 :       tree result = gimple_call_lhs (vcall_stmt);
    1611                 :           0 :       gphi *phi = create_phi_node (result, join_bb);
    1612                 :           0 :       gimple_call_set_lhs (vcall_stmt,
    1613                 :             :                            duplicate_ssa_name (result, vcall_stmt));
    1614                 :           0 :       add_phi_arg (phi, gimple_call_lhs (vcall_stmt), e_vj, UNKNOWN_LOCATION);
    1615                 :           0 :       gimple_call_set_lhs (icall_stmt,
    1616                 :             :                            duplicate_ssa_name (result, icall_stmt));
    1617                 :           0 :       add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
    1618                 :             :     }
    1619                 :             : 
    1620                 :             :   /* Because these are all string op builtins, they're all nothrow.  */
    1621                 :          11 :   gcc_assert (!stmt_could_throw_p (cfun, vcall_stmt));
    1622                 :          11 :   gcc_assert (!stmt_could_throw_p (cfun, icall_stmt));
    1623                 :          11 : }
    1624                 :             : 
    1625                 :             : /* Find values inside STMT for that we want to measure histograms for
    1626                 :             :    division/modulo optimization.  */
    1627                 :             : 
    1628                 :             : static bool
    1629                 :          62 : gimple_stringops_transform (gimple_stmt_iterator *gsi)
    1630                 :             : {
    1631                 :          62 :   gcall *stmt;
    1632                 :          62 :   tree blck_size;
    1633                 :          62 :   enum built_in_function fcode;
    1634                 :          62 :   histogram_value histogram;
    1635                 :          62 :   gcov_type count, all, val;
    1636                 :          62 :   tree dest, src;
    1637                 :          62 :   unsigned int dest_align, src_align;
    1638                 :          62 :   profile_probability prob;
    1639                 :          62 :   tree tree_val;
    1640                 :          62 :   int size_arg;
    1641                 :             : 
    1642                 :         111 :   stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
    1643                 :          60 :   if (!stmt)
    1644                 :             :     return false;
    1645                 :             : 
    1646                 :          60 :   if (!gimple_call_builtin_p (gsi_stmt (*gsi), BUILT_IN_NORMAL))
    1647                 :             :     return false;
    1648                 :             : 
    1649                 :          20 :   if (!interesting_stringop_to_profile_p (stmt, &size_arg))
    1650                 :             :     return false;
    1651                 :             : 
    1652                 :          20 :   blck_size = gimple_call_arg (stmt, size_arg);
    1653                 :          20 :   if (TREE_CODE (blck_size) == INTEGER_CST)
    1654                 :             :     return false;
    1655                 :             : 
    1656                 :          20 :   histogram = gimple_histogram_value_of_type (cfun, stmt,
    1657                 :             :                                               HIST_TYPE_TOPN_VALUES);
    1658                 :          20 :   if (!histogram)
    1659                 :             :     return false;
    1660                 :             : 
    1661                 :          20 :   if (!get_nth_most_common_value (stmt, "stringops", histogram, &val, &count,
    1662                 :             :                                   &all))
    1663                 :             :     return false;
    1664                 :             : 
    1665                 :          17 :   gimple_remove_histogram_value (cfun, stmt, histogram);
    1666                 :             : 
    1667                 :             :   /* We require that count is at least half of all.  */
    1668                 :          17 :   if (2 * count < all || optimize_bb_for_size_p (gimple_bb (stmt)))
    1669                 :           2 :     return false;
    1670                 :          15 :   if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
    1671                 :             :     return false;
    1672                 :          15 :   if (all > 0)
    1673                 :          15 :     prob = profile_probability::probability_in_gcov_type (count, all);
    1674                 :             :   else
    1675                 :           0 :     prob = profile_probability::never ();
    1676                 :             : 
    1677                 :          15 :   dest = gimple_call_arg (stmt, 0);
    1678                 :          15 :   dest_align = get_pointer_alignment (dest);
    1679                 :          15 :   fcode = DECL_FUNCTION_CODE (gimple_call_fndecl (stmt));
    1680                 :          15 :   switch (fcode)
    1681                 :             :     {
    1682                 :          11 :     case BUILT_IN_MEMCPY:
    1683                 :          11 :     case BUILT_IN_MEMPCPY:
    1684                 :          11 :     case BUILT_IN_MEMMOVE:
    1685                 :          11 :       src = gimple_call_arg (stmt, 1);
    1686                 :          11 :       src_align = get_pointer_alignment (src);
    1687                 :          11 :       if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
    1688                 :             :         return false;
    1689                 :             :       break;
    1690                 :           4 :     case BUILT_IN_MEMSET:
    1691                 :           8 :       if (!can_store_by_pieces (val, builtin_memset_read_str,
    1692                 :           4 :                                 gimple_call_arg (stmt, 1),
    1693                 :             :                                 dest_align, true))
    1694                 :             :         return false;
    1695                 :             :       break;
    1696                 :           0 :     case BUILT_IN_BZERO:
    1697                 :           0 :       if (!can_store_by_pieces (val, builtin_memset_read_str,
    1698                 :           0 :                                 integer_zero_node,
    1699                 :             :                                 dest_align, true))
    1700                 :             :         return false;
    1701                 :             :       break;
    1702                 :           0 :     default:
    1703                 :           0 :       gcc_unreachable ();
    1704                 :             :     }
    1705                 :             : 
    1706                 :          11 :   if (sizeof (gcov_type) == sizeof (HOST_WIDE_INT))
    1707                 :          11 :     tree_val = build_int_cst (get_gcov_type (), val);
    1708                 :             :   else
    1709                 :             :     {
    1710                 :             :       HOST_WIDE_INT a[2];
    1711                 :             :       a[0] = (unsigned HOST_WIDE_INT) val;
    1712                 :             :       a[1] = val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1;
    1713                 :             : 
    1714                 :             :       tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2,
    1715                 :             :         TYPE_PRECISION (get_gcov_type ()), false));
    1716                 :             :     }
    1717                 :             : 
    1718                 :          11 :   if (dump_enabled_p ())
    1719                 :          10 :     dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
    1720                 :             :                      "Transformation done: single value %i stringop for %s\n",
    1721                 :          10 :                      (int)val, built_in_names[(int)fcode]);
    1722                 :             : 
    1723                 :          11 :   gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
    1724                 :             : 
    1725                 :          11 :   return true;
    1726                 :             : }
    1727                 :             : 
    1728                 :             : void
    1729                 :      127745 : stringop_block_profile (gimple *stmt, unsigned int *expected_align,
    1730                 :             :                         HOST_WIDE_INT *expected_size)
    1731                 :             : {
    1732                 :      127745 :   histogram_value histogram;
    1733                 :      127745 :   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
    1734                 :             : 
    1735                 :      127745 :   if (!histogram)
    1736                 :      127726 :     *expected_size = -1;
    1737                 :          19 :   else if (!histogram->hvalue.counters[1])
    1738                 :             :     {
    1739                 :           2 :       *expected_size = -1;
    1740                 :           2 :       gimple_remove_histogram_value (cfun, stmt, histogram);
    1741                 :             :     }
    1742                 :             :   else
    1743                 :             :     {
    1744                 :          17 :       gcov_type size;
    1745                 :          17 :       size = ((histogram->hvalue.counters[0]
    1746                 :          17 :               + histogram->hvalue.counters[1] / 2)
    1747                 :             :                / histogram->hvalue.counters[1]);
    1748                 :             :       /* Even if we can hold bigger value in SIZE, INT_MAX
    1749                 :             :          is safe "infinity" for code generation strategies.  */
    1750                 :          17 :       if (size > INT_MAX)
    1751                 :             :         size = INT_MAX;
    1752                 :          17 :       *expected_size = size;
    1753                 :          17 :       gimple_remove_histogram_value (cfun, stmt, histogram);
    1754                 :             :     }
    1755                 :             : 
    1756                 :      127745 :   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
    1757                 :             : 
    1758                 :      127745 :   if (!histogram)
    1759                 :      127726 :     *expected_align = 0;
    1760                 :          19 :   else if (!histogram->hvalue.counters[0])
    1761                 :             :     {
    1762                 :           2 :       gimple_remove_histogram_value (cfun, stmt, histogram);
    1763                 :           2 :       *expected_align = 0;
    1764                 :             :     }
    1765                 :             :   else
    1766                 :             :     {
    1767                 :             :       gcov_type count;
    1768                 :             :       unsigned int alignment;
    1769                 :             : 
    1770                 :             :       count = histogram->hvalue.counters[0];
    1771                 :             :       alignment = 1;
    1772                 :         109 :       while (!(count & alignment)
    1773                 :         109 :              && (alignment <= UINT_MAX / 2 / BITS_PER_UNIT))
    1774                 :          92 :         alignment <<= 1;
    1775                 :          17 :       *expected_align = alignment * BITS_PER_UNIT;
    1776                 :          17 :       gimple_remove_histogram_value (cfun, stmt, histogram);
    1777                 :             :     }
    1778                 :      127745 : }
    1779                 :             : 
    1780                 :             : 
    1781                 :             : /* Find values inside STMT for that we want to measure histograms for
    1782                 :             :    division/modulo optimization.  */
    1783                 :             : 
    1784                 :             : static void
    1785                 :        7058 : gimple_divmod_values_to_profile (gimple *stmt, histogram_values *values)
    1786                 :             : {
    1787                 :        7058 :   tree lhs, divisor, op0, type;
    1788                 :        7058 :   histogram_value hist;
    1789                 :             : 
    1790                 :        7058 :   if (gimple_code (stmt) != GIMPLE_ASSIGN)
    1791                 :             :     return;
    1792                 :             : 
    1793                 :        3216 :   lhs = gimple_assign_lhs (stmt);
    1794                 :        3216 :   type = TREE_TYPE (lhs);
    1795                 :        3216 :   if (!INTEGRAL_TYPE_P (type))
    1796                 :             :     return;
    1797                 :             : 
    1798                 :        2245 :   switch (gimple_assign_rhs_code (stmt))
    1799                 :             :     {
    1800                 :          74 :     case TRUNC_DIV_EXPR:
    1801                 :          74 :     case TRUNC_MOD_EXPR:
    1802                 :          74 :       divisor = gimple_assign_rhs2 (stmt);
    1803                 :          74 :       op0 = gimple_assign_rhs1 (stmt);
    1804                 :             : 
    1805                 :          74 :       if (TREE_CODE (divisor) == SSA_NAME)
    1806                 :             :         /* Check for the case where the divisor is the same value most
    1807                 :             :            of the time.  */
    1808                 :          45 :         values->safe_push (gimple_alloc_histogram_value (cfun,
    1809                 :             :                                                          HIST_TYPE_TOPN_VALUES,
    1810                 :             :                                                          stmt, divisor));
    1811                 :             : 
    1812                 :             :       /* For mod, check whether it is not often a noop (or replaceable by
    1813                 :             :          a few subtractions).  */
    1814                 :          74 :       if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
    1815                 :          50 :           && TYPE_UNSIGNED (type)
    1816                 :          99 :           && TREE_CODE (divisor) == SSA_NAME)
    1817                 :             :         {
    1818                 :          21 :           tree val;
    1819                 :             :           /* Check for a special case where the divisor is power of 2.  */
    1820                 :          21 :           values->safe_push (gimple_alloc_histogram_value (cfun,
    1821                 :             :                                                            HIST_TYPE_POW2,
    1822                 :             :                                                            stmt, divisor));
    1823                 :          21 :           val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
    1824                 :          21 :           hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
    1825                 :             :                                                stmt, val);
    1826                 :          21 :           hist->hdata.intvl.int_start = 0;
    1827                 :          21 :           hist->hdata.intvl.steps = 2;
    1828                 :          21 :           values->safe_push (hist);
    1829                 :             :         }
    1830                 :             :       return;
    1831                 :             : 
    1832                 :             :     default:
    1833                 :             :       return;
    1834                 :             :     }
    1835                 :             : }
    1836                 :             : 
    1837                 :             : /* Find calls inside STMT for that we want to measure histograms for
    1838                 :             :    indirect/virtual call optimization. */
    1839                 :             : 
    1840                 :             : static void
    1841                 :        7058 : gimple_indirect_call_to_profile (gimple *stmt, histogram_values *values)
    1842                 :             : {
    1843                 :        7058 :   tree callee;
    1844                 :             : 
    1845                 :        7058 :   if (gimple_code (stmt) != GIMPLE_CALL
    1846                 :        1319 :       || gimple_call_internal_p (stmt)
    1847                 :        8332 :       || gimple_call_fndecl (stmt) != NULL_TREE)
    1848                 :        6975 :     return;
    1849                 :             : 
    1850                 :          83 :   callee = gimple_call_fn (stmt);
    1851                 :          83 :   histogram_value v = gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
    1852                 :          83 :                                                     stmt, callee);
    1853                 :          83 :   values->safe_push (v);
    1854                 :             : 
    1855                 :          83 :   return;
    1856                 :             : }
    1857                 :             : 
    1858                 :             : /* Find values inside STMT for that we want to measure histograms for
    1859                 :             :    string operations.  */
    1860                 :             : 
    1861                 :             : static void
    1862                 :        7058 : gimple_stringops_values_to_profile (gimple *gs, histogram_values *values)
    1863                 :             : {
    1864                 :        7058 :   gcall *stmt;
    1865                 :        7058 :   tree blck_size;
    1866                 :        7058 :   tree dest;
    1867                 :        7058 :   int size_arg;
    1868                 :             : 
    1869                 :        7058 :   stmt = dyn_cast <gcall *> (gs);
    1870                 :        1319 :   if (!stmt)
    1871                 :        6999 :     return;
    1872                 :             : 
    1873                 :        1319 :   if (!gimple_call_builtin_p (gs, BUILT_IN_NORMAL))
    1874                 :             :     return;
    1875                 :             : 
    1876                 :         390 :   if (!interesting_stringop_to_profile_p (stmt, &size_arg))
    1877                 :             :     return;
    1878                 :             : 
    1879                 :          59 :   dest = gimple_call_arg (stmt, 0);
    1880                 :          59 :   blck_size = gimple_call_arg (stmt, size_arg);
    1881                 :             : 
    1882                 :          59 :   if (TREE_CODE (blck_size) != INTEGER_CST)
    1883                 :             :     {
    1884                 :          48 :       values->safe_push (gimple_alloc_histogram_value (cfun,
    1885                 :             :                                                        HIST_TYPE_TOPN_VALUES,
    1886                 :             :                                                        stmt, blck_size));
    1887                 :          48 :       values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
    1888                 :             :                                                        stmt, blck_size));
    1889                 :             :     }
    1890                 :             : 
    1891                 :          59 :   if (TREE_CODE (blck_size) != INTEGER_CST)
    1892                 :          48 :     values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
    1893                 :             :                                                      stmt, dest));
    1894                 :             : }
    1895                 :             : 
    1896                 :             : /* Find values inside STMT for that we want to measure histograms and adds
    1897                 :             :    them to list VALUES.  */
    1898                 :             : 
    1899                 :             : static void
    1900                 :        7058 : gimple_values_to_profile (gimple *stmt, histogram_values *values)
    1901                 :             : {
    1902                 :        7058 :   gimple_divmod_values_to_profile (stmt, values);
    1903                 :        7058 :   gimple_stringops_values_to_profile (stmt, values);
    1904                 :        7058 :   gimple_indirect_call_to_profile (stmt, values);
    1905                 :        7058 : }
    1906                 :             : 
    1907                 :             : void
    1908                 :         941 : gimple_find_values_to_profile (histogram_values *values)
    1909                 :             : {
    1910                 :         941 :   basic_block bb;
    1911                 :         941 :   gimple_stmt_iterator gsi;
    1912                 :         941 :   unsigned i;
    1913                 :         941 :   histogram_value hist = NULL;
    1914                 :         941 :   values->create (0);
    1915                 :             : 
    1916                 :        5017 :   FOR_EACH_BB_FN (bb, cfun)
    1917                 :       15210 :     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1918                 :        7058 :       gimple_values_to_profile (gsi_stmt (gsi), values);
    1919                 :             : 
    1920                 :         941 :   values->safe_push (gimple_alloc_histogram_value (cfun,
    1921                 :             :                                                    HIST_TYPE_TIME_PROFILE));
    1922                 :             : 
    1923                 :        2196 :   FOR_EACH_VEC_ELT (*values, i, hist)
    1924                 :             :     {
    1925                 :        1255 :       switch (hist->type)
    1926                 :             :         {
    1927                 :          21 :         case HIST_TYPE_INTERVAL:
    1928                 :          21 :           hist->n_counters = hist->hdata.intvl.steps + 2;
    1929                 :          21 :           break;
    1930                 :             : 
    1931                 :          21 :         case HIST_TYPE_POW2:
    1932                 :          21 :           hist->n_counters = 2;
    1933                 :          21 :           break;
    1934                 :             : 
    1935                 :         176 :         case HIST_TYPE_TOPN_VALUES:
    1936                 :         176 :         case HIST_TYPE_INDIR_CALL:
    1937                 :         176 :           hist->n_counters = GCOV_TOPN_MEM_COUNTERS;
    1938                 :         176 :           break;
    1939                 :             : 
    1940                 :         941 :         case HIST_TYPE_TIME_PROFILE:
    1941                 :         941 :           hist->n_counters = 1;
    1942                 :         941 :           break;
    1943                 :             : 
    1944                 :          48 :         case HIST_TYPE_AVERAGE:
    1945                 :          48 :           hist->n_counters = 2;
    1946                 :          48 :           break;
    1947                 :             : 
    1948                 :          48 :         case HIST_TYPE_IOR:
    1949                 :          48 :           hist->n_counters = 1;
    1950                 :          48 :           break;
    1951                 :             : 
    1952                 :           0 :         default:
    1953                 :           0 :           gcc_unreachable ();
    1954                 :             :         }
    1955                 :        1255 :       if (dump_file && hist->hvalue.stmt != NULL)
    1956                 :             :         {
    1957                 :         134 :           fprintf (dump_file, "Stmt ");
    1958                 :         134 :           print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
    1959                 :         134 :           dump_histogram_value (dump_file, hist);
    1960                 :             :         }
    1961                 :             :     }
    1962                 :         941 : }
        

Generated by: LCOV version 2.0-1

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.