ipa-cp.c (ipa_value_from_jfunc): Make global.

	* ipa-cp.c (ipa_value_from_jfunc): Make global.
	(ipa_cst_from_jfunc): Remove, use ipa_value_from_jfunc instead.
	(get_indirect_edge_target): Rename, make global.
	(devirtualization_time_bonus, estimate_local_effects,)
	(ipcp_discover_new_direct_edges): Update.
	* ipa-inline-analysis.c (evaluate_conditions_for_edge):
	Generalize to also handle types.  Rename to ...
	(evaluate_properties_for_edge): Use instead of
	evaluate_conditions_for_edge.
	(estimate_edge_devirt_benefit): New function.
	(estimate_calls_size_and_time): Use it.
	(estimate_node_size_and_time, estimate_ipcp_clone_size_and_time,)
	(inline_merge_summary):	Update.
	(do_estimate_edge_time, do_estimate_edge_growth): Update.  Calculate
	parameter information at the call site and pass it on to subroutines.
	* tree-inline.c (estimate_num_insns): Distinguish between direct and
	indirect calls.
	(init_inline_once): Set size and time costs or indirect calls.
	* tree-inline.h (eni_weights): Add indirect_call_cost.

From-SVN: r181377

7 files changed, 189 insertions, 61 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a8292ff..01476a9 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,25 @@
+2011-11-15  Maxim Kuvyrkov  <maxim@codesourcery.com>
+
+	* ipa-cp.c (ipa_value_from_jfunc): Make global.
+	(ipa_cst_from_jfunc): Remove, use ipa_value_from_jfunc instead.
+	(get_indirect_edge_target): Rename, make global.
+	(devirtualization_time_bonus, estimate_local_effects,)
+	(ipcp_discover_new_direct_edges): Update.
+	* ipa-inline-analysis.c (evaluate_conditions_for_edge):
+	Generalize to also handle types.  Rename to ...
+	(evaluate_properties_for_edge): Use instead of
+	evaluate_conditions_for_edge.
+	(estimate_edge_devirt_benefit): New function.
+	(estimate_calls_size_and_time): Use it.
+	(estimate_node_size_and_time, estimate_ipcp_clone_size_and_time,)
+	(inline_merge_summary):	Update.
+	(do_estimate_edge_time, do_estimate_edge_growth): Update.  Calculate
+	parameter information at the call site and pass it on to subroutines.
+	* tree-inline.c (estimate_num_insns): Distinguish between direct and
+	indirect calls.
+	(init_inline_once): Set size and time costs or indirect calls.
+	* tree-inline.h (eni_weights): Add indirect_call_cost.
+
 2011-11-15  Tom de Vries  <tom@codesourcery.com>
 
 	PR tree-optimization/51005
diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
index 45cb00b..10e1834 100644
--- a/gcc/ipa-cp.c
+++ b/gcc/ipa-cp.c
@@ -693,7 +693,7 @@ ipa_value_from_known_type_jfunc (struct ipa_jump_func *jfunc)
    describes the caller node so that pass-through jump functions can be
    evaluated.  */
 
-static tree
+tree
 ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
 {
   if (jfunc->type == IPA_JF_CONST)
@@ -753,21 +753,6 @@ ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
     return NULL_TREE;
 }
 
-/* Determine whether JFUNC evaluates to a constant and if so, return it.
-   Otherwise return NULL. INFO describes the caller node so that pass-through
-   jump functions can be evaluated.  */
-
-tree
-ipa_cst_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
-{
-  tree res = ipa_value_from_jfunc (info, jfunc);
-
-  if (res && TREE_CODE (res) == TREE_BINFO)
-    return NULL_TREE;
-  else
-    return res;
-}
-
 
 /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
    bottom, not containing a variable component and without any known value at
@@ -1112,10 +1097,10 @@ propagate_constants_accross_call (struct cgraph_edge *cs)
    (which can contain both constants and binfos) or KNOWN_BINFOS (which can be
    NULL) return the destination.  */
 
