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