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 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 = xmalloc (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   int 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   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 655
 656   tree_val = build_int_cst_wide (get_gcov_type (),
 657                                  (unsigned HOST_WIDE_INT) val,
 658                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
 659   result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all);
 660
 661   if (dump_file)
 662     {
 663       fprintf (dump_file, "Div/mod by constant ");
 664       print_generic_expr (dump_file, value, TDF_SLIM);
 665       fprintf (dump_file, "=");
 666       print_generic_expr (dump_file, tree_val, TDF_SLIM);
 667       fprintf (dump_file, " transformation on insn ");
 668       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 669     }
 670
 671   GIMPLE_STMT_OPERAND (modify, 1) = result;
 672
 673   return true;
 674 }
 675
 676 /* Generate code for transformation 2 (with OPERATION, operands OP1
 677    and OP2, parent modify-expr STMT and probability of taking the optimal
 678    path PROB, which is equivalent to COUNT/ALL within roundoff error).
 679    This generates the result into a temp and returns
 680    the temp; it does not replace or alter the original STMT.  */
 681 static tree
 682 tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob,
 683                gcov_type count, gcov_type all)
 684 {
 685   tree stmt1, stmt2, stmt3, stmt4;
 686   tree tmp2, tmp3;
 687   tree label_decl1 = create_artificial_label ();
 688   tree label_decl2 = create_artificial_label ();
 689   tree label1, label2;
 690   tree bb1end, bb2end, bb3end;
 691   basic_block bb, bb2, bb3, bb4;
 692   tree optype = TREE_TYPE (operation);
 693   edge e12, e13, e23, e24, e34;
 694   block_stmt_iterator bsi;
 695   tree result = create_tmp_var (optype, "PROF");
 696
 697   bb = bb_for_stmt (stmt);
 698   bsi = bsi_for_stmt (stmt);
 699
 700   tmp2 = create_tmp_var (optype, "PROF");
 701   tmp3 = create_tmp_var (optype, "PROF");
 702   stmt2 = build_gimple_modify_stmt (tmp2,
 703                                     build2 (PLUS_EXPR, optype, op2,
 704                                             build_int_cst (optype, -1)));
 705   stmt3 = build_gimple_modify_stmt (tmp3,
 706                                     build2 (BIT_AND_EXPR, optype, tmp2, op2));
 707   stmt4 = build3 (COND_EXPR, void_type_node,
 708                   build2 (NE_EXPR, boolean_type_node,
 709                           tmp3, build_int_cst (optype, 0)),
 710                   NULL_TREE, NULL_TREE);
 711   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 712   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 713   bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT);
 714   bb1end = stmt4;
 715
 716   /* tmp2 == op2-1 inherited from previous block */
 717   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 718   stmt1 = build_gimple_modify_stmt (result,
 719                                     build2 (BIT_AND_EXPR, optype, op1, tmp2));
 720   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 721   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 722   bb2end = stmt1;
 723
 724   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 725   stmt1 = build_gimple_modify_stmt (result,
 726                                     build2 (TREE_CODE (operation), optype,
 727                                             op1, op2));
 728   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 729   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 730   bb3end = stmt1;
 731
 732   /* Fix CFG. */
 733   /* Edge e23 connects bb2 to bb3, etc. */
 734   e12 = split_block (bb, bb1end);
 735   bb2 = e12->dest;
 736   bb2->count = count;
 737   e23 = split_block (bb2, bb2end);
 738   bb3 = e23->dest;
 739   bb3->count = all - count;
 740   e34 = split_block (bb3, bb3end);
 741   bb4 = e34->dest;
 742   bb4->count = all;
 743
 744   e12->flags &= ~EDGE_FALLTHRU;
 745   e12->flags |= EDGE_FALSE_VALUE;
 746   e12->probability = prob;
 747   e12->count = count;
 748
 749   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
 750   e13->probability = REG_BR_PROB_BASE - prob;
 751   e13->count = all - count;
 752
 753   remove_edge (e23);
 754
 755   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
 756   e24->probability = REG_BR_PROB_BASE;
 757   e24->count = count;
 758
 759   e34->probability = REG_BR_PROB_BASE;
 760   e34->count = all - count;
 761
 762   return result;
 763 }
 764
 765 /* Do transform 2) on INSN if applicable.  */
 766 static bool
 767 tree_mod_pow2_value_transform (tree stmt)
 768 {
 769   histogram_value histogram;
 770   enum tree_code code;
 771   gcov_type count, wrong_values, all;
 772   tree modify, op, op1, op2, result, value;
 773   int prob;
 774
 775   modify = stmt;
 776   if (TREE_CODE (stmt) == RETURN_EXPR
 777       && TREE_OPERAND (stmt, 0)
 778       && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
 779     modify = TREE_OPERAND (stmt, 0);
 780   if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
 781     return false;
 782   op = GIMPLE_STMT_OPERAND (modify, 1);
 783   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 784     return false;
 785   code = TREE_CODE (op);
 786
 787   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
 788     return false;
 789
 790   op1 = TREE_OPERAND (op, 0);
 791   op2 = TREE_OPERAND (op, 1);
 792
 793   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
 794   if (!histogram)
 795     return false;
 796
 797   value = histogram->hvalue.value;
 798   wrong_values = histogram->hvalue.counters[0];
 799   count = histogram->hvalue.counters[1];
 800
 801   gimple_remove_histogram_value (cfun, stmt, histogram);
 802
 803   /* We require that we hit a power of 2 at least half of all evaluations.  */
 804   if (simple_cst_equal (op2, value) != 1 || count < wrong_values
 805       || !maybe_hot_bb_p (bb_for_stmt (stmt)))
 806     return false;
 807
 808   if (dump_file)
 809     {
 810       fprintf (dump_file, "Mod power of 2 transformation on insn ");
 811       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 812     }
 813
 814   /* Compute probability of taking the optimal path.  */
 815   all = count + wrong_values;
 816
 817   if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
 818     return false;
 819
 820   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 821
 822   result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
 823
 824   GIMPLE_STMT_OPERAND (modify, 1) = result;
 825
 826   return true;
 827 }
 828
 829 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
 830    and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
 831    support.  Currently only NCOUNTS==0 or 1 is supported and this is
 832    built into this interface.  The probabilities of taking the optimal
 833    paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
 834    COUNT2/ALL respectively within roundoff error).  This generates the
 835    result into a temp and returns the temp; it does not replace or alter
 836    the original STMT.  */
 837 /* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
 838
 839 static tree
 840 tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2,
 841                     int prob1, int prob2, int ncounts,
 842                     gcov_type count1, gcov_type count2, gcov_type all)
 843 {
 844   tree stmt1, stmt2, stmt3;
 845   tree tmp1;
 846   tree label_decl1 = create_artificial_label ();
 847   tree label_decl2 = create_artificial_label ();
 848   tree label_decl3 = create_artificial_label ();
 849   tree label1, label2, label3;
 850   tree bb1end, bb2end = NULL_TREE, bb3end;
 851   basic_block bb, bb2, bb3, bb4;
 852   tree optype = TREE_TYPE (operation);
 853   edge e12, e23 = 0, e24, e34, e14;
 854   block_stmt_iterator bsi;
 855   tree result = create_tmp_var (optype, "PROF");
 856
 857   bb = bb_for_stmt (stmt);
 858   bsi = bsi_for_stmt (stmt);
 859
 860   tmp1 = create_tmp_var (optype, "PROF");
 861   stmt1 = build_gimple_modify_stmt (result, op1);
 862   stmt2 = build_gimple_modify_stmt (tmp1, op2);
 863   stmt3 = build3 (COND_EXPR, void_type_node,
 864             build2 (LT_EXPR, boolean_type_node, result, tmp1),
 865             NULL_TREE, NULL_TREE);
 866   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 867   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 868   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 869   bb1end = stmt3;
 870
 871   if (ncounts)  /* Assumed to be 0 or 1 */
 872     {
 873       label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 874       stmt1 = build_gimple_modify_stmt (result,
 875                                         build2 (MINUS_EXPR, optype,
 876                                                 result, tmp1));
 877       stmt2 = build3 (COND_EXPR, void_type_node,
 878                 build2 (LT_EXPR, boolean_type_node, result, tmp1),
 879                 NULL_TREE, NULL_TREE);
 880       bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 881       bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 882       bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 883       bb2end = stmt2;
 884     }
 885
 886   /* Fallback case. */
 887   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 888   stmt1 = build_gimple_modify_stmt (result,
 889                                     build2 (TREE_CODE (operation), optype,
 890                                             result, tmp1));
 891   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 892   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 893   bb3end = stmt1;
 894
 895   label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
 896   bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
 897
 898   /* Fix CFG. */
 899   /* Edge e23 connects bb2 to bb3, etc. */
 900   /* However block 3 is optional; if it is not there, references
 901      to 3 really refer to block 2. */
 902   e12 = split_block (bb, bb1end);
 903   bb2 = e12->dest;
 904   bb2->count = all - count1;
 905
 906   if (ncounts)  /* Assumed to be 0 or 1.  */
 907     {
 908       e23 = split_block (bb2, bb2end);
 909       bb3 = e23->dest;
 910       bb3->count = all - count1 - count2;
 911     }
 912
 913   e34 = split_block (ncounts ? bb3 : bb2, bb3end);
 914   bb4 = e34->dest;
 915   bb4->count = all;
 916
 917   e12->flags &= ~EDGE_FALLTHRU;
 918   e12->flags |= EDGE_FALSE_VALUE;
 919   e12->probability = REG_BR_PROB_BASE - prob1;
 920   e12->count = all - count1;
 921
 922   e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
 923   e14->probability = prob1;
 924   e14->count = count1;
 925
 926   if (ncounts)  /* Assumed to be 0 or 1.  */
 927     {
 928       e23->flags &= ~EDGE_FALLTHRU;
 929       e23->flags |= EDGE_FALSE_VALUE;
 930       e23->count = all - count1 - count2;
 931       e23->probability = REG_BR_PROB_BASE - prob2;
 932
 933       e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
 934       e24->probability = prob2;
 935       e24->count = count2;
 936     }
 937
 938   e34->probability = REG_BR_PROB_BASE;
 939   e34->count = all - count1 - count2;
 940
 941   return result;
 942 }
 943
 944 /* Do transforms 3) and 4) on INSN if applicable.  */
 945 static bool
 946 tree_mod_subtract_transform (tree stmt)
 947 {
 948   histogram_value histogram;
 949   enum tree_code code;
 950   gcov_type count, wrong_values, all;
 951   tree modify, op, op1, op2, result, value;
 952   int prob1, prob2;
 953   unsigned int i, steps;
 954   gcov_type count1, count2;
 955
 956   modify = stmt;
 957   if (TREE_CODE (stmt) == RETURN_EXPR
 958       && TREE_OPERAND (stmt, 0)
 959       && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
 960     modify = TREE_OPERAND (stmt, 0);
 961   if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
 962     return false;
 963   op = GIMPLE_STMT_OPERAND (modify, 1);
 964   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 965     return false;
 966   code = TREE_CODE (op);
 967
 968   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
 969     return false;
 970
 971   op1 = TREE_OPERAND (op, 0);
 972   op2 = TREE_OPERAND (op, 1);
 973
 974   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
 975   if (!histogram)
 976     return false;
 977
 978   value = histogram->hvalue.value;
 979   all = 0;
 980   wrong_values = 0;
 981   for (i = 0; i < histogram->hdata.intvl.steps; i++)
 982     all += histogram->hvalue.counters[i];
 983
 984   wrong_values += histogram->hvalue.counters[i];
 985   wrong_values += histogram->hvalue.counters[i+1];
 986   steps = histogram->hdata.intvl.steps;
 987   all += wrong_values;
 988   count1 = histogram->hvalue.counters[0];
 989   count2 = histogram->hvalue.counters[1];
 990
 991   /* Compute probability of taking the optimal path.  */
 992   if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count))
 993     {
 994       gimple_remove_histogram_value (cfun, stmt, histogram);
 995       return false;
 996     }
 997
 998   /* We require that we use just subtractions in at least 50% of all
 999      evaluations.  */