-static tree
-get_indirect_edge_target (struct cgraph_edge *ie,
-			  VEC (tree, heap) *known_vals,
-			  VEC (tree, heap) *known_binfos)
+tree
+ipa_get_indirect_edge_target (struct cgraph_edge *ie,
+			      VEC (tree, heap) *known_vals,
+			      VEC (tree, heap) *known_binfos)
 {
   int param_index = ie->indirect_info->param_index;
   HOST_WIDE_INT token, anc_offset;
@@ -1185,7 +1170,7 @@ devirtualization_time_bonus (struct cgraph_node *node,
       struct inline_summary *isummary;
       tree target;
 
-      target = get_indirect_edge_target (ie, known_csts, known_binfos);
+      target = ipa_get_indirect_edge_target (ie, known_csts, known_binfos);
       if (!target)
 	continue;
 
@@ -1344,7 +1329,8 @@ estimate_local_effects (struct cgraph_node *node)
 
       init_caller_stats (&stats);
       cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false);
-      estimate_ipcp_clone_size_and_time (node, known_csts, &size, &time);
+      estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
+					 &size, &time);
       time -= devirtualization_time_bonus (node, known_csts, known_binfos);
       time -= removable_params_cost;
       size -= stats.n_calls * removable_params_cost;
@@ -1415,7 +1401,8 @@ estimate_local_effects (struct cgraph_node *node)
 	  else
 	    continue;
 
-	  estimate_ipcp_clone_size_and_time (node, known_csts, &size, &time);
+	  estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
+					     &size, &time);
 	  time_benefit = base_time - time
 	    + devirtualization_time_bonus (node, known_csts, known_binfos)
 	    + removable_params_cost + emc;
@@ -1673,7 +1660,7 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node,
       tree target;
 
       next_ie = ie->next_callee;
-      target = get_indirect_edge_target (ie, known_vals, NULL);
+      target = ipa_get_indirect_edge_target (ie, known_vals, NULL);
       if (target)
 	ipa_make_edge_direct_to_target (ie, target);
     }
