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     }
1202
1203   return true;
1204 }
1205
1206 /* Return true if the stringop CALL with FNDECL shall be profiled.  */
1207 static bool
1208 interesting_stringop_to_profile_p (tree fndecl, tree call)
1209 {
1210   enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
1211
1212   if (fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_MEMCPY
1213       && fcode != BUILT_IN_BZERO)
1214     return false;
1215
1216   switch (fcode)
1217     {
1218      case BUILT_IN_MEMCPY:
1219      case BUILT_IN_MEMPCPY:
1220        return validate_arglist (call,
1221                                 POINTER_TYPE, POINTER_TYPE, INTEGER_TYPE,
1222                                 VOID_TYPE);
1223      case BUILT_IN_MEMSET:
1224        return validate_arglist (call,
1225                                 POINTER_TYPE, INTEGER_TYPE, INTEGER_TYPE,
1226                                 VOID_TYPE);
1227      case BUILT_IN_BZERO:
1228        return validate_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1229                                 VOID_TYPE);
1230      default:
1231        gcc_unreachable ();
1232     }
1233 }
1234
1235 /* Convert   stringop (..., size)
1236    into
1237    if (size == VALUE)
1238      stringop (...., VALUE);
1239    else
1240      stringop (...., size);
1241    assuming constant propagation of VALUE will happen later.
1242 */
1243 static void
1244 tree_stringop_fixed_value (tree stmt, tree value, int prob, gcov_type count,
1245                            gcov_type all)
1246 {
1247   tree stmt1, stmt2, stmt3;
1248   tree tmp1, tmpv;
1249   tree label_decl1 = create_artificial_label ();
1250   tree label_decl2 = create_artificial_label ();
1251   tree label1, label2;
1252   tree bb1end, bb2end;
1253   basic_block bb, bb2, bb3, bb4;
1254   edge e12, e13, e23, e24, e34;
1255   block_stmt_iterator bsi;
1256   tree call = get_call_expr_in (stmt);
1257   tree blck_size = CALL_EXPR_ARG (call, 2);
1258   tree optype = TREE_TYPE (blck_size);
1259   int region;
1260
1261   bb = bb_for_stmt (stmt);
1262   bsi = bsi_for_stmt (stmt);
1263
1264   if (bsi_end_p (bsi))
1265     {
1266       edge_iterator ei;
1267       for (ei = ei_start (bb->succs); (e34 = ei_safe_edge (ei)); )
1268         if (!e34->flags & EDGE_ABNORMAL)
1269           break;
1270     }
1271   else
1272     {
1273       e34 = split_block (bb, stmt);
1274       bsi = bsi_for_stmt (stmt);
1275     }
1276   bb4 = e34->dest;
1277
1278   tmpv = create_tmp_var (optype, "PROF");
1279   tmp1 = create_tmp_var (optype, "PROF");
1280   stmt1 = build_gimple_modify_stmt (tmpv, fold_convert (optype, value));
1281   stmt2 = build_gimple_modify_stmt (tmp1, blck_size);
1282   stmt3 = build3 (COND_EXPR, void_type_node,
1283             build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
1284             NULL_TREE, NULL_TREE);
1285   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1286   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
1287   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
1288   bb1end = stmt3;
1289
1290   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
1291   stmt1 = unshare_expr (stmt);
1292   call = get_call_expr_in (stmt1);
1293   CALL_EXPR_ARG (call, 2) = value;
1294   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
1295   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1296   region = lookup_stmt_eh_region (stmt);
1297   if (region >= 0)
1298     add_stmt_to_eh_region (stmt1, region);
1299   bb2end = stmt1;
1300   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
1301   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
1302
1303   /* Fix CFG. */
1304   /* Edge e23 connects bb2 to bb3, etc. */
1305   e12 = split_block (bb, bb1end);
1306   bb2 = e12->dest;
1307   bb2->count = count;
1308   e23 = split_block (bb2, bb2end);
1309   bb3 = e23->dest;
1310   bb3->count = all - count;
1311
1312   e12->flags &= ~EDGE_FALLTHRU;
1313   e12->flags |= EDGE_FALSE_VALUE;
1314   e12->probability = prob;
1315   e12->count = count;
1316
1317   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
1318   e13->probability = REG_BR_PROB_BASE - prob;
1319   e13->count = all - count;
1320
1321   remove_edge (e23);
1322
1323   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
1324   e24->probability = REG_BR_PROB_BASE;
1325   e24->count = count;
1326
1327   e34->probability = REG_BR_PROB_BASE;
1328   e34->count = all - count;
1329 }
1330
1331 /* Find values inside STMT for that we want to measure histograms for
1332    division/modulo optimization.  */
1333 static bool
1334 tree_stringops_transform (block_stmt_iterator *bsi)
1335 {
1336   tree stmt = bsi_stmt (*bsi);
1337   tree call = get_call_expr_in (stmt);
1338   tree fndecl;
1339   tree blck_size;
1340   enum built_in_function fcode;
1341   histogram_value histogram;
1342   gcov_type count, all, val;
1343   tree value;
1344   tree dest, src;
1345   unsigned int dest_align, src_align;
1346   int prob;
1347   tree tree_val;
1348
1349   if (!call)
1350     return false;
1351   fndecl = get_callee_fndecl (call);
1352   if (!fndecl)
1353     return false;
1354   fcode = DECL_FUNCTION_CODE (fndecl);
1355   if (!interesting_stringop_to_profile_p (fndecl, call))
1356     return false;
1357
1358   if (fcode == BUILT_IN_BZERO)
1359     blck_size = CALL_EXPR_ARG (call, 1);
1360   else
1361     blck_size = CALL_EXPR_ARG (call, 2);
1362   if (TREE_CODE (blck_size) == INTEGER_CST)
1363     return false;
1364
1365   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1366   if (!histogram)
1367     return false;
1368   value = histogram->hvalue.value;
1369   val = histogram->hvalue.counters[0];
1370   count = histogram->hvalue.counters[1];
1371   all = histogram->hvalue.counters[2];
1372   gimple_remove_histogram_value (cfun, stmt, histogram);
1373   /* We require that count is at least half of all; this means
1374      that for the transformation to fire the value must be constant
1375      at least 80% of time.  */
1376   if ((6 * count / 5) < all || !maybe_hot_bb_p (bb_for_stmt (stmt)))
1377     return false;
1378   if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
1379     return false;
1380   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1381   dest = CALL_EXPR_ARG (call, 0);
1382   dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1383   switch (fcode)
1384     {
1385     case BUILT_IN_MEMCPY:
1386     case BUILT_IN_MEMPCPY:
1387       src = CALL_EXPR_ARG (call, 1);
1388       src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1389       if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1390         return false;
1391       break;
1392     case BUILT_IN_MEMSET:
1393       if (!can_store_by_pieces (val, builtin_memset_read_str,
1394                                 CALL_EXPR_ARG (call, 1),
1395                                 dest_align, true))
1396         return false;
1397       break;
1398     case BUILT_IN_BZERO:
1399       if (!can_store_by_pieces (val, builtin_memset_read_str,
1400                                 integer_zero_node,
1401                                 dest_align, true))
1402         return false;
1403       break;
1404     default:
1405       gcc_unreachable ();
1406     }
1407   tree_val = build_int_cst_wide (get_gcov_type (),
1408                                  (unsigned HOST_WIDE_INT) val,
1409                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1410   if (dump_file)
1411     {
1412       fprintf (dump_file, "Single value %i stringop transformation on ",
1413                (int)val);
1414       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1415     }
1416   tree_stringop_fixed_value (stmt, tree_val, prob, count, all);
1417
1418   return true;
1419 }
1420
1421 void
1422 stringop_block_profile (tree stmt, unsigned int *expected_align,
1423                         HOST_WIDE_INT *expected_size)
1424 {
1425   histogram_value histogram;
1426   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1427   if (!histogram)
1428     *expected_size = -1;
1429   else if (!histogram->hvalue.counters[1])
1430     {
1431       *expected_size = -1;
1432       gimple_remove_histogram_value (cfun, stmt, histogram);
1433     }
1434   else
1435     {
1436       gcov_type size;
1437       size = ((histogram->hvalue.counters[0]
1438               + histogram->hvalue.counters[1] / 2)
1439                / histogram->hvalue.counters[1]);
1440       /* Even if we can hold bigger value in SIZE, INT_MAX
1441          is safe "infinity" for code generation strategies.  */
1442       if (size > INT_MAX)
1443         size = INT_MAX;
1444       *expected_size = size;
1445       gimple_remove_histogram_value (cfun, stmt, histogram);
1446     }
1447   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1448   if (!histogram)
1449     *expected_align = 0;
1450   else if (!histogram->hvalue.counters[0])
1451     {
1452       gimple_remove_histogram_value (cfun, stmt, histogram);
1453       *expected_align = 0;
1454     }
1455   else
1456     {
1457       gcov_type count;
1458       int alignment;
1459
1460       count = histogram->hvalue.counters[0];
1461       alignment = 1;
1462       while (!(count & alignment)
1463              && (alignment * 2 * BITS_PER_UNIT))
1464         alignment <<= 1;
1465       *expected_align = alignment * BITS_PER_UNIT;
1466       gimple_remove_histogram_value (cfun, stmt, histogram);
1467     }
1468 }
1469
1470 struct value_prof_hooks {
1471   /* Find list of values for which we want to measure histograms.  */
1472   void (*find_values_to_profile) (histogram_values *);
1473
1474   /* Identify and exploit properties of values that are hard to analyze
1475      statically.  See value-prof.c for more detail.  */
1476   bool (*value_profile_transformations) (void);
1477 };
1478 \f
1479 /* Find values inside STMT for that we want to measure histograms for
1480    division/modulo optimization.  */
1481 static void
1482 tree_divmod_values_to_profile (tree stmt, histogram_values *values)
1483 {
1484   tree assign, lhs, rhs, divisor, op0, type;
1485   histogram_value hist;
1486
1487   if (TREE_CODE (stmt) == RETURN_EXPR)
1488     assign = TREE_OPERAND (stmt, 0);
1489   else
1490     assign = stmt;
1491
1492   if (!assign
1493       || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
1494     return;
1495   lhs = GIMPLE_STMT_OPERAND (assign, 0);
1496   type = TREE_TYPE (lhs);
1497   if (!INTEGRAL_TYPE_P (type))
1498     return;
1499
1500   rhs = GIMPLE_STMT_OPERAND (assign, 1);
1501   switch (TREE_CODE (rhs))
1502     {
1503     case TRUNC_DIV_EXPR:
1504     case TRUNC_MOD_EXPR:
1505       divisor = TREE_OPERAND (rhs, 1);
1506       op0 = TREE_OPERAND (rhs, 0);
1507
1508       VEC_reserve (histogram_value, heap, *values, 3);
1509
1510       if (is_gimple_reg (divisor))
1511         /* Check for the case where the divisor is the same value most
1512            of the time.  */
1513         VEC_quick_push (histogram_value, *values,
1514                         gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1515                                                       stmt, divisor));
1516
1517       /* For mod, check whether it is not often a noop (or replaceable by
1518          a few subtractions).  */
1519       if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
1520           && TYPE_UNSIGNED (type))
1521         {
1522           tree val;
1523           /* Check for a special case where the divisor is power of 2.  */
1524           VEC_quick_push (histogram_value, *values,
1525                           gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1526                                                         stmt, divisor));
1527
1528           val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1529           hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1530                                                stmt, val);
1531           hist->hdata.intvl.int_start = 0;
1532           hist->hdata.intvl.steps = 2;
1533           VEC_quick_push (histogram_value, *values, hist);
1534         }
1535       return;
1536
1537     default:
1538       return;
1539     }
1540 }
1541
1542 /* Find calls inside STMT for that we want to measure histograms for
1543    indirect/virtual call optimization. */
1544
1545 static void
1546 tree_indirect_call_to_profile (tree stmt, histogram_values *values)
1547 {
1548   tree                  call;
1549   tree                  callee;
1550
1551   call = get_call_expr_in (stmt);
1552
1553   if (!call || TREE_CODE (call) != CALL_EXPR)
1554     return;
1555
1556   callee = CALL_EXPR_FN (call);
1557
1558   if (TREE_CODE (callee) == ADDR_EXPR)
1559     return;
1560
1561   VEC_reserve (histogram_value, heap, *values, 3);
1562
1563   VEC_quick_push (histogram_value, *values,
1564                   gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1565                                                 stmt, callee));
1566
1567   return;
1568 }
1569
1570 /* Find values inside STMT for that we want to measure histograms for
1571    string operations.  */
1572 static void
1573 tree_stringops_values_to_profile (tree stmt, histogram_values *values)
1574 {
1575   tree call = get_call_expr_in (stmt);
1576   tree fndecl;
1577   tree blck_size;
1578   tree dest;
1579   enum built_in_function fcode;
1580
1581   if (!call)
1582     return;
1583   fndecl = get_callee_fndecl (call);
1584   if (!fndecl)
1585     return;
1586   fcode = DECL_FUNCTION_CODE (fndecl);
1587
1588   if (!interesting_stringop_to_profile_p (fndecl, call))
1589     return;
1590
1591   dest = CALL_EXPR_ARG (call, 0);
1592   if (fcode == BUILT_IN_BZERO)
1593     blck_size = CALL_EXPR_ARG (call, 1);
1594   else
1595     blck_size = CALL_EXPR_ARG (call, 2);
1596
1597   if (TREE_CODE (blck_size) != INTEGER_CST)
1598     {
1599       VEC_safe_push (histogram_value, heap, *values,
1600                      gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1601                                                    stmt, blck_size));
1602       VEC_safe_push (histogram_value, heap, *values,
1603                      gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1604                                                    stmt, blck_size));
1605     }
1606   if (TREE_CODE (blck_size) != INTEGER_CST)
1607     VEC_safe_push (histogram_value, heap, *values,
1608                    gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1609                                                  stmt, dest));
1610 }
1611
1612 /* Find values inside STMT for that we want to measure histograms and adds
1613    them to list VALUES.  */
1614
1615 static void
1616 tree_values_to_profile (tree stmt, histogram_values *values)
1617 {
1618   if (flag_value_profile_transformations)
1619     {
1620       tree_divmod_values_to_profile (stmt, values);
1621       tree_stringops_values_to_profile (stmt, values);
1622       tree_indirect_call_to_profile (stmt, values);
1623     }
1624 }
1625
1626 static void
1627 tree_find_values_to_profile (histogram_values *values)
1628 {
1629   basic_block bb;
1630   block_stmt_iterator bsi;
1631   unsigned i;
1632   histogram_value hist = NULL;
1633
1634   *values = NULL;
1635   FOR_EACH_BB (bb)
1636     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1637       tree_values_to_profile (bsi_stmt (bsi), values);
1638
1639   for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
1640     {
1641       switch (hist->type)
1642         {
1643         case HIST_TYPE_INTERVAL:
1644           hist->n_counters = hist->hdata.intvl.steps + 2;
1645           break;
1646
1647         case HIST_TYPE_POW2:
1648           hist->n_counters = 2;
1649           break;
1650
1651         case HIST_TYPE_SINGLE_VALUE:
1652           hist->n_counters = 3;
1653           break;
1654
1655         case HIST_TYPE_CONST_DELTA:
1656           hist->n_counters = 4;
1657           break;
1658
1659         case HIST_TYPE_INDIR_CALL:
1660           hist->n_counters = 3;
1661           break;
1662
1663         case HIST_TYPE_AVERAGE:
1664           hist->n_counters = 2;
1665           break;
1666
1667         case HIST_TYPE_IOR:
1668           hist->n_counters = 1;
1669           break;
1670
1671         default:
1672           gcc_unreachable ();
1673         }
1674       if (dump_file)
1675         {
1676           fprintf (dump_file, "Stmt ");
1677           print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
1678           dump_histogram_value (dump_file, hist);
1679         }
1680     }
1681 }
1682
1683 static struct value_prof_hooks tree_value_prof_hooks = {
1684   tree_find_values_to_profile,
1685   tree_value_profile_transformations
1686 };
1687
1688 void
1689 tree_register_value_prof_hooks (void)
1690 {
1691   gcc_assert (current_ir_type () == IR_GIMPLE);
1692   value_prof_hooks = &tree_value_prof_hooks;
1693 }
1694 \f
1695 /* IR-independent entry points.  */
1696 void
1697 find_values_to_profile (histogram_values *values)
1698 {
1699   (value_prof_hooks->find_values_to_profile) (values);
1700 }
1701
1702 bool
1703 value_profile_transformations (void)
1704 {
1705   return (value_prof_hooks->value_profile_transformations) ();
1706 }
1707 \f
1708