gcc/value-prof.c

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