gcc/value-prof.cc

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