/* Interprocedural constant propagation
- Copyright (C) 2005, 2006, 2007, 2008 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"
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:
else if (jfunc->type == IPA_JF_PASS_THROUGH)
{
struct ipcp_lattice *caller_lat;
+ tree cst;
- caller_lat = ipcp_get_lattice (info, jfunc->value.formal_id);
+ caller_lat = ipcp_get_lattice (info, jfunc->value.pass_through.formal_id);
lat->type = caller_lat->type;
- lat->constant = caller_lat->constant;
+ 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;
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)
}
}
+/* Return true if ipcp algorithms would allow cloning NODE. */
+
+static bool
+ipcp_versionable_function_p (struct cgraph_node *node)
+{
+ tree decl = node->decl;
+ basic_block bb;
+
+ /* 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)
+ return false;
+
+ /* Removing arguments doesn't work if we use __builtin_apply_args. */
+ FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (decl))
+ {
+ 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;
+ }
+ }
+
+ return true;
+}
+
/* Return true if this NODE is viable candidate for cloning. */
static bool
ipcp_cloning_candidate_p (struct cgraph_node *node)
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)
cgraph_node_name (node));
return false;
}
- if (!tree_versionable_function_p (node->decl))
+ if (!ipcp_versionable_function_p (node))
{
if (dump_file)
fprintf (dump_file, "Not considering %s for cloning; body is not versionable.\n",
if (cgraph_maybe_hot_edge_p (e))
n_hot_calls ++;
}
-
+
if (!n_calls)
{
if (dump_file)
cgraph_node_name (node));
return false;
}
- if (node->local.inline_summary.self_insns < n_calls)
+ if (node->local.inline_summary.self_size < 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);
{
/* Once we will be able to do in-place replacement, we can be more
lax here. */
- return tree_versionable_function_p (node->decl);
+ return ipcp_versionable_function_p (node);
}
/* Print count scale data structures. */
{
next = cs->next_caller;
if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
- {
- cgraph_redirect_edge_callee (cs, orig_node);
- gimple_call_set_fndecl (cs->call_stmt, orig_node->decl);
- }
+ cgraph_redirect_edge_callee (cs, orig_node);
}
}
}
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;
call site. Precise cost is dificult 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_insns
+ growth = node->local.inline_summary.self_size
- 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_insns,
+ cgraph_node_name (node), cost, node->local.inline_summary.self_size,
freq_sum);
return cost + 1;
}
{
if (node->count > max_count)
max_count = node->count;
- overall_size += node->local.inline_summary.self_insns;
+ overall_size += node->local.inline_summary.self_size;
}
max_new_size = overall_size;
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);
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)
return flag_ipa_cp;
}
-struct ipa_opt_pass pass_ipa_cp =
+struct ipa_opt_pass_d pass_ipa_cp =
{
{
IPA_PASS,
TODO_remove_functions /* 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 */