Patch by Tomas Bily <tbily@suse.cz>

        * cgraphunit.c (cgraph_finalize_function): Updating of pid
        * tree-profile.c:
        (tree_init_ic_make_global_vars): New function
        (tree_init_edge_profiler): call of tree_init_ic_make_global_vars
        (tree_gen_ic_profiler): New function
        (tree_gen_ic_func_profiler): New function
        (tree_profiling): Added calling of tree_gen_ic_func_profiler
        (tree_profile_hooks): Added hook for indirec/virtual calls
        * value-prof.c (tree_find_values_to_profile): New case for
        indirect calls
        (tree_values_to_profile): Call for determining indirect/virtual
        counters
        (tree_indirect_call_to_profile): New function
        (tree_ic_transform): New function
        (tree_ic): New function
        (find_func_by_pid): New function
        (init_pid_map): New function
        (tree_value_profile_transformations): Added check for
        indirect/virtual call transformation
        * value-prof.h (enum hist_type): New counter type for
        indirect/virtual calls
        (profile_hooks): Added new hook for profiling indirect/virtual
        calls
        * profile.c (instrument_values): New case for indirect/virtual
        call added
        * gcov-io.h (GCOV_LAST_VALUE_COUNTER): Changed to 6
        (GCOV_COUNTER_V_INDIR): New counter type
        (GCOV_COUNTER_NAMES): New name of counter "indirect" added
        (GCOV_MERGE_FUNCTIONS): New merge function for indirect/virtual
        call added
        * cgraph.c: Definition of cgraph_max_pid
        (cgraph_create_node): Default init of pid attribute
        * cgraph.h: Declaration of cgraph_max_pid
        (struct cgraph_node): Added pid attribute
        * libgcov.c (__gcov_indirect_call_profiler): New function
	(__gcov_one_value_profiler_body): New function
	(__gcov_one_value_profiler): Body was moved to
	__gcov_one_value_profiler_body and calls it

	gcc.dg/tree-prof/indir-call-prof.c: New.
	g++.dg/dg.exp: Add tree-prof subdirectory.
	g++.dg/tree-prof/indir-call-prof.C: New.
	g++.dg/tree-prof/tree-prof.exp: New.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@120975 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 250 insertions, 1 deletions

diff --git a/gcc/value-prof.c b/gcc/value-prof.c
index 2b2bb1b6c1e..f23fd68dd6f 100644
--- a/gcc/value-prof.c
+++ b/gcc/value-prof.c
@@ -40,6 +40,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "coverage.h"
 #include "tree.h"
 #include "gcov-io.h"
+#include "cgraph.h"
 #include "timevar.h"
 #include "tree-pass.h"
 #include "toplev.h"
@@ -60,6 +61,11 @@ static struct value_prof_hooks *value_prof_hooks;
       FIXME: This transformation was removed together with RTL based value
       profiling.
 
+   3) Indirect/virtual call specialization. If we can determine most
+      common function callee in indirect/virtual call. We can use this
+      information to improve code effectivity (espetialy info for
+      inliner).
+
    Every such optimization should add its requirements for profiled values to
    insn_values_to_profile function.  This function is called from branch_prob
    in profile.c and the requested values are instrumented by it in the first
@@ -81,6 +87,7 @@ static bool tree_divmod_fixed_value_transform (tree);
 static bool tree_mod_pow2_value_transform (tree);
 static bool tree_mod_subtract_transform (tree);
 static bool tree_stringops_transform (block_stmt_iterator *);
+static bool tree_ic_transform (tree);
 
 /* Allocate histogram value.  */
 
@@ -254,6 +261,19 @@ dump_histogram_value (FILE *dump_file, histogram_value hist)
 	}
       fprintf (dump_file, ".\n");
       break;
+    case HIST_TYPE_INDIR_CALL:
+      fprintf (dump_file, "Indirect call ");
+      if (hist->hvalue.counters)
+	{
+	   fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
+		    " match:"HOST_WIDEST_INT_PRINT_DEC
+		    " all:"HOST_WIDEST_INT_PRINT_DEC,
+		    (HOST_WIDEST_INT) hist->hvalue.counters[0],
+		    (HOST_WIDEST_INT) hist->hvalue.counters[1],
+		    (HOST_WIDEST_INT) hist->hvalue.counters[2]);
+	}
+      fprintf (dump_file, ".\n");
+      break;
    }
 }
 
