contrib/gcc-8.0/gcc/value-prof.c

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