gcc/value-prof.c

   1 /* Transformations based on profile information for values.
   2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  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 "timevar.h"
  44 #include "tree-pass.h"
  45 #include "toplev.h"
  46 #include "pointer-set.h"
  47
  48 static struct value_prof_hooks *value_prof_hooks;
  49
  50 /* In this file value profile based optimizations are placed.  Currently the
  51    following optimizations are implemented (for more detailed descriptions
  52    see comments at value_profile_transformations):
  53
  54    1) Division/modulo specialization.  Provided that we can determine that the
  55       operands of the division have some special properties, we may use it to
  56       produce more effective code.
  57    2) Speculative prefetching.  If we are able to determine that the difference
  58       between addresses accessed by a memory reference is usually constant, we
  59       may add the prefetch instructions.
  60       FIXME: This transformation was removed together with RTL based value
  61       profiling.
  62
  63    Every such optimization should add its requirements for profiled values to
  64    insn_values_to_profile function.  This function is called from branch_prob
  65    in profile.c and the requested values are instrumented by it in the first
  66    compilation with -fprofile-arcs.  The optimization may then read the
  67    gathered data in the second compilation with -fbranch-probabilities.
  68
  69    The measured data is pointed to from the histograms
  70    field of the statement annotation of the instrumented insns.  It is
  71    kept as a linked list of struct histogram_value_t's, which contain the
  72    same information as above.  */
  73
  74
  75 static tree tree_divmod_fixed_value (tree, tree, tree, tree,
  76                                     tree, int, gcov_type, gcov_type);
  77 static tree tree_mod_pow2 (tree, tree, tree, tree, int, gcov_type, gcov_type);
  78 static tree tree_mod_subtract (tree, tree, tree, tree, int, int, int,
  79                                 gcov_type, gcov_type, gcov_type);
  80 static bool tree_divmod_fixed_value_transform (tree);
  81 static bool tree_mod_pow2_value_transform (tree);
  82 static bool tree_mod_subtract_transform (tree);
  83 static bool tree_stringops_transform (block_stmt_iterator *);
  84
  85 /* Allocate histogram value.  */
  86
  87 static histogram_value
  88 gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
  89                               enum hist_type type, tree stmt, tree value)
  90 {
  91    histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
  92    hist->hvalue.value = value;
  93    hist->hvalue.stmt = stmt;
  94    hist->type = type;
  95    return hist;
  96 }
  97
  98 /* Hash value for histogram.  */
  99
 100 static hashval_t
 101 histogram_hash (const void *x)
 102 {
 103   return htab_hash_pointer (((histogram_value)x)->hvalue.stmt);
 104 }
 105
 106 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y.  */
 107
 108 static int
 109 histogram_eq (const void *x, const void *y)
 110 {
 111   return ((histogram_value) x)->hvalue.stmt == (tree)y;
 112 }
 113
 114 /* Set histogram for STMT.  */
 115
 116 static void
 117 set_histogram_value (struct function *fun, tree stmt, histogram_value hist)
 118 {
 119   void **loc;
 120   if (!hist && !VALUE_HISTOGRAMS (fun))
 121     return;
 122   if (!VALUE_HISTOGRAMS (fun))
 123     VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
 124                                            histogram_eq, NULL);
 125   loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
 126                                   htab_hash_pointer (stmt),
 127                                   hist ? INSERT : NO_INSERT);
 128   if (!hist)
 129     {
 130       if (loc)
 131         htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
 132       return;
 133     }
 134   *loc = hist;
 135 }
 136
 137 /* Get histogram list for STMT.  */
 138
 139 histogram_value
 140 gimple_histogram_value (struct function *fun, tree stmt)
 141 {
 142   if (!VALUE_HISTOGRAMS (fun))
 143     return NULL;
 144   return htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
 145                               htab_hash_pointer (stmt));
 146 }
 147
 148 /* Add histogram for STMT.  */
 149
 150 void
 151 gimple_add_histogram_value (struct function *fun, tree stmt, histogram_value hist)
 152 {
 153   hist->hvalue.next = gimple_histogram_value (fun, stmt);
 154   set_histogram_value (fun, stmt, hist);
 155 }
 156
 157 /* Remove histogram HIST from STMT's histogram list.  */
 158
 159 void
 160 gimple_remove_histogram_value (struct function *fun, tree stmt, histogram_value hist)
 161 {
 162   histogram_value hist2 = gimple_histogram_value (fun, stmt);
 163   if (hist == hist2)
 164     {
 165       set_histogram_value (fun, stmt, hist->hvalue.next);
 166     }
 167   else
 168     {
 169       while (hist2->hvalue.next != hist)
 170         hist2 = hist2->hvalue.next;
 171       hist2->hvalue.next = hist->hvalue.next;
 172     }
 173   free (hist->hvalue.counters);
 174 #ifdef ENABLE_CHECKING
 175   memset (hist, 0xab, sizeof (*hist));
 176 #endif
 177   free (hist);
 178 }
 179
 180 /* Lookup histogram of type TYPE in the STMT.  */
 181
 182 histogram_value
 183 gimple_histogram_value_of_type (struct function *fun, tree stmt, enum hist_type type)
 184 {
 185   histogram_value hist;
 186   for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
 187     if (hist->type == type)
 188       return hist;
 189   return NULL;
 190 }
 191
 192 /* Dump information about HIST to DUMP_FILE.  */
 193
 194 static void
 195 dump_histogram_value (FILE *dump_file, histogram_value hist)
 196 {
 197   switch (hist->type)
 198     {
 199     case HIST_TYPE_INTERVAL:
 200       fprintf (dump_file, "Interval counter range %d -- %d",
 201                hist->hdata.intvl.int_start,
 202                (hist->hdata.intvl.int_start
 203                 + hist->hdata.intvl.steps - 1));
 204       if (hist->hvalue.counters)
 205         {
 206            unsigned int i;
 207            fprintf(dump_file, " [");
 208            for (i = 0; i < hist->hdata.intvl.steps; i++)
 209              fprintf (dump_file, " %d:"HOST_WIDEST_INT_PRINT_DEC,
 210                       hist->hdata.intvl.int_start + i,
 211                       (HOST_WIDEST_INT) hist->hvalue.counters[i]);
 212            fprintf (dump_file, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC,
 213                     (HOST_WIDEST_INT) hist->hvalue.counters[i]);
 214         }
 215       fprintf (dump_file, ".\n");
 216       break;
 217
 218     case HIST_TYPE_POW2:
 219       fprintf (dump_file, "Pow2 counter ");
 220       if (hist->hvalue.counters)
 221         {
 222            fprintf (dump_file, "pow2:"HOST_WIDEST_INT_PRINT_DEC
 223                     " nonpow2:"HOST_WIDEST_INT_PRINT_DEC,
 224                     (HOST_WIDEST_INT) hist->hvalue.counters[0],
 225                     (HOST_WIDEST_INT) hist->hvalue.counters[1]);
 226         }
 227       fprintf (dump_file, ".\n");
 228       break;
 229
 230     case HIST_TYPE_SINGLE_VALUE:
 231       fprintf (dump_file, "Single value ");
 232       if (hist->hvalue.counters)
 233         {
 234            fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
 235                     " match:"HOST_WIDEST_INT_PRINT_DEC
 236                     " wrong:"HOST_WIDEST_INT_PRINT_DEC,
 237                     (HOST_WIDEST_INT) hist->hvalue.counters[0],
 238                     (HOST_WIDEST_INT) hist->hvalue.counters[1],
 239                     (HOST_WIDEST_INT) hist->hvalue.counters[2]);
 240         }
 241       fprintf (dump_file, ".\n");
 242       break;
 243
 244     case HIST_TYPE_CONST_DELTA:
 245       fprintf (dump_file, "Constant delta ");
 246       if (hist->hvalue.counters)
 247         {
 248            fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
 249                     " match:"HOST_WIDEST_INT_PRINT_DEC
 250                     " wrong:"HOST_WIDEST_INT_PRINT_DEC,
 251                     (HOST_WIDEST_INT) hist->hvalue.counters[0],
 252                     (HOST_WIDEST_INT) hist->hvalue.counters[1],
 253                     (HOST_WIDEST_INT) hist->hvalue.counters[2]);
 254         }
 255       fprintf (dump_file, ".\n");
 256       break;
 257    }
 258 }
 259
 260 /* Dump all histograms attached to STMT to DUMP_FILE.  */
 261
 262 void
 263 dump_histograms_for_stmt (struct function *fun, FILE *dump_file, tree stmt)
 264 {
 265   histogram_value hist;
 266   for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
 267    dump_histogram_value (dump_file, hist);
 268 }
 269
 270 /* Remove all histograms associated with STMT.  */
 271
 272 void
 273 gimple_remove_stmt_histograms (struct function *fun, tree stmt)
 274 {
 275   histogram_value val;
 276   while ((val = gimple_histogram_value (fun, stmt)) != NULL)
 277     gimple_remove_histogram_value (fun, stmt, val);
 278 }
 279
 280 /* Duplicate all histograms associates with OSTMT to STMT.  */
 281
 282 void
 283 gimple_duplicate_stmt_histograms (struct function *fun, tree stmt,
 284                                   struct function *ofun, tree ostmt)
 285 {
 286   histogram_value val;
 287   for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
 288     {
 289       histogram_value new = gimple_alloc_histogram_value (fun, val->type, NULL, NULL);
 290       memcpy (new, val, sizeof (*val));
 291       new->hvalue.stmt = stmt;
 292       new->hvalue.counters = xmalloc (sizeof (*new->hvalue.counters) * new->n_counters);
 293       memcpy (new->hvalue.counters, val->hvalue.counters, sizeof (*new->hvalue.counters) * new->n_counters);
 294       gimple_add_histogram_value (fun, stmt, new);
 295     }
 296 }
 297
 298 static bool error_found = false;
 299
 300 /* Helper function for verify_histograms.  For each histogram reachable via htab
 301    walk verify that it was reached via statement walk.  */
 302
 303 static int
 304 visit_hist (void **slot, void *data)
 305 {
 306   struct pointer_set_t *visited = (struct pointer_set_t *) data;
 307   histogram_value hist = *(histogram_value *) slot;
 308   if (!pointer_set_contains (visited, hist))
 309     {
 310       error ("Dead histogram");
 311       dump_histogram_value (stderr, hist);
 312       debug_generic_stmt (hist->hvalue.stmt);
 313       error_found = true;
 314     }
 315   return 0;
 316 }
 317
 318 /* Verify sanity of the histograms.  */
 319
 320 void
 321 verify_histograms (void)
 322 {
 323   basic_block bb;
 324   block_stmt_iterator bsi;
 325   histogram_value hist;
 326   struct pointer_set_t *visited_hists;
 327
 328   error_found = false;
 329   visited_hists = pointer_set_create ();
 330   FOR_EACH_BB (bb)
 331     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 332       {
 333         tree stmt = bsi_stmt (bsi);
 334
 335         for (hist = gimple_histogram_value (cfun, stmt); hist; hist = hist->hvalue.next)
 336           {
 337             if (hist->hvalue.stmt != stmt)
 338               {
 339                 error ("Histogram value statement does not correspond to statement"
 340                        " it is associated with");
 341                 debug_generic_stmt (stmt);
 342                 dump_histogram_value (stderr, hist);
 343                 error_found = true;
 344               }
 345             pointer_set_insert (visited_hists, hist);
 346           }
 347       }
 348   if (VALUE_HISTOGRAMS (cfun))
 349     htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists);
 350   pointer_set_destroy (visited_hists);
 351   if (error_found)
 352     internal_error ("verify_histograms failed");
 353 }
 354
 355 /* Helper function for verify_histograms.  For each histogram reachable via htab
 356    walk verify that it was reached via statement walk.  */
 357
 358 static int
 359 free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
 360 {
 361   histogram_value hist = *(histogram_value *) slot;
 362   free (hist->hvalue.counters);
 363 #ifdef ENABLE_CHECKING
 364   memset (hist, 0xab, sizeof (*hist));
 365 #endif
 366   free (hist);
 367   return 0;
 368 }
 369
 370 void
 371 free_histograms (void)
 372 {
 373   if (VALUE_HISTOGRAMS (cfun))
 374     {
 375       htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL);
 376       htab_delete (VALUE_HISTOGRAMS (cfun));
 377       VALUE_HISTOGRAMS (cfun) = NULL;
 378     }
 379 }
 380
 381 /* The overall number of invocations of the counter should match execution count
 382    of basic block.  Report it as error rather than internal error as it might
 383    mean that user has misused the profile somehow.  */
 384 static bool
 385 check_counter (tree stmt, const char * name, gcov_type all, gcov_type bb_count)
 386 {
 387   if (all != bb_count)
 388     {
 389       location_t * locus;
 390       locus = (stmt != NULL && EXPR_HAS_LOCATION (stmt)
 391                ? EXPR_LOCUS (stmt)
 392                : &DECL_SOURCE_LOCATION (current_function_decl));
 393       error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)",
 394              locus, name, (int)all, (int)bb_count);
 395       return true;
 396     }
 397   return false;
 398 }
 399
 400 /* Tree based transformations. */
 401 static bool
 402 tree_value_profile_transformations (void)
 403 {
 404   basic_block bb;
 405   block_stmt_iterator bsi;
 406   bool changed = false;
 407
 408   FOR_EACH_BB (bb)
 409     {
 410       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 411         {
 412           tree stmt = bsi_stmt (bsi);
 413           histogram_value th = gimple_histogram_value (cfun, stmt);
 414           if (!th)
 415             continue;
 416
 417           if (dump_file)
 418             {
 419               fprintf (dump_file, "Trying transformations on stmt ");
 420               print_generic_stmt (dump_file, stmt, TDF_SLIM);
 421               dump_histograms_for_stmt (cfun, dump_file, stmt);
 422             }
 423
 424           /* Transformations:  */
 425           /* The order of things in this conditional controls which
 426              transformation is used when more than one is applicable.  */
 427           /* It is expected that any code added by the transformations
 428              will be added before the current statement, and that the
 429              current statement remain valid (although possibly
 430              modified) upon return.  */
 431           if (flag_value_profile_transformations
 432               && (tree_mod_subtract_transform (stmt)
 433                   || tree_divmod_fixed_value_transform (stmt)
 434                   || tree_mod_pow2_value_transform (stmt)
 435                   || tree_stringops_transform (&bsi)))
 436             {
 437               stmt = bsi_stmt (bsi);
 438               changed = true;
 439               /* Original statement may no longer be in the same block. */
 440               if (bb != bb_for_stmt (stmt))
 441                 {
 442                   bb = bb_for_stmt (stmt);
 443                   bsi = bsi_for_stmt (stmt);
 444                 }
 445             }
 446         }
 447     }
 448
 449   if (changed)
 450     {
 451       counts_to_freqs ();
 452     }
 453
 454   return changed;
 455 }
 456
 457 /* Generate code for transformation 1 (with OPERATION, operands OP1
 458    and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
 459    probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
 460    within roundoff error).  This generates the result into a temp and returns
 461    the temp; it does not replace or alter the original STMT.  */
 462 static tree
 463 tree_divmod_fixed_value (tree stmt, tree operation,
 464                          tree op1, tree op2, tree value, int prob, gcov_type count,
 465                          gcov_type all)
 466 {
 467   tree stmt1, stmt2, stmt3;
 468   tree tmp1, tmp2, tmpv;
 469   tree label_decl1 = create_artificial_label ();
 470   tree label_decl2 = create_artificial_label ();
 471   tree label1, label2;
 472   tree bb1end, bb2end, bb3end;
 473   basic_block bb, bb2, bb3, bb4;
 474   tree optype = TREE_TYPE (operation);
 475   edge e12, e13, e23, e24, e34;
 476   block_stmt_iterator bsi;
 477
 478   bb = bb_for_stmt (stmt);
 479   bsi = bsi_for_stmt (stmt);
 480
 481   tmpv = create_tmp_var (optype, "PROF");
 482   tmp1 = create_tmp_var (optype, "PROF");
 483   stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, tmpv,
 484                   fold_convert (optype, value));
 485   stmt2 = build2 (GIMPLE_MODIFY_STMT, optype, tmp1, op2);
 486   stmt3 = build3 (COND_EXPR, void_type_node,
 487             build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
 488             build1 (GOTO_EXPR, void_type_node, label_decl2),
 489             build1 (GOTO_EXPR, void_type_node, label_decl1));
 490   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 491   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 492   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 493   bb1end = stmt3;
 494
 495   tmp2 = create_tmp_var (optype, "PROF");
 496   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 497   stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, tmp2,
 498                   build2 (TREE_CODE (operation), optype, op1, tmpv));
 499   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 500   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 501   bb2end = stmt1;
 502
 503   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 504   stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, tmp2,
 505                   build2 (TREE_CODE (operation), optype, op1, op2));
 506   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 507   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 508   bb3end = stmt1;
 509
 510   /* Fix CFG. */
 511   /* Edge e23 connects bb2 to bb3, etc. */
 512   e12 = split_block (bb, bb1end);
 513   bb2 = e12->dest;
 514   bb2->count = count;
 515   e23 = split_block (bb2, bb2end);
 516   bb3 = e23->dest;
 517   bb3->count = all - count;
 518   e34 = split_block (bb3, bb3end);
 519   bb4 = e34->dest;
 520   bb4->count = all;
 521
 522   e12->flags &= ~EDGE_FALLTHRU;
 523   e12->flags |= EDGE_FALSE_VALUE;
 524   e12->probability = prob;
 525   e12->count = count;
 526
 527   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
 528   e13->probability = REG_BR_PROB_BASE - prob;
 529   e13->count = all - count;
 530
 531   remove_edge (e23);
 532
 533   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
 534   e24->probability = REG_BR_PROB_BASE;
 535   e24->count = count;
 536
 537   e34->probability = REG_BR_PROB_BASE;
 538   e34->count = all - count;
 539
 540   return tmp2;
 541 }
 542
 543 /* Do transform 1) on INSN if applicable.  */
 544 static bool
 545 tree_divmod_fixed_value_transform (tree stmt)
 546 {
 547   histogram_value histogram;
 548   enum tree_code code;
 549   gcov_type val, count, all;
 550   tree modify, op, op1, op2, result, value, tree_val;
 551   int prob;
 552
 553   modify = stmt;
 554   if (TREE_CODE (stmt) == RETURN_EXPR
 555       && TREE_OPERAND (stmt, 0)
 556       && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
 557     modify = TREE_OPERAND (stmt, 0);
 558   if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
 559     return false;
 560   op = GIMPLE_STMT_OPERAND (modify, 1);
 561   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 562     return false;
 563   code = TREE_CODE (op);
 564
 565   if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
 566     return false;
 567
 568   op1 = TREE_OPERAND (op, 0);
 569   op2 = TREE_OPERAND (op, 1);
 570
 571   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
 572   if (!histogram)
 573     return false;
 574
 575   value = histogram->hvalue.value;
 576   val = histogram->hvalue.counters[0];
 577   count = histogram->hvalue.counters[1];
 578   all = histogram->hvalue.counters[2];
 579   gimple_remove_histogram_value (cfun, stmt, histogram);
 580
 581   /* We require that count is at least half of all; this means
 582      that for the transformation to fire the value must be constant
 583      at least 50% of time (and 75% gives the guarantee of usage).  */
 584   if (simple_cst_equal (op2, value) != 1 || 2 * count < all
 585       || !maybe_hot_bb_p (bb_for_stmt (stmt)))
 586     return false;
 587
 588   if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
 589     return false;
 590
 591   /* Compute probability of taking the optimal path.  */
 592   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 593
 594   tree_val = build_int_cst_wide (get_gcov_type (),
 595                                  (unsigned HOST_WIDE_INT) val,
 596                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
 597   result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all);
 598
 599   if (dump_file)
 600     {
 601       fprintf (dump_file, "Div/mod by constant ");
 602       print_generic_expr (dump_file, value, TDF_SLIM);
 603       fprintf (dump_file, "=");
 604       print_generic_expr (dump_file, tree_val, TDF_SLIM);
 605       fprintf (dump_file, " transformation on insn ");
 606       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 607     }
 608
 609   GIMPLE_STMT_OPERAND (modify, 1) = result;
 610
 611   return true;
 612 }
 613
 614 /* Generate code for transformation 2 (with OPERATION, operands OP1
 615    and OP2, parent modify-expr STMT and probability of taking the optimal
 616    path PROB, which is equivalent to COUNT/ALL within roundoff error).
 617    This generates the result into a temp and returns
 618    the temp; it does not replace or alter the original STMT.  */
 619 static tree
 620 tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob,
 621                gcov_type count, gcov_type all)
 622 {
 623   tree stmt1, stmt2, stmt3, stmt4;
 624   tree tmp2, tmp3;
 625   tree label_decl1 = create_artificial_label ();
 626   tree label_decl2 = create_artificial_label ();
 627   tree label1, label2;
 628   tree bb1end, bb2end, bb3end;
 629   basic_block bb, bb2, bb3, bb4;
 630   tree optype = TREE_TYPE (operation);
 631   edge e12, e13, e23, e24, e34;
 632   block_stmt_iterator bsi;
 633   tree result = create_tmp_var (optype, "PROF");
 634
 635   bb = bb_for_stmt (stmt);
 636   bsi = bsi_for_stmt (stmt);
 637
 638   tmp2 = create_tmp_var (optype, "PROF");
 639   tmp3 = create_tmp_var (optype, "PROF");
 640   stmt2 = build2 (GIMPLE_MODIFY_STMT, optype, tmp2,
 641                   build2 (PLUS_EXPR, optype, op2, build_int_cst (optype, -1)));
 642   stmt3 = build2 (GIMPLE_MODIFY_STMT, optype, tmp3,
 643                   build2 (BIT_AND_EXPR, optype, tmp2, op2));
 644   stmt4 = build3 (COND_EXPR, void_type_node,
 645                   build2 (NE_EXPR, boolean_type_node,
 646                           tmp3, build_int_cst (optype, 0)),
 647                   build1 (GOTO_EXPR, void_type_node, label_decl2),
 648                   build1 (GOTO_EXPR, void_type_node, label_decl1));
 649   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 650   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 651   bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT);
 652   bb1end = stmt4;
 653
 654   /* tmp2 == op2-1 inherited from previous block */
 655   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 656   stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, result,
 657                   build2 (BIT_AND_EXPR, optype, op1, tmp2));
 658   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 659   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 660   bb2end = stmt1;
 661
 662   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 663   stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, result,
 664                   build2 (TREE_CODE (operation), optype, op1, op2));
 665   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 666   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 667   bb3end = stmt1;
 668
 669   /* Fix CFG. */
 670   /* Edge e23 connects bb2 to bb3, etc. */
 671   e12 = split_block (bb, bb1end);
 672   bb2 = e12->dest;
 673   bb2->count = count;
 674   e23 = split_block (bb2, bb2end);
 675   bb3 = e23->dest;
 676   bb3->count = all - count;
 677   e34 = split_block (bb3, bb3end);
 678   bb4 = e34->dest;
 679   bb4->count = all;
 680
 681   e12->flags &= ~EDGE_FALLTHRU;
 682   e12->flags |= EDGE_FALSE_VALUE;
 683   e12->probability = prob;
 684   e12->count = count;
 685
 686   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
 687   e13->probability = REG_BR_PROB_BASE - prob;
 688   e13->count = all - count;
 689
 690   remove_edge (e23);
 691
 692   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
 693   e24->probability = REG_BR_PROB_BASE;
 694   e24->count = count;
 695
 696   e34->probability = REG_BR_PROB_BASE;
 697   e34->count = all - count;
 698
 699   return result;
 700 }
 701
 702 /* Do transform 2) on INSN if applicable.  */
 703 static bool
 704 tree_mod_pow2_value_transform (tree stmt)
 705 {
 706   histogram_value histogram;
 707   enum tree_code code;
 708   gcov_type count, wrong_values, all;
 709   tree modify, op, op1, op2, result, value;
 710   int prob;
 711
 712   modify = stmt;
 713   if (TREE_CODE (stmt) == RETURN_EXPR
 714       && TREE_OPERAND (stmt, 0)
 715       && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
 716     modify = TREE_OPERAND (stmt, 0);
 717   if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
 718     return false;
 719   op = GIMPLE_STMT_OPERAND (modify, 1);
 720   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 721     return false;
 722   code = TREE_CODE (op);
 723
 724   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
 725     return false;
 726
 727   op1 = TREE_OPERAND (op, 0);
 728   op2 = TREE_OPERAND (op, 1);
 729
 730   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
 731   if (!histogram)
 732     return false;
 733
 734   value = histogram->hvalue.value;
 735   wrong_values = histogram->hvalue.counters[0];
 736   count = histogram->hvalue.counters[1];
 737
 738   gimple_remove_histogram_value (cfun, stmt, histogram);
 739
 740   /* We require that we hit a power of 2 at least half of all evaluations.  */
 741   if (simple_cst_equal (op2, value) != 1 || count < wrong_values
 742       || !maybe_hot_bb_p (bb_for_stmt (stmt)))
 743     return false;
 744
 745   if (dump_file)
 746     {
 747       fprintf (dump_file, "Mod power of 2 transformation on insn ");
 748       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 749     }
 750
 751   /* Compute probability of taking the optimal path.  */
 752   all = count + wrong_values;
 753
 754   if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
 755     return false;
 756
 757   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 758
 759   result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
 760
 761   GIMPLE_STMT_OPERAND (modify, 1) = result;
 762
 763   return true;
 764 }
 765
 766 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
 767    and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
 768    support.  Currently only NCOUNTS==0 or 1 is supported and this is
 769    built into this interface.  The probabilities of taking the optimal
 770    paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
 771    COUNT2/ALL respectively within roundoff error).  This generates the
 772    result into a temp and returns the temp; it does not replace or alter
 773    the original STMT.  */
 774 /* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
 775
 776 static tree
 777 tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2,
 778                     int prob1, int prob2, int ncounts,
 779                     gcov_type count1, gcov_type count2, gcov_type all)
 780 {
 781   tree stmt1, stmt2, stmt3;
 782   tree tmp1;
 783   tree label_decl1 = create_artificial_label ();
 784   tree label_decl2 = create_artificial_label ();
 785   tree label_decl3 = create_artificial_label ();
 786   tree label1, label2, label3;
 787   tree bb1end, bb2end = NULL_TREE, bb3end;
 788   basic_block bb, bb2, bb3, bb4;
 789   tree optype = TREE_TYPE (operation);
 790   edge e12, e23 = 0, e24, e34, e14;
 791   block_stmt_iterator bsi;
 792   tree result = create_tmp_var (optype, "PROF");
 793
 794   bb = bb_for_stmt (stmt);
 795   bsi = bsi_for_stmt (stmt);
 796
 797   tmp1 = create_tmp_var (optype, "PROF");
 798   stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, result, op1);
 799   stmt2 = build2 (GIMPLE_MODIFY_STMT, optype, tmp1, op2);
 800   stmt3 = build3 (COND_EXPR, void_type_node,
 801             build2 (LT_EXPR, boolean_type_node, result, tmp1),
 802             build1 (GOTO_EXPR, void_type_node, label_decl3),
 803             build1 (GOTO_EXPR, void_type_node,
 804                     ncounts ? label_decl1 : label_decl2));
 805   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 806   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 807   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 808   bb1end = stmt3;
 809
 810   if (ncounts)  /* Assumed to be 0 or 1 */
 811     {
 812       label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 813       stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, result,
 814                       build2 (MINUS_EXPR, optype, result, tmp1));
 815       stmt2 = build3 (COND_EXPR, void_type_node,
 816                 build2 (LT_EXPR, boolean_type_node, result, tmp1),
 817                 build1 (GOTO_EXPR, void_type_node, label_decl3),
 818                 build1 (GOTO_EXPR, void_type_node, label_decl2));
 819       bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 820       bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 821       bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 822       bb2end = stmt2;
 823     }
 824
 825   /* Fallback case. */
 826   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 827   stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, result,
 828                     build2 (TREE_CODE (operation), optype, result, tmp1));
 829   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 830   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 831   bb3end = stmt1;
 832
 833   label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
 834   bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
 835
 836   /* Fix CFG. */
 837   /* Edge e23 connects bb2 to bb3, etc. */
 838   /* However block 3 is optional; if it is not there, references
 839      to 3 really refer to block 2. */
 840   e12 = split_block (bb, bb1end);
 841   bb2 = e12->dest;
 842   bb2->count = all - count1;
 843
 844   if (ncounts)  /* Assumed to be 0 or 1.  */
 845     {
 846       e23 = split_block (bb2, bb2end);
 847       bb3 = e23->dest;
 848       bb3->count = all - count1 - count2;
 849     }
 850
 851   e34 = split_block (ncounts ? bb3 : bb2, bb3end);
 852   bb4 = e34->dest;
 853   bb4->count = all;
 854
 855   e12->flags &= ~EDGE_FALLTHRU;
 856   e12->flags |= EDGE_FALSE_VALUE;
 857   e12->probability = REG_BR_PROB_BASE - prob1;
 858   e12->count = all - count1;
 859
 860   e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
 861   e14->probability = prob1;
 862   e14->count = count1;
 863
 864   if (ncounts)  /* Assumed to be 0 or 1.  */
 865     {
 866       e23->flags &= ~EDGE_FALLTHRU;
 867       e23->flags |= EDGE_FALSE_VALUE;
 868       e23->count = all - count1 - count2;
 869       e23->probability = REG_BR_PROB_BASE - prob2;
 870
 871       e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
 872       e24->probability = prob2;
 873       e24->count = count2;
 874     }
 875
 876   e34->probability = REG_BR_PROB_BASE;
 877   e34->count = all - count1 - count2;
 878
 879   return result;
 880 }
 881
 882 /* Do transforms 3) and 4) on INSN if applicable.  */
 883 static bool
 884 tree_mod_subtract_transform (tree stmt)
 885 {
 886   histogram_value histogram;
 887   enum tree_code code;
 888   gcov_type count, wrong_values, all;
 889   tree modify, op, op1, op2, result, value;
 890   int prob1, prob2;
 891   unsigned int i, steps;
 892   gcov_type count1, count2;
 893
 894   modify = stmt;
 895   if (TREE_CODE (stmt) == RETURN_EXPR
 896       && TREE_OPERAND (stmt, 0)
 897       && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
 898     modify = TREE_OPERAND (stmt, 0);
 899   if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
 900     return false;
 901   op = GIMPLE_STMT_OPERAND (modify, 1);
 902   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 903     return false;
 904   code = TREE_CODE (op);
 905
 906   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
 907     return false;
 908
 909   op1 = TREE_OPERAND (op, 0);
 910   op2 = TREE_OPERAND (op, 1);
 911
 912   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
 913   if (!histogram)
 914     return false;
 915
 916   value = histogram->hvalue.value;
 917   all = 0;
 918   wrong_values = 0;
 919   for (i = 0; i < histogram->hdata.intvl.steps; i++)
 920     all += histogram->hvalue.counters[i];
 921
 922   wrong_values += histogram->hvalue.counters[i];
 923   wrong_values += histogram->hvalue.counters[i+1];
 924   steps = histogram->hdata.intvl.steps;
 925   all += wrong_values;
 926   count1 = histogram->hvalue.counters[0];
 927   count2 = histogram->hvalue.counters[1];
 928
 929   /* Compute probability of taking the optimal path.  */
 930   if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count))
 931     {
 932       gimple_remove_histogram_value (cfun, stmt, histogram);
 933       return false;
 934     }
 935
 936   /* We require that we use just subtractions in at least 50% of all
 937      evaluations.  */
 938   count = 0;
 939   for (i = 0; i < histogram->hdata.intvl.steps; i++)
 940     {
 941       count += histogram->hvalue.counters[i];
 942       if (count * 2 >= all)
 943         break;
 944     }
 945   if (i == steps
 946       || !maybe_hot_bb_p (bb_for_stmt (stmt)))
 947     return false;
 948
 949   gimple_remove_histogram_value (cfun, stmt, histogram);
 950   if (dump_file)
 951     {
 952       fprintf (dump_file, "Mod subtract transformation on insn ");
 953       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 954     }
 955
 956   /* Compute probability of taking the optimal path(s).  */
 957   prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all;
 958   prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all;
 959
 960   /* In practice, "steps" is always 2.  This interface reflects this,
 961      and will need to be changed if "steps" can change.  */
 962   result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i,
 963                               count1, count2, all);
 964
 965   GIMPLE_STMT_OPERAND (modify, 1) = result;
 966
 967   return true;
 968 }
 969
 970 /* Return true if the stringop FNDECL with ARGLIST shall be profiled.  */
 971 static bool
 972 interesting_stringop_to_profile_p (tree fndecl, tree arglist)
 973 {
 974   enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
 975
 976   if (fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_MEMCPY
 977       && fcode != BUILT_IN_BZERO)
 978     return false;
 979
 980   switch (fcode)
 981     {
 982      case BUILT_IN_MEMCPY:
 983      case BUILT_IN_MEMPCPY:
 984         return validate_arglist (arglist,
 985                                  POINTER_TYPE, POINTER_TYPE, INTEGER_TYPE,
 986                                  VOID_TYPE);
 987      case BUILT_IN_MEMSET:
 988         return validate_arglist (arglist,
 989                                  POINTER_TYPE, INTEGER_TYPE, INTEGER_TYPE,
 990                                  VOID_TYPE);
 991      case BUILT_IN_BZERO:
 992         return validate_arglist (arglist, POINTER_TYPE, INTEGER_TYPE,
 993                                  VOID_TYPE);
 994      default:
 995         gcc_unreachable ();
 996     }
 997 }
 998
 999 /* Convert   stringop (..., size)
1000    into
1001    if (size == VALUE)
1002      stringop (...., VALUE);
1003    else
1004      stringop (...., size);
1005    assuming constant propagation of VALUE will happen later.
1006 */
1007 static void
1008 tree_stringop_fixed_value (tree stmt, tree value, int prob, gcov_type count,
1009                            gcov_type all)
1010 {
1011   tree stmt1, stmt2, stmt3;
1012   tree tmp1, tmpv;
1013   tree label_decl1 = create_artificial_label ();
1014   tree label_decl2 = create_artificial_label ();
1015   tree label1, label2;
1016   tree bb1end, bb2end;
1017   basic_block bb, bb2, bb3, bb4;
1018   edge e12, e13, e23, e24, e34;
1019   block_stmt_iterator bsi;
1020   tree call = get_call_expr_in (stmt);
1021   tree arglist = TREE_OPERAND (call, 1);
1022   tree blck_size = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist)));
1023   tree optype = TREE_TYPE (blck_size);
1024   int region;
1025
1026   bb = bb_for_stmt (stmt);
1027   bsi = bsi_for_stmt (stmt);
1028
1029   if (bsi_end_p (bsi))
1030     {
1031       edge_iterator ei;
1032       for (ei = ei_start (bb->succs); (e34 = ei_safe_edge (ei)); )
1033         if (!e34->flags & EDGE_ABNORMAL)
1034           break;
1035     }
1036   else
1037     {
1038       e34 = split_block (bb, stmt);
1039       bsi = bsi_for_stmt (stmt);
1040     }
1041   bb4 = e34->dest;
1042
1043   tmpv = create_tmp_var (optype, "PROF");
1044   tmp1 = create_tmp_var (optype, "PROF");
1045   stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, tmpv,
1046                   fold_convert (optype, value));
1047   stmt2 = build2 (GIMPLE_MODIFY_STMT, optype, tmp1, blck_size);
1048   stmt3 = build3 (COND_EXPR, void_type_node,
1049             build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
1050             build1 (GOTO_EXPR, void_type_node, label_decl2),
1051             build1 (GOTO_EXPR, void_type_node, label_decl1));
1052   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1053   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
1054   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
1055   bb1end = stmt3;
1056
1057   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
1058   stmt1 = unshare_expr (stmt);
1059   call = get_call_expr_in (stmt1);
1060   arglist = TREE_OPERAND (call, 1);
1061   TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist))) = value;
1062   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
1063   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1064   region = lookup_stmt_eh_region (stmt);
1065   if (region >= 0)
1066     add_stmt_to_eh_region (stmt1, region);
1067   bb2end = stmt1;
1068   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
1069   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
1070
1071   /* Fix CFG. */
1072   /* Edge e23 connects bb2 to bb3, etc. */
1073   e12 = split_block (bb, bb1end);
1074   bb2 = e12->dest;
1075   bb2->count = count;
1076   e23 = split_block (bb2, bb2end);
1077   bb3 = e23->dest;
1078   bb3->count = all - count;
1079
1080   e12->flags &= ~EDGE_FALLTHRU;
1081   e12->flags |= EDGE_FALSE_VALUE;
1082   e12->probability = prob;
1083   e12->count = count;
1084
1085   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
1086   e13->probability = REG_BR_PROB_BASE - prob;
1087   e13->count = all - count;
1088
1089   remove_edge (e23);
1090
1091   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
1092   e24->probability = REG_BR_PROB_BASE;
1093   e24->count = count;
1094
1095   e34->probability = REG_BR_PROB_BASE;
1096   e34->count = all - count;
1097 }
1098
1099 /* Find values inside STMT for that we want to measure histograms for
1100    division/modulo optimization.  */
1101 static bool
1102 tree_stringops_transform (block_stmt_iterator *bsi)
1103 {
1104   tree stmt = bsi_stmt (*bsi);
1105   tree call = get_call_expr_in (stmt);
1106   tree fndecl;
1107   tree arglist;
1108   tree blck_size;
1109   enum built_in_function fcode;
1110   histogram_value histogram;
1111   gcov_type count, all, val;
1112   tree value;
1113   tree dest, src;
1114   unsigned int dest_align, src_align;
1115   int prob;
1116   tree tree_val;
1117
1118   if (!call)
1119     return false;
1120   fndecl = get_callee_fndecl (call);
1121   if (!fndecl)
1122     return false;
1123   fcode = DECL_FUNCTION_CODE (fndecl);
1124   arglist = TREE_OPERAND (call, 1);
1125   if (!interesting_stringop_to_profile_p (fndecl, arglist))
1126     return false;
1127
1128   if (fcode == BUILT_IN_BZERO)
1129     blck_size = TREE_VALUE (TREE_CHAIN (arglist));
1130   else
1131     blck_size = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist)));
1132   if (TREE_CODE (blck_size) == INTEGER_CST)
1133     return false;
1134
1135   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1136   if (!histogram)
1137     return false;
1138   value = histogram->hvalue.value;
1139   val = histogram->hvalue.counters[0];
1140   count = histogram->hvalue.counters[1];
1141   all = histogram->hvalue.counters[2];
1142   gimple_remove_histogram_value (cfun, stmt, histogram);
1143   /* We require that count is at least half of all; this means
1144      that for the transformation to fire the value must be constant
1145      at least 80% of time.  */
1146   if ((6 * count / 5) < all || !maybe_hot_bb_p (bb_for_stmt (stmt)))
1147     return false;
1148   if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
1149     return false;
1150   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1151   dest = TREE_VALUE (arglist);
1152   dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1153   switch (fcode)
1154     {
1155     case BUILT_IN_MEMCPY:
1156     case BUILT_IN_MEMPCPY:
1157       src = TREE_VALUE (TREE_CHAIN (arglist));
1158       src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1159       if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1160         return false;
1161       break;
1162     case BUILT_IN_MEMSET:
1163       if (!can_store_by_pieces (val, builtin_memset_read_str,
1164                                 TREE_VALUE (TREE_CHAIN (arglist)),
1165                                 dest_align))
1166         return false;
1167       break;
1168     case BUILT_IN_BZERO:
1169       if (!can_store_by_pieces (val, builtin_memset_read_str,
1170                                 integer_zero_node,
1171                                 dest_align))
1172         return false;
1173       break;
1174     default:
1175       gcc_unreachable ();
1176     }
1177   tree_val = build_int_cst_wide (get_gcov_type (),
1178                                  (unsigned HOST_WIDE_INT) val,
1179                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1180   if (dump_file)
1181     {
1182       fprintf (dump_file, "Single value %i stringop transformation on ",
1183                (int)val);
1184       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1185     }
1186   tree_stringop_fixed_value (stmt, tree_val, prob, count, all);
1187
1188   return true;
1189 }
1190
1191 struct value_prof_hooks {
1192   /* Find list of values for which we want to measure histograms.  */
1193   void (*find_values_to_profile) (histogram_values *);
1194
1195   /* Identify and exploit properties of values that are hard to analyze
1196      statically.  See value-prof.c for more detail.  */
1197   bool (*value_profile_transformations) (void);
1198 };
1199 \f
1200 /* Find values inside STMT for that we want to measure histograms for
1201    division/modulo optimization.  */
1202 static void
1203 tree_divmod_values_to_profile (tree stmt, histogram_values *values)
1204 {
1205   tree assign, lhs, rhs, divisor, op0, type;
1206   histogram_value hist;
1207
1208   if (TREE_CODE (stmt) == RETURN_EXPR)
1209     assign = TREE_OPERAND (stmt, 0);
1210   else
1211     assign = stmt;
1212
1213   if (!assign
1214       || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
1215     return;
1216   lhs = GIMPLE_STMT_OPERAND (assign, 0);
1217   type = TREE_TYPE (lhs);
1218   if (!INTEGRAL_TYPE_P (type))
1219     return;
1220
1221   rhs = GIMPLE_STMT_OPERAND (assign, 1);
1222   switch (TREE_CODE (rhs))
1223     {
1224     case TRUNC_DIV_EXPR:
1225     case TRUNC_MOD_EXPR:
1226       divisor = TREE_OPERAND (rhs, 1);
1227       op0 = TREE_OPERAND (rhs, 0);
1228
1229       VEC_reserve (histogram_value, heap, *values, 3);
1230
1231       if (is_gimple_reg (divisor))
1232         /* Check for the case where the divisor is the same value most
1233            of the time.  */
1234         VEC_quick_push (histogram_value, *values,
1235                         gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1236                                                       stmt, divisor));
1237
1238       /* For mod, check whether it is not often a noop (or replaceable by
1239          a few subtractions).  */
1240       if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
1241           && TYPE_UNSIGNED (type))
1242         {
1243           tree val;
1244           /* Check for a special case where the divisor is power of 2.  */
1245           VEC_quick_push (histogram_value, *values,
1246                           gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1247                                                         stmt, divisor));
1248
1249           val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1250           hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1251                                                stmt, val);
1252           hist->hdata.intvl.int_start = 0;
1253           hist->hdata.intvl.steps = 2;
1254           VEC_quick_push (histogram_value, *values, hist);
1255         }
1256       return;
1257
1258     default:
1259       return;
1260     }
1261 }
1262
1263 /* Find values inside STMT for that we want to measure histograms for
1264    string operations.  */
1265 static void
1266 tree_stringops_values_to_profile (tree stmt, histogram_values *values)
1267 {
1268   tree call = get_call_expr_in (stmt);
1269   tree fndecl;
1270   tree arglist;
1271   tree blck_size;
1272   enum built_in_function fcode;
1273
1274   if (!call)
1275     return;
1276   fndecl = get_callee_fndecl (call);
1277   if (!fndecl)
1278     return;
1279   fcode = DECL_FUNCTION_CODE (fndecl);
1280   arglist = TREE_OPERAND (call, 1);
1281
1282   if (!interesting_stringop_to_profile_p (fndecl, arglist))
1283     return;
1284
1285   if (fcode == BUILT_IN_BZERO)
1286     blck_size = TREE_VALUE (TREE_CHAIN (arglist));
1287   else
1288     blck_size = TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist)));
1289
1290   if (TREE_CODE (blck_size) != INTEGER_CST)
1291     VEC_safe_push (histogram_value, heap, *values,
1292                    gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1293                                                  stmt, blck_size));
1294 }
1295
1296 /* Find values inside STMT for that we want to measure histograms and adds
1297    them to list VALUES.  */
1298
1299 static void
1300 tree_values_to_profile (tree stmt, histogram_values *values)
1301 {
1302   if (flag_value_profile_transformations)
1303     {
1304       tree_divmod_values_to_profile (stmt, values);
1305       tree_stringops_values_to_profile (stmt, values);
1306     }
1307 }
1308
1309 static void
1310 tree_find_values_to_profile (histogram_values *values)
1311 {
1312   basic_block bb;
1313   block_stmt_iterator bsi;
1314   unsigned i;
1315   histogram_value hist = NULL;
1316
1317   *values = NULL;
1318   FOR_EACH_BB (bb)
1319     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1320       tree_values_to_profile (bsi_stmt (bsi), values);
1321
1322   for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
1323     {
1324       switch (hist->type)
1325         {
1326         case HIST_TYPE_INTERVAL:
1327           hist->n_counters = hist->hdata.intvl.steps + 2;
1328           break;
1329
1330         case HIST_TYPE_POW2:
1331           hist->n_counters = 2;
1332           break;
1333
1334         case HIST_TYPE_SINGLE_VALUE:
1335           hist->n_counters = 3;
1336           break;
1337
1338         case HIST_TYPE_CONST_DELTA:
1339           hist->n_counters = 4;
1340           break;
1341
1342         default:
1343           gcc_unreachable ();
1344         }
1345       if (dump_file)
1346         {
1347           fprintf (dump_file, "Stmt ");
1348           print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
1349           dump_histogram_value (dump_file, hist);
1350         }
1351     }
1352 }
1353
1354 static struct value_prof_hooks tree_value_prof_hooks = {
1355   tree_find_values_to_profile,
1356   tree_value_profile_transformations
1357 };
1358
1359 void
1360 tree_register_value_prof_hooks (void)
1361 {
1362   gcc_assert (current_ir_type () == IR_GIMPLE);
1363   value_prof_hooks = &tree_value_prof_hooks;
1364 }
1365 \f
1366 /* IR-independent entry points.  */
1367 void
1368 find_values_to_profile (histogram_values *values)
1369 {
1370   (value_prof_hooks->find_values_to_profile) (values);
1371 }
1372
1373 bool
1374 value_profile_transformations (void)
1375 {
1376   return (value_prof_hooks->value_profile_transformations) ();
1377 }
1378 \f
1379