/* Interprocedural constant propagation
- Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
+ Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
Free Software Foundation, Inc.
Contributed by Razya Ladelsky <RAZYA@il.ibm.com>
with the value 3.
The algorithm used is based on "Interprocedural Constant Propagation", by
- Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg
+ David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86, pg
152-161
The optimization is divided into three stages:
#include "tree-inline.h"
#include "fibheap.h"
#include "params.h"
+#include "ipa-inline.h"
/* Number of functions identified as candidates for cloning. When not cloning
we can simplify iterate stage not forcing it to go through the decision
res->constant = lat1->constant;
}
-/* Return the lattice corresponding to the Ith formal parameter of the function
- described by INFO. */
-static inline struct ipcp_lattice *
-ipcp_get_lattice (struct ipa_node_params *info, int i)
-{
- return &(info->params[i].ipcp_lattice);
-}
-
-/* Given the jump function JFUNC, compute the lattice LAT that describes the
- value coming down the callsite. INFO describes the caller node so that
- pass-through jump functions can be evaluated. */
-static void
-ipcp_lattice_from_jfunc (struct ipa_node_params *info, struct ipcp_lattice *lat,
- struct ipa_jump_func *jfunc)
-{
- if (jfunc->type == IPA_JF_CONST)
- {
- lat->type = IPA_CONST_VALUE;
- lat->constant = jfunc->value.constant;
- }
- else if (jfunc->type == IPA_JF_PASS_THROUGH)
- {
- struct ipcp_lattice *caller_lat;
- tree cst;
-
- caller_lat = ipcp_get_lattice (info, jfunc->value.pass_through.formal_id);
- lat->type = caller_lat->type;
- if (caller_lat->type != IPA_CONST_VALUE)
- return;
- cst = caller_lat->constant;
-
- if (jfunc->value.pass_through.operation != NOP_EXPR)
- {
- tree restype;
- if (TREE_CODE_CLASS (jfunc->value.pass_through.operation)
- == tcc_comparison)
- restype = boolean_type_node;
- else
- restype = TREE_TYPE (cst);
- cst = fold_binary (jfunc->value.pass_through.operation,
- restype, cst, jfunc->value.pass_through.operand);
- }
- if (!cst || !is_gimple_ip_invariant (cst))
- lat->type = IPA_BOTTOM;
- lat->constant = cst;
- }
- else if (jfunc->type == IPA_JF_ANCESTOR)
- {
- struct ipcp_lattice *caller_lat;
- tree t;
- bool ok;
-
- caller_lat = ipcp_get_lattice (info, jfunc->value.ancestor.formal_id);
- lat->type = caller_lat->type;
- if (caller_lat->type != IPA_CONST_VALUE)
- return;
- if (TREE_CODE (caller_lat->constant) != ADDR_EXPR)
- {
- /* This can happen when the constant is a NULL pointer. */
- lat->type = IPA_BOTTOM;
- return;
- }
- t = TREE_OPERAND (caller_lat->constant, 0);
- ok = build_ref_for_offset (&t, TREE_TYPE (t),
- jfunc->value.ancestor.offset,
- jfunc->value.ancestor.type, false);
- if (!ok)
- {
- lat->type = IPA_BOTTOM;
- lat->constant = NULL_TREE;
- }
- else
- lat->constant = build_fold_addr_expr (t);
- }
- else
- lat->type = IPA_BOTTOM;
-}
-
/* True when OLD_LAT and NEW_LAT values are not the same. */
static bool
count = ipa_get_param_count (info);
for (i = 0; i < count; i++)
{
- struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
+ struct ipcp_lattice *lat = ipa_get_lattice (info, i);
fprintf (f, " param [%d]: ", i);
if (lat->type == IPA_CONST_VALUE)
/* There are a number of generic reasons functions cannot be versioned. We
also cannot remove parameters if there are type attributes such as fnspec
present. */
- if (!node->local.versionable
+ if (!inline_summary (node)->versionable
|| TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
return false;
if (cgraph_only_called_directly_p (node) || !node->analyzed)
return false;
+ /* When function address is taken, we are pretty sure it will be called in hidden way. */
+ if (node->address_taken)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Not considering %s for cloning; address is taken.\n",
+ cgraph_node_name (node));
+ return false;
+ }
+
if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
{
if (dump_file)
- fprintf (dump_file, "Not considering %s for cloning; body is overwrittable.\n",
+ fprintf (dump_file, "Not considering %s for cloning; body is overwritable.\n",
cgraph_node_name (node));
return false;
}
cgraph_node_name (node));
return false;
}
- if (node->local.inline_summary.self_size < n_calls)
+ if (inline_summary (node)->self_size < n_calls)
{
if (dump_file)
fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
/* When profile is available and function is hot, propagate into it even if
calls seems cold; constant propagation can improve function's speed
- significandly. */
+ significantly. */
if (max_count)
{
if (direct_call_sum > node->count * 90 / 100)
if (ipa_is_called_with_var_arguments (info))
type = IPA_BOTTOM;
- else if (cgraph_only_called_directly_p (node))
+ else if (node->local.local)
type = IPA_TOP;
/* When cloning is allowed, we can assume that externally visible functions
are not called. We will compensate this by cloning later. */
for (i = 0; i < ipa_get_param_count (info) ; i++)
{
- ipcp_get_lattice (info, i)->type = type;
+ ipa_get_lattice (info, i)->type = type;
if (type == IPA_BOTTOM)
ipa_set_param_cannot_devirtualize (info, i);
}
}
-/* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
- Return the tree. */
+/* Build a constant tree with type TREE_TYPE and value according to LAT.
+ Return the tree, or, if it is not possible to convert such value
+ to TREE_TYPE, NULL. */
static tree
build_const_val (struct ipcp_lattice *lat, tree tree_type)
{
{
if (fold_convertible_p (tree_type, val))
return fold_build1 (NOP_EXPR, tree_type, val);
- else
+ else if (TYPE_SIZE (tree_type) == TYPE_SIZE (TREE_TYPE (val)))
return fold_build1 (VIEW_CONVERT_EXPR, tree_type, val);
+ else
+ return NULL;
}
return val;
}
FIXME: This code is wrong. Since the callers can be also clones and
the clones are not scaled yet, the sums gets unrealistically high.
To properly compute the counts, we would need to do propagation across
- callgraph (as external call to A might imply call to non-clonned B
- if A's clone calls clonned B). */
+ callgraph (as external call to A might imply call to non-cloned B
+ if A's clone calls cloned B). */
static void
ipcp_compute_node_scale (struct cgraph_node *node)
{
count = ipa_get_param_count (info);
for (i = 0; i < count; i++)
{
- struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
+ struct ipcp_lattice *lat = ipa_get_lattice (info, i);
if (lat->type == IPA_TOP)
{
prop_again = true;
struct ipa_node_params *callee_info,
struct ipa_jump_func *jf, int i)
{
- tree cst, binfo;
-
switch (jf->type)
{
case IPA_JF_UNKNOWN:
case IPA_JF_CONST_MEMBER_PTR:
+ case IPA_JF_CONST:
break;
case IPA_JF_KNOWN_TYPE:
return ipcp_add_param_type (callee_info, i, jf->value.base_binfo);
- case IPA_JF_CONST:
- cst = jf->value.constant;
- if (TREE_CODE (cst) != ADDR_EXPR)
- break;
- binfo = gimple_get_relevant_ref_binfo (TREE_OPERAND (cst, 0), NULL_TREE);
- if (!binfo)
- break;
- return ipcp_add_param_type (callee_info, i, binfo);
-
case IPA_JF_PASS_THROUGH:
case IPA_JF_ANCESTOR:
return ipcp_copy_types (caller_info, callee_info, i, jf);
for (i = 0; i < count; i++)
{
jump_func = ipa_get_ith_jump_func (args, i);
- ipcp_lattice_from_jfunc (info, &inc_lat, jump_func);
- dest_lat = ipcp_get_lattice (callee_info, i);
+ ipa_lattice_from_jfunc (info, &inc_lat, jump_func);
+ dest_lat = ipa_get_lattice (callee_info, i);
ipa_lattice_meet (&new_lat, &inc_lat, dest_lat);
if (ipcp_lattice_changed (&new_lat, dest_lat))
{
struct ipa_replace_map *replace_map;
tree const_val;
- replace_map = ggc_alloc_ipa_replace_map ();
const_val = build_const_val (lat, TREE_TYPE (parm_tree));
+ if (const_val == NULL_TREE)
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, " const ");
+ print_generic_expr (dump_file, lat->constant, 0);
+ fprintf (dump_file, " can't be converted to param ");
+ print_generic_expr (dump_file, parm_tree, 0);
+ fprintf (dump_file, "\n");
+ }
+ return NULL;
+ }
+ replace_map = ggc_alloc_ipa_replace_map ();
if (dump_file)
{
fprintf (dump_file, " replacing param ");
if (!n_cloning_candidates)
return false;
+ /* We can't redirect anything in thunks, yet. */
+ if (cs->caller->thunk.thunk_p)
+ return true;
+
if ((orig = ipcp_get_orig_node (node)) != NULL)
node = orig;
if (ipcp_get_orig_node (cs->caller))
count = ipa_get_param_count (orig_callee_info);
for (i = 0; i < count; i++)
{
- struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i);
+ struct ipcp_lattice *lat = ipa_get_lattice (orig_callee_info, i);
struct ipa_jump_func *jump_func;
jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
for (node = cgraph_nodes; node; node = node->next)
if (node->analyzed && ipcp_node_is_clone (node))
{
- bitmap args_to_skip = BITMAP_ALLOC (NULL);
+ bitmap args_to_skip = NULL;
struct cgraph_node *orig_node = ipcp_get_orig_node (node);
struct ipa_node_params *info = IPA_NODE_REF (orig_node);
int i, count = ipa_get_param_count (info);
struct cgraph_edge *cs, *next;
- for (i = 0; i < count; i++)
+ if (node->local.can_change_signature)
{
- struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
-
- /* We can proactively remove obviously unused arguments. */
- if (!ipa_is_param_used (info, i))
+ args_to_skip = BITMAP_ALLOC (NULL);
+ for (i = 0; i < count; i++)
{
- bitmap_set_bit (args_to_skip, i);
- continue;
- }
+ struct ipcp_lattice *lat = ipa_get_lattice (info, i);
- if (lat->type == IPA_CONST_VALUE)
- bitmap_set_bit (args_to_skip, i);
+ /* We can proactively remove obviously unused arguments. */
+ if (!ipa_is_param_used (info, i))
+ {
+ bitmap_set_bit (args_to_skip, i);
+ continue;
+ }
+
+ if (lat->type == IPA_CONST_VALUE)
+ bitmap_set_bit (args_to_skip, i);
+ }
}
for (cs = node->callers; cs; cs = next)
{
scale = ipcp_get_node_scale (orig_node);
node->count = orig_node->count * scale / REG_BR_PROB_BASE;
scale_complement = REG_BR_PROB_BASE - scale;
+
+ gcc_assert (scale_complement >= 0);
orig_node->count =
orig_node->count * scale_complement / REG_BR_PROB_BASE;
for (cs = node->callees; cs; cs = cs->next_callee)
int removable_args = 0;
bool need_original
= !cgraph_will_be_removed_from_program_if_no_direct_calls (node);
+ VEC (tree, heap) *known_vals = NULL;
struct ipa_node_params *info;
int i, count;
int growth;
else
need_original = true;
- /* If we will be able to fully replace orignal node, we never increase
+ /* If we will be able to fully replace original node, we never increase
program size. */
if (!need_original)
return 0;
info = IPA_NODE_REF (node);
count = ipa_get_param_count (info);
- for (i = 0; i < count; i++)
- {
- struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
+ VEC_safe_grow_cleared (tree, heap, known_vals, count);
+ if (node->local.can_change_signature)
+ for (i = 0; i < count; i++)
+ {
+ struct ipcp_lattice *lat = ipa_get_lattice (info, i);
- /* We can proactively remove obviously unused arguments. */
- if (!ipa_is_param_used (info, i))
- removable_args++;
+ /* We can proactively remove obviously unused arguments. */
+ if (!ipa_is_param_used (info, i))
+ removable_args++;
- if (lat->type == IPA_CONST_VALUE)
- removable_args++;
- }
+ if (lat->type == IPA_CONST_VALUE)
+ {
+ removable_args++;
+ VEC_replace (tree, known_vals, i, lat->constant);
+ }
+ }
/* We make just very simple estimate of savings for removal of operand from
- call site. Precise cost is dificult to get, as our size metric counts
+ call site. Precise cost is difficult to get, as our size metric counts
constants and moves as free. Generally we are looking for cases that
small function is called very many times. */
- growth = node->local.inline_summary.self_size
+ estimate_ipcp_clone_size_and_time (node, known_vals, &growth, NULL);
+ VEC_free (tree, heap, known_vals);
+ growth = growth
- removable_args * redirectable_node_callers;
if (growth < 0)
return 0;
cost /= freq_sum * 1000 / REG_BR_PROB_BASE + 1;
if (dump_file)
fprintf (dump_file, "Cost of versioning %s is %i, (size: %i, freq: %i)\n",
- cgraph_node_name (node), cost, node->local.inline_summary.self_size,
+ cgraph_node_name (node), cost, inline_summary (node)->self_size,
freq_sum);
return cost + 1;
}
for (ie = node->indirect_calls; ie; ie = next_ie)
{
- int param_index, types_count, j;
- HOST_WIDE_INT token;
- tree target;
+ int param_index;
+ HOST_WIDE_INT token, anc_offset;
+ tree target, delta, otr_type;
+ struct ipcp_lattice *lat;
next_ie = ie->next_callee;
if (!ie->indirect_info->polymorphic)
continue;
param_index = ie->indirect_info->param_index;
- if (param_index == -1
- || ipa_param_cannot_devirtualize_p (info, param_index)
- || ipa_param_types_vec_empty (info, param_index))
+ if (param_index == -1)
continue;
+ lat = ipa_get_lattice (info, param_index);
token = ie->indirect_info->otr_token;
+ anc_offset = ie->indirect_info->anc_offset;
+ otr_type = ie->indirect_info->otr_type;
target = NULL_TREE;
- types_count = VEC_length (tree, info->params[param_index].types);
- for (j = 0; j < types_count; j++)
+ if (lat->type == IPA_CONST_VALUE)
+ {
+ tree binfo = gimple_extract_devirt_binfo_from_cst (lat->constant);
+ if (!binfo)
+ continue;
+ binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
+ if (!binfo)
+ continue;
+ target = gimple_get_virt_method_for_binfo (token, binfo, &delta,
+ false);
+ }
+ else
{
- tree binfo = VEC_index (tree, info->params[param_index].types, j);
- tree t = gimple_fold_obj_type_ref_known_binfo (token, binfo);
+ int types_count, j;
- if (!t)
- {
- target = NULL_TREE;
- break;
- }
- else if (!target)
- target = t;
- else if (target != t)
+ if (ipa_param_cannot_devirtualize_p (info, param_index)
+ || ipa_param_types_vec_empty (info, param_index))
+ continue;
+
+ types_count = VEC_length (tree, info->params[param_index].types);
+ for (j = 0; j < types_count; j++)
{
- target = NULL_TREE;
- break;
+ tree binfo = VEC_index (tree, info->params[param_index].types, j);
+ tree d, t;
+
+ binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
+ if (!binfo)
+ {
+ target = NULL_TREE;
+ break;
+ }
+
+ t = gimple_get_virt_method_for_binfo (token, binfo, &d, true);
+ if (!t)
+ {
+ target = NULL_TREE;
+ break;
+ }
+ else if (!target)
+ {
+ target = t;
+ delta = d;
+ }
+ else if (target != t || !tree_int_cst_equal (delta, d))
+ {
+ target = NULL_TREE;
+ break;
+ }
}
}
if (target)
- ipa_make_edge_direct_to_target (ie, target);
+ ipa_make_edge_direct_to_target (ie, target, delta);
}
}
for (i = 0; i < count; i++)
{
- struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
+ struct ipcp_lattice *lat = ipa_get_lattice (info, i);
if ((ipcp_lat_is_insertable (lat)
/* Do not count obviously unused arguments. */
&& ipa_is_param_used (info, i))
struct cgraph_indirect_call_info *ici = ie->indirect_info;
next_ie = ie->next_callee;
- if (ici->param_index != index)
+ if (ici->param_index != index
+ || ici->polymorphic)
continue;
- if (ici->polymorphic)
- {
- tree binfo;
- HOST_WIDE_INT token;
-
- if (TREE_CODE (cst) != ADDR_EXPR)
- continue;
-
- binfo = gimple_get_relevant_ref_binfo (TREE_OPERAND (cst, 0),
- NULL_TREE);
- if (!binfo)
- continue;
- gcc_assert (ie->indirect_info->anc_offset == 0);
- token = ie->indirect_info->otr_token;
- cst = gimple_fold_obj_type_ref_known_binfo (token, binfo);
- if (!cst)
- continue;
- }
-
- ipa_make_edge_direct_to_target (ie, cst);
+ ipa_make_edge_direct_to_target (ie, cst, NULL_TREE);
}
}
{
if (node->count > max_count)
max_count = node->count;
- overall_size += node->local.inline_summary.self_size;
+ overall_size += inline_summary (node)->self_size;
}
max_new_size = overall_size;
if (new_size + growth > max_new_size)
break;
if (growth
- && optimize_function_for_size_p (DECL_STRUCT_FUNCTION (node->decl)))
+ && cgraph_optimize_for_size_p (node))
{
if (dump_file)
fprintf (dump_file, "Not versioning, cold code would grow");
continue;
}
- new_size += growth;
-
- /* Look if original function becomes dead after clonning. */
- for (cs = node->callers; cs != NULL; cs = cs->next_caller)
- if (cs->caller == node || ipcp_need_redirect_p (cs))
- break;
- if (!cs && cgraph_will_be_removed_from_program_if_no_direct_calls (node))
- bitmap_set_bit (dead_nodes, node->uid);
-
info = IPA_NODE_REF (node);
count = ipa_get_param_count (info);
replace_trees = VEC_alloc (ipa_replace_map_p, gc, 1);
- args_to_skip = BITMAP_GGC_ALLOC ();
+
+ if (node->local.can_change_signature)
+ args_to_skip = BITMAP_GGC_ALLOC ();
+ else
+ args_to_skip = NULL;
for (i = 0; i < count; i++)
{
- struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
+ struct ipcp_lattice *lat = ipa_get_lattice (info, i);
parm_tree = ipa_get_param (info, i);
/* We can proactively remove obviously unused arguments. */
- if (!ipa_is_param_used (info, i))
+ if (!ipa_is_param_used (info, i))
{
- bitmap_set_bit (args_to_skip, i);
+ if (args_to_skip)
+ bitmap_set_bit (args_to_skip, i);
continue;
}
{
replace_param =
ipcp_create_replace_map (parm_tree, lat);
+ if (replace_param == NULL)
+ break;
VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_param);
- bitmap_set_bit (args_to_skip, i);
+ if (args_to_skip)
+ bitmap_set_bit (args_to_skip, i);
}
}
+ if (i < count)
+ {
+ if (dump_file)
+ fprintf (dump_file, "Not versioning, some parameters couldn't be replaced");
+ continue;
+ }
+
+ new_size += growth;
+
+ /* Look if original function becomes dead after cloning. */
+ for (cs = node->callers; cs != NULL; cs = cs->next_caller)
+ if (cs->caller == node || ipcp_need_redirect_p (cs))
+ break;
+ if (!cs && cgraph_will_be_removed_from_program_if_no_direct_calls (node))
+ bitmap_set_bit (dead_nodes, node->uid);
/* Compute how many callers node has. */
node_callers = 0;
info = IPA_NODE_REF (node);
for (i = 0; i < count; i++)
{
- struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
+ struct ipcp_lattice *lat = ipa_get_lattice (info, i);
if (lat->type == IPA_CONST_VALUE)
ipcp_discover_new_direct_edges (node1, i, lat->constant);
}
ipa_print_all_params (dump_file);
ipa_print_all_jump_functions (dump_file);
}
+ ipa_check_create_node_params ();
+ ipa_check_create_edge_args ();
/* 2. Do the interprocedural propagation. */
ipcp_iterate_stage ();
/* 3. Insert the constants found to the functions. */
if (dump_file)
fprintf (dump_file, "\nIPA constant propagation start:\n");
- ipa_check_create_node_params ();
- ipa_check_create_edge_args ();
ipa_register_cgraph_hooks ();
- for (node = cgraph_nodes; node; node = node->next)
- if (node->analyzed)
+ /* FIXME: We could propagate through thunks happily and we could be
+ even able to clone them, if needed. Do that later. */
+ FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
{
/* Unreachable nodes should have been eliminated before ipcp. */
gcc_assert (node->needed || node->reachable);
- node->local.versionable = tree_versionable_function_p (node->decl);
+ inline_summary (node)->versionable = tree_versionable_function_p (node->decl);
ipa_analyze_node (node);
}
}
cgraph_gate_cp (void)
{
/* FIXME: We should remove the optimize check after we ensure we never run
- IPA passes when not optimizng. */
+ IPA passes when not optimizing. */
return flag_ipa_cp && optimize;
}
projects / gcc.git / blobdiff