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