@@ -432,7 +452,8 @@ tree_value_profile_transformations (void)
 	      && (tree_mod_subtract_transform (stmt)
 		  || tree_divmod_fixed_value_transform (stmt)
 		  || tree_mod_pow2_value_transform (stmt)
-		  || tree_stringops_transform (&bsi)))
+		  || tree_stringops_transform (&bsi)
+		  || tree_ic_transform (stmt)))
 	    {
 	      stmt = bsi_stmt (bsi);
 	      changed = true;
@@ -967,6 +988,201 @@ tree_mod_subtract_transform (tree stmt)
   return true;
 }
 
+static struct cgraph_node** pid_map = NULL;
+
+/* Initialize map of pids (pid -> cgraph node) */
+
+static void 
+init_pid_map (void)
+{
+  struct cgraph_node *n;
+
+  if (pid_map != NULL)
+    return;
+
+  pid_map 
+    = (struct cgraph_node**) xmalloc (sizeof (struct cgraph_node*) * cgraph_max_pid);
+
+  for (n = cgraph_nodes; n; n = n->next)
+    {
+      if (n->pid != -1)
+	pid_map [n->pid] = n;
+    }
+}
+
+/* Return cgraph node for function with pid */
+
+static inline struct cgraph_node*
+find_func_by_pid (int	pid)
+{
+  init_pid_map ();
+
+  return pid_map [pid];
+}
+
+/* Do transformation
+
+  if (actual_callee_addres == addres_of_most_common_function/method)
+    do direct call
+  else
+    old call
+ */
+
+static tree
+tree_ic (tree stmt, tree call, struct cgraph_node* direct_call, 
+	 int prob, gcov_type count, gcov_type all)
+{
+  tree stmt1, stmt2, stmt3;
+  tree tmp1, tmpv;
+  tree label_decl1 = create_artificial_label ();
+  tree label_decl2 = create_artificial_label ();
+  tree label1, label2;
+  tree bb1end, bb2end, bb3end;
+  tree new_call;
+  basic_block bb, bb2, bb3, bb4;
+  tree optype = build_pointer_type (void_type_node);
+  edge e12, e13, e23, e24, e34;
+  block_stmt_iterator bsi;
+  int region;
+
+  bb = bb_for_stmt (stmt);
+  bsi = bsi_for_stmt (stmt);
+
+  tmpv = create_tmp_var (optype, "PROF");
+  tmp1 = create_tmp_var (optype, "PROF");
+  stmt1 = build2 (GIMPLE_MODIFY_STMT, optype, tmpv, 
+		  unshare_expr (TREE_OPERAND (call, 0)));
+  stmt2 = build2 (GIMPLE_MODIFY_STMT, optype, tmp1, 
+		  fold_convert (optype, build_addr (direct_call->decl, 
+						    current_function_decl)));
+  stmt3 = build3 (COND_EXPR, void_type_node,
+		  build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
+		  build1 (GOTO_EXPR, void_type_node, label_decl2),
+		  build1 (GOTO_EXPR, void_type_node, label_decl1));
+  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
+  bb1end = stmt3;
+
+  label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
+  stmt1 = unshare_expr (stmt);
+  new_call = get_call_expr_in (stmt1);
+  TREE_OPERAND (new_call, 0) = build_addr (direct_call->decl, 
+					   current_function_decl);
+  bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
+  bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
+  bb2end = stmt1;
+
+  label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
+  bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
+  bb3end = stmt;
+
+  /* Fix CFG. */
+  /* Edge e23 connects bb2 to bb3, etc. */
+  e12 = split_block (bb, bb1end);
+  bb2 = e12->dest;
+  bb2->count = count;
+  e23 = split_block (bb2, bb2end);
+  bb3 = e23->dest;
+  bb3->count = all - count;
+  e34 = split_block (bb3, bb3end);
+  bb4 = e34->dest;
+  bb4->count = all;
+
+  e12->flags &= ~EDGE_FALLTHRU;
+  e12->flags |= EDGE_FALSE_VALUE;
+  e12->probability = prob;
+  e12->count = count;
+
+  e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
+  e13->probability = REG_BR_PROB_BASE - prob;
+  e13->count = all - count;
+
+  remove_edge (e23);
+  
+  e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
+  e24->probability = REG_BR_PROB_BASE;
+  e24->count = count;
+  e34->probability = REG_BR_PROB_BASE;
+  e34->count = all - count;
+
+  /* Fix eh edges */
+  region = lookup_stmt_eh_region (stmt);
+  if (region >=0 && tree_could_throw_p (stmt1))
+    {
+      add_stmt_to_eh_region (stmt1, region);
+      make_eh_edges (stmt1);
+    }
+
+  if (region >=0 && tree_could_throw_p (stmt))
+    {
+      tree_purge_dead_eh_edges (bb4);
+      make_eh_edges (stmt);
+    }
+
+  return stmt1;
+}
+
+/*
+  For every checked indirect/virtual call determine if most common pid of
+  function/class method has probability more than 50%. If yes modify code of
+  this call to:
+ */
+
+static bool
+tree_ic_transform (tree stmt)
+{
+  histogram_value histogram;
+  gcov_type val, count, all;
+  int prob;
+  tree call, callee, modify;
+  struct cgraph_node *direct_call;
+  
+  call = get_call_expr_in (stmt);
+
+  if (!call || TREE_CODE (call) != CALL_EXPR)
+    return false;
+
+  callee = TREE_OPERAND (call, 0);
+
+  if (TREE_CODE (callee) == ADDR_EXPR)
+    return false;
+
+  histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
+  if (!histogram)
+    return false;
+
+  val = histogram->hvalue.counters [0];
+  count = histogram->hvalue.counters [1];
+  all = histogram->hvalue.counters [2];
+  gimple_remove_histogram_value (cfun, stmt, histogram);
+
+  if (4 * count <= 3 * all)
+    return false;
+
+  prob = (count * REG_BR_PROB_BASE + all / 2) / all;
+  direct_call = find_func_by_pid ((int)val);
+
+  if (direct_call == NULL)
+    return false;
+
+  modify = tree_ic (stmt, call, direct_call, prob, count, all);
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "Indirect call -> direct call ");
+      print_generic_expr (dump_file, call, TDF_SLIM);
+      fprintf (dump_file, "=> ");
+      print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
+      fprintf (dump_file, " transformation on insn ");
+      print_generic_stmt (dump_file, stmt, TDF_SLIM);
+      fprintf (dump_file, " to ");
+      print_generic_stmt (dump_file, modify, TDF_SLIM);
+    }
+
+  return true;
+}
+
 /* Return true if the stringop FNDECL with ARGLIST shall be profiled.  */
 static bool
 interesting_stringop_to_profile_p (tree fndecl, tree arglist)
