gcc/value-prof.c

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