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

Generated by: LCOV version 1.0

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