* [PATCH 0/6] Cgraph changes and various devirtualizations
@ 2010-02-13 18:03 Martin Jambor
2010-02-13 18:03 ` [PATCH 1/6] Clarify edge redirection for inline clones Martin Jambor
` (5 more replies)
0 siblings, 6 replies; 23+ messages in thread
From: Martin Jambor @ 2010-02-13 18:03 UTC (permalink / raw)
To: GCC Patches; +Cc: Jan Hubicka
Hi,
this patch series introduces a number of changes to the call graph
handling, improves how we fold calls to OBJ_TYPE_REFs and then uses
these structural improvements to implement inlining of virtual calls
which have a known callee because of previous inlining and
devirtualization as a part of IPA-CP.
The individual patches have comments describing them in detail in
their separate emails. All of them - with a potential exception of
the first one - are intended for 4.6 and even though that means they
are in an RFC stage I consider them rather complete.
As far as performance impact is concerned, I expect to find out what
exactly it is from pretty-ipa branch automated tester. Nevertheless,
today I have manually measured ~3.5% improvement in 483.xalancbmk run
time. In the same benchmark, these changes bring about 96 new call
graph edges created by indirect inlining (and so potentially inlined)
and IPA-CP devirtualizes further 70 calls. In our libstdc++ testsuite
there are 70 devirtualizations, 96 new indirect inlining edges for
virtual functions and 2603 more OBJ_TYPE_REF calls are folded in
fold_gimple_call in tree-ssa-ccp.c.
I have seen no change in DLV and tramp3D, which I more or less
expected, and none in xpdf as well, which surprised me a bit. On the
whole, however, I do believe that at least the ability to inline
virtual calls is very important for quite a lot of applications.
I'll be grateful for any comments (and approval to commit to
pretty-ipa).
Thanks,
Martin
^ permalink raw reply [flat|nested] 23+ messages in thread
* [PATCH 1/6] Clarify edge redirection for inline clones
2010-02-13 18:03 [PATCH 0/6] Cgraph changes and various devirtualizations Martin Jambor
@ 2010-02-13 18:03 ` Martin Jambor
2010-02-22 14:23 ` Jan Hubicka
2010-02-13 18:04 ` [PATCH 6/6] Devirtualization in ipa-cp Martin Jambor
` (4 subsequent siblings)
5 siblings, 1 reply; 23+ messages in thread
From: Martin Jambor @ 2010-02-13 18:03 UTC (permalink / raw)
To: GCC Patches; +Cc: Jan Hubicka
[-- Attachment #1: improve_cgraph_edge_redirection.diff --]
[-- Type: text/plain, Size: 8414 bytes --]
Hi,
this patch a new one in the series and it changes how we set
declarations in call statements to reflect the callee of the
corresponding call graph edge. Currently we do this for all nodes in
cgraph_materialize_all_clones and since at this point inline clones
still share their bodies, we do it only for one of them, the one which
passes through condition
(!node->clone_of || node->clone_of->decl != node->decl)
For the same reason, it is also never done for call statements for
which gimple_call_fndecl returns NULL - so that we don't change
statements of all inline clones because of an indirect-inlining
created edge out of one of them.
However, in order to use this mechanism for IPA-CP devirtualization we
need to be able to redirect even these statements. Therefore this
patch keeps the current redirection only for nodes which are not
inlined and deals with these in copy_bb in tree-inline.c.
I have put this change to the beginning of the series because the
current mechanism is quite fragile and I suspect that PR 41290 is
caused by an original node (with inline clones) somehow ceasing to
exist which would lead exactly to these kinds of cgraph verification
issues. I have asked the reporter to verify this hypothesis and if it
fixes the issue, I will request an approval to commit to trunk now.
Otherwise I will wait with this until stage1.
I have bootstrapped and regression tested this patch separately on
x86_64-linux.
Thanks,
Martin
2010-02-12 Martin Jambor <mjambor@suse.cz>
* cgraph.h (cgraph_redirect_edge_call_stmt_to_callee): Declare.
* cgraphunit.c (cgraph_materialize_all_clones): Moved call
redirection...
(cgraph_redirect_edge_call_stmt_to_callee): ...to this new
function.
(verify_cgraph_node): Do not check for edges pointing to wrong
nodes in inline clones.
* tree-inline.c (copy_bb): Call
cgraph_redirect_edge_call_stmt_to_callee.
Index: icln/gcc/cgraph.h
===================================================================
--- icln.orig/gcc/cgraph.h
+++ icln/gcc/cgraph.h
@@ -530,7 +530,7 @@ void cgraph_remove_edge_duplication_hook
struct cgraph_2node_hook_list *cgraph_add_node_duplication_hook (cgraph_2node_hook, void *);
void cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *);
void cgraph_materialize_all_clones (void);
-
+gimple cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *);
/* In cgraphbuild.c */
unsigned int rebuild_cgraph_edges (void);
void reset_inline_failed (struct cgraph_node *);
Index: icln/gcc/cgraphunit.c
===================================================================
--- icln.orig/gcc/cgraphunit.c
+++ icln/gcc/cgraphunit.c
@@ -751,8 +751,9 @@ verify_cgraph_node (struct cgraph_node *
debug_tree (e->callee->decl);
error_found = true;
}
- else if (!clone_of_p (cgraph_node (decl), e->callee)
- && !e->callee->global.inlined_to)
+ else if (!node->global.inlined_to
+ && !e->callee->global.inlined_to
+ && !clone_of_p (cgraph_node (decl), e->callee))
{
error ("edge points to wrong declaration:");
debug_tree (e->callee->decl);
@@ -2222,11 +2223,60 @@ cgraph_materialize_clone (struct cgraph_
bitmap_obstack_release (NULL);
}
+/* If necessary, change the function declaration in the call statement
+ associated with E so that it corresponds to the edge callee. */
+
+gimple
+cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
+{
+ tree decl = gimple_call_fndecl (e->call_stmt);
+ gimple new_stmt;
+ gimple_stmt_iterator gsi;
+
+ if (!decl || decl == e->callee->decl
+ /* Don't update call from same body alias to the real function. */
+ || cgraph_get_node (decl) == cgraph_get_node (e->callee->decl))
+ return e->call_stmt;
+
+ if (cgraph_dump_file)
+ {
+ fprintf (cgraph_dump_file, "updating call of %s in %s:",
+ cgraph_node_name (e->caller),
+ cgraph_node_name (e->callee));
+ print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
+ }
+
+ if (e->callee->clone.combined_args_to_skip)
+ new_stmt = gimple_call_copy_skip_args (e->call_stmt,
+ e->callee->clone.combined_args_to_skip);
+ else
+ new_stmt = e->call_stmt;
+ if (gimple_vdef (new_stmt)
+ && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
+ SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
+ gimple_call_set_fndecl (new_stmt, e->callee->decl);
+
+ gsi = gsi_for_stmt (e->call_stmt);
+ gsi_replace (&gsi, new_stmt, true);
+
+ /* Update EH information too, just in case. */
+ maybe_clean_or_replace_eh_stmt (e->call_stmt, new_stmt);
+
+ cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
+
+ if (cgraph_dump_file)
+ {
+ fprintf (cgraph_dump_file, " updated to:");
+ print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
+ }
+ return new_stmt;
+}
+
/* Once all functions from compilation unit are in memory, produce all clones
- and update all calls.
- We might also do this on demand if we don't want to bring all functions to
- memory prior compilation, but current WHOPR implementation does that and it is
- is bit easier to keep everything right in this order. */
+ and update all calls. We might also do this on demand if we don't want to
+ bring all functions to memory prior compilation, but current WHOPR
+ implementation does that and it is is bit easier to keep everything right in
+ this order. */
void
cgraph_materialize_all_clones (void)
{
@@ -2302,63 +2352,15 @@ cgraph_materialize_all_clones (void)
if (cgraph_dump_file)
fprintf (cgraph_dump_file, "Updating call sites\n");
for (node = cgraph_nodes; node; node = node->next)
- if (node->analyzed && gimple_has_body_p (node->decl)
- && (!node->clone_of || node->clone_of->decl != node->decl))
+ if (node->analyzed && !node->global.inlined_to
+ && gimple_has_body_p (node->decl))
{
struct cgraph_edge *e;
current_function_decl = node->decl;
push_cfun (DECL_STRUCT_FUNCTION (node->decl));
for (e = node->callees; e; e = e->next_callee)
- {
- tree decl = gimple_call_fndecl (e->call_stmt);
- /* When function gets inlined, indirect inlining might've invented
- new edge for orginally indirect stmt. Since we are not
- preserving clones in the original form, we must not update here
- since other inline clones don't need to contain call to the same
- call. Inliner will do the substitution for us later. */
- if (decl && decl != e->callee->decl)
- {
- gimple new_stmt;
- gimple_stmt_iterator gsi;
-
- if (cgraph_get_node (decl) == cgraph_get_node (e->callee->decl))
- /* Don't update call from same body alias to the real function. */
- continue;
-
- if (cgraph_dump_file)
- {
- fprintf (cgraph_dump_file, "updating call of %s in %s:",
- cgraph_node_name (node),
- cgraph_node_name (e->callee));
- print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
- }
-
- if (e->callee->clone.combined_args_to_skip)
- new_stmt = gimple_call_copy_skip_args (e->call_stmt,
- e->callee->clone.combined_args_to_skip);
- else
- new_stmt = e->call_stmt;
- if (gimple_vdef (new_stmt)
- && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
- SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
- gimple_call_set_fndecl (new_stmt, e->callee->decl);
-
- gsi = gsi_for_stmt (e->call_stmt);
- gsi_replace (&gsi, new_stmt, true);
-
- /* Update EH information too, just in case. */
- maybe_clean_or_replace_eh_stmt (e->call_stmt, new_stmt);
-
- cgraph_set_call_stmt_including_clones (node, e->call_stmt, new_stmt);
-
- if (cgraph_dump_file)
- {
- fprintf (cgraph_dump_file, " updated to:");
- print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
- }
- }
- }
+ cgraph_redirect_edge_call_stmt_to_callee (e);
pop_cfun ();
current_function_decl = NULL;
#ifdef ENABLE_CHECKING
Index: icln/gcc/tree-inline.c
===================================================================
--- icln.orig/gcc/tree-inline.c
+++ icln/gcc/tree-inline.c
@@ -1651,6 +1651,7 @@ copy_bb (copy_body_data *id, basic_block
bb->frequency,
copy_basic_block->frequency);
}
+ stmt = cgraph_redirect_edge_call_stmt_to_callee (edge);
}
break;
^ permalink raw reply [flat|nested] 23+ messages in thread
* [PATCH 4/6] Remove unused ipa_note_param_call.called flag (approved)
2010-02-13 18:03 [PATCH 0/6] Cgraph changes and various devirtualizations Martin Jambor
` (3 preceding siblings ...)
2010-02-13 18:04 ` [PATCH 5/6] Indirect inlining " Martin Jambor
@ 2010-02-13 18:04 ` Martin Jambor
2010-02-13 18:14 ` Richard Guenther
2010-02-22 15:04 ` Jan Hubicka
2010-02-13 18:04 ` [PATCH 2/6] Indirect call graph edges Martin Jambor
5 siblings, 2 replies; 23+ messages in thread
From: Martin Jambor @ 2010-02-13 18:04 UTC (permalink / raw)
To: GCC Patches; +Cc: Jan Hubicka
[-- Attachment #1: remove_unused_call_flag.diff --]
[-- Type: text/plain, Size: 3673 bytes --]
This patch is a minor cleanup. I have realized that the called flag
in the ipa-prop parameter descriptor is not used and I could not
really think how the flag can be obviously useful in a short-term
either so I removed it.
I have bootstrapped and tested this change along with the next one in
the series.
The patch has already been approved by Honza but this is its place in
the series and so I re-send it along.
Thanks,
Martin
2009-12-28 Martin Jambor <mjambor@suse.cz>
* ipa-prop.h (struct ipa_param_descriptor): Removed the called field.
(ipa_is_param_called): Removed.
* ipa-prop.c (ipa_note_param_call): Do not set the called flag.
Removed parameter info.
(ipa_print_node_params): Do not print the called flag.
Index: icln/gcc/ipa-prop.c
===================================================================
--- icln.orig/gcc/ipa-prop.c
+++ icln/gcc/ipa-prop.c
@@ -736,20 +736,16 @@ ipa_is_ssa_with_stmt_def (tree t)
}
/* Create a new indirect call graph edge describing a call to a parameter
- number FORMAL_ID and and set the called flag of the parameter. NODE is the
- caller and is described by INFO. STMT is the corresponding call
+ number FORMAL_ID. NODE is the caller, STMT is the corresponding call
statement. */
static void
-ipa_note_param_call (struct cgraph_node *node, struct ipa_node_params *info,
- int formal_id, gimple stmt)
+ipa_note_param_call (struct cgraph_node *node, int formal_id, gimple stmt)
{
struct cgraph_edge *cs;
basic_block bb = gimple_bb (stmt);
int freq;
- info->params[formal_id].called = 1;
-
freq = compute_call_stmt_bb_frequency (current_function_decl, bb);
cs = cgraph_create_indirect_edge (node, stmt, bb->count, freq,
bb->loop_depth);
@@ -826,7 +822,7 @@ ipa_analyze_call_uses (struct cgraph_nod
/* assuming TREE_CODE (var) == PARM_DECL */
index = ipa_get_param_decl_index (info, var);
if (index >= 0)
- ipa_note_param_call (node, info, index, call);
+ ipa_note_param_call (node, index, call);
return;
}
@@ -923,7 +919,7 @@ ipa_analyze_call_uses (struct cgraph_nod
index = ipa_get_param_decl_index (info, rec);
if (index >= 0 && !ipa_is_param_modified (info, index))
- ipa_note_param_call (node, info, index, call);
+ ipa_note_param_call (node, index, call);
return;
}
@@ -1405,8 +1401,6 @@ ipa_print_node_params (FILE * f, struct
: "(unnamed)"));
if (ipa_is_param_modified (info, i))
fprintf (f, " modified");
- if (ipa_is_param_called (info, i))
- fprintf (f, " called");
fprintf (f, "\n");
}
}
Index: icln/gcc/ipa-prop.h
===================================================================
--- icln.orig/gcc/ipa-prop.h
+++ icln/gcc/ipa-prop.h
@@ -143,8 +143,6 @@ struct ipa_param_descriptor
tree decl;
/* Whether the value parameter has been modified within the function. */
unsigned modified : 1;
- /* Whether the parameter has been used as a call destination. */
- unsigned called : 1;
};
/* ipa_node_params stores information related to formal parameters of functions
@@ -220,17 +218,6 @@ ipa_is_param_modified (struct ipa_node_p
return info->params[i].modified;
}
-/* Return the called flag corresponding to the Ith formal parameter of the
- function associated with INFO. Note that there is no setter method as the
- goal is to set all flags when building the array in
- ipa_detect_called_params. */
-
-static inline bool
-ipa_is_param_called (struct ipa_node_params *info, int i)
-{
- return info->params[i].called;
-}
-
/* Flag this node as having callers with variable number of arguments. */
static inline void
^ permalink raw reply [flat|nested] 23+ messages in thread
* [PATCH 3/6] Folding of virtual calls
2010-02-13 18:03 [PATCH 0/6] Cgraph changes and various devirtualizations Martin Jambor
2010-02-13 18:03 ` [PATCH 1/6] Clarify edge redirection for inline clones Martin Jambor
2010-02-13 18:04 ` [PATCH 6/6] Devirtualization in ipa-cp Martin Jambor
@ 2010-02-13 18:04 ` Martin Jambor
2010-02-13 18:12 ` Richard Guenther
2010-02-13 18:04 ` [PATCH 5/6] Indirect inlining " Martin Jambor
` (2 subsequent siblings)
5 siblings, 1 reply; 23+ messages in thread
From: Martin Jambor @ 2010-02-13 18:04 UTC (permalink / raw)
To: GCC Patches; +Cc: Jan Hubicka
[-- Attachment #1: combined_virtcall_folding.diff --]
[-- Type: text/plain, Size: 12638 bytes --]
Hi,
this patch has not changed at all since I posted it last time in
January but needs to be applied before the next one is so I send it
along again.
The purpose of the patch is to allow folding of more complex
OBJ_TYPE_REFs, as opposed to only the simple class we are able to fold
today. This patch only implements devirtualization through statement
folding (which is also greatly improved, for example we can now fold
when early inlining makes type information available). However, it
also facilitates interface necessary for IPA devirtualization
including indirect inlining of virtual calls.
The juggling with binfos is a bit bizarre and perhaps a C++ maintainer
should have a look at it but it has worked seamlessly in my tests for
a few months now so I'm becoming quite confident it is in fact
correct.
Thanks,
Martin
2010-02-10 Martin Jambor <mjambor@suse.cz>
* gimple.c (get_base_binfo_for_type): New function.
(get_relevant_ref_binfo_single_inh): New function.
(get_relevant_ref_binfo_multi_inh): New function.
(gimple_fold_obj_type_ref_known_binfo): New function.
(gimple_fold_obj_type_ref): Get binfo from
get_relevant_ref_binfo_single_inh and
get_relevant_ref_binfo_multi_inh and use
gimple_fold_obj_type_ref_known_binfo.
* gimple.h (gimple_fold_obj_type_ref): Declare.
(gimple_fold_obj_type_ref_known_binfo): Declare.
* tree-ssa-ccp.c (fold_gimple_call): Simplify condition for
folding virtual calls and call gimple_fold_obj_type_ref.
Index: icln/gcc/gimple.c
===================================================================
--- icln.orig/gcc/gimple.c
+++ icln/gcc/gimple.c
@@ -4632,27 +4632,167 @@ gimple_decl_printable_name (tree decl, i
return IDENTIFIER_POINTER (DECL_NAME (decl));
}
+/* Search for a base binfo of BINFO that corresponds to TYPE and return it if
+ it is found or NULL_TREE if it is not. */
+
+static tree
+get_base_binfo_for_type (tree binfo, tree type)
+{
+ int i;
+ tree base_binfo;
+ tree res = NULL_TREE;
+
+ for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
+ if (TREE_TYPE (base_binfo) == type)
+ {
+ gcc_assert (!res);
+ res = base_binfo;
+ }
+
+ return res;
+}
+
+/* Return a binfo describing the true type of object referenced by expression
+ REF if all component references access first ancestors. REF can consist of
+ a series of COMPONENT_REFs of with a declaration or an INDIREC_REF. It can
+ also be just a simple declaration, indirect reference or an SSA_NAME. If
+ the function discoveres an INIDRECT_REF or an SSA_NAME, it will assume that
+ the encapsulating type is described by KNOWN_BINFO or return NULL_TREE if
+ KNOWN_BINFO is NULL_TREE. Otherwise the first nonartifical field declaration
+ or the base declaration will be examined to get the encapsulating type. If
+ a COMPONENT_REF referencing an ancestor which is not the first one, this
+ function returns NULL_TREE and sets *try_multi to true. */
+
+static tree
+get_relevant_ref_binfo_single_inh (tree ref, tree known_binfo, bool *try_multi)
+{
+ while (true)
+ {
+ if (TREE_CODE (ref) == COMPONENT_REF)
+ {
+ tree par_type;
+ tree binfo, base_binfo;
+ tree field = TREE_OPERAND (ref, 1);
+
+ if (!DECL_ARTIFICIAL (field))
+ {
+ tree type = TREE_TYPE (field);
+ if (TREE_CODE (type) == RECORD_TYPE)
+ return TYPE_BINFO (type);
+ else
+ return NULL_TREE;
+ }
+
+ par_type = TREE_TYPE (TREE_OPERAND (ref, 0));
+ binfo = TYPE_BINFO (par_type);
+ if (!binfo
+ || BINFO_N_BASE_BINFOS (binfo) == 0)
+ {
+ if (try_multi)
+ *try_multi = 1;
+ return NULL_TREE;
+ }
+ base_binfo = BINFO_BASE_BINFO (binfo, 0);
+ if (TREE_TYPE (base_binfo) != TREE_TYPE (field))
+ {
+ if (try_multi)
+ *try_multi = 1;
+ return NULL_TREE;
+ }
+
+ ref = TREE_OPERAND (ref, 0);
+ }
+ else if (DECL_P (ref) && TREE_CODE (TREE_TYPE (ref)) == RECORD_TYPE)
+ return TYPE_BINFO (TREE_TYPE (ref));
+ else if (known_binfo
+ && (TREE_CODE (ref) == SSA_NAME
+ || TREE_CODE (ref) == INDIRECT_REF))
+ return known_binfo;
+ else
+ return NULL_TREE;
+ }
+}
-/* Fold a OBJ_TYPE_REF expression to the address of a function.
- KNOWN_TYPE carries the true type of OBJ_TYPE_REF_OBJECT(REF). Adapted
- from cp_fold_obj_type_ref, but it tolerates types with no binfo
- data. */
+
+/* Return a binfo describing the part of object referenced by expression REF.
+ This can and often is a base_binfo of a descendatn binfo. REF can consist of
+ a series of COMPONENT_REFs of with a declaration or an INDIREC_REF. It can
+ also be just a simple declaration, indirect reference or an SSA_NAME. If
+ the function discoveres an INIDRECT_REF or an SSA_NAME, it will assume that
+ the encapsulating type is described by KNOWN_BINFO or return NULL_TREE if
+ KNOWN_BINFO is NULL_TREE. Otherwise the first nonartifical field
+ declaration or the base declaration will be examined to get the
+ encapsulating type. */
+
+static tree
+get_relevant_ref_binfo_multi_inh (tree ref, tree known_binfo)
+{
+ if (DECL_P (ref) && TREE_CODE (TREE_TYPE (ref)) == RECORD_TYPE)
+ return TYPE_BINFO (TREE_TYPE (ref));
+ else if (TREE_CODE (ref) == COMPONENT_REF)
+ {
+ tree desc_binfo;
+ tree field = TREE_OPERAND (ref, 1);
+
+ if (!DECL_ARTIFICIAL (field))
+ {
+ tree type = TREE_TYPE (field);
+ if (TREE_CODE (type) == RECORD_TYPE)
+ return TYPE_BINFO (type);
+ else
+ return NULL_TREE;
+ }
+
+ desc_binfo = get_relevant_ref_binfo_multi_inh (TREE_OPERAND (ref, 0),
+ known_binfo);
+ if (!desc_binfo)
+ return NULL_TREE;
+ return get_base_binfo_for_type (desc_binfo, TREE_TYPE (field));
+ }
+ else if (known_binfo
+ && (TREE_CODE (ref) == SSA_NAME
+ || TREE_CODE (ref) == INDIRECT_REF))
+ return known_binfo;
+ else
+ return NULL_TREE;
+}
+
+/* Return a binfo describing the part of object referenced by expression REF
+ using both get_relevant_ref_binfo_single_inh and
+ get_relevant_ref_binfo_multi_inh in this particular order. */
tree
-gimple_fold_obj_type_ref (tree ref, tree known_type)
+gimple_get_relevant_ref_binfo (tree ref, tree known_binfo)
+{
+ bool try_multi = false;
+ tree binfo;
+
+ binfo = get_relevant_ref_binfo_single_inh (ref, known_binfo, &try_multi);
+ if (!binfo && try_multi)
+ binfo = get_relevant_ref_binfo_multi_inh (ref, known_binfo);
+ return binfo;
+}
+
+
+/* Fold a OBJ_TYPE_REF expression to the address of a function. TOKEN is
+ integer form of OBJ_TYPE_REF_TOKEN of the reference expression. KNOWN_BINFO
+ carries the binfo describing the true type of OBJ_TYPE_REF_OBJECT(REF). */
+
+tree
+gimple_fold_obj_type_ref_known_binfo (HOST_WIDE_INT token, tree known_binfo)
{
- HOST_WIDE_INT index;
HOST_WIDE_INT i;
- tree v;
- tree fndecl;
+ tree v, fndecl;
- if (TYPE_BINFO (known_type) == NULL_TREE)
+ /* If binfo flag 2 is not set, this binfo does not "have its own virtual
+ table" (according to cp/cp-tree.h) and cannot be safely used for
+ devirtualization. Purely empirical experience also shows that we can also
+ bail out if flag 5 is set. This test also probably works in lto. */
+ if (BINFO_FLAG_5 (known_binfo))
return NULL_TREE;
-
- v = BINFO_VIRTUALS (TYPE_BINFO (known_type));
- index = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
+ v = BINFO_VIRTUALS (known_binfo);
i = 0;
- while (i != index)
+ while (i != token)
{
i += (TARGET_VTABLE_USES_DESCRIPTORS
? TARGET_VTABLE_USES_DESCRIPTORS : 1);
@@ -4660,15 +4800,34 @@ gimple_fold_obj_type_ref (tree ref, tree
}
fndecl = TREE_VALUE (v);
+ return build_fold_addr_expr (fndecl);
+}
-#ifdef ENABLE_CHECKING
- gcc_assert (tree_int_cst_equal (OBJ_TYPE_REF_TOKEN (ref),
- DECL_VINDEX (fndecl)));
-#endif
- cgraph_node (fndecl)->local.vtable_method = true;
+/* Fold a OBJ_TYPE_REF expression to the address of a function. If KNOWN_TYPE
+ is not NULL_TREE, it is the true type of the outmost encapsulating object if
+ that comes from a pointer SSA_NAME. If the true outmost encapsulating type
+ can be determined from a declaration OBJ_TYPE_REF_OBJECT(REF), it is used
+ regardless of KNOWN_TYPE (which thuc can be NULL_TREE). */
- return build_fold_addr_expr (fndecl);
+tree
+gimple_fold_obj_type_ref (tree ref, tree known_type)
+{
+ tree obj = OBJ_TYPE_REF_OBJECT (ref);
+ tree known_binfo = known_type ? TYPE_BINFO (known_type) : NULL_TREE;
+ tree binfo;
+
+ if (TREE_CODE (obj) == ADDR_EXPR)
+ obj = TREE_OPERAND (obj, 0);
+
+ binfo = gimple_get_relevant_ref_binfo (obj, known_binfo);
+ if (binfo)
+ {
+ HOST_WIDE_INT token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
+ return gimple_fold_obj_type_ref_known_binfo (token, binfo);
+ }
+ else
+ return NULL_TREE;
}
#include "gt-gimple.h"
Index: icln/gcc/tree-ssa-ccp.c
===================================================================
--- icln.orig/gcc/tree-ssa-ccp.c
+++ icln/gcc/tree-ssa-ccp.c
@@ -3007,9 +3007,6 @@ fold_gimple_call (gimple_stmt_iterator *
}
else
{
- /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve
- here are when we've propagated the address of a decl into the
- object slot. */
/* ??? Should perhaps do this in fold proper. However, doing it
there requires that we create a new CALL_EXPR, and that requires
copying EH region info to the new node. Easier to just do it
@@ -3017,19 +3014,11 @@ fold_gimple_call (gimple_stmt_iterator *
/* ??? Is there a good reason not to do this in fold_stmt_inplace? */
callee = gimple_call_fn (stmt);
if (TREE_CODE (callee) == OBJ_TYPE_REF
- && lang_hooks.fold_obj_type_ref
- && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
- && DECL_P (TREE_OPERAND
- (OBJ_TYPE_REF_OBJECT (callee), 0)))
+ && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR)
{
tree t;
- /* ??? Caution: Broken ADDR_EXPR semantics means that
- looking at the type of the operand of the addr_expr
- can yield an array type. See silly exception in
- check_pointer_types_r. */
- t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
- t = lang_hooks.fold_obj_type_ref (callee, t);
+ t = gimple_fold_obj_type_ref (callee, NULL_TREE);
if (t)
{
gimple_call_set_fn (stmt, t);
Index: icln/gcc/gimple.h
===================================================================
--- icln.orig/gcc/gimple.h
+++ icln/gcc/gimple.h
@@ -864,7 +864,9 @@ unsigned get_gimple_rhs_num_ops (enum tr
#define gimple_alloc(c, n) gimple_alloc_stat (c, n MEM_STAT_INFO)
gimple gimple_alloc_stat (enum gimple_code, unsigned MEM_STAT_DECL);
const char *gimple_decl_printable_name (tree, int);
+tree gimple_get_relevant_ref_binfo (tree ref, tree known_binfo);
tree gimple_fold_obj_type_ref (tree, tree);
+tree gimple_fold_obj_type_ref_known_binfo (HOST_WIDE_INT, tree);
/* Returns true iff T is a valid GIMPLE statement. */
extern bool is_gimple_stmt (tree);
Index: icln/gcc/testsuite/g++.dg/otr-fold-1.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/otr-fold-1.C
@@ -0,0 +1,77 @@
+/* Verify that simple virtual calls are inlined even without early
+ inlining, even when a typecast to an ancestor is involved along the
+ way. */
+/* { dg-do run } */
+/* { dg-options "-O -fdump-tree-optimized-slim" } */
+
+extern "C" void abort (void);
+
+class Distraction
+{
+public:
+ float f;
+ double d;
+ Distraction ()
+ {
+ f = 8.3;
+ d = 10.2;
+ }
+ virtual float bar (float z);
+};
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+
+class B : public Distraction, public A
+{
+public:
+ virtual int foo (int i);
+};
+
+float Distraction::bar (float z)
+{
+ f += z;
+ return f/2;
+}
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+static int middleman_1 (class A *obj, int i)
+{
+ return obj->foo (i);
+}
+
+static int middleman_2 (class B *obj, int i)
+{
+ return middleman_1 (obj, i);
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+
+ if (middleman_2 (&b, get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "= B::foo" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
^ permalink raw reply [flat|nested] 23+ messages in thread
* [PATCH 2/6] Indirect call graph edges
2010-02-13 18:03 [PATCH 0/6] Cgraph changes and various devirtualizations Martin Jambor
` (4 preceding siblings ...)
2010-02-13 18:04 ` [PATCH 4/6] Remove unused ipa_note_param_call.called flag (approved) Martin Jambor
@ 2010-02-13 18:04 ` Martin Jambor
2010-02-13 18:17 ` Richard Guenther
2010-02-22 15:52 ` Jan Hubicka
5 siblings, 2 replies; 23+ messages in thread
From: Martin Jambor @ 2010-02-13 18:04 UTC (permalink / raw)
To: GCC Patches; +Cc: Jan Hubicka
[-- Attachment #1: indirect_cgraph_edges.diff --]
[-- Type: text/plain, Size: 52938 bytes --]
Hi,
this is a re-post of the same patch I already sent here in January.
There are only minor differences. I have renamed the flag
indirect_call to indirect_inlining_edge and changed its purpose to be
exactly that, an edge made direct by indirect inlining (it may go away
completely, I currently use it only for asserts in ipa-cp
devirtualization) and I have added a few things to cgraph node
dumping. Most importantly, I have re-worked streaming so that
information for indirect inlining associated with nodes is written to
the jump functions section again in order to allow the cgraph stream
to remain simple and concise (which means it cannot store trees).
The patch adds a new kind of edge to the call graph to represent
indirect calls with unknown callees (which we hope we can determine at
some stage) and uses them to replace ipa_param_call_notes in
ipa-prop.h. My immediate reason to do this is to move all the
information there from the notes because I will need them to be in
memory managed by the garbage collector (and did not want
ipa_node_params to become garbage collected) but in a broader sense
this is the right thing to do because it facilitates a more general
approach to keep information about such calls (ipa-cp jump functions
and the like) that is also consistent with how we do this for direct
edges.
The data structure layout (a flag and a pointer in struct cgraph_edge
to a another special structure) was really chosen by Honza. The
subsequent patches add some more stuff to cgraph_indirect_call_info so
it won't look this silly for long.
I have successfully bootstrapped and tested this beast on x86_84-linux
and would like to commit something along these lines when stage1 opens
again. Obviously, I welcome any comments.
Thanks,
Martin
2010-02-10 Martin Jambor <mjambor@suse.cz>
* cgraph.h (struct cgraph_node): New field indirect_calls.
(struct cgraph_indirect_call_info): New type.
(struct cgraph_edge): Removed field indirect_call. New fields
indirect_info, indirect_inlining_edge and indirect_unknown_callee.
(cgraph_create_indirect_edge): Declare.
(cgraph_make_edge_direct): Likewise.
(enum LTO_cgraph_tags): New item LTO_cgraph_indirect_edge.
* ipa-prop.h (struct ipa_param_call_note): Removed.
(struct ipa_node_params): Removed field param_calls.
* cgraph.c (cgraph_add_edge_to_call_site_hash): New function.
(cgraph_edge): Search also among the indirect edges, use
cgraph_add_edge_to_call_site_hash to add edges to the call site hash.
(cgraph_set_call_stmt): Possibly turn an indirect edge into a direct
one, use cgraph_add_edge_to_call_site_hash to add edges to the call
site hash.
(initialize_inline_failed): Assign a reason to indirect edges.
(cgraph_create_edge_1): New function.
(cgraph_create_edge): Moved some functionality to
cgraph_create_edge_1.
(cgraph_create_indirect_edge): New function.
(cgraph_edge_remove_callee): Add an assert checking for
non-indirectness.
(cgraph_edge_remove_caller): Special-case indirect edges.
(cgraph_remove_edge): Likewise.
(cgraph_set_edge_callee): New function.
(cgraph_redirect_edge_callee): Use cgraph_set_edge_callee.
(cgraph_make_edge_direct): New function.
(cgraph_update_edges_for_call_stmt_node): Do nothing only when also
the declaration of the call statement matches.
(cgraph_node_remove_callees): Special-case indirect edges.
(cgraph_clone_edge): Likewise.
(cgraph_clone_node): Clone also the indirect edges.
(dump_cgraph_node): Dump indirect_inlining_edge flag instead of
indirect_call, dump count of indirect_calls edges.
* ipa-prop.c (ipa_note_param_call): Create indirect edges instead of
creating notes. New parameter node.
(ipa_analyze_call_uses): New parameter node, pass it on to
ipa_note_param_call.
(ipa_analyze_stmt_uses): Likewise.
(ipa_analyze_params_uses): Pass node to ipa_analyze_stmt_uses.
(print_edge_addition_message): Work on edges rather than on notes.
(update_call_notes_after_inlining): Likewise.
(ipa_free_node_params_substructures): Do not free notes.
(ipa_node_duplication_hook): Do not duplicate notes.
(ipa_write_param_call_note): Removed.
(ipa_read_param_call_note): Removed.
(ipa_write_indirect_edge_info): New function.
(ipa_read_indirect_edge_info): Likewise.
(ipa_write_node_info): Do not stream notes, do stream information
in indirect edges.
(ipa_read_node_info): Likewise.
(lto_ipa_fixup_call_notes): Removed.
* ipa-cp.c (pass_ipa_cp): Set stmt_fixup to NULL.
* ipa-inline.c (pass_ipa_inline): Likewise.
* cgraphunit.c (verify_cgraph_node): Check also indirect edges.
* cif-code.def (INDIRECT_UNKNOWN_CALL): New reason.
* tree-inline.c (copy_bb): Removed an unnecessary double check for
is_gimple_call.
* tree-inline.c (get_indirect_callee_fndecl): Do not consider indirect
edges.
* lto-cgraph.c (output_outgoing_cgraph_edges): New function.
(output_cgraph): Stream also indirect edges.
(lto_output_edge): Added capability to stream indirect edges.
(input_edge): Likewise.
(input_cgraph_1): Likewise.
* testsuite/gcc.dg/lto/20091209-1_0.c: New testcase.
Index: icln/gcc/cgraph.h
===================================================================
--- icln.orig/gcc/cgraph.h
+++ icln/gcc/cgraph.h
@@ -184,6 +184,9 @@ struct GTY((chain_next ("%h.next"), chai
struct cgraph_edge *callers;
struct cgraph_node *next;
struct cgraph_node *previous;
+ /* List of edges representing indirect calls with a yet undetermined
+ caller. */
+ struct cgraph_edge *indirect_calls;
/* For nested functions points to function the node is nested in. */
struct cgraph_node *origin;
/* Points to first nested function, if any. */
@@ -311,6 +314,17 @@ typedef enum {
CIF_N_REASONS
} cgraph_inline_failed_t;
+/* Structure containing additional information about an indirect call. */
+
+struct GTY(()) cgraph_indirect_call_info
+{
+ /* Index of the parameter that is called. */
+ int param_index;
+
+ /* Whether this edge has already been looked at by indirect inlining. */
+ unsigned int inlining_processed : 1;
+};
+
struct GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) cgraph_edge {
/* Expected number of executions: calculated in profile.c. */
gcov_type count;
@@ -321,6 +335,8 @@ struct GTY((chain_next ("%h.next_caller"
struct cgraph_edge *prev_callee;
struct cgraph_edge *next_callee;
gimple call_stmt;
+ /* Additional information about an indirect call. Can be NULL for */
+ struct cgraph_indirect_call_info *indirect_info;
PTR GTY ((skip (""))) aux;
/* When equal to CIF_OK, inline this call. Otherwise, points to the
explanation why function was not inlined. */
@@ -336,8 +352,12 @@ struct GTY((chain_next ("%h.next_caller"
int uid;
/* Depth of loop nest, 1 means no loop nest. */
unsigned short int loop_nest;
- /* Whether this edge describes a call that was originally indirect. */
- unsigned int indirect_call : 1;
+ /* Whether this edge was created by indirect inlining. */
+ unsigned int indirect_inlining_edge : 1;
+ /* Whether this edge describes an inderect call with an undetermined
+ callee. */
+ unsigned int indirect_unknown_callee : 1;
+ /* Whether this edge is still a danglig */
/* True if the corresponding CALL stmt cannot be inlined. */
unsigned int call_stmt_cannot_inline_p : 1;
/* Can this call throw externally? */
@@ -435,7 +455,8 @@ void cgraph_node_remove_callees (struct
struct cgraph_edge *cgraph_create_edge (struct cgraph_node *,
struct cgraph_node *,
gimple, gcov_type, int, int);
-
+struct cgraph_edge *cgraph_create_indirect_edge (struct cgraph_node *, gimple,
+ gcov_type, int, int);
struct cgraph_node * cgraph_get_node (tree);
struct cgraph_node *cgraph_node (tree);
bool cgraph_same_body_alias (tree, tree);
@@ -461,6 +482,7 @@ struct cgraph_node * cgraph_clone_node (
int, bool, VEC(cgraph_edge_p,heap) *);
void cgraph_redirect_edge_callee (struct cgraph_edge *, struct cgraph_node *);
+void cgraph_make_edge_direct (struct cgraph_edge *, struct cgraph_node *);
struct cgraph_asm_node *cgraph_add_asm_node (tree);
@@ -628,6 +650,7 @@ enum LTO_cgraph_tags
LTO_cgraph_overwritable_node,
LTO_cgraph_unavail_node,
LTO_cgraph_edge,
+ LTO_cgraph_indirect_edge, /* edges with indirect_unknown_callee set */
LTO_cgraph_last_tag
};
Index: icln/gcc/ipa-prop.h
===================================================================
--- icln.orig/gcc/ipa-prop.h
+++ icln/gcc/ipa-prop.h
@@ -134,32 +134,6 @@ struct ipcp_lattice
tree constant;
};
-/* Each instance of the following structure describes a statement that calls a
- function parameter. Those referring to statements within the same function
- are linked in a list. */
-struct ipa_param_call_note
-{
- /* Expected number of executions: calculated in profile.c. */
- gcov_type count;
- /* Linked list's next */
- struct ipa_param_call_note *next;
- /* Statement that contains the call to the parameter above. */
- gimple stmt;
- /* When in LTO, we the above stmt will be NULL and we need an uid. */
- unsigned int lto_stmt_uid;
- /* Index of the parameter that is called. */
- int formal_id;
- /* Expected frequency of executions within the function. see cgraph_edge in
- cgraph.h for more on this. */
- int frequency;
- /* Depth of loop nest, 1 means no loop nest. */
- unsigned short int loop_nest;
- /* Set when we have already found the target to be a compile time constant
- and turned this into an edge or when the note was found unusable for some
- reason. */
- bool processed;
-};
-
/* Structure describing a single formal parameter. */
struct ipa_param_descriptor
{
@@ -185,8 +159,6 @@ struct ipa_node_params
/* Pointer to an array of structures describing individual formal
parameters. */
struct ipa_param_descriptor *params;
- /* List of structures enumerating calls to a formal parameter. */
- struct ipa_param_call_note *param_calls;
/* Only for versioned nodes this field would not be NULL,
it points to the node that IPA cp cloned from. */
struct cgraph_node *ipcp_orig_node;
Index: icln/gcc/cgraph.c
===================================================================
--- icln.orig/gcc/cgraph.c
+++ icln/gcc/cgraph.c
@@ -721,6 +721,19 @@ edge_eq (const void *x, const void *y)
return ((const struct cgraph_edge *) x)->call_stmt == y;
}
+/* Add call graph edge E to call site hash of its caller. */
+
+static inline void
+cgraph_add_edge_to_call_site_hash (struct cgraph_edge *e)
+{
+ void **slot;
+ slot = htab_find_slot_with_hash (e->caller->call_site_hash,
+ e->call_stmt,
+ htab_hash_pointer (e->call_stmt),
+ INSERT);
+ gcc_assert (!*slot);
+ *slot = e;
+}
/* Return the callgraph edge representing the GIMPLE_CALL statement
CALL_STMT. */
@@ -741,26 +754,28 @@ cgraph_edge (struct cgraph_node *node, g
solution. It is not good idea to add pointer into CALL_EXPR itself
because we want to make possible having multiple cgraph nodes representing
different clones of the same body before the body is actually cloned. */
- for (e = node->callees; e; e= e->next_callee)
+ for (e = node->callees; e; e = e->next_callee)
{
if (e->call_stmt == call_stmt)
break;
n++;
}
+ if (!e)
+ for (e = node->indirect_calls; e; e = e->next_callee)
+ {
+ if (e->call_stmt == call_stmt)
+ break;
+ n++;
+ }
+
if (n > 100)
{
node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
for (e2 = node->callees; e2; e2 = e2->next_callee)
- {
- void **slot;
- slot = htab_find_slot_with_hash (node->call_site_hash,
- e2->call_stmt,
- htab_hash_pointer (e2->call_stmt),
- INSERT);
- gcc_assert (!*slot);
- *slot = e2;
- }
+ cgraph_add_edge_to_call_site_hash (e2);
+ for (e2 = node->indirect_calls; e2; e2 = e2->next_callee)
+ cgraph_add_edge_to_call_site_hash (e2);
}
return e;
@@ -772,26 +787,31 @@ cgraph_edge (struct cgraph_node *node, g
void
cgraph_set_call_stmt (struct cgraph_edge *e, gimple new_stmt)
{
+ tree decl;
+
if (e->caller->call_site_hash)
{
htab_remove_elt_with_hash (e->caller->call_site_hash,
e->call_stmt,
htab_hash_pointer (e->call_stmt));
}
+
e->call_stmt = new_stmt;
+ if (e->indirect_unknown_callee
+ && (decl = gimple_call_fndecl (new_stmt)))
+ {
+ /* Constant propagation (and possibly also inlining?) can turn an
+ indirect call into a direct one. */
+ struct cgraph_node *new_callee = cgraph_node (decl);
+
+ cgraph_make_edge_direct (e, new_callee);
+ }
+
push_cfun (DECL_STRUCT_FUNCTION (e->caller->decl));
e->can_throw_external = stmt_can_throw_external (new_stmt);
pop_cfun ();
if (e->caller->call_site_hash)
- {
- void **slot;
- slot = htab_find_slot_with_hash (e->caller->call_site_hash,
- e->call_stmt,
- htab_hash_pointer
- (e->call_stmt), INSERT);
- gcc_assert (!*slot);
- *slot = e;
- }
+ cgraph_add_edge_to_call_site_hash (e);
}
/* Like cgraph_set_call_stmt but walk the clone tree and update all
@@ -893,7 +913,9 @@ initialize_inline_failed (struct cgraph_
{
struct cgraph_node *callee = e->callee;
- if (!callee->analyzed)
+ if (e->indirect_unknown_callee)
+ e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
+ else if (!callee->analyzed)
e->inline_failed = CIF_BODY_NOT_AVAILABLE;
else if (callee->local.redefined_extern_inline)
e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
@@ -905,15 +927,16 @@ initialize_inline_failed (struct cgraph_
e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
}
-/* Create edge from CALLER to CALLEE in the cgraph. */
-
-struct cgraph_edge *
-cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
- gimple call_stmt, gcov_type count, int freq, int nest)
+/* Allocate a cgraph_edge structure and fill it with data according to the
+ parameters ow which only CALLEE can be NULL (when creating an indirect call
+ edge). */
+
+static struct cgraph_edge *
+cgraph_create_edge_1 (struct cgraph_node *caller, struct cgraph_node *callee,
+ gimple call_stmt, gcov_type count, int freq, int nest)
{
struct cgraph_edge *edge;
-
/* LTO does not actually have access to the call_stmt since these
have not been loaded yet. */
if (call_stmt)
@@ -939,47 +962,84 @@ cgraph_create_edge (struct cgraph_node *
}
edge->aux = NULL;
-
edge->caller = caller;
edge->callee = callee;
+ edge->prev_caller = NULL;
+ edge->next_caller = NULL;
+ edge->prev_callee = NULL;
+ edge->next_callee = NULL;
+
+ edge->count = count;
+ gcc_assert (count >= 0);
+ edge->frequency = freq;
+ gcc_assert (freq >= 0);
+ gcc_assert (freq <= CGRAPH_FREQ_MAX);
+ edge->loop_nest = nest;
+
edge->call_stmt = call_stmt;
push_cfun (DECL_STRUCT_FUNCTION (caller->decl));
edge->can_throw_external
= call_stmt ? stmt_can_throw_external (call_stmt) : false;
pop_cfun ();
- edge->prev_caller = NULL;
+ edge->call_stmt_cannot_inline_p =
+ (call_stmt ? gimple_call_cannot_inline_p (call_stmt) : false);
+ if (call_stmt && caller->call_site_hash)
+ cgraph_add_edge_to_call_site_hash (edge);
+
+ edge->indirect_info = NULL;
+ edge->indirect_inlining_edge = 0;
+
+ return edge;
+}
+
+/* Create edge from CALLER to CALLEE in the cgraph. */
+
+struct cgraph_edge *
+cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
+ gimple call_stmt, gcov_type count, int freq, int nest)
+{
+ struct cgraph_edge *edge = cgraph_create_edge_1 (caller, callee, call_stmt,
+ count, freq, nest);
+
+ edge->indirect_unknown_callee = 0;
+ initialize_inline_failed (edge);
+
edge->next_caller = callee->callers;
if (callee->callers)
callee->callers->prev_caller = edge;
- edge->prev_callee = NULL;
edge->next_callee = caller->callees;
if (caller->callees)
caller->callees->prev_callee = edge;
caller->callees = edge;
callee->callers = edge;
- edge->count = count;
- gcc_assert (count >= 0);
- edge->frequency = freq;
- gcc_assert (freq >= 0);
- gcc_assert (freq <= CGRAPH_FREQ_MAX);
- edge->loop_nest = nest;
- edge->indirect_call = 0;
- edge->call_stmt_cannot_inline_p =
- (call_stmt ? gimple_call_cannot_inline_p (call_stmt) : false);
- if (call_stmt && caller->call_site_hash)
- {
- void **slot;
- slot = htab_find_slot_with_hash (caller->call_site_hash,
- edge->call_stmt,
- htab_hash_pointer
- (edge->call_stmt),
- INSERT);
- gcc_assert (!*slot);
- *slot = edge;
- }
+ return edge;
+}
+
+
+/* Create an indirect edge with a yet-undetermined callee where the call
+ statement destination is a formal parameter of the caller with index
+ PARAM_INDEX. */
+
+struct cgraph_edge *
+cgraph_create_indirect_edge (struct cgraph_node *caller, gimple call_stmt,
+ gcov_type count, int freq, int nest)
+{
+ struct cgraph_edge *edge = cgraph_create_edge_1 (caller, NULL, call_stmt,
+ count, freq, nest);
+
+ edge->indirect_unknown_callee = 1;
initialize_inline_failed (edge);
+ edge->indirect_info = GGC_NEW (struct cgraph_indirect_call_info);
+ edge->indirect_info->param_index = -1;
+ edge->indirect_info->inlining_processed = 0;
+
+ edge->next_callee = caller->indirect_calls;
+ if (caller->indirect_calls)
+ caller->indirect_calls->prev_callee = edge;
+ caller->indirect_calls = edge;
+
return edge;
}
@@ -988,6 +1048,7 @@ cgraph_create_edge (struct cgraph_node *
static inline void
cgraph_edge_remove_callee (struct cgraph_edge *e)
{
+ gcc_assert (!e->indirect_unknown_callee);
if (e->prev_caller)
e->prev_caller->next_caller = e->next_caller;
if (e->next_caller)
@@ -1006,7 +1067,12 @@ cgraph_edge_remove_caller (struct cgraph
if (e->next_callee)
e->next_callee->prev_callee = e->prev_callee;
if (!e->prev_callee)
- e->caller->callees = e->next_callee;
+ {
+ if (e->indirect_unknown_callee)
+ e->caller->indirect_calls = e->next_callee;
+ else
+ e->caller->callees = e->next_callee;
+ }
if (e->caller->call_site_hash)
htab_remove_elt_with_hash (e->caller->call_site_hash,
e->call_stmt,
@@ -1035,8 +1101,9 @@ cgraph_remove_edge (struct cgraph_edge *
/* Call all edge removal hooks. */
cgraph_call_edge_removal_hooks (e);
- /* Remove from callers list of the callee. */
- cgraph_edge_remove_callee (e);
+ if (!e->indirect_unknown_callee)
+ /* Remove from callers list of the callee. */
+ cgraph_edge_remove_callee (e);
/* Remove from callees list of the callers. */
cgraph_edge_remove_caller (e);
@@ -1045,6 +1112,20 @@ cgraph_remove_edge (struct cgraph_edge *
cgraph_free_edge (e);
}
+/* Set callee of call graph edge E and add it to the corresponding set of
+ callers. */
+
+static void
+cgraph_set_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
+{
+ e->prev_caller = NULL;
+ if (n->callers)
+ n->callers->prev_caller = e;
+ e->next_caller = n->callers;
+ n->callers = e;
+ e->callee = n;
+}
+
/* Redirect callee of E to N. The function does not update underlying
call expression. */
@@ -1055,12 +1136,37 @@ cgraph_redirect_edge_callee (struct cgra
cgraph_edge_remove_callee (e);
/* Insert to callers list of the new callee. */
- e->prev_caller = NULL;
- if (n->callers)
- n->callers->prev_caller = e;
- e->next_caller = n->callers;
- n->callers = e;
- e->callee = n;
+ cgraph_set_edge_callee (e, n);
+}
+
+/* Make an indirect EDGE with an unknown callee an ordinary edge leading to
+ CALLEE. */
+
+void
+cgraph_make_edge_direct (struct cgraph_edge *edge, struct cgraph_node *callee)
+{
+ edge->indirect_unknown_callee = 0;
+
+ /* Get the edge out of the indirect edge list. */
+ if (edge->prev_callee)
+ edge->prev_callee->next_callee = edge->next_callee;
+ if (edge->next_callee)
+ edge->next_callee->prev_callee = edge->prev_callee;
+ if (!edge->prev_callee)
+ edge->caller->indirect_calls = edge->next_callee;
+
+ /* Put it into the normal callee list */
+ edge->prev_callee = NULL;
+ edge->next_callee = edge->caller->callees;
+ if (edge->caller->callees)
+ edge->caller->callees->prev_callee = edge;
+ edge->caller->callees = edge;
+
+ /* Insert to callers list of the new callee. */
+ cgraph_set_edge_callee (edge, callee);
+
+ /* We need to re-determine the inlining status of the edge. */
+ initialize_inline_failed (edge);
}
@@ -1091,7 +1197,7 @@ cgraph_update_edges_for_call_stmt_node (
{
/* See if the call is already there. It might be because of indirect
inlining already found it. */
- if (new_call && e->callee->decl == new_call)
+ if (new_call && e->callee && e->callee->decl == new_call)
return;
/* Otherwise remove edge and create new one; we can't simply redirect
@@ -1169,7 +1275,8 @@ cgraph_node_remove_callees (struct cgrap
{
f = e->next_callee;
cgraph_call_edge_removal_hooks (e);
- cgraph_edge_remove_callee (e);
+ if (!e->indirect_unknown_callee)
+ cgraph_edge_remove_callee (e);
cgraph_free_edge (e);
}
node->callees = NULL;
@@ -1624,6 +1731,8 @@ void
dump_cgraph_node (FILE *f, struct cgraph_node *node)
{
struct cgraph_edge *edge;
+ int indirect_calls_count = 0;
+
fprintf (f, "%s/%i(%i)", cgraph_node_name (node), node->uid,
node->pid);
dump_addr (f, " @", (void *)node);
@@ -1697,8 +1806,8 @@ dump_cgraph_node (FILE *f, struct cgraph
edge->frequency / (double)CGRAPH_FREQ_BASE);
if (!edge->inline_failed)
fprintf(f, "(inlined) ");
- if (edge->indirect_call)
- fprintf(f, "(indirect) ");
+ if (edge->indirect_inlining_edge)
+ fprintf(f, "(indirect_inlining) ");
if (edge->can_throw_external)
fprintf(f, "(can throw external) ");
}
@@ -1710,8 +1819,8 @@ dump_cgraph_node (FILE *f, struct cgraph
edge->callee->uid);
if (!edge->inline_failed)
fprintf(f, "(inlined) ");
- if (edge->indirect_call)
- fprintf(f, "(indirect) ");
+ if (edge->indirect_inlining_edge)
+ fprintf(f, "(indirect_inlining) ");
if (edge->count)
fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
(HOST_WIDEST_INT)edge->count);
@@ -1725,6 +1834,12 @@ dump_cgraph_node (FILE *f, struct cgraph
}
fprintf (f, "\n");
+ for (edge = node->indirect_calls; edge; edge = edge->next_callee)
+ indirect_calls_count++;
+ if (indirect_calls_count)
+ fprintf (f, " has %i outgoing edges for indirect calls.\n",
+ indirect_calls_count);
+
if (node->same_body)
{
struct cgraph_node *n;
@@ -1844,11 +1959,30 @@ cgraph_clone_edge (struct cgraph_edge *e
freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
if (freq > CGRAPH_FREQ_MAX)
freq = CGRAPH_FREQ_MAX;
- new_edge = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
- e->loop_nest + loop_nest);
+
+ if (e->indirect_unknown_callee)
+ {
+ tree decl;
+
+ if (call_stmt && (decl = gimple_call_fndecl (call_stmt)))
+ {
+ struct cgraph_node *callee = cgraph_node (decl);
+ new_edge = cgraph_create_edge (n, callee, call_stmt, count, freq,
+ e->loop_nest + loop_nest);
+ }
+ else
+ {
+ new_edge = cgraph_create_indirect_edge (n, call_stmt, count, freq,
+ e->loop_nest + loop_nest);
+ new_edge->indirect_info->param_index = e->indirect_info->param_index;
+ }
+ }
+ else
+ new_edge = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
+ e->loop_nest + loop_nest);
new_edge->inline_failed = e->inline_failed;
- new_edge->indirect_call = e->indirect_call;
+ new_edge->indirect_inlining_edge = e->indirect_inlining_edge;
new_edge->lto_stmt_uid = stmt_uid;
if (update_original)
{
@@ -1918,6 +2052,10 @@ cgraph_clone_node (struct cgraph_node *n
cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
count_scale, freq, loop_nest, update_original);
+ for (e = n->indirect_calls; e; e = e->next_callee)
+ cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
+ count_scale, freq, loop_nest, update_original);
+
new_node->next_sibling_clone = n->clones;
if (n->clones)
n->clones->prev_sibling_clone = new_node;
Index: icln/gcc/ipa-prop.c
===================================================================
--- icln.orig/gcc/ipa-prop.c
+++ icln/gcc/ipa-prop.c
@@ -735,41 +735,36 @@ ipa_is_ssa_with_stmt_def (tree t)
return false;
}
-/* Creates a new note describing a call to a parameter number FORMAL_ID and
- attaches it to the linked list of INFO. It also sets the called flag of the
- parameter. STMT is the corresponding call statement. */
+/* Create a new indirect call graph edge describing a call to a parameter
+ number FORMAL_ID and and set the called flag of the parameter. NODE is the
+ caller and is described by INFO. STMT is the corresponding call
+ statement. */
static void
-ipa_note_param_call (struct ipa_node_params *info, int formal_id,
- gimple stmt)
+ipa_note_param_call (struct cgraph_node *node, struct ipa_node_params *info,
+ int formal_id, gimple stmt)
{
- struct ipa_param_call_note *note;
+ struct cgraph_edge *cs;
basic_block bb = gimple_bb (stmt);
+ int freq;
info->params[formal_id].called = 1;
- note = XCNEW (struct ipa_param_call_note);
- note->formal_id = formal_id;
- note->stmt = stmt;
- note->lto_stmt_uid = gimple_uid (stmt);
- note->count = bb->count;
- note->frequency = compute_call_stmt_bb_frequency (current_function_decl, bb);
- note->loop_nest = bb->loop_depth;
-
- note->next = info->param_calls;
- info->param_calls = note;
-
- return;
+ freq = compute_call_stmt_bb_frequency (current_function_decl, bb);
+ cs = cgraph_create_indirect_edge (node, stmt, bb->count, freq,
+ bb->loop_depth);
+ cs->indirect_info->param_index = formal_id;
}
-/* Analyze the CALL and examine uses of formal parameters of the caller
+/* Analyze the CALL and examine uses of formal parameters of the caller NODE
(described by INFO). Currently it checks whether the call calls a pointer
that is a formal parameter and if so, the parameter is marked with the
- called flag and a note describing the call is created. This is very simple
- for ordinary pointers represented in SSA but not-so-nice when it comes to
- member pointers. The ugly part of this function does nothing more than
- tries to match the pattern of such a call. An example of such a pattern is
- the gimple dump below, the call is on the last line:
+ called flag and a an indirect call graph edge describing the call is
+ created. This is very simple for ordinary pointers represented in SSA but
+ not-so-nice when it comes to member pointers. The ugly part of this
+ function does nothing more than tries to match the pattern of such a call.
+ An example of such a pattern is the gimple dump below, the call is on the
+ last line:
<bb 2>:
f$__delta_5 = f.__delta;
@@ -809,7 +804,8 @@ ipa_note_param_call (struct ipa_node_par
*/
static void
-ipa_analyze_call_uses (struct ipa_node_params *info, gimple call)
+ipa_analyze_call_uses (struct cgraph_node *node, struct ipa_node_params *info,
+ gimple call)
{
tree target = gimple_call_fn (call);
gimple def;
@@ -830,7 +826,7 @@ ipa_analyze_call_uses (struct ipa_node_p
/* assuming TREE_CODE (var) == PARM_DECL */
index = ipa_get_param_decl_index (info, var);
if (index >= 0)
- ipa_note_param_call (info, index, call);
+ ipa_note_param_call (node, info, index, call);
return;
}
@@ -927,20 +923,21 @@ ipa_analyze_call_uses (struct ipa_node_p
index = ipa_get_param_decl_index (info, rec);
if (index >= 0 && !ipa_is_param_modified (info, index))
- ipa_note_param_call (info, index, call);
+ ipa_note_param_call (node, info, index, call);
return;
}
-/* Analyze the statement STMT with respect to formal parameters (described in
- INFO) and their uses. Currently it only checks whether formal parameters
- are called. */
+/* Analyze the call statement STMT with respect to formal parameters (described
+ in INFO) of caller given by NODE. Currently it only checks whether formal
+ parameters are called. */
static void
-ipa_analyze_stmt_uses (struct ipa_node_params *info, gimple stmt)
+ipa_analyze_stmt_uses (struct cgraph_node *node, struct ipa_node_params *info,
+ gimple stmt)
{
if (is_gimple_call (stmt))
- ipa_analyze_call_uses (info, stmt);
+ ipa_analyze_call_uses (node, info, stmt);
}
/* Scan the function body of NODE and inspect the uses of formal parameters.
@@ -965,7 +962,7 @@ ipa_analyze_params_uses (struct cgraph_n
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
- ipa_analyze_stmt_uses (info, stmt);
+ ipa_analyze_stmt_uses (node, info, stmt);
}
}
@@ -1021,9 +1018,8 @@ update_jump_functions_after_inlining (st
by JFUNC. NODE is the node where the call is. */
static void
-print_edge_addition_message (FILE *f, struct ipa_param_call_note *nt,
- struct ipa_jump_func *jfunc,
- struct cgraph_node *node)
+print_edge_addition_message (FILE *f, struct cgraph_edge *e,
+ struct ipa_jump_func *jfunc)
{
fprintf (f, "ipa-prop: Discovered an indirect call to a known target (");
if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
@@ -1034,8 +1030,8 @@ print_edge_addition_message (FILE *f, st
else
print_node_brief(f, "", jfunc->value.constant, 0);
- fprintf (f, ") in %s: ", cgraph_node_name (node));
- print_gimple_stmt (f, nt->stmt, 2, TDF_SLIM);
+ fprintf (f, ") in %s: ", cgraph_node_name (e->caller));
+ print_gimple_stmt (f, e->call_stmt, 2, TDF_SLIM);
}
/* Update the param called notes associated with NODE when CS is being inlined,
@@ -1049,37 +1045,43 @@ update_call_notes_after_inlining (struct
struct cgraph_node *node,
VEC (cgraph_edge_p, heap) **new_edges)
{
- struct ipa_node_params *info = IPA_NODE_REF (node);
struct ipa_edge_args *top = IPA_EDGE_REF (cs);
- struct ipa_param_call_note *nt;
+ struct cgraph_edge *ie, *next_ie;
bool res = false;
- for (nt = info->param_calls; nt; nt = nt->next)
+ ipa_check_create_edge_args ();
+
+ for (ie = node->indirect_calls; ie; ie = next_ie)
{
+ struct cgraph_indirect_call_info *ici = ie->indirect_info;
struct ipa_jump_func *jfunc;
- if (nt->processed)
+ next_ie = ie->next_callee;
+ if (ici->inlining_processed)
continue;
+ /* If we ever use indirect edges for anything other than indirect
+ inlining, we will need to skip those with negative param_indices. */
+ gcc_assert (ici->param_index >= 0);
+
/* We must check range due to calls with variable number of arguments: */
- if (nt->formal_id >= ipa_get_cs_argument_count (top))
+ if (ici->param_index >= ipa_get_cs_argument_count (top))
{
- nt->processed = true;
+ ici->inlining_processed = true;
continue;
}
- jfunc = ipa_get_ith_jump_func (top, nt->formal_id);
+ jfunc = ipa_get_ith_jump_func (top, ici->param_index);
if (jfunc->type == IPA_JF_PASS_THROUGH
&& jfunc->value.pass_through.operation == NOP_EXPR)
- nt->formal_id = jfunc->value.pass_through.formal_id;
+ ici->param_index = jfunc->value.pass_through.formal_id;
else if (jfunc->type == IPA_JF_CONST
|| jfunc->type == IPA_JF_CONST_MEMBER_PTR)
{
struct cgraph_node *callee;
- struct cgraph_edge *new_indirect_edge;
tree decl;
- nt->processed = true;
+ ici->inlining_processed = true;
if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
decl = jfunc->value.member_cst.pfn;
else
@@ -1097,16 +1099,12 @@ update_call_notes_after_inlining (struct
res = true;
if (dump_file)
- print_edge_addition_message (dump_file, nt, jfunc, node);
+ print_edge_addition_message (dump_file, ie, jfunc);
- new_indirect_edge = cgraph_create_edge (node, callee, nt->stmt,
- nt->count, nt->frequency,
- nt->loop_nest);
- new_indirect_edge->lto_stmt_uid = nt->lto_stmt_uid;
- new_indirect_edge->indirect_call = 1;
- ipa_check_create_edge_args ();
+ cgraph_make_edge_direct (ie, callee);
+ ie->indirect_inlining_edge = 1;
if (new_edges)
- VEC_safe_push (cgraph_edge_p, heap, *new_edges, new_indirect_edge);
+ VEC_safe_push (cgraph_edge_p, heap, *new_edges, ie);
top = IPA_EDGE_REF (cs);
}
else
@@ -1114,9 +1112,10 @@ update_call_notes_after_inlining (struct
/* Ancestor jum functions and pass theoughs with operations should
not be used on parameters that then get called. */
gcc_assert (jfunc->type == IPA_JF_UNKNOWN);
- nt->processed = true;
+ ici->inlining_processed = true;
}
}
+
return res;
}
@@ -1208,13 +1207,6 @@ ipa_free_node_params_substructures (stru
if (info->params)
free (info->params);
- while (info->param_calls)
- {
- struct ipa_param_call_note *note = info->param_calls;
- info->param_calls = note->next;
- free (note);
- }
-
memset (info, 0, sizeof (*info));
}
@@ -1314,7 +1306,6 @@ ipa_node_duplication_hook (struct cgraph
__attribute__((unused)) void *data)
{
struct ipa_node_params *old_info, *new_info;
- struct ipa_param_call_note *note;
int param_count;
ipa_check_create_node_params ();
@@ -1328,17 +1319,6 @@ ipa_node_duplication_hook (struct cgraph
sizeof (struct ipa_param_descriptor) * param_count);
new_info->ipcp_orig_node = old_info->ipcp_orig_node;
new_info->count_scale = old_info->count_scale;
-
- for (note = old_info->param_calls; note; note = note->next)
- {
- struct ipa_param_call_note *nn;
-
- nn = (struct ipa_param_call_note *)
- xcalloc (1, sizeof (struct ipa_param_call_note));
- memcpy (nn, note, sizeof (struct ipa_param_call_note));
- nn->next = new_info->param_calls;
- new_info->param_calls = nn;
- }
}
/* Register our cgraph hooks if they are not already there. */
@@ -1964,40 +1944,40 @@ ipa_read_jump_function (struct lto_input
}
}
-/* Stream out a parameter call note. */
+/* Stream out parts of cgraph_indirect_call_info corresponding to CS that are
+ relevant to indirect inlining to OB. */
static void
-ipa_write_param_call_note (struct output_block *ob,
- struct ipa_param_call_note *note)
+ipa_write_indirect_edge_info (struct output_block *ob,
+ struct cgraph_edge *cs)
{
- gcc_assert (!note->processed);
- lto_output_uleb128_stream (ob->main_stream, gimple_uid (note->stmt));
- lto_output_sleb128_stream (ob->main_stream, note->formal_id);
- lto_output_sleb128_stream (ob->main_stream, note->count);
- lto_output_sleb128_stream (ob->main_stream, note->frequency);
- lto_output_sleb128_stream (ob->main_stream, note->loop_nest);
+ struct cgraph_indirect_call_info *ii = cs->indirect_info;
+ struct bitpack_d *bp;
+
+ lto_output_sleb128_stream (ob->main_stream, ii->param_index);
+ bp = bitpack_create ();
+ bp_pack_value (bp, ii->inlining_processed, 1);
+ lto_output_bitpack (ob->main_stream, bp);
+ bitpack_delete (bp);
}
-/* Read in a parameter call note. */
+/* Read in parts of cgraph_indirect_call_info corresponding to CS that are
+ relevant to indirect inlining from IB. */
static void
-ipa_read_param_call_note (struct lto_input_block *ib,
- struct ipa_node_params *info)
-
+ipa_read_indirect_edge_info (struct lto_input_block *ib,
+ struct data_in *data_in ATTRIBUTE_UNUSED,
+ struct cgraph_edge *cs)
{
- struct ipa_param_call_note *note = XCNEW (struct ipa_param_call_note);
-
- note->lto_stmt_uid = (unsigned int) lto_input_uleb128 (ib);
- note->formal_id = (int) lto_input_sleb128 (ib);
- note->count = (gcov_type) lto_input_sleb128 (ib);
- note->frequency = (int) lto_input_sleb128 (ib);
- note->loop_nest = (int) lto_input_sleb128 (ib);
+ struct cgraph_indirect_call_info *ii = cs->indirect_info;
+ struct bitpack_d *bp;
- note->next = info->param_calls;
- info->param_calls = note;
+ ii->param_index = (int) lto_input_sleb128 (ib);
+ bp = lto_input_bitpack (ib);
+ ii->inlining_processed = bp_unpack_value (bp, 1);
+ bitpack_delete (bp);
}
-
/* Stream out NODE info to OB. */
static void
@@ -2009,8 +1989,6 @@ ipa_write_node_info (struct output_block
int j;
struct cgraph_edge *e;
struct bitpack_d *bp;
- int note_count = 0;
- struct ipa_param_call_note *note;
encoder = ob->decl_state->cgraph_node_encoder;
node_ref = lto_cgraph_encoder_encode (encoder, node);
@@ -2024,10 +2002,7 @@ ipa_write_node_info (struct output_block
gcc_assert (!info->node_enqueued);
gcc_assert (!info->ipcp_orig_node);
for (j = 0; j < ipa_get_param_count (info); j++)
- {
- bp_pack_value (bp, info->params[j].modified, 1);
- bp_pack_value (bp, info->params[j].called, 1);
- }
+ bp_pack_value (bp, info->params[j].modified, 1);
lto_output_bitpack (ob->main_stream, bp);
bitpack_delete (bp);
for (e = node->callees; e; e = e->next_callee)
@@ -2039,12 +2014,8 @@ ipa_write_node_info (struct output_block
for (j = 0; j < ipa_get_cs_argument_count (args); j++)
ipa_write_jump_function (ob, ipa_get_ith_jump_func (args, j));
}
-
- for (note = info->param_calls; note; note = note->next)
- note_count++;
- lto_output_uleb128_stream (ob->main_stream, note_count);
- for (note = info->param_calls; note; note = note->next)
- ipa_write_param_call_note (ob, note);
+ for (e = node->indirect_calls; e; e = e->next_callee)
+ ipa_write_indirect_edge_info (ob, e);
}
/* Srtream in NODE info from IB. */
@@ -2057,7 +2028,6 @@ ipa_read_node_info (struct lto_input_blo
int k;
struct cgraph_edge *e;
struct bitpack_d *bp;
- int i, note_count;
ipa_initialize_node_params (node);
@@ -2071,10 +2041,7 @@ ipa_read_node_info (struct lto_input_blo
}
info->node_enqueued = false;
for (k = 0; k < ipa_get_param_count (info); k++)
- {
- info->params[k].modified = bp_unpack_value (bp, 1);
- info->params[k].called = bp_unpack_value (bp, 1);
- }
+ info->params[k].modified = bp_unpack_value (bp, 1);
bitpack_delete (bp);
for (e = node->callees; e; e = e->next_callee)
{
@@ -2090,10 +2057,8 @@ ipa_read_node_info (struct lto_input_blo
for (k = 0; k < ipa_get_cs_argument_count (args); k++)
ipa_read_jump_function (ib, ipa_get_ith_jump_func (args, k), data_in);
}
-
- note_count = lto_input_uleb128 (ib);
- for (i = 0; i < note_count; i++)
- ipa_read_param_call_note (ib, info);
+ for (e = node->indirect_calls; e; e = e->next_callee)
+ ipa_read_indirect_edge_info (ib, data_in, e);
}
/* Write jump functions for nodes in SET. */
@@ -2218,29 +2183,3 @@ ipa_update_after_lto_read (void)
}
}
}
-
-/* Walk param call notes of NODE and set their call statements given the uid
- stored in each note and STMTS which is an array of statements indexed by the
- uid. */
-
-void
-lto_ipa_fixup_call_notes (struct cgraph_node *node, gimple *stmts)
-{
- struct ipa_node_params *info;
- struct ipa_param_call_note *note;
-
- ipa_check_create_node_params ();
- info = IPA_NODE_REF (node);
- note = info->param_calls;
- /* If there are no notes or they have already been fixed up (the same fixup
- is called for both inlining and ipa-cp), there's nothing to do. */
- if (!note || note->stmt)
- return;
-
- do
- {
- note->stmt = stmts[note->lto_stmt_uid];
- note = note->next;
- }
- while (note);
-}
Index: icln/gcc/ipa-cp.c
===================================================================
--- icln.orig/gcc/ipa-cp.c
+++ icln/gcc/ipa-cp.c
@@ -1332,7 +1332,7 @@ struct ipa_opt_pass_d pass_ipa_cp =
ipcp_write_summary, /* write_summary */
ipcp_read_summary, /* read_summary */
NULL, /* function_read_summary */
- lto_ipa_fixup_call_notes, /* stmt_fixup */
+ NULL, /* stmt_fixup */
0, /* TODOs */
NULL, /* function_transform */
NULL, /* variable_transform */
Index: icln/gcc/ipa-inline.c
===================================================================
--- icln.orig/gcc/ipa-inline.c
+++ icln/gcc/ipa-inline.c
@@ -2066,7 +2066,7 @@ struct ipa_opt_pass_d pass_ipa_inline =
inline_write_summary, /* write_summary */
inline_read_summary, /* read_summary */
NULL, /* function_read_summary */
- lto_ipa_fixup_call_notes, /* stmt_fixup */
+ NULL, /* stmt_fixup */
0, /* TODOs */
inline_transform, /* function_transform */
NULL, /* variable_transform */
Index: icln/gcc/cgraphunit.c
===================================================================
--- icln.orig/gcc/cgraphunit.c
+++ icln/gcc/cgraphunit.c
@@ -607,6 +607,24 @@ verify_cgraph_node (struct cgraph_node *
error ("Inline clone is needed");
error_found = true;
}
+ for (e = node->indirect_calls; e; e = e->next_callee)
+ {
+ if (e->aux)
+ {
+ error ("aux field set for indirect edge from %s",
+ identifier_to_locale (cgraph_node_name (e->caller)));
+ error_found = true;
+ }
+ if (!e->indirect_unknown_callee
+ || !e->indirect_info)
+ {
+ error ("An indirect edge from %s is not marked as indirect or has "
+ "associated indirect_info, the corresponding statement is: ",
+ identifier_to_locale (cgraph_node_name (e->caller)));
+ debug_gimple_stmt (e->call_stmt);
+ error_found = true;
+ }
+ }
for (e = node->callers; e; e = e->next_caller)
{
if (e->count < 0)
@@ -733,10 +751,10 @@ verify_cgraph_node (struct cgraph_node *
gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
- tree decl;
- if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
+ if (is_gimple_call (stmt))
{
struct cgraph_edge *e = cgraph_edge (node, stmt);
+ tree decl = gimple_call_fndecl (stmt);
if (e)
{
if (e->aux)
@@ -745,25 +763,38 @@ verify_cgraph_node (struct cgraph_node *
debug_gimple_stmt (stmt);
error_found = true;
}
- if (e->callee->same_body_alias)
+ if (!e->indirect_unknown_callee)
{
- error ("edge points to same body alias:");
- debug_tree (e->callee->decl);
- error_found = true;
+ if (e->callee->same_body_alias)
+ {
+ error ("edge points to same body alias:");
+ debug_tree (e->callee->decl);
+ error_found = true;
+ }
+ else if (!node->global.inlined_to
+ && !e->callee->global.inlined_to
+ && decl
+ && !clone_of_p (cgraph_node (decl),
+ e->callee))
+ {
+ error ("edge points to wrong declaration:");
+ debug_tree (e->callee->decl);
+ fprintf (stderr," Instead of:");
+ debug_tree (decl);
+ error_found = true;
+ }
}
- else if (!node->global.inlined_to
- && !e->callee->global.inlined_to
- && !clone_of_p (cgraph_node (decl), e->callee))
+ else if (decl)
{
- error ("edge points to wrong declaration:");
- debug_tree (e->callee->decl);
- fprintf (stderr," Instead of:");
- debug_tree (decl);
+ error ("an indirect edge with unknown callee "
+ "corresponding to a call_stmt with "
+ "a known declaration:");
error_found = true;
+ debug_gimple_stmt (e->call_stmt);
}
e->aux = (void *)1;
}
- else
+ else if (decl)
{
error ("missing callgraph edge for call stmt:");
debug_gimple_stmt (stmt);
@@ -779,7 +810,7 @@ verify_cgraph_node (struct cgraph_node *
for (e = node->callees; e; e = e->next_callee)
{
- if (!e->aux && !e->indirect_call)
+ if (!e->aux)
{
error ("edge %s->%s has no corresponding call_stmt",
identifier_to_locale (cgraph_node_name (e->caller)),
@@ -787,6 +818,17 @@ verify_cgraph_node (struct cgraph_node *
debug_gimple_stmt (e->call_stmt);
error_found = true;
}
+ e->aux = 0;
+ }
+ for (e = node->indirect_calls; e; e = e->next_callee)
+ {
+ if (!e->aux)
+ {
+ error ("an indirect edge from %s has no corresponding call_stmt",
+ identifier_to_locale (cgraph_node_name (e->caller)));
+ debug_gimple_stmt (e->call_stmt);
+ error_found = true;
+ }
e->aux = 0;
}
}
Index: icln/gcc/cif-code.def
===================================================================
--- icln.orig/gcc/cif-code.def
+++ icln/gcc/cif-code.def
@@ -84,3 +84,7 @@ DEFCIFCODE(MISMATCHED_ARGUMENTS, N_("mis
/* Call was originally indirect. */
DEFCIFCODE(ORIGINALLY_INDIRECT_CALL,
N_("originally indirect function call not considered for inlining"))
+
+/* Ths edge represents an indirect edge with a yet-undetermined callee . */
+DEFCIFCODE(INDIRECT_UNKNOWN_CALL,
+ N_("indirect function call with a yet undetermined callee"))
Index: icln/gcc/tree-inline.c
===================================================================
--- icln.orig/gcc/tree-inline.c
+++ icln/gcc/tree-inline.c
@@ -1674,9 +1674,8 @@ copy_bb (copy_body_data *id, basic_block
/* Constant propagation on argument done during inlining
may create new direct call. Produce an edge for it. */
if ((!edge
- || (edge->indirect_call
+ || (edge->indirect_inlining_edge
&& id->transform_call_graph_edges == CB_CGE_MOVE_CLONES))
- && is_gimple_call (stmt)
&& (fn = gimple_call_fndecl (stmt)) != NULL)
{
struct cgraph_node *dest = cgraph_node (fn);
@@ -3452,7 +3451,7 @@ get_indirect_callee_fndecl (struct cgrap
struct cgraph_edge *cs;
cs = cgraph_edge (node, stmt);
- if (cs)
+ if (cs && !cs->indirect_unknown_callee)
return cs->callee->decl;
return NULL_TREE;
@@ -3535,7 +3534,7 @@ expand_call_inline (basic_block bb, gimp
/* If this call was originally indirect, we do not want to emit any
inlining related warnings or sorry messages because there are no
guarantees regarding those. */
- if (cg_edge->indirect_call)
+ if (cg_edge->indirect_inlining_edge)
goto egress;
if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn))
Index: icln/gcc/lto-cgraph.c
===================================================================
--- icln.orig/gcc/lto-cgraph.c
+++ icln/gcc/lto-cgraph.c
@@ -139,15 +139,21 @@ lto_output_edge (struct lto_simple_outpu
intptr_t ref;
struct bitpack_d *bp;
- lto_output_uleb128_stream (ob->main_stream, LTO_cgraph_edge);
+ if (edge->indirect_unknown_callee)
+ lto_output_uleb128_stream (ob->main_stream, LTO_cgraph_indirect_edge);
+ else
+ lto_output_uleb128_stream (ob->main_stream, LTO_cgraph_edge);
ref = lto_cgraph_encoder_lookup (encoder, edge->caller);
gcc_assert (ref != LCC_NOT_FOUND);
lto_output_sleb128_stream (ob->main_stream, ref);
- ref = lto_cgraph_encoder_lookup (encoder, edge->callee);
- gcc_assert (ref != LCC_NOT_FOUND);
- lto_output_sleb128_stream (ob->main_stream, ref);
+ if (!edge->indirect_unknown_callee)
+ {
+ ref = lto_cgraph_encoder_lookup (encoder, edge->callee);
+ gcc_assert (ref != LCC_NOT_FOUND);
+ lto_output_sleb128_stream (ob->main_stream, ref);
+ }
lto_output_sleb128_stream (ob->main_stream, edge->count);
@@ -157,7 +163,7 @@ lto_output_edge (struct lto_simple_outpu
bp_pack_value (bp, edge->inline_failed, HOST_BITS_PER_INT);
bp_pack_value (bp, edge->frequency, HOST_BITS_PER_INT);
bp_pack_value (bp, edge->loop_nest, 30);
- bp_pack_value (bp, edge->indirect_call, 1);
+ bp_pack_value (bp, edge->indirect_inlining_edge, 1);
bp_pack_value (bp, edge->call_stmt_cannot_inline_p, 1);
bp_pack_value (bp, edge->can_throw_external, 1);
lto_output_bitpack (ob->main_stream, bp);
@@ -371,6 +377,24 @@ output_profile_summary (struct lto_simpl
lto_output_uleb128_stream (ob->main_stream, 0);
}
+/* Output all callees or indirect outgoing edges. EDGE must be the first such
+ edge. */
+
+static void
+output_outgoing_cgraph_edges (struct cgraph_edge *edge,
+ struct lto_simple_output_block *ob,
+ lto_cgraph_encoder_t encoder)
+{
+ if (!edge)
+ return;
+
+ /* Output edges in backward direction, so the reconstructed callgraph match
+ and it is easy to associate call sites in the IPA pass summaries. */
+ while (edge->next_callee)
+ edge = edge->next_callee;
+ for (; edge; edge = edge->prev_callee)
+ lto_output_edge (ob, edge, encoder);
+}
/* Output the part of the cgraph in SET. */
@@ -460,16 +484,8 @@ output_cgraph (cgraph_node_set set)
for (csi = csi_start (set); !csi_end_p (csi); csi_next (&csi))
{
node = csi_node (csi);
- if (node->callees)
- {
- /* Output edges in backward direction, so the reconstructed callgraph
- match and it is easy to associate call sites in the IPA pass summaries. */
- edge = node->callees;
- while (edge->next_callee)
- edge = edge->next_callee;
- for (; edge; edge = edge->prev_callee)
- lto_output_edge (ob, edge, encoder);
- }
+ output_outgoing_cgraph_edges (node->callees, ob, encoder);
+ output_outgoing_cgraph_edges (node->indirect_calls, ob, encoder);
}
lto_output_uleb128_stream (ob->main_stream, 0);
@@ -657,11 +673,14 @@ input_node (struct lto_file_decl_data *f
}
-/* Read an edge from IB. NODES points to a vector of previously read
- nodes for decoding caller and callee of the edge to be read. */
+/* Read an edge from IB. NODES points to a vector of previously read nodes for
+ decoding caller and callee of the edge to be read. If INDIRECT is true, the
+ edge being read is indirect (in the sense that it has
+ indirect_unknown_callee set). */
static void
-input_edge (struct lto_input_block *ib, VEC(cgraph_node_ptr, heap) *nodes)
+input_edge (struct lto_input_block *ib, VEC(cgraph_node_ptr, heap) *nodes,
+ bool indirect)
{
struct cgraph_node *caller, *callee;
struct cgraph_edge *edge;
@@ -677,9 +696,14 @@ input_edge (struct lto_input_block *ib,
if (caller == NULL || caller->decl == NULL_TREE)
internal_error ("bytecode stream: no caller found while reading edge");
- callee = VEC_index (cgraph_node_ptr, nodes, lto_input_sleb128 (ib));
- if (callee == NULL || callee->decl == NULL_TREE)
- internal_error ("bytecode stream: no callee found while reading edge");
+ if (!indirect)
+ {
+ callee = VEC_index (cgraph_node_ptr, nodes, lto_input_sleb128 (ib));
+ if (callee == NULL || callee->decl == NULL_TREE)
+ internal_error ("bytecode stream: no callee found while reading edge");
+ }
+ else
+ callee = NULL;
count = (gcov_type) lto_input_sleb128 (ib);
@@ -697,10 +721,14 @@ input_edge (struct lto_input_block *ib,
|| caller_resolution == LDPR_PREEMPTED_IR)
return;
- edge = cgraph_create_edge (caller, callee, NULL, count, freq, nest);
+ if (indirect)
+ edge = cgraph_create_indirect_edge (caller, NULL, count, freq, nest);
+ else
+ edge = cgraph_create_edge (caller, callee, NULL, count, freq, nest);
+
+ edge->indirect_inlining_edge = bp_unpack_value (bp, 1);
edge->lto_stmt_uid = stmt_id;
edge->inline_failed = inline_failed;
- edge->indirect_call = bp_unpack_value (bp, 1);
edge->call_stmt_cannot_inline_p = bp_unpack_value (bp, 1);
edge->can_throw_external = bp_unpack_value (bp, 1);
bitpack_delete (bp);
@@ -723,7 +751,9 @@ input_cgraph_1 (struct lto_file_decl_dat
while (tag)
{
if (tag == LTO_cgraph_edge)
- input_edge (ib, nodes);
+ input_edge (ib, nodes, false);
+ else if (tag == LTO_cgraph_indirect_edge)
+ input_edge (ib, nodes, true);
else
{
node = input_node (file_data, ib, tag);
Index: icln/gcc/lto-streamer-in.c
===================================================================
--- icln.orig/gcc/lto-streamer-in.c
+++ icln/gcc/lto-streamer-in.c
@@ -1220,6 +1220,8 @@ fixup_call_stmt_edges_1 (struct cgraph_n
struct cgraph_edge *cedge;
for (cedge = node->callees; cedge; cedge = cedge->next_callee)
cedge->call_stmt = stmts[cedge->lto_stmt_uid];
+ for (cedge = node->indirect_calls; cedge; cedge = cedge->next_callee)
+ cedge->call_stmt = stmts[cedge->lto_stmt_uid];
}
/* Fixup call_stmt pointers in NODE and all clones. */
Index: icln/gcc/testsuite/gcc.dg/lto/20091209-1_0.c
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/gcc.dg/lto/20091209-1_0.c
@@ -0,0 +1,23 @@
+/* Stream an indirect edge in and out. */
+
+/* { dg-lto-do link } */
+/* { dg-lto-options {{ -O3 -fno-early-inlining -flto }} } */
+
+volatile int something;
+
+static void hooray ()
+{
+ something = 1;
+}
+
+static void hiphip (void (*f)())
+{
+ something = 2;
+ f ();
+}
+
+int main (int argc, int *argv[])
+{
+ hiphip (hooray);
+ return 0;
+}
^ permalink raw reply [flat|nested] 23+ messages in thread
* [PATCH 6/6] Devirtualization in ipa-cp
2010-02-13 18:03 [PATCH 0/6] Cgraph changes and various devirtualizations Martin Jambor
2010-02-13 18:03 ` [PATCH 1/6] Clarify edge redirection for inline clones Martin Jambor
@ 2010-02-13 18:04 ` Martin Jambor
2010-02-22 16:37 ` Jan Hubicka
2010-02-13 18:04 ` [PATCH 3/6] Folding of virtual calls Martin Jambor
` (3 subsequent siblings)
5 siblings, 1 reply; 23+ messages in thread
From: Martin Jambor @ 2010-02-13 18:04 UTC (permalink / raw)
To: GCC Patches; +Cc: Jan Hubicka
[-- Attachment #1: ipa-cp-devirtualization.diff --]
[-- Type: text/plain, Size: 32751 bytes --]
Hi,
this patch implements IPA devirtualization outside inlining. It is
based on IPA-CP and so the called virtual method must be known and the
same in all contexts in which the caller function is invoked in order
to be inlined.
This is the first time I post this patch. It works in the sense that
it passes bootstrap and regression tests but is still work in progress
in a way because I'd like to place a hard limit on maximum size of
types vector in ipa_param_descriptor which is still to be determined
experimentally. The patch might also introduce too many needless
virtual clones. While many unnecessary clones cannot be avoided, I
might try to get rid off at least those where it is easy. It depends
on how many we'll have.
Comments welcome, I'll seek to commit something quite similar to this
(with the changes outlined above) in stage1.
Thanks,
Martin
2010-02-10 Martin Jambor <mjambor@suse.cz>
* ipa-prop.h (enum ipa_lattice_type): Changed comments.
(struct ipa_param_descriptor): New fields types and
cannot_devirtualize.
(ipa_param_cannot_devirtualize_p): New function.
(ipa_param_types_vec_empty): Likewise.
(ipa_make_edge_direct_to_target): Declare.
(ipa_get_binfo_at_offset): Likewise.
* ipa-cp.c: Fixed first stage driver name in initial comment.
(ipcp_analyze_node): Call ipa_analyze_params_uses.
(ipcp_print_all_lattices): Print devirtualization info.
(ipa_set_param_cannot_devirtualize): New function.
(ipcp_initialize_node_lattices): Set cannot_devirtualize when setting
lattice to BOTTOM.
(ipcp_init_stage): Merged into...
(ipcp_generate_summary): ...its caller.
(ipcp_change_tops_to_bottom): Also process type lists.
(ipcp_add_param_type): New function.
(ipcp_copy_types): Likewise.
(ipcp_propagate_types): Likewise.
(ipcp_propagate_stage): Also propagate types.
(ipcp_need_redirect_p): Variable jump_func moved to its scope block.
Also return true if propagated types require it.
(ipcp_update_callgraph): Dump redirection info.
(ipcp_process_devirtualization_opportunities): New function.
(ipcp_const_param_count): Include known type information.
(ipcp_insert_stage): Call ipcp_process_devirtualization_opportunities
on new node. Fixed formatting.
* ipa-prop.c (get_binfo_at_offset): Renamed to ipa_get_binfo_at_offset
and changed all callers. Made externally visible.
(make_edge_direct_to_target): Renamed to ipa_make_edge_direct_to_target
and changed all callers. Made externally visible.
(ipa_node_duplication_hook): Duplicate types vector.
* cgraphunit.c (cgraph_materialize_all_clones): Also try to redirect
outgoing calls for which we can't get a decl from the statement.
* ipa-inline.c (inline_indirect_intraprocedural_analysis): Call
ipa_analyze_params_uses only when ipa-cp is disabled.
* gcc/testsuite/g++.dg/ipa/devirt-1.C: New test.
* gcc/testsuite/g++.dg/ipa/devirt-2.C: Likewise.
* gcc/testsuite/g++.dg/ipa/devirt-3.C: Likewise.
* gcc/testsuite/g++.dg/ipa/devirt-4.C: Likewise.
* gcc/testsuite/g++.dg/ipa/devirt-5.C: Likewise.
Index: icln/gcc/ipa-cp.c
===================================================================
--- icln.orig/gcc/ipa-cp.c
+++ icln/gcc/ipa-cp.c
@@ -69,7 +69,7 @@ along with GCC; see the file COPYING3.
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.
+ -ipcp_generate_summary() is the first stage driver.
Second stage - interprocedural analysis
========================================
@@ -184,6 +184,7 @@ ipcp_analyze_node (struct cgraph_node *n
ipa_initialize_node_params (node);
ipa_detect_param_modifications (node);
+ ipa_analyze_params_uses (node);
}
/* Return scale for NODE. */
@@ -387,12 +388,17 @@ ipcp_print_all_lattices (FILE * f)
{
fprintf (f, "type is CONST ");
print_generic_expr (f, lat->constant, 0);
- fprintf (f, "\n");
}
else if (lat->type == IPA_TOP)
- fprintf (f, "type is TOP\n");
+ fprintf (f, "type is TOP");
else
- fprintf (f, "type is BOTTOM\n");
+ fprintf (f, "type is BOTTOM");
+ if (ipa_param_cannot_devirtualize_p (info, i))
+ fprintf (f, " - cannot_devirtualize set\n");
+ else if (ipa_param_types_vec_empty (info, i))
+ fprintf (f, " - type list empty\n");
+ else
+ fprintf (f, "\n");
}
}
}
@@ -531,6 +537,16 @@ ipcp_cloning_candidate_p (struct cgraph_
return true;
}
+static bool
+ipa_set_param_cannot_devirtualize (struct ipa_node_params *info, int i)
+{
+ bool ret = info->params[i].cannot_devirtualize;
+ info->params[i].cannot_devirtualize = 1;
+ if (info->params[i].types)
+ VEC_free (tree, heap, info->params[i].types);
+ return ret;
+}
+
/* Initialize ipcp_lattices array. The lattices corresponding to supported
types (integers, real types and Fortran constants defined as const_decls)
are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
@@ -553,7 +569,11 @@ ipcp_initialize_node_lattices (struct cg
type = IPA_BOTTOM;
for (i = 0; i < ipa_get_param_count (info) ; i++)
- ipcp_get_lattice (info, i)->type = type;
+ {
+ ipcp_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.
@@ -607,41 +627,10 @@ ipcp_compute_node_scale (struct cgraph_n
ipcp_set_node_scale (node, sum * REG_BR_PROB_BASE / node->count);
}
-/* 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)
- {
- /* 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)))
- ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
- ipa_compute_jump_functions (cs);
- }
- }
-}
-
/* Return true if there are some formal parameters whose value is IPA_TOP (in
the whole compilation unit). Change their values to IPA_BOTTOM, since they
most probably get their values from outside of this compilation unit. */
+
static bool
ipcp_change_tops_to_bottom (void)
{
@@ -669,11 +658,144 @@ ipcp_change_tops_to_bottom (void)
}
lat->type = IPA_BOTTOM;
}
+ if (!ipa_param_cannot_devirtualize_p (info, i)
+ && ipa_param_types_vec_empty (info, i))
+ {
+ prop_again = true;
+ ipa_set_param_cannot_devirtualize (info, i);
+ if (dump_file)
+ {
+ fprintf (dump_file, "Marking param ");
+ print_generic_expr (dump_file, ipa_get_param (info, i), 0);
+ fprintf (dump_file, " of node %s as unusable for "
+ "devirtualization.\n",
+ cgraph_node_name (node));
+ }
+ }
}
}
return prop_again;
}
+/* Insert BINFO to the list of known types of parameter number I of the
+ function described by CALLEE_INFO. Return true iff the callee parameter
+ still can be used for devirtualization and BINFO was not already there. */
+
+static bool
+ipcp_add_param_type (struct ipa_node_params *callee_info, int i, tree binfo)
+{
+ int j, count;
+
+ if (ipa_param_cannot_devirtualize_p (callee_info, i))
+ return false;
+
+ if (callee_info->params[i].types)
+ {
+ count = VEC_length (tree, callee_info->params[i].types);
+ for (j = 0; j < count; j++)
+ if (VEC_index (tree, callee_info->params[i].types, j) == binfo)
+ return false;
+ }
+
+ VEC_safe_push (tree, heap, callee_info->params[i].types, binfo);
+ return true;
+}
+
+/* Copy known types information for parameter number CALLEE_IDX of CALLEE_INFO
+ from a parameter of CALLER_INFO as described by JF. Return true iff the
+ type information changed in any way. JF must be a pass-through or an
+ ancestor jump function. */
+
+static bool
+ipcp_copy_types (struct ipa_node_params *caller_info,
+ struct ipa_node_params *callee_info,
+ int callee_idx, struct ipa_jump_func *jf)
+{
+ int caller_idx, j, count;
+ bool res;
+
+ if (ipa_param_cannot_devirtualize_p (callee_info, callee_idx))
+ return false;
+
+ if (jf->type == IPA_JF_PASS_THROUGH)
+ {
+ if (jf->value.pass_through.operation != NOP_EXPR)
+ {
+ ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
+ return true;
+ }
+ caller_idx = jf->value.pass_through.formal_id;
+ }
+ else
+ caller_idx = jf->value.ancestor.formal_id;
+
+ if (ipa_param_cannot_devirtualize_p (caller_info, caller_idx))
+ {
+ ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
+ return true;
+ }
+
+ if (!caller_info->params[caller_idx].types)
+ return false;
+
+ res = false;
+ count = VEC_length (tree, caller_info->params[caller_idx].types);
+ for (j = 0; j < count; j++)
+ {
+ tree binfo = VEC_index (tree, caller_info->params[caller_idx].types, j);
+ if (jf->type == IPA_JF_ANCESTOR)
+ {
+ binfo = ipa_get_binfo_at_offset (binfo, jf->value.ancestor.offset,
+ jf->value.ancestor.type);
+ if (!binfo)
+ {
+ ipa_set_param_cannot_devirtualize (callee_info, callee_idx);
+ return true;
+ }
+ }
+ res |= ipcp_add_param_type (callee_info, callee_idx, binfo);
+ }
+ return res;
+}
+
+/* Propagate type information for parameter of CALLEE_INFO number I as
+ described by JF. CALLER_INFO describes the caller. Return true iff the
+ type information changed in any way. */
+
+static bool
+ipcp_propagate_types (struct ipa_node_params *caller_info,
+ 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:
+ 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);
+ }
+
+ /* If we reach this we cannot use this parameter for devirtualization. */
+ return !ipa_set_param_cannot_devirtualize (callee_info, i);
+}
+
/* Interprocedural analysis. The algorithm propagates constants from the
caller's parameters to the callee's arguments. */
static void
@@ -721,6 +843,9 @@ ipcp_propagate_stage (void)
dest_lat->constant = new_lat.constant;
ipa_push_func_to_list (&wl, cs->callee);
}
+
+ if (ipcp_propagate_types (info, callee_info, jump_func, i))
+ ipa_push_func_to_list (&wl, cs->callee);
}
}
}
@@ -872,7 +997,6 @@ ipcp_need_redirect_p (struct cgraph_edge
{
struct ipa_node_params *orig_callee_info;
int i, count;
- struct ipa_jump_func *jump_func;
struct cgraph_node *node = cs->callee, *orig;
if (!n_cloning_candidates)
@@ -888,12 +1012,16 @@ ipcp_need_redirect_p (struct cgraph_edge
for (i = 0; i < count; i++)
{
struct ipcp_lattice *lat = ipcp_get_lattice (orig_callee_info, i);
- if (ipcp_lat_is_const (lat))
- {
- jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
- if (jump_func->type != IPA_JF_CONST)
- return true;
- }
+ struct ipa_jump_func *jump_func;
+
+ jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
+ if ((ipcp_lat_is_const (lat)
+ && jump_func->type != IPA_JF_CONST)
+ || (!ipa_param_cannot_devirtualize_p (orig_callee_info, i)
+ && !ipa_param_types_vec_empty (orig_callee_info, i)
+ && jump_func->type != IPA_JF_CONST
+ && jump_func->type != IPA_JF_KNOWN_TYPE))
+ return true;
}
return false;
@@ -935,7 +1063,15 @@ ipcp_update_callgraph (void)
{
next = cs->next_caller;
if (!ipcp_node_is_clone (cs->caller) && ipcp_need_redirect_p (cs))
- cgraph_redirect_edge_callee (cs, orig_node);
+ {
+ if (dump_file)
+ fprintf (dump_file, "Redirecting edge %s/%i -> %s/%i "
+ "back to %s/%i.",
+ cgraph_node_name (cs->caller), cs->caller->uid,
+ cgraph_node_name (cs->callee), cs->callee->uid,
+ cgraph_node_name (orig_node), orig_node->uid);
+ cgraph_redirect_edge_callee (cs, orig_node);
+ }
}
}
}
@@ -1056,6 +1192,56 @@ ipcp_estimate_cloning_cost (struct cgrap
return cost + 1;
}
+/* Walk indirect calls of NODE and if any polymorphic can be turned into a
+ direct one now, do so. */
+
+static void
+ipcp_process_devirtualization_opportunities (struct cgraph_node *node)
+{
+ struct ipa_node_params *info = IPA_NODE_REF (node);
+ struct cgraph_edge *ie, *next_ie;
+
+ for (ie = node->indirect_calls; ie; ie = next_ie)
+ {
+ int param_index, types_count, j;
+ HOST_WIDE_INT token;
+ tree target;
+
+ next_ie = ie->next_callee;
+ if (!ie->indirect_info->polymorphic)
+ continue;
+ param_index = ie->indirect_info->param_index;
+ if (ipa_param_cannot_devirtualize_p (info, param_index)
+ || ipa_param_types_vec_empty (info, param_index))
+ continue;
+
+ token = ie->indirect_info->otr_token;
+ target = NULL_TREE;
+ types_count = VEC_length (tree, info->params[param_index].types);
+ for (j = 0; j < types_count; j++)
+ {
+ tree binfo = VEC_index (tree, info->params[param_index].types, j);
+ tree t = gimple_fold_obj_type_ref_known_binfo (token, binfo);
+
+ if (!t)
+ {
+ target = NULL_TREE;
+ break;
+ }
+ else if (!target)
+ target = t;
+ else if (target != t)
+ {
+ target = NULL_TREE;
+ break;
+ }
+ }
+
+ if (target)
+ ipa_make_edge_direct_to_target (ie, target);
+ }
+}
+
/* Return number of live constant parameters. */
static int
ipcp_const_param_count (struct cgraph_node *node)
@@ -1069,11 +1255,13 @@ ipcp_const_param_count (struct cgraph_no
{
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)))
+ 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_param_cannot_devirtualize_p (info, i)
+ && !ipa_param_types_vec_empty (info, i)))
const_param++;
}
return const_param;
@@ -1115,7 +1303,8 @@ ipcp_insert_stage (void)
max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
max_new_size = max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
- /* First collect all functions we proved to have constant arguments to heap. */
+ /* First collect all functions we proved to have constant arguments to
+ heap. */
heap = fibheap_new ();
for (node = cgraph_nodes; node; node = node->next)
{
@@ -1127,7 +1316,8 @@ ipcp_insert_stage (void)
if (ipa_is_called_with_var_arguments (info))
continue;
if (ipcp_const_param_count (node))
- node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node), node);
+ node->aux = fibheap_insert (heap, ipcp_estimate_cloning_cost (node),
+ node);
}
/* Now clone in priority order until code size growth limits are met or
@@ -1213,6 +1403,8 @@ ipcp_insert_stage (void)
if (node1 == NULL)
continue;
+ ipcp_process_devirtualization_opportunities (node1);
+
if (dump_file)
fprintf (dump_file, "versioned function %s with growth %i, overall %i\n",
cgraph_node_name (node), (int)growth, (int)new_size);
@@ -1275,18 +1467,44 @@ ipcp_driver (void)
return 0;
}
-/* Note function body size. */
+/* 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_generate_summary (void)
{
+ struct cgraph_node *node;
+ struct cgraph_edge *cs;
+
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 ();
- /* 1. Call the init stage to initialize
- the ipa_node_params and ipa_edge_args structures. */
- ipcp_init_stage ();
+
+ 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)
+ {
+ /* 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)))
+ ipa_set_called_with_variable_arg (IPA_NODE_REF (cs->callee));
+ ipa_compute_jump_functions (cs);
+ }
+ }
}
/* Write ipcp summary for nodes in SET. */
Index: icln/gcc/ipa-inline.c
===================================================================
--- icln.orig/gcc/ipa-inline.c
+++ icln/gcc/ipa-inline.c
@@ -1922,8 +1922,8 @@ inline_indirect_intraprocedural_analysis
{
ipa_initialize_node_params (node);
ipa_detect_param_modifications (node);
+ ipa_analyze_params_uses (node);
}
- ipa_analyze_params_uses (node);
if (!flag_ipa_cp)
for (cs = node->callees; cs; cs = cs->next_callee)
Index: icln/gcc/ipa-prop.h
===================================================================
--- icln.orig/gcc/ipa-prop.h
+++ icln/gcc/ipa-prop.h
@@ -132,11 +132,12 @@ struct GTY (()) ipa_jump_func
computed by the interprocedural stage of IPCP.
There are three main values of the lattice:
IPA_TOP - unknown,
- IPA_BOTTOM - non constant,
+ IPA_BOTTOM - variable,
IPA_CONST_VALUE - simple scalar constant,
- Cval of formal f will have a constant value if all callsites to this
- function have the same constant value passed to f.
- Integer and real constants are represented as IPA_CONST_VALUE. */
+
+ We also use this type to propagate types accross the call graph for the
+ purpose of devirtualization. In that case, IPA_CONST_VALUE denotes a known
+ type, rather than a constant. */
enum ipa_lattice_type
{
IPA_BOTTOM,
@@ -160,8 +161,14 @@ struct ipa_param_descriptor
struct ipcp_lattice ipcp_lattice;
/* PARAM_DECL of this parameter. */
tree decl;
- /* Whether the value parameter has been modified within the function. */
+ /* Vector of BINFOs of types that this argument might encounter. NULL
+ basically means a top value, bottom is marked by the cannot_devirtualize
+ flag below.*/
+ VEC (tree, heap) *types;
+ /* Whether the value parameter is modified within the function. */
unsigned modified : 1;
+ /* Set when parameter type cannot be used for devirtualization. */
+ unsigned cannot_devirtualize : 1;
};
/* ipa_node_params stores information related to formal parameters of functions
@@ -237,6 +244,25 @@ ipa_is_param_modified (struct ipa_node_p
return info->params[i].modified;
}
+/* Return the cannot_devirtualize flag corresponding to the Ith formal
+ parameter of the function associated with INFO. The corresponding function
+ to set the flag is ipa_set_param_cannot_devirtualize. */
+
+static inline bool
+ipa_param_cannot_devirtualize_p (struct ipa_node_params *info, int i)
+{
+ return info->params[i].cannot_devirtualize;
+}
+
+/* Return true iff the vector of possible types of the Ith formal parameter of
+ the function associated with INFO is empty. */
+
+static inline bool
+ipa_param_types_vec_empty (struct ipa_node_params *info, int i)
+{
+ return info->params[i].types == NULL;
+}
+
/* Flag this node as having callers with variable number of arguments. */
static inline void
@@ -411,6 +437,11 @@ void ipa_analyze_params_uses (struct cgr
bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
VEC (cgraph_edge_p, heap) **new_edges);
+/* Indirect edge and binfo processing. */
+struct cgraph_edge *ipa_make_edge_direct_to_target (struct cgraph_edge *, tree);
+tree ipa_get_binfo_at_offset (tree, HOST_WIDE_INT, tree);
+
+
/* Debugging interface. */
void ipa_print_node_params (FILE *, struct cgraph_node *node);
void ipa_print_all_params (FILE *);
Index: icln/gcc/cgraphunit.c
===================================================================
--- icln.orig/gcc/cgraphunit.c
+++ icln/gcc/cgraphunit.c
@@ -2275,9 +2275,10 @@ cgraph_redirect_edge_call_stmt_to_callee
gimple new_stmt;
gimple_stmt_iterator gsi;
- if (!decl || decl == e->callee->decl
+ if (e->indirect_unknown_callee
+ || decl == e->callee->decl
/* Don't update call from same body alias to the real function. */
- || cgraph_get_node (decl) == cgraph_get_node (e->callee->decl))
+ || (decl && cgraph_get_node (decl) == cgraph_get_node (e->callee->decl)))
return e->call_stmt;
if (cgraph_dump_file)
@@ -2402,7 +2403,10 @@ cgraph_materialize_all_clones (void)
current_function_decl = node->decl;
push_cfun (DECL_STRUCT_FUNCTION (node->decl));
for (e = node->callees; e; e = e->next_callee)
- cgraph_redirect_edge_call_stmt_to_callee (e);
+ {
+ gcc_assert (!e->indirect_inlining_edge);
+ cgraph_redirect_edge_call_stmt_to_callee (e);
+ }
pop_cfun ();
current_function_decl = NULL;
#ifdef ENABLE_CHECKING
Index: icln/gcc/ipa-prop.c
===================================================================
--- icln.orig/gcc/ipa-prop.c
+++ icln/gcc/ipa-prop.c
@@ -1169,8 +1169,8 @@ ipa_analyze_params_uses (struct cgraph_n
OFFSET within the BINFO type and which i of EXPECTED_TYPE. If it can be
found, return, otherwise return NULL_TREE. */
-static tree
-get_binfo_at_offset (tree binfo, HOST_WIDE_INT offset, tree expected_type)
+tree
+ipa_get_binfo_at_offset (tree binfo, HOST_WIDE_INT offset, tree expected_type)
{
tree type;
@@ -1231,9 +1231,9 @@ combine_known_type_and_ancestor_jfs (str
{
tree new_binfo;
- new_binfo = get_binfo_at_offset (src->value.base_binfo,
- dst->value.ancestor.offset,
- dst->value.ancestor.type);
+ new_binfo = ipa_get_binfo_at_offset (src->value.base_binfo,
+ dst->value.ancestor.offset,
+ dst->value.ancestor.type);
if (new_binfo)
{
dst->type = IPA_JF_KNOWN_TYPE;
@@ -1320,8 +1320,8 @@ update_jump_functions_after_inlining (st
/* If TARGET is an addr_expr of a function declaration, make it the destination
of an indirect edge IE and return the edge. Otherwise, return NULL. */
-static struct cgraph_edge *
-make_edge_direct_to_target (struct cgraph_edge *ie, tree target)
+struct cgraph_edge *
+ipa_make_edge_direct_to_target (struct cgraph_edge *ie, tree target)
{
struct cgraph_node *callee;
@@ -1369,7 +1369,7 @@ try_make_edge_direct_simple_call (struct
else
return NULL;
- return make_edge_direct_to_target (ie, target);
+ return ipa_make_edge_direct_to_target (ie, target);
}
/* Try to find a destination for indirect edge IE that corresponds to a
@@ -1403,14 +1403,14 @@ try_make_edge_direct_virtual_call (struc
token = ie->indirect_info->otr_token;
type = ie->indirect_info->otr_type;
- binfo = get_binfo_at_offset (binfo, ie->indirect_info->anc_offset, type);
+ binfo = ipa_get_binfo_at_offset (binfo, ie->indirect_info->anc_offset, type);
if (binfo)
target = gimple_fold_obj_type_ref_known_binfo (token, binfo);
else
return NULL;
if (target)
- return make_edge_direct_to_target (ie, target);
+ return ipa_make_edge_direct_to_target (ie, target);
else
return NULL;
}
@@ -1673,7 +1673,7 @@ ipa_node_duplication_hook (struct cgraph
__attribute__((unused)) void *data)
{
struct ipa_node_params *old_info, *new_info;
- int param_count;
+ int param_count, i;
ipa_check_create_node_params ();
old_info = IPA_NODE_REF (src);
@@ -1684,8 +1684,16 @@ ipa_node_duplication_hook (struct cgraph
new_info->params = (struct ipa_param_descriptor *)
duplicate_array (old_info->params,
sizeof (struct ipa_param_descriptor) * param_count);
+ for (i = 0; i < param_count; i++)
+ new_info->params[i].types = VEC_copy (tree, heap,
+ old_info->params[i].types);
new_info->ipcp_orig_node = old_info->ipcp_orig_node;
new_info->count_scale = old_info->count_scale;
+
+ new_info->called_with_var_arguments = old_info->called_with_var_arguments;
+ new_info->modification_analysis_done = old_info->modification_analysis_done;
+ new_info->uses_analysis_done = old_info->uses_analysis_done;
+ new_info->node_enqueued = old_info->node_enqueued;
}
/* Register our cgraph hooks if they are not already there. */
Index: icln/gcc/testsuite/g++.dg/ipa/devirt-1.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/devirt-1.C
@@ -0,0 +1,62 @@
+/* Verify that simple virtual calls are converted to direct calls by ipa-cp. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int C::foo (int i)
+{
+ return i + 3;
+}
+
+static int middleman (class A *obj, int i)
+{
+ return obj->foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+ if (middleman (&b, get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo" "cp" } } */
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/devirt-2.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/devirt-2.C
@@ -0,0 +1,60 @@
+/* Verify that simple virtual calls using this pointer are converted
+ to direct calls by ipa-cp. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+ int middleman (int i)
+ {
+ return foo (i);
+ }
+};
+
+class B : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int C::foo (int i)
+{
+ return i + 3;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+ if (b.middleman (get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo" "cp" } } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/devirt-3.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/devirt-3.C
@@ -0,0 +1,63 @@
+/* Verify that simple virtual calls on an object refrence are
+ converted to simple calls by ipa-cp. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int C::foo (int i)
+{
+ return i + 3;
+}
+
+static int middleman (class A &obj, int i)
+{
+ return obj.foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+ if (middleman (b, get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo" "cp" } } */
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/devirt-4.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/devirt-4.C
@@ -0,0 +1,68 @@
+/* Verify that ipa-co can convert virtual calls to direct ones even
+ when a typecast to an ancestor is involved along the way. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int C::foo (int i)
+{
+ return i + 3;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+static int middleman_1 (class A *obj, int i)
+{
+ return obj->foo (i);
+}
+
+static int middleman_2 (class B *obj, int i)
+{
+ return middleman_1 (obj, i);
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+ if (middleman_2 (&b, get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo" "cp" } } */
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/devirt-5.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/devirt-5.C
@@ -0,0 +1,79 @@
+/* Verify that ipa-cp can convert simple virtual calls to a direct
+ ones even when a typecast to an ancestor is involved along the way
+ and that ancestor is not the first one with virtual functions. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */
+
+extern "C" void abort (void);
+
+class Distraction
+{
+public:
+ float f;
+ double d;
+ Distraction ()
+ {
+ f = 8.3;
+ d = 10.2;
+ }
+ virtual float bar (float z);
+};
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+
+class B : public Distraction, public A
+{
+public:
+ virtual int foo (int i);
+};
+
+float Distraction::bar (float z)
+{
+ f += z;
+ return f/2;
+}
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+static int middleman_1 (class A *obj, int i)
+{
+ return obj->foo (i);
+}
+
+static int middleman_2 (class B *obj, int i)
+{
+ return middleman_1 (obj, i);
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+
+ if (middleman_2 (&b, get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo" "cp" } } */
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
^ permalink raw reply [flat|nested] 23+ messages in thread
* [PATCH 5/6] Indirect inlining of virtual calls
2010-02-13 18:03 [PATCH 0/6] Cgraph changes and various devirtualizations Martin Jambor
` (2 preceding siblings ...)
2010-02-13 18:04 ` [PATCH 3/6] Folding of virtual calls Martin Jambor
@ 2010-02-13 18:04 ` Martin Jambor
2010-02-22 16:49 ` Jan Hubicka
2010-02-13 18:04 ` [PATCH 4/6] Remove unused ipa_note_param_call.called flag (approved) Martin Jambor
2010-02-13 18:04 ` [PATCH 2/6] Indirect call graph edges Martin Jambor
5 siblings, 1 reply; 23+ messages in thread
From: Martin Jambor @ 2010-02-13 18:04 UTC (permalink / raw)
To: GCC Patches; +Cc: Jan Hubicka
[-- Attachment #1: iinline_virt_methods.diff --]
[-- Type: text/plain, Size: 46654 bytes --]
This patch improves the main inlining pass so that it is able to
inline virtual calls which will have known base type because of
previous inlining decisions. Inlining is perhaps the most important
part of devirtualization, when I benchmarked a previous version of
this patch I got ~3% improvement in 483.xalancbmk execution time. In
artificially constructed example (which is dumb but not particularly
weird) I got over 60%. I believe many C++ applications where small
virtual methods are used extensively will benefit tangibly. In any
way, this patch only provides inliner with more choices and so at
least in theory should not lead to any regressions.
This patch depends on all the previous ones in the series, especially
on the new indirect call graph edges and improved OBJ_TYPE_REF
folding. It adds a new type of jump function that simply carries over
a known base type of the function, adds some information about the
O_T_R to the indirect edges and substantially improves the code
combining various types of jump functions when inlining. Then the
framework we already have for indirect inlining works well with only
minor tweaks to extract types from known global constants and the
like.
The patch also works with LTO and since we now stream indirect
inlining node information along the jump functions again (which is the
major change since the last submission), it should also work with
WHOPR.
I have bootstrapped and regression tested all the patches up to this
one on x86_64-linux with no problems. I will seek approval to commit
them when stage1 opens and I will welcome any comments or suggestions.
Thanks,
Martin
2010-02-12 Martin Jambor <mjambor@suse.cz>
* cgraph.h (cgraph_indirect_call_info): New fields anc_offset,
otr_token and polymorphic.
* cgraph.c (cgraph_create_indirect_edge): Inilialize the above fields.
(cgraph_clone_edge): Copy the above fields.
* ipa-prop.h (enum jump_func_type): Added known_type jump function
type, reordered items, updated comments.
(union jump_func_value): Added base_type field, reordered fields.
(enum ipa_lattice_type): Moved down in the file.
(struct ipa_param_descriptor): New field polymorphic.
(ipa_is_param_polymorphic): New function.
* ipa-prop.c (ipa_print_node_jump_functions): Print known type jump
functions.
(compute_complex_pass_through): Renamed to...
(compute_complex_assign_jump_func): this.
(compute_complex_ancestor_jump_func): New function.
(compute_known_type_jump_func): Likewise.
(compute_scalar_jump_functions): Create known type and complex ancestor
jump functions.
(ipa_note_param_call): New parameter polymorphic, set the corresponding
flag in the call note accordingly.
(ipa_analyze_call_uses): Renamed to...
(ipa_analyze_indirect_call_uses): this. New parameter target, define
variable var only in the block where it is used.
(ipa_analyze_virtual_call_uses): New function.
(ipa_analyze_call_uses): Likewise.
(get_binfo_at_offset): Likewise.
(combine_known_type_and_ancestor_jfs): Likewise.
(update_jump_functions_after_inlining): Implemented handling of a
number of new jump function types combination.
(print_edge_addition_message): Removed.
(make_edge_direct_to_target): New function.
(try_make_edge_direct_simple_call): Likewise.
(try_make_edge_direct_virtual_call): Likewise.
(update_call_notes_after_inlining): Renamed to...
(update_indirect_edges_after_inlining): this. Moved edge creation for
indirect calls to try_make_edge_direct_simple_call, also calls
try_make_edge_direct_virtual_call for virtual calls.
(ipa_print_node_params): Changed the header message.
(ipa_write_jump_function): Stream also known type jump functions.
(ipa_read_jump_function): Likewise.
(ipa_write_indirect_edge_info): Stream new fields in
cgraph_indirect_call_info.
(ipa_read_indirect_edge_info): Likewise.
* testsuite/g++.dg/ipa/ivinline-1.C: New test.
* testsuite/g++.dg/ipa/ivinline-2.C: New test.
* testsuite/g++.dg/ipa/ivinline-3.C: New test.
* testsuite/g++.dg/ipa/ivinline-4.C: New test.
* testsuite/g++.dg/ipa/ivinline-5.C: New test.
* testsuite/g++.dg/ipa/ivinline-6.C: New test.
Index: icln/gcc/ipa-prop.c
===================================================================
--- icln.orig/gcc/ipa-prop.c
+++ icln/gcc/ipa-prop.c
@@ -283,6 +283,13 @@ ipa_print_node_jump_functions (FILE *f,
fprintf (f, " param %d: ", i);
if (type == IPA_JF_UNKNOWN)
fprintf (f, "UNKNOWN\n");
+ else if (type == IPA_JF_KNOWN_TYPE)
+ {
+ tree binfo_type = TREE_TYPE (jump_func->value.base_binfo);
+ fprintf (f, "KNOWN TYPE, type in binfo is: ");
+ print_generic_expr (f, binfo_type, 0);
+ fprintf (f, " (%u)\n", TYPE_UID (binfo_type));
+ }
else if (type == IPA_JF_CONST)
{
tree val = jump_func->value.constant;
@@ -313,9 +320,11 @@ ipa_print_node_jump_functions (FILE *f,
else if (type == IPA_JF_ANCESTOR)
{
fprintf (f, "ANCESTOR: ");
- fprintf (f, "%d, offset "HOST_WIDE_INT_PRINT_DEC"\n",
+ fprintf (f, "%d, offset "HOST_WIDE_INT_PRINT_DEC", ",
jump_func->value.ancestor.formal_id,
jump_func->value.ancestor.offset);
+ print_generic_expr (f, jump_func->value.ancestor.type, 0);
+ fprintf (dump_file, "\n");
}
}
}
@@ -335,51 +344,60 @@ ipa_print_all_jump_functions (FILE *f)
}
}
-/* Determine whether passing ssa name NAME constitutes a polynomial
- pass-through function or getting an address of an acestor and if so, write
- such a jump function to JFUNC. INFO describes the caller. */
+/* Given that an actual argument is an SSA_NAME (given in NAME) and is a result
+ of an assignment statement STMT, try to find out whether NAME can be
+ described by a (possibly polynomial) pass-through jump-function or an
+ ancestor jump function and if so, write the appropriate function into
+ JFUNC */
static void
-compute_complex_pass_through (struct ipa_node_params *info,
- struct ipa_jump_func *jfunc,
- tree name)
+compute_complex_assign_jump_func (struct ipa_node_params *info,
+ struct ipa_jump_func *jfunc,
+ gimple stmt, tree name)
{
HOST_WIDE_INT offset, size, max_size;
tree op1, op2, type;
int index;
- gimple stmt = SSA_NAME_DEF_STMT (name);
- if (!is_gimple_assign (stmt))
- return;
op1 = gimple_assign_rhs1 (stmt);
op2 = gimple_assign_rhs2 (stmt);
- if (op2)
+ if (TREE_CODE (op1) == SSA_NAME
+ && SSA_NAME_IS_DEFAULT_DEF (op1))
{
- if (TREE_CODE (op1) != SSA_NAME
- || !SSA_NAME_IS_DEFAULT_DEF (op1)
- || (TREE_CODE_CLASS (gimple_expr_code (stmt)) != tcc_comparison
- && !useless_type_conversion_p (TREE_TYPE (name),
- TREE_TYPE (op1)))
- || !is_gimple_ip_invariant (op2))
+ index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op1));
+ if (index < 0)
return;
- index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op1));
- if (index >= 0)
+ if (op2)
{
+ if (!is_gimple_ip_invariant (op2)
+ || (TREE_CODE_CLASS (gimple_expr_code (stmt)) != tcc_comparison
+ && !useless_type_conversion_p (TREE_TYPE (name),
+ TREE_TYPE (op1))))
+ return;
+
jfunc->type = IPA_JF_PASS_THROUGH;
jfunc->value.pass_through.formal_id = index;
jfunc->value.pass_through.operation = gimple_assign_rhs_code (stmt);
jfunc->value.pass_through.operand = op2;
}
+ else if (gimple_assign_unary_nop_p (stmt))
+ {
+ jfunc->type = IPA_JF_PASS_THROUGH;
+ jfunc->value.pass_through.formal_id = index;
+ jfunc->value.pass_through.operation = NOP_EXPR;
+ }
return;
}
if (TREE_CODE (op1) != ADDR_EXPR)
return;
+
op1 = TREE_OPERAND (op1, 0);
type = TREE_TYPE (op1);
-
+ if (TREE_CODE (type) != RECORD_TYPE)
+ return;
op1 = get_ref_base_and_extent (op1, &offset, &size, &max_size);
if (TREE_CODE (op1) != INDIRECT_REF
/* If this is a varying address, punt. */
@@ -402,6 +420,120 @@ compute_complex_pass_through (struct ipa
}
+/* Given that an actual argument is an SSA_NAME that is a result of a phi
+ statement PHI, try to find out whether NAME is in fact a
+ multiple-inheritance typecast from a descendant into an ancestor of a formal
+ parameter and thus can be described by an ancestor jump function and if so,
+ write the appropriate function into JFUNC.
+
+ Essentially we want to match the following pattern:
+
+ if (obj_2(D) != 0B)
+ goto <bb 3>;
+ else
+ goto <bb 4>;
+
+ <bb 3>:
+ iftmp.1_3 = &obj_2(D)->D.1762;
+
+ <bb 4>:
+ # iftmp.1_1 = PHI <iftmp.1_3(3), 0B(2)>
+ D.1879_6 = middleman_1 (iftmp.1_1, i_5(D));
+ return D.1879_6; */
+
+static void
+compute_complex_ancestor_jump_func (struct ipa_node_params *info,
+ struct ipa_jump_func *jfunc,
+ gimple phi)
+{
+ HOST_WIDE_INT offset, size, max_size;
+ gimple assign, cond;
+ basic_block phi_bb, assign_bb, cond_bb;
+ tree tmp, parm, expr;
+ int index, i;
+
+ if (gimple_phi_num_args (phi) != 2
+ || !integer_zerop (PHI_ARG_DEF (phi, 1)))
+ return;
+
+ tmp = PHI_ARG_DEF (phi, 0);
+ if (TREE_CODE (tmp) != SSA_NAME
+ || SSA_NAME_IS_DEFAULT_DEF (tmp)
+ || !POINTER_TYPE_P (TREE_TYPE (tmp))
+ || TREE_CODE (TREE_TYPE (TREE_TYPE (tmp))) != RECORD_TYPE)
+ return;
+
+ assign = SSA_NAME_DEF_STMT (tmp);
+ assign_bb = gimple_bb (assign);
+ if (!single_pred_p (assign_bb)
+ || !gimple_assign_single_p (assign))
+ return;
+ expr = gimple_assign_rhs1 (assign);
+
+ if (TREE_CODE (expr) != ADDR_EXPR)
+ return;
+ expr = TREE_OPERAND (expr, 0);
+ expr = get_ref_base_and_extent (expr, &offset, &size, &max_size);
+
+ if (TREE_CODE (expr) != INDIRECT_REF
+ /* If this is a varying address, punt. */
+ || max_size == -1
+ || max_size != size)
+ return;
+ parm = TREE_OPERAND (expr, 0);
+ if (TREE_CODE (parm) != SSA_NAME
+ || !SSA_NAME_IS_DEFAULT_DEF (parm))
+ return;
+
+ index = ipa_get_param_decl_index (info, SSA_NAME_VAR (parm));
+ if (index < 0)
+ return;
+
+ cond_bb = single_pred (assign_bb);
+ cond = last_stmt (cond_bb);
+ if (gimple_code (cond) != GIMPLE_COND
+ || gimple_cond_code (cond) != NE_EXPR
+ || gimple_cond_lhs (cond) != parm
+ || !integer_zerop (gimple_cond_rhs (cond)))
+ return;
+
+
+ phi_bb = gimple_bb (phi);
+ for (i = 0; i < 2; i++)
+ {
+ basic_block pred = EDGE_PRED (phi_bb, i)->src;
+ if (pred != assign_bb && pred != cond_bb)
+ return;
+ }
+
+ jfunc->type = IPA_JF_ANCESTOR;
+ jfunc->value.ancestor.formal_id = index;
+ jfunc->value.ancestor.offset = offset;
+ jfunc->value.ancestor.type = TREE_TYPE (TREE_TYPE (tmp));
+}
+
+/* Given OP whch is passed as an actual argument to a called function,
+ determine if it is possible to construct a KNOWN_TYPE jump function for it
+ and if so, create one and store it to JFUNC. */
+
+static void
+compute_known_type_jump_func (tree op, struct ipa_jump_func *jfunc)
+{
+ tree binfo;
+
+ if (TREE_CODE (op) != ADDR_EXPR)
+ return;
+
+ op = TREE_OPERAND (op, 0);
+ binfo = gimple_get_relevant_ref_binfo (op, NULL_TREE);
+ if (binfo)
+ {
+ jfunc->type = IPA_JF_KNOWN_TYPE;
+ jfunc->value.base_binfo = binfo;
+ }
+}
+
+
/* Determine the jump functions of scalar arguments. Scalar means SSA names
and constants of a number of selected types. INFO is the ipa_node_params
structure associated with the caller, FUNCTIONS is a pointer to an array of
@@ -439,8 +571,18 @@ compute_scalar_jump_functions (struct ip
}
}
else
- compute_complex_pass_through (info, &functions[num], arg);
+ {
+ gimple stmt = SSA_NAME_DEF_STMT (arg);
+ if (is_gimple_assign (stmt))
+ compute_complex_assign_jump_func (info, &functions[num],
+ stmt, arg);
+ else if (gimple_code (stmt) == GIMPLE_PHI)
+ compute_complex_ancestor_jump_func (info, &functions[num],
+ stmt);
+ }
}
+ else
+ compute_known_type_jump_func (arg, &functions[num]);
}
}
@@ -740,16 +882,27 @@ ipa_is_ssa_with_stmt_def (tree t)
statement. */
static void
-ipa_note_param_call (struct cgraph_node *node, int formal_id, gimple stmt)
+ipa_note_param_call (struct cgraph_node *node, int param_index, gimple stmt,
+ bool polymorphic)
{
struct cgraph_edge *cs;
basic_block bb = gimple_bb (stmt);
int freq;
- freq = compute_call_stmt_bb_frequency (current_function_decl, bb);
+ freq = compute_call_stmt_bb_frequency (node->decl, bb);
cs = cgraph_create_indirect_edge (node, stmt, bb->count, freq,
bb->loop_depth);
- cs->indirect_info->param_index = formal_id;
+ cs->indirect_info->param_index = param_index;
+ cs->indirect_info->anc_offset = 0;
+ cs->indirect_info->polymorphic = polymorphic;
+ if (polymorphic)
+ {
+ tree otr = gimple_call_fn (stmt);
+ tree type, token = OBJ_TYPE_REF_TOKEN (otr);
+ cs->indirect_info->otr_token = tree_low_cst (token, 1);
+ type = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (otr)));
+ cs->indirect_info->otr_type = type;
+ }
}
/* Analyze the CALL and examine uses of formal parameters of the caller NODE
@@ -800,12 +953,11 @@ ipa_note_param_call (struct cgraph_node
*/
static void
-ipa_analyze_call_uses (struct cgraph_node *node, struct ipa_node_params *info,
- gimple call)
+ipa_analyze_indirect_call_uses (struct cgraph_node *node,
+ struct ipa_node_params *info,
+ gimple call, tree target)
{
- tree target = gimple_call_fn (call);
gimple def;
- tree var;
tree n1, n2;
gimple d1, d2;
tree rec, rec2, cond;
@@ -813,16 +965,12 @@ ipa_analyze_call_uses (struct cgraph_nod
int index;
basic_block bb, virt_bb, join;
- if (TREE_CODE (target) != SSA_NAME)
- return;
-
- var = SSA_NAME_VAR (target);
if (SSA_NAME_IS_DEFAULT_DEF (target))
{
- /* assuming TREE_CODE (var) == PARM_DECL */
+ tree var = SSA_NAME_VAR (target);
index = ipa_get_param_decl_index (info, var);
if (index >= 0)
- ipa_note_param_call (node, index, call);
+ ipa_note_param_call (node, index, call, false);
return;
}
@@ -919,11 +1067,63 @@ ipa_analyze_call_uses (struct cgraph_nod
index = ipa_get_param_decl_index (info, rec);
if (index >= 0 && !ipa_is_param_modified (info, index))
- ipa_note_param_call (node, index, call);
+ ipa_note_param_call (node, index, call, false);
return;
}
+/* Analyze a CALL to an OBJ_TYPE_REF which is passed in TARGET and if the
+ object referenced in the expression is a formal parameter of the caller
+ (described by INFO), create a call note for the statement. */
+
+static void
+ipa_analyze_virtual_call_uses (struct cgraph_node *node,
+ struct ipa_node_params *info, gimple call,
+ tree target)
+{
+ tree obj = OBJ_TYPE_REF_OBJECT (target);
+ tree var;
+ int index;
+
+ if (TREE_CODE (obj) == ADDR_EXPR)
+ {
+ do
+ {
+ obj = TREE_OPERAND (obj, 0);
+ }
+ while (TREE_CODE (obj) == COMPONENT_REF);
+ if (TREE_CODE (obj) != INDIRECT_REF)
+ return;
+ obj = TREE_OPERAND (obj, 0);
+ }
+
+ if (TREE_CODE (obj) != SSA_NAME
+ || !SSA_NAME_IS_DEFAULT_DEF (obj))
+ return;
+
+ var = SSA_NAME_VAR (obj);
+ index = ipa_get_param_decl_index (info, var);
+
+ if (index >= 0)
+ ipa_note_param_call (node, index, call, true);
+}
+
+/* Analyze a call statement CALL whether and how it utilizes formal parameters
+ of the caller (described by INFO). */
+
+static void
+ipa_analyze_call_uses (struct cgraph_node *node,
+ struct ipa_node_params *info, gimple call)
+{
+ tree target = gimple_call_fn (call);
+
+ if (TREE_CODE (target) == SSA_NAME)
+ ipa_analyze_indirect_call_uses (node, info, call, target);
+ else if (TREE_CODE (target) == OBJ_TYPE_REF)
+ ipa_analyze_virtual_call_uses (node, info, call, target);
+}
+
+
/* Analyze the call statement STMT with respect to formal parameters (described
in INFO) of caller given by NODE. Currently it only checks whether formal
parameters are called. */
@@ -965,12 +1165,87 @@ ipa_analyze_params_uses (struct cgraph_n
info->uses_analysis_done = 1;
}
+/* Try to find a base info of BINFO that would have its field decl at offset
+ OFFSET within the BINFO type and which i of EXPECTED_TYPE. If it can be
+ found, return, otherwise return NULL_TREE. */
+
+static tree
+get_binfo_at_offset (tree binfo, HOST_WIDE_INT offset, tree expected_type)
+{
+ tree type;
+
+ if (offset == 0)
+ return binfo;
+
+ type = TREE_TYPE (binfo);
+ while (offset > 0)
+ {
+ tree base_binfo, found_binfo;
+ HOST_WIDE_INT pos, size;
+ tree fld;
+ int i;
+
+ if (TREE_CODE (type) != RECORD_TYPE)
+ return NULL_TREE;
+
+ for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
+ {
+ if (TREE_CODE (fld) != FIELD_DECL)
+ continue;
+
+ pos = int_bit_position (fld);
+ size = tree_low_cst (DECL_SIZE (fld), 1);
+ if (pos <= offset && (pos + size) > offset)
+ break;
+ }
+ if (!fld)
+ return NULL_TREE;
+
+ found_binfo = NULL_TREE;
+ for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
+ if (TREE_TYPE (base_binfo) == TREE_TYPE (fld))
+ {
+ found_binfo = base_binfo;
+ break;
+ }
+
+ if (!found_binfo)
+ return NULL_TREE;
+
+ type = TREE_TYPE (fld);
+ binfo = found_binfo;
+ offset -= pos;
+ }
+ if (type != expected_type)
+ return NULL_TREE;
+ return binfo;
+}
+
+/* Update the jump function DST when the call graph edge correspondng to SRC is
+ is being inlined, knowing that DST is of type ancestor and src of known
+ type. */
+
+static void
+combine_known_type_and_ancestor_jfs (struct ipa_jump_func *src,
+ struct ipa_jump_func *dst)
+{
+ tree new_binfo;
+
+ new_binfo = get_binfo_at_offset (src->value.base_binfo,
+ dst->value.ancestor.offset,
+ dst->value.ancestor.type);
+ if (new_binfo)
+ {
+ dst->type = IPA_JF_KNOWN_TYPE;
+ dst->value.base_binfo = new_binfo;
+ }
+ else
+ dst->type = IPA_JF_UNKNOWN;
+}
+
/* Update the jump functions associated with call graph edge E when the call
graph edge CS is being inlined, assuming that E->caller is already (possibly
- indirectly) inlined into CS->callee and that E has not been inlined.
-
- We keep pass through functions only if they do not contain any operation.
- This is sufficient for inlining and greately simplifies things. */
+ indirectly) inlined into CS->callee and that E has not been inlined. */
static void
update_jump_functions_after_inlining (struct cgraph_edge *cs,
@@ -983,51 +1258,161 @@ update_jump_functions_after_inlining (st
for (i = 0; i < count; i++)
{
- struct ipa_jump_func *src, *dst = ipa_get_ith_jump_func (args, i);
+ struct ipa_jump_func *dst = ipa_get_ith_jump_func (args, i);
if (dst->type == IPA_JF_ANCESTOR)
{
- dst->type = IPA_JF_UNKNOWN;
- continue;
- }
+ struct ipa_jump_func *src;
- if (dst->type != IPA_JF_PASS_THROUGH)
- continue;
+ /* Variable number of arguments can cause havoc if we try to access
+ one that does not exist in the inlined edge. So make sure we
+ don't. */
+ if (dst->value.ancestor.formal_id >= ipa_get_cs_argument_count (top))
+ {
+ dst->type = IPA_JF_UNKNOWN;
+ continue;
+ }
+
+ src = ipa_get_ith_jump_func (top, dst->value.ancestor.formal_id);
+ if (src->type == IPA_JF_KNOWN_TYPE)
+ combine_known_type_and_ancestor_jfs (src, dst);
+ else if (src->type == IPA_JF_CONST)
+ {
+ struct ipa_jump_func kt_func;
- /* We must check range due to calls with variable number of arguments and
- we cannot combine jump functions with operations. */
- if (dst->value.pass_through.operation != NOP_EXPR
- || (dst->value.pass_through.formal_id
- >= ipa_get_cs_argument_count (top)))
+ kt_func.type = IPA_JF_UNKNOWN;
+ compute_known_type_jump_func (src->value.constant, &kt_func);
+ if (kt_func.type == IPA_JF_KNOWN_TYPE)
+ combine_known_type_and_ancestor_jfs (&kt_func, dst);
+ else
+ dst->type = IPA_JF_UNKNOWN;
+ }
+ else if (src->type == IPA_JF_PASS_THROUGH
+ && src->value.pass_through.operation == NOP_EXPR)
+ dst->value.ancestor.formal_id = src->value.pass_through.formal_id;
+ else if (src->type == IPA_JF_ANCESTOR)
+ {
+ dst->value.ancestor.formal_id = src->value.ancestor.formal_id;
+ dst->value.ancestor.offset += src->value.ancestor.offset;
+ }
+ else
+ dst->type = IPA_JF_UNKNOWN;
+ }
+ else if (dst->type == IPA_JF_PASS_THROUGH)
{
- dst->type = IPA_JF_UNKNOWN;
- continue;
+ struct ipa_jump_func *src;
+ /* We must check range due to calls with variable number of arguments
+ and we cannot combine jump functions with operations. */
+ if (dst->value.pass_through.operation == NOP_EXPR
+ && (dst->value.pass_through.formal_id
+ < ipa_get_cs_argument_count (top)))
+ {
+ src = ipa_get_ith_jump_func (top,
+ dst->value.pass_through.formal_id);
+ *dst = *src;
+ }
+ else
+ dst->type = IPA_JF_UNKNOWN;
}
+ }
+}
+
+/* If TARGET is an addr_expr of a function declaration, make it the destination
+ of an indirect edge IE and return the edge. Otherwise, return NULL. */
+
+static struct cgraph_edge *
+make_edge_direct_to_target (struct cgraph_edge *ie, tree target)
+{
+ struct cgraph_node *callee;
+
+ if (TREE_CODE (target) != ADDR_EXPR)
+ return NULL;
+ target = TREE_OPERAND (target, 0);
+ if (TREE_CODE (target) != FUNCTION_DECL)
+ return NULL;
+ callee = cgraph_node (target);
+ if (!callee)
+ return NULL;
+
+ cgraph_make_edge_direct (ie, callee);
+ if (dump_file)
+ {
+ fprintf (dump_file, "ipa-prop: Discovered %s call to a known target "
+ "(%s/%i -> %s/%i) for stmt ",
+ ie->indirect_info->polymorphic ? "a virtual" : "an indirect",
+ cgraph_node_name (ie->caller), ie->caller->uid,
+ cgraph_node_name (ie->callee), ie->callee->uid);
- src = ipa_get_ith_jump_func (top, dst->value.pass_through.formal_id);
- *dst = *src;
+ if (ie->call_stmt)
+ print_gimple_stmt (dump_file, ie->call_stmt, 2, TDF_SLIM);
+ else
+ fprintf (dump_file, "with uid %i\n", ie->lto_stmt_uid);
}
+ return ie;
}
-/* Print out a debug message to file F that we have discovered that an indirect
- call described by NT is in fact a call of a known constant function described
- by JFUNC. NODE is the node where the call is. */
+/* Try to find a destination for indirect edge IE that corresponds to a simple
+ call or a call of a member function pointer and where the destination is a
+ pointer formal parameter described by jump function JFUNC. If it can be
+ determined, return the newly direct edge, otherwise return NULL. */
-static void
-print_edge_addition_message (FILE *f, struct cgraph_edge *e,
- struct ipa_jump_func *jfunc)
+static struct cgraph_edge *
+try_make_edge_direct_simple_call (struct cgraph_edge *ie,
+ struct ipa_jump_func *jfunc)
+{
+ tree target;
+
+ if (jfunc->type == IPA_JF_CONST)
+ target = jfunc->value.constant;
+ else if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
+ target = jfunc->value.member_cst.pfn;
+ else
+ return NULL;
+
+ return make_edge_direct_to_target (ie, target);
+}
+
+/* Try to find a destination for indirect edge IE that corresponds to a
+ virtuall call based on a formal parameter which is described by jump
+ function JFUNC and if it can be determined, make it direct and return the
+ direct edge. Otherwise, return NULL. */
+
+static struct cgraph_edge *
+try_make_edge_direct_virtual_call (struct cgraph_edge *ie,
+ struct ipa_jump_func *jfunc)
{
- fprintf (f, "ipa-prop: Discovered an indirect call to a known target (");
- if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
+ tree binfo, type, target;
+ HOST_WIDE_INT token;
+
+ if (jfunc->type == IPA_JF_KNOWN_TYPE)
+ binfo = jfunc->value.base_binfo;
+ else if (jfunc->type == IPA_JF_CONST)
{
- print_node_brief (f, "", jfunc->value.member_cst.pfn, 0);
- print_node_brief (f, ", ", jfunc->value.member_cst.delta, 0);
+ tree cst = jfunc->value.constant;
+ if (TREE_CODE (cst) == ADDR_EXPR)
+ binfo = gimple_get_relevant_ref_binfo (TREE_OPERAND (cst, 0),
+ NULL_TREE);
+ else
+ return NULL;
}
else
- print_node_brief(f, "", jfunc->value.constant, 0);
+ return NULL;
+
+ if (!binfo)
+ return NULL;
+
+ token = ie->indirect_info->otr_token;
+ type = ie->indirect_info->otr_type;
+ binfo = get_binfo_at_offset (binfo, ie->indirect_info->anc_offset, type);
+ if (binfo)
+ target = gimple_fold_obj_type_ref_known_binfo (token, binfo);
+ else
+ return NULL;
- fprintf (f, ") in %s: ", cgraph_node_name (e->caller));
- print_gimple_stmt (f, e->call_stmt, 2, TDF_SLIM);
+ if (target)
+ return make_edge_direct_to_target (ie, target);
+ else
+ return NULL;
}
/* Update the param called notes associated with NODE when CS is being inlined,
@@ -1037,12 +1422,12 @@ print_edge_addition_message (FILE *f, st
unless NEW_EDGES is NULL. Return true iff a new edge(s) were created. */
static bool
-update_call_notes_after_inlining (struct cgraph_edge *cs,
- struct cgraph_node *node,
- VEC (cgraph_edge_p, heap) **new_edges)
+update_indirect_edges_after_inlining (struct cgraph_edge *cs,
+ struct cgraph_node *node,
+ VEC (cgraph_edge_p, heap) **new_edges)
{
struct ipa_edge_args *top = IPA_EDGE_REF (cs);
- struct cgraph_edge *ie, *next_ie;
+ struct cgraph_edge *ie, *next_ie, *new_direct_edge;
bool res = false;
ipa_check_create_edge_args ();
@@ -1063,7 +1448,7 @@ update_call_notes_after_inlining (struct
/* We must check range due to calls with variable number of arguments: */
if (ici->param_index >= ipa_get_cs_argument_count (top))
{
- ici->inlining_processed = true;
+ ici->inlining_processed = 1;
continue;
}
@@ -1071,44 +1456,30 @@ update_call_notes_after_inlining (struct
if (jfunc->type == IPA_JF_PASS_THROUGH
&& jfunc->value.pass_through.operation == NOP_EXPR)
ici->param_index = jfunc->value.pass_through.formal_id;
- else if (jfunc->type == IPA_JF_CONST
- || jfunc->type == IPA_JF_CONST_MEMBER_PTR)
+ else if (jfunc->type == IPA_JF_ANCESTOR)
{
- struct cgraph_node *callee;
- tree decl;
-
- ici->inlining_processed = true;
- if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
- decl = jfunc->value.member_cst.pfn;
- else
- decl = jfunc->value.constant;
-
- if (TREE_CODE (decl) != ADDR_EXPR)
- continue;
- decl = TREE_OPERAND (decl, 0);
-
- if (TREE_CODE (decl) != FUNCTION_DECL)
- continue;
- callee = cgraph_node (decl);
- if (!callee || !callee->local.inlinable)
- continue;
-
- res = true;
- if (dump_file)
- print_edge_addition_message (dump_file, ie, jfunc);
-
- cgraph_make_edge_direct (ie, callee);
- ie->indirect_inlining_edge = 1;
- if (new_edges)
- VEC_safe_push (cgraph_edge_p, heap, *new_edges, ie);
- top = IPA_EDGE_REF (cs);
+ ici->param_index = jfunc->value.ancestor.formal_id;
+ ici->anc_offset += jfunc->value.ancestor.offset;
}
else
+ /* Either we can find a destination for this edge now or never. */
+ ici->inlining_processed = 1;
+
+ if (ici->polymorphic)
+ new_direct_edge = try_make_edge_direct_virtual_call (ie, jfunc);
+ else
+ new_direct_edge = try_make_edge_direct_simple_call (ie, jfunc);
+
+ if (new_direct_edge)
{
- /* Ancestor jum functions and pass theoughs with operations should
- not be used on parameters that then get called. */
- gcc_assert (jfunc->type == IPA_JF_UNKNOWN);
- ici->inlining_processed = true;
+ new_direct_edge->indirect_inlining_edge = 1;
+ if (new_edges)
+ {
+ VEC_safe_push (cgraph_edge_p, heap, *new_edges,
+ new_direct_edge);
+ top = IPA_EDGE_REF (cs);
+ res = true;
+ }
}
}
@@ -1131,7 +1502,7 @@ propagate_info_to_inlined_callees (struc
struct cgraph_edge *e;
bool res;
- res = update_call_notes_after_inlining (cs, node, new_edges);
+ res = update_indirect_edges_after_inlining (cs, node, new_edges);
for (e = node->callees; e; e = e->next_callee)
if (!e->inline_failed)
@@ -1389,7 +1760,8 @@ ipa_print_node_params (FILE * f, struct
if (!node->analyzed)
return;
info = IPA_NODE_REF (node);
- fprintf (f, " function %s Trees :: \n", cgraph_node_name (node));
+ fprintf (f, " function %s parameter descriptors:\n",
+ cgraph_node_name (node));
count = ipa_get_param_count (info);
for (i = 0; i < count; i++)
{
@@ -1881,6 +2253,9 @@ ipa_write_jump_function (struct output_b
{
case IPA_JF_UNKNOWN:
break;
+ case IPA_JF_KNOWN_TYPE:
+ lto_output_tree (ob, jump_func->value.base_binfo, true);
+ break;
case IPA_JF_CONST:
lto_output_tree (ob, jump_func->value.constant, true);
break;
@@ -1918,6 +2293,9 @@ ipa_read_jump_function (struct lto_input
{
case IPA_JF_UNKNOWN:
break;
+ case IPA_JF_KNOWN_TYPE:
+ jump_func->value.base_binfo = lto_input_tree (ib, data_in);
+ break;
case IPA_JF_CONST:
jump_func->value.constant = lto_input_tree (ib, data_in);
break;
@@ -1949,10 +2327,19 @@ ipa_write_indirect_edge_info (struct out
struct bitpack_d *bp;
lto_output_sleb128_stream (ob->main_stream, ii->param_index);
+ lto_output_sleb128_stream (ob->main_stream, ii->anc_offset);
bp = bitpack_create ();
+ gcc_assert (!ii->inlining_processed);
bp_pack_value (bp, ii->inlining_processed, 1);
+ bp_pack_value (bp, ii->polymorphic, 1);
lto_output_bitpack (ob->main_stream, bp);
bitpack_delete (bp);
+
+ if (ii->polymorphic)
+ {
+ lto_output_sleb128_stream (ob->main_stream, ii->otr_token);
+ lto_output_tree (ob, ii->otr_type, true);
+ }
}
/* Read in parts of cgraph_indirect_call_info corresponding to CS that are
@@ -1967,9 +2354,16 @@ ipa_read_indirect_edge_info (struct lto_
struct bitpack_d *bp;
ii->param_index = (int) lto_input_sleb128 (ib);
+ ii->anc_offset = (HOST_WIDE_INT) lto_input_sleb128 (ib);
bp = lto_input_bitpack (ib);
ii->inlining_processed = bp_unpack_value (bp, 1);
+ ii->polymorphic = bp_unpack_value (bp, 1);
bitpack_delete (bp);
+ if (ii->polymorphic)
+ {
+ ii->otr_token = (HOST_WIDE_INT) lto_input_sleb128 (ib);
+ ii->otr_type = lto_input_tree (ib, data_in);
+ }
}
/* Stream out NODE info to OB. */
Index: icln/gcc/ipa-prop.h
===================================================================
--- icln.orig/gcc/ipa-prop.h
+++ icln/gcc/ipa-prop.h
@@ -38,38 +38,40 @@ along with GCC; see the file COPYING3.
argument.
Unknown - neither of the above.
- IPA_JF_CONST_MEMBER_PTR stands for C++ member pointers, other constants are
- represented with IPA_JF_CONST.
+ IPA_JF_CONST_MEMBER_PTR stands for C++ member pointers, it is a special
+ constant in this regard. Other constants are represented with IPA_JF_CONST.
+
+ IPA_JF_ANCESTOR is a special pass-through jump function, which means that
+ the result is an address of a part of the object pointed to by the formal
+ parameter to which the function refers. It is mainly intended to represent
+ getting addresses of of ancestor fields in C++
+ (e.g. &this_1(D)->D.1766.D.1756). Note that if the original pointer is
+ NULL, ancestor jump function must behave like a simple pass-through.
+
+ Other pass-through functions can either simply pass on an unchanged formal
+ parameter or can apply one simple binary operation to it (such jump
+ functions are called polynomial).
+
+ IPA_JF_KNOWN_TYPE is a special type of an "unknown" function that applies
+ only to pointer parameters. It means that even though we cannot prove that
+ the passed value is an interprocedural constant, we still know the exact
+ type of the containing object which may be valuable for devirtualization.
+
+ Jump functions are computed in ipa-prop.c by function
+ update_call_notes_after_inlining. Some information can be lost and jump
+ functions degraded accordingly when inlining, see
+ update_call_notes_after_inlining in the same file. */
- In addition to "ordinary" pass through functions represented by
- IPA_JF_PASS_THROUGH, IPA_JF_ANCESTOR represents getting addresses of of
- ancestor fields in C++ (e.g. &this_1(D)->D.1766.D.1756). */
enum jump_func_type
{
IPA_JF_UNKNOWN = 0, /* newly allocated and zeroed jump functions default */
- IPA_JF_CONST,
- IPA_JF_CONST_MEMBER_PTR,
- IPA_JF_PASS_THROUGH,
- IPA_JF_ANCESTOR
-};
-
-/* All formal parameters in the program have a lattice associated with it
- computed by the interprocedural stage of IPCP.
- There are three main values of the lattice:
- IPA_TOP - unknown,
- IPA_BOTTOM - non constant,
- IPA_CONST_VALUE - simple scalar constant,
- Cval of formal f will have a constant value if all callsites to this
- function have the same constant value passed to f.
- Integer and real constants are represented as IPA_CONST_VALUE. */
-enum ipa_lattice_type
-{
- IPA_BOTTOM,
- IPA_CONST_VALUE,
- IPA_TOP
+ IPA_JF_KNOWN_TYPE, /* represented by field base_binfo */
+ IPA_JF_CONST, /* represented by field costant */
+ IPA_JF_CONST_MEMBER_PTR, /* represented by field member_cst */
+ IPA_JF_PASS_THROUGH, /* represented by field pass_through */
+ IPA_JF_ANCESTOR /* represented by field ancestor */
};
-
/* Structure holding data required to describe a pass-through jump function. */
struct GTY(()) ipa_pass_through_data
@@ -86,8 +88,8 @@ struct GTY(()) ipa_pass_through_data
enum tree_code operation;
};
-/* Structure holding data required to describe and ancestor pass throu
- funkci. */
+/* Structure holding data required to describe an ancestor pass-through
+ jump function. */
struct GTY(()) ipa_ancestor_jf_data
{
@@ -118,13 +120,30 @@ struct GTY (()) ipa_jump_func
functions and member_cst holds constant c++ member functions. */
union jump_func_value
{
+ tree GTY ((tag ("IPA_JF_KNOWN_TYPE"))) base_binfo;
tree GTY ((tag ("IPA_JF_CONST"))) constant;
+ struct ipa_member_ptr_cst GTY ((tag ("IPA_JF_CONST_MEMBER_PTR"))) member_cst;
struct ipa_pass_through_data GTY ((tag ("IPA_JF_PASS_THROUGH"))) pass_through;
struct ipa_ancestor_jf_data GTY ((tag ("IPA_JF_ANCESTOR"))) ancestor;
- struct ipa_member_ptr_cst GTY ((tag ("IPA_JF_CONST_MEMBER_PTR"))) member_cst;
} GTY ((desc ("%1.type"))) value;
};
+/* All formal parameters in the program have a lattice associated with it
+ computed by the interprocedural stage of IPCP.
+ There are three main values of the lattice:
+ IPA_TOP - unknown,
+ IPA_BOTTOM - non constant,
+ IPA_CONST_VALUE - simple scalar constant,
+ Cval of formal f will have a constant value if all callsites to this
+ function have the same constant value passed to f.
+ Integer and real constants are represented as IPA_CONST_VALUE. */
+enum ipa_lattice_type
+{
+ IPA_BOTTOM,
+ IPA_CONST_VALUE,
+ IPA_TOP
+};
+
/* All formal parameters in the program have a cval computed by
the interprocedural stage of IPCP. See enum ipa_lattice_type for
the various types of lattices supported */
Index: icln/gcc/testsuite/g++.dg/ipa/ivinline-1.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/ivinline-1.C
@@ -0,0 +1,61 @@
+/* Verify that simple virtual calls are inlined even without early
+ inlining. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fdump-ipa-inline -fno-early-inlining -fno-ipa-cp" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int C::foo (int i)
+{
+ return i + 3;
+}
+
+int middleman (class A *obj, int i)
+{
+ return obj->foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+ if (middleman (&b, get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "B::foo\[^\\n\]*inline copy in int main" "inline" } } */
+/* { dg-final { cleanup-ipa-dump "inline" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/ivinline-2.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/ivinline-2.C
@@ -0,0 +1,60 @@
+/* Verify that simple virtual calls using this pointer are inlined
+ even without early inlining.. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fdump-ipa-inline -fno-early-inlining -fno-ipa-cp" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+ int middleman (int i)
+ {
+ return foo (i);
+ }
+};
+
+class B : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int C::foo (int i)
+{
+ return i + 3;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+ if (b.middleman (get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "B::foo\[^\\n\]*inline copy in int main" "inline" } } */
+/* { dg-final { cleanup-ipa-dump "inline" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/ivinline-3.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/ivinline-3.C
@@ -0,0 +1,61 @@
+/* Verify that simple virtual calls on an object refrence are inlined
+ even without early inlining. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fdump-ipa-inline -fno-early-inlining -fno-ipa-cp" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int C::foo (int i)
+{
+ return i + 3;
+}
+
+int middleman (class A &obj, int i)
+{
+ return obj.foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+ if (middleman (b, get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "B::foo\[^\\n\]*inline copy in int main" "inline" } } */
+/* { dg-final { cleanup-ipa-dump "inline" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/ivinline-4.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/ivinline-4.C
@@ -0,0 +1,67 @@
+/* Verify that simple virtual calls are inlined even without early
+ inlining, even when a typecast to an ancestor is involved along the
+ way. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fdump-ipa-inline -fno-early-inlining -fno-ipa-cp" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int C::foo (int i)
+{
+ return i + 3;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+static int middleman_1 (class A *obj, int i)
+{
+ return obj->foo (i);
+}
+
+static int middleman_2 (class B *obj, int i)
+{
+ return middleman_1 (obj, i);
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+ if (middleman_2 (&b, get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "B::foo\[^\\n\]*inline copy in int main" "inline" } } */
+/* { dg-final { cleanup-ipa-dump "inline" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/ivinline-5.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/ivinline-5.C
@@ -0,0 +1,53 @@
+/* Verify that virtual call inlining does not pick a wrong method when
+ there is a user defined ancestor in an object. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fdump-ipa-inline -fno-early-inlining -fno-ipa-cp" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+ class A confusion;
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int middleman (class A *obj, int i)
+{
+ return obj->foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+ int i = get_input ();
+ if ((middleman (&b, i) + 100 * middleman (&b.confusion, i)) != 203)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "A::foo\[^\\n\]*inline copy in int main" "inline" } } */
+/* { dg-final { scan-ipa-dump "B::foo\[^\\n\]*inline copy in int main" "inline" } } */
+/* { dg-final { cleanup-ipa-dump "inline" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/ivinline-6.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/ivinline-6.C
@@ -0,0 +1,56 @@
+/* Verify that virtual call inlining works also when it has to get the
+ type from an ipa invariant and that even in this case it does not
+ pick a wrong method when there is a user defined ancestor in an
+ object. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fdump-ipa-inline -fno-early-inlining -fno-ipa-cp" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+ class A confusion;
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int middleman (class A *obj, int i)
+{
+ return obj->foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+class B b;
+
+int main (int argc, char *argv[])
+{
+ int i = get_input ();
+ if ((middleman (&b, i) + 100 * middleman (&b.confusion, i)) != 203)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "A::foo\[^\\n\]*inline copy in int main" "inline" } } */
+/* { dg-final { scan-ipa-dump "B::foo\[^\\n\]*inline copy in int main" "inline" } } */
+/* { dg-final { cleanup-ipa-dump "inline" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/ivinline-7.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/ivinline-7.C
@@ -0,0 +1,77 @@
+/* Verify that simple virtual calls are inlined even without early
+ inlining, even when a typecast to an ancestor is involved along the
+ way and that ancestor is not the first one with virtual functions. */
+/* { dg-do run } */
+/* { dg-options "-O3 -fdump-ipa-inline -fno-early-inlining -fno-ipa-cp" } */
+
+extern "C" void abort (void);
+
+class Distraction
+{
+public:
+ float f;
+ double d;
+ Distraction ()
+ {
+ f = 8.3;
+ d = 10.2;
+ }
+ virtual float bar (float z);
+};
+
+class A
+{
+public:
+ int data;
+ virtual int foo (int i);
+};
+
+
+class B : public Distraction, public A
+{
+public:
+ virtual int foo (int i);
+};
+
+float Distraction::bar (float z)
+{
+ f += z;
+ return f/2;
+}
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+static int middleman_1 (class A *obj, int i)
+{
+ return obj->foo (i);
+}
+
+static int middleman_2 (class B *obj, int i)
+{
+ return middleman_1 (obj, i);
+}
+
+int main (int argc, char *argv[])
+{
+ class B b;
+
+ if (middleman_2 (&b, get_input ()) != 3)
+ abort ();
+ return 0;
+}
+
+/* { dg-final { scan-ipa-dump "B::foo\[^\\n\]*inline copy in int main" "inline" } } */
+/* { dg-final { cleanup-ipa-dump "inline" } } */
Index: icln/gcc/cgraph.h
===================================================================
--- icln.orig/gcc/cgraph.h
+++ icln/gcc/cgraph.h
@@ -318,11 +318,21 @@ typedef enum {
struct GTY(()) cgraph_indirect_call_info
{
+ /* Offset accumulated from ancestor jump functions of inlined call graph
+ edges. */
+ HOST_WIDE_INT anc_offset;
+ /* OBJ_TYPE_REF_TOKEN of a polymorphic call (if polymorphic is set). */
+ HOST_WIDE_INT otr_token;
+ /* Type of the object from OBJ_TYPE_REF_OBJECT. */
+ tree otr_type;
/* Index of the parameter that is called. */
int param_index;
/* Whether this edge has already been looked at by indirect inlining. */
unsigned int inlining_processed : 1;
+ /* Set when the call is a virtual call with the parameter being the
+ associated object pointer rather than a simple direct call. */
+ unsigned polymorphic : 1;
};
struct GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) cgraph_edge {
Index: icln/gcc/cgraph.c
===================================================================
--- icln.orig/gcc/cgraph.c
+++ icln/gcc/cgraph.c
@@ -1032,8 +1032,8 @@ cgraph_create_indirect_edge (struct cgra
initialize_inline_failed (edge);
edge->indirect_info = GGC_NEW (struct cgraph_indirect_call_info);
+ memset (edge->indirect_info, 0, sizeof (*edge->indirect_info));
edge->indirect_info->param_index = -1;
- edge->indirect_info->inlining_processed = 0;
edge->next_callee = caller->indirect_calls;
if (caller->indirect_calls)
@@ -1972,9 +1972,16 @@ cgraph_clone_edge (struct cgraph_edge *e
}
else
{
+ struct cgraph_indirect_call_info *new_ii, *old_ii = e->indirect_info;
new_edge = cgraph_create_indirect_edge (n, call_stmt, count, freq,
e->loop_nest + loop_nest);
- new_edge->indirect_info->param_index = e->indirect_info->param_index;
+ new_ii = new_edge->indirect_info;
+ new_ii->param_index = old_ii->param_index;
+ new_ii->anc_offset = old_ii->anc_offset;
+ new_ii->otr_token = old_ii->otr_token;
+ new_ii->otr_type = old_ii->otr_type;
+ new_ii->inlining_processed = old_ii->inlining_processed;
+ new_ii->polymorphic = old_ii->polymorphic;
}
}
else
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 3/6] Folding of virtual calls
2010-02-13 18:04 ` [PATCH 3/6] Folding of virtual calls Martin Jambor
@ 2010-02-13 18:12 ` Richard Guenther
0 siblings, 0 replies; 23+ messages in thread
From: Richard Guenther @ 2010-02-13 18:12 UTC (permalink / raw)
To: Martin Jambor; +Cc: GCC Patches, Jan Hubicka
On Sat, Feb 13, 2010 at 7:01 PM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
> this patch has not changed at all since I posted it last time in
> January but needs to be applied before the next one is so I send it
> along again.
>
> The purpose of the patch is to allow folding of more complex
> OBJ_TYPE_REFs, as opposed to only the simple class we are able to fold
> today. This patch only implements devirtualization through statement
> folding (which is also greatly improved, for example we can now fold
> when early inlining makes type information available). However, it
> also facilitates interface necessary for IPA devirtualization
> including indirect inlining of virtual calls.
>
> The juggling with binfos is a bit bizarre and perhaps a C++ maintainer
> should have a look at it but it has worked seamlessly in my tests for
> a few months now so I'm becoming quite confident it is in fact
> correct.
May I ask you to start populating new gimple-fold.[ch] files instead of
adding to gimple.c? Eventually all of fold_stmt should move there
from tree-ssa-ccp.c, but of course not as part of this patch.
Thanks,
Richard.
> Thanks,
>
> Martin
>
>
> 2010-02-10 Martin Jambor <mjambor@suse.cz>
>
> * gimple.c (get_base_binfo_for_type): New function.
> (get_relevant_ref_binfo_single_inh): New function.
> (get_relevant_ref_binfo_multi_inh): New function.
> (gimple_fold_obj_type_ref_known_binfo): New function.
> (gimple_fold_obj_type_ref): Get binfo from
> get_relevant_ref_binfo_single_inh and
> get_relevant_ref_binfo_multi_inh and use
> gimple_fold_obj_type_ref_known_binfo.
> * gimple.h (gimple_fold_obj_type_ref): Declare.
> (gimple_fold_obj_type_ref_known_binfo): Declare.
> * tree-ssa-ccp.c (fold_gimple_call): Simplify condition for
> folding virtual calls and call gimple_fold_obj_type_ref.
>
>
> Index: icln/gcc/gimple.c
> ===================================================================
> --- icln.orig/gcc/gimple.c
> +++ icln/gcc/gimple.c
> @@ -4632,27 +4632,167 @@ gimple_decl_printable_name (tree decl, i
> return IDENTIFIER_POINTER (DECL_NAME (decl));
> }
>
> +/* Search for a base binfo of BINFO that corresponds to TYPE and return it if
> + it is found or NULL_TREE if it is not. */
> +
> +static tree
> +get_base_binfo_for_type (tree binfo, tree type)
> +{
> + int i;
> + tree base_binfo;
> + tree res = NULL_TREE;
> +
> + for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
> + if (TREE_TYPE (base_binfo) == type)
> + {
> + gcc_assert (!res);
> + res = base_binfo;
> + }
> +
> + return res;
> +}
> +
> +/* Return a binfo describing the true type of object referenced by expression
> + REF if all component references access first ancestors. REF can consist of
> + a series of COMPONENT_REFs of with a declaration or an INDIREC_REF. It can
> + also be just a simple declaration, indirect reference or an SSA_NAME. If
> + the function discoveres an INIDRECT_REF or an SSA_NAME, it will assume that
> + the encapsulating type is described by KNOWN_BINFO or return NULL_TREE if
> + KNOWN_BINFO is NULL_TREE. Otherwise the first nonartifical field declaration
> + or the base declaration will be examined to get the encapsulating type. If
> + a COMPONENT_REF referencing an ancestor which is not the first one, this
> + function returns NULL_TREE and sets *try_multi to true. */
> +
> +static tree
> +get_relevant_ref_binfo_single_inh (tree ref, tree known_binfo, bool *try_multi)
> +{
> + while (true)
> + {
> + if (TREE_CODE (ref) == COMPONENT_REF)
> + {
> + tree par_type;
> + tree binfo, base_binfo;
> + tree field = TREE_OPERAND (ref, 1);
> +
> + if (!DECL_ARTIFICIAL (field))
> + {
> + tree type = TREE_TYPE (field);
> + if (TREE_CODE (type) == RECORD_TYPE)
> + return TYPE_BINFO (type);
> + else
> + return NULL_TREE;
> + }
> +
> + par_type = TREE_TYPE (TREE_OPERAND (ref, 0));
> + binfo = TYPE_BINFO (par_type);
> + if (!binfo
> + || BINFO_N_BASE_BINFOS (binfo) == 0)
> + {
> + if (try_multi)
> + *try_multi = 1;
> + return NULL_TREE;
> + }
> + base_binfo = BINFO_BASE_BINFO (binfo, 0);
> + if (TREE_TYPE (base_binfo) != TREE_TYPE (field))
> + {
> + if (try_multi)
> + *try_multi = 1;
> + return NULL_TREE;
> + }
> +
> + ref = TREE_OPERAND (ref, 0);
> + }
> + else if (DECL_P (ref) && TREE_CODE (TREE_TYPE (ref)) == RECORD_TYPE)
> + return TYPE_BINFO (TREE_TYPE (ref));
> + else if (known_binfo
> + && (TREE_CODE (ref) == SSA_NAME
> + || TREE_CODE (ref) == INDIRECT_REF))
> + return known_binfo;
> + else
> + return NULL_TREE;
> + }
> +}
>
> -/* Fold a OBJ_TYPE_REF expression to the address of a function.
> - KNOWN_TYPE carries the true type of OBJ_TYPE_REF_OBJECT(REF). Adapted
> - from cp_fold_obj_type_ref, but it tolerates types with no binfo
> - data. */
> +
> +/* Return a binfo describing the part of object referenced by expression REF.
> + This can and often is a base_binfo of a descendatn binfo. REF can consist of
> + a series of COMPONENT_REFs of with a declaration or an INDIREC_REF. It can
> + also be just a simple declaration, indirect reference or an SSA_NAME. If
> + the function discoveres an INIDRECT_REF or an SSA_NAME, it will assume that
> + the encapsulating type is described by KNOWN_BINFO or return NULL_TREE if
> + KNOWN_BINFO is NULL_TREE. Otherwise the first nonartifical field
> + declaration or the base declaration will be examined to get the
> + encapsulating type. */
> +
> +static tree
> +get_relevant_ref_binfo_multi_inh (tree ref, tree known_binfo)
> +{
> + if (DECL_P (ref) && TREE_CODE (TREE_TYPE (ref)) == RECORD_TYPE)
> + return TYPE_BINFO (TREE_TYPE (ref));
> + else if (TREE_CODE (ref) == COMPONENT_REF)
> + {
> + tree desc_binfo;
> + tree field = TREE_OPERAND (ref, 1);
> +
> + if (!DECL_ARTIFICIAL (field))
> + {
> + tree type = TREE_TYPE (field);
> + if (TREE_CODE (type) == RECORD_TYPE)
> + return TYPE_BINFO (type);
> + else
> + return NULL_TREE;
> + }
> +
> + desc_binfo = get_relevant_ref_binfo_multi_inh (TREE_OPERAND (ref, 0),
> + known_binfo);
> + if (!desc_binfo)
> + return NULL_TREE;
> + return get_base_binfo_for_type (desc_binfo, TREE_TYPE (field));
> + }
> + else if (known_binfo
> + && (TREE_CODE (ref) == SSA_NAME
> + || TREE_CODE (ref) == INDIRECT_REF))
> + return known_binfo;
> + else
> + return NULL_TREE;
> +}
> +
> +/* Return a binfo describing the part of object referenced by expression REF
> + using both get_relevant_ref_binfo_single_inh and
> + get_relevant_ref_binfo_multi_inh in this particular order. */
>
> tree
> -gimple_fold_obj_type_ref (tree ref, tree known_type)
> +gimple_get_relevant_ref_binfo (tree ref, tree known_binfo)
> +{
> + bool try_multi = false;
> + tree binfo;
> +
> + binfo = get_relevant_ref_binfo_single_inh (ref, known_binfo, &try_multi);
> + if (!binfo && try_multi)
> + binfo = get_relevant_ref_binfo_multi_inh (ref, known_binfo);
> + return binfo;
> +}
> +
> +
> +/* Fold a OBJ_TYPE_REF expression to the address of a function. TOKEN is
> + integer form of OBJ_TYPE_REF_TOKEN of the reference expression. KNOWN_BINFO
> + carries the binfo describing the true type of OBJ_TYPE_REF_OBJECT(REF). */
> +
> +tree
> +gimple_fold_obj_type_ref_known_binfo (HOST_WIDE_INT token, tree known_binfo)
> {
> - HOST_WIDE_INT index;
> HOST_WIDE_INT i;
> - tree v;
> - tree fndecl;
> + tree v, fndecl;
>
> - if (TYPE_BINFO (known_type) == NULL_TREE)
> + /* If binfo flag 2 is not set, this binfo does not "have its own virtual
> + table" (according to cp/cp-tree.h) and cannot be safely used for
> + devirtualization. Purely empirical experience also shows that we can also
> + bail out if flag 5 is set. This test also probably works in lto. */
> + if (BINFO_FLAG_5 (known_binfo))
> return NULL_TREE;
> -
> - v = BINFO_VIRTUALS (TYPE_BINFO (known_type));
> - index = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
> + v = BINFO_VIRTUALS (known_binfo);
> i = 0;
> - while (i != index)
> + while (i != token)
> {
> i += (TARGET_VTABLE_USES_DESCRIPTORS
> ? TARGET_VTABLE_USES_DESCRIPTORS : 1);
> @@ -4660,15 +4800,34 @@ gimple_fold_obj_type_ref (tree ref, tree
> }
>
> fndecl = TREE_VALUE (v);
> + return build_fold_addr_expr (fndecl);
> +}
>
> -#ifdef ENABLE_CHECKING
> - gcc_assert (tree_int_cst_equal (OBJ_TYPE_REF_TOKEN (ref),
> - DECL_VINDEX (fndecl)));
> -#endif
>
> - cgraph_node (fndecl)->local.vtable_method = true;
> +/* Fold a OBJ_TYPE_REF expression to the address of a function. If KNOWN_TYPE
> + is not NULL_TREE, it is the true type of the outmost encapsulating object if
> + that comes from a pointer SSA_NAME. If the true outmost encapsulating type
> + can be determined from a declaration OBJ_TYPE_REF_OBJECT(REF), it is used
> + regardless of KNOWN_TYPE (which thuc can be NULL_TREE). */
>
> - return build_fold_addr_expr (fndecl);
> +tree
> +gimple_fold_obj_type_ref (tree ref, tree known_type)
> +{
> + tree obj = OBJ_TYPE_REF_OBJECT (ref);
> + tree known_binfo = known_type ? TYPE_BINFO (known_type) : NULL_TREE;
> + tree binfo;
> +
> + if (TREE_CODE (obj) == ADDR_EXPR)
> + obj = TREE_OPERAND (obj, 0);
> +
> + binfo = gimple_get_relevant_ref_binfo (obj, known_binfo);
> + if (binfo)
> + {
> + HOST_WIDE_INT token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
> + return gimple_fold_obj_type_ref_known_binfo (token, binfo);
> + }
> + else
> + return NULL_TREE;
> }
>
> #include "gt-gimple.h"
> Index: icln/gcc/tree-ssa-ccp.c
> ===================================================================
> --- icln.orig/gcc/tree-ssa-ccp.c
> +++ icln/gcc/tree-ssa-ccp.c
> @@ -3007,9 +3007,6 @@ fold_gimple_call (gimple_stmt_iterator *
> }
> else
> {
> - /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve
> - here are when we've propagated the address of a decl into the
> - object slot. */
> /* ??? Should perhaps do this in fold proper. However, doing it
> there requires that we create a new CALL_EXPR, and that requires
> copying EH region info to the new node. Easier to just do it
> @@ -3017,19 +3014,11 @@ fold_gimple_call (gimple_stmt_iterator *
> /* ??? Is there a good reason not to do this in fold_stmt_inplace? */
> callee = gimple_call_fn (stmt);
> if (TREE_CODE (callee) == OBJ_TYPE_REF
> - && lang_hooks.fold_obj_type_ref
> - && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
> - && DECL_P (TREE_OPERAND
> - (OBJ_TYPE_REF_OBJECT (callee), 0)))
> + && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR)
> {
> tree t;
>
> - /* ??? Caution: Broken ADDR_EXPR semantics means that
> - looking at the type of the operand of the addr_expr
> - can yield an array type. See silly exception in
> - check_pointer_types_r. */
> - t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
> - t = lang_hooks.fold_obj_type_ref (callee, t);
> + t = gimple_fold_obj_type_ref (callee, NULL_TREE);
> if (t)
> {
> gimple_call_set_fn (stmt, t);
> Index: icln/gcc/gimple.h
> ===================================================================
> --- icln.orig/gcc/gimple.h
> +++ icln/gcc/gimple.h
> @@ -864,7 +864,9 @@ unsigned get_gimple_rhs_num_ops (enum tr
> #define gimple_alloc(c, n) gimple_alloc_stat (c, n MEM_STAT_INFO)
> gimple gimple_alloc_stat (enum gimple_code, unsigned MEM_STAT_DECL);
> const char *gimple_decl_printable_name (tree, int);
> +tree gimple_get_relevant_ref_binfo (tree ref, tree known_binfo);
> tree gimple_fold_obj_type_ref (tree, tree);
> +tree gimple_fold_obj_type_ref_known_binfo (HOST_WIDE_INT, tree);
>
> /* Returns true iff T is a valid GIMPLE statement. */
> extern bool is_gimple_stmt (tree);
> Index: icln/gcc/testsuite/g++.dg/otr-fold-1.C
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/g++.dg/otr-fold-1.C
> @@ -0,0 +1,77 @@
> +/* Verify that simple virtual calls are inlined even without early
> + inlining, even when a typecast to an ancestor is involved along the
> + way. */
> +/* { dg-do run } */
> +/* { dg-options "-O -fdump-tree-optimized-slim" } */
> +
> +extern "C" void abort (void);
> +
> +class Distraction
> +{
> +public:
> + float f;
> + double d;
> + Distraction ()
> + {
> + f = 8.3;
> + d = 10.2;
> + }
> + virtual float bar (float z);
> +};
> +
> +class A
> +{
> +public:
> + int data;
> + virtual int foo (int i);
> +};
> +
> +
> +class B : public Distraction, public A
> +{
> +public:
> + virtual int foo (int i);
> +};
> +
> +float Distraction::bar (float z)
> +{
> + f += z;
> + return f/2;
> +}
> +
> +int A::foo (int i)
> +{
> + return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> + return i + 2;
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> + return 1;
> +}
> +
> +static int middleman_1 (class A *obj, int i)
> +{
> + return obj->foo (i);
> +}
> +
> +static int middleman_2 (class B *obj, int i)
> +{
> + return middleman_1 (obj, i);
> +}
> +
> +int main (int argc, char *argv[])
> +{
> + class B b;
> +
> + if (middleman_2 (&b, get_input ()) != 3)
> + abort ();
> + return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump "= B::foo" "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>
>
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 4/6] Remove unused ipa_note_param_call.called flag (approved)
2010-02-13 18:04 ` [PATCH 4/6] Remove unused ipa_note_param_call.called flag (approved) Martin Jambor
@ 2010-02-13 18:14 ` Richard Guenther
2010-03-05 16:19 ` Martin Jambor
2010-02-22 15:04 ` Jan Hubicka
1 sibling, 1 reply; 23+ messages in thread
From: Richard Guenther @ 2010-02-13 18:14 UTC (permalink / raw)
To: Martin Jambor; +Cc: GCC Patches, Jan Hubicka
On Sat, Feb 13, 2010 at 7:01 PM, Martin Jambor <mjambor@suse.cz> wrote:
> This patch is a minor cleanup. I have realized that the called flag
> in the ipa-prop parameter descriptor is not used and I could not
> really think how the flag can be obviously useful in a short-term
> either so I removed it.
>
> I have bootstrapped and tested this change along with the next one in
> the series.
>
> The patch has already been approved by Honza but this is its place in
> the series and so I re-send it along.
If this applies independently of the rest of the series it is ok for the trunk
at this stage.
Thanks,
Richard.
> Thanks,
>
> Martin
>
>
> 2009-12-28 Martin Jambor <mjambor@suse.cz>
>
> * ipa-prop.h (struct ipa_param_descriptor): Removed the called field.
> (ipa_is_param_called): Removed.
> * ipa-prop.c (ipa_note_param_call): Do not set the called flag.
> Removed parameter info.
> (ipa_print_node_params): Do not print the called flag.
>
> Index: icln/gcc/ipa-prop.c
> ===================================================================
> --- icln.orig/gcc/ipa-prop.c
> +++ icln/gcc/ipa-prop.c
> @@ -736,20 +736,16 @@ ipa_is_ssa_with_stmt_def (tree t)
> }
>
> /* Create a new indirect call graph edge describing a call to a parameter
> - number FORMAL_ID and and set the called flag of the parameter. NODE is the
> - caller and is described by INFO. STMT is the corresponding call
> + number FORMAL_ID. NODE is the caller, STMT is the corresponding call
> statement. */
>
> static void
> -ipa_note_param_call (struct cgraph_node *node, struct ipa_node_params *info,
> - int formal_id, gimple stmt)
> +ipa_note_param_call (struct cgraph_node *node, int formal_id, gimple stmt)
> {
> struct cgraph_edge *cs;
> basic_block bb = gimple_bb (stmt);
> int freq;
>
> - info->params[formal_id].called = 1;
> -
> freq = compute_call_stmt_bb_frequency (current_function_decl, bb);
> cs = cgraph_create_indirect_edge (node, stmt, bb->count, freq,
> bb->loop_depth);
> @@ -826,7 +822,7 @@ ipa_analyze_call_uses (struct cgraph_nod
> /* assuming TREE_CODE (var) == PARM_DECL */
> index = ipa_get_param_decl_index (info, var);
> if (index >= 0)
> - ipa_note_param_call (node, info, index, call);
> + ipa_note_param_call (node, index, call);
> return;
> }
>
> @@ -923,7 +919,7 @@ ipa_analyze_call_uses (struct cgraph_nod
>
> index = ipa_get_param_decl_index (info, rec);
> if (index >= 0 && !ipa_is_param_modified (info, index))
> - ipa_note_param_call (node, info, index, call);
> + ipa_note_param_call (node, index, call);
>
> return;
> }
> @@ -1405,8 +1401,6 @@ ipa_print_node_params (FILE * f, struct
> : "(unnamed)"));
> if (ipa_is_param_modified (info, i))
> fprintf (f, " modified");
> - if (ipa_is_param_called (info, i))
> - fprintf (f, " called");
> fprintf (f, "\n");
> }
> }
> Index: icln/gcc/ipa-prop.h
> ===================================================================
> --- icln.orig/gcc/ipa-prop.h
> +++ icln/gcc/ipa-prop.h
> @@ -143,8 +143,6 @@ struct ipa_param_descriptor
> tree decl;
> /* Whether the value parameter has been modified within the function. */
> unsigned modified : 1;
> - /* Whether the parameter has been used as a call destination. */
> - unsigned called : 1;
> };
>
> /* ipa_node_params stores information related to formal parameters of functions
> @@ -220,17 +218,6 @@ ipa_is_param_modified (struct ipa_node_p
> return info->params[i].modified;
> }
>
> -/* Return the called flag corresponding to the Ith formal parameter of the
> - function associated with INFO. Note that there is no setter method as the
> - goal is to set all flags when building the array in
> - ipa_detect_called_params. */
> -
> -static inline bool
> -ipa_is_param_called (struct ipa_node_params *info, int i)
> -{
> - return info->params[i].called;
> -}
> -
> /* Flag this node as having callers with variable number of arguments. */
>
> static inline void
>
>
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 2/6] Indirect call graph edges
2010-02-13 18:04 ` [PATCH 2/6] Indirect call graph edges Martin Jambor
@ 2010-02-13 18:17 ` Richard Guenther
2010-02-13 18:25 ` Richard Guenther
2010-02-22 15:52 ` Jan Hubicka
1 sibling, 1 reply; 23+ messages in thread
From: Richard Guenther @ 2010-02-13 18:17 UTC (permalink / raw)
To: Martin Jambor; +Cc: GCC Patches, Jan Hubicka
On Sat, Feb 13, 2010 at 7:01 PM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
> this is a re-post of the same patch I already sent here in January.
> There are only minor differences. I have renamed the flag
> indirect_call to indirect_inlining_edge and changed its purpose to be
> exactly that, an edge made direct by indirect inlining (it may go away
> completely, I currently use it only for asserts in ipa-cp
> devirtualization) and I have added a few things to cgraph node
> dumping. Most importantly, I have re-worked streaming so that
> information for indirect inlining associated with nodes is written to
> the jump functions section again in order to allow the cgraph stream
> to remain simple and concise (which means it cannot store trees).
>
> The patch adds a new kind of edge to the call graph to represent
> indirect calls with unknown callees (which we hope we can determine at
> some stage) and uses them to replace ipa_param_call_notes in
> ipa-prop.h. My immediate reason to do this is to move all the
> information there from the notes because I will need them to be in
> memory managed by the garbage collector (and did not want
> ipa_node_params to become garbage collected) but in a broader sense
> this is the right thing to do because it facilitates a more general
> approach to keep information about such calls (ipa-cp jump functions
> and the like) that is also consistent with how we do this for direct
> edges.
>
> The data structure layout (a flag and a pointer in struct cgraph_edge
> to a another special structure) was really chosen by Honza. The
> subsequent patches add some more stuff to cgraph_indirect_call_info so
> it won't look this silly for long.
>
> I have successfully bootstrapped and tested this beast on x86_84-linux
> and would like to commit something along these lines when stage1 opens
> again. Obviously, I welcome any comments.
The cgraph.c file at the top currently contains very brief documentation
which needs to be updated as it says:
The callgraph at the moment does not represent indirect calls or calls
from other compilation unit.
Note that I think we should have some more elaborate overall overview
about the cgraph interface.
Thanks,
Richard.
> Thanks,
>
> Martin
>
>
> 2010-02-10 Martin Jambor <mjambor@suse.cz>
>
> * cgraph.h (struct cgraph_node): New field indirect_calls.
> (struct cgraph_indirect_call_info): New type.
> (struct cgraph_edge): Removed field indirect_call. New fields
> indirect_info, indirect_inlining_edge and indirect_unknown_callee.
> (cgraph_create_indirect_edge): Declare.
> (cgraph_make_edge_direct): Likewise.
> (enum LTO_cgraph_tags): New item LTO_cgraph_indirect_edge.
> * ipa-prop.h (struct ipa_param_call_note): Removed.
> (struct ipa_node_params): Removed field param_calls.
> * cgraph.c (cgraph_add_edge_to_call_site_hash): New function.
> (cgraph_edge): Search also among the indirect edges, use
> cgraph_add_edge_to_call_site_hash to add edges to the call site hash.
> (cgraph_set_call_stmt): Possibly turn an indirect edge into a direct
> one, use cgraph_add_edge_to_call_site_hash to add edges to the call
> site hash.
> (initialize_inline_failed): Assign a reason to indirect edges.
> (cgraph_create_edge_1): New function.
> (cgraph_create_edge): Moved some functionality to
> cgraph_create_edge_1.
> (cgraph_create_indirect_edge): New function.
> (cgraph_edge_remove_callee): Add an assert checking for
> non-indirectness.
> (cgraph_edge_remove_caller): Special-case indirect edges.
> (cgraph_remove_edge): Likewise.
> (cgraph_set_edge_callee): New function.
> (cgraph_redirect_edge_callee): Use cgraph_set_edge_callee.
> (cgraph_make_edge_direct): New function.
> (cgraph_update_edges_for_call_stmt_node): Do nothing only when also
> the declaration of the call statement matches.
> (cgraph_node_remove_callees): Special-case indirect edges.
> (cgraph_clone_edge): Likewise.
> (cgraph_clone_node): Clone also the indirect edges.
> (dump_cgraph_node): Dump indirect_inlining_edge flag instead of
> indirect_call, dump count of indirect_calls edges.
> * ipa-prop.c (ipa_note_param_call): Create indirect edges instead of
> creating notes. New parameter node.
> (ipa_analyze_call_uses): New parameter node, pass it on to
> ipa_note_param_call.
> (ipa_analyze_stmt_uses): Likewise.
> (ipa_analyze_params_uses): Pass node to ipa_analyze_stmt_uses.
> (print_edge_addition_message): Work on edges rather than on notes.
> (update_call_notes_after_inlining): Likewise.
> (ipa_free_node_params_substructures): Do not free notes.
> (ipa_node_duplication_hook): Do not duplicate notes.
> (ipa_write_param_call_note): Removed.
> (ipa_read_param_call_note): Removed.
> (ipa_write_indirect_edge_info): New function.
> (ipa_read_indirect_edge_info): Likewise.
> (ipa_write_node_info): Do not stream notes, do stream information
> in indirect edges.
> (ipa_read_node_info): Likewise.
> (lto_ipa_fixup_call_notes): Removed.
> * ipa-cp.c (pass_ipa_cp): Set stmt_fixup to NULL.
> * ipa-inline.c (pass_ipa_inline): Likewise.
> * cgraphunit.c (verify_cgraph_node): Check also indirect edges.
> * cif-code.def (INDIRECT_UNKNOWN_CALL): New reason.
> * tree-inline.c (copy_bb): Removed an unnecessary double check for
> is_gimple_call.
> * tree-inline.c (get_indirect_callee_fndecl): Do not consider indirect
> edges.
> * lto-cgraph.c (output_outgoing_cgraph_edges): New function.
> (output_cgraph): Stream also indirect edges.
> (lto_output_edge): Added capability to stream indirect edges.
> (input_edge): Likewise.
> (input_cgraph_1): Likewise.
>
> * testsuite/gcc.dg/lto/20091209-1_0.c: New testcase.
>
>
> Index: icln/gcc/cgraph.h
> ===================================================================
> --- icln.orig/gcc/cgraph.h
> +++ icln/gcc/cgraph.h
> @@ -184,6 +184,9 @@ struct GTY((chain_next ("%h.next"), chai
> struct cgraph_edge *callers;
> struct cgraph_node *next;
> struct cgraph_node *previous;
> + /* List of edges representing indirect calls with a yet undetermined
> + caller. */
> + struct cgraph_edge *indirect_calls;
> /* For nested functions points to function the node is nested in. */
> struct cgraph_node *origin;
> /* Points to first nested function, if any. */
> @@ -311,6 +314,17 @@ typedef enum {
> CIF_N_REASONS
> } cgraph_inline_failed_t;
>
> +/* Structure containing additional information about an indirect call. */
> +
> +struct GTY(()) cgraph_indirect_call_info
> +{
> + /* Index of the parameter that is called. */
> + int param_index;
> +
> + /* Whether this edge has already been looked at by indirect inlining. */
> + unsigned int inlining_processed : 1;
> +};
> +
> struct GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) cgraph_edge {
> /* Expected number of executions: calculated in profile.c. */
> gcov_type count;
> @@ -321,6 +335,8 @@ struct GTY((chain_next ("%h.next_caller"
> struct cgraph_edge *prev_callee;
> struct cgraph_edge *next_callee;
> gimple call_stmt;
> + /* Additional information about an indirect call. Can be NULL for */
> + struct cgraph_indirect_call_info *indirect_info;
> PTR GTY ((skip (""))) aux;
> /* When equal to CIF_OK, inline this call. Otherwise, points to the
> explanation why function was not inlined. */
> @@ -336,8 +352,12 @@ struct GTY((chain_next ("%h.next_caller"
> int uid;
> /* Depth of loop nest, 1 means no loop nest. */
> unsigned short int loop_nest;
> - /* Whether this edge describes a call that was originally indirect. */
> - unsigned int indirect_call : 1;
> + /* Whether this edge was created by indirect inlining. */
> + unsigned int indirect_inlining_edge : 1;
> + /* Whether this edge describes an inderect call with an undetermined
> + callee. */
> + unsigned int indirect_unknown_callee : 1;
> + /* Whether this edge is still a danglig */
> /* True if the corresponding CALL stmt cannot be inlined. */
> unsigned int call_stmt_cannot_inline_p : 1;
> /* Can this call throw externally? */
> @@ -435,7 +455,8 @@ void cgraph_node_remove_callees (struct
> struct cgraph_edge *cgraph_create_edge (struct cgraph_node *,
> struct cgraph_node *,
> gimple, gcov_type, int, int);
> -
> +struct cgraph_edge *cgraph_create_indirect_edge (struct cgraph_node *, gimple,
> + gcov_type, int, int);
> struct cgraph_node * cgraph_get_node (tree);
> struct cgraph_node *cgraph_node (tree);
> bool cgraph_same_body_alias (tree, tree);
> @@ -461,6 +482,7 @@ struct cgraph_node * cgraph_clone_node (
> int, bool, VEC(cgraph_edge_p,heap) *);
>
> void cgraph_redirect_edge_callee (struct cgraph_edge *, struct cgraph_node *);
> +void cgraph_make_edge_direct (struct cgraph_edge *, struct cgraph_node *);
>
> struct cgraph_asm_node *cgraph_add_asm_node (tree);
>
> @@ -628,6 +650,7 @@ enum LTO_cgraph_tags
> LTO_cgraph_overwritable_node,
> LTO_cgraph_unavail_node,
> LTO_cgraph_edge,
> + LTO_cgraph_indirect_edge, /* edges with indirect_unknown_callee set */
> LTO_cgraph_last_tag
> };
>
> Index: icln/gcc/ipa-prop.h
> ===================================================================
> --- icln.orig/gcc/ipa-prop.h
> +++ icln/gcc/ipa-prop.h
> @@ -134,32 +134,6 @@ struct ipcp_lattice
> tree constant;
> };
>
> -/* Each instance of the following structure describes a statement that calls a
> - function parameter. Those referring to statements within the same function
> - are linked in a list. */
> -struct ipa_param_call_note
> -{
> - /* Expected number of executions: calculated in profile.c. */
> - gcov_type count;
> - /* Linked list's next */
> - struct ipa_param_call_note *next;
> - /* Statement that contains the call to the parameter above. */
> - gimple stmt;
> - /* When in LTO, we the above stmt will be NULL and we need an uid. */
> - unsigned int lto_stmt_uid;
> - /* Index of the parameter that is called. */
> - int formal_id;
> - /* Expected frequency of executions within the function. see cgraph_edge in
> - cgraph.h for more on this. */
> - int frequency;
> - /* Depth of loop nest, 1 means no loop nest. */
> - unsigned short int loop_nest;
> - /* Set when we have already found the target to be a compile time constant
> - and turned this into an edge or when the note was found unusable for some
> - reason. */
> - bool processed;
> -};
> -
> /* Structure describing a single formal parameter. */
> struct ipa_param_descriptor
> {
> @@ -185,8 +159,6 @@ struct ipa_node_params
> /* Pointer to an array of structures describing individual formal
> parameters. */
> struct ipa_param_descriptor *params;
> - /* List of structures enumerating calls to a formal parameter. */
> - struct ipa_param_call_note *param_calls;
> /* Only for versioned nodes this field would not be NULL,
> it points to the node that IPA cp cloned from. */
> struct cgraph_node *ipcp_orig_node;
> Index: icln/gcc/cgraph.c
> ===================================================================
> --- icln.orig/gcc/cgraph.c
> +++ icln/gcc/cgraph.c
> @@ -721,6 +721,19 @@ edge_eq (const void *x, const void *y)
> return ((const struct cgraph_edge *) x)->call_stmt == y;
> }
>
> +/* Add call graph edge E to call site hash of its caller. */
> +
> +static inline void
> +cgraph_add_edge_to_call_site_hash (struct cgraph_edge *e)
> +{
> + void **slot;
> + slot = htab_find_slot_with_hash (e->caller->call_site_hash,
> + e->call_stmt,
> + htab_hash_pointer (e->call_stmt),
> + INSERT);
> + gcc_assert (!*slot);
> + *slot = e;
> +}
>
> /* Return the callgraph edge representing the GIMPLE_CALL statement
> CALL_STMT. */
> @@ -741,26 +754,28 @@ cgraph_edge (struct cgraph_node *node, g
> solution. It is not good idea to add pointer into CALL_EXPR itself
> because we want to make possible having multiple cgraph nodes representing
> different clones of the same body before the body is actually cloned. */
> - for (e = node->callees; e; e= e->next_callee)
> + for (e = node->callees; e; e = e->next_callee)
> {
> if (e->call_stmt == call_stmt)
> break;
> n++;
> }
>
> + if (!e)
> + for (e = node->indirect_calls; e; e = e->next_callee)
> + {
> + if (e->call_stmt == call_stmt)
> + break;
> + n++;
> + }
> +
> if (n > 100)
> {
> node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
> for (e2 = node->callees; e2; e2 = e2->next_callee)
> - {
> - void **slot;
> - slot = htab_find_slot_with_hash (node->call_site_hash,
> - e2->call_stmt,
> - htab_hash_pointer (e2->call_stmt),
> - INSERT);
> - gcc_assert (!*slot);
> - *slot = e2;
> - }
> + cgraph_add_edge_to_call_site_hash (e2);
> + for (e2 = node->indirect_calls; e2; e2 = e2->next_callee)
> + cgraph_add_edge_to_call_site_hash (e2);
> }
>
> return e;
> @@ -772,26 +787,31 @@ cgraph_edge (struct cgraph_node *node, g
> void
> cgraph_set_call_stmt (struct cgraph_edge *e, gimple new_stmt)
> {
> + tree decl;
> +
> if (e->caller->call_site_hash)
> {
> htab_remove_elt_with_hash (e->caller->call_site_hash,
> e->call_stmt,
> htab_hash_pointer (e->call_stmt));
> }
> +
> e->call_stmt = new_stmt;
> + if (e->indirect_unknown_callee
> + && (decl = gimple_call_fndecl (new_stmt)))
> + {
> + /* Constant propagation (and possibly also inlining?) can turn an
> + indirect call into a direct one. */
> + struct cgraph_node *new_callee = cgraph_node (decl);
> +
> + cgraph_make_edge_direct (e, new_callee);
> + }
> +
> push_cfun (DECL_STRUCT_FUNCTION (e->caller->decl));
> e->can_throw_external = stmt_can_throw_external (new_stmt);
> pop_cfun ();
> if (e->caller->call_site_hash)
> - {
> - void **slot;
> - slot = htab_find_slot_with_hash (e->caller->call_site_hash,
> - e->call_stmt,
> - htab_hash_pointer
> - (e->call_stmt), INSERT);
> - gcc_assert (!*slot);
> - *slot = e;
> - }
> + cgraph_add_edge_to_call_site_hash (e);
> }
>
> /* Like cgraph_set_call_stmt but walk the clone tree and update all
> @@ -893,7 +913,9 @@ initialize_inline_failed (struct cgraph_
> {
> struct cgraph_node *callee = e->callee;
>
> - if (!callee->analyzed)
> + if (e->indirect_unknown_callee)
> + e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
> + else if (!callee->analyzed)
> e->inline_failed = CIF_BODY_NOT_AVAILABLE;
> else if (callee->local.redefined_extern_inline)
> e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
> @@ -905,15 +927,16 @@ initialize_inline_failed (struct cgraph_
> e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
> }
>
> -/* Create edge from CALLER to CALLEE in the cgraph. */
> -
> -struct cgraph_edge *
> -cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
> - gimple call_stmt, gcov_type count, int freq, int nest)
> +/* Allocate a cgraph_edge structure and fill it with data according to the
> + parameters ow which only CALLEE can be NULL (when creating an indirect call
> + edge). */
> +
> +static struct cgraph_edge *
> +cgraph_create_edge_1 (struct cgraph_node *caller, struct cgraph_node *callee,
> + gimple call_stmt, gcov_type count, int freq, int nest)
> {
> struct cgraph_edge *edge;
>
> -
> /* LTO does not actually have access to the call_stmt since these
> have not been loaded yet. */
> if (call_stmt)
> @@ -939,47 +962,84 @@ cgraph_create_edge (struct cgraph_node *
> }
>
> edge->aux = NULL;
> -
> edge->caller = caller;
> edge->callee = callee;
> + edge->prev_caller = NULL;
> + edge->next_caller = NULL;
> + edge->prev_callee = NULL;
> + edge->next_callee = NULL;
> +
> + edge->count = count;
> + gcc_assert (count >= 0);
> + edge->frequency = freq;
> + gcc_assert (freq >= 0);
> + gcc_assert (freq <= CGRAPH_FREQ_MAX);
> + edge->loop_nest = nest;
> +
> edge->call_stmt = call_stmt;
> push_cfun (DECL_STRUCT_FUNCTION (caller->decl));
> edge->can_throw_external
> = call_stmt ? stmt_can_throw_external (call_stmt) : false;
> pop_cfun ();
> - edge->prev_caller = NULL;
> + edge->call_stmt_cannot_inline_p =
> + (call_stmt ? gimple_call_cannot_inline_p (call_stmt) : false);
> + if (call_stmt && caller->call_site_hash)
> + cgraph_add_edge_to_call_site_hash (edge);
> +
> + edge->indirect_info = NULL;
> + edge->indirect_inlining_edge = 0;
> +
> + return edge;
> +}
> +
> +/* Create edge from CALLER to CALLEE in the cgraph. */
> +
> +struct cgraph_edge *
> +cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
> + gimple call_stmt, gcov_type count, int freq, int nest)
> +{
> + struct cgraph_edge *edge = cgraph_create_edge_1 (caller, callee, call_stmt,
> + count, freq, nest);
> +
> + edge->indirect_unknown_callee = 0;
> + initialize_inline_failed (edge);
> +
> edge->next_caller = callee->callers;
> if (callee->callers)
> callee->callers->prev_caller = edge;
> - edge->prev_callee = NULL;
> edge->next_callee = caller->callees;
> if (caller->callees)
> caller->callees->prev_callee = edge;
> caller->callees = edge;
> callee->callers = edge;
> - edge->count = count;
> - gcc_assert (count >= 0);
> - edge->frequency = freq;
> - gcc_assert (freq >= 0);
> - gcc_assert (freq <= CGRAPH_FREQ_MAX);
> - edge->loop_nest = nest;
> - edge->indirect_call = 0;
> - edge->call_stmt_cannot_inline_p =
> - (call_stmt ? gimple_call_cannot_inline_p (call_stmt) : false);
> - if (call_stmt && caller->call_site_hash)
> - {
> - void **slot;
> - slot = htab_find_slot_with_hash (caller->call_site_hash,
> - edge->call_stmt,
> - htab_hash_pointer
> - (edge->call_stmt),
> - INSERT);
> - gcc_assert (!*slot);
> - *slot = edge;
> - }
>
> + return edge;
> +}
> +
> +
> +/* Create an indirect edge with a yet-undetermined callee where the call
> + statement destination is a formal parameter of the caller with index
> + PARAM_INDEX. */
> +
> +struct cgraph_edge *
> +cgraph_create_indirect_edge (struct cgraph_node *caller, gimple call_stmt,
> + gcov_type count, int freq, int nest)
> +{
> + struct cgraph_edge *edge = cgraph_create_edge_1 (caller, NULL, call_stmt,
> + count, freq, nest);
> +
> + edge->indirect_unknown_callee = 1;
> initialize_inline_failed (edge);
>
> + edge->indirect_info = GGC_NEW (struct cgraph_indirect_call_info);
> + edge->indirect_info->param_index = -1;
> + edge->indirect_info->inlining_processed = 0;
> +
> + edge->next_callee = caller->indirect_calls;
> + if (caller->indirect_calls)
> + caller->indirect_calls->prev_callee = edge;
> + caller->indirect_calls = edge;
> +
> return edge;
> }
>
> @@ -988,6 +1048,7 @@ cgraph_create_edge (struct cgraph_node *
> static inline void
> cgraph_edge_remove_callee (struct cgraph_edge *e)
> {
> + gcc_assert (!e->indirect_unknown_callee);
> if (e->prev_caller)
> e->prev_caller->next_caller = e->next_caller;
> if (e->next_caller)
> @@ -1006,7 +1067,12 @@ cgraph_edge_remove_caller (struct cgraph
> if (e->next_callee)
> e->next_callee->prev_callee = e->prev_callee;
> if (!e->prev_callee)
> - e->caller->callees = e->next_callee;
> + {
> + if (e->indirect_unknown_callee)
> + e->caller->indirect_calls = e->next_callee;
> + else
> + e->caller->callees = e->next_callee;
> + }
> if (e->caller->call_site_hash)
> htab_remove_elt_with_hash (e->caller->call_site_hash,
> e->call_stmt,
> @@ -1035,8 +1101,9 @@ cgraph_remove_edge (struct cgraph_edge *
> /* Call all edge removal hooks. */
> cgraph_call_edge_removal_hooks (e);
>
> - /* Remove from callers list of the callee. */
> - cgraph_edge_remove_callee (e);
> + if (!e->indirect_unknown_callee)
> + /* Remove from callers list of the callee. */
> + cgraph_edge_remove_callee (e);
>
> /* Remove from callees list of the callers. */
> cgraph_edge_remove_caller (e);
> @@ -1045,6 +1112,20 @@ cgraph_remove_edge (struct cgraph_edge *
> cgraph_free_edge (e);
> }
>
> +/* Set callee of call graph edge E and add it to the corresponding set of
> + callers. */
> +
> +static void
> +cgraph_set_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
> +{
> + e->prev_caller = NULL;
> + if (n->callers)
> + n->callers->prev_caller = e;
> + e->next_caller = n->callers;
> + n->callers = e;
> + e->callee = n;
> +}
> +
> /* Redirect callee of E to N. The function does not update underlying
> call expression. */
>
> @@ -1055,12 +1136,37 @@ cgraph_redirect_edge_callee (struct cgra
> cgraph_edge_remove_callee (e);
>
> /* Insert to callers list of the new callee. */
> - e->prev_caller = NULL;
> - if (n->callers)
> - n->callers->prev_caller = e;
> - e->next_caller = n->callers;
> - n->callers = e;
> - e->callee = n;
> + cgraph_set_edge_callee (e, n);
> +}
> +
> +/* Make an indirect EDGE with an unknown callee an ordinary edge leading to
> + CALLEE. */
> +
> +void
> +cgraph_make_edge_direct (struct cgraph_edge *edge, struct cgraph_node *callee)
> +{
> + edge->indirect_unknown_callee = 0;
> +
> + /* Get the edge out of the indirect edge list. */
> + if (edge->prev_callee)
> + edge->prev_callee->next_callee = edge->next_callee;
> + if (edge->next_callee)
> + edge->next_callee->prev_callee = edge->prev_callee;
> + if (!edge->prev_callee)
> + edge->caller->indirect_calls = edge->next_callee;
> +
> + /* Put it into the normal callee list */
> + edge->prev_callee = NULL;
> + edge->next_callee = edge->caller->callees;
> + if (edge->caller->callees)
> + edge->caller->callees->prev_callee = edge;
> + edge->caller->callees = edge;
> +
> + /* Insert to callers list of the new callee. */
> + cgraph_set_edge_callee (edge, callee);
> +
> + /* We need to re-determine the inlining status of the edge. */
> + initialize_inline_failed (edge);
> }
>
>
> @@ -1091,7 +1197,7 @@ cgraph_update_edges_for_call_stmt_node (
> {
> /* See if the call is already there. It might be because of indirect
> inlining already found it. */
> - if (new_call && e->callee->decl == new_call)
> + if (new_call && e->callee && e->callee->decl == new_call)
> return;
>
> /* Otherwise remove edge and create new one; we can't simply redirect
> @@ -1169,7 +1275,8 @@ cgraph_node_remove_callees (struct cgrap
> {
> f = e->next_callee;
> cgraph_call_edge_removal_hooks (e);
> - cgraph_edge_remove_callee (e);
> + if (!e->indirect_unknown_callee)
> + cgraph_edge_remove_callee (e);
> cgraph_free_edge (e);
> }
> node->callees = NULL;
> @@ -1624,6 +1731,8 @@ void
> dump_cgraph_node (FILE *f, struct cgraph_node *node)
> {
> struct cgraph_edge *edge;
> + int indirect_calls_count = 0;
> +
> fprintf (f, "%s/%i(%i)", cgraph_node_name (node), node->uid,
> node->pid);
> dump_addr (f, " @", (void *)node);
> @@ -1697,8 +1806,8 @@ dump_cgraph_node (FILE *f, struct cgraph
> edge->frequency / (double)CGRAPH_FREQ_BASE);
> if (!edge->inline_failed)
> fprintf(f, "(inlined) ");
> - if (edge->indirect_call)
> - fprintf(f, "(indirect) ");
> + if (edge->indirect_inlining_edge)
> + fprintf(f, "(indirect_inlining) ");
> if (edge->can_throw_external)
> fprintf(f, "(can throw external) ");
> }
> @@ -1710,8 +1819,8 @@ dump_cgraph_node (FILE *f, struct cgraph
> edge->callee->uid);
> if (!edge->inline_failed)
> fprintf(f, "(inlined) ");
> - if (edge->indirect_call)
> - fprintf(f, "(indirect) ");
> + if (edge->indirect_inlining_edge)
> + fprintf(f, "(indirect_inlining) ");
> if (edge->count)
> fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
> (HOST_WIDEST_INT)edge->count);
> @@ -1725,6 +1834,12 @@ dump_cgraph_node (FILE *f, struct cgraph
> }
> fprintf (f, "\n");
>
> + for (edge = node->indirect_calls; edge; edge = edge->next_callee)
> + indirect_calls_count++;
> + if (indirect_calls_count)
> + fprintf (f, " has %i outgoing edges for indirect calls.\n",
> + indirect_calls_count);
> +
> if (node->same_body)
> {
> struct cgraph_node *n;
> @@ -1844,11 +1959,30 @@ cgraph_clone_edge (struct cgraph_edge *e
> freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
> if (freq > CGRAPH_FREQ_MAX)
> freq = CGRAPH_FREQ_MAX;
> - new_edge = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
> - e->loop_nest + loop_nest);
> +
> + if (e->indirect_unknown_callee)
> + {
> + tree decl;
> +
> + if (call_stmt && (decl = gimple_call_fndecl (call_stmt)))
> + {
> + struct cgraph_node *callee = cgraph_node (decl);
> + new_edge = cgraph_create_edge (n, callee, call_stmt, count, freq,
> + e->loop_nest + loop_nest);
> + }
> + else
> + {
> + new_edge = cgraph_create_indirect_edge (n, call_stmt, count, freq,
> + e->loop_nest + loop_nest);
> + new_edge->indirect_info->param_index = e->indirect_info->param_index;
> + }
> + }
> + else
> + new_edge = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
> + e->loop_nest + loop_nest);
>
> new_edge->inline_failed = e->inline_failed;
> - new_edge->indirect_call = e->indirect_call;
> + new_edge->indirect_inlining_edge = e->indirect_inlining_edge;
> new_edge->lto_stmt_uid = stmt_uid;
> if (update_original)
> {
> @@ -1918,6 +2052,10 @@ cgraph_clone_node (struct cgraph_node *n
> cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
> count_scale, freq, loop_nest, update_original);
>
> + for (e = n->indirect_calls; e; e = e->next_callee)
> + cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
> + count_scale, freq, loop_nest, update_original);
> +
> new_node->next_sibling_clone = n->clones;
> if (n->clones)
> n->clones->prev_sibling_clone = new_node;
> Index: icln/gcc/ipa-prop.c
> ===================================================================
> --- icln.orig/gcc/ipa-prop.c
> +++ icln/gcc/ipa-prop.c
> @@ -735,41 +735,36 @@ ipa_is_ssa_with_stmt_def (tree t)
> return false;
> }
>
> -/* Creates a new note describing a call to a parameter number FORMAL_ID and
> - attaches it to the linked list of INFO. It also sets the called flag of the
> - parameter. STMT is the corresponding call statement. */
> +/* Create a new indirect call graph edge describing a call to a parameter
> + number FORMAL_ID and and set the called flag of the parameter. NODE is the
> + caller and is described by INFO. STMT is the corresponding call
> + statement. */
>
> static void
> -ipa_note_param_call (struct ipa_node_params *info, int formal_id,
> - gimple stmt)
> +ipa_note_param_call (struct cgraph_node *node, struct ipa_node_params *info,
> + int formal_id, gimple stmt)
> {
> - struct ipa_param_call_note *note;
> + struct cgraph_edge *cs;
> basic_block bb = gimple_bb (stmt);
> + int freq;
>
> info->params[formal_id].called = 1;
>
> - note = XCNEW (struct ipa_param_call_note);
> - note->formal_id = formal_id;
> - note->stmt = stmt;
> - note->lto_stmt_uid = gimple_uid (stmt);
> - note->count = bb->count;
> - note->frequency = compute_call_stmt_bb_frequency (current_function_decl, bb);
> - note->loop_nest = bb->loop_depth;
> -
> - note->next = info->param_calls;
> - info->param_calls = note;
> -
> - return;
> + freq = compute_call_stmt_bb_frequency (current_function_decl, bb);
> + cs = cgraph_create_indirect_edge (node, stmt, bb->count, freq,
> + bb->loop_depth);
> + cs->indirect_info->param_index = formal_id;
> }
>
> -/* Analyze the CALL and examine uses of formal parameters of the caller
> +/* Analyze the CALL and examine uses of formal parameters of the caller NODE
> (described by INFO). Currently it checks whether the call calls a pointer
> that is a formal parameter and if so, the parameter is marked with the
> - called flag and a note describing the call is created. This is very simple
> - for ordinary pointers represented in SSA but not-so-nice when it comes to
> - member pointers. The ugly part of this function does nothing more than
> - tries to match the pattern of such a call. An example of such a pattern is
> - the gimple dump below, the call is on the last line:
> + called flag and a an indirect call graph edge describing the call is
> + created. This is very simple for ordinary pointers represented in SSA but
> + not-so-nice when it comes to member pointers. The ugly part of this
> + function does nothing more than tries to match the pattern of such a call.
> + An example of such a pattern is the gimple dump below, the call is on the
> + last line:
>
> <bb 2>:
> f$__delta_5 = f.__delta;
> @@ -809,7 +804,8 @@ ipa_note_param_call (struct ipa_node_par
> */
>
> static void
> -ipa_analyze_call_uses (struct ipa_node_params *info, gimple call)
> +ipa_analyze_call_uses (struct cgraph_node *node, struct ipa_node_params *info,
> + gimple call)
> {
> tree target = gimple_call_fn (call);
> gimple def;
> @@ -830,7 +826,7 @@ ipa_analyze_call_uses (struct ipa_node_p
> /* assuming TREE_CODE (var) == PARM_DECL */
> index = ipa_get_param_decl_index (info, var);
> if (index >= 0)
> - ipa_note_param_call (info, index, call);
> + ipa_note_param_call (node, info, index, call);
> return;
> }
>
> @@ -927,20 +923,21 @@ ipa_analyze_call_uses (struct ipa_node_p
>
> index = ipa_get_param_decl_index (info, rec);
> if (index >= 0 && !ipa_is_param_modified (info, index))
> - ipa_note_param_call (info, index, call);
> + ipa_note_param_call (node, info, index, call);
>
> return;
> }
>
> -/* Analyze the statement STMT with respect to formal parameters (described in
> - INFO) and their uses. Currently it only checks whether formal parameters
> - are called. */
> +/* Analyze the call statement STMT with respect to formal parameters (described
> + in INFO) of caller given by NODE. Currently it only checks whether formal
> + parameters are called. */
>
> static void
> -ipa_analyze_stmt_uses (struct ipa_node_params *info, gimple stmt)
> +ipa_analyze_stmt_uses (struct cgraph_node *node, struct ipa_node_params *info,
> + gimple stmt)
> {
> if (is_gimple_call (stmt))
> - ipa_analyze_call_uses (info, stmt);
> + ipa_analyze_call_uses (node, info, stmt);
> }
>
> /* Scan the function body of NODE and inspect the uses of formal parameters.
> @@ -965,7 +962,7 @@ ipa_analyze_params_uses (struct cgraph_n
> for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> {
> gimple stmt = gsi_stmt (gsi);
> - ipa_analyze_stmt_uses (info, stmt);
> + ipa_analyze_stmt_uses (node, info, stmt);
> }
> }
>
> @@ -1021,9 +1018,8 @@ update_jump_functions_after_inlining (st
> by JFUNC. NODE is the node where the call is. */
>
> static void
> -print_edge_addition_message (FILE *f, struct ipa_param_call_note *nt,
> - struct ipa_jump_func *jfunc,
> - struct cgraph_node *node)
> +print_edge_addition_message (FILE *f, struct cgraph_edge *e,
> + struct ipa_jump_func *jfunc)
> {
> fprintf (f, "ipa-prop: Discovered an indirect call to a known target (");
> if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
> @@ -1034,8 +1030,8 @@ print_edge_addition_message (FILE *f, st
> else
> print_node_brief(f, "", jfunc->value.constant, 0);
>
> - fprintf (f, ") in %s: ", cgraph_node_name (node));
> - print_gimple_stmt (f, nt->stmt, 2, TDF_SLIM);
> + fprintf (f, ") in %s: ", cgraph_node_name (e->caller));
> + print_gimple_stmt (f, e->call_stmt, 2, TDF_SLIM);
> }
>
> /* Update the param called notes associated with NODE when CS is being inlined,
> @@ -1049,37 +1045,43 @@ update_call_notes_after_inlining (struct
> struct cgraph_node *node,
> VEC (cgraph_edge_p, heap) **new_edges)
> {
> - struct ipa_node_params *info = IPA_NODE_REF (node);
> struct ipa_edge_args *top = IPA_EDGE_REF (cs);
> - struct ipa_param_call_note *nt;
> + struct cgraph_edge *ie, *next_ie;
> bool res = false;
>
> - for (nt = info->param_calls; nt; nt = nt->next)
> + ipa_check_create_edge_args ();
> +
> + for (ie = node->indirect_calls; ie; ie = next_ie)
> {
> + struct cgraph_indirect_call_info *ici = ie->indirect_info;
> struct ipa_jump_func *jfunc;
>
> - if (nt->processed)
> + next_ie = ie->next_callee;
> + if (ici->inlining_processed)
> continue;
>
> + /* If we ever use indirect edges for anything other than indirect
> + inlining, we will need to skip those with negative param_indices. */
> + gcc_assert (ici->param_index >= 0);
> +
> /* We must check range due to calls with variable number of arguments: */
> - if (nt->formal_id >= ipa_get_cs_argument_count (top))
> + if (ici->param_index >= ipa_get_cs_argument_count (top))
> {
> - nt->processed = true;
> + ici->inlining_processed = true;
> continue;
> }
>
> - jfunc = ipa_get_ith_jump_func (top, nt->formal_id);
> + jfunc = ipa_get_ith_jump_func (top, ici->param_index);
> if (jfunc->type == IPA_JF_PASS_THROUGH
> && jfunc->value.pass_through.operation == NOP_EXPR)
> - nt->formal_id = jfunc->value.pass_through.formal_id;
> + ici->param_index = jfunc->value.pass_through.formal_id;
> else if (jfunc->type == IPA_JF_CONST
> || jfunc->type == IPA_JF_CONST_MEMBER_PTR)
> {
> struct cgraph_node *callee;
> - struct cgraph_edge *new_indirect_edge;
> tree decl;
>
> - nt->processed = true;
> + ici->inlining_processed = true;
> if (jfunc->type == IPA_JF_CONST_MEMBER_PTR)
> decl = jfunc->value.member_cst.pfn;
> else
> @@ -1097,16 +1099,12 @@ update_call_notes_after_inlining (struct
>
> res = true;
> if (dump_file)
> - print_edge_addition_message (dump_file, nt, jfunc, node);
> + print_edge_addition_message (dump_file, ie, jfunc);
>
> - new_indirect_edge = cgraph_create_edge (node, callee, nt->stmt,
> - nt->count, nt->frequency,
> - nt->loop_nest);
> - new_indirect_edge->lto_stmt_uid = nt->lto_stmt_uid;
> - new_indirect_edge->indirect_call = 1;
> - ipa_check_create_edge_args ();
> + cgraph_make_edge_direct (ie, callee);
> + ie->indirect_inlining_edge = 1;
> if (new_edges)
> - VEC_safe_push (cgraph_edge_p, heap, *new_edges, new_indirect_edge);
> + VEC_safe_push (cgraph_edge_p, heap, *new_edges, ie);
> top = IPA_EDGE_REF (cs);
> }
> else
> @@ -1114,9 +1112,10 @@ update_call_notes_after_inlining (struct
> /* Ancestor jum functions and pass theoughs with operations should
> not be used on parameters that then get called. */
> gcc_assert (jfunc->type == IPA_JF_UNKNOWN);
> - nt->processed = true;
> + ici->inlining_processed = true;
> }
> }
> +
> return res;
> }
>
> @@ -1208,13 +1207,6 @@ ipa_free_node_params_substructures (stru
> if (info->params)
> free (info->params);
>
> - while (info->param_calls)
> - {
> - struct ipa_param_call_note *note = info->param_calls;
> - info->param_calls = note->next;
> - free (note);
> - }
> -
> memset (info, 0, sizeof (*info));
> }
>
> @@ -1314,7 +1306,6 @@ ipa_node_duplication_hook (struct cgraph
> __attribute__((unused)) void *data)
> {
> struct ipa_node_params *old_info, *new_info;
> - struct ipa_param_call_note *note;
> int param_count;
>
> ipa_check_create_node_params ();
> @@ -1328,17 +1319,6 @@ ipa_node_duplication_hook (struct cgraph
> sizeof (struct ipa_param_descriptor) * param_count);
> new_info->ipcp_orig_node = old_info->ipcp_orig_node;
> new_info->count_scale = old_info->count_scale;
> -
> - for (note = old_info->param_calls; note; note = note->next)
> - {
> - struct ipa_param_call_note *nn;
> -
> - nn = (struct ipa_param_call_note *)
> - xcalloc (1, sizeof (struct ipa_param_call_note));
> - memcpy (nn, note, sizeof (struct ipa_param_call_note));
> - nn->next = new_info->param_calls;
> - new_info->param_calls = nn;
> - }
> }
>
> /* Register our cgraph hooks if they are not already there. */
> @@ -1964,40 +1944,40 @@ ipa_read_jump_function (struct lto_input
> }
> }
>
> -/* Stream out a parameter call note. */
> +/* Stream out parts of cgraph_indirect_call_info corresponding to CS that are
> + relevant to indirect inlining to OB. */
>
> static void
> -ipa_write_param_call_note (struct output_block *ob,
> - struct ipa_param_call_note *note)
> +ipa_write_indirect_edge_info (struct output_block *ob,
> + struct cgraph_edge *cs)
> {
> - gcc_assert (!note->processed);
> - lto_output_uleb128_stream (ob->main_stream, gimple_uid (note->stmt));
> - lto_output_sleb128_stream (ob->main_stream, note->formal_id);
> - lto_output_sleb128_stream (ob->main_stream, note->count);
> - lto_output_sleb128_stream (ob->main_stream, note->frequency);
> - lto_output_sleb128_stream (ob->main_stream, note->loop_nest);
> + struct cgraph_indirect_call_info *ii = cs->indirect_info;
> + struct bitpack_d *bp;
> +
> + lto_output_sleb128_stream (ob->main_stream, ii->param_index);
> + bp = bitpack_create ();
> + bp_pack_value (bp, ii->inlining_processed, 1);
> + lto_output_bitpack (ob->main_stream, bp);
> + bitpack_delete (bp);
> }
>
> -/* Read in a parameter call note. */
> +/* Read in parts of cgraph_indirect_call_info corresponding to CS that are
> + relevant to indirect inlining from IB. */
>
> static void
> -ipa_read_param_call_note (struct lto_input_block *ib,
> - struct ipa_node_params *info)
> -
> +ipa_read_indirect_edge_info (struct lto_input_block *ib,
> + struct data_in *data_in ATTRIBUTE_UNUSED,
> + struct cgraph_edge *cs)
> {
> - struct ipa_param_call_note *note = XCNEW (struct ipa_param_call_note);
> -
> - note->lto_stmt_uid = (unsigned int) lto_input_uleb128 (ib);
> - note->formal_id = (int) lto_input_sleb128 (ib);
> - note->count = (gcov_type) lto_input_sleb128 (ib);
> - note->frequency = (int) lto_input_sleb128 (ib);
> - note->loop_nest = (int) lto_input_sleb128 (ib);
> + struct cgraph_indirect_call_info *ii = cs->indirect_info;
> + struct bitpack_d *bp;
>
> - note->next = info->param_calls;
> - info->param_calls = note;
> + ii->param_index = (int) lto_input_sleb128 (ib);
> + bp = lto_input_bitpack (ib);
> + ii->inlining_processed = bp_unpack_value (bp, 1);
> + bitpack_delete (bp);
> }
>
> -
> /* Stream out NODE info to OB. */
>
> static void
> @@ -2009,8 +1989,6 @@ ipa_write_node_info (struct output_block
> int j;
> struct cgraph_edge *e;
> struct bitpack_d *bp;
> - int note_count = 0;
> - struct ipa_param_call_note *note;
>
> encoder = ob->decl_state->cgraph_node_encoder;
> node_ref = lto_cgraph_encoder_encode (encoder, node);
> @@ -2024,10 +2002,7 @@ ipa_write_node_info (struct output_block
> gcc_assert (!info->node_enqueued);
> gcc_assert (!info->ipcp_orig_node);
> for (j = 0; j < ipa_get_param_count (info); j++)
> - {
> - bp_pack_value (bp, info->params[j].modified, 1);
> - bp_pack_value (bp, info->params[j].called, 1);
> - }
> + bp_pack_value (bp, info->params[j].modified, 1);
> lto_output_bitpack (ob->main_stream, bp);
> bitpack_delete (bp);
> for (e = node->callees; e; e = e->next_callee)
> @@ -2039,12 +2014,8 @@ ipa_write_node_info (struct output_block
> for (j = 0; j < ipa_get_cs_argument_count (args); j++)
> ipa_write_jump_function (ob, ipa_get_ith_jump_func (args, j));
> }
> -
> - for (note = info->param_calls; note; note = note->next)
> - note_count++;
> - lto_output_uleb128_stream (ob->main_stream, note_count);
> - for (note = info->param_calls; note; note = note->next)
> - ipa_write_param_call_note (ob, note);
> + for (e = node->indirect_calls; e; e = e->next_callee)
> + ipa_write_indirect_edge_info (ob, e);
> }
>
> /* Srtream in NODE info from IB. */
> @@ -2057,7 +2028,6 @@ ipa_read_node_info (struct lto_input_blo
> int k;
> struct cgraph_edge *e;
> struct bitpack_d *bp;
> - int i, note_count;
>
> ipa_initialize_node_params (node);
>
> @@ -2071,10 +2041,7 @@ ipa_read_node_info (struct lto_input_blo
> }
> info->node_enqueued = false;
> for (k = 0; k < ipa_get_param_count (info); k++)
> - {
> - info->params[k].modified = bp_unpack_value (bp, 1);
> - info->params[k].called = bp_unpack_value (bp, 1);
> - }
> + info->params[k].modified = bp_unpack_value (bp, 1);
> bitpack_delete (bp);
> for (e = node->callees; e; e = e->next_callee)
> {
> @@ -2090,10 +2057,8 @@ ipa_read_node_info (struct lto_input_blo
> for (k = 0; k < ipa_get_cs_argument_count (args); k++)
> ipa_read_jump_function (ib, ipa_get_ith_jump_func (args, k), data_in);
> }
> -
> - note_count = lto_input_uleb128 (ib);
> - for (i = 0; i < note_count; i++)
> - ipa_read_param_call_note (ib, info);
> + for (e = node->indirect_calls; e; e = e->next_callee)
> + ipa_read_indirect_edge_info (ib, data_in, e);
> }
>
> /* Write jump functions for nodes in SET. */
> @@ -2218,29 +2183,3 @@ ipa_update_after_lto_read (void)
> }
> }
> }
> -
> -/* Walk param call notes of NODE and set their call statements given the uid
> - stored in each note and STMTS which is an array of statements indexed by the
> - uid. */
> -
> -void
> -lto_ipa_fixup_call_notes (struct cgraph_node *node, gimple *stmts)
> -{
> - struct ipa_node_params *info;
> - struct ipa_param_call_note *note;
> -
> - ipa_check_create_node_params ();
> - info = IPA_NODE_REF (node);
> - note = info->param_calls;
> - /* If there are no notes or they have already been fixed up (the same fixup
> - is called for both inlining and ipa-cp), there's nothing to do. */
> - if (!note || note->stmt)
> - return;
> -
> - do
> - {
> - note->stmt = stmts[note->lto_stmt_uid];
> - note = note->next;
> - }
> - while (note);
> -}
> Index: icln/gcc/ipa-cp.c
> ===================================================================
> --- icln.orig/gcc/ipa-cp.c
> +++ icln/gcc/ipa-cp.c
> @@ -1332,7 +1332,7 @@ struct ipa_opt_pass_d pass_ipa_cp =
> ipcp_write_summary, /* write_summary */
> ipcp_read_summary, /* read_summary */
> NULL, /* function_read_summary */
> - lto_ipa_fixup_call_notes, /* stmt_fixup */
> + NULL, /* stmt_fixup */
> 0, /* TODOs */
> NULL, /* function_transform */
> NULL, /* variable_transform */
> Index: icln/gcc/ipa-inline.c
> ===================================================================
> --- icln.orig/gcc/ipa-inline.c
> +++ icln/gcc/ipa-inline.c
> @@ -2066,7 +2066,7 @@ struct ipa_opt_pass_d pass_ipa_inline =
> inline_write_summary, /* write_summary */
> inline_read_summary, /* read_summary */
> NULL, /* function_read_summary */
> - lto_ipa_fixup_call_notes, /* stmt_fixup */
> + NULL, /* stmt_fixup */
> 0, /* TODOs */
> inline_transform, /* function_transform */
> NULL, /* variable_transform */
> Index: icln/gcc/cgraphunit.c
> ===================================================================
> --- icln.orig/gcc/cgraphunit.c
> +++ icln/gcc/cgraphunit.c
> @@ -607,6 +607,24 @@ verify_cgraph_node (struct cgraph_node *
> error ("Inline clone is needed");
> error_found = true;
> }
> + for (e = node->indirect_calls; e; e = e->next_callee)
> + {
> + if (e->aux)
> + {
> + error ("aux field set for indirect edge from %s",
> + identifier_to_locale (cgraph_node_name (e->caller)));
> + error_found = true;
> + }
> + if (!e->indirect_unknown_callee
> + || !e->indirect_info)
> + {
> + error ("An indirect edge from %s is not marked as indirect or has "
> + "associated indirect_info, the corresponding statement is: ",
> + identifier_to_locale (cgraph_node_name (e->caller)));
> + debug_gimple_stmt (e->call_stmt);
> + error_found = true;
> + }
> + }
> for (e = node->callers; e; e = e->next_caller)
> {
> if (e->count < 0)
> @@ -733,10 +751,10 @@ verify_cgraph_node (struct cgraph_node *
> gsi_next (&gsi))
> {
> gimple stmt = gsi_stmt (gsi);
> - tree decl;
> - if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
> + if (is_gimple_call (stmt))
> {
> struct cgraph_edge *e = cgraph_edge (node, stmt);
> + tree decl = gimple_call_fndecl (stmt);
> if (e)
> {
> if (e->aux)
> @@ -745,25 +763,38 @@ verify_cgraph_node (struct cgraph_node *
> debug_gimple_stmt (stmt);
> error_found = true;
> }
> - if (e->callee->same_body_alias)
> + if (!e->indirect_unknown_callee)
> {
> - error ("edge points to same body alias:");
> - debug_tree (e->callee->decl);
> - error_found = true;
> + if (e->callee->same_body_alias)
> + {
> + error ("edge points to same body alias:");
> + debug_tree (e->callee->decl);
> + error_found = true;
> + }
> + else if (!node->global.inlined_to
> + && !e->callee->global.inlined_to
> + && decl
> + && !clone_of_p (cgraph_node (decl),
> + e->callee))
> + {
> + error ("edge points to wrong declaration:");
> + debug_tree (e->callee->decl);
> + fprintf (stderr," Instead of:");
> + debug_tree (decl);
> + error_found = true;
> + }
> }
> - else if (!node->global.inlined_to
> - && !e->callee->global.inlined_to
> - && !clone_of_p (cgraph_node (decl), e->callee))
> + else if (decl)
> {
> - error ("edge points to wrong declaration:");
> - debug_tree (e->callee->decl);
> - fprintf (stderr," Instead of:");
> - debug_tree (decl);
> + error ("an indirect edge with unknown callee "
> + "corresponding to a call_stmt with "
> + "a known declaration:");
> error_found = true;
> + debug_gimple_stmt (e->call_stmt);
> }
> e->aux = (void *)1;
> }
> - else
> + else if (decl)
> {
> error ("missing callgraph edge for call stmt:");
> debug_gimple_stmt (stmt);
> @@ -779,7 +810,7 @@ verify_cgraph_node (struct cgraph_node *
>
> for (e = node->callees; e; e = e->next_callee)
> {
> - if (!e->aux && !e->indirect_call)
> + if (!e->aux)
> {
> error ("edge %s->%s has no corresponding call_stmt",
> identifier_to_locale (cgraph_node_name (e->caller)),
> @@ -787,6 +818,17 @@ verify_cgraph_node (struct cgraph_node *
> debug_gimple_stmt (e->call_stmt);
> error_found = true;
> }
> + e->aux = 0;
> + }
> + for (e = node->indirect_calls; e; e = e->next_callee)
> + {
> + if (!e->aux)
> + {
> + error ("an indirect edge from %s has no corresponding call_stmt",
> + identifier_to_locale (cgraph_node_name (e->caller)));
> + debug_gimple_stmt (e->call_stmt);
> + error_found = true;
> + }
> e->aux = 0;
> }
> }
> Index: icln/gcc/cif-code.def
> ===================================================================
> --- icln.orig/gcc/cif-code.def
> +++ icln/gcc/cif-code.def
> @@ -84,3 +84,7 @@ DEFCIFCODE(MISMATCHED_ARGUMENTS, N_("mis
> /* Call was originally indirect. */
> DEFCIFCODE(ORIGINALLY_INDIRECT_CALL,
> N_("originally indirect function call not considered for inlining"))
> +
> +/* Ths edge represents an indirect edge with a yet-undetermined callee . */
> +DEFCIFCODE(INDIRECT_UNKNOWN_CALL,
> + N_("indirect function call with a yet undetermined callee"))
> Index: icln/gcc/tree-inline.c
> ===================================================================
> --- icln.orig/gcc/tree-inline.c
> +++ icln/gcc/tree-inline.c
> @@ -1674,9 +1674,8 @@ copy_bb (copy_body_data *id, basic_block
> /* Constant propagation on argument done during inlining
> may create new direct call. Produce an edge for it. */
> if ((!edge
> - || (edge->indirect_call
> + || (edge->indirect_inlining_edge
> && id->transform_call_graph_edges == CB_CGE_MOVE_CLONES))
> - && is_gimple_call (stmt)
> && (fn = gimple_call_fndecl (stmt)) != NULL)
> {
> struct cgraph_node *dest = cgraph_node (fn);
> @@ -3452,7 +3451,7 @@ get_indirect_callee_fndecl (struct cgrap
> struct cgraph_edge *cs;
>
> cs = cgraph_edge (node, stmt);
> - if (cs)
> + if (cs && !cs->indirect_unknown_callee)
> return cs->callee->decl;
>
> return NULL_TREE;
> @@ -3535,7 +3534,7 @@ expand_call_inline (basic_block bb, gimp
> /* If this call was originally indirect, we do not want to emit any
> inlining related warnings or sorry messages because there are no
> guarantees regarding those. */
> - if (cg_edge->indirect_call)
> + if (cg_edge->indirect_inlining_edge)
> goto egress;
>
> if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn))
> Index: icln/gcc/lto-cgraph.c
> ===================================================================
> --- icln.orig/gcc/lto-cgraph.c
> +++ icln/gcc/lto-cgraph.c
> @@ -139,15 +139,21 @@ lto_output_edge (struct lto_simple_outpu
> intptr_t ref;
> struct bitpack_d *bp;
>
> - lto_output_uleb128_stream (ob->main_stream, LTO_cgraph_edge);
> + if (edge->indirect_unknown_callee)
> + lto_output_uleb128_stream (ob->main_stream, LTO_cgraph_indirect_edge);
> + else
> + lto_output_uleb128_stream (ob->main_stream, LTO_cgraph_edge);
>
> ref = lto_cgraph_encoder_lookup (encoder, edge->caller);
> gcc_assert (ref != LCC_NOT_FOUND);
> lto_output_sleb128_stream (ob->main_stream, ref);
>
> - ref = lto_cgraph_encoder_lookup (encoder, edge->callee);
> - gcc_assert (ref != LCC_NOT_FOUND);
> - lto_output_sleb128_stream (ob->main_stream, ref);
> + if (!edge->indirect_unknown_callee)
> + {
> + ref = lto_cgraph_encoder_lookup (encoder, edge->callee);
> + gcc_assert (ref != LCC_NOT_FOUND);
> + lto_output_sleb128_stream (ob->main_stream, ref);
> + }
>
> lto_output_sleb128_stream (ob->main_stream, edge->count);
>
> @@ -157,7 +163,7 @@ lto_output_edge (struct lto_simple_outpu
> bp_pack_value (bp, edge->inline_failed, HOST_BITS_PER_INT);
> bp_pack_value (bp, edge->frequency, HOST_BITS_PER_INT);
> bp_pack_value (bp, edge->loop_nest, 30);
> - bp_pack_value (bp, edge->indirect_call, 1);
> + bp_pack_value (bp, edge->indirect_inlining_edge, 1);
> bp_pack_value (bp, edge->call_stmt_cannot_inline_p, 1);
> bp_pack_value (bp, edge->can_throw_external, 1);
> lto_output_bitpack (ob->main_stream, bp);
> @@ -371,6 +377,24 @@ output_profile_summary (struct lto_simpl
> lto_output_uleb128_stream (ob->main_stream, 0);
> }
>
> +/* Output all callees or indirect outgoing edges. EDGE must be the first such
> + edge. */
> +
> +static void
> +output_outgoing_cgraph_edges (struct cgraph_edge *edge,
> + struct lto_simple_output_block *ob,
> + lto_cgraph_encoder_t encoder)
> +{
> + if (!edge)
> + return;
> +
> + /* Output edges in backward direction, so the reconstructed callgraph match
> + and it is easy to associate call sites in the IPA pass summaries. */
> + while (edge->next_callee)
> + edge = edge->next_callee;
> + for (; edge; edge = edge->prev_callee)
> + lto_output_edge (ob, edge, encoder);
> +}
>
> /* Output the part of the cgraph in SET. */
>
> @@ -460,16 +484,8 @@ output_cgraph (cgraph_node_set set)
> for (csi = csi_start (set); !csi_end_p (csi); csi_next (&csi))
> {
> node = csi_node (csi);
> - if (node->callees)
> - {
> - /* Output edges in backward direction, so the reconstructed callgraph
> - match and it is easy to associate call sites in the IPA pass summaries. */
> - edge = node->callees;
> - while (edge->next_callee)
> - edge = edge->next_callee;
> - for (; edge; edge = edge->prev_callee)
> - lto_output_edge (ob, edge, encoder);
> - }
> + output_outgoing_cgraph_edges (node->callees, ob, encoder);
> + output_outgoing_cgraph_edges (node->indirect_calls, ob, encoder);
> }
>
> lto_output_uleb128_stream (ob->main_stream, 0);
> @@ -657,11 +673,14 @@ input_node (struct lto_file_decl_data *f
> }
>
>
> -/* Read an edge from IB. NODES points to a vector of previously read
> - nodes for decoding caller and callee of the edge to be read. */
> +/* Read an edge from IB. NODES points to a vector of previously read nodes for
> + decoding caller and callee of the edge to be read. If INDIRECT is true, the
> + edge being read is indirect (in the sense that it has
> + indirect_unknown_callee set). */
>
> static void
> -input_edge (struct lto_input_block *ib, VEC(cgraph_node_ptr, heap) *nodes)
> +input_edge (struct lto_input_block *ib, VEC(cgraph_node_ptr, heap) *nodes,
> + bool indirect)
> {
> struct cgraph_node *caller, *callee;
> struct cgraph_edge *edge;
> @@ -677,9 +696,14 @@ input_edge (struct lto_input_block *ib,
> if (caller == NULL || caller->decl == NULL_TREE)
> internal_error ("bytecode stream: no caller found while reading edge");
>
> - callee = VEC_index (cgraph_node_ptr, nodes, lto_input_sleb128 (ib));
> - if (callee == NULL || callee->decl == NULL_TREE)
> - internal_error ("bytecode stream: no callee found while reading edge");
> + if (!indirect)
> + {
> + callee = VEC_index (cgraph_node_ptr, nodes, lto_input_sleb128 (ib));
> + if (callee == NULL || callee->decl == NULL_TREE)
> + internal_error ("bytecode stream: no callee found while reading edge");
> + }
> + else
> + callee = NULL;
>
> count = (gcov_type) lto_input_sleb128 (ib);
>
> @@ -697,10 +721,14 @@ input_edge (struct lto_input_block *ib,
> || caller_resolution == LDPR_PREEMPTED_IR)
> return;
>
> - edge = cgraph_create_edge (caller, callee, NULL, count, freq, nest);
> + if (indirect)
> + edge = cgraph_create_indirect_edge (caller, NULL, count, freq, nest);
> + else
> + edge = cgraph_create_edge (caller, callee, NULL, count, freq, nest);
> +
> + edge->indirect_inlining_edge = bp_unpack_value (bp, 1);
> edge->lto_stmt_uid = stmt_id;
> edge->inline_failed = inline_failed;
> - edge->indirect_call = bp_unpack_value (bp, 1);
> edge->call_stmt_cannot_inline_p = bp_unpack_value (bp, 1);
> edge->can_throw_external = bp_unpack_value (bp, 1);
> bitpack_delete (bp);
> @@ -723,7 +751,9 @@ input_cgraph_1 (struct lto_file_decl_dat
> while (tag)
> {
> if (tag == LTO_cgraph_edge)
> - input_edge (ib, nodes);
> + input_edge (ib, nodes, false);
> + else if (tag == LTO_cgraph_indirect_edge)
> + input_edge (ib, nodes, true);
> else
> {
> node = input_node (file_data, ib, tag);
> Index: icln/gcc/lto-streamer-in.c
> ===================================================================
> --- icln.orig/gcc/lto-streamer-in.c
> +++ icln/gcc/lto-streamer-in.c
> @@ -1220,6 +1220,8 @@ fixup_call_stmt_edges_1 (struct cgraph_n
> struct cgraph_edge *cedge;
> for (cedge = node->callees; cedge; cedge = cedge->next_callee)
> cedge->call_stmt = stmts[cedge->lto_stmt_uid];
> + for (cedge = node->indirect_calls; cedge; cedge = cedge->next_callee)
> + cedge->call_stmt = stmts[cedge->lto_stmt_uid];
> }
>
> /* Fixup call_stmt pointers in NODE and all clones. */
> Index: icln/gcc/testsuite/gcc.dg/lto/20091209-1_0.c
> ===================================================================
> --- /dev/null
> +++ icln/gcc/testsuite/gcc.dg/lto/20091209-1_0.c
> @@ -0,0 +1,23 @@
> +/* Stream an indirect edge in and out. */
> +
> +/* { dg-lto-do link } */
> +/* { dg-lto-options {{ -O3 -fno-early-inlining -flto }} } */
> +
> +volatile int something;
> +
> +static void hooray ()
> +{
> + something = 1;
> +}
> +
> +static void hiphip (void (*f)())
> +{
> + something = 2;
> + f ();
> +}
> +
> +int main (int argc, int *argv[])
> +{
> + hiphip (hooray);
> + return 0;
> +}
>
>
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 2/6] Indirect call graph edges
2010-02-13 18:17 ` Richard Guenther
@ 2010-02-13 18:25 ` Richard Guenther
2010-03-05 17:06 ` Martin Jambor
0 siblings, 1 reply; 23+ messages in thread
From: Richard Guenther @ 2010-02-13 18:25 UTC (permalink / raw)
To: Martin Jambor; +Cc: GCC Patches, Jan Hubicka
On Sat, Feb 13, 2010 at 7:16 PM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Sat, Feb 13, 2010 at 7:01 PM, Martin Jambor <mjambor@suse.cz> wrote:
>> Hi,
>>
>> this is a re-post of the same patch I already sent here in January.
>> There are only minor differences. I have renamed the flag
>> indirect_call to indirect_inlining_edge and changed its purpose to be
>> exactly that, an edge made direct by indirect inlining (it may go away
>> completely, I currently use it only for asserts in ipa-cp
>> devirtualization) and I have added a few things to cgraph node
>> dumping. Most importantly, I have re-worked streaming so that
>> information for indirect inlining associated with nodes is written to
>> the jump functions section again in order to allow the cgraph stream
>> to remain simple and concise (which means it cannot store trees).
>>
>> The patch adds a new kind of edge to the call graph to represent
>> indirect calls with unknown callees (which we hope we can determine at
>> some stage) and uses them to replace ipa_param_call_notes in
>> ipa-prop.h. My immediate reason to do this is to move all the
>> information there from the notes because I will need them to be in
>> memory managed by the garbage collector (and did not want
>> ipa_node_params to become garbage collected) but in a broader sense
>> this is the right thing to do because it facilitates a more general
>> approach to keep information about such calls (ipa-cp jump functions
>> and the like) that is also consistent with how we do this for direct
>> edges.
>>
>> The data structure layout (a flag and a pointer in struct cgraph_edge
>> to a another special structure) was really chosen by Honza. The
>> subsequent patches add some more stuff to cgraph_indirect_call_info so
>> it won't look this silly for long.
>>
>> I have successfully bootstrapped and tested this beast on x86_84-linux
>> and would like to commit something along these lines when stage1 opens
>> again. Obviously, I welcome any comments.
>
> The cgraph.c file at the top currently contains very brief documentation
> which needs to be updated as it says:
>
> The callgraph at the moment does not represent indirect calls or calls
> from other compilation unit.
>
> Note that I think we should have some more elaborate overall overview
> about the cgraph interface.
Btw, I wonder what the callee node of an indirect edge points to? Should
we have a way to put a cgraph node set there? In IPA mod/ref analysis
it would be useful to know which functions can be reached via an
indirect call - the conservative set should be all functions that had their
address taken (but I believe we lie here for virtual functions).
Pointer analysis could also restrict the callee set like for
void (*p)(void);
if (b)
p = foo;
else
p = bar;
(*p)();
where we know we either call foo or bar. Is there a suitable place to
note this kind of information?
Thanks,
Richard.
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 1/6] Clarify edge redirection for inline clones
2010-02-13 18:03 ` [PATCH 1/6] Clarify edge redirection for inline clones Martin Jambor
@ 2010-02-22 14:23 ` Jan Hubicka
0 siblings, 0 replies; 23+ messages in thread
From: Jan Hubicka @ 2010-02-22 14:23 UTC (permalink / raw)
To: Martin Jambor; +Cc: GCC Patches, Jan Hubicka
>
> 2010-02-12 Martin Jambor <mjambor@suse.cz>
>
> * cgraph.h (cgraph_redirect_edge_call_stmt_to_callee): Declare.
> * cgraphunit.c (cgraph_materialize_all_clones): Moved call
> redirection...
> (cgraph_redirect_edge_call_stmt_to_callee): ...to this new
> function.
> (verify_cgraph_node): Do not check for edges pointing to wrong
> nodes in inline clones.
> * tree-inline.c (copy_bb): Call
> cgraph_redirect_edge_call_stmt_to_callee.
As we discussed earlier, it would make most sense to redirect calls just before inlining
visits them, but this should work on mainline well. So the patch is OK for pretty-ipa and
if you can find a testcase producing ICE at mainline, then for mainlie too.
Honza
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 4/6] Remove unused ipa_note_param_call.called flag (approved)
2010-02-13 18:04 ` [PATCH 4/6] Remove unused ipa_note_param_call.called flag (approved) Martin Jambor
2010-02-13 18:14 ` Richard Guenther
@ 2010-02-22 15:04 ` Jan Hubicka
1 sibling, 0 replies; 23+ messages in thread
From: Jan Hubicka @ 2010-02-22 15:04 UTC (permalink / raw)
To: Martin Jambor; +Cc: GCC Patches, Jan Hubicka
> 2009-12-28 Martin Jambor <mjambor@suse.cz>
>
> * ipa-prop.h (struct ipa_param_descriptor): Removed the called field.
> (ipa_is_param_called): Removed.
> * ipa-prop.c (ipa_note_param_call): Do not set the called flag.
> Removed parameter info.
> (ipa_print_node_params): Do not print the called flag.
OK for pretty-ipa
Honza
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 2/6] Indirect call graph edges
2010-02-13 18:04 ` [PATCH 2/6] Indirect call graph edges Martin Jambor
2010-02-13 18:17 ` Richard Guenther
@ 2010-02-22 15:52 ` Jan Hubicka
2010-02-22 16:05 ` Richard Guenther
1 sibling, 1 reply; 23+ messages in thread
From: Jan Hubicka @ 2010-02-22 15:52 UTC (permalink / raw)
To: Martin Jambor; +Cc: GCC Patches, Jan Hubicka
> 2010-02-10 Martin Jambor <mjambor@suse.cz>
>
> * cgraph.h (struct cgraph_node): New field indirect_calls.
> (struct cgraph_indirect_call_info): New type.
> (struct cgraph_edge): Removed field indirect_call. New fields
> indirect_info, indirect_inlining_edge and indirect_unknown_callee.
> (cgraph_create_indirect_edge): Declare.
> (cgraph_make_edge_direct): Likewise.
> (enum LTO_cgraph_tags): New item LTO_cgraph_indirect_edge.
> * ipa-prop.h (struct ipa_param_call_note): Removed.
> (struct ipa_node_params): Removed field param_calls.
> * cgraph.c (cgraph_add_edge_to_call_site_hash): New function.
> (cgraph_edge): Search also among the indirect edges, use
> cgraph_add_edge_to_call_site_hash to add edges to the call site hash.
> (cgraph_set_call_stmt): Possibly turn an indirect edge into a direct
> one, use cgraph_add_edge_to_call_site_hash to add edges to the call
> site hash.
> (initialize_inline_failed): Assign a reason to indirect edges.
> (cgraph_create_edge_1): New function.
> (cgraph_create_edge): Moved some functionality to
> cgraph_create_edge_1.
> (cgraph_create_indirect_edge): New function.
> (cgraph_edge_remove_callee): Add an assert checking for
> non-indirectness.
> (cgraph_edge_remove_caller): Special-case indirect edges.
> (cgraph_remove_edge): Likewise.
> (cgraph_set_edge_callee): New function.
> (cgraph_redirect_edge_callee): Use cgraph_set_edge_callee.
> (cgraph_make_edge_direct): New function.
> (cgraph_update_edges_for_call_stmt_node): Do nothing only when also
> the declaration of the call statement matches.
> (cgraph_node_remove_callees): Special-case indirect edges.
> (cgraph_clone_edge): Likewise.
> (cgraph_clone_node): Clone also the indirect edges.
> (dump_cgraph_node): Dump indirect_inlining_edge flag instead of
> indirect_call, dump count of indirect_calls edges.
> * ipa-prop.c (ipa_note_param_call): Create indirect edges instead of
> creating notes. New parameter node.
> (ipa_analyze_call_uses): New parameter node, pass it on to
> ipa_note_param_call.
> (ipa_analyze_stmt_uses): Likewise.
> (ipa_analyze_params_uses): Pass node to ipa_analyze_stmt_uses.
> (print_edge_addition_message): Work on edges rather than on notes.
> (update_call_notes_after_inlining): Likewise.
> (ipa_free_node_params_substructures): Do not free notes.
> (ipa_node_duplication_hook): Do not duplicate notes.
> (ipa_write_param_call_note): Removed.
> (ipa_read_param_call_note): Removed.
> (ipa_write_indirect_edge_info): New function.
> (ipa_read_indirect_edge_info): Likewise.
> (ipa_write_node_info): Do not stream notes, do stream information
> in indirect edges.
> (ipa_read_node_info): Likewise.
> (lto_ipa_fixup_call_notes): Removed.
> * ipa-cp.c (pass_ipa_cp): Set stmt_fixup to NULL.
> * ipa-inline.c (pass_ipa_inline): Likewise.
> * cgraphunit.c (verify_cgraph_node): Check also indirect edges.
> * cif-code.def (INDIRECT_UNKNOWN_CALL): New reason.
> * tree-inline.c (copy_bb): Removed an unnecessary double check for
> is_gimple_call.
> * tree-inline.c (get_indirect_callee_fndecl): Do not consider indirect
> edges.
> * lto-cgraph.c (output_outgoing_cgraph_edges): New function.
> (output_cgraph): Stream also indirect edges.
> (lto_output_edge): Added capability to stream indirect edges.
> (input_edge): Likewise.
> (input_cgraph_1): Likewise.
>
> * testsuite/gcc.dg/lto/20091209-1_0.c: New testcase.
OK (for pretty-ipa).
As Richard commented, we will need way of collecting list of indirect callers
for need of passes propagating data across callgraph. That can be done
incrementally. We need way to get list of possible destinations that should
be fed in by PTA.
Honza
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 2/6] Indirect call graph edges
2010-02-22 15:52 ` Jan Hubicka
@ 2010-02-22 16:05 ` Richard Guenther
2010-02-22 16:06 ` Jan Hubicka
0 siblings, 1 reply; 23+ messages in thread
From: Richard Guenther @ 2010-02-22 16:05 UTC (permalink / raw)
To: Jan Hubicka; +Cc: Martin Jambor, GCC Patches
On Mon, Feb 22, 2010 at 4:44 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> 2010-02-10 Martin Jambor <mjambor@suse.cz>
>>
>> * cgraph.h (struct cgraph_node): New field indirect_calls.
>> (struct cgraph_indirect_call_info): New type.
>> (struct cgraph_edge): Removed field indirect_call. New fields
>> indirect_info, indirect_inlining_edge and indirect_unknown_callee.
>> (cgraph_create_indirect_edge): Declare.
>> (cgraph_make_edge_direct): Likewise.
>> (enum LTO_cgraph_tags): New item LTO_cgraph_indirect_edge.
>> * ipa-prop.h (struct ipa_param_call_note): Removed.
>> (struct ipa_node_params): Removed field param_calls.
>> * cgraph.c (cgraph_add_edge_to_call_site_hash): New function.
>> (cgraph_edge): Search also among the indirect edges, use
>> cgraph_add_edge_to_call_site_hash to add edges to the call site hash.
>> (cgraph_set_call_stmt): Possibly turn an indirect edge into a direct
>> one, use cgraph_add_edge_to_call_site_hash to add edges to the call
>> site hash.
>> (initialize_inline_failed): Assign a reason to indirect edges.
>> (cgraph_create_edge_1): New function.
>> (cgraph_create_edge): Moved some functionality to
>> cgraph_create_edge_1.
>> (cgraph_create_indirect_edge): New function.
>> (cgraph_edge_remove_callee): Add an assert checking for
>> non-indirectness.
>> (cgraph_edge_remove_caller): Special-case indirect edges.
>> (cgraph_remove_edge): Likewise.
>> (cgraph_set_edge_callee): New function.
>> (cgraph_redirect_edge_callee): Use cgraph_set_edge_callee.
>> (cgraph_make_edge_direct): New function.
>> (cgraph_update_edges_for_call_stmt_node): Do nothing only when also
>> the declaration of the call statement matches.
>> (cgraph_node_remove_callees): Special-case indirect edges.
>> (cgraph_clone_edge): Likewise.
>> (cgraph_clone_node): Clone also the indirect edges.
>> (dump_cgraph_node): Dump indirect_inlining_edge flag instead of
>> indirect_call, dump count of indirect_calls edges.
>> * ipa-prop.c (ipa_note_param_call): Create indirect edges instead of
>> creating notes. New parameter node.
>> (ipa_analyze_call_uses): New parameter node, pass it on to
>> ipa_note_param_call.
>> (ipa_analyze_stmt_uses): Likewise.
>> (ipa_analyze_params_uses): Pass node to ipa_analyze_stmt_uses.
>> (print_edge_addition_message): Work on edges rather than on notes.
>> (update_call_notes_after_inlining): Likewise.
>> (ipa_free_node_params_substructures): Do not free notes.
>> (ipa_node_duplication_hook): Do not duplicate notes.
>> (ipa_write_param_call_note): Removed.
>> (ipa_read_param_call_note): Removed.
>> (ipa_write_indirect_edge_info): New function.
>> (ipa_read_indirect_edge_info): Likewise.
>> (ipa_write_node_info): Do not stream notes, do stream information
>> in indirect edges.
>> (ipa_read_node_info): Likewise.
>> (lto_ipa_fixup_call_notes): Removed.
>> * ipa-cp.c (pass_ipa_cp): Set stmt_fixup to NULL.
>> * ipa-inline.c (pass_ipa_inline): Likewise.
>> * cgraphunit.c (verify_cgraph_node): Check also indirect edges.
>> * cif-code.def (INDIRECT_UNKNOWN_CALL): New reason.
>> * tree-inline.c (copy_bb): Removed an unnecessary double check for
>> is_gimple_call.
>> * tree-inline.c (get_indirect_callee_fndecl): Do not consider indirect
>> edges.
>> * lto-cgraph.c (output_outgoing_cgraph_edges): New function.
>> (output_cgraph): Stream also indirect edges.
>> (lto_output_edge): Added capability to stream indirect edges.
>> (input_edge): Likewise.
>> (input_cgraph_1): Likewise.
>>
>> * testsuite/gcc.dg/lto/20091209-1_0.c: New testcase.
>
> OK (for pretty-ipa).
> As Richard commented, we will need way of collecting list of indirect callers
> for need of passes propagating data across callgraph. That can be done
> incrementally. We need way to get list of possible destinations that should
> be fed in by PTA.
Yeah. We currently throw away the points-to solution for function
pointer SSA names ...
Richard.
> Honza
>
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 2/6] Indirect call graph edges
2010-02-22 16:05 ` Richard Guenther
@ 2010-02-22 16:06 ` Jan Hubicka
0 siblings, 0 replies; 23+ messages in thread
From: Jan Hubicka @ 2010-02-22 16:06 UTC (permalink / raw)
To: Richard Guenther; +Cc: Jan Hubicka, Martin Jambor, GCC Patches
> On Mon, Feb 22, 2010 at 4:44 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> 2010-02-10  Martin Jambor  <mjambor@suse.cz>
> >>
> >> Â Â Â * cgraph.h (struct cgraph_node): New field indirect_calls.
> >> Â Â Â (struct cgraph_indirect_call_info): New type.
> >> Â Â Â (struct cgraph_edge): Removed field indirect_call. New fields
> >> Â Â Â indirect_info, indirect_inlining_edge and indirect_unknown_callee.
> >> Â Â Â (cgraph_create_indirect_edge): Declare.
> >> Â Â Â (cgraph_make_edge_direct): Likewise.
> >> Â Â Â (enum LTO_cgraph_tags): New item LTO_cgraph_indirect_edge.
> >> Â Â Â * ipa-prop.h (struct ipa_param_call_note): Removed.
> >> Â Â Â (struct ipa_node_params): Removed field param_calls.
> >> Â Â Â * cgraph.c (cgraph_add_edge_to_call_site_hash): New function..
> >> Â Â Â (cgraph_edge): Search also among the indirect edges, use
> >> Â Â Â cgraph_add_edge_to_call_site_hash to add edges to the call site hash.
> >> Â Â Â (cgraph_set_call_stmt): Possibly turn an indirect edge into a direct
> >> Â Â Â one, use cgraph_add_edge_to_call_site_hash to add edges to the call
> >> Â Â Â site hash.
> >> Â Â Â (initialize_inline_failed): Assign a reason to indirect edges.
> >> Â Â Â (cgraph_create_edge_1): New function.
> >> Â Â Â (cgraph_create_edge): Moved some functionality to
> >> Â Â Â cgraph_create_edge_1.
> >> Â Â Â (cgraph_create_indirect_edge): New function.
> >> Â Â Â (cgraph_edge_remove_callee): Add an assert checking for
> >> Â Â Â non-indirectness.
> >> Â Â Â (cgraph_edge_remove_caller): Special-case indirect edges.
> >> Â Â Â (cgraph_remove_edge): Likewise.
> >> Â Â Â (cgraph_set_edge_callee): New function.
> >> Â Â Â (cgraph_redirect_edge_callee): Use cgraph_set_edge_callee.
> >> Â Â Â (cgraph_make_edge_direct): New function.
> >> Â Â Â (cgraph_update_edges_for_call_stmt_node): Do nothing only when also
> >> Â Â Â the declaration of the call statement matches.
> >> Â Â Â (cgraph_node_remove_callees): Special-case indirect edges.
> >> Â Â Â (cgraph_clone_edge): Likewise.
> >> Â Â Â (cgraph_clone_node): Clone also the indirect edges.
> >> Â Â Â (dump_cgraph_node): Dump indirect_inlining_edge flag instead of
> >> Â Â Â indirect_call, dump count of indirect_calls edges.
> >> Â Â Â * ipa-prop.c (ipa_note_param_call): Create indirect edges instead of
> >> Â Â Â creating notes. Â New parameter node.
> >> Â Â Â (ipa_analyze_call_uses): New parameter node, pass it on to
> >> Â Â Â ipa_note_param_call.
> >> Â Â Â (ipa_analyze_stmt_uses): Likewise.
> >> Â Â Â (ipa_analyze_params_uses): Pass node to ipa_analyze_stmt_uses.
> >> Â Â Â (print_edge_addition_message): Work on edges rather than on notes.
> >> Â Â Â (update_call_notes_after_inlining): Likewise.
> >> Â Â Â (ipa_free_node_params_substructures): Do not free notes.
> >> Â Â Â (ipa_node_duplication_hook): Do not duplicate notes.
> >> Â Â Â (ipa_write_param_call_note): Removed.
> >> Â Â Â (ipa_read_param_call_note): Removed.
> >> Â Â Â (ipa_write_indirect_edge_info): New function.
> >> Â Â Â (ipa_read_indirect_edge_info): Likewise.
> >> Â Â Â (ipa_write_node_info): Do not stream notes, do stream information
> >> Â Â Â in indirect edges.
> >> Â Â Â (ipa_read_node_info): Likewise.
> >> Â Â Â (lto_ipa_fixup_call_notes): Removed.
> >> Â Â Â * ipa-cp.c (pass_ipa_cp): Set stmt_fixup to NULL.
> >> Â Â Â * ipa-inline.c (pass_ipa_inline): Likewise.
> >> Â Â Â * cgraphunit.c (verify_cgraph_node): Check also indirect edges.
> >> Â Â Â * cif-code.def (INDIRECT_UNKNOWN_CALL): New reason.
> >> Â Â Â * tree-inline.c (copy_bb): Removed an unnecessary double check for
> >> Â Â Â is_gimple_call.
> >> Â Â Â * tree-inline.c (get_indirect_callee_fndecl): Do not consider indirect
> >> Â Â Â edges.
> >> Â Â Â * lto-cgraph.c (output_outgoing_cgraph_edges): New function.
> >> Â Â Â (output_cgraph): Stream also indirect edges.
> >> Â Â Â (lto_output_edge): Added capability to stream indirect edges..
> >> Â Â Â (input_edge): Likewise.
> >> Â Â Â (input_cgraph_1): Likewise.
> >>
> >> Â Â Â * testsuite/gcc.dg/lto/20091209-1_0.c: New testcase.
> >
> > OK (for pretty-ipa).
> > As Richard commented, we will need way of collecting list of indirect callers
> > for need of passes propagating data across callgraph. Â That can be done
> > incrementally. Â We need way to get list of possible destinations that should
> > be fed in by PTA.
>
> Yeah. We currently throw away the points-to solution for function
> pointer SSA names ...
Yep, also the patch does not provide quite a callgraph with indirect edges, it
just adds edges for callback calls that are interesting for ipa-cp/inlining. I
guess we will need to merge stuff with PTA work first before getting to full
callgraph with indirect calls.
I just didn't wanted to have separate ipa-prop specific datastructure for indirect
calls when we should go for callgraph edges in not so long run.
Honza
>
> Richard.
>
> > Honza
> >
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 6/6] Devirtualization in ipa-cp
2010-02-13 18:04 ` [PATCH 6/6] Devirtualization in ipa-cp Martin Jambor
@ 2010-02-22 16:37 ` Jan Hubicka
2010-03-11 13:42 ` Martin Jambor
0 siblings, 1 reply; 23+ messages in thread
From: Jan Hubicka @ 2010-02-22 16:37 UTC (permalink / raw)
To: Martin Jambor; +Cc: GCC Patches, Jan Hubicka
> @@ -531,6 +537,16 @@ ipcp_cloning_candidate_p (struct cgraph_
> return true;
> }
>
comments ;) How this is different from BOTTOM in the lattice?
The patch overall seems to make sense. Please add describing comment on the
top of ipa-cp as we are now diverging from classical ipa-cp formulation
somewhat (but I can't seem to justify separate devirtualization pass that would
do precisely the same as ipa-cp does but at types only)
I guess patch is Ok with the comment for pretty-ipa, we can deal with the
unnecesary clonning issue later.
Honza
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 5/6] Indirect inlining of virtual calls
2010-02-13 18:04 ` [PATCH 5/6] Indirect inlining " Martin Jambor
@ 2010-02-22 16:49 ` Jan Hubicka
2010-03-10 13:45 ` Martin Jambor
0 siblings, 1 reply; 23+ messages in thread
From: Jan Hubicka @ 2010-02-22 16:49 UTC (permalink / raw)
To: Martin Jambor; +Cc: GCC Patches, Jan Hubicka
> Index: icln/gcc/ipa-prop.c
> ===================================================================
> --- icln.orig/gcc/ipa-prop.c
> +++ icln/gcc/ipa-prop.c
> +/* Given that an actual argument is an SSA_NAME that is a result of a phi
> + statement PHI, try to find out whether NAME is in fact a
> + multiple-inheritance typecast from a descendant into an ancestor of a formal
> + parameter and thus can be described by an ancestor jump function and if so,
> + write the appropriate function into JFUNC.
> +
> + Essentially we want to match the following pattern:
> +
> + if (obj_2(D) != 0B)
> + goto <bb 3>;
> + else
> + goto <bb 4>;
> +
> + <bb 3>:
> + iftmp.1_3 = &obj_2(D)->D.1762;
> +
> + <bb 4>:
> + # iftmp.1_1 = PHI <iftmp.1_3(3), 0B(2)>
> + D.1879_6 = middleman_1 (iftmp.1_1, i_5(D));
> + return D.1879_6; */
Hmm, fragile, but this is old code, right?
> +/* Try to find a base info of BINFO that would have its field decl at offset
> + OFFSET within the BINFO type and which i of EXPECTED_TYPE. If it can be
> + found, return, otherwise return NULL_TREE. */
I guess stuff like this (supporting the overall devirtualization in gimple) should go
into tree.c or similar common place. It would be nice if someone C++ FE aware took a look
on this.
> +
> +static tree
> +get_binfo_at_offset (tree binfo, HOST_WIDE_INT offset, tree expected_type)
> +{
> + tree type;
> +
> + if (offset == 0)
> + return binfo;
> +
> + type = TREE_TYPE (binfo);
> + while (offset > 0)
> + {
> + tree base_binfo, found_binfo;
> + HOST_WIDE_INT pos, size;
> + tree fld;
> + int i;
> +
> + if (TREE_CODE (type) != RECORD_TYPE)
> + return NULL_TREE;
> +
> + for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
> + {
> + if (TREE_CODE (fld) != FIELD_DECL)
> + continue;
> +
> + pos = int_bit_position (fld);
> + size = tree_low_cst (DECL_SIZE (fld), 1);
> + if (pos <= offset && (pos + size) > offset)
> + break;
> + }
> + if (!fld)
> + return NULL_TREE;
> +
> + found_binfo = NULL_TREE;
> + for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
> + if (TREE_TYPE (base_binfo) == TREE_TYPE (fld))
> + {
> + found_binfo = base_binfo;
> + break;
> + }
> +
> + if (!found_binfo)
> + return NULL_TREE;
> +
> + type = TREE_TYPE (fld);
> + binfo = found_binfo;
> + offset -= pos;
> + }
> + if (type != expected_type)
> + return NULL_TREE;
> + return binfo;
> +}
> +
Patch is OK for pretty-ipa.
Honza
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 4/6] Remove unused ipa_note_param_call.called flag (approved)
2010-02-13 18:14 ` Richard Guenther
@ 2010-03-05 16:19 ` Martin Jambor
0 siblings, 0 replies; 23+ messages in thread
From: Martin Jambor @ 2010-03-05 16:19 UTC (permalink / raw)
To: Richard Guenther; +Cc: GCC Patches, Jan Hubicka
Hi,
On Sat, Feb 13, 2010 at 07:14:05PM +0100, Richard Guenther wrote:
> On Sat, Feb 13, 2010 at 7:01 PM, Martin Jambor <mjambor@suse.cz> wrote:
> > This patch is a minor cleanup. Â I have realized that the called flag
> > in the ipa-prop parameter descriptor is not used and I could not
> > really think how the flag can be obviously useful in a short-term
> > either so I removed it.
> >
> > I have bootstrapped and tested this change along with the next one in
> > the series.
> >
> > The patch has already been approved by Honza but this is its place in
> > the series and so I re-send it along.
>
> If this applies independently of the rest of the series it is ok for the trunk
> at this stage.
>
OK, I have moved this patch to the beginning of the queue which
required some minor changes. I will commit the patch below if there
are no objections in the next few hours.
Yes, I have re-bootstrapped and re-tested the patch.
Thanks,
Martin
2010-03-05 Martin Jambor <mjambor@suse.cz>
* ipa-prop.h (struct ipa_param_descriptor): Removed the called field.
(ipa_is_param_called): Removed.
* ipa-prop.c (ipa_note_param_call): Do not set the called flag.
(ipa_print_node_params): Do not print the called flag.
(ipa_write_node_info): Do not stream the called flag.
(ipa_read_node_info): Likewise.
Index: icln/gcc/ipa-prop.c
===================================================================
--- icln.orig/gcc/ipa-prop.c
+++ icln/gcc/ipa-prop.c
@@ -746,8 +746,6 @@ ipa_note_param_call (struct ipa_node_par
struct ipa_param_call_note *note;
basic_block bb = gimple_bb (stmt);
- info->params[formal_id].called = 1;
-
note = XCNEW (struct ipa_param_call_note);
note->formal_id = formal_id;
note->stmt = stmt;
@@ -1425,8 +1423,6 @@ ipa_print_node_params (FILE * f, struct
: "(unnamed)"));
if (ipa_is_param_modified (info, i))
fprintf (f, " modified");
- if (ipa_is_param_called (info, i))
- fprintf (f, " called");
fprintf (f, "\n");
}
}
@@ -2024,10 +2020,7 @@ ipa_write_node_info (struct output_block
gcc_assert (!info->node_enqueued);
gcc_assert (!info->ipcp_orig_node);
for (j = 0; j < ipa_get_param_count (info); j++)
- {
- bp_pack_value (bp, info->params[j].modified, 1);
- bp_pack_value (bp, info->params[j].called, 1);
- }
+ bp_pack_value (bp, info->params[j].modified, 1);
lto_output_bitpack (ob->main_stream, bp);
bitpack_delete (bp);
for (e = node->callees; e; e = e->next_callee)
@@ -2071,10 +2064,7 @@ ipa_read_node_info (struct lto_input_blo
}
info->node_enqueued = false;
for (k = 0; k < ipa_get_param_count (info); k++)
- {
- info->params[k].modified = bp_unpack_value (bp, 1);
- info->params[k].called = bp_unpack_value (bp, 1);
- }
+ info->params[k].modified = bp_unpack_value (bp, 1);
bitpack_delete (bp);
for (e = node->callees; e; e = e->next_callee)
{
Index: icln/gcc/ipa-prop.h
===================================================================
--- icln.orig/gcc/ipa-prop.h
+++ icln/gcc/ipa-prop.h
@@ -169,8 +169,6 @@ struct ipa_param_descriptor
tree decl;
/* Whether the value parameter has been modified within the function. */
unsigned modified : 1;
- /* Whether the parameter has been used as a call destination. */
- unsigned called : 1;
};
/* ipa_node_params stores information related to formal parameters of functions
@@ -248,17 +246,6 @@ ipa_is_param_modified (struct ipa_node_p
return info->params[i].modified;
}
-/* Return the called flag corresponding to the Ith formal parameter of the
- function associated with INFO. Note that there is no setter method as the
- goal is to set all flags when building the array in
- ipa_detect_called_params. */
-
-static inline bool
-ipa_is_param_called (struct ipa_node_params *info, int i)
-{
- return info->params[i].called;
-}
-
/* Flag this node as having callers with variable number of arguments. */
static inline void
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 2/6] Indirect call graph edges
2010-02-13 18:25 ` Richard Guenther
@ 2010-03-05 17:06 ` Martin Jambor
0 siblings, 0 replies; 23+ messages in thread
From: Martin Jambor @ 2010-03-05 17:06 UTC (permalink / raw)
To: Richard Guenther; +Cc: GCC Patches, Jan Hubicka
Hi,
On Sat, Feb 13, 2010 at 07:25:01PM +0100, Richard Guenther wrote:
> On Sat, Feb 13, 2010 at 7:16 PM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
> >> The data structure layout (a flag and a pointer in struct cgraph_edge
> >> to a another special structure) was really chosen by Honza. The
> >> subsequent patches add some more stuff to cgraph_indirect_call_info so
> >> it won't look this silly for long.
> >>
> >> I have successfully bootstrapped and tested this beast on x86_84-linux
> >> and would like to commit something along these lines when stage1 opens
> >> again. Obviously, I welcome any comments.
> >
> > The cgraph.c file at the top currently contains very brief documentation
> > which needs to be updated as it says:
> >
> > The callgraph at the moment does not represent indirect calls or calls
> > from other compilation unit.
Thanks, I have updated the comment.
> >
> > Note that I think we should have some more elaborate overall overview
> > about the cgraph interface.
>
> Btw, I wonder what the callee node of an indirect edge points to?
With this patch applied it points to whatever value is in the
parameter with index edge->indirect_info->param_index. The index is
initialized to -1 when creating an inedirect edge but at the moment I
always set it to a non-negative value immediately afterwards.
> Should we have a way to put a cgraph node set there? In IPA mod/ref
> analysis it would be useful to know which functions can be reached
> via an indirect call - the conservative set should be all functions
> that had their address taken (but I believe we lie here for virtual
> functions).
>
> Pointer analysis could also restrict the callee set like for
>
> void (*p)(void);
> if (b)
> p = foo;
> else
> p = bar;
> (*p)();
>
> where we know we either call foo or bar. Is there a suitable place to
> note this kind of information?
Well, you can put anything into struct cgraph_indirect_call_info, be
it a head of a linked list of such nodes or a bitmap (node uids should
be rather dense, since all concerned nodes are needed none of them
should disappear and/or be reused and I don't think we will be
redirecting these calls to clones).
I will re-send the patch set (except those submitted/committed
separately) soon.
Thanks,
Martin
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 5/6] Indirect inlining of virtual calls
2010-02-22 16:49 ` Jan Hubicka
@ 2010-03-10 13:45 ` Martin Jambor
2010-03-10 15:24 ` Jan Hubicka
0 siblings, 1 reply; 23+ messages in thread
From: Martin Jambor @ 2010-03-10 13:45 UTC (permalink / raw)
To: Jan Hubicka; +Cc: GCC Patches
Hi,
On Mon, Feb 22, 2010 at 05:37:43PM +0100, Jan Hubicka wrote:
> > Index: icln/gcc/ipa-prop.c
> > ===================================================================
> > --- icln.orig/gcc/ipa-prop.c
> > +++ icln/gcc/ipa-prop.c
> > +/* Given that an actual argument is an SSA_NAME that is a result of a phi
> > + statement PHI, try to find out whether NAME is in fact a
> > + multiple-inheritance typecast from a descendant into an ancestor of a formal
> > + parameter and thus can be described by an ancestor jump function and if so,
> > + write the appropriate function into JFUNC.
> > +
> > + Essentially we want to match the following pattern:
> > +
> > + if (obj_2(D) != 0B)
> > + goto <bb 3>;
> > + else
> > + goto <bb 4>;
> > +
> > + <bb 3>:
> > + iftmp.1_3 = &obj_2(D)->D.1762;
> > +
> > + <bb 4>:
> > + # iftmp.1_1 = PHI <iftmp.1_3(3), 0B(2)>
> > + D.1879_6 = middleman_1 (iftmp.1_1, i_5(D));
> > + return D.1879_6; */
>
> Hmm, fragile, but this is old code, right?
I don't understand. This is what typecasting to a second-or-later
ancestor looks like (NULL for NULL, add offset otherwise). The
function that builds ANCESTOR jump functions needs to match it.
>
> > +/* Try to find a base info of BINFO that would have its field decl at offset
> > + OFFSET within the BINFO type and which i of EXPECTED_TYPE. If it can be
> > + found, return, otherwise return NULL_TREE. */
>
> I guess stuff like this (supporting the overall devirtualization in
> gimple) should go into tree.c or similar common place.
OK, I've moved it there.
> It would be nice if someone C++ FE aware took a look on this.
Indeed.
Thanks,
Martin
> > +
> > +static tree
> > +get_binfo_at_offset (tree binfo, HOST_WIDE_INT offset, tree expected_type)
> > +{
> > + tree type;
> > +
> > + if (offset == 0)
> > + return binfo;
> > +
> > + type = TREE_TYPE (binfo);
> > + while (offset > 0)
> > + {
> > + tree base_binfo, found_binfo;
> > + HOST_WIDE_INT pos, size;
> > + tree fld;
> > + int i;
> > +
> > + if (TREE_CODE (type) != RECORD_TYPE)
> > + return NULL_TREE;
> > +
> > + for (fld = TYPE_FIELDS (type); fld; fld = TREE_CHAIN (fld))
> > + {
> > + if (TREE_CODE (fld) != FIELD_DECL)
> > + continue;
> > +
> > + pos = int_bit_position (fld);
> > + size = tree_low_cst (DECL_SIZE (fld), 1);
> > + if (pos <= offset && (pos + size) > offset)
> > + break;
> > + }
> > + if (!fld)
> > + return NULL_TREE;
> > +
> > + found_binfo = NULL_TREE;
> > + for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
> > + if (TREE_TYPE (base_binfo) == TREE_TYPE (fld))
> > + {
> > + found_binfo = base_binfo;
> > + break;
> > + }
> > +
> > + if (!found_binfo)
> > + return NULL_TREE;
> > +
> > + type = TREE_TYPE (fld);
> > + binfo = found_binfo;
> > + offset -= pos;
> > + }
> > + if (type != expected_type)
> > + return NULL_TREE;
> > + return binfo;
> > +}
> > +
>
> Patch is OK for pretty-ipa.
>
> Honza
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 5/6] Indirect inlining of virtual calls
2010-03-10 13:45 ` Martin Jambor
@ 2010-03-10 15:24 ` Jan Hubicka
0 siblings, 0 replies; 23+ messages in thread
From: Jan Hubicka @ 2010-03-10 15:24 UTC (permalink / raw)
To: Jan Hubicka, GCC Patches
> Hi,
>
> > > + <bb 3>:
> > > + iftmp.1_3 = &obj_2(D)->D.1762;
> > > +
> > > + <bb 4>:
> > > + # iftmp.1_1 = PHI <iftmp.1_3(3), 0B(2)>
> > > + D.1879_6 = middleman_1 (iftmp.1_1, i_5(D));
> > > + return D.1879_6; */
> >
> > Hmm, fragile, but this is old code, right?
>
> I don't understand. This is what typecasting to a second-or-later
> ancestor looks like (NULL for NULL, add offset otherwise). The
> function that builds ANCESTOR jump functions needs to match it.
Yep, I guess for sake of those optimizations we might think of inventing GIMPLE codes
for these operations and lowering later. But if we can limit this matching to few
places and get it robust enough I uess it is fine.
Honza
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 6/6] Devirtualization in ipa-cp
2010-02-22 16:37 ` Jan Hubicka
@ 2010-03-11 13:42 ` Martin Jambor
0 siblings, 0 replies; 23+ messages in thread
From: Martin Jambor @ 2010-03-11 13:42 UTC (permalink / raw)
To: Jan Hubicka; +Cc: GCC Patches
Hi,
On Mon, Feb 22, 2010 at 05:08:05PM +0100, Jan Hubicka wrote:
> > @@ -531,6 +537,16 @@ ipcp_cloning_candidate_p (struct cgraph_
> > return true;
> > }
> >
> comments ;) How this is different from BOTTOM in the lattice?
I have added the missing comment. cannot_devirtualize is basically
BOTTOM for devirtualization. However these two are distinct values.
For example, sometimes we cannot propagate a constant because an
ADDR_EXPR of a local variable is passed in an argument, so the IPA-CP
lattice is BOTTOM, but we still can propagate the type for
devirtualization. Or there may be different constants passed to a
function, again resulting to IPA-CP BOTTOM lattice for the parameter,
but we still might build and use a list of their types. Conversely,
even if we propagate an IPA constant in IPA-CP, its type might not
have any BINFO associated with it and therefore we cannot use the
parameter for devirtualization.
>
> The patch overall seems to make sense. Please add describing
> comment on the top of ipa-cp as we are now diverging from classical
> ipa-cp formulation somewhat (but I can't seem to justify separate
> devirtualization pass that would do precisely the same as ipa-cp
> does but at types only)
Thanks, I have added that comment too and will resubmit the patches
soon.
Martin
^ permalink raw reply [flat|nested] 23+ messages in thread
end of thread, other threads:[~2010-03-11 13:20 UTC | newest]
Thread overview: 23+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2010-02-13 18:03 [PATCH 0/6] Cgraph changes and various devirtualizations Martin Jambor
2010-02-13 18:03 ` [PATCH 1/6] Clarify edge redirection for inline clones Martin Jambor
2010-02-22 14:23 ` Jan Hubicka
2010-02-13 18:04 ` [PATCH 6/6] Devirtualization in ipa-cp Martin Jambor
2010-02-22 16:37 ` Jan Hubicka
2010-03-11 13:42 ` Martin Jambor
2010-02-13 18:04 ` [PATCH 3/6] Folding of virtual calls Martin Jambor
2010-02-13 18:12 ` Richard Guenther
2010-02-13 18:04 ` [PATCH 5/6] Indirect inlining " Martin Jambor
2010-02-22 16:49 ` Jan Hubicka
2010-03-10 13:45 ` Martin Jambor
2010-03-10 15:24 ` Jan Hubicka
2010-02-13 18:04 ` [PATCH 4/6] Remove unused ipa_note_param_call.called flag (approved) Martin Jambor
2010-02-13 18:14 ` Richard Guenther
2010-03-05 16:19 ` Martin Jambor
2010-02-22 15:04 ` Jan Hubicka
2010-02-13 18:04 ` [PATCH 2/6] Indirect call graph edges Martin Jambor
2010-02-13 18:17 ` Richard Guenther
2010-02-13 18:25 ` Richard Guenther
2010-03-05 17:06 ` Martin Jambor
2010-02-22 15:52 ` Jan Hubicka
2010-02-22 16:05 ` Richard Guenther
2010-02-22 16:06 ` Jan Hubicka
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).