1000   count = 0;
1001   for (i = 0; i < histogram->hdata.intvl.steps; i++)
1002     {
1003       count += histogram->hvalue.counters[i];
1004       if (count * 2 >= all)
1005         break;
1006     }
1007   if (i == steps
1008       || !maybe_hot_bb_p (bb_for_stmt (stmt)))
1009     return false;
1010
1011   gimple_remove_histogram_value (cfun, stmt, histogram);
1012   if (dump_file)
1013     {
1014       fprintf (dump_file, "Mod subtract transformation on insn ");
1015       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1016     }
1017
1018   /* Compute probability of taking the optimal path(s).  */
1019   prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all;
1020   prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all;
1021
1022   /* In practice, "steps" is always 2.  This interface reflects this,
1023      and will need to be changed if "steps" can change.  */
1024   result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i,
1025                               count1, count2, all);
1026
1027   GIMPLE_STMT_OPERAND (modify, 1) = result;
1028
1029   return true;
1030 }
1031
1032 static struct cgraph_node** pid_map = NULL;
1033
1034 /* Initialize map of pids (pid -> cgraph node) */
1035
1036 static void
1037 init_pid_map (void)
1038 {
1039   struct cgraph_node *n;
1040
1041   if (pid_map != NULL)
1042     return;
1043
1044   pid_map
1045     = (struct cgraph_node**) xmalloc (sizeof (struct cgraph_node*) * cgraph_max_pid);
1046
1047   for (n = cgraph_nodes; n; n = n->next)
1048     {
1049       if (n->pid != -1)
1050         pid_map [n->pid] = n;
1051     }
1052 }
1053
1054 /* Return cgraph node for function with pid */
1055
1056 static inline struct cgraph_node*
1057 find_func_by_pid (int   pid)
1058 {
1059   init_pid_map ();
1060
1061   return pid_map [pid];
1062 }
1063
1064 /* Do transformation
1065
1066   if (actual_callee_address == address_of_most_common_function/method)
1067     do direct call
1068   else
1069     old call
1070  */
1071
1072 static tree
1073 tree_ic (tree stmt, tree call, struct cgraph_node* direct_call,
1074          int prob, gcov_type count, gcov_type all)
1075 {
1076   tree stmt1, stmt2, stmt3;
1077   tree tmp1, tmpv, tmp;
1078   tree label_decl1 = create_artificial_label ();
1079   tree label_decl2 = create_artificial_label ();
1080   tree label1, label2;
1081   tree bb1end, bb2end, bb3end;
1082   tree new_call;
1083   basic_block bb, bb2, bb3, bb4;
1084   tree optype = build_pointer_type (void_type_node);
1085   edge e12, e13, e23, e24, e34;
1086   block_stmt_iterator bsi;
1087   int region;
1088
1089   bb = bb_for_stmt (stmt);
1090   bsi = bsi_for_stmt (stmt);
1091
1092   tmpv = create_tmp_var (optype, "PROF");
1093   tmp1 = create_tmp_var (optype, "PROF");
1094   stmt1 = build_gimple_modify_stmt (tmpv,
1095                                     unshare_expr (CALL_EXPR_FN (call)));
1096   tmp = fold_convert (optype, build_addr (direct_call->decl,
1097                                           current_function_decl));
1098   stmt2 = build_gimple_modify_stmt (tmp1, tmp);
1099   stmt3 = build3 (COND_EXPR, void_type_node,
1100                   build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
1101                   NULL_TREE, NULL_TREE);
1102   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1103   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
1104   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
1105   bb1end = stmt3;
1106
1107   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
1108   stmt1 = unshare_expr (stmt);
1109   new_call = get_call_expr_in (stmt1);
1110   CALL_EXPR_FN (new_call) = build_addr (direct_call->decl,
1111                                         current_function_decl);
1112   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
1113   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1114   bb2end = stmt1;
1115
1116   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
1117   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
1118   bb3end = stmt;
1119
1120   /* Fix CFG. */
1121   /* Edge e23 connects bb2 to bb3, etc. */
1122   e12 = split_block (bb, bb1end);
1123   bb2 = e12->dest;
1124   bb2->count = count;
1125   e23 = split_block (bb2, bb2end);
1126   bb3 = e23->dest;
1127   bb3->count = all - count;
1128   e34 = split_block (bb3, bb3end);
1129   bb4 = e34->dest;
1130   bb4->count = all;
1131
1132   e12->flags &= ~EDGE_FALLTHRU;
1133   e12->flags |= EDGE_FALSE_VALUE;
1134   e12->probability = prob;
1135   e12->count = count;
1136
1137   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
1138   e13->probability = REG_BR_PROB_BASE - prob;
1139   e13->count = all - count;
1140
1141   remove_edge (e23);
1142
1143   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
1144   e24->probability = REG_BR_PROB_BASE;
1145   e24->count = count;
1146   e34->probability = REG_BR_PROB_BASE;
1147   e34->count = all - count;
1148
1149   /* Fix eh edges */
1150   region = lookup_stmt_eh_region (stmt);
1151   if (region >=0 && tree_could_throw_p (stmt1))
1152     {
1153       add_stmt_to_eh_region (stmt1, region);
1154       make_eh_edges (stmt1);
1155     }
1156
1157   if (region >=0 && tree_could_throw_p (stmt))
1158     {
1159       tree_purge_dead_eh_edges (bb4);
1160       make_eh_edges (stmt);
1161     }
1162
1163   return stmt1;
1164 }
1165
1166 /*
1167   For every checked indirect/virtual call determine if most common pid of
1168   function/class method has probability more than 50%. If yes modify code of
1169   this call to:
1170  */
1171
1172 static bool
1173 tree_ic_transform (tree stmt)
1174 {
1175   histogram_value histogram;
1176   gcov_type val, count, all;
1177   int prob;
1178   tree call, callee, modify;
1179   struct cgraph_node *direct_call;
1180
1181   call = get_call_expr_in (stmt);
1182
1183   if (!call || TREE_CODE (call) != CALL_EXPR)
1184     return false;
1185
1186   callee = CALL_EXPR_FN (call);
1187
1188   if (TREE_CODE (callee) == ADDR_EXPR)
1189     return false;
1190
1191   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1192   if (!histogram)
1193     return false;
1194
1195   val = histogram->hvalue.counters [0];
1196   count = histogram->hvalue.counters [1];
1197   all = histogram->hvalue.counters [2];
1198   gimple_remove_histogram_value (cfun, stmt, histogram);
1199
1200   if (4 * count <= 3 * all)
1201     return false;
1202
1203   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1204   direct_call = find_func_by_pid ((int)val);
1205
1206   if (direct_call == NULL)
1207     return false;
1208
1209   modify = tree_ic (stmt, call, direct_call, prob, count, all);
1210
1211   if (dump_file)
1212     {
1213       fprintf (dump_file, "Indirect call -> direct call ");
1214       print_generic_expr (dump_file, call, TDF_SLIM);
1215       fprintf (dump_file, "=> ");
1216       print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1217       fprintf (dump_file, " transformation on insn ");
1218       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1219       fprintf (dump_file, " to ");
1220       print_generic_stmt (dump_file, modify, TDF_SLIM);
1221       fprintf (dump_file, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1222                " hist->all "HOST_WIDEST_INT_PRINT_DEC"\n", count, all);
1223     }
1224
1225   return true;
1226 }
1227
1228 /* Return true if the stringop CALL with FNDECL shall be profiled.  */
1229 static bool
1230 interesting_stringop_to_profile_p (tree fndecl, tree call)
1231 {
1232   enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
1233
1234   if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY
1235       && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO)
1236     return false;
1237
1238   switch (fcode)
1239     {
1240      case BUILT_IN_MEMCPY:
1241      case BUILT_IN_MEMPCPY:
1242        return validate_arglist (call,
1243                                 POINTER_TYPE, POINTER_TYPE, INTEGER_TYPE,
1244                                 VOID_TYPE);
1245      case BUILT_IN_MEMSET:
1246        return validate_arglist (call,
1247                                 POINTER_TYPE, INTEGER_TYPE, INTEGER_TYPE,
1248                                 VOID_TYPE);
1249      case BUILT_IN_BZERO:
1250        return validate_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1251                                 VOID_TYPE);
1252      default:
1253        gcc_unreachable ();
1254     }
1255 }
1256
1257 /* Convert   stringop (..., size)
1258    into
1259    if (size == VALUE)
1260      stringop (...., VALUE);
1261    else
1262      stringop (...., size);
1263    assuming constant propagation of VALUE will happen later.
1264 */
1265 static void
1266 tree_stringop_fixed_value (tree stmt, tree value, int prob, gcov_type count,
1267                            gcov_type all)
1268 {
1269   tree stmt1, stmt2, stmt3;
1270   tree tmp1, tmpv;
1271   tree label_decl1 = create_artificial_label ();
1272   tree label_decl2 = create_artificial_label ();
1273   tree label1, label2;
1274   tree bb1end, bb2end;
1275   basic_block bb, bb2, bb3, bb4;
1276   edge e12, e13, e23, e24, e34;
1277   block_stmt_iterator bsi;
1278   tree call = get_call_expr_in (stmt);
1279   tree blck_size = CALL_EXPR_ARG (call, 2);
1280   tree optype = TREE_TYPE (blck_size);
1281   int region;
1282
1283   bb = bb_for_stmt (stmt);
1284   bsi = bsi_for_stmt (stmt);
1285
1286   if (bsi_end_p (bsi))
1287     {
1288       edge_iterator ei;
1289       for (ei = ei_start (bb->succs); (e34 = ei_safe_edge (ei)); )
1290         if (!e34->flags & EDGE_ABNORMAL)
1291           break;
1292     }
1293   else
1294     {
1295       e34 = split_block (bb, stmt);
1296       bsi = bsi_for_stmt (stmt);
1297     }
1298   bb4 = e34->dest;
1299
1300   tmpv = create_tmp_var (optype, "PROF");
1301   tmp1 = create_tmp_var (optype, "PROF");
1302   stmt1 = build_gimple_modify_stmt (tmpv, fold_convert (optype, value));
1303   stmt2 = build_gimple_modify_stmt (tmp1, blck_size);
1304   stmt3 = build3 (COND_EXPR, void_type_node,
1305             build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
1306             NULL_TREE, NULL_TREE);
1307   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1308   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
1309   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
1310   bb1end = stmt3;
1311
1312   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
1313   stmt1 = unshare_expr (stmt);
1314   call = get_call_expr_in (stmt1);
1315   CALL_EXPR_ARG (call, 2) = value;
1316   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
1317   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1318   region = lookup_stmt_eh_region (stmt);
1319   if (region >= 0)
1320     add_stmt_to_eh_region (stmt1, region);
1321   bb2end = stmt1;
1322   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
1323   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
1324
1325   /* Fix CFG. */
1326   /* Edge e23 connects bb2 to bb3, etc. */
1327   e12 = split_block (bb, bb1end);
1328   bb2 = e12->dest;
1329   bb2->count = count;
1330   e23 = split_block (bb2, bb2end);
1331   bb3 = e23->dest;
1332   bb3->count = all - count;
1333
1334   e12->flags &= ~EDGE_FALLTHRU;
1335   e12->flags |= EDGE_FALSE_VALUE;
1336   e12->probability = prob;
1337   e12->count = count;
1338
1339   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
1340   e13->probability = REG_BR_PROB_BASE - prob;
1341   e13->count = all - count;
1342
1343   remove_edge (e23);
1344
1345   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
1346   e24->probability = REG_BR_PROB_BASE;
1347   e24->count = count;
1348
1349   e34->probability = REG_BR_PROB_BASE;
1350   e34->count = all - count;
1351 }
1352
1353 /* Find values inside STMT for that we want to measure histograms for
1354    division/modulo optimization.  */
1355 static bool
1356 tree_stringops_transform (block_stmt_iterator *bsi)
1357 {
1358   tree stmt = bsi_stmt (*bsi);
1359   tree call = get_call_expr_in (stmt);
1360   tree fndecl;
1361   tree blck_size;
1362   enum built_in_function fcode;
1363   histogram_value histogram;
1364   gcov_type count, all, val;
1365   tree value;
1366   tree dest, src;
1367   unsigned int dest_align, src_align;
1368   int prob;
1369   tree tree_val;
1370
1371   if (!call)
1372     return false;
1373   fndecl = get_callee_fndecl (call);
1374   if (!fndecl)
1375     return false;
1376   fcode = DECL_FUNCTION_CODE (fndecl);
1377   if (!interesting_stringop_to_profile_p (fndecl, call))
1378     return false;
1379
1380   if (fcode == BUILT_IN_BZERO)
1381     blck_size = CALL_EXPR_ARG (call, 1);
1382   else
1383     blck_size = CALL_EXPR_ARG (call, 2);
1384   if (TREE_CODE (blck_size) == INTEGER_CST)
1385     return false;
1386
1387   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1388   if (!histogram)
1389     return false;
1390   value = histogram->hvalue.value;
1391   val = histogram->hvalue.counters[0];
1392   count = histogram->hvalue.counters[1];
1393   all = histogram->hvalue.counters[2];
1394   gimple_remove_histogram_value (cfun, stmt, histogram);
1395   /* We require that count is at least half of all; this means
1396      that for the transformation to fire the value must be constant
1397      at least 80% of time.  */
1398   if ((6 * count / 5) < all || !maybe_hot_bb_p (bb_for_stmt (stmt)))
1399     return false;
1400   if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
1401     return false;
1402   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1403   dest = CALL_EXPR_ARG (call, 0);
1404   dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1405   switch (fcode)
1406     {
1407     case BUILT_IN_MEMCPY:
1408     case BUILT_IN_MEMPCPY:
1409       src = CALL_EXPR_ARG (call, 1);
1410       src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1411       if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1412         return false;
1413       break;
1414     case BUILT_IN_MEMSET:
1415       if (!can_store_by_pieces (val, builtin_memset_read_str,
1416                                 CALL_EXPR_ARG (call, 1),
1417                                 dest_align, true))
1418         return false;
1419       break;
1420     case BUILT_IN_BZERO:
1421       if (!can_store_by_pieces (val, builtin_memset_read_str,
1422                                 integer_zero_node,
1423                                 dest_align, true))
1424         return false;
1425       break;
1426     default:
1427       gcc_unreachable ();
1428     }
1429   tree_val = build_int_cst_wide (get_gcov_type (),
1430                                  (unsigned HOST_WIDE_INT) val,
1431                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1432   if (dump_file)
1433     {
1434       fprintf (dump_file, "Single value %i stringop transformation on ",
1435                (int)val);
1436       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1437     }
1438   tree_stringop_fixed_value (stmt, tree_val, prob, count, all);
1439
1440   return true;
1441 }
1442
1443 void
1444 stringop_block_profile (tree stmt, unsigned int *expected_align,
1445                         HOST_WIDE_INT *expected_size)
1446 {
1447   histogram_value histogram;
1448   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1449   if (!histogram)
1450     *expected_size = -1;
1451   else if (!histogram->hvalue.counters[1])
1452     {
1453       *expected_size = -1;
1454       gimple_remove_histogram_value (cfun, stmt, histogram);
1455     }
1456   else
1457     {
1458       gcov_type size;
1459       size = ((histogram->hvalue.counters[0]
1460               + histogram->hvalue.counters[1] / 2)
1461                / histogram->hvalue.counters[1]);
1462       /* Even if we can hold bigger value in SIZE, INT_MAX
1463          is safe "infinity" for code generation strategies.  */
1464       if (size > INT_MAX)
1465         size = INT_MAX;
1466       *expected_size = size;
1467       gimple_remove_histogram_value (cfun, stmt, histogram);
1468     }
1469   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1470   if (!histogram)
1471     *expected_align = 0;
1472   else if (!histogram->hvalue.counters[0])
1473     {
1474       gimple_remove_histogram_value (cfun, stmt, histogram);
1475       *expected_align = 0;
1476     }
1477   else
1478     {
1479       gcov_type count;
1480       int alignment;
1481
1482       count = histogram->hvalue.counters[0];
1483       alignment = 1;
1484       while (!(count & alignment)
1485              && (alignment * 2 * BITS_PER_UNIT))
1486         alignment <<= 1;
1487       *expected_align = alignment * BITS_PER_UNIT;
1488       gimple_remove_histogram_value (cfun, stmt, histogram);
1489     }
1490 }
1491
1492 struct value_prof_hooks {
1493   /* Find list of values for which we want to measure histograms.  */
1494   void (*find_values_to_profile) (histogram_values *);
1495
1496   /* Identify and exploit properties of values that are hard to analyze
1497      statically.  See value-prof.c for more detail.  */
1498   bool (*value_profile_transformations) (void);
1499 };
1500 \f
1501 /* Find values inside STMT for that we want to measure histograms for
1502    division/modulo optimization.  */
1503 static void
1504 tree_divmod_values_to_profile (tree stmt, histogram_values *values)
1505 {
1506   tree assign, lhs, rhs, divisor, op0, type;
1507   histogram_value hist;
1508
1509   if (TREE_CODE (stmt) == RETURN_EXPR)
1510     assign = TREE_OPERAND (stmt, 0);
1511   else
1512     assign = stmt;
1513
1514   if (!assign
1515       || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
1516     return;
1517   lhs = GIMPLE_STMT_OPERAND (assign, 0);
1518   type = TREE_TYPE (lhs);
1519   if (!INTEGRAL_TYPE_P (type))
1520     return;
1521
1522   rhs = GIMPLE_STMT_OPERAND (assign, 1);
1523   switch (TREE_CODE (rhs))
1524     {
1525     case TRUNC_DIV_EXPR:
1526     case TRUNC_MOD_EXPR:
1527       divisor = TREE_OPERAND (rhs, 1);
1528       op0 = TREE_OPERAND (rhs, 0);
1529
1530       VEC_reserve (histogram_value, heap, *values, 3);
1531
1532       if (is_gimple_reg (divisor))
1533         /* Check for the case where the divisor is the same value most
1534            of the time.  */
1535         VEC_quick_push (histogram_value, *values,
1536                         gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1537                                                       stmt, divisor));
1538
1539       /* For mod, check whether it is not often a noop (or replaceable by
1540          a few subtractions).  */
1541       if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
1542           && TYPE_UNSIGNED (type))
1543         {
1544           tree val;
1545           /* Check for a special case where the divisor is power of 2.  */
1546           VEC_quick_push (histogram_value, *values,
1547                           gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1548                                                         stmt, divisor));
1549
1550           val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1551           hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1552                                                stmt, val);
1553           hist->hdata.intvl.int_start = 0;
1554           hist->hdata.intvl.steps = 2;
1555           VEC_quick_push (histogram_value, *values, hist);
1556         }
1557       return;
1558
1559     default:
1560       return;
1561     }
1562 }
1563
1564 /* Find calls inside STMT for that we want to measure histograms for
1565    indirect/virtual call optimization. */
1566
1567 static void
1568 tree_indirect_call_to_profile (tree stmt, histogram_values *values)
1569 {
1570   tree                  call;
1571   tree                  callee;
1572
1573   call = get_call_expr_in (stmt);
1574
1575   if (!call || TREE_CODE (call) != CALL_EXPR)
1576     return;
1577
1578   callee = CALL_EXPR_FN (call);
1579
1580   if (TREE_CODE (callee) == ADDR_EXPR)
1581     return;
1582
1583   VEC_reserve (histogram_value, heap, *values, 3);
1584
1585   VEC_quick_push (histogram_value, *values,
1586                   gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1587                                                 stmt, callee));
1588
1589   return;
1590 }
1591
1592 /* Find values inside STMT for that we want to measure histograms for
1593    string operations.  */
1594 static void
1595 tree_stringops_values_to_profile (tree stmt, histogram_values *values)
1596 {
1597   tree call = get_call_expr_in (stmt);
1598   tree fndecl;
1599   tree blck_size;
1600   tree dest;
1601   enum built_in_function fcode;
1602
1603   if (!call)
1604     return;
1605   fndecl = get_callee_fndecl (call);
1606   if (!fndecl)
1607     return;
1608   fcode = DECL_FUNCTION_CODE (fndecl);
1609
1610   if (!interesting_stringop_to_profile_p (fndecl, call))
1611     return;
1612
1613   dest = CALL_EXPR_ARG (call, 0);
1614   if (fcode == BUILT_IN_BZERO)
1615     blck_size = CALL_EXPR_ARG (call, 1);
1616   else
1617     blck_size = CALL_EXPR_ARG (call, 2);
1618
1619   if (TREE_CODE (blck_size) != INTEGER_CST)
1620     {
1621       VEC_safe_push (histogram_value, heap, *values,
1622                      gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1623                                                    stmt, blck_size));
1624       VEC_safe_push (histogram_value, heap, *values,
1625                      gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1626                                                    stmt, blck_size));
1627     }
1628   if (TREE_CODE (blck_size) != INTEGER_CST)
1629     VEC_safe_push (histogram_value, heap, *values,
1630                    gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1631                                                  stmt, dest));
1632 }
1633
1634 /* Find values inside STMT for that we want to measure histograms and adds
1635    them to list VALUES.  */
1636
1637 static void
1638 tree_values_to_profile (tree stmt, histogram_values *values)
1639 {
1640   if (flag_value_profile_transformations)
1641     {
1642       tree_divmod_values_to_profile (stmt, values);
1643       tree_stringops_values_to_profile (stmt, values);
1644       tree_indirect_call_to_profile (stmt, values);
1645     }
1646 }
1647
1648 static void
1649 tree_find_values_to_profile (histogram_values *values)
1650 {
1651   basic_block bb;
1652   block_stmt_iterator bsi;
1653   unsigned i;
1654   histogram_value hist = NULL;
1655
1656   *values = NULL;
1657   FOR_EACH_BB (bb)
1658     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1659       tree_values_to_profile (bsi_stmt (bsi), values);
1660
1661   for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
1662     {
1663       switch (hist->type)
1664         {
1665         case HIST_TYPE_INTERVAL:
1666           hist->n_counters = hist->hdata.intvl.steps + 2;
1667           break;
1668
1669         case HIST_TYPE_POW2:
1670           hist->n_counters = 2;
1671           break;
1672
1673         case HIST_TYPE_SINGLE_VALUE:
1674           hist->n_counters = 3;
1675           break;
1676
1677         case HIST_TYPE_CONST_DELTA:
1678           hist->n_counters = 4;
1679           break;
1680
1681         case HIST_TYPE_INDIR_CALL:
1682           hist->n_counters = 3;
1683           break;
1684
1685         case HIST_TYPE_AVERAGE:
1686           hist->n_counters = 2;
1687           break;
1688
1689         case HIST_TYPE_IOR:
1690           hist->n_counters = 1;
1691           break;
1692
1693         default:
1694           gcc_unreachable ();
1695         }
1696       if (dump_file)
1697         {
1698           fprintf (dump_file, "Stmt ");
1699           print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
1700           dump_histogram_value (dump_file, hist);
1701         }
1702     }
1703 }
1704
1705 static struct value_prof_hooks tree_value_prof_hooks = {
1706   tree_find_values_to_profile,
1707   tree_value_profile_transformations
1708 };
1709
1710 void
1711 tree_register_value_prof_hooks (void)
1712 {
1713   gcc_assert (current_ir_type () == IR_GIMPLE);
1714   value_prof_hooks = &tree_value_prof_hooks;
1715 }
1716 \f
1717 /* IR-independent entry points.  */
1718 void
1719 find_values_to_profile (histogram_values *values)
1720 {
1721   (value_prof_hooks->find_values_to_profile) (values);
1722 }
1723
1724 bool
1725 value_profile_transformations (void)
1726 {
1727   return (value_prof_hooks->value_profile_transformations) ();
1728 }
1729 \f
1730