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