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             NULL_TREE, NULL_TREE);
 531   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 532   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 533   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 534   bb1end = stmt3;
 535
 536   tmp2 = create_tmp_var (optype, "PROF");
 537   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 538   stmt1 = build_gimple_modify_stmt (tmp2,
 539                                     build2 (TREE_CODE (operation), optype,
 540                                             op1, tmpv));
 541   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 542   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 543   bb2end = stmt1;
 544
 545   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 546   stmt1 = build_gimple_modify_stmt (tmp2,
 547                                     build2 (TREE_CODE (operation), optype,
 548                                             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 = build_gimple_modify_stmt (tmp2,
 684                                     build2 (PLUS_EXPR, optype, op2,
 685                                             build_int_cst (optype, -1)));
 686   stmt3 = build_gimple_modify_stmt (tmp3,
 687                                     build2 (BIT_AND_EXPR, optype, tmp2, op2));
 688   stmt4 = build3 (COND_EXPR, void_type_node,
 689                   build2 (NE_EXPR, boolean_type_node,
 690                           tmp3, build_int_cst (optype, 0)),
 691                   NULL_TREE, NULL_TREE);
 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 = build_gimple_modify_stmt (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 = build_gimple_modify_stmt (result,
 707                                     build2 (TREE_CODE (operation), optype,
 708                                             op1, op2));
 709   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 710   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 711   bb3end = stmt1;
 712
 713   /* Fix CFG. */
 714   /* Edge e23 connects bb2 to bb3, etc. */
 715   e12 = split_block (bb, bb1end);
 716   bb2 = e12->dest;
 717   bb2->count = count;
 718   e23 = split_block (bb2, bb2end);
 719   bb3 = e23->dest;
 720   bb3->count = all - count;
 721   e34 = split_block (bb3, bb3end);
 722   bb4 = e34->dest;
 723   bb4->count = all;
 724
 725   e12->flags &= ~EDGE_FALLTHRU;
 726   e12->flags |= EDGE_FALSE_VALUE;
 727   e12->probability = prob;
 728   e12->count = count;
 729
 730   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
 731   e13->probability = REG_BR_PROB_BASE - prob;
 732   e13->count = all - count;
 733
 734   remove_edge (e23);
 735
 736   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
 737   e24->probability = REG_BR_PROB_BASE;
 738   e24->count = count;
 739
 740   e34->probability = REG_BR_PROB_BASE;
 741   e34->count = all - count;
 742
 743   return result;
 744 }
 745
 746 /* Do transform 2) on INSN if applicable.  */
 747 static bool
 748 tree_mod_pow2_value_transform (tree stmt)
 749 {
 750   histogram_value histogram;
 751   enum tree_code code;
 752   gcov_type count, wrong_values, all;
 753   tree modify, op, op1, op2, result, value;
 754   int prob;
 755
 756   modify = stmt;
 757   if (TREE_CODE (stmt) == RETURN_EXPR
 758       && TREE_OPERAND (stmt, 0)
 759       && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
 760     modify = TREE_OPERAND (stmt, 0);
 761   if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
 762     return false;
 763   op = GIMPLE_STMT_OPERAND (modify, 1);
 764   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 765     return false;
 766   code = TREE_CODE (op);
 767
 768   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
 769     return false;
 770
 771   op1 = TREE_OPERAND (op, 0);
 772   op2 = TREE_OPERAND (op, 1);
 773
 774   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
 775   if (!histogram)
 776     return false;
 777
 778   value = histogram->hvalue.value;
 779   wrong_values = histogram->hvalue.counters[0];
 780   count = histogram->hvalue.counters[1];
 781
 782   gimple_remove_histogram_value (cfun, stmt, histogram);
 783
 784   /* We require that we hit a power of 2 at least half of all evaluations.  */
 785   if (simple_cst_equal (op2, value) != 1 || count < wrong_values
 786       || !maybe_hot_bb_p (bb_for_stmt (stmt)))
 787     return false;
 788
 789   if (dump_file)
 790     {
 791       fprintf (dump_file, "Mod power of 2 transformation on insn ");
 792       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 793     }
 794
 795   /* Compute probability of taking the optimal path.  */
 796   all = count + wrong_values;
 797
 798   if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
 799     return false;
 800
 801   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 802
 803   result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
 804
 805   GIMPLE_STMT_OPERAND (modify, 1) = result;
 806
 807   return true;
 808 }
 809
 810 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
 811    and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
 812    support.  Currently only NCOUNTS==0 or 1 is supported and this is
 813    built into this interface.  The probabilities of taking the optimal
 814    paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
 815    COUNT2/ALL respectively within roundoff error).  This generates the
 816    result into a temp and returns the temp; it does not replace or alter
 817    the original STMT.  */
 818 /* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
 819
 820 static tree
 821 tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2,
 822                     int prob1, int prob2, int ncounts,
 823                     gcov_type count1, gcov_type count2, gcov_type all)
 824 {
 825   tree stmt1, stmt2, stmt3;
 826   tree tmp1;
 827   tree label_decl1 = create_artificial_label ();
 828   tree label_decl2 = create_artificial_label ();
 829   tree label_decl3 = create_artificial_label ();
 830   tree label1, label2, label3;
 831   tree bb1end, bb2end = NULL_TREE, bb3end;
 832   basic_block bb, bb2, bb3, bb4;
 833   tree optype = TREE_TYPE (operation);
 834   edge e12, e23 = 0, e24, e34, e14;
 835   block_stmt_iterator bsi;
 836   tree result = create_tmp_var (optype, "PROF");
 837
 838   bb = bb_for_stmt (stmt);
 839   bsi = bsi_for_stmt (stmt);
 840
 841   tmp1 = create_tmp_var (optype, "PROF");
 842   stmt1 = build_gimple_modify_stmt (result, op1);
 843   stmt2 = build_gimple_modify_stmt (tmp1, op2);
 844   stmt3 = build3 (COND_EXPR, void_type_node,
 845             build2 (LT_EXPR, boolean_type_node, result, tmp1),
 846             NULL_TREE, NULL_TREE);
 847   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 848   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 849   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 850   bb1end = stmt3;
 851
 852   if (ncounts)  /* Assumed to be 0 or 1 */
 853     {
 854       label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 855       stmt1 = build_gimple_modify_stmt (result,
 856                                         build2 (MINUS_EXPR, optype,
 857                                                 result, tmp1));
 858       stmt2 = build3 (COND_EXPR, void_type_node,
 859                 build2 (LT_EXPR, boolean_type_node, result, tmp1),
 860                 NULL_TREE, NULL_TREE);
 861       bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 862       bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 863       bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 864       bb2end = stmt2;
 865     }
 866
 867   /* Fallback case. */
 868   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 869   stmt1 = build_gimple_modify_stmt (result,
 870                                     build2 (TREE_CODE (operation), optype,
 871                                             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, tmp;
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 = build_gimple_modify_stmt (tmpv,
1076                                     unshare_expr (CALL_EXPR_FN (call)));
1077   tmp = fold_convert (optype, build_addr (direct_call->decl,
1078                                           current_function_decl));
1079   stmt2 = build_gimple_modify_stmt (tmp1, tmp);
1080   stmt3 = build3 (COND_EXPR, void_type_node,
1081                   build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
1082                   NULL_TREE, NULL_TREE);
1083   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1084   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
1085   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
1086   bb1end = stmt3;
1087
1088   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
1089   stmt1 = unshare_expr (stmt);
1090   new_call = get_call_expr_in (stmt1);
1091   CALL_EXPR_FN (new_call) = build_addr (direct_call->decl,
1092                                         current_function_decl);
1093   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
1094   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1095   bb2end = stmt1;
1096
1097   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
1098   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
1099   bb3end = stmt;
1100
1101   /* Fix CFG. */
1102   /* Edge e23 connects bb2 to bb3, etc. */
1103   e12 = split_block (bb, bb1end);
1104   bb2 = e12->dest;
1105   bb2->count = count;
1106   e23 = split_block (bb2, bb2end);
1107   bb3 = e23->dest;
1108   bb3->count = all - count;
1109   e34 = split_block (bb3, bb3end);
1110   bb4 = e34->dest;
1111   bb4->count = all;
1112
1113   e12->flags &= ~EDGE_FALLTHRU;
1114   e12->flags |= EDGE_FALSE_VALUE;
1115   e12->probability = prob;
1116   e12->count = count;
1117
1118   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
1119   e13->probability = REG_BR_PROB_BASE - prob;
1120   e13->count = all - count;
1121
1122   remove_edge (e23);
1123
1124   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
1125   e24->probability = REG_BR_PROB_BASE;
1126   e24->count = count;
1127   e34->probability = REG_BR_PROB_BASE;
1128   e34->count = all - count;
1129
1130   /* Fix eh edges */
1131   region = lookup_stmt_eh_region (stmt);
1132   if (region >=0 && tree_could_throw_p (stmt1))
1133     {
1134       add_stmt_to_eh_region (stmt1, region);
1135       make_eh_edges (stmt1);
1136     }
1137
1138   if (region >=0 && tree_could_throw_p (stmt))
1139     {
1140       tree_purge_dead_eh_edges (bb4);
1141       make_eh_edges (stmt);
1142     }
1143
1144   return stmt1;
1145 }
1146
1147 /*
1148   For every checked indirect/virtual call determine if most common pid of
1149   function/class method has probability more than 50%. If yes modify code of
1150   this call to:
1151  */
1152
1153 static bool
1154 tree_ic_transform (tree stmt)
1155 {
1156   histogram_value histogram;
1157   gcov_type val, count, all;
1158   int prob;
1159   tree call, callee, modify;
1160   struct cgraph_node *direct_call;
1161
1162   call = get_call_expr_in (stmt);
1163
1164   if (!call || TREE_CODE (call) != CALL_EXPR)
1165     return false;
1166
1167   callee = CALL_EXPR_FN (call);
1168
1169   if (TREE_CODE (callee) == ADDR_EXPR)
1170     return false;
1171
1172   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1173   if (!histogram)
1174     return false;
1175
1176   val = histogram->hvalue.counters [0];
1177   count = histogram->hvalue.counters [1];
1178   all = histogram->hvalue.counters [2];
1179   gimple_remove_histogram_value (cfun, stmt, histogram);
1180
1181   if (4 * count <= 3 * all)
1182     return false;
1183
1184   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1185   direct_call = find_func_by_pid ((int)val);
1186
1187   if (direct_call == NULL)
1188     return false;
1189
1190   modify = tree_ic (stmt, call, direct_call, prob, count, all);
1191
1192   if (dump_file)
1193     {
1194       fprintf (dump_file, "Indirect call -> direct call ");
1195       print_generic_expr (dump_file, call, TDF_SLIM);
1196       fprintf (dump_file, "=> ");
1197       print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1198       fprintf (dump_file, " transformation on insn ");
1199       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1200       fprintf (dump_file, " to ");
1201       print_generic_stmt (dump_file, modify, TDF_SLIM);
1202     }
1203
1204   return true;
1205 }
1206
1207 /* Return true if the stringop CALL with FNDECL shall be profiled.  */
1208 static bool
1209 interesting_stringop_to_profile_p (tree fndecl, tree call)
1210 {
1211   enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
1212
1213   if (fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_MEMCPY
1214       && fcode != BUILT_IN_BZERO)
1215     return false;
1216
1217   switch (fcode)
1218     {
1219      case BUILT_IN_MEMCPY:
1220      case BUILT_IN_MEMPCPY:
1221        return validate_arglist (call,
1222                                 POINTER_TYPE, POINTER_TYPE, INTEGER_TYPE,
1223                                 VOID_TYPE);
1224      case BUILT_IN_MEMSET:
1225        return validate_arglist (call,
1226                                 POINTER_TYPE, INTEGER_TYPE, INTEGER_TYPE,
1227                                 VOID_TYPE);
1228      case BUILT_IN_BZERO:
1229        return validate_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1230                                 VOID_TYPE);
1231      default:
1232        gcc_unreachable ();
1233     }
1234 }
1235
1236 /* Convert   stringop (..., size)
1237    into
1238    if (size == VALUE)
1239      stringop (...., VALUE);
1240    else
1241      stringop (...., size);
1242    assuming constant propagation of VALUE will happen later.
1243 */
1244 static void
1245 tree_stringop_fixed_value (tree stmt, tree value, int prob, gcov_type count,
1246                            gcov_type all)
1247 {
1248   tree stmt1, stmt2, stmt3;
1249   tree tmp1, tmpv;
1250   tree label_decl1 = create_artificial_label ();
1251   tree label_decl2 = create_artificial_label ();
1252   tree label1, label2;
1253   tree bb1end, bb2end;
1254   basic_block bb, bb2, bb3, bb4;
1255   edge e12, e13, e23, e24, e34;
1256   block_stmt_iterator bsi;
1257   tree call = get_call_expr_in (stmt);
1258   tree blck_size = CALL_EXPR_ARG (call, 2);
1259   tree optype = TREE_TYPE (blck_size);
1260   int region;
1261
1262   bb = bb_for_stmt (stmt);
1263   bsi = bsi_for_stmt (stmt);
1264
1265   if (bsi_end_p (bsi))
1266     {
1267       edge_iterator ei;
1268       for (ei = ei_start (bb->succs); (e34 = ei_safe_edge (ei)); )
1269         if (!e34->flags & EDGE_ABNORMAL)
1270           break;
1271     }
1272   else
1273     {
1274       e34 = split_block (bb, stmt);
1275       bsi = bsi_for_stmt (stmt);
1276     }
1277   bb4 = e34->dest;
1278
1279   tmpv = create_tmp_var (optype, "PROF");
1280   tmp1 = create_tmp_var (optype, "PROF");
1281   stmt1 = build_gimple_modify_stmt (tmpv, fold_convert (optype, value));
1282   stmt2 = build_gimple_modify_stmt (tmp1, blck_size);
1283   stmt3 = build3 (COND_EXPR, void_type_node,
1284             build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
1285             NULL_TREE, NULL_TREE);
1286   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1287   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
1288   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
1289   bb1end = stmt3;
1290
1291   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
1292   stmt1 = unshare_expr (stmt);
1293   call = get_call_expr_in (stmt1);
1294   CALL_EXPR_ARG (call, 2) = value;
1295   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
1296   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1297   region = lookup_stmt_eh_region (stmt);
1298   if (region >= 0)
1299     add_stmt_to_eh_region (stmt1, region);
1300   bb2end = stmt1;
1301   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
1302   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
1303
1304   /* Fix CFG. */
1305   /* Edge e23 connects bb2 to bb3, etc. */
1306   e12 = split_block (bb, bb1end);
1307   bb2 = e12->dest;
1308   bb2->count = count;
1309   e23 = split_block (bb2, bb2end);
1310   bb3 = e23->dest;
1311   bb3->count = all - count;
1312
1313   e12->flags &= ~EDGE_FALLTHRU;
1314   e12->flags |= EDGE_FALSE_VALUE;
1315   e12->probability = prob;
1316   e12->count = count;
1317
1318   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
1319   e13->probability = REG_BR_PROB_BASE - prob;
1320   e13->count = all - count;
1321
1322   remove_edge (e23);
1323
1324   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
1325   e24->probability = REG_BR_PROB_BASE;
1326   e24->count = count;
1327
1328   e34->probability = REG_BR_PROB_BASE;
1329   e34->count = all - count;
1330 }
1331
1332 /* Find values inside STMT for that we want to measure histograms for
1333    division/modulo optimization.  */
1334 static bool
1335 tree_stringops_transform (block_stmt_iterator *bsi)
1336 {
1337   tree stmt = bsi_stmt (*bsi);
1338   tree call = get_call_expr_in (stmt);
1339   tree fndecl;
1340   tree blck_size;
1341   enum built_in_function fcode;
1342   histogram_value histogram;
1343   gcov_type count, all, val;
1344   tree value;
1345   tree dest, src;
1346   unsigned int dest_align, src_align;
1347   int prob;
1348   tree tree_val;
1349
1350   if (!call)
1351     return false;
1352   fndecl = get_callee_fndecl (call);
1353   if (!fndecl)
1354     return false;
1355   fcode = DECL_FUNCTION_CODE (fndecl);
1356   if (!interesting_stringop_to_profile_p (fndecl, call))
1357     return false;
1358
1359   if (fcode == BUILT_IN_BZERO)
1360     blck_size = CALL_EXPR_ARG (call, 1);
1361   else
1362     blck_size = CALL_EXPR_ARG (call, 2);
1363   if (TREE_CODE (blck_size) == INTEGER_CST)
1364     return false;
1365
1366   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1367   if (!histogram)
1368     return false;
1369   value = histogram->hvalue.value;
1370   val = histogram->hvalue.counters[0];
1371   count = histogram->hvalue.counters[1];
1372   all = histogram->hvalue.counters[2];
1373   gimple_remove_histogram_value (cfun, stmt, histogram);
1374   /* We require that count is at least half of all; this means
1375      that for the transformation to fire the value must be constant
1376      at least 80% of time.  */
1377   if ((6 * count / 5) < all || !maybe_hot_bb_p (bb_for_stmt (stmt)))
1378     return false;
1379   if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
1380     return false;
1381   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1382   dest = CALL_EXPR_ARG (call, 0);
1383   dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1384   switch (fcode)
1385     {
1386     case BUILT_IN_MEMCPY:
1387     case BUILT_IN_MEMPCPY:
1388       src = CALL_EXPR_ARG (call, 1);
1389       src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1390       if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1391         return false;
1392       break;
1393     case BUILT_IN_MEMSET:
1394       if (!can_store_by_pieces (val, builtin_memset_read_str,
1395                                 CALL_EXPR_ARG (call, 1),
1396                                 dest_align))
1397         return false;
1398       break;
1399     case BUILT_IN_BZERO:
1400       if (!can_store_by_pieces (val, builtin_memset_read_str,
1401                                 integer_zero_node,
1402                                 dest_align))
1403         return false;
1404       break;
1405     default:
1406       gcc_unreachable ();
1407     }
1408   tree_val = build_int_cst_wide (get_gcov_type (),
1409                                  (unsigned HOST_WIDE_INT) val,
1410                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1411   if (dump_file)
1412     {
1413       fprintf (dump_file, "Single value %i stringop transformation on ",
1414                (int)val);
1415       print_generic_stmt (dump_file, stmt, TDF_SLIM);
1416     }
1417   tree_stringop_fixed_value (stmt, tree_val, prob, count, all);
1418
1419   return true;
1420 }
1421
1422 void
1423 stringop_block_profile (tree stmt, unsigned int *expected_align,
1424                         HOST_WIDE_INT *expected_size)
1425 {
1426   histogram_value histogram;
1427   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1428   if (!histogram)
1429     *expected_size = -1;
1430   else if (!histogram->hvalue.counters[1])
1431     {
1432       *expected_size = -1;
1433       gimple_remove_histogram_value (cfun, stmt, histogram);
1434     }
1435   else
1436     {
1437       gcov_type size;
1438       size = ((histogram->hvalue.counters[0]
1439               + histogram->hvalue.counters[1] / 2)
1440                / histogram->hvalue.counters[1]);
1441       /* Even if we can hold bigger value in SIZE, INT_MAX
1442          is safe "infinity" for code generation strategies.  */
1443       if (size > INT_MAX)
1444         size = INT_MAX;
1445       *expected_size = size;
1446       gimple_remove_histogram_value (cfun, stmt, histogram);
1447     }
1448   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1449   if (!histogram)
1450     *expected_align = 0;
1451   else if (!histogram->hvalue.counters[0])
1452     {
1453       gimple_remove_histogram_value (cfun, stmt, histogram);
1454       *expected_align = 0;
1455     }
1456   else
1457     {
1458       gcov_type count;
1459       int alignment;
1460
1461       count = histogram->hvalue.counters[0];
1462       alignment = 1;
1463       while (!(count & alignment)
1464              && (alignment * 2 * BITS_PER_UNIT))
1465         alignment <<= 1;
1466       *expected_align = alignment * BITS_PER_UNIT;
1467       gimple_remove_histogram_value (cfun, stmt, histogram);
1468     }
1469 }
1470
1471 struct value_prof_hooks {
1472   /* Find list of values for which we want to measure histograms.  */
1473   void (*find_values_to_profile) (histogram_values *);
1474
1475   /* Identify and exploit properties of values that are hard to analyze
1476      statically.  See value-prof.c for more detail.  */
1477   bool (*value_profile_transformations) (void);
1478 };
1479 \f
1480 /* Find values inside STMT for that we want to measure histograms for
1481    division/modulo optimization.  */
1482 static void
1483 tree_divmod_values_to_profile (tree stmt, histogram_values *values)
1484 {
1485   tree assign, lhs, rhs, divisor, op0, type;
1486   histogram_value hist;
1487
1488   if (TREE_CODE (stmt) == RETURN_EXPR)
1489     assign = TREE_OPERAND (stmt, 0);
1490   else
1491     assign = stmt;
1492
1493   if (!assign
1494       || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
1495     return;
1496   lhs = GIMPLE_STMT_OPERAND (assign, 0);
1497   type = TREE_TYPE (lhs);
1498   if (!INTEGRAL_TYPE_P (type))
1499     return;
1500
1501   rhs = GIMPLE_STMT_OPERAND (assign, 1);
1502   switch (TREE_CODE (rhs))
1503     {
1504     case TRUNC_DIV_EXPR:
1505     case TRUNC_MOD_EXPR:
1506       divisor = TREE_OPERAND (rhs, 1);
1507       op0 = TREE_OPERAND (rhs, 0);
1508
1509       VEC_reserve (histogram_value, heap, *values, 3);
1510
1511       if (is_gimple_reg (divisor))
1512         /* Check for the case where the divisor is the same value most
1513            of the time.  */
1514         VEC_quick_push (histogram_value, *values,
1515                         gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1516                                                       stmt, divisor));
1517
1518       /* For mod, check whether it is not often a noop (or replaceable by
1519          a few subtractions).  */
1520       if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
1521           && TYPE_UNSIGNED (type))
1522         {
1523           tree val;
1524           /* Check for a special case where the divisor is power of 2.  */
1525           VEC_quick_push (histogram_value, *values,
1526                           gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1527                                                         stmt, divisor));
1528
1529           val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1530           hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1531                                                stmt, val);
1532           hist->hdata.intvl.int_start = 0;
1533           hist->hdata.intvl.steps = 2;
1534           VEC_quick_push (histogram_value, *values, hist);
1535         }
1536       return;
1537
1538     default:
1539       return;
1540     }
1541 }
1542
1543 /* Find calls inside STMT for that we want to measure histograms for
1544    indirect/virtual call optimization. */
1545
1546 static void
1547 tree_indirect_call_to_profile (tree stmt, histogram_values *values)
1548 {
1549   tree                  call;
1550   tree                  callee;
1551
1552   call = get_call_expr_in (stmt);
1553
1554   if (!call || TREE_CODE (call) != CALL_EXPR)
1555     return;
1556
1557   callee = CALL_EXPR_FN (call);
1558
1559   if (TREE_CODE (callee) == ADDR_EXPR)
1560     return;
1561
1562   VEC_reserve (histogram_value, heap, *values, 3);
1563
1564   VEC_quick_push (histogram_value, *values,
1565                   gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1566                                                 stmt, callee));
1567
1568   return;
1569 }
1570
1571 /* Find values inside STMT for that we want to measure histograms for
1572    string operations.  */
1573 static void
1574 tree_stringops_values_to_profile (tree stmt, histogram_values *values)
1575 {
1576   tree call = get_call_expr_in (stmt);
1577   tree fndecl;
1578   tree blck_size;
1579   tree dest;
1580   enum built_in_function fcode;
1581
1582   if (!call)
1583     return;
1584   fndecl = get_callee_fndecl (call);
1585   if (!fndecl)
1586     return;
1587   fcode = DECL_FUNCTION_CODE (fndecl);
1588
1589   if (!interesting_stringop_to_profile_p (fndecl, call))
1590     return;
1591
1592   dest = CALL_EXPR_ARG (call, 0);
1593   if (fcode == BUILT_IN_BZERO)
1594     blck_size = CALL_EXPR_ARG (call, 1);
1595   else
1596     blck_size = CALL_EXPR_ARG (call, 2);
1597
1598   if (TREE_CODE (blck_size) != INTEGER_CST)
1599     {
1600       VEC_safe_push (histogram_value, heap, *values,
1601                      gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1602                                                    stmt, blck_size));
1603       VEC_safe_push (histogram_value, heap, *values,
1604                      gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1605                                                    stmt, blck_size));
1606     }
1607   if (TREE_CODE (blck_size) != INTEGER_CST)
1608     VEC_safe_push (histogram_value, heap, *values,
1609                    gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1610                                                  stmt, dest));
1611 }
1612
1613 /* Find values inside STMT for that we want to measure histograms and adds
1614    them to list VALUES.  */
1615
1616 static void
1617 tree_values_to_profile (tree stmt, histogram_values *values)
1618 {
1619   if (flag_value_profile_transformations)
1620     {
1621       tree_divmod_values_to_profile (stmt, values);
1622       tree_stringops_values_to_profile (stmt, values);
1623       tree_indirect_call_to_profile (stmt, values);
1624     }
1625 }
1626
1627 static void
1628 tree_find_values_to_profile (histogram_values *values)
1629 {
1630   basic_block bb;
1631   block_stmt_iterator bsi;
1632   unsigned i;
1633   histogram_value hist = NULL;
1634
1635   *values = NULL;
1636   FOR_EACH_BB (bb)
1637     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1638       tree_values_to_profile (bsi_stmt (bsi), values);
1639
1640   for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
1641     {
1642       switch (hist->type)
1643         {
1644         case HIST_TYPE_INTERVAL:
1645           hist->n_counters = hist->hdata.intvl.steps + 2;
1646           break;
1647
1648         case HIST_TYPE_POW2:
1649           hist->n_counters = 2;
1650           break;
1651
1652         case HIST_TYPE_SINGLE_VALUE:
1653           hist->n_counters = 3;
1654           break;
1655
1656         case HIST_TYPE_CONST_DELTA:
1657           hist->n_counters = 4;
1658           break;
1659
1660         case HIST_TYPE_INDIR_CALL:
1661           hist->n_counters = 3;
1662           break;
1663
1664         case HIST_TYPE_AVERAGE:
1665           hist->n_counters = 2;
1666           break;
1667
1668         case HIST_TYPE_IOR:
1669           hist->n_counters = 1;
1670           break;
1671
1672         default:
1673           gcc_unreachable ();
1674         }
1675       if (dump_file)
1676         {
1677           fprintf (dump_file, "Stmt ");
1678           print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
1679           dump_histogram_value (dump_file, hist);
1680         }
1681     }
1682 }
1683
1684 static struct value_prof_hooks tree_value_prof_hooks = {
1685   tree_find_values_to_profile,
1686   tree_value_profile_transformations
1687 };
1688
1689 void
1690 tree_register_value_prof_hooks (void)
1691 {
1692   gcc_assert (current_ir_type () == IR_GIMPLE);
1693   value_prof_hooks = &tree_value_prof_hooks;
1694 }
1695 \f
1696 /* IR-independent entry points.  */
1697 void
1698 find_values_to_profile (histogram_values *values)
1699 {
1700   (value_prof_hooks->find_values_to_profile) (values);
1701 }
1702
1703 bool
1704 value_profile_transformations (void)
1705 {
1706   return (value_prof_hooks->value_profile_transformations) ();
1707 }
1708 \f
1709