gcc/value-prof.c

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