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 (last_stmt (icall_bb) != icall_stmt)
1150     e_ij = split_block (icall_bb, icall_stmt);
1151   else
1152     e_ij = find_fallthru_edge (icall_bb->succs);
1153   join_bb = e_ij->dest;
1154   join_bb->count = all;
1155
1156   e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1157   e_cd->probability = prob;
1158   e_cd->count = count;
1159
1160   e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE);
1161   e_ci->probability = REG_BR_PROB_BASE - prob;
1162   e_ci->count = all - count;
1163
1164   remove_edge (e_di);
1165
1166   e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU);
1167   e_dj->probability = REG_BR_PROB_BASE;
1168   e_dj->count = count;
1169
1170   e_ij->probability = REG_BR_PROB_BASE;
1171   e_ij->count = all - count;
1172
1173   /* Insert PHI node for the call result if necessary.  */
1174   if (gimple_call_lhs (icall_stmt)
1175       && TREE_CODE (gimple_call_lhs (icall_stmt)) == SSA_NAME)
1176     {
1177       tree result = gimple_call_lhs (icall_stmt);
1178       gimple phi = create_phi_node (result, join_bb);
1179       SSA_NAME_DEF_STMT (result) = phi;
1180       gimple_call_set_lhs (icall_stmt,
1181                            make_ssa_name (SSA_NAME_VAR (result), icall_stmt));
1182       add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1183       gimple_call_set_lhs (dcall_stmt,
1184                            make_ssa_name (SSA_NAME_VAR (result), dcall_stmt));
1185       add_phi_arg (phi, gimple_call_lhs (dcall_stmt), e_dj, UNKNOWN_LOCATION);
1186     }
1187
1188   /* Build an EH edge for the direct call if necessary.  */
1189   lp_nr = lookup_stmt_eh_lp (icall_stmt);
1190   if (lp_nr != 0
1191       && stmt_could_throw_p (dcall_stmt))
1192     {
1193       edge e_eh, e;
1194       edge_iterator ei;
1195       gimple_stmt_iterator psi;
1196
1197       add_stmt_to_eh_lp (dcall_stmt, lp_nr);
1198       FOR_EACH_EDGE (e_eh, ei, icall_bb->succs)
1199         if (e_eh->flags & EDGE_EH)
1200           break;
1201       e = make_edge (dcall_bb, e_eh->dest, EDGE_EH);
1202       for (psi = gsi_start_phis (e_eh->dest);
1203            !gsi_end_p (psi); gsi_next (&psi))
1204         {
1205           gimple phi = gsi_stmt (psi);
1206           SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e),
1207                    PHI_ARG_DEF_FROM_EDGE (phi, e_eh));
1208         }
1209     }
1210
1211   return dcall_stmt;
1212 }
1213
1214 /*
1215   For every checked indirect/virtual call determine if most common pid of
1216   function/class method has probability more than 50%. If yes modify code of
1217   this call to:
1218  */
1219
1220 static bool
1221 gimple_ic_transform (gimple stmt)
1222 {
1223   histogram_value histogram;
1224   gcov_type val, count, all, bb_all;
1225   gcov_type prob;
1226   tree callee;
1227   gimple modify;
1228   struct cgraph_node *direct_call;
1229
1230   if (gimple_code (stmt) != GIMPLE_CALL)
1231     return false;
1232
1233   callee = gimple_call_fn (stmt);
1234
1235   if (TREE_CODE (callee) == FUNCTION_DECL)
1236     return false;
1237
1238   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1239   if (!histogram)
1240     return false;
1241
1242   val = histogram->hvalue.counters [0];
1243   count = histogram->hvalue.counters [1];
1244   all = histogram->hvalue.counters [2];
1245   gimple_remove_histogram_value (cfun, stmt, histogram);
1246
1247   if (4 * count <= 3 * all)
1248     return false;
1249
1250   bb_all = gimple_bb (stmt)->count;
1251   /* The order of CHECK_COUNTER calls is important -
1252      since check_counter can correct the third parameter
1253      and we want to make count <= all <= bb_all. */
1254   if ( check_counter (stmt, "ic", &all, &bb_all, bb_all)
1255       || check_counter (stmt, "ic", &count, &all, all))
1256     return false;
1257
1258   if (all > 0)
1259     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1260   else
1261     prob = 0;
1262   direct_call = find_func_by_pid ((int)val);
1263
1264   if (direct_call == NULL)
1265     return false;
1266
1267   modify = gimple_ic (stmt, direct_call, prob, count, all);
1268
1269   if (dump_file)
1270     {
1271       fprintf (dump_file, "Indirect call -> direct call ");
1272       print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1273       fprintf (dump_file, "=> ");
1274       print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1275       fprintf (dump_file, " transformation on insn ");
1276       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1277       fprintf (dump_file, " to ");
1278       print_gimple_stmt (dump_file, modify, 0, TDF_SLIM);
1279       fprintf (dump_file, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1280                " hist->all "HOST_WIDEST_INT_PRINT_DEC"\n", count, all);
1281     }
1282
1283   return true;
1284 }
1285
1286 /* Return true if the stringop CALL with FNDECL shall be profiled.
1287    SIZE_ARG be set to the argument index for the size of the string
1288    operation.
1289 */
1290 static bool
1291 interesting_stringop_to_profile_p (tree fndecl, gimple call, int *size_arg)
1292 {
1293   enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
1294
1295   if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY
1296       && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO)
1297     return false;
1298
1299   switch (fcode)
1300     {
1301      case BUILT_IN_MEMCPY:
1302      case BUILT_IN_MEMPCPY:
1303        *size_arg = 2;
1304        return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
1305                                        INTEGER_TYPE, VOID_TYPE);
1306      case BUILT_IN_MEMSET:
1307        *size_arg = 2;
1308        return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1309                                       INTEGER_TYPE, VOID_TYPE);
1310      case BUILT_IN_BZERO:
1311        *size_arg = 1;
1312        return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1313                                        VOID_TYPE);
1314      default:
1315        gcc_unreachable ();
1316     }
1317 }
1318
1319 /* Convert   stringop (..., vcall_size)
1320    into
1321    if (vcall_size == icall_size)
1322      stringop (..., icall_size);
1323    else
1324      stringop (..., vcall_size);
1325    assuming we'll propagate a true constant into ICALL_SIZE later.  */
1326
1327 static void
1328 gimple_stringop_fixed_value (gimple vcall_stmt, tree icall_size, int prob,
1329                              gcov_type count, gcov_type all)
1330 {
1331   gimple tmp_stmt, cond_stmt, icall_stmt;
1332   tree tmp0, tmp1, tmpv, vcall_size, optype;
1333   basic_block cond_bb, icall_bb, vcall_bb, join_bb;
1334   edge e_ci, e_cv, e_iv, e_ij, e_vj;
1335   gimple_stmt_iterator gsi;
1336   tree fndecl;
1337   int size_arg;
1338
1339   fndecl = gimple_call_fndecl (vcall_stmt);
1340   if (!interesting_stringop_to_profile_p (fndecl, vcall_stmt, &size_arg))
1341     gcc_unreachable();
1342
1343   cond_bb = gimple_bb (vcall_stmt);
1344   gsi = gsi_for_stmt (vcall_stmt);
1345
1346   vcall_size = gimple_call_arg (vcall_stmt, size_arg);
1347   optype = TREE_TYPE (vcall_size);
1348
1349   tmpv = create_tmp_var (optype, "PROF");
1350   tmp0 = make_ssa_name (tmpv, NULL);
1351   tmp1 = make_ssa_name (tmpv, NULL);
1352   tmp_stmt = gimple_build_assign (tmp0, fold_convert (optype, icall_size));
1353   SSA_NAME_DEF_STMT (tmp0) = tmp_stmt;
1354   gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1355
1356   tmp_stmt = gimple_build_assign (tmp1, vcall_size);
1357   SSA_NAME_DEF_STMT (tmp1) = tmp_stmt;
1358   gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1359
1360   cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1361   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1362
1363   gimple_set_vdef (vcall_stmt, NULL);
1364   gimple_set_vuse (vcall_stmt, NULL);
1365   update_stmt (vcall_stmt);
1366   icall_stmt = gimple_copy (vcall_stmt);
1367   gimple_call_set_arg (icall_stmt, size_arg, icall_size);
1368   gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT);
1369
1370   /* Fix CFG. */
1371   /* Edge e_ci connects cond_bb to icall_bb, etc. */
1372   e_ci = split_block (cond_bb, cond_stmt);
1373   icall_bb = e_ci->dest;
1374   icall_bb->count = count;
1375
1376   e_iv = split_block (icall_bb, icall_stmt);
1377   vcall_bb = e_iv->dest;
1378   vcall_bb->count = all - count;
1379
1380   e_vj = split_block (vcall_bb, vcall_stmt);
1381   join_bb = e_vj->dest;
1382   join_bb->count = all;
1383
1384   e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1385   e_ci->probability = prob;
1386   e_ci->count = count;
1387
1388   e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE);
1389   e_cv->probability = REG_BR_PROB_BASE - prob;
1390   e_cv->count = all - count;
1391
1392   remove_edge (e_iv);
1393
1394   e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU);
1395   e_ij->probability = REG_BR_PROB_BASE;
1396   e_ij->count = count;
1397
1398   e_vj->probability = REG_BR_PROB_BASE;
1399   e_vj->count = all - count;
1400
1401   /* Because these are all string op builtins, they're all nothrow.  */
1402   gcc_assert (!stmt_could_throw_p (vcall_stmt));
1403   gcc_assert (!stmt_could_throw_p (icall_stmt));
1404 }
1405
1406 /* Find values inside STMT for that we want to measure histograms for
1407    division/modulo optimization.  */
1408 static bool
1409 gimple_stringops_transform (gimple_stmt_iterator *gsi)
1410 {
1411   gimple stmt = gsi_stmt (*gsi);
1412   tree fndecl;
1413   tree blck_size;
1414   enum built_in_function fcode;
1415   histogram_value histogram;
1416   gcov_type count, all, val;
1417   tree dest, src;
1418   unsigned int dest_align, src_align;
1419   gcov_type prob;
1420   tree tree_val;
1421   int size_arg;
1422
1423   if (gimple_code (stmt) != GIMPLE_CALL)
1424     return false;
1425   fndecl = gimple_call_fndecl (stmt);
1426   if (!fndecl)
1427     return false;
1428   fcode = DECL_FUNCTION_CODE (fndecl);
1429   if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg))
1430     return false;
1431
1432   blck_size = gimple_call_arg (stmt, size_arg);
1433   if (TREE_CODE (blck_size) == INTEGER_CST)
1434     return false;
1435
1436   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1437   if (!histogram)
1438     return false;
1439   val = histogram->hvalue.counters[0];
1440   count = histogram->hvalue.counters[1];
1441   all = histogram->hvalue.counters[2];
1442   gimple_remove_histogram_value (cfun, stmt, histogram);
1443   /* We require that count is at least half of all; this means
1444      that for the transformation to fire the value must be constant
1445      at least 80% of time.  */
1446   if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1447     return false;
1448   if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
1449     return false;
1450   if (all > 0)
1451     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1452   else
1453     prob = 0;
1454   dest = gimple_call_arg (stmt, 0);
1455   dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1456   switch (fcode)
1457     {
1458     case BUILT_IN_MEMCPY:
1459     case BUILT_IN_MEMPCPY:
1460       src = gimple_call_arg (stmt, 1);
1461       src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1462       if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1463         return false;
1464       break;
1465     case BUILT_IN_MEMSET:
1466       if (!can_store_by_pieces (val, builtin_memset_read_str,
1467                                 gimple_call_arg (stmt, 1),
1468                                 dest_align, true))
1469         return false;
1470       break;
1471     case BUILT_IN_BZERO:
1472       if (!can_store_by_pieces (val, builtin_memset_read_str,
1473                                 integer_zero_node,
1474                                 dest_align, true))
1475         return false;
1476       break;
1477     default:
1478       gcc_unreachable ();
1479     }
1480   tree_val = build_int_cst_wide (get_gcov_type (),
1481                                  (unsigned HOST_WIDE_INT) val,
1482                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1483   if (dump_file)
1484     {
1485       fprintf (dump_file, "Single value %i stringop transformation on ",
1486                (int)val);
1487       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1488     }
1489   gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
1490
1491   return true;
1492 }
1493
1494 void
1495 stringop_block_profile (gimple stmt, unsigned int *expected_align,
1496                         HOST_WIDE_INT *expected_size)
1497 {
1498   histogram_value histogram;
1499   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1500   if (!histogram)
1501     *expected_size = -1;
1502   else if (!histogram->hvalue.counters[1])
1503     {
1504       *expected_size = -1;
1505       gimple_remove_histogram_value (cfun, stmt, histogram);
1506     }
1507   else
1508     {
1509       gcov_type size;
1510       size = ((histogram->hvalue.counters[0]
1511               + histogram->hvalue.counters[1] / 2)
1512                / histogram->hvalue.counters[1]);
1513       /* Even if we can hold bigger value in SIZE, INT_MAX
1514          is safe "infinity" for code generation strategies.  */
1515       if (size > INT_MAX)
1516         size = INT_MAX;
1517       *expected_size = size;
1518       gimple_remove_histogram_value (cfun, stmt, histogram);
1519     }
1520   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1521   if (!histogram)
1522     *expected_align = 0;
1523   else if (!histogram->hvalue.counters[0])
1524     {
1525       gimple_remove_histogram_value (cfun, stmt, histogram);
1526       *expected_align = 0;
1527     }
1528   else
1529     {
1530       gcov_type count;
1531       int alignment;
1532
1533       count = histogram->hvalue.counters[0];
1534       alignment = 1;
1535       while (!(count & alignment)
1536              && (alignment * 2 * BITS_PER_UNIT))
1537         alignment <<= 1;
1538       *expected_align = alignment * BITS_PER_UNIT;
1539       gimple_remove_histogram_value (cfun, stmt, histogram);
1540     }
1541 }
1542
1543 struct value_prof_hooks {
1544   /* Find list of values for which we want to measure histograms.  */
1545   void (*find_values_to_profile) (histogram_values *);
1546
1547   /* Identify and exploit properties of values that are hard to analyze
1548      statically.  See value-prof.c for more detail.  */
1549   bool (*value_profile_transformations) (void);
1550 };
1551 \f
1552 /* Find values inside STMT for that we want to measure histograms for
1553    division/modulo optimization.  */
1554 static void
1555 gimple_divmod_values_to_profile (gimple stmt, histogram_values *values)
1556 {
1557   tree lhs, divisor, op0, type;
1558   histogram_value hist;
1559
1560   if (gimple_code (stmt) != GIMPLE_ASSIGN)
1561     return;
1562
1563   lhs = gimple_assign_lhs (stmt);
1564   type = TREE_TYPE (lhs);
1565   if (!INTEGRAL_TYPE_P (type))
1566     return;
1567
1568   switch (gimple_assign_rhs_code (stmt))
1569     {
1570     case TRUNC_DIV_EXPR:
1571     case TRUNC_MOD_EXPR:
1572       divisor = gimple_assign_rhs2 (stmt);
1573       op0 = gimple_assign_rhs1 (stmt);
1574
1575       VEC_reserve (histogram_value, heap, *values, 3);
1576
1577       if (is_gimple_reg (divisor))
1578         /* Check for the case where the divisor is the same value most
1579            of the time.  */
1580         VEC_quick_push (histogram_value, *values,
1581                         gimple_alloc_histogram_value (cfun,
1582                                                       HIST_TYPE_SINGLE_VALUE,
1583                                                       stmt, divisor));
1584
1585       /* For mod, check whether it is not often a noop (or replaceable by
1586          a few subtractions).  */
1587       if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
1588           && TYPE_UNSIGNED (type))
1589         {
1590           tree val;
1591           /* Check for a special case where the divisor is power of 2.  */
1592           VEC_quick_push (histogram_value, *values,
1593                           gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1594                                                         stmt, divisor));
1595
1596           val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1597           hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1598                                                stmt, val);
1599           hist->hdata.intvl.int_start = 0;
1600           hist->hdata.intvl.steps = 2;
1601           VEC_quick_push (histogram_value, *values, hist);
1602         }
1603       return;
1604
1605     default:
1606       return;
1607     }
1608 }
1609
1610 /* Find calls inside STMT for that we want to measure histograms for
1611    indirect/virtual call optimization. */
1612
1613 static void
1614 gimple_indirect_call_to_profile (gimple stmt, histogram_values *values)
1615 {
1616   tree callee;
1617
1618   if (gimple_code (stmt) != GIMPLE_CALL
1619       || gimple_call_fndecl (stmt) != NULL_TREE)
1620     return;
1621
1622   callee = gimple_call_fn (stmt);
1623
1624   VEC_reserve (histogram_value, heap, *values, 3);
1625
1626   VEC_quick_push (histogram_value, *values,
1627                   gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1628                                                 stmt, callee));
1629
1630   return;
1631 }
1632
1633 /* Find values inside STMT for that we want to measure histograms for
1634    string operations.  */
1635 static void
1636 gimple_stringops_values_to_profile (gimple stmt, histogram_values *values)
1637 {
1638   tree fndecl;
1639   tree blck_size;
1640   tree dest;
1641   int size_arg;
1642
1643   if (gimple_code (stmt) != GIMPLE_CALL)
1644     return;
1645   fndecl = gimple_call_fndecl (stmt);
1646   if (!fndecl)
1647     return;
1648
1649   if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg))
1650     return;
1651
1652   dest = gimple_call_arg (stmt, 0);
1653   blck_size = gimple_call_arg (stmt, size_arg);
1654
1655   if (TREE_CODE (blck_size) != INTEGER_CST)
1656     {
1657       VEC_safe_push (histogram_value, heap, *values,
1658                      gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1659                                                    stmt, blck_size));
1660       VEC_safe_push (histogram_value, heap, *values,
1661                      gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1662                                                    stmt, blck_size));
1663     }
1664   if (TREE_CODE (blck_size) != INTEGER_CST)
1665     VEC_safe_push (histogram_value, heap, *values,
1666                    gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1667                                                  stmt, dest));
1668 }
1669
1670 /* Find values inside STMT for that we want to measure histograms and adds
1671    them to list VALUES.  */
1672
1673 static void
1674 gimple_values_to_profile (gimple stmt, histogram_values *values)
1675 {
1676   if (flag_value_profile_transformations)
1677     {
1678       gimple_divmod_values_to_profile (stmt, values);
1679       gimple_stringops_values_to_profile (stmt, values);
1680       gimple_indirect_call_to_profile (stmt, values);
1681     }
1682 }
1683
1684 static void
1685 gimple_find_values_to_profile (histogram_values *values)
1686 {
1687   basic_block bb;
1688   gimple_stmt_iterator gsi;
1689   unsigned i;
1690   histogram_value hist = NULL;
1691
1692   *values = NULL;
1693   FOR_EACH_BB (bb)
1694     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1695       gimple_values_to_profile (gsi_stmt (gsi), values);
1696
1697   FOR_EACH_VEC_ELT (histogram_value, *values, i, hist)
1698     {
1699       switch (hist->type)
1700         {
1701         case HIST_TYPE_INTERVAL:
1702           hist->n_counters = hist->hdata.intvl.steps + 2;
1703           break;
1704
1705         case HIST_TYPE_POW2:
1706           hist->n_counters = 2;
1707           break;
1708
1709         case HIST_TYPE_SINGLE_VALUE:
1710           hist->n_counters = 3;
1711           break;
1712
1713         case HIST_TYPE_CONST_DELTA:
1714           hist->n_counters = 4;
1715           break;
1716
1717         case HIST_TYPE_INDIR_CALL:
1718           hist->n_counters = 3;
1719           break;
1720
1721         case HIST_TYPE_AVERAGE:
1722           hist->n_counters = 2;
1723           break;
1724
1725         case HIST_TYPE_IOR:
1726           hist->n_counters = 1;
1727           break;
1728
1729         default:
1730           gcc_unreachable ();
1731         }
1732       if (dump_file)
1733         {
1734           fprintf (dump_file, "Stmt ");
1735           print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
1736           dump_histogram_value (dump_file, hist);
1737         }
1738     }
1739 }
1740
1741 static struct value_prof_hooks gimple_value_prof_hooks = {
1742   gimple_find_values_to_profile,
1743   gimple_value_profile_transformations
1744 };
1745
1746 void
1747 gimple_register_value_prof_hooks (void)
1748 {
1749   gcc_assert (current_ir_type () == IR_GIMPLE);
1750   value_prof_hooks = &gimple_value_prof_hooks;
1751 }
1752 \f
1753 /* IR-independent entry points.  */
1754 void
1755 find_values_to_profile (histogram_values *values)
1756 {
1757   (value_prof_hooks->find_values_to_profile) (values);
1758 }
1759
1760 bool
1761 value_profile_transformations (void)
1762 {
1763   return (value_prof_hooks->value_profile_transformations) ();
1764 }
1765 \f