@@ -1260,6 +1476,34 @@ tree_divmod_values_to_profile (tree stmt, histogram_values *values)
     }
 }
 
+/* Find calls inside STMT for that we want to measure histograms for 
+   indirect/virtual call optimization. */ 
+
+static void
+tree_indirect_call_to_profile (tree stmt, histogram_values *values)
+{
+  tree			call;
+  tree			callee;
+
+  call = get_call_expr_in (stmt);
+
+  if (!call || TREE_CODE (call) != CALL_EXPR)
+    return;
+
+  callee = TREE_OPERAND (call, 0);
+  
+  if (TREE_CODE (callee) == ADDR_EXPR)
+    return;
+
+  VEC_reserve (histogram_value, heap, *values, 3);
+
+  VEC_quick_push (histogram_value, *values, 
+		  gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
+						stmt, callee));
+
+  return;
+}
+
 /* Find values inside STMT for that we want to measure histograms for
    string operations.  */
 static void
@@ -1303,6 +1547,7 @@ tree_values_to_profile (tree stmt, histogram_values *values)
     {
       tree_divmod_values_to_profile (stmt, values);
       tree_stringops_values_to_profile (stmt, values);
+      tree_indirect_call_to_profile (stmt, values);
     }
 }
 
@@ -1339,6 +1584,10 @@ tree_find_values_to_profile (histogram_values *values)
 	  hist->n_counters = 4;
 	  break;
 
+ 	case HIST_TYPE_INDIR_CALL:
+ 	  hist->n_counters = 3;
+	  break;
+
 	default:
 	  gcc_unreachable ();
 	}