diff --git a/gcc/ipa-inline-analysis.c b/gcc/ipa-inline-analysis.c
index 91aa612..9ff247b 100644
--- a/gcc/ipa-inline-analysis.c
+++ b/gcc/ipa-inline-analysis.c
@@ -710,15 +710,25 @@ evaluate_conditions_for_known_args (struct cgraph_node *node,
 
 /* Work out what conditions might be true at invocation of E.  */
 
-static clause_t
-evaluate_conditions_for_edge (struct cgraph_edge *e, bool inline_p)
+static void
+evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
+			      clause_t *clause_ptr,
+			      VEC (tree, heap) **known_vals_ptr,
+			      VEC (tree, heap) **known_binfos_ptr)
 {
-  clause_t clause = inline_p ? 0 : 1 << predicate_not_inlined_condition;
   struct cgraph_node *callee = cgraph_function_or_thunk_node (e->callee, NULL);
   struct inline_summary *info = inline_summary (callee);
   int i;
 
-  if (ipa_node_params_vector && info->conds)
+  if (clause_ptr)
+    *clause_ptr = inline_p ? 0 : 1 << predicate_not_inlined_condition;
+  if (known_vals_ptr)
+    *known_vals_ptr = NULL;
+  if (known_binfos_ptr)
+    *known_binfos_ptr = NULL;
+
+  if (ipa_node_params_vector
+      && ((clause_ptr && info->conds) || known_vals_ptr || known_binfos_ptr))
     {
       struct ipa_node_params *parms_info;
       struct ipa_edge_args *args = IPA_EDGE_REF (e);
@@ -731,29 +741,42 @@ evaluate_conditions_for_edge (struct cgraph_edge *e, bool inline_p)
       else
         parms_info = IPA_NODE_REF (e->caller);
 
-      if (count)
-        VEC_safe_grow_cleared (tree, heap, known_vals, count);
+      if (count && (info->conds || known_vals_ptr))
+	VEC_safe_grow_cleared (tree, heap, known_vals, count);
+      if (count && known_binfos_ptr)
+	VEC_safe_grow_cleared (tree, heap, *known_binfos_ptr, count);
+
       for (i = 0; i < count; i++)
 	{
-	  tree cst = ipa_cst_from_jfunc (parms_info,
-					 ipa_get_ith_jump_func (args, i));
+	  tree cst = ipa_value_from_jfunc (parms_info,
+					   ipa_get_ith_jump_func (args, i));
 	  if (cst)
-	    VEC_replace (tree, known_vals, i, cst);
+	    {
+	      if (info->conds && TREE_CODE (cst) != TREE_BINFO)
+		VEC_replace (tree, known_vals, i, cst);
+	      else if (known_binfos_ptr != NULL)
+		VEC_replace (tree, *known_binfos_ptr, i, cst);
+	    }
 	  else if (inline_p
 		   && !VEC_index (inline_param_summary_t,
 				  es->param,
 				  i)->change_prob)
 	    VEC_replace (tree, known_vals, i, error_mark_node);
 	}
-      clause = evaluate_conditions_for_known_args (callee,
-						   inline_p, known_vals);
-      VEC_free (tree, heap, known_vals);
+
+      if (clause_ptr && info->conds)
+	*clause_ptr = evaluate_conditions_for_known_args (callee, inline_p,
+							  known_vals);
+
+      if (known_vals_ptr)
+	*known_vals_ptr = known_vals;
+      else
+	VEC_free (tree, heap, known_vals);
     }
-  else
-    for (i = 0; i < (int)VEC_length (condition, info->conds); i++)
-      clause |= 1 << (i + predicate_first_dynamic_condition);
 
-  return clause;
+  if (clause_ptr && !info->conds)
+    for (i = 0; i < (int)VEC_length (condition, info->conds); i++)
+      *clause_ptr |= 1 << (i + predicate_first_dynamic_condition);
 }
 
 
@@ -2169,11 +2192,71 @@ estimate_edge_size_and_time (struct cgraph_edge *e, int *size, int *time,
 }
 
 
-/* Increase SIZE and TIME for size and time needed to handle all calls in NODE.  */
+/* Estimate benefit devirtualizing indirect edge IE, provided KNOWN_VALS and
+   KNOWN_BINFOS.  */
+
+static void
+estimate_edge_devirt_benefit (struct cgraph_edge *ie,
+			      int *size, int *time, int prob,
+			      VEC (tree, heap) *known_vals,
+			      VEC (tree, heap) *known_binfos)
+{
+  tree target;
+  struct cgraph_node *callee;
+  struct inline_summary *isummary;
+  int edge_size = 0, edge_time = 0;
+
+  if (!known_vals || !known_binfos)
+    return;
+
+  target = ipa_get_indirect_edge_target (ie, known_vals, known_binfos);
+  if (!target)
+    return;
+
+  /* Account for difference in cost between indirect and direct calls.  */
+  *size -= ((eni_size_weights.indirect_call_cost - eni_size_weights.call_cost)
+	    * INLINE_SIZE_SCALE);
+  *time -= ((eni_time_weights.indirect_call_cost - eni_time_weights.call_cost)
+	    * INLINE_TIME_SCALE * prob / REG_BR_PROB_BASE);
+
+  callee = cgraph_get_node (target);
+  if (!callee || !callee->analyzed)
+    return;
+  isummary = inline_summary (callee);
+  if (!isummary->inlinable)
+    return;
+
+  estimate_edge_size_and_time (ie, &edge_size, &edge_time, prob);
+
+  /* Count benefit only from functions that definitely will be inlined
+     if additional context from NODE's caller were available.  */
+  if (edge_size >= isummary->size * INLINE_SIZE_SCALE)
+    {
+      /* Subtract size and time that we added for edge IE.  */
+      *size -= edge_size;
+      *time -= edge_time;
+
+      /* Subtract benefit from inlining devirtualized call.  */
+      *size -= edge_size - isummary->size * INLINE_SIZE_SCALE;
+      *time -= edge_time - (isummary->time * INLINE_TIME_SCALE * prob
+			    / REG_BR_PROB_BASE);
+
+      /* TODO: estimate benefit from optimizing CALLEE's body provided
+	 additional context from IE call site.
+	 For insipiration see ipa-cp.c: devirtualization_time_bonus().  */
+    }
+}
+
+
+/* Increase SIZE and TIME for size and time needed to handle all calls in NODE.
+   POSSIBLE_TRUTHS, KNOWN_VALS and KNOWN_BINFOS describe context of the call
+   site.  */
 
 static void
 estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time,
