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