gcc/value-prof.c

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