-			      clause_t possible_truths)
+			      clause_t possible_truths,
+			      VEC (tree, heap) *known_vals,
+			      VEC (tree, heap) *known_binfos)
 {
   struct cgraph_edge *e;
   for (e = node->callees; e; e = e->next_callee)
@@ -2189,25 +2272,32 @@ estimate_calls_size_and_time (struct cgraph_node *node, int *size, int *time,
 	    }
 	  else
 	    estimate_calls_size_and_time (e->callee, size, time,
-					  possible_truths);
+					  possible_truths,
+					  known_vals, known_binfos);
 	}
     }
-  /* TODO: look for devirtualizing oppurtunities.  */
   for (e = node->indirect_calls; e; e = e->next_callee)
     {
       struct inline_edge_summary *es = inline_edge_summary (e);
       if (!es->predicate || evaluate_predicate (es->predicate, possible_truths))
-        estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE);
+	{
+	  estimate_edge_size_and_time (e, size, time, REG_BR_PROB_BASE);
+	  estimate_edge_devirt_benefit (e, size, time, REG_BR_PROB_BASE,
+					known_vals, known_binfos);
+	}
     }
 }
 
 
 /* Estimate size and time needed to execute NODE assuming
-   POSSIBLE_TRUTHS clause. */
+   POSSIBLE_TRUTHS clause, and KNOWN_VALS and KNOWN_BINFOS information
+   about NODE's arguments. */
 
 static void
 estimate_node_size_and_time (struct cgraph_node *node,
 			     clause_t possible_truths,
+			     VEC (tree, heap) *known_vals,
+			     VEC (tree, heap) *known_binfos,
 		       	     int *ret_size, int *ret_time,
 			     VEC (inline_param_summary_t, heap)
 			       *inline_param_summary)
