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