gcc/value-prof.c

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