diff options
Diffstat (limited to 'contrib/gcc/value-prof.c')
| -rw-r--r-- | contrib/gcc/value-prof.c | 874 |
1 files changed, 874 insertions, 0 deletions
diff --git a/contrib/gcc/value-prof.c b/contrib/gcc/value-prof.c new file mode 100644 index 0000000..6c64e3c --- /dev/null +++ b/contrib/gcc/value-prof.c @@ -0,0 +1,874 @@ +/* Transformations based on profile information for values. + Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "rtl.h" +#include "expr.h" +#include "hard-reg-set.h" +#include "basic-block.h" +#include "value-prof.h" +#include "output.h" +#include "flags.h" +#include "insn-config.h" +#include "recog.h" +#include "optabs.h" +#include "regs.h" +#include "ggc.h" +#include "tree-flow.h" +#include "tree-flow-inline.h" +#include "diagnostic.h" +#include "coverage.h" +#include "tree.h" +#include "gcov-io.h" +#include "timevar.h" +#include "tree-pass.h" +#include "toplev.h" + +static struct value_prof_hooks *value_prof_hooks; + +/* In this file value profile based optimizations are placed. Currently the + following optimizations are implemented (for more detailed descriptions + see comments at value_profile_transformations): + + 1) Division/modulo specialization. Provided that we can determine that the + operands of the division have some special properties, we may use it to + produce more effective code. + 2) Speculative prefetching. If we are able to determine that the difference + between addresses accessed by a memory reference is usually constant, we + may add the prefetch instructions. + FIXME: This transformation was removed together with RTL based value + profiling. + + Every such optimization should add its requirements for profiled values to + insn_values_to_profile function. This function is called from branch_prob + in profile.c and the requested values are instrumented by it in the first + compilation with -fprofile-arcs. The optimization may then read the + gathered data in the second compilation with -fbranch-probabilities. + + The measured data is pointed to from the histograms + field of the statement annotation of the instrumented insns. It is + kept as a linked list of struct histogram_value_t's, which contain the + same information as above. */ + + +static tree tree_divmod_fixed_value (tree, tree, tree, tree, + tree, int, gcov_type, gcov_type); +static tree tree_mod_pow2 (tree, tree, tree, tree, int, gcov_type, gcov_type); +static tree tree_mod_subtract (tree, tree, tree, tree, int, int, int, + gcov_type, gcov_type, gcov_type); +static bool tree_divmod_fixed_value_transform (tree); +static bool tree_mod_pow2_value_transform (tree); +static bool tree_mod_subtract_transform (tree); + +/* The overall number of invocations of the counter should match execution count + of basic block. Report it as error rather than internal error as it might + mean that user has misused the profile somehow. */ +static bool +check_counter (tree stmt, const char * name, gcov_type all, gcov_type bb_count) +{ + if (all != bb_count) + { + location_t * locus; + locus = (stmt != NULL && EXPR_HAS_LOCATION (stmt) + ? EXPR_LOCUS (stmt) + : &DECL_SOURCE_LOCATION (current_function_decl)); + error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)", + locus, name, (int)all, (int)bb_count); + return true; + } + return false; +} + +/* Tree based transformations. */ +static bool +tree_value_profile_transformations (void) +{ + basic_block bb; + block_stmt_iterator bsi; + bool changed = false; + + FOR_EACH_BB (bb) + { + /* Ignore cold areas -- we are enlarging the code. */ + if (!maybe_hot_bb_p (bb)) + continue; + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + tree stmt = bsi_stmt (bsi); + stmt_ann_t ann = get_stmt_ann (stmt); + histogram_value th = ann->histograms; + if (!th) + continue; + + if (dump_file) + { + fprintf (dump_file, "Trying transformations on insn "); + print_generic_stmt (dump_file, stmt, TDF_SLIM); + } + + /* Transformations: */ + /* The order of things in this conditional controls which + transformation is used when more than one is applicable. */ + /* It is expected that any code added by the transformations + will be added before the current statement, and that the + current statement remain valid (although possibly + modified) upon return. */ + if (flag_value_profile_transformations + && (tree_mod_subtract_transform (stmt) + || tree_divmod_fixed_value_transform (stmt) + || tree_mod_pow2_value_transform (stmt))) + { + changed = true; + /* Original statement may no longer be in the same block. */ + if (bb != bb_for_stmt (stmt)) + { + bb = bb_for_stmt (stmt); + bsi = bsi_for_stmt (stmt); + } + } + + /* Free extra storage from compute_value_histograms. */ + while (th) + { + free (th->hvalue.counters); + th = th->hvalue.next; + } + ann->histograms = 0; + } + } + + if (changed) + { + counts_to_freqs (); + } + + return changed; +} + +/* Generate code for transformation 1 (with OPERATION, operands OP1 + and OP2, whose value is expected to be VALUE, parent modify-expr STMT and + probability of taking the optimal path PROB, which is equivalent to COUNT/ALL + within roundoff error). This generates the result into a temp and returns + the temp; it does not replace or alter the original STMT. */ +static tree +tree_divmod_fixed_value (tree stmt, tree operation, + tree op1, tree op2, tree value, int prob, gcov_type count, + gcov_type all) +{ + tree stmt1, stmt2, stmt3; + tree tmp1, tmp2, tmpv; + tree label_decl1 = create_artificial_label (); + tree label_decl2 = create_artificial_label (); + tree label_decl3 = create_artificial_label (); + tree label1, label2, label3; + tree bb1end, bb2end, bb3end; + basic_block bb, bb2, bb3, bb4; + tree optype = TREE_TYPE (operation); + edge e12, e13, e23, e24, e34; + block_stmt_iterator bsi; + + bb = bb_for_stmt (stmt); + bsi = bsi_for_stmt (stmt); + + tmpv = create_tmp_var (optype, "PROF"); + tmp1 = create_tmp_var (optype, "PROF"); + stmt1 = build2 (MODIFY_EXPR, optype, tmpv, fold_convert (optype, value)); + stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2); + stmt3 = build3 (COND_EXPR, void_type_node, + build2 (NE_EXPR, boolean_type_node, tmp1, tmpv), + build1 (GOTO_EXPR, void_type_node, label_decl2), + build1 (GOTO_EXPR, void_type_node, label_decl1)); + bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); + bb1end = stmt3; + + tmp2 = create_tmp_var (optype, "PROF"); + label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); + stmt1 = build2 (MODIFY_EXPR, optype, tmp2, + build2 (TREE_CODE (operation), optype, op1, tmpv)); + bsi_insert_before (&bsi, label1, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); + bb2end = stmt1; + + label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); + stmt1 = build2 (MODIFY_EXPR, optype, tmp2, + build2 (TREE_CODE (operation), optype, op1, op2)); + bsi_insert_before (&bsi, label2, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); + bb3end = stmt1; + + label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); + bsi_insert_before (&bsi, label3, BSI_SAME_STMT); + + /* Fix CFG. */ + /* Edge e23 connects bb2 to bb3, etc. */ + e12 = split_block (bb, bb1end); + bb2 = e12->dest; + bb2->count = count; + e23 = split_block (bb2, bb2end); + bb3 = e23->dest; + bb3->count = all - count; + e34 = split_block (bb3, bb3end); + bb4 = e34->dest; + bb4->count = all; + + e12->flags &= ~EDGE_FALLTHRU; + e12->flags |= EDGE_FALSE_VALUE; + e12->probability = prob; + e12->count = count; + + e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE); + e13->probability = REG_BR_PROB_BASE - prob; + e13->count = all - count; + + remove_edge (e23); + + e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); + e24->probability = REG_BR_PROB_BASE; + e24->count = count; + + e34->probability = REG_BR_PROB_BASE; + e34->count = all - count; + + return tmp2; +} + +/* Do transform 1) on INSN if applicable. */ +static bool +tree_divmod_fixed_value_transform (tree stmt) +{ + stmt_ann_t ann = get_stmt_ann (stmt); + histogram_value histogram; + enum tree_code code; + gcov_type val, count, all; + tree modify, op, op1, op2, result, value, tree_val; + int prob; + + modify = stmt; + if (TREE_CODE (stmt) == RETURN_EXPR + && TREE_OPERAND (stmt, 0) + && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) + modify = TREE_OPERAND (stmt, 0); + if (TREE_CODE (modify) != MODIFY_EXPR) + return false; + op = TREE_OPERAND (modify, 1); + if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) + return false; + code = TREE_CODE (op); + + if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR) + return false; + + op1 = TREE_OPERAND (op, 0); + op2 = TREE_OPERAND (op, 1); + if (!ann->histograms) + return false; + + for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) + if (histogram->type == HIST_TYPE_SINGLE_VALUE) + break; + + if (!histogram) + return false; + + value = histogram->hvalue.value; + val = histogram->hvalue.counters[0]; + count = histogram->hvalue.counters[1]; + all = histogram->hvalue.counters[2]; + + /* We require that count is at least half of all; this means + that for the transformation to fire the value must be constant + at least 50% of time (and 75% gives the guarantee of usage). */ + if (simple_cst_equal (op2, value) != 1 || 2 * count < all) + return false; + + if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count)) + return false; + + /* Compute probability of taking the optimal path. */ + prob = (count * REG_BR_PROB_BASE + all / 2) / all; + + tree_val = build_int_cst_wide (get_gcov_type (), + (unsigned HOST_WIDE_INT) val, + val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1); + result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all); + + if (dump_file) + { + fprintf (dump_file, "Div/mod by constant "); + print_generic_expr (dump_file, value, TDF_SLIM); + fprintf (dump_file, "="); + print_generic_expr (dump_file, tree_val, TDF_SLIM); + fprintf (dump_file, " transformation on insn "); + print_generic_stmt (dump_file, stmt, TDF_SLIM); + } + + TREE_OPERAND (modify, 1) = result; + + return true; +} + +/* Generate code for transformation 2 (with OPERATION, operands OP1 + and OP2, parent modify-expr STMT and probability of taking the optimal + path PROB, which is equivalent to COUNT/ALL within roundoff error). + This generates the result into a temp and returns + the temp; it does not replace or alter the original STMT. */ +static tree +tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob, + gcov_type count, gcov_type all) +{ + tree stmt1, stmt2, stmt3, stmt4; + tree tmp2, tmp3; + tree label_decl1 = create_artificial_label (); + tree label_decl2 = create_artificial_label (); + tree label_decl3 = create_artificial_label (); + tree label1, label2, label3; + tree bb1end, bb2end, bb3end; + basic_block bb, bb2, bb3, bb4; + tree optype = TREE_TYPE (operation); + edge e12, e13, e23, e24, e34; + block_stmt_iterator bsi; + tree result = create_tmp_var (optype, "PROF"); + + bb = bb_for_stmt (stmt); + bsi = bsi_for_stmt (stmt); + + tmp2 = create_tmp_var (optype, "PROF"); + tmp3 = create_tmp_var (optype, "PROF"); + stmt2 = build2 (MODIFY_EXPR, optype, tmp2, + build2 (PLUS_EXPR, optype, op2, build_int_cst (optype, -1))); + stmt3 = build2 (MODIFY_EXPR, optype, tmp3, + build2 (BIT_AND_EXPR, optype, tmp2, op2)); + stmt4 = build3 (COND_EXPR, void_type_node, + build2 (NE_EXPR, boolean_type_node, + tmp3, build_int_cst (optype, 0)), + build1 (GOTO_EXPR, void_type_node, label_decl2), + build1 (GOTO_EXPR, void_type_node, label_decl1)); + bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT); + bb1end = stmt4; + + /* tmp2 == op2-1 inherited from previous block */ + label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); + stmt1 = build2 (MODIFY_EXPR, optype, result, + build2 (BIT_AND_EXPR, optype, op1, tmp2)); + bsi_insert_before (&bsi, label1, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); + bb2end = stmt1; + + label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); + stmt1 = build2 (MODIFY_EXPR, optype, result, + build2 (TREE_CODE (operation), optype, op1, op2)); + bsi_insert_before (&bsi, label2, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); + bb3end = stmt1; + + label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); + bsi_insert_before (&bsi, label3, BSI_SAME_STMT); + + /* Fix CFG. */ + /* Edge e23 connects bb2 to bb3, etc. */ + e12 = split_block (bb, bb1end); + bb2 = e12->dest; + bb2->count = count; + e23 = split_block (bb2, bb2end); + bb3 = e23->dest; + bb3->count = all - count; + e34 = split_block (bb3, bb3end); + bb4 = e34->dest; + bb4->count = all; + + e12->flags &= ~EDGE_FALLTHRU; + e12->flags |= EDGE_FALSE_VALUE; + e12->probability = prob; + e12->count = count; + + e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE); + e13->probability = REG_BR_PROB_BASE - prob; + e13->count = all - count; + + remove_edge (e23); + + e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); + e24->probability = REG_BR_PROB_BASE; + e24->count = count; + + e34->probability = REG_BR_PROB_BASE; + e34->count = all - count; + + return result; +} + +/* Do transform 2) on INSN if applicable. */ +static bool +tree_mod_pow2_value_transform (tree stmt) +{ + stmt_ann_t ann = get_stmt_ann (stmt); + histogram_value histogram; + enum tree_code code; + gcov_type count, wrong_values, all; + tree modify, op, op1, op2, result, value; + int prob; + + modify = stmt; + if (TREE_CODE (stmt) == RETURN_EXPR + && TREE_OPERAND (stmt, 0) + && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) + modify = TREE_OPERAND (stmt, 0); + if (TREE_CODE (modify) != MODIFY_EXPR) + return false; + op = TREE_OPERAND (modify, 1); + if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) + return false; + code = TREE_CODE (op); + + if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op))) + return false; + + op1 = TREE_OPERAND (op, 0); + op2 = TREE_OPERAND (op, 1); + if (!ann->histograms) + return false; + + for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) + if (histogram->type == HIST_TYPE_POW2) + break; + + if (!histogram) + return false; + + value = histogram->hvalue.value; + wrong_values = histogram->hvalue.counters[0]; + count = histogram->hvalue.counters[1]; + + /* We require that we hit a power of 2 at least half of all evaluations. */ + if (simple_cst_equal (op2, value) != 1 || count < wrong_values) + return false; + + if (dump_file) + { + fprintf (dump_file, "Mod power of 2 transformation on insn "); + print_generic_stmt (dump_file, stmt, TDF_SLIM); + } + + /* Compute probability of taking the optimal path. */ + all = count + wrong_values; + if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count)) + return false; + + prob = (count * REG_BR_PROB_BASE + all / 2) / all; + + result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all); + + TREE_OPERAND (modify, 1) = result; + + return true; +} + +/* Generate code for transformations 3 and 4 (with OPERATION, operands OP1 + and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to + support. Currently only NCOUNTS==0 or 1 is supported and this is + built into this interface. The probabilities of taking the optimal + paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and + COUNT2/ALL respectively within roundoff error). This generates the + result into a temp and returns the temp; it does not replace or alter + the original STMT. */ +/* FIXME: Generalize the interface to handle NCOUNTS > 1. */ + +static tree +tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2, + int prob1, int prob2, int ncounts, + gcov_type count1, gcov_type count2, gcov_type all) +{ + tree stmt1, stmt2, stmt3; + tree tmp1; + tree label_decl1 = create_artificial_label (); + tree label_decl2 = create_artificial_label (); + tree label_decl3 = create_artificial_label (); + tree label1, label2, label3; + tree bb1end, bb2end = NULL_TREE, bb3end; + basic_block bb, bb2, bb3, bb4; + tree optype = TREE_TYPE (operation); + edge e12, e23 = 0, e24, e34, e14; + block_stmt_iterator bsi; + tree result = create_tmp_var (optype, "PROF"); + + bb = bb_for_stmt (stmt); + bsi = bsi_for_stmt (stmt); + + tmp1 = create_tmp_var (optype, "PROF"); + stmt1 = build2 (MODIFY_EXPR, optype, result, op1); + stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2); + stmt3 = build3 (COND_EXPR, void_type_node, + build2 (LT_EXPR, boolean_type_node, result, tmp1), + build1 (GOTO_EXPR, void_type_node, label_decl3), + build1 (GOTO_EXPR, void_type_node, + ncounts ? label_decl1 : label_decl2)); + bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT); + bb1end = stmt3; + + if (ncounts) /* Assumed to be 0 or 1 */ + { + label1 = build1 (LABEL_EXPR, void_type_node, label_decl1); + stmt1 = build2 (MODIFY_EXPR, optype, result, + build2 (MINUS_EXPR, optype, result, tmp1)); + stmt2 = build3 (COND_EXPR, void_type_node, + build2 (LT_EXPR, boolean_type_node, result, tmp1), + build1 (GOTO_EXPR, void_type_node, label_decl3), + build1 (GOTO_EXPR, void_type_node, label_decl2)); + bsi_insert_before (&bsi, label1, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT); + bb2end = stmt2; + } + + /* Fallback case. */ + label2 = build1 (LABEL_EXPR, void_type_node, label_decl2); + stmt1 = build2 (MODIFY_EXPR, optype, result, + build2 (TREE_CODE (operation), optype, result, tmp1)); + bsi_insert_before (&bsi, label2, BSI_SAME_STMT); + bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT); + bb3end = stmt1; + + label3 = build1 (LABEL_EXPR, void_type_node, label_decl3); + bsi_insert_before (&bsi, label3, BSI_SAME_STMT); + + /* Fix CFG. */ + /* Edge e23 connects bb2 to bb3, etc. */ + /* However block 3 is optional; if it is not there, references + to 3 really refer to block 2. */ + e12 = split_block (bb, bb1end); + bb2 = e12->dest; + bb2->count = all - count1; + + if (ncounts) /* Assumed to be 0 or 1. */ + { + e23 = split_block (bb2, bb2end); + bb3 = e23->dest; + bb3->count = all - count1 - count2; + } + + e34 = split_block (ncounts ? bb3 : bb2, bb3end); + bb4 = e34->dest; + bb4->count = all; + + e12->flags &= ~EDGE_FALLTHRU; + e12->flags |= EDGE_FALSE_VALUE; + e12->probability = REG_BR_PROB_BASE - prob1; + e12->count = all - count1; + + e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE); + e14->probability = prob1; + e14->count = count1; + + if (ncounts) /* Assumed to be 0 or 1. */ + { + e23->flags &= ~EDGE_FALLTHRU; + e23->flags |= EDGE_FALSE_VALUE; + e23->count = all - count1 - count2; + e23->probability = REG_BR_PROB_BASE - prob2; + + e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE); + e24->probability = prob2; + e24->count = count2; + } + + e34->probability = REG_BR_PROB_BASE; + e34->count = all - count1 - count2; + + return result; +} + +/* Do transforms 3) and 4) on INSN if applicable. */ +static bool +tree_mod_subtract_transform (tree stmt) +{ + stmt_ann_t ann = get_stmt_ann (stmt); + histogram_value histogram; + enum tree_code code; + gcov_type count, wrong_values, all; + tree modify, op, op1, op2, result, value; + int prob1, prob2; + unsigned int i; + + modify = stmt; + if (TREE_CODE (stmt) == RETURN_EXPR + && TREE_OPERAND (stmt, 0) + && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) + modify = TREE_OPERAND (stmt, 0); + if (TREE_CODE (modify) != MODIFY_EXPR) + return false; + op = TREE_OPERAND (modify, 1); + if (!INTEGRAL_TYPE_P (TREE_TYPE (op))) + return false; + code = TREE_CODE (op); + + if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op))) + return false; + + op1 = TREE_OPERAND (op, 0); + op2 = TREE_OPERAND (op, 1); + if (!ann->histograms) + return false; + + for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) + if (histogram->type == HIST_TYPE_INTERVAL) + break; + + if (!histogram) + return false; + + value = histogram->hvalue.value; + all = 0; + wrong_values = 0; + for (i = 0; i < histogram->hdata.intvl.steps; i++) + all += histogram->hvalue.counters[i]; + + wrong_values += histogram->hvalue.counters[i]; + wrong_values += histogram->hvalue.counters[i+1]; + all += wrong_values; + + /* Compute probability of taking the optimal path. */ + if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count)) + return false; + + /* We require that we use just subtractions in at least 50% of all + evaluations. */ + count = 0; + for (i = 0; i < histogram->hdata.intvl.steps; i++) + { + count += histogram->hvalue.counters[i]; + if (count * 2 >= all) + break; + } + if (i == histogram->hdata.intvl.steps) + return false; + + if (dump_file) + { + fprintf (dump_file, "Mod subtract transformation on insn "); + print_generic_stmt (dump_file, stmt, TDF_SLIM); + } + + /* Compute probability of taking the optimal path(s). */ + prob1 = (histogram->hvalue.counters[0] * REG_BR_PROB_BASE + all / 2) / all; + prob2 = (histogram->hvalue.counters[1] * REG_BR_PROB_BASE + all / 2) / all; + + /* In practice, "steps" is always 2. This interface reflects this, + and will need to be changed if "steps" can change. */ + result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i, + histogram->hvalue.counters[0], + histogram->hvalue.counters[1], all); + + TREE_OPERAND (modify, 1) = result; + + return true; +} + +struct value_prof_hooks { + /* Find list of values for which we want to measure histograms. */ + void (*find_values_to_profile) (histogram_values *); + + /* Identify and exploit properties of values that are hard to analyze + statically. See value-prof.c for more detail. */ + bool (*value_profile_transformations) (void); +}; + +/* Find values inside STMT for that we want to measure histograms for + division/modulo optimization. */ +static void +tree_divmod_values_to_profile (tree stmt, histogram_values *values) +{ + tree assign, lhs, rhs, divisor, op0, type; + histogram_value hist; + + if (TREE_CODE (stmt) == RETURN_EXPR) + assign = TREE_OPERAND (stmt, 0); + else + assign = stmt; + + if (!assign + || TREE_CODE (assign) != MODIFY_EXPR) + return; + lhs = TREE_OPERAND (assign, 0); + type = TREE_TYPE (lhs); + if (!INTEGRAL_TYPE_P (type)) + return; + + rhs = TREE_OPERAND (assign, 1); + switch (TREE_CODE (rhs)) + { + case TRUNC_DIV_EXPR: + case TRUNC_MOD_EXPR: + divisor = TREE_OPERAND (rhs, 1); + op0 = TREE_OPERAND (rhs, 0); + + VEC_reserve (histogram_value, heap, *values, 3); + + if (is_gimple_reg (divisor)) + { + /* Check for the case where the divisor is the same value most + of the time. */ + hist = ggc_alloc (sizeof (*hist)); + hist->hvalue.value = divisor; + hist->hvalue.stmt = stmt; + hist->type = HIST_TYPE_SINGLE_VALUE; + VEC_quick_push (histogram_value, *values, hist); + } + + /* For mod, check whether it is not often a noop (or replaceable by + a few subtractions). */ + if (TREE_CODE (rhs) == TRUNC_MOD_EXPR + && TYPE_UNSIGNED (type)) + { + /* Check for a special case where the divisor is power of 2. */ + hist = ggc_alloc (sizeof (*hist)); + hist->hvalue.value = divisor; + hist->hvalue.stmt = stmt; + hist->type = HIST_TYPE_POW2; + VEC_quick_push (histogram_value, *values, hist); + + hist = ggc_alloc (sizeof (*hist)); + hist->hvalue.stmt = stmt; + hist->hvalue.value + = build2 (TRUNC_DIV_EXPR, type, op0, divisor); + hist->type = HIST_TYPE_INTERVAL; + hist->hdata.intvl.int_start = 0; + hist->hdata.intvl.steps = 2; + VEC_quick_push (histogram_value, *values, hist); + } + return; + + default: + return; + } +} + +/* Find values inside STMT for that we want to measure histograms and adds + them to list VALUES. */ + +static void +tree_values_to_profile (tree stmt, histogram_values *values) +{ + if (flag_value_profile_transformations) + tree_divmod_values_to_profile (stmt, values); +} + +static void +tree_find_values_to_profile (histogram_values *values) +{ + basic_block bb; + block_stmt_iterator bsi; + unsigned i; + histogram_value hist; + + *values = NULL; + FOR_EACH_BB (bb) + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + tree_values_to_profile (bsi_stmt (bsi), values); + + for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++) + { + switch (hist->type) + { + case HIST_TYPE_INTERVAL: + if (dump_file) + { + fprintf (dump_file, "Interval counter for tree "); + print_generic_expr (dump_file, hist->hvalue.stmt, + TDF_SLIM); + fprintf (dump_file, ", range %d -- %d.\n", + hist->hdata.intvl.int_start, + (hist->hdata.intvl.int_start + + hist->hdata.intvl.steps - 1)); + } + hist->n_counters = hist->hdata.intvl.steps + 2; + break; + + case HIST_TYPE_POW2: + if (dump_file) + { + fprintf (dump_file, "Pow2 counter for tree "); + print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); + fprintf (dump_file, ".\n"); + } + hist->n_counters = 2; + break; + + case HIST_TYPE_SINGLE_VALUE: + if (dump_file) + { + fprintf (dump_file, "Single value counter for tree "); + print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); + fprintf (dump_file, ".\n"); + } + hist->n_counters = 3; + break; + + case HIST_TYPE_CONST_DELTA: + if (dump_file) + { + fprintf (dump_file, "Constant delta counter for tree "); + print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM); + fprintf (dump_file, ".\n"); + } + hist->n_counters = 4; + break; + + default: + gcc_unreachable (); + } + } +} + +static struct value_prof_hooks tree_value_prof_hooks = { + tree_find_values_to_profile, + tree_value_profile_transformations +}; + +void +tree_register_value_prof_hooks (void) +{ + value_prof_hooks = &tree_value_prof_hooks; + gcc_assert (ir_type ()); +} + +/* IR-independent entry points. */ +void +find_values_to_profile (histogram_values *values) +{ + (value_prof_hooks->find_values_to_profile) (values); +} + +bool +value_profile_transformations (void) +{ + return (value_prof_hooks->value_profile_transformations) (); +} + + |
