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