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