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