[middle-end, patch 7/8] Inlining of indirect calls

[Martin Jambor <mjambor at suse dot cz>]

This  patch updates information  gathered by  intraprocedural analysis
during  inlining.  Moreover,  if the  interprocedural  phase discovers
that there is an indirect call which now has a target known at compile
time thanks to previous inlining, a new edge is created for it so that
it  also can  be inlined.   In  the phase  when the  inlining plan  is
actually carried  out, these new edges  are also used  to identify the
to-be inlined callees.

The main difference is that last time I forgot to call
ipa_check_create_edge_args() from update_call_notes_after_inlining().
Otherwise this patch is also mostly the same as before.


2008-07-15  Martin Jambor  <mjambor@suse.cz>

	* ipa-inline.c (cgraph_consider_new_edge_for_inlining): New function.
	(cgraph_decide_recursive_inlining): Call
	ipa_propagate_indirect_call_infos if performing indirect inlining.
	(add_new_indirect_edges_to_heap): New fucntion.
	(cgraph_decide_inlining_of_small_functions): Call
	add_new_indirect_edges_to_heap after recursive inlining when
	performing indirect inlining, call ipa_propagate_indirect_call_infos
	after ordinary inlining in that situation.
	(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: Include fibheap.h.
	(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 fibheap.h.
	(struct ipa_param_call_note): 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.


Index: iinln/gcc/ipa-inline.c
===================================================================
--- iinln.orig/gcc/ipa-inline.c
+++ iinln/gcc/ipa-inline.c
@@ -619,6 +619,16 @@ update_caller_keys (fibheap_t heap, stru
       }
 }
 
+/* Computes the badness of the given EDGE and inserts into the HEAP.  Intended
+   to be called from outside this file during deciding about inlining small
+   functions.  */
+void
+cgraph_consider_new_edge_for_inlining (fibheap_t heap, struct cgraph_edge *edge)
+{
+  gcc_assert (!edge->aux);
+  edge->aux = fibheap_insert (heap, cgraph_edge_badness (edge), edge);
+}
+
 /* Recompute heap nodes for each of caller edges of each of callees.  */
 
 static void
@@ -761,6 +771,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 (NULL, curr);
       lookup_recursive_calls (node, curr->callee, heap);
       n++;
     }
@@ -818,6 +830,23 @@ compute_max_insns (int insns)
 	  * (100 + PARAM_VALUE (PARAM_INLINE_UNIT_GROWTH)) / 100);
 }
 
