gcc/value-prof.c

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