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 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   tmp2 = create_tmp_var (optype, "PROF");
 361   tmp3 = create_tmp_var (optype, "PROF");
 362   stmt2 = build2 (MODIFY_EXPR, optype, tmp2,
 363                   build2 (PLUS_EXPR, optype, op2, build_int_cst (optype, -1)));
 364   stmt3 = build2 (MODIFY_EXPR, optype, tmp3,
 365                   build2 (BIT_AND_EXPR, optype, tmp2, op2));
 366   stmt4 = build3 (COND_EXPR, void_type_node,
 367                   build2 (NE_EXPR, boolean_type_node,
 368                           tmp3, build_int_cst (optype, 0)),
 369                   build1 (GOTO_EXPR, void_type_node, label_decl2),
 370                   build1 (GOTO_EXPR, void_type_node, label_decl1));
 371   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 372   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 373   bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT);
 374   bb1end = stmt4;
 375
 376   /* tmp2 == op2-1 inherited from previous block */
 377   label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 378   stmt1 = build2 (MODIFY_EXPR, optype, result,
 379                   build2 (BIT_AND_EXPR, optype, op1, tmp2));
 380   bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 381   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 382   bb2end = stmt1;
 383
 384   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 385   stmt1 = build2 (MODIFY_EXPR, optype, result,
 386                   build2 (TREE_CODE (operation), optype, op1, op2));
 387   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 388   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 389   bb3end = stmt1;
 390
 391   label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
 392   bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
 393
 394   /* Fix CFG. */
 395   /* Edge e23 connects bb2 to bb3, etc. */
 396   e12 = split_block (bb, bb1end);
 397   bb2 = e12->dest;
 398   bb2->count = count;
 399   e23 = split_block (bb2, bb2end);
 400   bb3 = e23->dest;
 401   bb3->count = all - count;
 402   e34 = split_block (bb3, bb3end);
 403   bb4 = e34->dest;
 404   bb4->count = all;
 405
 406   e12->flags &= ~EDGE_FALLTHRU;
 407   e12->flags |= EDGE_FALSE_VALUE;
 408   e12->probability = prob;
 409   e12->count = count;
 410
 411   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
 412   e13->probability = REG_BR_PROB_BASE - prob;
 413   e13->count = all - count;
 414
 415   remove_edge (e23);
 416
 417   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
 418   e24->probability = REG_BR_PROB_BASE;
 419   e24->count = count;
 420
 421   e34->probability = REG_BR_PROB_BASE;
 422   e34->count = all - count;
 423
 424   return result;
 425 }
 426
 427 /* Do transform 2) on INSN if applicable.  */
 428 static bool
 429 tree_mod_pow2_value_transform (tree stmt)
 430 {
 431   stmt_ann_t ann = get_stmt_ann (stmt);
 432   histogram_value histogram;
 433   enum tree_code code;
 434   gcov_type count, wrong_values, all;
 435   tree modify, op, op1, op2, result, value;
 436   int prob;
 437
 438   modify = stmt;
 439   if (TREE_CODE (stmt) == RETURN_EXPR
 440       && TREE_OPERAND (stmt, 0)
 441       && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
 442     modify = TREE_OPERAND (stmt, 0);
 443   if (TREE_CODE (modify) != MODIFY_EXPR)
 444     return false;
 445   op = TREE_OPERAND (modify, 1);
 446   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 447     return false;
 448   code = TREE_CODE (op);
 449
 450   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
 451     return false;
 452
 453   op1 = TREE_OPERAND (op, 0);
 454   op2 = TREE_OPERAND (op, 1);
 455   if (!ann->histograms)
 456     return false;
 457
 458   for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
 459     if (histogram->type == HIST_TYPE_POW2)
 460       break;
 461
 462   if (!histogram)
 463     return false;
 464
 465   value = histogram->hvalue.value;
 466   wrong_values = histogram->hvalue.counters[0];
 467   count = histogram->hvalue.counters[1];
 468
 469   /* We require that we hit a power of 2 at least half of all evaluations.  */
 470   if (simple_cst_equal (op2, value) != 1 || count < wrong_values)
 471     return false;
 472
 473   if (dump_file)
 474     {
 475       fprintf (dump_file, "Mod power of 2 transformation on insn ");
 476       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 477     }
 478
 479   /* Compute probability of taking the optimal path.  */
 480   all = count + wrong_values;
 481   if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
 482     return false;
 483
 484   prob = (count * REG_BR_PROB_BASE + all / 2) / all;
 485
 486   result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
 487
 488   TREE_OPERAND (modify, 1) = result;
 489
 490   return true;
 491 }
 492
 493 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
 494    and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
 495    support.  Currently only NCOUNTS==0 or 1 is supported and this is
 496    built into this interface.  The probabilities of taking the optimal
 497    paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
 498    COUNT2/ALL respectively within roundoff error).  This generates the
 499    result into a temp and returns the temp; it does not replace or alter
 500    the original STMT.  */
 501 /* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
 502
 503 static tree
 504 tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2,
 505                     int prob1, int prob2, int ncounts,
 506                     gcov_type count1, gcov_type count2, gcov_type all)
 507 {
 508   tree stmt1, stmt2, stmt3;
 509   tree tmp1;
 510   tree label_decl1 = create_artificial_label ();
 511   tree label_decl2 = create_artificial_label ();
 512   tree label_decl3 = create_artificial_label ();
 513   tree label1, label2, label3;
 514   tree bb1end, bb2end = NULL_TREE, bb3end;
 515   basic_block bb, bb2, bb3, bb4;
 516   tree optype = TREE_TYPE (operation);
 517   edge e12, e23 = 0, e24, e34, e14;
 518   block_stmt_iterator bsi;
 519   tree result = create_tmp_var (optype, "PROF");
 520
 521   bb = bb_for_stmt (stmt);
 522   bsi = bsi_for_stmt (stmt);
 523
 524   tmp1 = create_tmp_var (optype, "PROF");
 525   stmt1 = build2 (MODIFY_EXPR, optype, result, op1);
 526   stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2);
 527   stmt3 = build3 (COND_EXPR, void_type_node,
 528             build2 (LT_EXPR, boolean_type_node, result, tmp1),
 529             build1 (GOTO_EXPR, void_type_node, label_decl3),
 530             build1 (GOTO_EXPR, void_type_node,
 531                     ncounts ? label_decl1 : label_decl2));
 532   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 533   bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 534   bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
 535   bb1end = stmt3;
 536
 537   if (ncounts)  /* Assumed to be 0 or 1 */
 538     {
 539       label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
 540       stmt1 = build2 (MODIFY_EXPR, optype, result,
 541                       build2 (MINUS_EXPR, optype, result, tmp1));
 542       stmt2 = build3 (COND_EXPR, void_type_node,
 543                 build2 (LT_EXPR, boolean_type_node, result, tmp1),
 544                 build1 (GOTO_EXPR, void_type_node, label_decl3),
 545                 build1 (GOTO_EXPR, void_type_node, label_decl2));
 546       bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
 547       bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 548       bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
 549       bb2end = stmt2;
 550     }
 551
 552   /* Fallback case. */
 553   label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
 554   stmt1 = build2 (MODIFY_EXPR, optype, result,
 555                     build2 (TREE_CODE (operation), optype, result, tmp1));
 556   bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
 557   bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
 558   bb3end = stmt1;
 559
 560   label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
 561   bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
 562
 563   /* Fix CFG. */
 564   /* Edge e23 connects bb2 to bb3, etc. */
 565   /* However block 3 is optional; if it is not there, references
 566      to 3 really refer to block 2. */
 567   e12 = split_block (bb, bb1end);
 568   bb2 = e12->dest;
 569   bb2->count = all - count1;
 570
 571   if (ncounts)  /* Assumed to be 0 or 1.  */
 572     {
 573       e23 = split_block (bb2, bb2end);
 574       bb3 = e23->dest;
 575       bb3->count = all - count1 - count2;
 576     }
 577
 578   e34 = split_block (ncounts ? bb3 : bb2, bb3end);
 579   bb4 = e34->dest;
 580   bb4->count = all;
 581
 582   e12->flags &= ~EDGE_FALLTHRU;
 583   e12->flags |= EDGE_FALSE_VALUE;
 584   e12->probability = REG_BR_PROB_BASE - prob1;
 585   e12->count = all - count1;
 586
 587   e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
 588   e14->probability = prob1;
 589   e14->count = count1;
 590
 591   if (ncounts)  /* Assumed to be 0 or 1.  */
 592     {
 593       e23->flags &= ~EDGE_FALLTHRU;
 594       e23->flags |= EDGE_FALSE_VALUE;
 595       e23->count = all - count1 - count2;
 596       e23->probability = REG_BR_PROB_BASE - prob2;
 597
 598       e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
 599       e24->probability = prob2;
 600       e24->count = count2;
 601     }
 602
 603   e34->probability = REG_BR_PROB_BASE;
 604   e34->count = all - count1 - count2;
 605
 606   return result;
 607 }
 608
 609 /* Do transforms 3) and 4) on INSN if applicable.  */
 610 static bool
 611 tree_mod_subtract_transform (tree stmt)
 612 {
 613   stmt_ann_t ann = get_stmt_ann (stmt);
 614   histogram_value histogram;
 615   enum tree_code code;
 616   gcov_type count, wrong_values, all;
 617   tree modify, op, op1, op2, result, value;
 618   int prob1, prob2;
 619   unsigned int i;
 620
 621   modify = stmt;
 622   if (TREE_CODE (stmt) == RETURN_EXPR
 623       && TREE_OPERAND (stmt, 0)
 624       && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
 625     modify = TREE_OPERAND (stmt, 0);
 626   if (TREE_CODE (modify) != MODIFY_EXPR)
 627     return false;
 628   op = TREE_OPERAND (modify, 1);
 629   if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
 630     return false;
 631   code = TREE_CODE (op);
 632
 633   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
 634     return false;
 635
 636   op1 = TREE_OPERAND (op, 0);
 637   op2 = TREE_OPERAND (op, 1);
 638   if (!ann->histograms)
 639     return false;
 640
 641   for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
 642     if (histogram->type == HIST_TYPE_INTERVAL)
 643       break;
 644
 645   if (!histogram)
 646     return false;
 647
 648   value = histogram->hvalue.value;
 649   all = 0;
 650   wrong_values = 0;
 651   for (i = 0; i < histogram->hdata.intvl.steps; i++)
 652     all += histogram->hvalue.counters[i];
 653
 654   wrong_values += histogram->hvalue.counters[i];
 655   wrong_values += histogram->hvalue.counters[i+1];
 656   all += wrong_values;
 657
 658   /* Compute probability of taking the optimal path.  */
 659   if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count))
 660     return false;
 661
 662   /* We require that we use just subtractions in at least 50% of all
 663      evaluations.  */
 664   count = 0;
 665   for (i = 0; i < histogram->hdata.intvl.steps; i++)
 666     {
 667       count += histogram->hvalue.counters[i];
 668       if (count * 2 >= all)
 669         break;
 670     }
 671   if (i == histogram->hdata.intvl.steps)
 672     return false;
 673
 674   if (dump_file)
 675     {
 676       fprintf (dump_file, "Mod subtract transformation on insn ");
 677       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 678     }
 679
 680   /* Compute probability of taking the optimal path(s).  */
 681   prob1 = (histogram->hvalue.counters[0] * REG_BR_PROB_BASE + all / 2) / all;
 682   prob2 = (histogram->hvalue.counters[1] * REG_BR_PROB_BASE + all / 2) / all;
 683
 684   /* In practice, "steps" is always 2.  This interface reflects this,
 685      and will need to be changed if "steps" can change.  */
 686   result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i,
 687                             histogram->hvalue.counters[0],
 688                             histogram->hvalue.counters[1], all);
 689
 690   TREE_OPERAND (modify, 1) = result;
 691
 692   return true;
 693 }
 694
 695 struct value_prof_hooks {
 696   /* Find list of values for which we want to measure histograms.  */
 697   void (*find_values_to_profile) (histogram_values *);
 698
 699   /* Identify and exploit properties of values that are hard to analyze
 700      statically.  See value-prof.c for more detail.  */
 701   bool (*value_profile_transformations) (void);
 702 };
 703 \f
 704 /* Find values inside STMT for that we want to measure histograms for
 705    division/modulo optimization.  */
 706 static void
 707 tree_divmod_values_to_profile (tree stmt, histogram_values *values)
 708 {
 709   tree assign, lhs, rhs, divisor, op0, type;
 710   histogram_value hist;
 711
 712   if (TREE_CODE (stmt) == RETURN_EXPR)
 713     assign = TREE_OPERAND (stmt, 0);
 714   else
 715     assign = stmt;
 716
 717   if (!assign
 718       || TREE_CODE (assign) != MODIFY_EXPR)
 719     return;
 720   lhs = TREE_OPERAND (assign, 0);
 721   type = TREE_TYPE (lhs);
 722   if (!INTEGRAL_TYPE_P (type))
 723     return;
 724
 725   rhs = TREE_OPERAND (assign, 1);
 726   switch (TREE_CODE (rhs))
 727     {
 728     case TRUNC_DIV_EXPR:
 729     case TRUNC_MOD_EXPR:
 730       divisor = TREE_OPERAND (rhs, 1);
 731       op0 = TREE_OPERAND (rhs, 0);
 732
 733       VEC_reserve (histogram_value, heap, *values, 3);
 734
 735       if (is_gimple_reg (divisor))
 736         {
 737           /* Check for the case where the divisor is the same value most
 738              of the time.  */
 739           hist = ggc_alloc (sizeof (*hist));
 740           hist->hvalue.value = divisor;
 741           hist->hvalue.stmt = stmt;
 742           hist->type = HIST_TYPE_SINGLE_VALUE;
 743           VEC_quick_push (histogram_value, *values, hist);
 744         }
 745
 746       /* For mod, check whether it is not often a noop (or replaceable by
 747          a few subtractions).  */
 748       if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
 749           && TYPE_UNSIGNED (type))
 750         {
 751           /* Check for a special case where the divisor is power of 2.  */
 752           hist = ggc_alloc (sizeof (*hist));
 753           hist->hvalue.value = divisor;
 754           hist->hvalue.stmt = stmt;
 755           hist->type = HIST_TYPE_POW2;
 756           VEC_quick_push (histogram_value, *values, hist);
 757
 758           hist = ggc_alloc (sizeof (*hist));
 759           hist->hvalue.stmt = stmt;
 760           hist->hvalue.value
 761                   = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
 762           hist->type = HIST_TYPE_INTERVAL;
 763           hist->hdata.intvl.int_start = 0;
 764           hist->hdata.intvl.steps = 2;
 765           VEC_quick_push (histogram_value, *values, hist);
 766         }
 767       return;
 768
 769     default:
 770       return;
 771     }
 772 }
 773
 774 /* Find values inside STMT for that we want to measure histograms and adds
 775    them to list VALUES.  */
 776
 777 static void
 778 tree_values_to_profile (tree stmt, histogram_values *values)
 779 {
 780   if (flag_value_profile_transformations)
 781     tree_divmod_values_to_profile (stmt, values);
 782 }
 783
 784 static void
 785 tree_find_values_to_profile (histogram_values *values)
 786 {
 787   basic_block bb;
 788   block_stmt_iterator bsi;
 789   unsigned i;
 790   histogram_value hist;
 791
 792   *values = NULL;
 793   FOR_EACH_BB (bb)
 794     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 795       tree_values_to_profile (bsi_stmt (bsi), values);
 796   static_values = *values;
 797
 798   for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
 799     {
 800       switch (hist->type)
 801         {
 802         case HIST_TYPE_INTERVAL:
 803           if (dump_file)
 804             {
 805               fprintf (dump_file, "Interval counter for tree ");
 806               print_generic_expr (dump_file, hist->hvalue.stmt,
 807                                   TDF_SLIM);
 808               fprintf (dump_file, ", range %d -- %d.\n",
 809                      hist->hdata.intvl.int_start,
 810                      (hist->hdata.intvl.int_start
 811                       + hist->hdata.intvl.steps - 1));
 812             }
 813           hist->n_counters = hist->hdata.intvl.steps + 2;
 814           break;
 815
 816         case HIST_TYPE_POW2:
 817           if (dump_file)
 818             {
 819               fprintf (dump_file, "Pow2 counter for tree ");
 820               print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
 821               fprintf (dump_file, ".\n");
 822             }
 823           hist->n_counters = 2;
 824           break;
 825
 826         case HIST_TYPE_SINGLE_VALUE:
 827           if (dump_file)
 828             {
 829               fprintf (dump_file, "Single value counter for tree ");
 830               print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
 831               fprintf (dump_file, ".\n");
 832             }
 833           hist->n_counters = 3;
 834           break;
 835
 836         case HIST_TYPE_CONST_DELTA:
 837           if (dump_file)
 838             {
 839               fprintf (dump_file, "Constant delta counter for tree ");
 840               print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
 841               fprintf (dump_file, ".\n");
 842             }
 843           hist->n_counters = 4;
 844           break;
 845
 846         default:
 847           gcc_unreachable ();
 848         }
 849     }
 850 }
 851
 852 static struct value_prof_hooks tree_value_prof_hooks = {
 853   tree_find_values_to_profile,
 854   tree_value_profile_transformations
 855 };
 856
 857 void
 858 tree_register_value_prof_hooks (void)
 859 {
 860   value_prof_hooks = &tree_value_prof_hooks;
 861   gcc_assert (ir_type ());
 862 }
 863 \f
 864 /* IR-independent entry points.  */
 865 void
 866 find_values_to_profile (histogram_values *values)
 867 {
 868   (value_prof_hooks->find_values_to_profile) (values);
 869 }
 870
 871 bool
 872 value_profile_transformations (void)
 873 {
 874   bool retval = (value_prof_hooks->value_profile_transformations) ();
 875   VEC_free (histogram_value, heap, static_values);
 876   return retval;
 877 }
 878 \f
 879