gcc/value-prof.c

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