/* 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"
#include "flags.h"
#include "timevar.h"
#include "diagnostic.h"
+#include "tree-pretty-print.h"
#include "tree-dump.h"
#include "tree-inline.h"
#include "fibheap.h"
ipcp_init_cloned_node (struct cgraph_node *orig_node,
struct cgraph_node *new_node)
{
- ipa_check_create_node_params ();
- ipa_initialize_node_params (new_node);
+ gcc_checking_assert (ipa_node_params_vector
+ && (VEC_length (ipa_node_params_t,
+ ipa_node_params_vector)
+ > (unsigned) cgraph_max_uid));
+ gcc_checking_assert (IPA_NODE_REF (new_node)->params);
IPA_NODE_REF (new_node)->ipcp_orig_node = orig_node;
}
-/* Perform intraprocedrual analysis needed for ipcp. */
-static void
-ipcp_analyze_node (struct cgraph_node *node)
-{
- /* Unreachable nodes should have been eliminated before ipcp. */
- gcc_assert (node->needed || node->reachable);
-
- ipa_initialize_node_params (node);
- ipa_detect_param_modifications (node);
-}
-
/* Return scale for NODE. */
static inline gcov_type
ipcp_get_node_scale (struct cgraph_node *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))
- return false;
-
- /* Removing arguments doesn't work if the function takes varargs. */
- if (DECL_STRUCT_FUNCTION (decl)->stdarg)
+ if (!node->local.versionable)
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;
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)
{
/* 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
/* Initialization and computation of IPCP data structures. This is the initial
intraprocedural analysis of functions, which gathers information to be
propagated later on. */
+
static void
ipcp_init_stage (void)
{
struct cgraph_node *node;
- struct cgraph_edge *cs;
for (node = cgraph_nodes; node; node = node->next)
if (node->analyzed)
- ipcp_analyze_node (node);
- for (node = cgraph_nodes; node; node = node->next)
- {
- if (!node->analyzed)
- continue;
- /* building jump functions */
- for (cs = node->callees; cs; cs = cs->next_callee)
- {
- if (!cs->callee->analyzed)
- 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);
- }
- }
+ {
+ /* Unreachable nodes should have been eliminated before ipcp. */
+ gcc_assert (node->needed || node->reachable);
+
+ node->local.versionable = tree_versionable_function_p (node->decl);
+ ipa_analyze_node (node);
+ }
}
/* Return true if there are some formal parameters whose value is IPA_TOP (in
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);
struct ipa_replace_map *replace_map;
tree const_val;
- replace_map = GGC_NEW (struct ipa_replace_map);
+ replace_map = ggc_alloc_ipa_replace_map ();
const_val = build_const_val (lat, TREE_TYPE (parm_tree));
if (dump_file)
{
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 = !cgraph_only_called_directly_p (node);
+ bool need_original
+ = !cgraph_will_be_removed_from_program_if_no_direct_calls (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 && cgraph_only_called_directly_p (node))
+ 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);
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;
new versioned node. */
node1 =
cgraph_create_virtual_clone (node, redirect_callers, replace_trees,
- args_to_skip);
+ args_to_skip, "constprop");
args_to_skip = NULL;
VEC_free (cgraph_edge_p, heap, redirect_callers);
replace_trees = NULL;
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)
{
- /* FIXME lto. IPA-CP does not tolerate running when the inlining decisions
- have not been applied. This happens when WPA modifies the callgraph.
- Since those decisions are not applied until after all the IPA passes
- have been run in LTRANS, this means that IPA passes may see partially
- modified callgraphs. The solution to this is to apply WPA decisions
- early during LTRANS. */
- return flag_ipa_cp && !flag_ltrans;
+ /* FIXME: We should remove the optimize check after we ensure we never run
+ IPA passes when not optimizng. */
+ return flag_ipa_cp && optimize;
}
struct ipa_opt_pass_d pass_ipa_cp =
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 */