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