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