gcc/value-prof.c

   1 /* Transformations based on profile information for values.
   2    Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  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 "timevar.h"
  44 #include "tree-pass.h"
  45 #include "toplev.h"
  46
  47 static struct value_prof_hooks *value_prof_hooks;
  48
  49 /* This is the vector of histograms.  Created in find_values_to_profile.
  50    During profile generation, freed by instrument_values.
  51    During profile use, freed by value_profile_transformations.  */
  52
  53 static histogram_values static_values = NULL;
  54
  55 /* In this file value profile based optimizations are placed.  Currently the
  56    following optimizations are implemented (for more detailed descriptions
  57    see comments at value_profile_transformations):
  58
  59    1) Division/modulo specialization.  Provided that we can determine that the
  60       operands of the division have some special properties, we may use it to
  61       produce more effective code.
  62    2) Speculative prefetching.  If we are able to determine that the difference
  63       between addresses accessed by a memory reference is usually constant, we
  64       may add the prefetch instructions.
  65       FIXME: This transformation was removed together with RTL based value
  66       profiling.
  67
  68    Every such optimization should add its requirements for profiled values to
  69    insn_values_to_profile function.  This function is called from branch_prob
  70    in profile.c and the requested values are instrumented by it in the first
  71    compilation with -fprofile-arcs.  The optimization may then read the
  72    gathered data in the second compilation with -fbranch-probabilities.
  73
  74    The measured data is pointed to from the histograms
  75    field of the statement annotation of the instrumented insns.  It is
  76    kept as a linked list of struct histogram_value_t's, which contain the
  77    same information as above.  */
  78
  79
  80 static tree tree_divmod_fixed_value (tree, tree, tree, tree,
  81                                     tree, int, gcov_type, gcov_type);
  82 static tree tree_mod_pow2 (tree, tree, tree, tree, int, gcov_type, gcov_type);
  83 static tree tree_mod_subtract (tree, tree, tree, tree, int, int, int,
  84                                 gcov_type, gcov_type, gcov_type);
  85 static bool tree_divmod_fixed_value_transform (tree);
  86 static bool tree_mod_pow2_value_transform (tree);
  87 static bool tree_mod_subtract_transform (tree);
  88
  89 /* The overall number of invocations of the counter should match execution count
  90    of basic block.  Report it as error rather than internal error as it might
  91    mean that user has misused the profile somehow.  */
  92 static bool
  93 check_counter (tree stmt, const char * name, gcov_type all, gcov_type bb_count)
  94 {
  95   if (all != bb_count)
  96     {
  97       location_t * locus;
  98       locus = (stmt != NULL && EXPR_HAS_LOCATION (stmt)
  99                ? EXPR_LOCUS (stmt)
 100                : &DECL_SOURCE_LOCATION (current_function_decl));
 101       error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)",
 102              locus, name, (int)all, (int)bb_count);
 103       return true;
 104     }
 105   return false;
 106 }
 107
 108 /* Tree based transformations. */
 109 static bool
 110 tree_value_profile_transformations (void)
 111 {
 112   basic_block bb;
 113   block_stmt_iterator bsi;
 114   bool changed = false;
 115
 116   FOR_EACH_BB (bb)
 117     {
 118       /* Ignore cold areas -- we are enlarging the code.  */
 119       if (!maybe_hot_bb_p (bb))
 120         continue;
 121
 122       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 123         {
 124           tree stmt = bsi_stmt (bsi);
 125           stmt_ann_t ann = get_stmt_ann (stmt);
 126           histogram_value th = ann->histograms;
 127           if (!th)
 128             continue;
 129
 130           if (dump_file)
 131             {
 132               fprintf (dump_file, "Trying transformations on insn ");
 133               print_generic_stmt (dump_file, stmt, TDF_SLIM);
 134             }
 135
 136           /* Transformations:  */
 137           /* The order of things in this conditional controls which
 138              transformation is used when more than one is applicable.  */
 139           /* It is expected that any code added by the transformations
 140              will be added before the current statement, and that the
 141              current statement remain valid (although possibly
 142              modified) upon return.  */
 143           if (flag_value_profile_transformations
 144               && (tree_mod_subtract_transform (stmt)
 145                   || tree_divmod_fixed_value_transform (stmt)
 146                   || tree_mod_pow2_value_transform (stmt)))
 147             {
 148               changed = true;
 149               /* Original statement may no longer be in the same block. */
 150               bb = bb_for_stmt (stmt);
 151             }
 152
 153           /* Free extra storage from compute_value_histograms.  */
 154           while (th)
 155             {
 156               free (th->hvalue.counters);
 157               th = th->hvalue.next;
 158             }
 159           ann->histograms = 0;
 160         }
 161     }
 162
 163   if (changed)
 164     {
 165       counts_to_freqs ();
 166     }
 167
 168   return changed;
 169 }
 170
 171 /* Generate code for transformation 1 (with OPERATION, operands OP1
 172    and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
 173    probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
 174    within roundoff error).  This generates the result into a temp and returns
 175    the temp; it does not replace or alter the original STMT.  */
 176 static tree
 177 tree_divmod_fixed_value (tree stmt, tree operation,
 178                          tree op1, tree op2, tree value, int prob, gcov_type count,
 179                          gcov_type all)
 180 {
 181   tree stmt1, stmt2, stmt3;
 182   tree tmp1, tmp2, tmpv;
 183   tree label_decl1 = create_artificial_label ();
 184   tree label_decl2 = create_artificial_label ();
 185   tree label_decl3 = create_artificial_label ();
 186   tree label1, label2, label3;
 187   tree bb1end, bb2end, bb3end;
 188   basic_block bb, bb2, bb3, bb4;
 189   tree optype = TREE_TYPE (operation);
 190   edge e12, e13, e23, e24, e34;
 191   block_stmt_iterator bsi;
 192
 193   bb = bb_for_stmt (stmt);
 194   bsi = bsi_for_stmt (stmt);
 195
 196   tmpv = create_tmp_var (optype, "PROF");
 197   tmp1 = create_tmp_var (optype, "PROF");
 198   stmt1 = build2 (MODIFY_EXPR, optype, tmpv, fold_convert (optype, value));
 199   stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2);
 200   stmt3 = build3 (COND_EXPR, void_type_node,
 201             build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
 202             build1 (GOTO_EXPR, void_type_node, label_decl2),
 203             build1 (GOTO_EXPR, void_type_node, label_decl1));
 204   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 205   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 206   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 207   bb1end = stmt3;
 208
 209   tmp2 = create_tmp_var (optype, "PROF");
 210   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 211   stmt1 = build2 (MODIFY_EXPR, optype, tmp2,
 212                   build2 (TREE_CODE (operation), optype, op1, tmpv));
 213   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 214   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 215   bb2end = stmt1;
 216
 217   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 218   stmt1 = build2 (MODIFY_EXPR, optype, tmp2,
 219                   build2 (TREE_CODE (operation), optype, op1, op2));
 220   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 221   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 222   bb3end = stmt1;
 223
 224   label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
 225   bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
 226
 227   /* Fix CFG. */
 228   /* Edge e23 connects bb2 to bb3, etc. */
 229   e12 = split_block (bb, bb1end);
 230   bb2 = e12->dest;
 231   bb2->count = count;
 232   e23 = split_block (bb2, bb2end);
 233   bb3 = e23->dest;
 234   bb3->count = all - count;
 235   e34 = split_block (bb3, bb3end);
 236   bb4 = e34->dest;
 237   bb4->count = all;
 238
 239   e12->flags &= ~EDGE_FALLTHRU;
 240   e12->flags |= EDGE_FALSE_VALUE;
 241   e12->probability = prob;
 242   e12->count = count;
 243
 244   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
 245   e13->probability = REG_BR_PROB_BASE - prob;
 246   e13->count = all - count;
 247
 248   remove_edge (e23);
 249
 250   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
 251   e24->probability = REG_BR_PROB_BASE;
 252   e24->count = count;
 253
 254   e34->probability = REG_BR_PROB_BASE;
 255   e34->count = all - count;
 256
 257   return tmp2;
 258 }
 259
 260 /* Do transform 1) on INSN if applicable.  */
 261 static bool
 262 tree_divmod_fixed_value_transform (tree stmt)
 263 {
 264   stmt_ann_t ann = get_stmt_ann (stmt);
 265   histogram_value histogram;
 266   enum tree_code code;
 267   gcov_type val, count, all;
 268   tree modify, op, op1, op2, result, value, tree_val;
 269   int prob;
 270
 271   modify = stmt;
 272   if (TREE_CODE (stmt) == RETURN_EXPR
 273       && TREE_OPERAND (stmt, 0)
 274       && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
 275     modify = TREE_OPERAND (stmt, 0);
 276   if (TREE_CODE (modify) != MODIFY_EXPR)
 277     return false;
 278   op = TREE_OPERAND (modify, 1);
 279   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 280     return false;
 281   code = TREE_CODE (op);
 282
 283   if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
 284     return false;
 285
 286   op1 = TREE_OPERAND (op, 0);
 287   op2 = TREE_OPERAND (op, 1);
 288   if (!ann->histograms)
 289     return false;
 290
 291   for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
 292     if (histogram->type == HIST_TYPE_SINGLE_VALUE)
 293       break;
 294
 295   if (!histogram)
 296     return false;
 297
 298   value = histogram->hvalue.value;
 299   val = histogram->hvalue.counters[0];
 300   count = histogram->hvalue.counters[1];
 301   all = histogram->hvalue.counters[2];
 302
 303   /* We require that count is at least half of all; this means
 304      that for the transformation to fire the value must be constant
 305      at least 50% of time (and 75% gives the guarantee of usage).  */
 306   if (simple_cst_equal (op2, value) != 1 || 2 * count < all)
 307     return false;
 308
 309   if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
 310     return false;
 311
 312   /* Compute probability of taking the optimal path.  */
 313   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 314
 315   tree_val = build_int_cst_wide (get_gcov_type (),
 316                                  (unsigned HOST_WIDE_INT) val,
 317                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
 318   result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all);
 319
 320   if (dump_file)
 321     {
 322       fprintf (dump_file, "Div/mod by constant ");
 323       print_generic_expr (dump_file, value, TDF_SLIM);
 324       fprintf (dump_file, "=");
 325       print_generic_expr (dump_file, tree_val, TDF_SLIM);
 326       fprintf (dump_file, " transformation on insn ");
 327       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 328     }
 329
 330   TREE_OPERAND (modify, 1) = result;
 331
 332   return true;
 333 }
 334
 335 /* Generate code for transformation 2 (with OPERATION, operands OP1
 336    and OP2, parent modify-expr STMT and probability of taking the optimal
 337    path PROB, which is equivalent to COUNT/ALL within roundoff error).
 338    This generates the result into a temp and returns
 339    the temp; it does not replace or alter the original STMT.  */
 340 static tree
 341 tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob,
 342                gcov_type count, gcov_type all)
 343 {
 344   tree stmt1, stmt2, stmt3, stmt4;
 345   tree tmp1, tmp2, tmp3;
 346   tree label_decl1 = create_artificial_label ();
 347   tree label_decl2 = create_artificial_label ();
 348   tree label_decl3 = create_artificial_label ();
 349   tree label1, label2, label3;
 350   tree bb1end, bb2end, bb3end;
 351   basic_block bb, bb2, bb3, bb4;
 352   tree optype = TREE_TYPE (operation);
 353   edge e12, e13, e23, e24, e34;
 354   block_stmt_iterator bsi;
 355   tree result = create_tmp_var (optype, "PROF");
 356
 357   bb = bb_for_stmt (stmt);
 358   bsi = bsi_for_stmt (stmt);
 359
 360   tmp1 = create_tmp_var (optype, "PROF");
 361   tmp2 = create_tmp_var (optype, "PROF");
 362   tmp3 = create_tmp_var (optype, "PROF");
 363   stmt1 = build2 (MODIFY_EXPR, optype, tmp1, fold_convert (optype, op2));
 364   stmt2 = build2 (MODIFY_EXPR, optype, tmp2,
 365                     build2 (PLUS_EXPR, optype, op2, integer_minus_one_node));
 366   stmt3 = build2 (MODIFY_EXPR, optype, tmp3,
 367                     build2 (BIT_AND_EXPR, optype, tmp2, tmp1));
 368   stmt4 = build3 (COND_EXPR, void_type_node,
 369             build2 (NE_EXPR, boolean_type_node, tmp3, integer_zero_node),
 370             build1 (GOTO_EXPR, void_type_node, label_decl2),
 371             build1 (GOTO_EXPR, void_type_node, label_decl1));
 372   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 373   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 374   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 375   bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT);
 376   bb1end = stmt4;
 377
 378   /* tmp2 == op2-1 inherited from previous block */
 379   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 380   stmt1 = build2 (MODIFY_EXPR, optype, result,
 381                   build2 (BIT_AND_EXPR, optype, op1, tmp2));
 382   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 383   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 384   bb2end = stmt1;
 385
 386   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 387   stmt1 = build2 (MODIFY_EXPR, optype, result,
 388                   build2 (TREE_CODE (operation), optype, op1, op2));
 389   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 390   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 391   bb3end = stmt1;
 392
 393   label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
 394   bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
 395
 396   /* Fix CFG. */
 397   /* Edge e23 connects bb2 to bb3, etc. */
 398   e12 = split_block (bb, bb1end);
 399   bb2 = e12->dest;
 400   bb2->count = count;
 401   e23 = split_block (bb2, bb2end);
 402   bb3 = e23->dest;
 403   bb3->count = all - count;
 404   e34 = split_block (bb3, bb3end);
 405   bb4 = e34->dest;
 406   bb4->count = all;
 407
 408   e12->flags &= ~EDGE_FALLTHRU;
 409   e12->flags |= EDGE_FALSE_VALUE;
 410   e12->probability = prob;
 411   e12->count = count;
 412
 413   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
 414   e13->probability = REG_BR_PROB_BASE - prob;
 415   e13->count = all - count;
 416
 417   remove_edge (e23);
 418
 419   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
 420   e24->probability = REG_BR_PROB_BASE;
 421   e24->count = count;
 422
 423   e34->probability = REG_BR_PROB_BASE;
 424   e34->count = all - count;
 425
 426   return result;
 427 }
 428
 429 /* Do transform 2) on INSN if applicable.  */
 430 static bool
 431 tree_mod_pow2_value_transform (tree stmt)
 432 {
 433   stmt_ann_t ann = get_stmt_ann (stmt);
 434   histogram_value histogram;
 435   enum tree_code code;
 436   gcov_type count, wrong_values, all;
 437   tree modify, op, op1, op2, result, value;
 438   int prob;
 439
 440   modify = stmt;
 441   if (TREE_CODE (stmt) == RETURN_EXPR
 442       && TREE_OPERAND (stmt, 0)
 443       && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
 444     modify = TREE_OPERAND (stmt, 0);
 445   if (TREE_CODE (modify) != MODIFY_EXPR)
 446     return false;
 447   op = TREE_OPERAND (modify, 1);
 448   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 449     return false;
 450   code = TREE_CODE (op);
 451
 452   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
 453     return false;
 454
 455   op1 = TREE_OPERAND (op, 0);
 456   op2 = TREE_OPERAND (op, 1);
 457   if (!ann->histograms)
 458     return false;
 459
 460   for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
 461     if (histogram->type == HIST_TYPE_POW2)
 462       break;
 463
 464   if (!histogram)
 465     return false;
 466
 467   value = histogram->hvalue.value;
 468   wrong_values = histogram->hvalue.counters[0];
 469   count = histogram->hvalue.counters[1];
 470
 471   /* We require that we hit a power of 2 at least half of all evaluations.  */
 472   if (simple_cst_equal (op2, value) != 1 || count < wrong_values)
 473     return false;
 474
 475   if (dump_file)
 476     {
 477       fprintf (dump_file, "Mod power of 2 transformation on insn ");
 478       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 479     }
 480
 481   /* Compute probability of taking the optimal path.  */
 482   all = count + wrong_values;
 483   if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
 484     return false;
 485
 486   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 487
 488   result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
 489
 490   TREE_OPERAND (modify, 1) = result;
 491
 492   return true;
 493 }
 494
 495 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
 496    and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
 497    support.  Currently only NCOUNTS==0 or 1 is supported and this is
 498    built into this interface.  The probabilities of taking the optimal
 499    paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
 500    COUNT2/ALL respectively within roundoff error).  This generates the
 501    result into a temp and returns the temp; it does not replace or alter
 502    the original STMT.  */
 503 /* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
 504
 505 static tree
 506 tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2,
 507                     int prob1, int prob2, int ncounts,
 508                     gcov_type count1, gcov_type count2, gcov_type all)
 509 {
 510   tree stmt1, stmt2, stmt3;
 511   tree tmp1;
 512   tree label_decl1 = create_artificial_label ();
 513   tree label_decl2 = create_artificial_label ();
 514   tree label_decl3 = create_artificial_label ();
 515   tree label1, label2, label3;
 516   tree bb1end, bb2end = NULL_TREE, bb3end;
 517   basic_block bb, bb2, bb3, bb4;
 518   tree optype = TREE_TYPE (operation);
 519   edge e12, e23 = 0, e24, e34, e14;
 520   block_stmt_iterator bsi;
 521   tree result = create_tmp_var (optype, "PROF");
 522
 523   bb = bb_for_stmt (stmt);
 524   bsi = bsi_for_stmt (stmt);
 525
 526   tmp1 = create_tmp_var (optype, "PROF");
 527   stmt1 = build2 (MODIFY_EXPR, optype, result, op1);
 528   stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2);
 529   stmt3 = build3 (COND_EXPR, void_type_node,
 530             build2 (LT_EXPR, boolean_type_node, result, tmp1),
 531             build1 (GOTO_EXPR, void_type_node, label_decl3),
 532             build1 (GOTO_EXPR, void_type_node,
 533                     ncounts ? label_decl1 : label_decl2));
 534   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 535   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 536   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 537   bb1end = stmt3;
 538
 539   if (ncounts)  /* Assumed to be 0 or 1 */
 540     {
 541       label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 542       stmt1 = build2 (MODIFY_EXPR, optype, result,
 543                       build2 (MINUS_EXPR, optype, result, tmp1));
 544       stmt2 = build3 (COND_EXPR, void_type_node,
 545                 build2 (LT_EXPR, boolean_type_node, result, tmp1),
 546                 build1 (GOTO_EXPR, void_type_node, label_decl3),
 547                 build1 (GOTO_EXPR, void_type_node, label_decl2));
 548       bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 549       bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 550       bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 551       bb2end = stmt2;
 552     }
 553
 554   /* Fallback case. */
 555   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 556   stmt1 = build2 (MODIFY_EXPR, optype, result,
 557                     build2 (TREE_CODE (operation), optype, result, tmp1));
 558   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 559   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 560   bb3end = stmt1;
 561
 562   label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
 563   bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
 564
 565   /* Fix CFG. */
 566   /* Edge e23 connects bb2 to bb3, etc. */
 567   /* However block 3 is optional; if it is not there, references
 568      to 3 really refer to block 2. */
 569   e12 = split_block (bb, bb1end);
 570   bb2 = e12->dest;
 571   bb2->count = all - count1;
 572
 573   if (ncounts)  /* Assumed to be 0 or 1.  */
 574     {
 575       e23 = split_block (bb2, bb2end);
 576       bb3 = e23->dest;
 577       bb3->count = all - count1 - count2;
 578     }
 579
 580   e34 = split_block (ncounts ? bb3 : bb2, bb3end);
 581   bb4 = e34->dest;
 582   bb4->count = all;
 583
 584   e12->flags &= ~EDGE_FALLTHRU;
 585   e12->flags |= EDGE_FALSE_VALUE;
 586   e12->probability = REG_BR_PROB_BASE - prob1;
 587   e12->count = all - count1;
 588
 589   e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
 590   e14->probability = prob1;
 591   e14->count = count1;
 592
 593   if (ncounts)  /* Assumed to be 0 or 1.  */
 594     {
 595       e23->flags &= ~EDGE_FALLTHRU;
 596       e23->flags |= EDGE_FALSE_VALUE;
 597       e23->count = all - count1 - count2;
 598       e23->probability = REG_BR_PROB_BASE - prob2;
 599
 600       e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
 601       e24->probability = prob2;
 602       e24->count = count2;
 603     }
 604
 605   e34->probability = REG_BR_PROB_BASE;
 606   e34->count = all - count1 - count2;
 607
 608   return result;
 609 }
 610
 611 /* Do transforms 3) and 4) on INSN if applicable.  */
 612 static bool
 613 tree_mod_subtract_transform (tree stmt)
 614 {
 615   stmt_ann_t ann = get_stmt_ann (stmt);
 616   histogram_value histogram;
 617   enum tree_code code;
 618   gcov_type count, wrong_values, all;
 619   tree modify, op, op1, op2, result, value;
 620   int prob1, prob2;
 621   unsigned int i;
 622
 623   modify = stmt;
 624   if (TREE_CODE (stmt) == RETURN_EXPR
 625       && TREE_OPERAND (stmt, 0)
 626       && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
 627     modify = TREE_OPERAND (stmt, 0);
 628   if (TREE_CODE (modify) != MODIFY_EXPR)
 629     return false;
 630   op = TREE_OPERAND (modify, 1);
 631   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 632     return false;
 633   code = TREE_CODE (op);
 634
 635   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
 636     return false;
 637
 638   op1 = TREE_OPERAND (op, 0);
 639   op2 = TREE_OPERAND (op, 1);
 640   if (!ann->histograms)
 641     return false;
 642
 643   for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
 644     if (histogram->type == HIST_TYPE_INTERVAL)
 645       break;
 646
 647   if (!histogram)
 648     return false;
 649
 650   value = histogram->hvalue.value;
 651   all = 0;
 652   wrong_values = 0;
 653   for (i = 0; i < histogram->hdata.intvl.steps; i++)
 654     all += histogram->hvalue.counters[i];
 655
 656   wrong_values += histogram->hvalue.counters[i];
 657   wrong_values += histogram->hvalue.counters[i+1];
 658   all += wrong_values;
 659
 660   /* Compute probability of taking the optimal path.  */
 661   if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count))
 662     return false;
 663
 664   /* We require that we use just subtractions in at least 50% of all
 665      evaluations.  */
 666   count = 0;
 667   for (i = 0; i < histogram->hdata.intvl.steps; i++)
 668     {
 669       count += histogram->hvalue.counters[i];
 670       if (count * 2 >= all)
 671         break;
 672     }
 673   if (i == histogram->hdata.intvl.steps)
 674     return false;
 675
 676   if (dump_file)
 677     {
 678       fprintf (dump_file, "Mod subtract transformation on insn ");
 679       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 680     }
 681
 682   /* Compute probability of taking the optimal path(s).  */
 683   prob1 = (histogram->hvalue.counters[0] * REG_BR_PROB_BASE + all / 2) / all;
 684   prob2 = (histogram->hvalue.counters[1] * REG_BR_PROB_BASE + all / 2) / all;
 685
 686   /* In practice, "steps" is always 2.  This interface reflects this,
 687      and will need to be changed if "steps" can change.  */
 688   result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i,
 689                             histogram->hvalue.counters[0],
 690                             histogram->hvalue.counters[1], all);
 691
 692   TREE_OPERAND (modify, 1) = result;
 693
 694   return true;
 695 }
 696
 697 struct value_prof_hooks {
 698   /* Find list of values for which we want to measure histograms.  */
 699   void (*find_values_to_profile) (histogram_values *);
 700
 701   /* Identify and exploit properties of values that are hard to analyze
 702      statically.  See value-prof.c for more detail.  */
 703   bool (*value_profile_transformations) (void);
 704 };
 705 \f
 706 /* Find values inside STMT for that we want to measure histograms for
 707    division/modulo optimization.  */
 708 static void
 709 tree_divmod_values_to_profile (tree stmt, histogram_values *values)
 710 {
 711   tree assign, lhs, rhs, divisor, op0, type;
 712   histogram_value hist;
 713
 714   if (TREE_CODE (stmt) == RETURN_EXPR)
 715     assign = TREE_OPERAND (stmt, 0);
 716   else
 717     assign = stmt;
 718
 719   if (!assign
 720       || TREE_CODE (assign) != MODIFY_EXPR)
 721     return;
 722   lhs = TREE_OPERAND (assign, 0);
 723   type = TREE_TYPE (lhs);
 724   if (!INTEGRAL_TYPE_P (type))
 725     return;
 726
 727   rhs = TREE_OPERAND (assign, 1);
 728   switch (TREE_CODE (rhs))
 729     {
 730     case TRUNC_DIV_EXPR:
 731     case TRUNC_MOD_EXPR:
 732       divisor = TREE_OPERAND (rhs, 1);
 733       op0 = TREE_OPERAND (rhs, 0);
 734
 735       VEC_reserve (histogram_value, heap, *values, 3);
 736
 737       if (is_gimple_reg (divisor))
 738         {
 739           /* Check for the case where the divisor is the same value most
 740              of the time.  */
 741           hist = ggc_alloc (sizeof (*hist));
 742           hist->hvalue.value = divisor;
 743           hist->hvalue.stmt = stmt;
 744           hist->type = HIST_TYPE_SINGLE_VALUE;
 745           VEC_quick_push (histogram_value, *values, hist);
 746         }
 747
 748       /* For mod, check whether it is not often a noop (or replaceable by
 749          a few subtractions).  */
 750       if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
 751           && TYPE_UNSIGNED (type))
 752         {
 753           /* Check for a special case where the divisor is power of 2.  */
 754           hist = ggc_alloc (sizeof (*hist));
 755           hist->hvalue.value = divisor;
 756           hist->hvalue.stmt = stmt;
 757           hist->type = HIST_TYPE_POW2;
 758           VEC_quick_push (histogram_value, *values, hist);
 759
 760           hist = ggc_alloc (sizeof (*hist));
 761           hist->hvalue.stmt = stmt;
 762           hist->hvalue.value
 763                   = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
 764           hist->type = HIST_TYPE_INTERVAL;
 765           hist->hdata.intvl.int_start = 0;
 766           hist->hdata.intvl.steps = 2;
 767           VEC_quick_push (histogram_value, *values, hist);
 768         }
 769       return;
 770
 771     default:
 772       return;
 773     }
 774 }
 775
 776 /* Find values inside STMT for that we want to measure histograms and adds
 777    them to list VALUES.  */
 778
 779 static void
 780 tree_values_to_profile (tree stmt, histogram_values *values)
 781 {
 782   if (flag_value_profile_transformations)
 783     tree_divmod_values_to_profile (stmt, values);
 784 }
 785
 786 static void
 787 tree_find_values_to_profile (histogram_values *values)
 788 {
 789   basic_block bb;
 790   block_stmt_iterator bsi;
 791   unsigned i;
 792   histogram_value hist;
 793
 794   *values = NULL;
 795   FOR_EACH_BB (bb)
 796     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 797       tree_values_to_profile (bsi_stmt (bsi), values);
 798   static_values = *values;
 799
 800   for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
 801     {
 802       switch (hist->type)
 803         {
 804         case HIST_TYPE_INTERVAL:
 805           if (dump_file)
 806             {
 807               fprintf (dump_file, "Interval counter for tree ");
 808               print_generic_expr (dump_file, hist->hvalue.stmt,
 809                                   TDF_SLIM);
 810               fprintf (dump_file, ", range %d -- %d.\n",
 811                      hist->hdata.intvl.int_start,
 812                      (hist->hdata.intvl.int_start
 813                       + hist->hdata.intvl.steps - 1));
 814             }
 815           hist->n_counters = hist->hdata.intvl.steps + 2;
 816           break;
 817
 818         case HIST_TYPE_POW2:
 819           if (dump_file)
 820             {
 821               fprintf (dump_file, "Pow2 counter for tree ");
 822               print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
 823               fprintf (dump_file, ".\n");
 824             }
 825           hist->n_counters = 2;
 826           break;
 827
 828         case HIST_TYPE_SINGLE_VALUE:
 829           if (dump_file)
 830             {
 831               fprintf (dump_file, "Single value counter for tree ");
 832               print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
 833               fprintf (dump_file, ".\n");
 834             }
 835           hist->n_counters = 3;
 836           break;
 837
 838         case HIST_TYPE_CONST_DELTA:
 839           if (dump_file)
 840             {
 841               fprintf (dump_file, "Constant delta counter for tree ");
 842               print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
 843               fprintf (dump_file, ".\n");
 844             }
 845           hist->n_counters = 4;
 846           break;
 847
 848         default:
 849           gcc_unreachable ();
 850         }
 851     }
 852 }
 853
 854 static struct value_prof_hooks tree_value_prof_hooks = {
 855   tree_find_values_to_profile,
 856   tree_value_profile_transformations
 857 };
 858
 859 void
 860 tree_register_value_prof_hooks (void)
 861 {
 862   value_prof_hooks = &tree_value_prof_hooks;
 863   gcc_assert (ir_type ());
 864 }
 865 \f
 866 /* IR-independent entry points.  */
 867 void
 868 find_values_to_profile (histogram_values *values)
 869 {
 870   (value_prof_hooks->find_values_to_profile) (values);
 871 }
 872
 873 bool
 874 value_profile_transformations (void)
 875 {
 876   bool retval = (value_prof_hooks->value_profile_transformations) ();
 877   VEC_free (histogram_value, heap, static_values);
 878   return retval;
 879 }
 880 \f
 881