gcc/value-prof.c

   1 /* Transformations based on profile information for values.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   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   /* Because these are all string op builtins, they're all nothrow.  */
1405   gcc_assert (!stmt_could_throw_p (vcall_stmt));
1406   gcc_assert (!stmt_could_throw_p (icall_stmt));
1407 }
1408
1409 /* Find values inside STMT for that we want to measure histograms for
1410    division/modulo optimization.  */
1411 static bool
1412 gimple_stringops_transform (gimple_stmt_iterator *gsi)
1413 {
1414   gimple stmt = gsi_stmt (*gsi);
1415   tree fndecl;
1416   tree blck_size;
1417   enum built_in_function fcode;
1418   histogram_value histogram;
1419   gcov_type count, all, val;
1420   tree dest, src;
1421   unsigned int dest_align, src_align;
1422   gcov_type prob;
1423   tree tree_val;
1424   int size_arg;
1425
1426   if (gimple_code (stmt) != GIMPLE_CALL)
1427     return false;
1428   fndecl = gimple_call_fndecl (stmt);
1429   if (!fndecl)
1430     return false;
1431   fcode = DECL_FUNCTION_CODE (fndecl);
1432   if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg))
1433     return false;
1434
1435   blck_size = gimple_call_arg (stmt, size_arg);
1436   if (TREE_CODE (blck_size) == INTEGER_CST)
1437     return false;
1438
1439   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1440   if (!histogram)
1441     return false;
1442   val = histogram->hvalue.counters[0];
1443   count = histogram->hvalue.counters[1];
1444   all = histogram->hvalue.counters[2];
1445   gimple_remove_histogram_value (cfun, stmt, histogram);
1446   /* We require that count is at least half of all; this means
1447      that for the transformation to fire the value must be constant
1448      at least 80% of time.  */
1449   if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1450     return false;
1451   if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
1452     return false;
1453   if (all > 0)
1454     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1455   else
1456     prob = 0;
1457   dest = gimple_call_arg (stmt, 0);
1458   dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1459   switch (fcode)
1460     {
1461     case BUILT_IN_MEMCPY:
1462     case BUILT_IN_MEMPCPY:
1463       src = gimple_call_arg (stmt, 1);
1464       src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1465       if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1466         return false;
1467       break;
1468     case BUILT_IN_MEMSET:
1469       if (!can_store_by_pieces (val, builtin_memset_read_str,
1470                                 gimple_call_arg (stmt, 1),
1471                                 dest_align, true))
1472         return false;
1473       break;
1474     case BUILT_IN_BZERO:
1475       if (!can_store_by_pieces (val, builtin_memset_read_str,
1476                                 integer_zero_node,
1477                                 dest_align, true))
1478         return false;
1479       break;
1480     default:
1481       gcc_unreachable ();
1482     }
1483   tree_val = build_int_cst_wide (get_gcov_type (),
1484                                  (unsigned HOST_WIDE_INT) val,
1485                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1486   if (dump_file)
1487     {
1488       fprintf (dump_file, "Single value %i stringop transformation on ",
1489                (int)val);
1490       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1491     }
1492   gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
1493
1494   return true;
1495 }
1496
1497 void
1498 stringop_block_profile (gimple stmt, unsigned int *expected_align,
1499                         HOST_WIDE_INT *expected_size)
1500 {
1501   histogram_value histogram;
1502   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1503   if (!histogram)
1504     *expected_size = -1;
1505   else if (!histogram->hvalue.counters[1])
1506     {
1507       *expected_size = -1;
1508       gimple_remove_histogram_value (cfun, stmt, histogram);
1509     }
1510   else
1511     {
1512       gcov_type size;
1513       size = ((histogram->hvalue.counters[0]
1514               + histogram->hvalue.counters[1] / 2)
1515                / histogram->hvalue.counters[1]);
1516       /* Even if we can hold bigger value in SIZE, INT_MAX
1517          is safe "infinity" for code generation strategies.  */
1518       if (size > INT_MAX)
1519         size = INT_MAX;
1520       *expected_size = size;
1521       gimple_remove_histogram_value (cfun, stmt, histogram);
1522     }
1523   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1524   if (!histogram)
1525     *expected_align = 0;
1526   else if (!histogram->hvalue.counters[0])
1527     {
1528       gimple_remove_histogram_value (cfun, stmt, histogram);
1529       *expected_align = 0;
1530     }
1531   else
1532     {
1533       gcov_type count;
1534       int alignment;
1535
1536       count = histogram->hvalue.counters[0];
1537       alignment = 1;
1538       while (!(count & alignment)
1539              && (alignment * 2 * BITS_PER_UNIT))
1540         alignment <<= 1;
1541       *expected_align = alignment * BITS_PER_UNIT;
1542       gimple_remove_histogram_value (cfun, stmt, histogram);
1543     }
1544 }
1545
1546 \f
1547 /* Find values inside STMT for that we want to measure histograms for
1548    division/modulo optimization.  */
1549 static void
1550 gimple_divmod_values_to_profile (gimple stmt, histogram_values *values)
1551 {
1552   tree lhs, divisor, op0, type;
1553   histogram_value hist;
1554
1555   if (gimple_code (stmt) != GIMPLE_ASSIGN)
1556     return;
1557
1558   lhs = gimple_assign_lhs (stmt);
1559   type = TREE_TYPE (lhs);
1560   if (!INTEGRAL_TYPE_P (type))
1561     return;
1562
1563   switch (gimple_assign_rhs_code (stmt))
1564     {
1565     case TRUNC_DIV_EXPR:
1566     case TRUNC_MOD_EXPR:
1567       divisor = gimple_assign_rhs2 (stmt);
1568       op0 = gimple_assign_rhs1 (stmt);
1569
1570       VEC_reserve (histogram_value, heap, *values, 3);
1571
1572       if (is_gimple_reg (divisor))
1573         /* Check for the case where the divisor is the same value most
1574            of the time.  */
1575         VEC_quick_push (histogram_value, *values,
1576                         gimple_alloc_histogram_value (cfun,
1577                                                       HIST_TYPE_SINGLE_VALUE,
1578                                                       stmt, divisor));
1579
1580       /* For mod, check whether it is not often a noop (or replaceable by
1581          a few subtractions).  */
1582       if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
1583           && TYPE_UNSIGNED (type))
1584         {
1585           tree val;
1586           /* Check for a special case where the divisor is power of 2.  */
1587           VEC_quick_push (histogram_value, *values,
1588                           gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1589                                                         stmt, divisor));
1590
1591           val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1592           hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1593                                                stmt, val);
1594           hist->hdata.intvl.int_start = 0;
1595           hist->hdata.intvl.steps = 2;
1596           VEC_quick_push (histogram_value, *values, hist);
1597         }
1598       return;
1599
1600     default:
1601       return;
1602     }
1603 }
1604
1605 /* Find calls inside STMT for that we want to measure histograms for
1606    indirect/virtual call optimization. */
1607
1608 static void
1609 gimple_indirect_call_to_profile (gimple stmt, histogram_values *values)
1610 {
1611   tree callee;
1612
1613   if (gimple_code (stmt) != GIMPLE_CALL
1614       || gimple_call_fndecl (stmt) != NULL_TREE)
1615     return;
1616
1617   callee = gimple_call_fn (stmt);
1618
1619   VEC_reserve (histogram_value, heap, *values, 3);
1620
1621   VEC_quick_push (histogram_value, *values,
1622                   gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1623                                                 stmt, callee));
1624
1625   return;
1626 }
1627
1628 /* Find values inside STMT for that we want to measure histograms for
1629    string operations.  */
1630 static void
1631 gimple_stringops_values_to_profile (gimple stmt, histogram_values *values)
1632 {
1633   tree fndecl;
1634   tree blck_size;
1635   tree dest;
1636   int size_arg;
1637
1638   if (gimple_code (stmt) != GIMPLE_CALL)
1639     return;
1640   fndecl = gimple_call_fndecl (stmt);
1641   if (!fndecl)
1642     return;
1643
1644   if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg))
1645     return;
1646
1647   dest = gimple_call_arg (stmt, 0);
1648   blck_size = gimple_call_arg (stmt, size_arg);
1649
1650   if (TREE_CODE (blck_size) != INTEGER_CST)
1651     {
1652       VEC_safe_push (histogram_value, heap, *values,
1653                      gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1654                                                    stmt, blck_size));
1655       VEC_safe_push (histogram_value, heap, *values,
1656                      gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1657                                                    stmt, blck_size));
1658     }
1659   if (TREE_CODE (blck_size) != INTEGER_CST)
1660     VEC_safe_push (histogram_value, heap, *values,
1661                    gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1662                                                  stmt, dest));
1663 }
1664
1665 /* Find values inside STMT for that we want to measure histograms and adds
1666    them to list VALUES.  */
1667
1668 static void
1669 gimple_values_to_profile (gimple stmt, histogram_values *values)
1670 {
1671   if (flag_value_profile_transformations)
1672     {
1673       gimple_divmod_values_to_profile (stmt, values);
1674       gimple_stringops_values_to_profile (stmt, values);
1675       gimple_indirect_call_to_profile (stmt, values);
1676     }
1677 }
1678
1679 void
1680 gimple_find_values_to_profile (histogram_values *values)
1681 {
1682   basic_block bb;
1683   gimple_stmt_iterator gsi;
1684   unsigned i;
1685   histogram_value hist = NULL;
1686
1687   *values = NULL;
1688   FOR_EACH_BB (bb)
1689     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1690       gimple_values_to_profile (gsi_stmt (gsi), values);
1691
1692   FOR_EACH_VEC_ELT (histogram_value, *values, i, hist)
1693     {
1694       switch (hist->type)
1695         {
1696         case HIST_TYPE_INTERVAL:
1697           hist->n_counters = hist->hdata.intvl.steps + 2;
1698           break;
1699
1700         case HIST_TYPE_POW2:
1701           hist->n_counters = 2;
1702           break;
1703
1704         case HIST_TYPE_SINGLE_VALUE:
1705           hist->n_counters = 3;
1706           break;
1707
1708         case HIST_TYPE_CONST_DELTA:
1709           hist->n_counters = 4;
1710           break;
1711
1712         case HIST_TYPE_INDIR_CALL:
1713           hist->n_counters = 3;
1714           break;
1715
1716         case HIST_TYPE_AVERAGE:
1717           hist->n_counters = 2;
1718           break;
1719
1720         case HIST_TYPE_IOR:
1721           hist->n_counters = 1;
1722           break;
1723
1724         default:
1725           gcc_unreachable ();
1726         }
1727       if (dump_file)
1728         {
1729           fprintf (dump_file, "Stmt ");
1730           print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
1731           dump_histogram_value (dump_file, hist);
1732         }
1733     }
1734 }
1735