/* Interprocedural constant propagation
- Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
+ Free Software Foundation, Inc.
Contributed by Razya Ladelsky <RAZYA@il.ibm.com>
-
+
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 3, or (at your option) any later
version.
-
+
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
-
+
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
{
printf ("value is %d",y);
}
-
+
int f (int x)
{
g (x);
f (3);
h (3);
}
-
-
+
+
The IPCP algorithm will find that g's formal argument y is always called
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
152-161
-
+
The optimization is divided into three stages:
First stage - intraprocedural analysis
=======================================
This phase computes jump_function and modification flags.
-
+
A jump function for a callsite represents the values passed as an actual
arguments of a given callsite. There are three types of values:
Pass through - the caller's formal parameter is passed as an actual argument.
Constant - a constant is passed as an actual argument.
Unknown - neither of the above.
-
+
The jump function info, ipa_jump_func, is stored in ipa_edge_args
structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
modified_flags are defined in ipa_node_params structure
(defined in ipa_prop.h and pointed to by cgraph_edge->aux).
-
+
-ipcp_init_stage() is the first stage driver.
Second stage - interprocedural analysis
TOP - unknown.
BOTTOM - non constant.
CONSTANT - constant value.
-
+
Lattice describing a formal parameter p will have a constant value if all
callsites invoking this function have the same constant value passed to p.
-
+
The lattices are stored in ipcp_lattice which is itself in ipa_node_params
structure (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
and many calls redirected back to fit the description above.
-ipcp_insert_stage() is the third phase driver.
-
+
*/
#include "config.h"
/* Unreachable nodes should have been eliminated before ipcp. */
gcc_assert (node->needed || node->reachable);
+ node->local.versionable = tree_versionable_function_p (node->decl);
ipa_initialize_node_params (node);
ipa_detect_param_modifications (node);
}
if (lat1->type != lat2->type)
return false;
- if (operand_equal_p (lat1->constant, lat2->constant, 0))
- return true;
-
- return false;
+ if (TREE_CODE (lat1->constant) == ADDR_EXPR
+ && TREE_CODE (lat2->constant) == ADDR_EXPR
+ && TREE_CODE (TREE_OPERAND (lat1->constant, 0)) == CONST_DECL
+ && TREE_CODE (TREE_OPERAND (lat2->constant, 0)) == CONST_DECL)
+ return operand_equal_p (DECL_INITIAL (TREE_OPERAND (lat1->constant, 0)),
+ DECL_INITIAL (TREE_OPERAND (lat2->constant, 0)), 0);
+ else
+ return operand_equal_p (lat1->constant, lat2->constant, 0);
}
/* Compute Meet arithmetics:
cst = caller_lat->constant;
if (jfunc->value.pass_through.operation != NOP_EXPR)
- cst = fold_binary (jfunc->value.pass_through.operation,
- TREE_TYPE (cst), cst,
- jfunc->value.pass_through.operand);
+ {
+ 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;
fprintf (f, " param [%d]: ", i);
if (lat->type == IPA_CONST_VALUE)
{
+ tree cst = lat->constant;
fprintf (f, "type is CONST ");
- print_generic_expr (f, lat->constant, 0);
+ print_generic_expr (f, cst, 0);
+ if (TREE_CODE (cst) == ADDR_EXPR
+ && TREE_CODE (TREE_OPERAND (cst, 0)) == CONST_DECL)
+ {
+ fprintf (f, " -> ");
+ print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (cst, 0)),
+ 0);
+ }
fprintf (f, "\n");
}
else if (lat->type == IPA_TOP)
static bool
ipcp_versionable_function_p (struct cgraph_node *node)
{
- tree decl = node->decl;
- basic_block bb;
+ struct cgraph_edge *edge;
/* There are a number of generic reasons functions cannot be versioned. */
- if (!tree_versionable_function_p (decl))
+ if (!node->local.versionable)
return false;
- /* Removing arguments doesn't work if the function takes varargs. */
- if (DECL_STRUCT_FUNCTION (decl)->stdarg)
- return false;
-
- /* Removing arguments doesn't work if we use __builtin_apply_args. */
- FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (decl))
+ /* Removing arguments doesn't work if the function takes varargs
+ or use __builtin_apply_args. */
+ for (edge = node->callees; edge; edge = edge->next_callee)
{
- gimple_stmt_iterator gsi;
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- const_gimple stmt = gsi_stmt (gsi);
- tree t;
-
- if (!is_gimple_call (stmt))
- continue;
- t = gimple_call_fndecl (stmt);
- if (t == NULL_TREE)
- continue;
- if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL
- && DECL_FUNCTION_CODE (t) == BUILT_IN_APPLY_ARGS)
- return false;
- }
+ tree t = edge->callee->decl;
+ if (DECL_BUILT_IN_CLASS (t) == BUILT_IN_NORMAL
+ && (DECL_FUNCTION_CODE (t) == BUILT_IN_APPLY_ARGS
+ || DECL_FUNCTION_CODE (t) == BUILT_IN_VA_START))
+ return false;
}
return true;
FIXME: in future we should clone such functions when they are called with
different constants, but current ipcp implementation is not good on this.
*/
- if (!node->needed || !node->analyzed)
+ if (cgraph_only_called_directly_p (node) || !node->analyzed)
return false;
if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
if (cgraph_maybe_hot_edge_p (e))
n_hot_calls ++;
}
-
+
if (!n_calls)
{
if (dump_file)
fprintf (dump_file, "Considering %s for cloning; code would shrink.\n",
cgraph_node_name (node));
return true;
- }
+ }
if (!flag_ipa_cp_clone)
{
if (ipa_is_called_with_var_arguments (info))
type = IPA_BOTTOM;
- else if (!node->needed)
+ else if (cgraph_only_called_directly_p (node))
type = IPA_TOP;
/* When cloning is allowed, we can assume that externally visible functions
are not called. We will compensate this by cloning later. */
/* Compute the proper scale for NODE. It is the ratio between the number of
direct calls (represented on the incoming cgraph_edges) and sum of all
- invocations of NODE (represented as count in cgraph_node). */
+ invocations of NODE (represented as count in cgraph_node).
+
+ 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). */
static void
ipcp_compute_node_scale (struct cgraph_node *node)
{
/* Compute sum of all counts of callers. */
for (cs = node->callers; cs != NULL; cs = cs->next_caller)
sum += cs->count;
+ /* Work around the unrealistically high sum problem. We just don't want
+ the non-cloned body to have negative or very low frequency. Since
+ majority of execution time will be spent in clones anyway, this should
+ give good enough profile. */
+ if (sum > node->count * 9 / 10)
+ sum = node->count * 9 / 10;
if (node->count == 0)
ipcp_set_node_scale (node, 0);
else
/* building jump functions */
for (cs = node->callees; cs; cs = cs->next_callee)
{
- if (!cs->callee->analyzed)
+ /* We do not need to bother analyzing calls to unknown
+ functions unless they may become known during lto/whopr. */
+ if (!cs->callee->analyzed && !flag_lto && !flag_whopr)
continue;
ipa_count_arguments (cs);
if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
!= ipa_get_param_count (IPA_NODE_REF (cs->callee)))
- {
- /* Handle cases of functions with
- a variable number of parameters. */
- ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
- if (flag_indirect_inlining)
- ipa_compute_jump_functions (cs);
- }
- else
- ipa_compute_jump_functions (cs);
+ ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
+ ipa_compute_jump_functions (cs);
}
}
}
struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee);
struct ipa_edge_args *args = IPA_EDGE_REF (cs);
- if (ipa_is_called_with_var_arguments (callee_info))
+ if (ipa_is_called_with_var_arguments (callee_info)
+ || !cs->callee->analyzed
+ || ipa_is_called_with_var_arguments (callee_info))
continue;
count = ipa_get_cs_argument_count (args);
if (dump_file)
fprintf (dump_file, "\nIPA iterate stage:\n\n");
+
+ if (in_lto_p)
+ ipa_update_after_lto_read ();
+
for (node = cgraph_nodes; node; node = node->next)
{
ipcp_initialize_node_lattices (node);
for (i = 0; i < count; i++)
{
struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
- tree parm_tree = ipa_get_param (info, i);
/* We can proactively remove obviously unused arguments. */
- if (is_gimple_reg (parm_tree)
- && !gimple_default_def (DECL_STRUCT_FUNCTION (orig_node->decl),
- parm_tree))
+ if (!ipa_is_param_used (info, i))
{
bitmap_set_bit (args_to_skip, i);
continue;
struct cgraph_edge *cs;
int redirectable_node_callers = 0;
int removable_args = 0;
- bool need_original = node->needed;
+ bool need_original = !cgraph_only_called_directly_p (node);
struct ipa_node_params *info;
int i, count;
int growth;
for (i = 0; i < count; i++)
{
struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
- tree parm_tree = ipa_get_param (info, i);
/* We can proactively remove obviously unused arguments. */
- if (is_gimple_reg (parm_tree)
- && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
- parm_tree))
+ if (!ipa_is_param_used (info, i))
removable_args++;
if (lat->type == IPA_CONST_VALUE)
for (i = 0; i < count; i++)
{
struct ipcp_lattice *lat = ipcp_get_lattice (info, i);
- tree parm_tree = ipa_get_param (info, i);
if (ipcp_lat_is_insertable (lat)
/* Do not count obviously unused arguments. */
- && (!is_gimple_reg (parm_tree)
- || gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
- parm_tree)))
+ && ipa_is_param_used (info, i))
const_param++;
}
return const_param;
for (cs = node->callers; cs != NULL; cs = cs->next_caller)
if (cs->caller == node || ipcp_need_redirect_p (cs))
break;
- if (!cs && !node->needed)
+ if (!cs && cgraph_only_called_directly_p (node))
bitmap_set_bit (dead_nodes, node->uid);
info = IPA_NODE_REF (node);
parm_tree = ipa_get_param (info, i);
/* We can proactively remove obviously unused arguments. */
- if (is_gimple_reg (parm_tree)
- && !gimple_default_def (DECL_STRUCT_FUNCTION (node->decl),
- parm_tree))
+ if (!ipa_is_param_used (info, i))
{
bitmap_set_bit (args_to_skip, i);
continue;
ipcp_print_profile_data (dump_file);
}
/* Free all IPCP structures. */
- free_all_ipa_structures_after_ipa_cp ();
+ ipa_free_all_structures_after_ipa_cp ();
if (dump_file)
fprintf (dump_file, "\nIPA constant propagation end\n");
return 0;
ipa_check_create_node_params ();
ipa_check_create_edge_args ();
ipa_register_cgraph_hooks ();
- /* 1. Call the init stage to initialize
+ /* 1. Call the init stage to initialize
the ipa_node_params and ipa_edge_args structures. */
ipcp_init_stage ();
}
+/* Write ipcp summary for nodes in SET. */
+static void
+ipcp_write_summary (cgraph_node_set set,
+ varpool_node_set vset ATTRIBUTE_UNUSED)
+{
+ ipa_prop_write_jump_functions (set);
+}
+
+/* Read ipcp summary. */
+static void
+ipcp_read_summary (void)
+{
+ ipa_prop_read_jump_functions ();
+}
+
/* Gate for IPCP optimization. */
static bool
cgraph_gate_cp (void)
0, /* properties_destroyed */
0, /* todo_flags_start */
TODO_dump_cgraph | TODO_dump_func |
- TODO_remove_functions /* todo_flags_finish */
+ TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
},
ipcp_generate_summary, /* generate_summary */
- NULL, /* write_summary */
- NULL, /* read_summary */
- NULL, /* function_read_summary */
+ ipcp_write_summary, /* write_summary */
+ ipcp_read_summary, /* read_summary */
+ NULL, /* write_optimization_summary */
+ NULL, /* read_optimization_summary */
+ NULL, /* stmt_fixup */
0, /* TODOs */
NULL, /* function_transform */
NULL, /* variable_transform */