X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Fvalue-prof.c;h=b819cdcc06f448025fa24e3f74758ee65e846406;hp=6c64e3cbe271dade378ab486e2641d1c631b8d60;hb=4ce12f0156e9df62da3049b9c4aa7ec7fb7af153;hpb=102a5b984a4f89d0d90253b9eabecea6f2bc920d diff --git a/gcc/value-prof.c b/gcc/value-prof.c index 6c64e3cbe27..b819cdcc06f 100644 --- a/gcc/value-prof.c +++ b/gcc/value-prof.c @@ -1,11 +1,12 @@ /* Transformations based on profile information for values. - Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 + 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 +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -14,9 +15,8 @@ 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. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -37,12 +37,16 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "tree-flow.h" #include "tree-flow-inline.h" #include "diagnostic.h" +#include "tree-pretty-print.h" +#include "gimple-pretty-print.h" #include "coverage.h" #include "tree.h" #include "gcov-io.h" +#include "cgraph.h" #include "timevar.h" #include "tree-pass.h" #include "toplev.h" +#include "pointer-set.h" static struct value_prof_hooks *value_prof_hooks; @@ -59,6 +63,11 @@ static struct value_prof_hooks *value_prof_hooks; FIXME: This transformation was removed together with RTL based value profiling. + 3) Indirect/virtual call specialization. If we can determine most + common function callee in indirect/virtual call. We can use this + information to improve code effectiveness (especially info for + inliner). + 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 @@ -71,60 +80,436 @@ static struct value_prof_hooks *value_prof_hooks; 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); +static tree gimple_divmod_fixed_value (gimple, tree, int, gcov_type, gcov_type); +static tree gimple_mod_pow2 (gimple, int, gcov_type, gcov_type); +static tree gimple_mod_subtract (gimple, int, int, int, gcov_type, gcov_type, + gcov_type); +static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *); +static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *); +static bool gimple_mod_subtract_transform (gimple_stmt_iterator *); +static bool gimple_stringops_transform (gimple_stmt_iterator *); +static bool gimple_ic_transform (gimple); + +/* Allocate histogram value. */ + +static histogram_value +gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED, + enum hist_type type, gimple stmt, tree value) +{ + histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist)); + hist->hvalue.value = value; + hist->hvalue.stmt = stmt; + hist->type = type; + return hist; +} + +/* Hash value for histogram. */ + +static hashval_t +histogram_hash (const void *x) +{ + return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt); +} + +/* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */ + +static int +histogram_eq (const void *x, const void *y) +{ + return ((const_histogram_value) x)->hvalue.stmt == (const_gimple) y; +} + +/* Set histogram for STMT. */ + +static void +set_histogram_value (struct function *fun, gimple stmt, histogram_value hist) +{ + void **loc; + if (!hist && !VALUE_HISTOGRAMS (fun)) + return; + if (!VALUE_HISTOGRAMS (fun)) + VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash, + histogram_eq, NULL); + loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt, + htab_hash_pointer (stmt), + hist ? INSERT : NO_INSERT); + if (!hist) + { + if (loc) + htab_clear_slot (VALUE_HISTOGRAMS (fun), loc); + return; + } + *loc = hist; +} + +/* Get histogram list for STMT. */ + +histogram_value +gimple_histogram_value (struct function *fun, gimple stmt) +{ + if (!VALUE_HISTOGRAMS (fun)) + return NULL; + return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt, + htab_hash_pointer (stmt)); +} + +/* Add histogram for STMT. */ + +void +gimple_add_histogram_value (struct function *fun, gimple stmt, + histogram_value hist) +{ + hist->hvalue.next = gimple_histogram_value (fun, stmt); + set_histogram_value (fun, stmt, hist); +} + + +/* Remove histogram HIST from STMT's histogram list. */ + +void +gimple_remove_histogram_value (struct function *fun, gimple stmt, + histogram_value hist) +{ + histogram_value hist2 = gimple_histogram_value (fun, stmt); + if (hist == hist2) + { + set_histogram_value (fun, stmt, hist->hvalue.next); + } + else + { + while (hist2->hvalue.next != hist) + hist2 = hist2->hvalue.next; + hist2->hvalue.next = hist->hvalue.next; + } + free (hist->hvalue.counters); +#ifdef ENABLE_CHECKING + memset (hist, 0xab, sizeof (*hist)); +#endif + free (hist); +} + + +/* Lookup histogram of type TYPE in the STMT. */ + +histogram_value +gimple_histogram_value_of_type (struct function *fun, gimple stmt, + enum hist_type type) +{ + histogram_value hist; + for (hist = gimple_histogram_value (fun, stmt); hist; + hist = hist->hvalue.next) + if (hist->type == type) + return hist; + return NULL; +} + +/* Dump information about HIST to DUMP_FILE. */ + +static void +dump_histogram_value (FILE *dump_file, histogram_value hist) +{ + switch (hist->type) + { + case HIST_TYPE_INTERVAL: + fprintf (dump_file, "Interval counter range %d -- %d", + hist->hdata.intvl.int_start, + (hist->hdata.intvl.int_start + + hist->hdata.intvl.steps - 1)); + if (hist->hvalue.counters) + { + unsigned int i; + fprintf(dump_file, " ["); + for (i = 0; i < hist->hdata.intvl.steps; i++) + fprintf (dump_file, " %d:"HOST_WIDEST_INT_PRINT_DEC, + hist->hdata.intvl.int_start + i, + (HOST_WIDEST_INT) hist->hvalue.counters[i]); + fprintf (dump_file, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC, + (HOST_WIDEST_INT) hist->hvalue.counters[i]); + } + fprintf (dump_file, ".\n"); + break; + + case HIST_TYPE_POW2: + fprintf (dump_file, "Pow2 counter "); + if (hist->hvalue.counters) + { + fprintf (dump_file, "pow2:"HOST_WIDEST_INT_PRINT_DEC + " nonpow2:"HOST_WIDEST_INT_PRINT_DEC, + (HOST_WIDEST_INT) hist->hvalue.counters[0], + (HOST_WIDEST_INT) hist->hvalue.counters[1]); + } + fprintf (dump_file, ".\n"); + break; + + case HIST_TYPE_SINGLE_VALUE: + fprintf (dump_file, "Single value "); + if (hist->hvalue.counters) + { + fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC + " match:"HOST_WIDEST_INT_PRINT_DEC + " wrong:"HOST_WIDEST_INT_PRINT_DEC, + (HOST_WIDEST_INT) hist->hvalue.counters[0], + (HOST_WIDEST_INT) hist->hvalue.counters[1], + (HOST_WIDEST_INT) hist->hvalue.counters[2]); + } + fprintf (dump_file, ".\n"); + break; + + case HIST_TYPE_AVERAGE: + fprintf (dump_file, "Average value "); + if (hist->hvalue.counters) + { + fprintf (dump_file, "sum:"HOST_WIDEST_INT_PRINT_DEC + " times:"HOST_WIDEST_INT_PRINT_DEC, + (HOST_WIDEST_INT) hist->hvalue.counters[0], + (HOST_WIDEST_INT) hist->hvalue.counters[1]); + } + fprintf (dump_file, ".\n"); + break; + + case HIST_TYPE_IOR: + fprintf (dump_file, "IOR value "); + if (hist->hvalue.counters) + { + fprintf (dump_file, "ior:"HOST_WIDEST_INT_PRINT_DEC, + (HOST_WIDEST_INT) hist->hvalue.counters[0]); + } + fprintf (dump_file, ".\n"); + break; + + case HIST_TYPE_CONST_DELTA: + fprintf (dump_file, "Constant delta "); + if (hist->hvalue.counters) + { + fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC + " match:"HOST_WIDEST_INT_PRINT_DEC + " wrong:"HOST_WIDEST_INT_PRINT_DEC, + (HOST_WIDEST_INT) hist->hvalue.counters[0], + (HOST_WIDEST_INT) hist->hvalue.counters[1], + (HOST_WIDEST_INT) hist->hvalue.counters[2]); + } + fprintf (dump_file, ".\n"); + break; + case HIST_TYPE_INDIR_CALL: + fprintf (dump_file, "Indirect call "); + if (hist->hvalue.counters) + { + fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC + " match:"HOST_WIDEST_INT_PRINT_DEC + " all:"HOST_WIDEST_INT_PRINT_DEC, + (HOST_WIDEST_INT) hist->hvalue.counters[0], + (HOST_WIDEST_INT) hist->hvalue.counters[1], + (HOST_WIDEST_INT) hist->hvalue.counters[2]); + } + fprintf (dump_file, ".\n"); + break; + } +} + +/* Dump all histograms attached to STMT to DUMP_FILE. */ + +void +dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple stmt) +{ + histogram_value hist; + for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next) + dump_histogram_value (dump_file, hist); +} + +/* Remove all histograms associated with STMT. */ + +void +gimple_remove_stmt_histograms (struct function *fun, gimple stmt) +{ + histogram_value val; + while ((val = gimple_histogram_value (fun, stmt)) != NULL) + gimple_remove_histogram_value (fun, stmt, val); +} + +/* Duplicate all histograms associates with OSTMT to STMT. */ + +void +gimple_duplicate_stmt_histograms (struct function *fun, gimple stmt, + struct function *ofun, gimple ostmt) +{ + histogram_value val; + for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next) + { + histogram_value new_val = gimple_alloc_histogram_value (fun, val->type, NULL, NULL); + memcpy (new_val, val, sizeof (*val)); + new_val->hvalue.stmt = stmt; + new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters); + memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters); + gimple_add_histogram_value (fun, stmt, new_val); + } +} + + +/* Move all histograms associated with OSTMT to STMT. */ + +void +gimple_move_stmt_histograms (struct function *fun, gimple stmt, gimple ostmt) +{ + histogram_value val = gimple_histogram_value (fun, ostmt); + if (val) + { + /* The following three statements can't be reordered, + because histogram hashtab relies on stmt field value + for finding the exact slot. */ + set_histogram_value (fun, ostmt, NULL); + for (; val != NULL; val = val->hvalue.next) + val->hvalue.stmt = stmt; + set_histogram_value (fun, stmt, val); + } +} + +static bool error_found = false; + +/* Helper function for verify_histograms. For each histogram reachable via htab + walk verify that it was reached via statement walk. */ + +static int +visit_hist (void **slot, void *data) +{ + struct pointer_set_t *visited = (struct pointer_set_t *) data; + histogram_value hist = *(histogram_value *) slot; + if (!pointer_set_contains (visited, hist)) + { + error ("Dead histogram"); + dump_histogram_value (stderr, hist); + debug_gimple_stmt (hist->hvalue.stmt); + error_found = true; + } + return 1; +} + + +/* Verify sanity of the histograms. */ + +void +verify_histograms (void) +{ + basic_block bb; + gimple_stmt_iterator gsi; + histogram_value hist; + struct pointer_set_t *visited_hists; + + error_found = false; + visited_hists = pointer_set_create (); + FOR_EACH_BB (bb) + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple stmt = gsi_stmt (gsi); + + for (hist = gimple_histogram_value (cfun, stmt); hist; + hist = hist->hvalue.next) + { + if (hist->hvalue.stmt != stmt) + { + error ("Histogram value statement does not correspond to " + "the statement it is associated with"); + debug_gimple_stmt (stmt); + dump_histogram_value (stderr, hist); + error_found = true; + } + pointer_set_insert (visited_hists, hist); + } + } + if (VALUE_HISTOGRAMS (cfun)) + htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists); + pointer_set_destroy (visited_hists); + if (error_found) + internal_error ("verify_histograms failed"); +} + +/* Helper function for verify_histograms. For each histogram reachable via htab + walk verify that it was reached via statement walk. */ + +static int +free_hist (void **slot, void *data ATTRIBUTE_UNUSED) +{ + histogram_value hist = *(histogram_value *) slot; + free (hist->hvalue.counters); +#ifdef ENABLE_CHECKING + memset (hist, 0xab, sizeof (*hist)); +#endif + free (hist); + return 1; +} + +void +free_histograms (void) +{ + if (VALUE_HISTOGRAMS (cfun)) + { + htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL); + htab_delete (VALUE_HISTOGRAMS (cfun)); + VALUE_HISTOGRAMS (cfun) = NULL; + } +} + + +/* 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. */ -/* 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) +check_counter (gimple stmt, const char * name, + gcov_type *count, gcov_type *all, gcov_type bb_count) { - if (all != bb_count) + if (*all != bb_count || *count > *all) { - 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; + location_t locus; + locus = (stmt != NULL) + ? gimple_location (stmt) + : DECL_SOURCE_LOCATION (current_function_decl); + if (flag_profile_correction) + { + inform (locus, "Correcting inconsistent value profile: " + "%s profiler overall count (%d) does not match BB count " + "(%d)", name, (int)*all, (int)bb_count); + *all = bb_count; + if (*count > *all) + *count = *all; + return false; + } + else + { + error_at (locus, "Corrupted value profile: %s " + "profiler overall count (%d) does not match BB count (%d)", + name, (int)*all, (int)bb_count); + return true; + } } + return false; } -/* Tree based transformations. */ + +/* GIMPLE based transformations. */ + static bool -tree_value_profile_transformations (void) +gimple_value_profile_transformations (void) { basic_block bb; - block_stmt_iterator bsi; + gimple_stmt_iterator gsi; 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)) + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - tree stmt = bsi_stmt (bsi); - stmt_ann_t ann = get_stmt_ann (stmt); - histogram_value th = ann->histograms; + gimple stmt = gsi_stmt (gsi); + histogram_value th = gimple_histogram_value (cfun, stmt); if (!th) continue; if (dump_file) { - fprintf (dump_file, "Trying transformations on insn "); - print_generic_stmt (dump_file, stmt, TDF_SLIM); + fprintf (dump_file, "Trying transformations on stmt "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + dump_histograms_for_stmt (cfun, dump_file, stmt); } /* Transformations: */ @@ -135,26 +520,21 @@ tree_value_profile_transformations (void) 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))) + && (gimple_mod_subtract_transform (&gsi) + || gimple_divmod_fixed_value_transform (&gsi) + || gimple_mod_pow2_value_transform (&gsi) + || gimple_stringops_transform (&gsi) + || gimple_ic_transform (stmt))) { + stmt = gsi_stmt (gsi); changed = true; /* Original statement may no longer be in the same block. */ - if (bb != bb_for_stmt (stmt)) + if (bb != gimple_bb (stmt)) { - bb = bb_for_stmt (stmt); - bsi = bsi_for_stmt (stmt); + bb = gimple_bb (stmt); + gsi = gsi_for_stmt (stmt); } } - - /* Free extra storage from compute_value_histograms. */ - while (th) - { - free (th->hvalue.counters); - th = th->hvalue.next; - } - ann->histograms = 0; } } @@ -166,62 +546,57 @@ tree_value_profile_transformations (void) 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. */ + +/* Generate code for transformation 1 (with parent gimple assignment + 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) +gimple_divmod_fixed_value (gimple stmt, tree value, int prob, gcov_type count, + gcov_type all) { - tree stmt1, stmt2, stmt3; + gimple 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; + gimple bb1end, bb2end, bb3end; basic_block bb, bb2, bb3, bb4; - tree optype = TREE_TYPE (operation); + tree optype, op1, op2; edge e12, e13, e23, e24, e34; - block_stmt_iterator bsi; + gimple_stmt_iterator gsi; - bb = bb_for_stmt (stmt); - bsi = bsi_for_stmt (stmt); + gcc_assert (is_gimple_assign (stmt) + && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR + || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR)); + + optype = TREE_TYPE (gimple_assign_lhs (stmt)); + op1 = gimple_assign_rhs1 (stmt); + op2 = gimple_assign_rhs2 (stmt); + + bb = gimple_bb (stmt); + gsi = gsi_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); + stmt1 = gimple_build_assign (tmpv, fold_convert (optype, value)); + stmt2 = gimple_build_assign (tmp1, op2); + stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE); + gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); + gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT); + gsi_insert_before (&gsi, stmt3, GSI_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); + stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2, + op1, tmpv); + gsi_insert_before (&gsi, stmt1, GSI_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); + stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2, + op1, op2); + gsi_insert_before (&gsi, stmt1, GSI_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); @@ -244,7 +619,7 @@ tree_divmod_fixed_value (tree stmt, tree operation, e13->count = all - count; remove_edge (e23); - + e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); e24->probability = REG_BR_PROB_BASE; e24->count = count; @@ -255,41 +630,33 @@ tree_divmod_fixed_value (tree stmt, tree operation, return tmp2; } + /* Do transform 1) on INSN if applicable. */ + static bool -tree_divmod_fixed_value_transform (tree stmt) +gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si) { - 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) + tree result, value, tree_val; + gcov_type prob; + gimple stmt; + + stmt = gsi_stmt (*si); + if (gimple_code (stmt) != GIMPLE_ASSIGN) return false; - op1 = TREE_OPERAND (op, 0); - op2 = TREE_OPERAND (op, 1); - if (!ann->histograms) + if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))) return false; - for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) - if (histogram->type == HIST_TYPE_SINGLE_VALUE) - break; + code = gimple_assign_rhs_code (stmt); + if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR) + return false; + + histogram = gimple_histogram_value_of_type (cfun, stmt, + HIST_TYPE_SINGLE_VALUE); if (!histogram) return false; @@ -297,23 +664,29 @@ tree_divmod_fixed_value_transform (tree stmt) val = histogram->hvalue.counters[0]; count = histogram->hvalue.counters[1]; all = histogram->hvalue.counters[2]; + gimple_remove_histogram_value (cfun, stmt, histogram); /* 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) + if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1 + || 2 * count < all + || optimize_bb_for_size_p (gimple_bb (stmt))) return false; - if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count)) + if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count)) return false; /* Compute probability of taking the optimal path. */ - prob = (count * REG_BR_PROB_BASE + all / 2) / all; + if (all > 0) + prob = (count * REG_BR_PROB_BASE + all / 2) / all; + else + prob = 0; 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); + result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all); if (dump_file) { @@ -322,73 +695,63 @@ tree_divmod_fixed_value_transform (tree stmt) 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); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } - TREE_OPERAND (modify, 1) = result; + gimple_assign_set_rhs_from_tree (si, 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 +/* Generate code for transformation 2 (with parent gimple assign 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) +gimple_mod_pow2 (gimple stmt, int prob, gcov_type count, gcov_type all) { - tree stmt1, stmt2, stmt3, stmt4; + gimple 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; + gimple bb1end, bb2end, bb3end; basic_block bb, bb2, bb3, bb4; - tree optype = TREE_TYPE (operation); + tree optype, op1, op2; edge e12, e13, e23, e24, e34; - block_stmt_iterator bsi; - tree result = create_tmp_var (optype, "PROF"); + gimple_stmt_iterator gsi; + tree result; - bb = bb_for_stmt (stmt); - bsi = bsi_for_stmt (stmt); + gcc_assert (is_gimple_assign (stmt) + && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR); + optype = TREE_TYPE (gimple_assign_lhs (stmt)); + op1 = gimple_assign_rhs1 (stmt); + op2 = gimple_assign_rhs2 (stmt); + + bb = gimple_bb (stmt); + gsi = gsi_for_stmt (stmt); + + result = create_tmp_var (optype, "PROF"); 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); + stmt2 = gimple_build_assign_with_ops (PLUS_EXPR, tmp2, op2, + build_int_cst (optype, -1)); + stmt3 = gimple_build_assign_with_ops (BIT_AND_EXPR, tmp3, tmp2, op2); + stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0), + NULL_TREE, NULL_TREE); + gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT); + gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT); + gsi_insert_before (&gsi, stmt4, GSI_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); + /* tmp2 == op2-1 inherited from previous block. */ + stmt1 = gimple_build_assign_with_ops (BIT_AND_EXPR, result, op1, tmp2); + gsi_insert_before (&gsi, stmt1, GSI_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); + stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result, + op1, op2); + gsi_insert_before (&gsi, stmt1, GSI_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); @@ -411,7 +774,7 @@ tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob, e13->count = all - count; remove_edge (e23); - + e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); e24->probability = REG_BR_PROB_BASE; e24->count = count; @@ -424,39 +787,29 @@ tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob, /* Do transform 2) on INSN if applicable. */ static bool -tree_mod_pow2_value_transform (tree stmt) +gimple_mod_pow2_value_transform (gimple_stmt_iterator *si) { - 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))) + tree lhs_type, result, value; + gcov_type prob; + gimple stmt; + + stmt = gsi_stmt (*si); + if (gimple_code (stmt) != GIMPLE_ASSIGN) return false; - op1 = TREE_OPERAND (op, 0); - op2 = TREE_OPERAND (op, 1); - if (!ann->histograms) + lhs_type = TREE_TYPE (gimple_assign_lhs (stmt)); + if (!INTEGRAL_TYPE_P (lhs_type)) return false; - for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) - if (histogram->type == HIST_TYPE_POW2) - break; + code = gimple_assign_rhs_code (stmt); + + if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type)) + return false; + histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2); if (!histogram) return false; @@ -464,100 +817,95 @@ tree_mod_pow2_value_transform (tree stmt) wrong_values = histogram->hvalue.counters[0]; count = histogram->hvalue.counters[1]; + gimple_remove_histogram_value (cfun, stmt, histogram); + /* 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) + if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1 + || count < wrong_values + || optimize_bb_for_size_p (gimple_bb (stmt))) return false; if (dump_file) { fprintf (dump_file, "Mod power of 2 transformation on insn "); - print_generic_stmt (dump_file, stmt, TDF_SLIM); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } /* Compute probability of taking the optimal path. */ all = count + wrong_values; - if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count)) + + if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count)) return false; - prob = (count * REG_BR_PROB_BASE + all / 2) / all; + if (all > 0) + prob = (count * REG_BR_PROB_BASE + all / 2) / all; + else + prob = 0; - result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all); + result = gimple_mod_pow2 (stmt, prob, count, all); - TREE_OPERAND (modify, 1) = result; + gimple_assign_set_rhs_from_tree (si, 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 +/* Generate code for transformations 3 and 4 (with parent gimple assign 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) +gimple_mod_subtract (gimple stmt, int prob1, int prob2, int ncounts, + gcov_type count1, gcov_type count2, gcov_type all) { - tree stmt1, stmt2, stmt3; + gimple 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; + gimple bb1end, bb2end = NULL, bb3end; basic_block bb, bb2, bb3, bb4; - tree optype = TREE_TYPE (operation); + tree optype, op1, op2; edge e12, e23 = 0, e24, e34, e14; - block_stmt_iterator bsi; - tree result = create_tmp_var (optype, "PROF"); + gimple_stmt_iterator gsi; + tree result; + + gcc_assert (is_gimple_assign (stmt) + && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR); - bb = bb_for_stmt (stmt); - bsi = bsi_for_stmt (stmt); + optype = TREE_TYPE (gimple_assign_lhs (stmt)); + op1 = gimple_assign_rhs1 (stmt); + op2 = gimple_assign_rhs2 (stmt); + bb = gimple_bb (stmt); + gsi = gsi_for_stmt (stmt); + + result = create_tmp_var (optype, "PROF"); 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); + stmt1 = gimple_build_assign (result, op1); + stmt2 = gimple_build_assign (tmp1, op2); + stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE); + gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); + gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT); + gsi_insert_before (&gsi, stmt3, GSI_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); + stmt1 = gimple_build_assign_with_ops (MINUS_EXPR, result, result, tmp1); + stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE); + gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); + gsi_insert_before (&gsi, stmt2, GSI_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); + stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result, + result, tmp1); + gsi_insert_before (&gsi, stmt1, GSI_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 @@ -565,7 +913,7 @@ tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2, 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); @@ -604,46 +952,38 @@ tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2, return result; } -/* Do transforms 3) and 4) on INSN if applicable. */ + +/* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */ + static bool -tree_mod_subtract_transform (tree stmt) +gimple_mod_subtract_transform (gimple_stmt_iterator *si) { - 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))) + tree lhs_type, result; + gcov_type prob1, prob2; + unsigned int i, steps; + gcov_type count1, count2; + gimple stmt; + + stmt = gsi_stmt (*si); + if (gimple_code (stmt) != GIMPLE_ASSIGN) return false; - op1 = TREE_OPERAND (op, 0); - op2 = TREE_OPERAND (op, 1); - if (!ann->histograms) + lhs_type = TREE_TYPE (gimple_assign_lhs (stmt)); + if (!INTEGRAL_TYPE_P (lhs_type)) return false; - for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next) - if (histogram->type == HIST_TYPE_INTERVAL) - break; + code = gimple_assign_rhs_code (stmt); + + if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type)) + return false; + histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL); if (!histogram) return false; - value = histogram->hvalue.value; all = 0; wrong_values = 0; for (i = 0; i < histogram->hdata.intvl.steps; i++) @@ -651,11 +991,22 @@ tree_mod_subtract_transform (tree stmt) wrong_values += histogram->hvalue.counters[i]; wrong_values += histogram->hvalue.counters[i+1]; + steps = histogram->hdata.intvl.steps; all += wrong_values; + count1 = histogram->hvalue.counters[0]; + count2 = histogram->hvalue.counters[1]; /* Compute probability of taking the optimal path. */ - if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count)) - return false; + if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count)) + { + gimple_remove_histogram_value (cfun, stmt, histogram); + return false; + } + + if (flag_profile_correction && count1 + count2 > all) + all = count1 + count2; + + gcc_assert (count1 + count2 <= all); /* We require that we use just subtractions in at least 50% of all evaluations. */ @@ -666,98 +1017,539 @@ tree_mod_subtract_transform (tree stmt) if (count * 2 >= all) break; } - if (i == histogram->hdata.intvl.steps) + if (i == steps + || optimize_bb_for_size_p (gimple_bb (stmt))) return false; + gimple_remove_histogram_value (cfun, stmt, histogram); if (dump_file) { fprintf (dump_file, "Mod subtract transformation on insn "); - print_generic_stmt (dump_file, stmt, TDF_SLIM); + print_gimple_stmt (dump_file, stmt, 0, 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; + if (all > 0) + { + prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all; + prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all; + } + else + { + prob1 = prob2 = 0; + } /* 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); + result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all); + + gimple_assign_set_rhs_from_tree (si, result); + + return true; +} + +static struct cgraph_node** pid_map = NULL; + +/* Initialize map of pids (pid -> cgraph node) */ + +static void +init_pid_map (void) +{ + struct cgraph_node *n; + + if (pid_map != NULL) + return; - TREE_OPERAND (modify, 1) = result; + pid_map = XCNEWVEC (struct cgraph_node*, cgraph_max_pid); + + for (n = cgraph_nodes; n; n = n->next) + { + if (n->pid != -1) + pid_map [n->pid] = n; + } +} + +/* Return cgraph node for function with pid */ + +static inline struct cgraph_node* +find_func_by_pid (int pid) +{ + init_pid_map (); + + return pid_map [pid]; +} + +/* Do transformation + + if (actual_callee_address == address_of_most_common_function/method) + do direct call + else + old call + */ + +static gimple +gimple_ic (gimple icall_stmt, struct cgraph_node *direct_call, + int prob, gcov_type count, gcov_type all) +{ + gimple dcall_stmt, load_stmt, cond_stmt; + tree tmp1, tmpv, tmp; + basic_block cond_bb, dcall_bb, icall_bb, join_bb; + tree optype = build_pointer_type (void_type_node); + edge e_cd, e_ci, e_di, e_dj, e_ij; + gimple_stmt_iterator gsi; + int lp_nr; + + cond_bb = gimple_bb (icall_stmt); + gsi = gsi_for_stmt (icall_stmt); + + tmpv = create_tmp_var (optype, "PROF"); + tmp1 = create_tmp_var (optype, "PROF"); + tmp = unshare_expr (gimple_call_fn (icall_stmt)); + load_stmt = gimple_build_assign (tmpv, tmp); + gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT); + + tmp = fold_convert (optype, build_addr (direct_call->decl, + current_function_decl)); + load_stmt = gimple_build_assign (tmp1, tmp); + gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT); + + cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE); + gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); + + dcall_stmt = gimple_copy (icall_stmt); + gimple_call_set_fndecl (dcall_stmt, direct_call->decl); + gsi_insert_before (&gsi, dcall_stmt, GSI_SAME_STMT); + + /* Fix CFG. */ + /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */ + e_cd = split_block (cond_bb, cond_stmt); + dcall_bb = e_cd->dest; + dcall_bb->count = count; + + e_di = split_block (dcall_bb, dcall_stmt); + icall_bb = e_di->dest; + icall_bb->count = all - count; + + e_ij = split_block (icall_bb, icall_stmt); + join_bb = e_ij->dest; + join_bb->count = all; + + e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE; + e_cd->probability = prob; + e_cd->count = count; + + e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE); + e_ci->probability = REG_BR_PROB_BASE - prob; + e_ci->count = all - count; + + remove_edge (e_di); + + e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU); + e_dj->probability = REG_BR_PROB_BASE; + e_dj->count = count; + + e_ij->probability = REG_BR_PROB_BASE; + e_ij->count = all - count; + + /* Fix eh edges */ + lp_nr = lookup_stmt_eh_lp (icall_stmt); + if (lp_nr != 0) + { + if (stmt_could_throw_p (dcall_stmt)) + { + add_stmt_to_eh_lp (dcall_stmt, lp_nr); + make_eh_edges (dcall_stmt); + } + + gcc_assert (stmt_could_throw_p (icall_stmt)); + make_eh_edges (icall_stmt); + + /* The old EH edges are sill on the join BB, purge them. */ + gimple_purge_dead_eh_edges (join_bb); + } + + return dcall_stmt; +} + +/* + For every checked indirect/virtual call determine if most common pid of + function/class method has probability more than 50%. If yes modify code of + this call to: + */ + +static bool +gimple_ic_transform (gimple stmt) +{ + histogram_value histogram; + gcov_type val, count, all, bb_all; + gcov_type prob; + tree callee; + gimple modify; + struct cgraph_node *direct_call; + + if (gimple_code (stmt) != GIMPLE_CALL) + return false; + + callee = gimple_call_fn (stmt); + + if (TREE_CODE (callee) == FUNCTION_DECL) + return false; + + histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL); + if (!histogram) + return false; + + val = histogram->hvalue.counters [0]; + count = histogram->hvalue.counters [1]; + all = histogram->hvalue.counters [2]; + gimple_remove_histogram_value (cfun, stmt, histogram); + + if (4 * count <= 3 * all) + return false; + + bb_all = gimple_bb (stmt)->count; + /* The order of CHECK_COUNTER calls is important - + since check_counter can correct the third parameter + and we want to make count <= all <= bb_all. */ + if ( check_counter (stmt, "ic", &all, &bb_all, bb_all) + || check_counter (stmt, "ic", &count, &all, all)) + return false; + + if (all > 0) + prob = (count * REG_BR_PROB_BASE + all / 2) / all; + else + prob = 0; + direct_call = find_func_by_pid ((int)val); + + if (direct_call == NULL) + return false; + + modify = gimple_ic (stmt, direct_call, prob, count, all); + + if (dump_file) + { + fprintf (dump_file, "Indirect call -> direct call "); + print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM); + fprintf (dump_file, "=> "); + print_generic_expr (dump_file, direct_call->decl, TDF_SLIM); + fprintf (dump_file, " transformation on insn "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + fprintf (dump_file, " to "); + print_gimple_stmt (dump_file, modify, 0, TDF_SLIM); + fprintf (dump_file, "hist->count "HOST_WIDEST_INT_PRINT_DEC + " hist->all "HOST_WIDEST_INT_PRINT_DEC"\n", count, all); + } + + return true; +} + +/* Return true if the stringop CALL with FNDECL shall be profiled. + SIZE_ARG be set to the argument index for the size of the string + operation. +*/ +static bool +interesting_stringop_to_profile_p (tree fndecl, gimple call, int *size_arg) +{ + enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl); + + if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY + && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO) + return false; + + switch (fcode) + { + case BUILT_IN_MEMCPY: + case BUILT_IN_MEMPCPY: + *size_arg = 2; + return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE, + INTEGER_TYPE, VOID_TYPE); + case BUILT_IN_MEMSET: + *size_arg = 2; + return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE, + INTEGER_TYPE, VOID_TYPE); + case BUILT_IN_BZERO: + *size_arg = 1; + return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE, + VOID_TYPE); + default: + gcc_unreachable (); + } +} + +/* Convert stringop (..., vcall_size) + into + if (vcall_size == icall_size) + stringop (..., icall_size); + else + stringop (..., vcall_size); + assuming we'll propagate a true constant into ICALL_SIZE later. */ + +static void +gimple_stringop_fixed_value (gimple vcall_stmt, tree icall_size, int prob, + gcov_type count, gcov_type all) +{ + gimple tmp_stmt, cond_stmt, icall_stmt; + tree tmp1, tmpv, vcall_size, optype; + basic_block cond_bb, icall_bb, vcall_bb, join_bb; + edge e_ci, e_cv, e_iv, e_ij, e_vj; + gimple_stmt_iterator gsi; + tree fndecl; + int size_arg; + + fndecl = gimple_call_fndecl (vcall_stmt); + if (!interesting_stringop_to_profile_p (fndecl, vcall_stmt, &size_arg)) + gcc_unreachable(); + + cond_bb = gimple_bb (vcall_stmt); + gsi = gsi_for_stmt (vcall_stmt); + + vcall_size = gimple_call_arg (vcall_stmt, size_arg); + optype = TREE_TYPE (vcall_size); + + tmpv = create_tmp_var (optype, "PROF"); + tmp1 = create_tmp_var (optype, "PROF"); + tmp_stmt = gimple_build_assign (tmpv, fold_convert (optype, icall_size)); + gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT); + + tmp_stmt = gimple_build_assign (tmp1, vcall_size); + gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT); + + cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE); + gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); + + icall_stmt = gimple_copy (vcall_stmt); + gimple_call_set_arg (icall_stmt, size_arg, icall_size); + gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT); + + /* Fix CFG. */ + /* Edge e_ci connects cond_bb to icall_bb, etc. */ + e_ci = split_block (cond_bb, cond_stmt); + icall_bb = e_ci->dest; + icall_bb->count = count; + + e_iv = split_block (icall_bb, icall_stmt); + vcall_bb = e_iv->dest; + vcall_bb->count = all - count; + + e_vj = split_block (vcall_bb, vcall_stmt); + join_bb = e_vj->dest; + join_bb->count = all; + + e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE; + e_ci->probability = prob; + e_ci->count = count; + + e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE); + e_cv->probability = REG_BR_PROB_BASE - prob; + e_cv->count = all - count; + + remove_edge (e_iv); + + e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU); + e_ij->probability = REG_BR_PROB_BASE; + e_ij->count = count; + + e_vj->probability = REG_BR_PROB_BASE; + e_vj->count = all - count; + + /* Because these are all string op builtins, they're all nothrow. */ + gcc_assert (!stmt_could_throw_p (vcall_stmt)); + gcc_assert (!stmt_could_throw_p (icall_stmt)); +} + +/* Find values inside STMT for that we want to measure histograms for + division/modulo optimization. */ +static bool +gimple_stringops_transform (gimple_stmt_iterator *gsi) +{ + gimple stmt = gsi_stmt (*gsi); + tree fndecl; + tree blck_size; + enum built_in_function fcode; + histogram_value histogram; + gcov_type count, all, val; + tree dest, src; + unsigned int dest_align, src_align; + gcov_type prob; + tree tree_val; + int size_arg; + + if (gimple_code (stmt) != GIMPLE_CALL) + return false; + fndecl = gimple_call_fndecl (stmt); + if (!fndecl) + return false; + fcode = DECL_FUNCTION_CODE (fndecl); + if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg)) + return false; + + blck_size = gimple_call_arg (stmt, size_arg); + if (TREE_CODE (blck_size) == INTEGER_CST) + return false; + + histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE); + if (!histogram) + return false; + val = histogram->hvalue.counters[0]; + count = histogram->hvalue.counters[1]; + all = histogram->hvalue.counters[2]; + gimple_remove_histogram_value (cfun, stmt, histogram); + /* 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 80% of time. */ + if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt))) + return false; + if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count)) + return false; + if (all > 0) + prob = (count * REG_BR_PROB_BASE + all / 2) / all; + else + prob = 0; + dest = gimple_call_arg (stmt, 0); + dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT); + switch (fcode) + { + case BUILT_IN_MEMCPY: + case BUILT_IN_MEMPCPY: + src = gimple_call_arg (stmt, 1); + src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT); + if (!can_move_by_pieces (val, MIN (dest_align, src_align))) + return false; + break; + case BUILT_IN_MEMSET: + if (!can_store_by_pieces (val, builtin_memset_read_str, + gimple_call_arg (stmt, 1), + dest_align, true)) + return false; + break; + case BUILT_IN_BZERO: + if (!can_store_by_pieces (val, builtin_memset_read_str, + integer_zero_node, + dest_align, true)) + return false; + break; + default: + gcc_unreachable (); + } + tree_val = build_int_cst_wide (get_gcov_type (), + (unsigned HOST_WIDE_INT) val, + val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1); + if (dump_file) + { + fprintf (dump_file, "Single value %i stringop transformation on ", + (int)val); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + gimple_stringop_fixed_value (stmt, tree_val, prob, count, all); return true; } +void +stringop_block_profile (gimple stmt, unsigned int *expected_align, + HOST_WIDE_INT *expected_size) +{ + histogram_value histogram; + histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE); + if (!histogram) + *expected_size = -1; + else if (!histogram->hvalue.counters[1]) + { + *expected_size = -1; + gimple_remove_histogram_value (cfun, stmt, histogram); + } + else + { + gcov_type size; + size = ((histogram->hvalue.counters[0] + + histogram->hvalue.counters[1] / 2) + / histogram->hvalue.counters[1]); + /* Even if we can hold bigger value in SIZE, INT_MAX + is safe "infinity" for code generation strategies. */ + if (size > INT_MAX) + size = INT_MAX; + *expected_size = size; + gimple_remove_histogram_value (cfun, stmt, histogram); + } + histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR); + if (!histogram) + *expected_align = 0; + else if (!histogram->hvalue.counters[0]) + { + gimple_remove_histogram_value (cfun, stmt, histogram); + *expected_align = 0; + } + else + { + gcov_type count; + int alignment; + + count = histogram->hvalue.counters[0]; + alignment = 1; + while (!(count & alignment) + && (alignment * 2 * BITS_PER_UNIT)) + alignment <<= 1; + *expected_align = alignment * BITS_PER_UNIT; + gimple_remove_histogram_value (cfun, stmt, histogram); + } +} + 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); + 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) +gimple_divmod_values_to_profile (gimple stmt, histogram_values *values) { - tree assign, lhs, rhs, divisor, op0, type; + tree lhs, 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) + if (gimple_code (stmt) != GIMPLE_ASSIGN) return; - lhs = TREE_OPERAND (assign, 0); + + lhs = gimple_assign_lhs (stmt); type = TREE_TYPE (lhs); if (!INTEGRAL_TYPE_P (type)) return; - rhs = TREE_OPERAND (assign, 1); - switch (TREE_CODE (rhs)) + switch (gimple_assign_rhs_code (stmt)) { case TRUNC_DIV_EXPR: case TRUNC_MOD_EXPR: - divisor = TREE_OPERAND (rhs, 1); - op0 = TREE_OPERAND (rhs, 0); + divisor = gimple_assign_rhs2 (stmt); + op0 = gimple_assign_rhs1 (stmt); 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); - } + /* Check for the case where the divisor is the same value most + of the time. */ + VEC_quick_push (histogram_value, *values, + gimple_alloc_histogram_value (cfun, + HIST_TYPE_SINGLE_VALUE, + stmt, divisor)); /* For mod, check whether it is not often a noop (or replaceable by a few subtractions). */ - if (TREE_CODE (rhs) == TRUNC_MOD_EXPR + if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR && TYPE_UNSIGNED (type)) { + tree val; /* 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); + VEC_quick_push (histogram_value, *values, + gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2, + stmt, divisor)); - hist = ggc_alloc (sizeof (*hist)); - hist->hvalue.stmt = stmt; - hist->hvalue.value - = build2 (TRUNC_DIV_EXPR, type, op0, divisor); - hist->type = HIST_TYPE_INTERVAL; + val = build2 (TRUNC_DIV_EXPR, type, op0, divisor); + hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL, + stmt, val); hist->hdata.intvl.int_start = 0; hist->hdata.intvl.steps = 2; VEC_quick_push (histogram_value, *values, hist); @@ -769,93 +1561,147 @@ tree_divmod_values_to_profile (tree stmt, histogram_values *values) } } +/* Find calls inside STMT for that we want to measure histograms for + indirect/virtual call optimization. */ + +static void +gimple_indirect_call_to_profile (gimple stmt, histogram_values *values) +{ + tree callee; + + if (gimple_code (stmt) != GIMPLE_CALL + || gimple_call_fndecl (stmt) != NULL_TREE) + return; + + callee = gimple_call_fn (stmt); + + VEC_reserve (histogram_value, heap, *values, 3); + + VEC_quick_push (histogram_value, *values, + gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL, + stmt, callee)); + + return; +} + +/* Find values inside STMT for that we want to measure histograms for + string operations. */ +static void +gimple_stringops_values_to_profile (gimple stmt, histogram_values *values) +{ + tree fndecl; + tree blck_size; + tree dest; + int size_arg; + + if (gimple_code (stmt) != GIMPLE_CALL) + return; + fndecl = gimple_call_fndecl (stmt); + if (!fndecl) + return; + + if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg)) + return; + + dest = gimple_call_arg (stmt, 0); + blck_size = gimple_call_arg (stmt, size_arg); + + if (TREE_CODE (blck_size) != INTEGER_CST) + { + VEC_safe_push (histogram_value, heap, *values, + gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE, + stmt, blck_size)); + VEC_safe_push (histogram_value, heap, *values, + gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE, + stmt, blck_size)); + } + if (TREE_CODE (blck_size) != INTEGER_CST) + VEC_safe_push (histogram_value, heap, *values, + gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR, + stmt, dest)); +} + /* 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) +gimple_values_to_profile (gimple stmt, histogram_values *values) { if (flag_value_profile_transformations) - tree_divmod_values_to_profile (stmt, values); + { + gimple_divmod_values_to_profile (stmt, values); + gimple_stringops_values_to_profile (stmt, values); + gimple_indirect_call_to_profile (stmt, values); + } } static void -tree_find_values_to_profile (histogram_values *values) +gimple_find_values_to_profile (histogram_values *values) { basic_block bb; - block_stmt_iterator bsi; + gimple_stmt_iterator gsi; unsigned i; - histogram_value hist; + histogram_value hist = NULL; *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 (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + gimple_values_to_profile (gsi_stmt (gsi), 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; + case HIST_TYPE_INDIR_CALL: + hist->n_counters = 3; + break; + + case HIST_TYPE_AVERAGE: + hist->n_counters = 2; + break; + + case HIST_TYPE_IOR: + hist->n_counters = 1; + break; + default: gcc_unreachable (); } + if (dump_file) + { + fprintf (dump_file, "Stmt "); + print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM); + dump_histogram_value (dump_file, hist); + } } } -static struct value_prof_hooks tree_value_prof_hooks = { - tree_find_values_to_profile, - tree_value_profile_transformations +static struct value_prof_hooks gimple_value_prof_hooks = { + gimple_find_values_to_profile, + gimple_value_profile_transformations }; void -tree_register_value_prof_hooks (void) +gimple_register_value_prof_hooks (void) { - value_prof_hooks = &tree_value_prof_hooks; - gcc_assert (ir_type ()); + gcc_assert (current_ir_type () == IR_GIMPLE); + value_prof_hooks = &gimple_value_prof_hooks; } /* IR-independent entry points. */ @@ -871,4 +1717,3 @@ value_profile_transformations (void) return (value_prof_hooks->value_profile_transformations) (); } -