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