gcc/value-prof.c

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