@@ -2258,7 +2348,8 @@ estimate_node_size_and_time (struct cgraph_node *node,
   if (time > MAX_TIME * INLINE_TIME_SCALE)
     time = MAX_TIME * INLINE_TIME_SCALE;
 
-  estimate_calls_size_and_time (node, &size, &time, possible_truths);
+  estimate_calls_size_and_time (node, &size, &time, possible_truths,
+				known_vals, known_binfos);
   time = (time + INLINE_TIME_SCALE / 2) / INLINE_TIME_SCALE;
   size = (size + INLINE_SIZE_SCALE / 2) / INLINE_SIZE_SCALE;
 
@@ -2276,17 +2367,20 @@ estimate_node_size_and_time (struct cgraph_node *node,
 
 /* Estimate size and time needed to execute callee of EDGE assuming that
    parameters known to be constant at caller of EDGE are propagated.
-   KNOWN_VALs is a vector of assumed known constant values for parameters.  */
+   KNOWN_VALS and KNOWN_BINFOS are vectors of assumed known constant values
+   and types for parameters.  */
 
 void
 estimate_ipcp_clone_size_and_time (struct cgraph_node *node,
 				   VEC (tree, heap) *known_vals,
+				   VEC (tree, heap) *known_binfos,
 		                   int *ret_size, int *ret_time)
 {
   clause_t clause;
 
   clause = evaluate_conditions_for_known_args (node, false, known_vals);
-  estimate_node_size_and_time (node, clause, ret_size, ret_time,
+  estimate_node_size_and_time (node, clause, known_vals, known_binfos,
+			       ret_size, ret_time,
 			       NULL);
 }
 
@@ -2542,9 +2636,9 @@ inline_merge_summary (struct cgraph_edge *edge)
       int count = ipa_get_cs_argument_count (args);
       int i;
 
-      clause = evaluate_conditions_for_edge (edge, true);
+      evaluate_properties_for_edge (edge, true, &clause, NULL, NULL);
       if (count)
-        VEC_safe_grow_cleared (int, heap, operand_map, count);
+	VEC_safe_grow_cleared (int, heap, operand_map, count);
       for (i = 0; i < count; i++)
 	{
 	  struct ipa_jump_func *jfunc = ipa_get_ith_jump_func (args, i);
@@ -2588,7 +2682,8 @@ inline_merge_summary (struct cgraph_edge *edge)
   for (i = 0; VEC_iterate (size_time_entry, info->entry, i, e); i++)
     info->size += e->size, info->time += e->time;
   estimate_calls_size_and_time (to, &info->size, &info->time,
-				~(clause_t)(1 << predicate_false_condition));
+				~(clause_t)(1 << predicate_false_condition),
+				NULL, NULL);
 
   inline_update_callee_summaries (edge->callee,
 				  inline_edge_summary (edge)->loop_depth);
@@ -2616,13 +2711,21 @@ do_estimate_edge_time (struct cgraph_edge *edge)
   int time;
   int size;
   gcov_type ret;
+  struct cgraph_node *callee;
+  clause_t clause;
+  VEC (tree, heap) *known_vals;
+  VEC (tree, heap) *known_binfos;
   struct inline_edge_summary *es = inline_edge_summary (edge);
 
+  callee = cgraph_function_or_thunk_node (edge->callee, NULL);
+
   gcc_checking_assert (edge->inline_failed);
-  estimate_node_size_and_time (cgraph_function_or_thunk_node (edge->callee,
-							      NULL),
-			       evaluate_conditions_for_edge (edge, true),
+  evaluate_properties_for_edge (edge, true,
+				&clause, &known_vals, &known_binfos);
+  estimate_node_size_and_time (callee, clause, known_vals, known_binfos,
 			       &size, &time, es->param);
+  VEC_free (tree, heap, known_vals);
+  VEC_free (tree, heap, known_binfos);
 
   ret = (((gcov_type)time
 	   - es->call_stmt_time) * edge->frequency
@@ -2656,6 +2759,9 @@ do_estimate_edge_growth (struct cgraph_edge *edge)
 {
   int size;
   struct cgraph_node *callee;
+  clause_t clause;
+  VEC (tree, heap) *known_vals;
+  VEC (tree, heap) *known_binfos;
 
   /* When we do caching, use do_estimate_edge_time to populate the entry.  */
 
@@ -2668,13 +2774,17 @@ do_estimate_edge_growth (struct cgraph_edge *edge)
       gcc_checking_assert (size);
       return size - (size > 0);
     }
+
   callee = cgraph_function_or_thunk_node (edge->callee, NULL);
 
   /* Early inliner runs without caching, go ahead and do the dirty work.  */
   gcc_checking_assert (edge->inline_failed);
-  estimate_node_size_and_time (callee,
-			       evaluate_conditions_for_edge (edge, true),
+  evaluate_properties_for_edge (edge, true,
+				&clause, &known_vals, &known_binfos);
+  estimate_node_size_and_time (callee, clause, known_vals, known_binfos,
 			       &size, NULL, NULL);
+  VEC_free (tree, heap, known_vals);
+  VEC_free (tree, heap, known_binfos);
   gcc_checking_assert (inline_edge_summary (edge)->call_stmt_size);
   return size - inline_edge_summary (edge)->call_stmt_size;
 }
diff --git a/gcc/ipa-inline.h b/gcc/ipa-inline.h
index 6df7867..a2c6cac 100644
--- a/gcc/ipa-inline.h
+++ b/gcc/ipa-inline.h
@@ -169,6 +169,7 @@ int estimate_time_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 int estimate_size_after_inlining (struct cgraph_node *, struct cgraph_edge *);
 void estimate_ipcp_clone_size_and_time (struct cgraph_node *,
 					VEC (tree, heap) *known_vals,
+					VEC (tree, heap) *known_binfos,
 					int *, int *);
 int do_estimate_growth (struct cgraph_node *);
 void inline_merge_summary (struct cgraph_edge *edge);
diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
index 58caa92..1a609a5 100644
--- a/gcc/ipa-prop.h
+++ b/gcc/ipa-prop.h
@@ -346,6 +346,9 @@ bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
 					VEC (cgraph_edge_p, heap) **new_edges);
 
 /* Indirect edge and binfo processing.  */
+tree ipa_get_indirect_edge_target (struct cgraph_edge *ie,
+				   VEC (tree, heap) *known_csts,
+				   VEC (tree, heap) *known_binfs);
 struct cgraph_edge *ipa_make_edge_direct_to_target (struct cgraph_edge *, tree);
 
 /* Functions related to both.  */
@@ -437,8 +440,8 @@ void ipa_prop_write_jump_functions (cgraph_node_set set);
 void ipa_prop_read_jump_functions (void);
 void ipa_update_after_lto_read (void);
 int ipa_get_param_decl_index (struct ipa_node_params *, tree);
-tree ipa_cst_from_jfunc (struct ipa_node_params *info,
-			 struct ipa_jump_func *jfunc);
+tree ipa_value_from_jfunc (struct ipa_node_params *info,
+			   struct ipa_jump_func *jfunc);
 
 
 /* From tree-sra.c:  */
diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c
index 7daa9d2..2260403 100644
--- a/gcc/tree-inline.c
+++ b/gcc/tree-inline.c
@@ -3521,7 +3521,7 @@ estimate_num_insns (gimple stmt, eni_weights *weights)
     case GIMPLE_CALL:
       {
 	tree decl = gimple_call_fndecl (stmt);
-	struct cgraph_node *node;
+	struct cgraph_node *node = NULL;
 
 	/* Do not special case builtins where we see the body.
 	   This just confuse inliner.  */
@@ -3556,7 +3556,7 @@ estimate_num_insns (gimple stmt, eni_weights *weights)
 	      }
 	  }
 
-	cost = weights->call_cost;
+	cost = node ? weights->call_cost : weights->indirect_call_cost;
 	if (gimple_call_lhs (stmt))
 	  cost += estimate_move_cost (TREE_TYPE (gimple_call_lhs (stmt)));
 	for (i = 0; i < gimple_call_num_args (stmt); i++)
@@ -3674,6 +3674,7 @@ void
 init_inline_once (void)
 {
   eni_size_weights.call_cost = 1;
+  eni_size_weights.indirect_call_cost = 3;
   eni_size_weights.target_builtin_call_cost = 1;
   eni_size_weights.div_mod_cost = 1;
   eni_size_weights.omp_cost = 40;
@@ -3686,6 +3687,7 @@ init_inline_once (void)
      underestimating the cost does less harm than overestimating it, so
      we choose a rather small value here.  */
   eni_time_weights.call_cost = 10;
+  eni_time_weights.indirect_call_cost = 15;
   eni_time_weights.target_builtin_call_cost = 1;
   eni_time_weights.div_mod_cost = 10;
   eni_time_weights.omp_cost = 40;
diff --git a/gcc/tree-inline.h b/gcc/tree-inline.h
index 2aac5f8..ba0b2c4 100644
--- a/gcc/tree-inline.h
+++ b/gcc/tree-inline.h
@@ -135,6 +135,9 @@ typedef struct eni_weights_d
   /* Cost per call.  */
   unsigned call_cost;
 
+  /* Cost per indirect call.  */
+  unsigned indirect_call_cost;
+
   /* Cost per call to a target specific builtin */
   unsigned target_builtin_call_cost;