gcc/value-prof.c

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