+/* Scans the subtree of functions inlined to NODE and all indirect edges that
+   have not their badness computed yet to the HEAP.  */
+static void
+add_new_indirect_edges_to_heap (fibheap_t heap, struct cgraph_node *node)
+{
+  struct cgraph_edge *e;
+  for (e = node->callees; e; e = e->next_callee)
+    if (e->inline_failed)
+      {
+	if (e->indirect_call && !e->aux)
+	  cgraph_consider_new_edge_for_inlining (heap, e);
+      }
+    else
+      add_new_indirect_edges_to_heap (heap, e->callee);
+}
+
+
 /* 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.
@@ -964,6 +993,8 @@ cgraph_decide_inlining_of_small_function
 	  if (!cgraph_decide_recursive_inlining (where))
 	    continue;
           update_callee_keys (heap, where, updated_nodes);
+	  if (flag_indirect_inlining)
+	    add_new_indirect_edges_to_heap (heap, where);
 	}
       else
 	{
@@ -979,6 +1010,8 @@ cgraph_decide_inlining_of_small_function
 	    }
 	  callee = edge->callee;
 	  cgraph_mark_inline_edge (edge, true);
+	  if (flag_indirect_inlining)
+	    ipa_propagate_indirect_call_infos (heap, edge);
 	  update_callee_keys (heap, callee, updated_nodes);
 	}
       where = edge->caller;
@@ -1100,6 +1133,8 @@ cgraph_decide_inlining (void)
 				  	   &e->inline_failed))
 	    continue;
 	  cgraph_mark_inline_edge (e, true);
+	  if (flag_indirect_inlining)
+	    ipa_propagate_indirect_call_infos (NULL, e);
 	  if (dump_file)
 	    fprintf (dump_file, 
 		     " Inlined into %s which now has %i insns.\n",
@@ -1121,6 +1156,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 +1679,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
@@ -31,6 +31,7 @@ along with GCC; see the file COPYING3.  
 #include "tree-inline.h"
 #include "flags.h"
 #include "timevar.h"
+#include "fibheap.h"
 #include "flags.h"
 #include "diagnostic.h"
 
@@ -851,6 +852,151 @@ ipa_analyze_params_uses (struct cgraph_n
   info->uses_analysis_done = 1;
 }
 
+/* Updates 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;
+    }
+}
+
+/* Prints out a debug message to file F that we have discovered 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);
+}
+
+/* Updates 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, a new cgraph edge is
+   created for it.  Finally, if HEAP is non-NULL, such new edges are added to
+   the heap through cgraph_consider_new_edge_for_inlining.  */
+static void
+update_call_notes_after_inlining (fibheap_t heap, struct cgraph_edge *cs,
+				  struct cgraph_node *node)
+{
+  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_edge;
+	  tree decl;
+
+	  nt->processed = true;
+	  if (jfunc->type == IPA_CONST_MEMBER_PTR)
+	    decl = jfunc->value.member_cst.pfn;
+	  else
+	    decl = jfunc->value.constant;
+
+	  gcc_assert (DECL_P (decl));
+	  callee = cgraph_node (decl);
+	  if (!callee || !callee->local.inlinable)
+	    continue;
+
+	  if (dump_file)
+	    print_edge_addition_message (dump_file, nt, jfunc, node);
+
+	  new_edge = cgraph_create_edge (node, callee, nt->stmt, nt->count,
+					 nt->frequency, nt->loop_nest);
+	  new_edge->indirect_call = 1;
+	  ipa_check_create_edge_args ();
+	  if (heap)
+	    cgraph_consider_new_edge_for_inlining (heap, new_edge);
+	}
+    }
+}
+
+/* This function recursively traverses subtree of NODE (including node) made of
+   inlined cgraph_edges when CS has been inlined.  It invokes
+   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.  HEAP must be the heap used for decisiding on inlining
+   small functions or NULL.  In the former case, any newly created edges will
+   be added to it immediately.  */
+static void
+propagate_info_to_inlined_callees (fibheap_t heap, struct cgraph_edge *cs,
+				   struct cgraph_node *node)
+{
+  struct cgraph_edge *e;
+
+  update_call_notes_after_inlining (heap, cs, node);
+
+  for (e = node->callees; e; e = e->next_callee)
+    if (!e->inline_failed)
+      propagate_info_to_inlined_callees (heap, cs, e->callee);
+    else
+      update_jump_functions_after_inlining (cs, e);
+}
+
+/* Updates 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.  HEAP must be the heap used for decisiding on
+   inlining small functions or NULL.  In the former case, any newly created
+   edges will be added to it immediately.  */
+void
+ipa_propagate_indirect_call_infos (fibheap_t heap, struct cgraph_edge *cs)
+{
+  propagate_info_to_inlined_callees (heap, cs, cs->callee);
+}
+
 /* 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 "fibheap.h"
 
 /* The following definitions and interfaces are used by
    interprocedural analyses.  */
@@ -128,6 +129,10 @@ struct ipa_param_flags
    are linked in a list.  */
 struct ipa_param_call_note
 {
+  /* 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;
   /* Index of the parameter that is called.  */
   unsigned int formal_id;
   /* Statement that contains the call to the parameter above.  */
@@ -377,6 +382,7 @@ 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 (fibheap_t, struct cgraph_edge *);
 
 /* Debugging interface.  */
 void ipa_print_all_tree_maps (FILE *);
@@ -385,4 +391,8 @@ void ipa_print_all_param_flags (FILE *);
 void ipa_print_node_jump_functions (FILE *f, struct cgraph_node *node);
 void ipa_print_all_jump_functions (FILE * f);
 
+/* From ipa-inline.c */
+void cgraph_consider_new_edge_for_inlining (fibheap_t heap,
+					    struct cgraph_edge *edge);
+
 #endif /* IPA_PROP_H */
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;
Index: iinln/gcc/Makefile.in
===================================================================
--- iinln.orig/gcc/Makefile.in
+++ iinln/gcc/Makefile.in
@@ -838,7 +838,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 $(FIBHEAP_H)
 
 #
 # Now figure out from those variables how to compile and link.
@@ -2529,7 +2529,7 @@ varpool.o : varpool.c $(CONFIG_H) $(SYST
    $(FIBHEAP_H) output.h $(PARAMS_H) $(RTL_H) $(TIMEVAR_H) $(IPA_PROP_H) \
    gt-varpool.h
 ipa.o : ipa.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRAPH_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  $(FIBHEAP_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
 ipa-cp.o : ipa-cp.c $(CONFIG_H) $(SYSTEM_H) coretypes.h  \

--