gcc/value-prof.c

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