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