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                     "profiler overall count (%d) does not match BB count (%d)",
 478                     name, (int)*all, (int)bb_count);
 479           return true;
 480         }
 481     }
 482
 483   return false;
 484 }
 485
 486
 487 /* GIMPLE based transformations. */
 488
 489 bool
 490 gimple_value_profile_transformations (void)
 491 {
 492   basic_block bb;
 493   gimple_stmt_iterator gsi;
 494   bool changed = false;
 495
 496   FOR_EACH_BB (bb)
 497     {
 498       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 499         {
 500           gimple stmt = gsi_stmt (gsi);
 501           histogram_value th = gimple_histogram_value (cfun, stmt);
 502           if (!th)
 503             continue;
 504
 505           if (dump_file)
 506             {
 507               fprintf (dump_file, "Trying transformations on stmt ");
 508               print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 509               dump_histograms_for_stmt (cfun, dump_file, stmt);
 510             }
 511
 512           /* Transformations:  */
 513           /* The order of things in this conditional controls which
 514              transformation is used when more than one is applicable.  */
 515           /* It is expected that any code added by the transformations
 516              will be added before the current statement, and that the
 517              current statement remain valid (although possibly
 518              modified) upon return.  */
 519           if (flag_value_profile_transformations
 520               && (gimple_mod_subtract_transform (&gsi)
 521                   || gimple_divmod_fixed_value_transform (&gsi)
 522                   || gimple_mod_pow2_value_transform (&gsi)
 523                   || gimple_stringops_transform (&gsi)
 524                   || gimple_ic_transform (stmt)))
 525             {
 526               stmt = gsi_stmt (gsi);
 527               changed = true;
 528               /* Original statement may no longer be in the same block. */
 529               if (bb != gimple_bb (stmt))
 530                 {
 531                   bb = gimple_bb (stmt);
 532                   gsi = gsi_for_stmt (stmt);
 533                 }
 534             }
 535         }
 536     }
 537
 538   if (changed)
 539     {
 540       counts_to_freqs ();
 541     }
 542
 543   return changed;
 544 }
 545
 546
 547 /* Generate code for transformation 1 (with parent gimple assignment
 548    STMT and probability of taking the optimal path PROB, which is
 549    equivalent to COUNT/ALL within roundoff error).  This generates the
 550    result into a temp and returns the temp; it does not replace or
 551    alter the original STMT.  */
 552
 553 static tree
 554 gimple_divmod_fixed_value (gimple stmt, tree value, int prob, gcov_type count,
 555                            gcov_type all)
 556 {
 557   gimple stmt1, stmt2, stmt3;
 558   tree tmp0, tmp1, tmp2, tmpv;
 559   gimple bb1end, bb2end, bb3end;
 560   basic_block bb, bb2, bb3, bb4;
 561   tree optype, op1, op2;
 562   edge e12, e13, e23, e24, e34;
 563   gimple_stmt_iterator gsi;
 564
 565   gcc_assert (is_gimple_assign (stmt)
 566               && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
 567                   || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR));
 568
 569   optype = TREE_TYPE (gimple_assign_lhs (stmt));
 570   op1 = gimple_assign_rhs1 (stmt);
 571   op2 = gimple_assign_rhs2 (stmt);
 572
 573   bb = gimple_bb (stmt);
 574   gsi = gsi_for_stmt (stmt);
 575
 576   tmpv = create_tmp_reg (optype, "PROF");
 577   tmp0 = make_ssa_name (tmpv, NULL);
 578   tmp1 = make_ssa_name (tmpv, NULL);
 579   stmt1 = gimple_build_assign (tmp0, fold_convert (optype, value));
 580   SSA_NAME_DEF_STMT (tmp0) = stmt1;
 581   stmt2 = gimple_build_assign (tmp1, op2);
 582   SSA_NAME_DEF_STMT (tmp1) = stmt2;
 583   stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
 584   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
 585   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
 586   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
 587   bb1end = stmt3;
 588
 589   tmp2 = make_rename_temp (optype, "PROF");
 590   stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2,
 591                                         op1, tmp0);
 592   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
 593   bb2end = stmt1;
 594
 595   stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2,
 596                                         op1, op2);
 597   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
 598   bb3end = stmt1;
 599
 600   /* Fix CFG. */
 601   /* Edge e23 connects bb2 to bb3, etc. */
 602   e12 = split_block (bb, bb1end);
 603   bb2 = e12->dest;
 604   bb2->count = count;
 605   e23 = split_block (bb2, bb2end);
 606   bb3 = e23->dest;
 607   bb3->count = all - count;
 608   e34 = split_block (bb3, bb3end);
 609   bb4 = e34->dest;
 610   bb4->count = all;
 611
 612   e12->flags &= ~EDGE_FALLTHRU;
 613   e12->flags |= EDGE_FALSE_VALUE;
 614   e12->probability = prob;
 615   e12->count = count;
 616
 617   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
 618   e13->probability = REG_BR_PROB_BASE - prob;
 619   e13->count = all - count;
 620
 621   remove_edge (e23);
 622
 623   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
 624   e24->probability = REG_BR_PROB_BASE;
 625   e24->count = count;
 626
 627   e34->probability = REG_BR_PROB_BASE;
 628   e34->count = all - count;
 629
 630   return tmp2;
 631 }
 632
 633
 634 /* Do transform 1) on INSN if applicable.  */
 635
 636 static bool
 637 gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
 638 {
 639   histogram_value histogram;
 640   enum tree_code code;
 641   gcov_type val, count, all;
 642   tree result, value, tree_val;
 643   gcov_type prob;
 644   gimple stmt;
 645
 646   stmt = gsi_stmt (*si);
 647   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 648     return false;
 649
 650   if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
 651     return false;
 652
 653   code = gimple_assign_rhs_code (stmt);
 654
 655   if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
 656     return false;
 657
 658   histogram = gimple_histogram_value_of_type (cfun, stmt,
 659                                               HIST_TYPE_SINGLE_VALUE);
 660   if (!histogram)
 661     return false;
 662
 663   value = histogram->hvalue.value;
 664   val = histogram->hvalue.counters[0];
 665   count = histogram->hvalue.counters[1];
 666   all = histogram->hvalue.counters[2];
 667   gimple_remove_histogram_value (cfun, stmt, histogram);
 668
 669   /* We require that count is at least half of all; this means
 670      that for the transformation to fire the value must be constant
 671      at least 50% of time (and 75% gives the guarantee of usage).  */
 672   if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
 673       || 2 * count < all
 674       || optimize_bb_for_size_p (gimple_bb (stmt)))
 675     return false;
 676
 677   if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
 678     return false;
 679
 680   /* Compute probability of taking the optimal path.  */
 681   if (all > 0)
 682     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 683   else
 684     prob = 0;
 685
 686   tree_val = build_int_cst_wide (get_gcov_type (),
 687                                  (unsigned HOST_WIDE_INT) val,
 688                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
 689   result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all);
 690
 691   if (dump_file)
 692     {
 693       fprintf (dump_file, "Div/mod by constant ");
 694       print_generic_expr (dump_file, value, TDF_SLIM);
 695       fprintf (dump_file, "=");
 696       print_generic_expr (dump_file, tree_val, TDF_SLIM);
 697       fprintf (dump_file, " transformation on insn ");
 698       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 699     }
 700
 701   gimple_assign_set_rhs_from_tree (si, result);
 702   update_stmt (gsi_stmt (*si));
 703
 704   return true;
 705 }
 706
 707 /* Generate code for transformation 2 (with parent gimple assign STMT and
 708    probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
 709    within roundoff error).  This generates the result into a temp and returns
 710    the temp; it does not replace or alter the original STMT.  */
 711 static tree
 712 gimple_mod_pow2 (gimple stmt, int prob, gcov_type count, gcov_type all)
 713 {
 714   gimple stmt1, stmt2, stmt3, stmt4;
 715   tree tmp2, tmp3, tmpv;
 716   gimple bb1end, bb2end, bb3end;
 717   basic_block bb, bb2, bb3, bb4;
 718   tree optype, op1, op2;
 719   edge e12, e13, e23, e24, e34;
 720   gimple_stmt_iterator gsi;
 721   tree result;
 722
 723   gcc_assert (is_gimple_assign (stmt)
 724               && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
 725
 726   optype = TREE_TYPE (gimple_assign_lhs (stmt));
 727   op1 = gimple_assign_rhs1 (stmt);
 728   op2 = gimple_assign_rhs2 (stmt);
 729
 730   bb = gimple_bb (stmt);
 731   gsi = gsi_for_stmt (stmt);
 732
 733   result = make_rename_temp (optype, "PROF");
 734   tmpv = create_tmp_var (optype, "PROF");
 735   tmp2 = make_ssa_name (tmpv, NULL);
 736   tmp3 = make_ssa_name (tmpv, NULL);
 737   stmt2 = gimple_build_assign_with_ops (PLUS_EXPR, tmp2, op2,
 738                                         build_int_cst (optype, -1));
 739   SSA_NAME_DEF_STMT (tmp2) = stmt2;
 740   stmt3 = gimple_build_assign_with_ops (BIT_AND_EXPR, tmp3, tmp2, op2);
 741   SSA_NAME_DEF_STMT (tmp3) = stmt3;
 742   stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0),
 743                              NULL_TREE, NULL_TREE);
 744   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
 745   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
 746   gsi_insert_before (&gsi, stmt4, GSI_SAME_STMT);
 747   bb1end = stmt4;
 748
 749   /* tmp2 == op2-1 inherited from previous block.  */
 750   stmt1 = gimple_build_assign_with_ops (BIT_AND_EXPR, result, op1, tmp2);
 751   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
 752   bb2end = stmt1;
 753
 754   stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result,
 755                                         op1, op2);
 756   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
 757   bb3end = stmt1;
 758
 759   /* Fix CFG. */
 760   /* Edge e23 connects bb2 to bb3, etc. */
 761   e12 = split_block (bb, bb1end);
 762   bb2 = e12->dest;
 763   bb2->count = count;
 764   e23 = split_block (bb2, bb2end);
 765   bb3 = e23->dest;
 766   bb3->count = all - count;
 767   e34 = split_block (bb3, bb3end);
 768   bb4 = e34->dest;
 769   bb4->count = all;
 770
 771   e12->flags &= ~EDGE_FALLTHRU;
 772   e12->flags |= EDGE_FALSE_VALUE;
 773   e12->probability = prob;
 774   e12->count = count;
 775
 776   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
 777   e13->probability = REG_BR_PROB_BASE - prob;
 778   e13->count = all - count;
 779
 780   remove_edge (e23);
 781
 782   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
 783   e24->probability = REG_BR_PROB_BASE;
 784   e24->count = count;
 785
 786   e34->probability = REG_BR_PROB_BASE;
 787   e34->count = all - count;
 788
 789   return result;
 790 }
 791
 792 /* Do transform 2) on INSN if applicable.  */
 793 static bool
 794 gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
 795 {
 796   histogram_value histogram;
 797   enum tree_code code;
 798   gcov_type count, wrong_values, all;
 799   tree lhs_type, result, value;
 800   gcov_type prob;
 801   gimple stmt;
 802
 803   stmt = gsi_stmt (*si);
 804   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 805     return false;
 806
 807   lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
 808   if (!INTEGRAL_TYPE_P (lhs_type))
 809     return false;
 810
 811   code = gimple_assign_rhs_code (stmt);
 812
 813   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
 814     return false;
 815
 816   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
 817   if (!histogram)
 818     return false;
 819
 820   value = histogram->hvalue.value;
 821   wrong_values = histogram->hvalue.counters[0];
 822   count = histogram->hvalue.counters[1];
 823
 824   gimple_remove_histogram_value (cfun, stmt, histogram);
 825
 826   /* We require that we hit a power of 2 at least half of all evaluations.  */
 827   if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
 828       || count < wrong_values
 829       || optimize_bb_for_size_p (gimple_bb (stmt)))
 830     return false;
 831
 832   if (dump_file)
 833     {
 834       fprintf (dump_file, "Mod power of 2 transformation on insn ");
 835       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 836     }
 837
 838   /* Compute probability of taking the optimal path.  */
 839   all = count + wrong_values;
 840
 841   if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count))
 842     return false;
 843
 844   if (all > 0)
 845     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 846   else
 847     prob = 0;
 848
 849   result = gimple_mod_pow2 (stmt, prob, count, all);
 850
 851   gimple_assign_set_rhs_from_tree (si, result);
 852   update_stmt (gsi_stmt (*si));
 853
 854   return true;
 855 }
 856
 857 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
 858    NCOUNTS the number of cases to support.  Currently only NCOUNTS==0 or 1 is
 859    supported and this is built into this interface.  The probabilities of taking
 860    the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
 861    COUNT2/ALL respectively within roundoff error).  This generates the
 862    result into a temp and returns the temp; it does not replace or alter
 863    the original STMT.  */
 864 /* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
 865
 866 static tree
 867 gimple_mod_subtract (gimple stmt, int prob1, int prob2, int ncounts,
 868                      gcov_type count1, gcov_type count2, gcov_type all)
 869 {
 870   gimple stmt1, stmt2, stmt3;
 871   tree tmp1;
 872   gimple bb1end, bb2end = NULL, bb3end;
 873   basic_block bb, bb2, bb3, bb4;
 874   tree optype, op1, op2;
 875   edge e12, e23 = 0, e24, e34, e14;
 876   gimple_stmt_iterator gsi;
 877   tree result;
 878
 879   gcc_assert (is_gimple_assign (stmt)
 880               && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
 881
 882   optype = TREE_TYPE (gimple_assign_lhs (stmt));
 883   op1 = gimple_assign_rhs1 (stmt);
 884   op2 = gimple_assign_rhs2 (stmt);
 885
 886   bb = gimple_bb (stmt);
 887   gsi = gsi_for_stmt (stmt);
 888
 889   result = make_rename_temp (optype, "PROF");
 890   tmp1 = make_ssa_name (create_tmp_var (optype, "PROF"), NULL);
 891   stmt1 = gimple_build_assign (result, op1);
 892   stmt2 = gimple_build_assign (tmp1, op2);
 893   SSA_NAME_DEF_STMT (tmp1) = stmt2;
 894   stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
 895   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
 896   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
 897   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
 898   bb1end = stmt3;
 899
 900   if (ncounts)  /* Assumed to be 0 or 1 */
 901     {
 902       stmt1 = gimple_build_assign_with_ops (MINUS_EXPR, result, result, tmp1);
 903       stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
 904       gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
 905       gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
 906       bb2end = stmt2;
 907     }
 908
 909   /* Fallback case. */
 910   stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result,
 911                                         result, tmp1);
 912   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
 913   bb3end = stmt1;
 914
 915   /* Fix CFG. */
 916   /* Edge e23 connects bb2 to bb3, etc. */
 917   /* However block 3 is optional; if it is not there, references
 918      to 3 really refer to block 2. */
 919   e12 = split_block (bb, bb1end);
 920   bb2 = e12->dest;
 921   bb2->count = all - count1;
 922
 923   if (ncounts)  /* Assumed to be 0 or 1.  */
 924     {
 925       e23 = split_block (bb2, bb2end);
 926       bb3 = e23->dest;
 927       bb3->count = all - count1 - count2;
 928     }
 929
 930   e34 = split_block (ncounts ? bb3 : bb2, bb3end);
 931   bb4 = e34->dest;
 932   bb4->count = all;
 933
 934   e12->flags &= ~EDGE_FALLTHRU;
 935   e12->flags |= EDGE_FALSE_VALUE;
 936   e12->probability = REG_BR_PROB_BASE - prob1;
 937   e12->count = all - count1;
 938
 939   e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
 940   e14->probability = prob1;
 941   e14->count = count1;
 942
 943   if (ncounts)  /* Assumed to be 0 or 1.  */
 944     {
 945       e23->flags &= ~EDGE_FALLTHRU;
 946       e23->flags |= EDGE_FALSE_VALUE;
 947       e23->count = all - count1 - count2;
 948       e23->probability = REG_BR_PROB_BASE - prob2;
 949
 950       e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
 951       e24->probability = prob2;
 952       e24->count = count2;
 953     }
 954
 955   e34->probability = REG_BR_PROB_BASE;
 956   e34->count = all - count1 - count2;
 957
 958   return result;
 959 }
 960
 961
 962 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable.  */
 963
 964 static bool
 965 gimple_mod_subtract_transform (gimple_stmt_iterator *si)
 966 {
 967   histogram_value histogram;
 968   enum tree_code code;
 969   gcov_type count, wrong_values, all;
 970   tree lhs_type, result;
 971   gcov_type prob1, prob2;
 972   unsigned int i, steps;
 973   gcov_type count1, count2;
 974   gimple stmt;
 975
 976   stmt = gsi_stmt (*si);
 977   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 978     return false;
 979
 980   lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
 981   if (!INTEGRAL_TYPE_P (lhs_type))
 982     return false;
 983
 984   code = gimple_assign_rhs_code (stmt);
 985
 986   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
 987     return false;
 988
 989   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
 990   if (!histogram)
 991     return false;
 992
 993   all = 0;
 994   wrong_values = 0;
 995   for (i = 0; i < histogram->hdata.intvl.steps; i++)
 996     all += histogram->hvalue.counters[i];
 997
 998   wrong_values += histogram->hvalue.counters[i];
 999   wrong_values += histogram->hvalue.counters[i+1];
1000   steps = histogram->hdata.intvl.steps;
1001   all += wrong_values;
1002   count1 = histogram->hvalue.counters[0];
1003   count2 = histogram->hvalue.counters[1];
1004
1005   /* Compute probability of taking the optimal path.  */
1006   if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count))
1007     {
1008       gimple_remove_histogram_value (cfun, stmt, histogram);
1009       return false;
1010     }
1011
1012   if (flag_profile_correction && count1 + count2 > all)
1013       all = count1 + count2;
1014
1015   gcc_assert (count1 + count2 <= all);
1016
1017   /* We require that we use just subtractions in at least 50% of all
1018      evaluations.  */
1019   count = 0;
1020   for (i = 0; i < histogram->hdata.intvl.steps; i++)
1021     {
1022       count += histogram->hvalue.counters[i];
1023       if (count * 2 >= all)
1024         break;
1025     }
1026   if (i == steps
1027       || optimize_bb_for_size_p (gimple_bb (stmt)))
1028     return false;
1029
1030   gimple_remove_histogram_value (cfun, stmt, histogram);
1031   if (dump_file)
1032     {
1033       fprintf (dump_file, "Mod subtract transformation on insn ");
1034       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1035     }
1036
1037   /* Compute probability of taking the optimal path(s).  */
1038   if (all > 0)
1039     {
1040       prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all;
1041       prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all;
1042     }
1043   else
1044     {
1045       prob1 = prob2 = 0;
1046     }
1047
1048   /* In practice, "steps" is always 2.  This interface reflects this,
1049      and will need to be changed if "steps" can change.  */
1050   result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all);
1051
1052   gimple_assign_set_rhs_from_tree (si, result);
1053   update_stmt (gsi_stmt (*si));
1054
1055   return true;
1056 }
1057
1058 static struct cgraph_node** pid_map = NULL;
1059
1060 /* Initialize map of pids (pid -> cgraph node) */
1061
1062 static void
1063 init_pid_map (void)
1064 {
1065   struct cgraph_node *n;
1066
1067   if (pid_map != NULL)
1068     return;
1069
1070   pid_map = XCNEWVEC (struct cgraph_node*, cgraph_max_pid);
1071
1072   for (n = cgraph_nodes; n; n = n->next)
1073     {
1074       if (n->pid != -1)
1075         pid_map [n->pid] = n;
1076     }
1077 }
1078
1079 /* Return cgraph node for function with pid */
1080
1081 static inline struct cgraph_node*
1082 find_func_by_pid (int   pid)
1083 {
1084   init_pid_map ();
1085
1086   return pid_map [pid];
1087 }
1088
1089 /* Do transformation
1090
1091   if (actual_callee_address == address_of_most_common_function/method)
1092     do direct call
1093   else
1094     old call
1095  */
1096
1097 static gimple
1098 gimple_ic (gimple icall_stmt, struct cgraph_node *direct_call,
1099            int prob, gcov_type count, gcov_type all)
1100 {
1101   gimple dcall_stmt, load_stmt, cond_stmt;
1102   tree tmp0, tmp1, tmpv, tmp;
1103   basic_block cond_bb, dcall_bb, icall_bb, join_bb;
1104   tree optype = build_pointer_type (void_type_node);
1105   edge e_cd, e_ci, e_di, e_dj, e_ij;
1106   gimple_stmt_iterator gsi;
1107   int lp_nr;
1108
1109   cond_bb = gimple_bb (icall_stmt);
1110   gsi = gsi_for_stmt (icall_stmt);
1111
1112   tmpv = create_tmp_reg (optype, "PROF");
1113   tmp0 = make_ssa_name (tmpv, NULL);
1114   tmp1 = make_ssa_name (tmpv, NULL);
1115   tmp = unshare_expr (gimple_call_fn (icall_stmt));
1116   load_stmt = gimple_build_assign (tmp0, tmp);
1117   SSA_NAME_DEF_STMT (tmp0) = load_stmt;
1118   gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1119
1120   tmp = fold_convert (optype, build_addr (direct_call->decl,
1121                                           current_function_decl));
1122   load_stmt = gimple_build_assign (tmp1, tmp);
1123   SSA_NAME_DEF_STMT (tmp1) = load_stmt;
1124   gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1125
1126   cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1127   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1128
1129   gimple_set_vdef (icall_stmt, NULL_TREE);
1130   gimple_set_vuse (icall_stmt, NULL_TREE);
1131   update_stmt (icall_stmt);
1132   dcall_stmt = gimple_copy (icall_stmt);
1133   gimple_call_set_fndecl (dcall_stmt, direct_call->decl);
1134   gsi_insert_before (&gsi, dcall_stmt, GSI_SAME_STMT);
1135
1136   /* Fix CFG. */
1137   /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1138   e_cd = split_block (cond_bb, cond_stmt);
1139   dcall_bb = e_cd->dest;
1140   dcall_bb->count = count;
1141
1142   e_di = split_block (dcall_bb, dcall_stmt);
1143   icall_bb = e_di->dest;
1144   icall_bb->count = all - count;
1145
1146   /* Do not disturb existing EH edges from the indirect call.  */
1147   if (!stmt_ends_bb_p (icall_stmt))
1148     e_ij = split_block (icall_bb, icall_stmt);
1149   else
1150     {
1151       e_ij = find_fallthru_edge (icall_bb->succs);
1152       e_ij->probability = REG_BR_PROB_BASE;
1153       e_ij->count = all - count;
1154       e_ij = single_pred_edge (split_edge (e_ij));
1155     }
1156   join_bb = e_ij->dest;
1157   join_bb->count = all;
1158
1159   e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1160   e_cd->probability = prob;
1161   e_cd->count = count;
1162
1163   e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE);
1164   e_ci->probability = REG_BR_PROB_BASE - prob;
1165   e_ci->count = all - count;
1166
1167   remove_edge (e_di);
1168
1169   e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU);
1170   e_dj->probability = REG_BR_PROB_BASE;
1171   e_dj->count = count;
1172
1173   e_ij->probability = REG_BR_PROB_BASE;
1174   e_ij->count = all - count;
1175
1176   /* Insert PHI node for the call result if necessary.  */
1177   if (gimple_call_lhs (icall_stmt)
1178       && TREE_CODE (gimple_call_lhs (icall_stmt)) == SSA_NAME)
1179     {
1180       tree result = gimple_call_lhs (icall_stmt);
1181       gimple phi = create_phi_node (result, join_bb);
1182       SSA_NAME_DEF_STMT (result) = phi;
1183       gimple_call_set_lhs (icall_stmt,
1184                            make_ssa_name (SSA_NAME_VAR (result), icall_stmt));
1185       add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1186       gimple_call_set_lhs (dcall_stmt,
1187                            make_ssa_name (SSA_NAME_VAR (result), dcall_stmt));
1188       add_phi_arg (phi, gimple_call_lhs (dcall_stmt), e_dj, UNKNOWN_LOCATION);
1189     }
1190
1191   /* Build an EH edge for the direct call if necessary.  */
1192   lp_nr = lookup_stmt_eh_lp (icall_stmt);
1193   if (lp_nr != 0
1194       && stmt_could_throw_p (dcall_stmt))
1195     {
1196       edge e_eh, e;
1197       edge_iterator ei;
1198       gimple_stmt_iterator psi;
1199
1200       add_stmt_to_eh_lp (dcall_stmt, lp_nr);
1201       FOR_EACH_EDGE (e_eh, ei, icall_bb->succs)
1202         if (e_eh->flags & EDGE_EH)
1203           break;
1204       e = make_edge (dcall_bb, e_eh->dest, EDGE_EH);
1205       for (psi = gsi_start_phis (e_eh->dest);
1206            !gsi_end_p (psi); gsi_next (&psi))
1207         {
1208           gimple phi = gsi_stmt (psi);
1209           SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e),
1210                    PHI_ARG_DEF_FROM_EDGE (phi, e_eh));
1211         }
1212     }
1213
1214   return dcall_stmt;
1215 }
1216
1217 /*
1218   For every checked indirect/virtual call determine if most common pid of
1219   function/class method has probability more than 50%. If yes modify code of
1220   this call to:
1221  */
1222
1223 static bool
1224 gimple_ic_transform (gimple stmt)
1225 {
1226   histogram_value histogram;
1227   gcov_type val, count, all, bb_all;
1228   gcov_type prob;
1229   tree callee;
1230   gimple modify;
1231   struct cgraph_node *direct_call;
1232
1233   if (gimple_code (stmt) != GIMPLE_CALL)
1234     return false;
1235
1236   callee = gimple_call_fn (stmt);
1237
1238   if (TREE_CODE (callee) == FUNCTION_DECL)
1239     return false;
1240
1241   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1242   if (!histogram)
1243     return false;
1244
1245   val = histogram->hvalue.counters [0];
1246   count = histogram->hvalue.counters [1];
1247   all = histogram->hvalue.counters [2];
1248   gimple_remove_histogram_value (cfun, stmt, histogram);
1249
1250   if (4 * count <= 3 * all)
1251     return false;
1252
1253   bb_all = gimple_bb (stmt)->count;
1254   /* The order of CHECK_COUNTER calls is important -
1255      since check_counter can correct the third parameter
1256      and we want to make count <= all <= bb_all. */
1257   if ( check_counter (stmt, "ic", &all, &bb_all, bb_all)
1258       || check_counter (stmt, "ic", &count, &all, all))
1259     return false;
1260
1261   if (all > 0)
1262     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1263   else
1264     prob = 0;
1265   direct_call = find_func_by_pid ((int)val);
1266
1267   if (direct_call == NULL)
1268     return false;
1269
1270   modify = gimple_ic (stmt, direct_call, prob, count, all);
1271
1272   if (dump_file)
1273     {
1274       fprintf (dump_file, "Indirect call -> direct call ");
1275       print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1276       fprintf (dump_file, "=> ");
1277       print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1278       fprintf (dump_file, " transformation on insn ");
1279       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1280       fprintf (dump_file, " to ");
1281       print_gimple_stmt (dump_file, modify, 0, TDF_SLIM);
1282       fprintf (dump_file, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1283                " hist->all "HOST_WIDEST_INT_PRINT_DEC"\n", count, all);
1284     }
1285
1286   return true;
1287 }
1288
1289 /* Return true if the stringop CALL with FNDECL shall be profiled.
1290    SIZE_ARG be set to the argument index for the size of the string
1291    operation.
1292 */
1293 static bool
1294 interesting_stringop_to_profile_p (tree fndecl, gimple call, int *size_arg)
1295 {
1296   enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
1297
1298   if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY
1299       && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO)
1300     return false;
1301
1302   switch (fcode)
1303     {
1304      case BUILT_IN_MEMCPY:
1305      case BUILT_IN_MEMPCPY:
1306        *size_arg = 2;
1307        return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
1308                                        INTEGER_TYPE, VOID_TYPE);
1309      case BUILT_IN_MEMSET:
1310        *size_arg = 2;
1311        return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1312                                       INTEGER_TYPE, VOID_TYPE);
1313      case BUILT_IN_BZERO:
1314        *size_arg = 1;
1315        return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1316                                        VOID_TYPE);
1317      default:
1318        gcc_unreachable ();
1319     }
1320 }
1321
1322 /* Convert   stringop (..., vcall_size)
1323    into
1324    if (vcall_size == icall_size)
1325      stringop (..., icall_size);
1326    else
1327      stringop (..., vcall_size);
1328    assuming we'll propagate a true constant into ICALL_SIZE later.  */
1329
1330 static void
1331 gimple_stringop_fixed_value (gimple vcall_stmt, tree icall_size, int prob,
1332                              gcov_type count, gcov_type all)
1333 {
1334   gimple tmp_stmt, cond_stmt, icall_stmt;
1335   tree tmp0, tmp1, tmpv, vcall_size, optype;
1336   basic_block cond_bb, icall_bb, vcall_bb, join_bb;
1337   edge e_ci, e_cv, e_iv, e_ij, e_vj;
1338   gimple_stmt_iterator gsi;
1339   tree fndecl;
1340   int size_arg;
1341
1342   fndecl = gimple_call_fndecl (vcall_stmt);
1343   if (!interesting_stringop_to_profile_p (fndecl, vcall_stmt, &size_arg))
1344     gcc_unreachable();
1345
1346   cond_bb = gimple_bb (vcall_stmt);
1347   gsi = gsi_for_stmt (vcall_stmt);
1348
1349   vcall_size = gimple_call_arg (vcall_stmt, size_arg);
1350   optype = TREE_TYPE (vcall_size);
1351
1352   tmpv = create_tmp_var (optype, "PROF");
1353   tmp0 = make_ssa_name (tmpv, NULL);
1354   tmp1 = make_ssa_name (tmpv, NULL);
1355   tmp_stmt = gimple_build_assign (tmp0, fold_convert (optype, icall_size));
1356   SSA_NAME_DEF_STMT (tmp0) = tmp_stmt;
1357   gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1358
1359   tmp_stmt = gimple_build_assign (tmp1, vcall_size);
1360   SSA_NAME_DEF_STMT (tmp1) = tmp_stmt;
1361   gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1362
1363   cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1364   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1365
1366   gimple_set_vdef (vcall_stmt, NULL);
1367   gimple_set_vuse (vcall_stmt, NULL);
1368   update_stmt (vcall_stmt);
1369   icall_stmt = gimple_copy (vcall_stmt);
1370   gimple_call_set_arg (icall_stmt, size_arg, icall_size);
1371   gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT);
1372
1373   /* Fix CFG. */
1374   /* Edge e_ci connects cond_bb to icall_bb, etc. */
1375   e_ci = split_block (cond_bb, cond_stmt);
1376   icall_bb = e_ci->dest;
1377   icall_bb->count = count;
1378
1379   e_iv = split_block (icall_bb, icall_stmt);
1380   vcall_bb = e_iv->dest;
1381   vcall_bb->count = all - count;
1382
1383   e_vj = split_block (vcall_bb, vcall_stmt);
1384   join_bb = e_vj->dest;
1385   join_bb->count = all;
1386
1387   e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1388   e_ci->probability = prob;
1389   e_ci->count = count;
1390
1391   e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE);
1392   e_cv->probability = REG_BR_PROB_BASE - prob;
1393   e_cv->count = all - count;
1394
1395   remove_edge (e_iv);
1396
1397   e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU);
1398   e_ij->probability = REG_BR_PROB_BASE;
1399   e_ij->count = count;
1400
1401   e_vj->probability = REG_BR_PROB_BASE;
1402   e_vj->count = all - count;
1403
1404   /* Insert PHI node for the call result if necessary.  */
1405   if (gimple_call_lhs (vcall_stmt)
1406       && TREE_CODE (gimple_call_lhs (vcall_stmt)) == SSA_NAME)
1407     {
1408       tree result = gimple_call_lhs (vcall_stmt);
1409       gimple phi = create_phi_node (result, join_bb);
1410       SSA_NAME_DEF_STMT (result) = phi;
1411       gimple_call_set_lhs (vcall_stmt,
1412                            make_ssa_name (SSA_NAME_VAR (result), vcall_stmt));
1413       add_phi_arg (phi, gimple_call_lhs (vcall_stmt), e_vj, UNKNOWN_LOCATION);
1414       gimple_call_set_lhs (icall_stmt,
1415                            make_ssa_name (SSA_NAME_VAR (result), icall_stmt));
1416       add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1417     }
1418
1419   /* Because these are all string op builtins, they're all nothrow.  */
1420   gcc_assert (!stmt_could_throw_p (vcall_stmt));
1421   gcc_assert (!stmt_could_throw_p (icall_stmt));
1422 }
1423
1424 /* Find values inside STMT for that we want to measure histograms for
1425    division/modulo optimization.  */
1426 static bool
1427 gimple_stringops_transform (gimple_stmt_iterator *gsi)
1428 {
1429   gimple stmt = gsi_stmt (*gsi);
1430   tree fndecl;
1431   tree blck_size;
1432   enum built_in_function fcode;
1433   histogram_value histogram;
1434   gcov_type count, all, val;
1435   tree dest, src;
1436   unsigned int dest_align, src_align;
1437   gcov_type prob;
1438   tree tree_val;
1439   int size_arg;
1440
1441   if (gimple_code (stmt) != GIMPLE_CALL)
1442     return false;
1443   fndecl = gimple_call_fndecl (stmt);
1444   if (!fndecl)
1445     return false;
1446   fcode = DECL_FUNCTION_CODE (fndecl);
1447   if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg))
1448     return false;
1449
1450   blck_size = gimple_call_arg (stmt, size_arg);
1451   if (TREE_CODE (blck_size) == INTEGER_CST)
1452     return false;
1453
1454   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1455   if (!histogram)
1456     return false;
1457   val = histogram->hvalue.counters[0];
1458   count = histogram->hvalue.counters[1];
1459   all = histogram->hvalue.counters[2];
1460   gimple_remove_histogram_value (cfun, stmt, histogram);
1461   /* We require that count is at least half of all; this means
1462      that for the transformation to fire the value must be constant
1463      at least 80% of time.  */
1464   if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1465     return false;
1466   if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
1467     return false;
1468   if (all > 0)
1469     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1470   else
1471     prob = 0;
1472   dest = gimple_call_arg (stmt, 0);
1473   dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1474   switch (fcode)
1475     {
1476     case BUILT_IN_MEMCPY:
1477     case BUILT_IN_MEMPCPY:
1478       src = gimple_call_arg (stmt, 1);
1479       src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1480       if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1481         return false;
1482       break;
1483     case BUILT_IN_MEMSET:
1484       if (!can_store_by_pieces (val, builtin_memset_read_str,
1485                                 gimple_call_arg (stmt, 1),
1486                                 dest_align, true))
1487         return false;
1488       break;
1489     case BUILT_IN_BZERO:
1490       if (!can_store_by_pieces (val, builtin_memset_read_str,
1491                                 integer_zero_node,
1492                                 dest_align, true))
1493         return false;
1494       break;
1495     default:
1496       gcc_unreachable ();
1497     }
1498   tree_val = build_int_cst_wide (get_gcov_type (),
1499                                  (unsigned HOST_WIDE_INT) val,
1500                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1501   if (dump_file)
1502     {
1503       fprintf (dump_file, "Single value %i stringop transformation on ",
1504                (int)val);
1505       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1506     }
1507   gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
1508
1509   return true;
1510 }
1511
1512 void
1513 stringop_block_profile (gimple stmt, unsigned int *expected_align,
1514                         HOST_WIDE_INT *expected_size)
1515 {
1516   histogram_value histogram;
1517   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1518   if (!histogram)
1519     *expected_size = -1;
1520   else if (!histogram->hvalue.counters[1])
1521     {
1522       *expected_size = -1;
1523       gimple_remove_histogram_value (cfun, stmt, histogram);
1524     }
1525   else
1526     {
1527       gcov_type size;
1528       size = ((histogram->hvalue.counters[0]
1529               + histogram->hvalue.counters[1] / 2)
1530                / histogram->hvalue.counters[1]);
1531       /* Even if we can hold bigger value in SIZE, INT_MAX
1532          is safe "infinity" for code generation strategies.  */
1533       if (size > INT_MAX)
1534         size = INT_MAX;
1535       *expected_size = size;
1536       gimple_remove_histogram_value (cfun, stmt, histogram);
1537     }
1538   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1539   if (!histogram)
1540     *expected_align = 0;
1541   else if (!histogram->hvalue.counters[0])
1542     {
1543       gimple_remove_histogram_value (cfun, stmt, histogram);
1544       *expected_align = 0;
1545     }
1546   else
1547     {
1548       gcov_type count;
1549       int alignment;
1550
1551       count = histogram->hvalue.counters[0];
1552       alignment = 1;
1553       while (!(count & alignment)
1554              && (alignment * 2 * BITS_PER_UNIT))
1555         alignment <<= 1;
1556       *expected_align = alignment * BITS_PER_UNIT;
1557       gimple_remove_histogram_value (cfun, stmt, histogram);
1558     }
1559 }
1560
1561 \f
1562 /* Find values inside STMT for that we want to measure histograms for
1563    division/modulo optimization.  */
1564 static void
1565 gimple_divmod_values_to_profile (gimple stmt, histogram_values *values)
1566 {
1567   tree lhs, divisor, op0, type;
1568   histogram_value hist;
1569
1570   if (gimple_code (stmt) != GIMPLE_ASSIGN)
1571     return;
1572
1573   lhs = gimple_assign_lhs (stmt);
1574   type = TREE_TYPE (lhs);
1575   if (!INTEGRAL_TYPE_P (type))
1576     return;
1577
1578   switch (gimple_assign_rhs_code (stmt))
1579     {
1580     case TRUNC_DIV_EXPR:
1581     case TRUNC_MOD_EXPR:
1582       divisor = gimple_assign_rhs2 (stmt);
1583       op0 = gimple_assign_rhs1 (stmt);
1584
1585       VEC_reserve (histogram_value, heap, *values, 3);
1586
1587       if (is_gimple_reg (divisor))
1588         /* Check for the case where the divisor is the same value most
1589            of the time.  */
1590         VEC_quick_push (histogram_value, *values,
1591                         gimple_alloc_histogram_value (cfun,
1592                                                       HIST_TYPE_SINGLE_VALUE,
1593                                                       stmt, divisor));
1594
1595       /* For mod, check whether it is not often a noop (or replaceable by
1596          a few subtractions).  */
1597       if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
1598           && TYPE_UNSIGNED (type))
1599         {
1600           tree val;
1601           /* Check for a special case where the divisor is power of 2.  */
1602           VEC_quick_push (histogram_value, *values,
1603                           gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1604                                                         stmt, divisor));
1605
1606           val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1607           hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1608                                                stmt, val);
1609           hist->hdata.intvl.int_start = 0;
1610           hist->hdata.intvl.steps = 2;
1611           VEC_quick_push (histogram_value, *values, hist);
1612         }
1613       return;
1614
1615     default:
1616       return;
1617     }
1618 }
1619
1620 /* Find calls inside STMT for that we want to measure histograms for
1621    indirect/virtual call optimization. */
1622
1623 static void
1624 gimple_indirect_call_to_profile (gimple stmt, histogram_values *values)
1625 {
1626   tree callee;
1627
1628   if (gimple_code (stmt) != GIMPLE_CALL
1629       || gimple_call_fndecl (stmt) != NULL_TREE)
1630     return;
1631
1632   callee = gimple_call_fn (stmt);
1633
1634   VEC_reserve (histogram_value, heap, *values, 3);
1635
1636   VEC_quick_push (histogram_value, *values,
1637                   gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1638                                                 stmt, callee));
1639
1640   return;
1641 }
1642
1643 /* Find values inside STMT for that we want to measure histograms for
1644    string operations.  */
1645 static void
1646 gimple_stringops_values_to_profile (gimple stmt, histogram_values *values)
1647 {
1648   tree fndecl;
1649   tree blck_size;
1650   tree dest;
1651   int size_arg;
1652
1653   if (gimple_code (stmt) != GIMPLE_CALL)
1654     return;
1655   fndecl = gimple_call_fndecl (stmt);
1656   if (!fndecl)
1657     return;
1658
1659   if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg))
1660     return;
1661
1662   dest = gimple_call_arg (stmt, 0);
1663   blck_size = gimple_call_arg (stmt, size_arg);
1664
1665   if (TREE_CODE (blck_size) != INTEGER_CST)
1666     {
1667       VEC_safe_push (histogram_value, heap, *values,
1668                      gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1669                                                    stmt, blck_size));
1670       VEC_safe_push (histogram_value, heap, *values,
1671                      gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1672                                                    stmt, blck_size));
1673     }
1674   if (TREE_CODE (blck_size) != INTEGER_CST)
1675     VEC_safe_push (histogram_value, heap, *values,
1676                    gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1677                                                  stmt, dest));
1678 }
1679
1680 /* Find values inside STMT for that we want to measure histograms and adds
1681    them to list VALUES.  */
1682
1683 static void
1684 gimple_values_to_profile (gimple stmt, histogram_values *values)
1685 {
1686   if (flag_value_profile_transformations)
1687     {
1688       gimple_divmod_values_to_profile (stmt, values);
1689       gimple_stringops_values_to_profile (stmt, values);
1690       gimple_indirect_call_to_profile (stmt, values);
1691     }
1692 }
1693
1694 void
1695 gimple_find_values_to_profile (histogram_values *values)
1696 {
1697   basic_block bb;
1698   gimple_stmt_iterator gsi;
1699   unsigned i;
1700   histogram_value hist = NULL;
1701
1702   *values = NULL;
1703   FOR_EACH_BB (bb)
1704     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1705       gimple_values_to_profile (gsi_stmt (gsi), values);
1706
1707   FOR_EACH_VEC_ELT (histogram_value, *values, i, hist)
1708     {
1709       switch (hist->type)
1710         {
1711         case HIST_TYPE_INTERVAL:
1712           hist->n_counters = hist->hdata.intvl.steps + 2;
1713           break;
1714
1715         case HIST_TYPE_POW2:
1716           hist->n_counters = 2;
1717           break;
1718
1719         case HIST_TYPE_SINGLE_VALUE:
1720           hist->n_counters = 3;
1721           break;
1722
1723         case HIST_TYPE_CONST_DELTA:
1724           hist->n_counters = 4;
1725           break;
1726
1727         case HIST_TYPE_INDIR_CALL:
1728           hist->n_counters = 3;
1729           break;
1730
1731         case HIST_TYPE_AVERAGE:
1732           hist->n_counters = 2;
1733           break;
1734
1735         case HIST_TYPE_IOR:
1736           hist->n_counters = 1;
1737           break;
1738
1739         default:
1740           gcc_unreachable ();
1741         }
1742       if (dump_file)
1743         {
1744           fprintf (dump_file, "Stmt ");
1745           print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
1746           dump_histogram_value (dump_file, hist);
1747         }
1748     }
1749 }
1750