+
+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;
+
+ 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);
+};
+\f
+/* Find values inside STMT for that we want to measure histograms for
+ division/modulo optimization. */
+static void
+gimple_divmod_values_to_profile (gimple stmt, histogram_values *values)
+{
+ tree lhs, divisor, op0, type;
+ histogram_value hist;
+
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ return;
+
+ lhs = gimple_assign_lhs (stmt);
+ type = TREE_TYPE (lhs);
+ if (!INTEGRAL_TYPE_P (type))
+ return;
+
+ switch (gimple_assign_rhs_code (stmt))
+ {
+ case TRUNC_DIV_EXPR:
+ case TRUNC_MOD_EXPR:
+ 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. */
+ 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 (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. */
+ VEC_quick_push (histogram_value, *values,
+ gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
+ stmt, divisor));
+
+ 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);
+ }
+ return;
+
+ default:
+ return;
+ }
+}
+
+/* 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
+gimple_values_to_profile (gimple stmt, histogram_values *values)
+{
+ if (flag_value_profile_transformations)
+ {
+ gimple_divmod_values_to_profile (stmt, values);
+ gimple_stringops_values_to_profile (stmt, values);
+ gimple_indirect_call_to_profile (stmt, values);
+ }
+}
+
+static void
+gimple_find_values_to_profile (histogram_values *values)
+{
+ basic_block bb;
+ gimple_stmt_iterator gsi;
+ unsigned i;
+ histogram_value hist = NULL;
+
+ *values = NULL;
+ FOR_EACH_BB (bb)
+ 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:
+ hist->n_counters = hist->hdata.intvl.steps + 2;
+ break;
+
+ case HIST_TYPE_POW2:
+ hist->n_counters = 2;
+ break;
+
+ case HIST_TYPE_SINGLE_VALUE:
+ hist->n_counters = 3;
+ break;
+
+ case HIST_TYPE_CONST_DELTA:
+ 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 gimple_value_prof_hooks = {
+ gimple_find_values_to_profile,
+ gimple_value_profile_transformations
+};
+
+void
+gimple_register_value_prof_hooks (void)
+{
+ gcc_assert (current_ir_type () == IR_GIMPLE);
+ value_prof_hooks = &gimple_value_prof_hooks;
+}
+\f
+/* 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) ();
+}
+\f