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