gcc/value-prof.c

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