gcc/value-prof.c

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