This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [middle-end, patch 7/8] Inlining of indirect calls
Hi,
On Mon, Jul 21, 2008 at 09:46:23PM +0200, Jan Hubicka wrote:
> > 2008-07-21 Martin Jambor <mjambor@suse.cz>
> >
> > * ipa-inline.c (cgraph_decide_recursive_inlining): Call
> > ipa_propagate_indirect_call_infos if performing indirect inlining,
> > pass a new parameter new_edges to it.
> > (add_new_edges_to_heap): New fucntion.
> > (cgraph_decide_inlining_of_small_functions): New vector
> > new_indirect_edges for newly found indirect edges , call
> > ipa_propagate_indirect_call_infos after inlining.
> > (cgraph_decide_inlining): Call ipa_propagate_indirect_call_infos after
> > inlining if performing indirect inlining. Call
> > free_all_ipa_structures_after_iinln when doing so too.
> > (inline_generate_summary): Do not call
> > free_all_ipa_structures_after_iinln here.
> > * ipa-prop.c (update_jump_functions_after_inlining): New function.
> > (print_edge_addition_message): New function.
> > (update_call_notes_after_inlining): New function.
> > (propagate_info_to_inlined_callees): New function.
> > (ipa_propagate_indirect_call_infos): New function.
> > * ipa-prop.h: Include cgraph.h
> > (struct ipa_param_call_note): Fields reordered, new field processed.
> > * cgraph.h (cgraph_edge): Shrink loop_nest field to 31 bits, add a new
> > flag indirect_call.
> > * cgraphunit.c (verify_cgraph_node): Allow indirect edges not to have
> > rediscovered call statements.
> > * cgraph.c (cgraph_create_edge): Initialize indirect_call to zero.
> > (dump_cgraph_node): Dump also the indirect_call flag.
> > (cgraph_clone_edge): Copy also the indirect_call flag.
> > * tree-inline.c (copy_bb): Do not check for fndecls from call
> > expressions, check for edge availability when moving clones.
> > (get_indirect_callee_fndecl): New function.
> > (expand_call_inline): If callee declaration is not apprent from
> > the statement, try calling get_indirect_callee_fndecl. Do not
> > issue warnings or call sorry when not inlinings an indirect edge.
> > * Makefile.in (IPA_PROP_H): Added $(CGRAPH_H) to dependencies.
> >
>
> OK
> Honza
When testing at -O2, I have bumped into a gcc_assert in
update_call_notes_after_inlining(). Apparently, we need to check that
the declaration we have is a FUNCTION_DECL because NULLs disguised as
integers can get this far. The new patch is below.
I am bootstrapping and regression testing the whole series now and
will commit it tomorrow if everything goes fine.
Thanks a lot,
Martin
2008-07-22 Martin Jambor <mjambor@suse.cz>
* ipa-inline.c (cgraph_decide_recursive_inlining): Call
ipa_propagate_indirect_call_infos if performing indirect inlining,
pass a new parameter new_edges to it.
(add_new_edges_to_heap): New fucntion.
(cgraph_decide_inlining_of_small_functions): New vector
new_indirect_edges for newly found indirect edges , call
ipa_propagate_indirect_call_infos after inlining.
(cgraph_decide_inlining): Call ipa_propagate_indirect_call_infos after
inlining if performing indirect inlining. Call
free_all_ipa_structures_after_iinln when doing so too.
(inline_generate_summary): Do not call
free_all_ipa_structures_after_iinln here.
* ipa-prop.c (update_jump_functions_after_inlining): New function.
(print_edge_addition_message): New function.
(update_call_notes_after_inlining): New function.
(propagate_info_to_inlined_callees): New function.
(ipa_propagate_indirect_call_infos): New function.
* ipa-prop.h: Include cgraph.h
(struct ipa_param_call_note): Fields reordered, new field processed.
* cgraph.h (cgraph_edge): Shrink loop_nest field to 31 bits, add a new
flag indirect_call.
* cgraphunit.c (verify_cgraph_node): Allow indirect edges not to have
rediscovered call statements.
* cgraph.c (cgraph_create_edge): Initialize indirect_call to zero.
(dump_cgraph_node): Dump also the indirect_call flag.
(cgraph_clone_edge): Copy also the indirect_call flag.
* tree-inline.c (copy_bb): Do not check for fndecls from call
expressions, check for edge availability when moving clones.
(get_indirect_callee_fndecl): New function.
(expand_call_inline): If callee declaration is not apprent from
the statement, try calling get_indirect_callee_fndecl. Do not
issue warnings or call sorry when not inlinings an indirect edge.
* Makefile.in (IPA_PROP_H): Added $(CGRAPH_H) to dependencies.
Index: iinln/gcc/ipa-inline.c
===================================================================
--- iinln.orig/gcc/ipa-inline.c
+++ iinln/gcc/ipa-inline.c
@@ -661,10 +661,12 @@ lookup_recursive_calls (struct cgraph_no
}
/* Decide on recursive inlining: in the case function has recursive calls,
- inline until body size reaches given argument. */
+ inline until body size reaches given argument. If any new indirect edges
+ are discovered in the process, add them to NEW_EDGES, unless it is NULL. */
static bool
-cgraph_decide_recursive_inlining (struct cgraph_node *node)
+cgraph_decide_recursive_inlining (struct cgraph_node *node,
+ VEC (cgraph_edge_p, heap) *new_edges)
{
int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
int max_depth = PARAM_VALUE (PARAM_MAX_INLINE_RECURSIVE_DEPTH_AUTO);
@@ -761,6 +763,8 @@ cgraph_decide_recursive_inlining (struct
}
cgraph_redirect_edge_callee (curr, master_clone);
cgraph_mark_inline_edge (curr, false);
+ if (flag_indirect_inlining)
+ ipa_propagate_indirect_call_infos (curr, new_edges);
lookup_recursive_calls (node, curr->callee, heap);
n++;
}
@@ -818,6 +822,20 @@ compute_max_insns (int insns)
* (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
}
+/* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
+static void
+add_new_edges_to_heap (fibheap_t heap, VEC (cgraph_edge_p, heap) *new_edges)
+{
+ while (VEC_length (cgraph_edge_p, new_edges) > 0)
+ {
+ struct cgraph_edge *edge = VEC_pop (cgraph_edge_p, new_edges);
+
+ gcc_assert (!edge->aux);
+ edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
+ }
+}
+
+
/* We use greedy algorithm for inlining of small functions:
All inline candidates are put into prioritized heap based on estimated
growth of the overall number of instructions and then update the estimates.
@@ -834,6 +852,10 @@ cgraph_decide_inlining_of_small_function
fibheap_t heap = fibheap_new ();
bitmap updated_nodes = BITMAP_ALLOC (NULL);
int min_insns, max_insns;
+ VEC (cgraph_edge_p, heap) *new_indirect_edges = NULL;
+
+ if (flag_indirect_inlining)
+ new_indirect_edges = VEC_alloc (cgraph_edge_p, heap, 8);
if (dump_file)
fprintf (dump_file, "\nDeciding on smaller functions:\n");
@@ -961,8 +983,10 @@ cgraph_decide_inlining_of_small_function
where = edge->caller;
if (where->global.inlined_to)
where = where->global.inlined_to;
- if (!cgraph_decide_recursive_inlining (where))
+ if (!cgraph_decide_recursive_inlining (where, new_indirect_edges))
continue;
+ if (flag_indirect_inlining)
+ add_new_edges_to_heap (heap, new_indirect_edges);
update_callee_keys (heap, where, updated_nodes);
}
else
@@ -979,6 +1003,11 @@ cgraph_decide_inlining_of_small_function
}
callee = edge->callee;
cgraph_mark_inline_edge (edge, true);
+ if (flag_indirect_inlining)
+ {
+ ipa_propagate_indirect_call_infos (edge, new_indirect_edges);
+ add_new_edges_to_heap (heap, new_indirect_edges);
+ }
update_callee_keys (heap, callee, updated_nodes);
}
where = edge->caller;
@@ -1021,6 +1050,9 @@ cgraph_decide_inlining_of_small_function
&edge->inline_failed))
edge->inline_failed = N_("--param inline-unit-growth limit reached");
}
+
+ if (new_indirect_edges)
+ VEC_free (cgraph_edge_p, heap, new_indirect_edges);
fibheap_delete (heap);
BITMAP_FREE (updated_nodes);
}
@@ -1100,6 +1132,8 @@ cgraph_decide_inlining (void)
&e->inline_failed))
continue;
cgraph_mark_inline_edge (e, true);
+ if (flag_indirect_inlining)
+ ipa_propagate_indirect_call_infos (e, NULL);
if (dump_file)
fprintf (dump_file,
" Inlined into %s which now has %i insns.\n",
@@ -1121,6 +1155,11 @@ cgraph_decide_inlining (void)
if (!flag_really_no_inline)
cgraph_decide_inlining_of_small_functions ();
+ /* After this point, any edge discovery performed by indirect inlining is no
+ good so let's give up. */
+ if (flag_indirect_inlining)
+ free_all_ipa_structures_after_iinln ();
+
if (!flag_really_no_inline
&& flag_inline_functions_called_once)
{
@@ -1639,8 +1678,6 @@ inline_generate_summary (void)
}
current_function_decl = NULL;
- if (flag_indirect_inlining)
- free_all_ipa_structures_after_iinln ();
free (order);
return;
}
Index: iinln/gcc/ipa-prop.c
===================================================================
--- iinln.orig/gcc/ipa-prop.c
+++ iinln/gcc/ipa-prop.c
@@ -872,6 +872,154 @@ ipa_analyze_params_uses (struct cgraph_n
info->uses_analysis_done = 1;
}
+/* Update the jump functions assocated 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. */
+static void
+update_jump_functions_after_inlining (struct cgraph_edge *cs,
+ struct cgraph_edge *e)
+{
+ struct ipa_edge_args *top = IPA_EDGE_REF (cs);
+ struct ipa_edge_args *args = IPA_EDGE_REF (e);
+ int count = ipa_get_cs_argument_count (args);
+ int i;
+
+ for (i = 0; i < count; i++)
+ {
+ struct ipa_jump_func *src, *dst = ipa_get_ith_jump_func (args, i);
+
+ if (dst->type != IPA_PASS_THROUGH)
+ continue;
+
+ /* We must check range due to calls with variable number of arguments: */
+ if (dst->value.formal_id >= (unsigned) ipa_get_cs_argument_count (top))
+ {
+ dst->type = IPA_BOTTOM;
+ continue;
+ }
+
+ src = ipa_get_ith_jump_func (top, dst->value.formal_id);
+ *dst = *src;
+ }
+}
+
+/* Print out a debug message to file F that we have discovered that an indirect
+ call descibed by NT is in fact a call of a known constant function descibed
+ 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)
+{
+ fprintf (f, "ipa-prop: Discovered an indirect call to a known target (");
+ if (jfunc->type == IPA_CONST_MEMBER_PTR)
+ {
+ print_node_brief (f, "", jfunc->value.member_cst.pfn, 0);
+ print_node_brief (f, ", ", jfunc->value.member_cst.delta, 0);
+ }
+ else
+ print_node_brief(f, "", jfunc->value.constant, 0);
+
+ fprintf (f, ") in %s: ", cgraph_node_name (node));
+ print_generic_stmt (f, nt->stmt, 2);
+}
+
+/* Update the param called notes associated with NODE when CS is being inlined,
+ assuming NODE is (potentially indirectly) inlined into CS->callee.
+ Moreover, if the callee is discovered to be constant, create a new cgraph
+ edge for it. Newly discovered indirect edges will be added to NEW_EDGES,
+ unless it is NULL. */
+static void
+update_call_notes_after_inlining (struct cgraph_edge *cs,
+ 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;
+
+ for (nt = info->param_calls; nt; nt = nt->next)
+ {
+ struct ipa_jump_func *jfunc;
+
+ if (nt->processed)
+ continue;
+
+ /* We must check range due to calls with variable number of arguments: */
+ if (nt->formal_id >= (unsigned) ipa_get_cs_argument_count (top))
+ {
+ nt->processed = true;
+ continue;
+ }
+
+ jfunc = ipa_get_ith_jump_func (top, nt->formal_id);
+ if (jfunc->type == IPA_PASS_THROUGH)
+ nt->formal_id = jfunc->value.formal_id;
+ else if (jfunc->type == IPA_CONST || jfunc->type == IPA_CONST_MEMBER_PTR)
+ {
+ struct cgraph_node *callee;
+ struct cgraph_edge *new_indirect_edge;
+ tree decl;
+
+ nt->processed = true;
+ if (jfunc->type == IPA_CONST_MEMBER_PTR)
+ decl = jfunc->value.member_cst.pfn;
+ else
+ decl = jfunc->value.constant;
+
+ if (TREE_CODE (decl) != FUNCTION_DECL)
+ continue;
+ callee = cgraph_node (decl);
+ if (!callee || !callee->local.inlinable)
+ continue;
+
+ if (dump_file)
+ print_edge_addition_message (dump_file, nt, jfunc, node);
+
+ new_indirect_edge = cgraph_create_edge (node, callee, nt->stmt,
+ nt->count, nt->frequency,
+ nt->loop_nest);
+ new_indirect_edge->indirect_call = 1;
+ ipa_check_create_edge_args ();
+ if (new_edges)
+ VEC_safe_push (cgraph_edge_p, heap, new_edges, new_indirect_edge);
+ }
+ }
+}
+
+/* Recursively traverse subtree of NODE (including node) made of inlined
+ cgraph_edges when CS has been inlined and invoke
+ update_call_notes_after_inlining on all nodes and
+ update_jump_functions_after_inlining on all non-inlined edges that lead out
+ of this subtree. Newly discovered indirect edges will be added to
+ NEW_EDGES, unless it is NULL. */
+static void
+propagate_info_to_inlined_callees (struct cgraph_edge *cs,
+ struct cgraph_node *node,
+ VEC (cgraph_edge_p, heap) *new_edges)
+{
+ struct cgraph_edge *e;
+
+ update_call_notes_after_inlining (cs, node, new_edges);
+
+ for (e = node->callees; e; e = e->next_callee)
+ if (!e->inline_failed)
+ propagate_info_to_inlined_callees (cs, e->callee, new_edges);
+ else
+ update_jump_functions_after_inlining (cs, e);
+}
+
+/* Update jump functions and call note functions on inlining the call site CS.
+ CS is expected to lead to a node already cloned by
+ cgraph_clone_inline_nodes. Newly discovered indirect edges will be added to
+ NEW_EDGES, unless it is NULL. */
+void
+ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
+ VEC (cgraph_edge_p, heap) *new_edges)
+{
+ propagate_info_to_inlined_callees (cs, cs->callee, new_edges);
+}
+
/* Frees all dynamically allocated structures that the argument info points
to. */
void
Index: iinln/gcc/ipa-prop.h
===================================================================
--- iinln.orig/gcc/ipa-prop.h
+++ iinln/gcc/ipa-prop.h
@@ -22,6 +22,7 @@ along with GCC; see the file COPYING3.
#include "tree.h"
#include "vec.h"
+#include "cgraph.h"
/* The following definitions and interfaces are used by
interprocedural analyses. */
@@ -128,10 +129,12 @@ struct ipa_param_flags
are linked in a list. */
struct ipa_param_call_note
{
- /* Index of the parameter that is called. */
- unsigned int formal_id;
+ /* Linked list's next */
+ struct ipa_param_call_note *next;
/* Statement that contains the call to the parameter above. */
tree stmt;
+ /* Index of the parameter that is called. */
+ unsigned int formal_id;
/* Expected number of executions: calculated in profile.c. */
gcov_type count;
/* Expected frequency of executions within the function. see cgraph_edge in
@@ -139,9 +142,10 @@ struct ipa_param_call_note
int frequency;
/* Depth of loop nest, 1 means no loop nest. */
int loop_nest;
-
- /* Linked list's next */
- struct ipa_param_call_note *next;
+ /* 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;
};
/* ipa_node_params stores information related to formal parameters of functions
@@ -377,6 +381,8 @@ void ipa_count_formal_params (struct cgr
void ipa_create_param_decls_array (struct cgraph_node *);
void ipa_detect_param_modifications (struct cgraph_node *);
void ipa_analyze_params_uses (struct cgraph_node *);
+void ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
+ VEC (cgraph_edge_p, heap) *new_edges);
/* Debugging interface. */
void ipa_print_all_tree_maps (FILE *);
Index: iinln/gcc/cgraph.h
===================================================================
--- iinln.orig/gcc/cgraph.h
+++ iinln/gcc/cgraph.h
@@ -208,7 +208,9 @@ struct cgraph_edge GTY((chain_next ("%h.
per function call. The range is 0 to CGRAPH_FREQ_MAX. */
int frequency;
/* Depth of loop nest, 1 means no loop nest. */
- int loop_nest;
+ unsigned int loop_nest : 31;
+ /* Whether this edge describes a call that was originally indirect. */
+ unsigned int indirect_call : 1;
/* Unique id of the edge. */
int uid;
};
Index: iinln/gcc/cgraphunit.c
===================================================================
--- iinln.orig/gcc/cgraphunit.c
+++ iinln/gcc/cgraphunit.c
@@ -796,7 +796,7 @@ verify_cgraph_node (struct cgraph_node *
for (e = node->callees; e; e = e->next_callee)
{
- if (!e->aux)
+ if (!e->aux && !e->indirect_call)
{
error ("edge %s->%s has no corresponding call_stmt",
cgraph_node_name (e->caller),
Index: iinln/gcc/cgraph.c
===================================================================
--- iinln.orig/gcc/cgraph.c
+++ iinln/gcc/cgraph.c
@@ -625,6 +625,7 @@ cgraph_create_edge (struct cgraph_node *
gcc_assert (freq >= 0);
gcc_assert (freq <= CGRAPH_FREQ_MAX);
edge->loop_nest = nest;
+ edge->indirect_call = 0;
edge->uid = cgraph_edge_max_uid++;
if (caller->call_site_hash)
{
@@ -1048,6 +1049,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) ");
}
fprintf (f, "\n calls: ");
@@ -1057,6 +1060,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->count)
fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
(HOST_WIDEST_INT)edge->count);
@@ -1166,6 +1171,7 @@ cgraph_clone_edge (struct cgraph_edge *e
e->loop_nest + loop_nest);
new->inline_failed = e->inline_failed;
+ new->indirect_call = e->indirect_call;
if (update_original)
{
e->count -= new->count;
Index: iinln/gcc/tree-inline.c
===================================================================
--- iinln.orig/gcc/tree-inline.c
+++ iinln/gcc/tree-inline.c
@@ -951,7 +951,7 @@ copy_bb (copy_body_data *id, basic_block
pointer_set_insert (id->statements_to_fold, stmt);
/* We're duplicating a CALL_EXPR. Find any corresponding
callgraph edges and update or duplicate them. */
- if (call && (decl = get_callee_fndecl (call)))
+ if (call)
{
struct cgraph_node *node;
struct cgraph_edge *edge;
@@ -962,7 +962,8 @@ copy_bb (copy_body_data *id, basic_block
edge = cgraph_edge (id->src_node, orig_stmt);
if (edge)
cgraph_clone_edge (edge, id->dst_node, stmt,
- REG_BR_PROB_BASE, 1, edge->frequency, true);
+ REG_BR_PROB_BASE, 1,
+ edge->frequency, true);
break;
case CB_CGE_MOVE_CLONES:
@@ -971,8 +972,8 @@ copy_bb (copy_body_data *id, basic_block
node = node->next_clone)
{
edge = cgraph_edge (node, orig_stmt);
- gcc_assert (edge);
- cgraph_set_call_stmt (edge, stmt);
+ if (edge)
+ cgraph_set_call_stmt (edge, stmt);
}
/* FALLTHRU */
@@ -2580,6 +2581,20 @@ add_lexical_block (tree current_block, t
BLOCK_SUPERCONTEXT (new_block) = current_block;
}
+/* Fetch callee declaration from the call graph edge going from NODE and
+ associated with STMR call statement. Return NULL_TREE if not found. */
+static tree
+get_indirect_callee_fndecl (struct cgraph_node *node, tree stmt)
+{
+ struct cgraph_edge *cs;
+
+ cs = cgraph_edge (node, stmt);
+ if (cs)
+ return cs->callee->decl;
+
+ return NULL_TREE;
+}
+
/* If *TP is a CALL_EXPR, replace it with its inline expansion. */
static bool
@@ -2621,7 +2636,11 @@ expand_call_inline (basic_block bb, tree
If we cannot, then there is no hope of inlining the function. */
fn = get_callee_fndecl (t);
if (!fn)
- goto egress;
+ {
+ fn = get_indirect_callee_fndecl (id->dst_node, stmt);
+ if (!fn)
+ goto egress;
+ }
/* Turn forward declarations into real ones. */
fn = cgraph_node (fn)->decl;
@@ -2672,6 +2691,12 @@ expand_call_inline (basic_block bb, tree
inlining. */
if (!cgraph_inline_p (cg_edge, &reason))
{
+ /* 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)
+ goto egress;
+
if (lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn))
/* Avoid warnings during early inline pass. */
&& (!flag_unit_at_a_time || cgraph_global_info_ready))
Index: iinln/gcc/Makefile.in
===================================================================
--- iinln.orig/gcc/Makefile.in
+++ iinln/gcc/Makefile.in
@@ -860,7 +860,7 @@ TREE_INLINE_H = tree-inline.h $(VARRAY_H
REAL_H = real.h $(MACHMODE_H)
DBGCNT_H = dbgcnt.h dbgcnt.def
EBIMAP_H = ebitmap.h sbitmap.h
-IPA_PROP_H = ipa-prop.h $(TREE_H) vec.h
+IPA_PROP_H = ipa-prop.h $(TREE_H) vec.h $(CGRAPH_H)
GSTAB_H = gstab.h stab.def
BITMAP_H = bitmap.h $(HASHTAB_H) statistics.h
@@ -2563,7 +2563,7 @@ varpool.o : varpool.c $(CONFIG_H) $(SYST
$(TREE_FLOW_H) gt-varpool.h
ipa.o : ipa.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRAPH_H) \
tree-pass.h $(TIMEVAR_H)
-ipa-prop.o : ipa-prop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
+ipa-prop.o : ipa-prop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
langhooks.h $(GGC_H) $(TARGET_H) $(CGRAPH_H) $(IPA_PROP_H) $(DIAGNOSTIC_H) \
$(TREE_FLOW_H) $(TM_H) tree-pass.h $(FLAGS_H) $(TREE_H) $(TREE_INLINE_H) \
$(TIMEVAR_H)