Re: [tuples, patch 5/7] Formal parameter use analysis

[Martin Jambor <mjambor at suse dot cz>]

Hi,

On Thu, Jul 24, 2008 at 03:02:06PM +0200, Martin Jambor wrote:
> This patch is a tuplified version of an already committed patch in the
> trunk.   The new  functions  in  ipa-cp.c are  of  interest to  tuples
> maintainers, other  than that, I believe  Honza's ACK for  the rest of
> the patch is good for tuples too.

The following version does not suffer from PR 36926.  I have not been
able to test it though.  The change is very small one, as can be seen
from the trunk fix in
http://gcc.gnu.org/ml/gcc-patches/2008-07/msg02014.html.

Thanks,

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

	* cgraphbuild.c (compute_call_stmt_bb_frequency): New function.
	(build_cgraph_edges): Call compute_call_stmt_bb_frequency instead
	of computing the frequency separately.
	(rebuild_cgraph_edges): Call compute_call_stmt_bb_frequency instead
	of computing the frequency separately.
	* ipa-cp.c (ipcp_print_all_structures): Replace a call to 
	ipa_print_all_param_modified with a call to ipa_print_all_param_flags.
	* ipa-prop.c (ipa_get_member_ptr_load_param): New function.
	(ipa_get_stmt_member_ptr_load_param): New function.
	(ipa_is_ssa_with_stmt_def): New function.
	(ipa_note_param_call): New function.
	(ipa_analyze_call_uses): New function.
	(ipa_analyze_stmt_uses): New function.
	(ipa_analyze_params_uses): New function.
	(ipa_free_node_params_substructures): Also free the param_calls linked
	list.
	(ipa_node_duplication_hook): Also duplicate the param_calls linked list.
	(ipa_print_node_param_flags): New function.
	(ipa_print_all_params_modified): Renamed to ipa_print_all_param_flags.
	(ipa_print_all_param_flags): Calls ipa_print_node_param_flags.
	* ipa-prop.h (struct ipa_param_flags): New field called.
	(struct ipa_param_call_note): New structure.
	(struct ipa_node_params): New fields param_calls and
	uses_analysis_done.
	(ipa_is_ith_param_called): New function.
	* ipa-inline.c (inline_indirect_intraprocedural_analysis): Call
	ipa_analyze_params_uses and dump parameter flags.



Index: tinln/gcc/cgraph.h
===================================================================
--- tinln.orig/gcc/cgraph.h
+++ tinln/gcc/cgraph.h
@@ -377,6 +377,7 @@ void cgraph_remove_node_duplication_hook
 
 /* In cgraphbuild.c  */
 unsigned int rebuild_cgraph_edges (void);
+int compute_call_stmt_bb_frequency (basic_block bb);
 
 /* In ipa.c  */
 bool cgraph_remove_unreachable_nodes (bool, FILE *);
Index: tinln/gcc/cgraphbuild.c
===================================================================
--- tinln.orig/gcc/cgraphbuild.c
+++ tinln/gcc/cgraphbuild.c
@@ -105,6 +105,25 @@ initialize_inline_failed (struct cgraph_
     }
 }
 
+/* Computes the frequency of the call statement so that it can be stored in
+   cgraph_edge.  BB is the basic block of the call statement.  */
+int
+compute_call_stmt_bb_frequency (basic_block bb)
+{
+  int entry_freq = ENTRY_BLOCK_PTR->frequency;
+  int freq;
+
+  if (!entry_freq)
+    entry_freq = 1;
+
+  freq = (!bb->frequency && !entry_freq ? CGRAPH_FREQ_BASE
+	      : bb->frequency * CGRAPH_FREQ_BASE / entry_freq);
+  if (freq > CGRAPH_FREQ_MAX)
+    freq = CGRAPH_FREQ_MAX;
+
+  return freq;
+}
+
 /* Create cgraph edges for function calls.
    Also look for functions and variables having addresses taken.  */
 
@@ -116,10 +135,6 @@ build_cgraph_edges (void)
   struct pointer_set_t *visited_nodes = pointer_set_create ();
   gimple_stmt_iterator gsi;
   tree step;
-  int entry_freq = ENTRY_BLOCK_PTR->frequency;
-
-  if (!entry_freq)
-    entry_freq = 1;
 
   /* Create the callgraph edges and record the nodes referenced by the function.
      body.  */
@@ -133,12 +148,8 @@ build_cgraph_edges (void)
 	  {
 	    size_t i;
 	    size_t n = gimple_call_num_args (stmt);
-	    int freq = (!bb->frequency && !entry_freq ? CGRAPH_FREQ_BASE
-			: bb->frequency * CGRAPH_FREQ_BASE / entry_freq);
-	    if (freq > CGRAPH_FREQ_MAX)
-	      freq = CGRAPH_FREQ_MAX;
 	    cgraph_create_edge (node, cgraph_node (decl), stmt,
-				bb->count, freq,
+				bb->count, compute_call_stmt_bb_frequency (bb),
 				bb->loop_depth);
 	    for (i = 0; i < n; i++)
 	      walk_tree (gimple_call_arg_ptr (stmt, i), record_reference,
@@ -232,10 +243,6 @@ rebuild_cgraph_edges (void)
   basic_block bb;
   struct cgraph_node *node = cgraph_node (current_function_decl);
   gimple_stmt_iterator gsi;
-  int entry_freq = ENTRY_BLOCK_PTR->frequency;
-
-  if (!entry_freq)
-    entry_freq = 1;
 
   cgraph_node_remove_callees (node);
 
@@ -248,14 +255,10 @@ rebuild_cgraph_edges (void)
 	tree decl;
 
 	if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
-	  {
-	    int freq = (!bb->frequency && !entry_freq ? CGRAPH_FREQ_BASE
-			: bb->frequency * CGRAPH_FREQ_BASE / entry_freq);
-	    if (freq > CGRAPH_FREQ_MAX)
-	      freq = CGRAPH_FREQ_MAX;
-	    cgraph_create_edge (node, cgraph_node (decl), stmt,
-				bb->count, freq, bb->loop_depth);
-	   }
+	  cgraph_create_edge (node, cgraph_node (decl), stmt,
+			      bb->count, compute_call_stmt_bb_frequency (bb),
+			      bb->loop_depth);
+
       }
   initialize_inline_failed (node);
   gcc_assert (!node->global.inlined_to);
Index: tinln/gcc/ipa-cp.c
===================================================================
--- tinln.orig/gcc/ipa-cp.c
+++ tinln/gcc/ipa-cp.c
@@ -709,7 +709,7 @@ ipcp_print_all_structures (FILE * f)
   ipcp_print_all_lattices (f);
   ipcp_function_scale_print (f);
   ipa_print_all_tree_maps (f);
-  ipa_print_all_params_modified (f);
+  ipa_print_all_param_flags (f);
   ipa_print_all_jump_functions (f);
 }
 
Index: tinln/gcc/ipa-prop.c
===================================================================
--- tinln.orig/gcc/ipa-prop.c
+++ tinln/gcc/ipa-prop.c
@@ -573,6 +573,286 @@ ipa_compute_jump_functions (struct cgrap
   compute_cst_member_ptr_arguments (arguments->jump_functions, call);
 }
 
+/* If RHS looks like a rhs of a statement loading pfn from a member pointer
+   formal parameter, return the parameter, otherwise return NULL.  */
+static tree
+ipa_get_member_ptr_load_param (tree rhs)
+{
+  tree rec, fld;
+  tree ptr_field;
+
+  if (TREE_CODE (rhs) != COMPONENT_REF)
+    return NULL_TREE;
+
+  rec = TREE_OPERAND (rhs, 0);
+  if (TREE_CODE (rec) != PARM_DECL
+      || !type_like_member_ptr_p (TREE_TYPE (rec), &ptr_field, NULL))
+    return NULL_TREE;
+
+  fld = TREE_OPERAND (rhs, 1);
+  if (fld == ptr_field)
+    return rec;
+  else
+    return NULL_TREE;
+}
+
+/* If STMT looks like a statement loading a value from a member pointer formal
+   parameter, this function retuns that parameter.  */
+static tree
+ipa_get_stmt_member_ptr_load_param (gimple stmt)
+{
+  tree rhs;
+
+  if (!is_gimple_assign (stmt) || gimple_num_ops (stmt) != 2)
+    return NULL_TREE;
+
+  rhs = gimple_assign_rhs1 (stmt);
+  return ipa_get_member_ptr_load_param (rhs);
+}
+
+/* Returns true iff T is an SSA_NAME defined by a statement.  */
+static bool
+ipa_is_ssa_with_stmt_def (tree t)
+{
+  if (TREE_CODE (t) == SSA_NAME
+      && !SSA_NAME_IS_DEFAULT_DEF (t))
+    return true;
+  else
+    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.  */
+static void
+ipa_note_param_call (struct ipa_node_params *info, int formal_id,
+		     gimple stmt)
+{
+  struct ipa_param_call_note *note;
+  basic_block bb = gimple_bb (stmt);
+
+  info->param_flags[formal_id].called = 1;
+
+  note = XCNEW (struct ipa_param_call_note);
+  note->formal_id = formal_id;
+  note->stmt = stmt;
+  note->count = bb->count;
+  note->frequency = compute_call_stmt_bb_frequency (bb);
+
+  note->next = info->param_calls;
+  info->param_calls = note;
+
+  return;
+}
+
+/* Analyze the CALL and examine uses of formal parameters of the caller
+   (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:
+
+     <bb 2>:
+       f$__delta_5 = f.__delta;
+       f$__pfn_24 = f.__pfn;
+       D.2496_3 = (int) f$__pfn_24;
+       D.2497_4 = D.2496_3 & 1;
+       if (D.2497_4 != 0)
+         goto <bb 3>;
+       else
+         goto <bb 4>;
+
+     <bb 3>:
+       D.2500_7 = (unsigned int) f$__delta_5;
+       D.2501_8 = &S + D.2500_7;
+       D.2502_9 = (int (*__vtbl_ptr_type) (void) * *) D.2501_8;
+       D.2503_10 = *D.2502_9;
+       D.2504_12 = f$__pfn_24 + -1;
+       D.2505_13 = (unsigned int) D.2504_12;
+       D.2506_14 = D.2503_10 + D.2505_13;
+       D.2507_15 = *D.2506_14;
+       iftmp.11_16 = (String:: *) D.2507_15;
+
+     <bb 4>:
+       # iftmp.11_1 = PHI <iftmp.11_16(3), f$__pfn_24(2)>
+       D.2500_19 = (unsigned int) f$__delta_5;
+       D.2508_20 = &S + D.2500_19;
+       D.2493_21 = iftmp.11_1 (D.2508_20, 4);
+
+   Such patterns are results of simple calls to a member pointer:
+
+     int doprinting (int (MyString::* f)(int) const)
+     {
+       MyString S ("somestring");
+
+       return (S.*f)(4);
+     }
+*/
+
+static void
+ipa_analyze_call_uses (struct ipa_node_params *info, gimple call)
+{
+  tree target = gimple_call_fn (call);
+  gimple def;
+  tree var;
+  tree n1, n2;
+  gimple d1, d2;
+  tree rec, rec2, cond;
+  gimple branch;
+  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 */
+      index = ipa_get_param_decl_index (info, var);
+      if (index >= 0)
+	ipa_note_param_call (info, index, call);
+      return;
+    }
+
+  /* Now we need to try to match the complex pattern of calling a member
+     pointer. */
+
+  if (!POINTER_TYPE_P (TREE_TYPE (target))
+      || TREE_CODE (TREE_TYPE (TREE_TYPE (target))) != METHOD_TYPE)
+    return;
+
+  def = SSA_NAME_DEF_STMT (target);
+  if (gimple_code (def) != GIMPLE_PHI)
+    return;
+
+  if (gimple_phi_num_args (def) != 2)
+    return;
+
+  /* First, we need to check whether one of these is a load from a member
+     pointer that is a parameter to this function. */
+  n1 = PHI_ARG_DEF (def, 0);
+  n2 = PHI_ARG_DEF (def, 1);
+  if (!ipa_is_ssa_with_stmt_def (n1) || !ipa_is_ssa_with_stmt_def (n2))
+    return;
+  d1 = SSA_NAME_DEF_STMT (n1);
+  d2 = SSA_NAME_DEF_STMT (n2);
+
+  if ((rec = ipa_get_stmt_member_ptr_load_param (d1)))
+    {
+      if (ipa_get_stmt_member_ptr_load_param (d2))
+	return;
+
+      bb = gimple_bb (d1);
+      virt_bb = gimple_bb (d2);
+    }
+  else if ((rec = ipa_get_stmt_member_ptr_load_param (d2)))
+    {
+      bb = gimple_bb (d2);
+      virt_bb = gimple_bb (d1);
+    }
+  else
+    return;
+
+  /* Second, we need to check that the basic blocks are laid out in the way
+     corresponding to the pattern. */
+
+  join = gimple_bb (def);
+  if (!single_pred_p (virt_bb) || !single_succ_p (virt_bb)
+      || single_pred (virt_bb) != bb
+      || single_succ (virt_bb) != join)
+    return;
+
+  /* Third, let's see that the branching is done depending on the least
+     significant bit of the pfn. */
+
+  branch = last_stmt (bb);
+  if (gimple_code (branch) != GIMPLE_COND)
+    return;
+
+  if (gimple_cond_code (branch) != NE_EXPR
+      || !integer_zerop (gimple_cond_rhs (branch)))
+    return;
+
+  cond = gimple_cond_lhs (branch);
+  if (!ipa_is_ssa_with_stmt_def (cond))
+    return;
+
+  def = SSA_NAME_DEF_STMT (cond);
+  if (!is_gimple_assign (def) || gimple_num_ops (def) != 3
+      || gimple_assign_rhs_code (def) != BIT_AND_EXPR
+      || !integer_onep (gimple_assign_rhs2 (def)))
+    return;
+
+  cond = gimple_assign_rhs1 (def);
+  if (!ipa_is_ssa_with_stmt_def (cond))
+    return;
+
+  def = SSA_NAME_DEF_STMT (cond);
+
+  if (is_gimple_assign (def) && gimple_num_ops (def) == 2
+      && gimple_assign_rhs_code (def) == NOP_EXPR)
+    {
+      cond = gimple_assign_rhs1 (def);
+      if (!ipa_is_ssa_with_stmt_def (cond))
+	return;
+      def = SSA_NAME_DEF_STMT (cond);
+    }
+
+  rec2 = ipa_get_stmt_member_ptr_load_param (def);
+  if (rec != rec2)
+    return;
+
+  index = ipa_get_param_decl_index (info, rec);
+  if (index >= 0 && !ipa_is_ith_param_modified (info, index))
+    ipa_note_param_call (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.  */
+static void
+ipa_analyze_stmt_uses (struct ipa_node_params *info, gimple stmt)
+{
+  if (is_gimple_call (stmt))
+    ipa_analyze_call_uses (info, stmt);
+}
+
+/* Scan the function body of NODE and inspect the uses of formal parameters.
+   Store the findings in various structures of the associated ipa_node_params
+   structure, such as parameter flags, notes etc.  */
+void
+ipa_analyze_params_uses (struct cgraph_node *node)
+{
+  tree decl = node->decl;
+  basic_block bb;
+  struct function *func;
+  gimple_stmt_iterator gsi;
+  struct ipa_node_params *info = IPA_NODE_REF (node);
+
+  if (ipa_get_param_count (info) == 0 || info->uses_analysis_done)
+    return;
+  if (!info->param_flags)
+    info->param_flags = XCNEWVEC (struct ipa_param_flags,
+				  ipa_get_param_count (info));
+
+  func = DECL_STRUCT_FUNCTION (decl);
+  FOR_EACH_BB_FN (bb, func)
+    {
+      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gimple stmt = gsi_stmt (gsi);
+	  ipa_analyze_stmt_uses (info, stmt);
+	}
+    }
+
+  info->uses_analysis_done = 1;
+}
+
 /* Frees all dynamically allocated structures that the argument info points
    to.  */
 void
@@ -612,6 +892,13 @@ ipa_free_node_params_substructures (stru
   if (info->param_flags)
     free (info->param_flags);
 
+  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));
 }
 
@@ -689,6 +976,7 @@ ipa_node_duplication_hook (struct cgraph
 			   void *data)
 {
   struct ipa_node_params *old_info, *new_info;
+  struct ipa_param_call_note *note;
   int param_count;
 
   ipa_check_create_node_params ();
@@ -709,6 +997,17 @@ ipa_node_duplication_hook (struct cgraph
   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;
+    }
+
   data = data; 			/* Suppressing compiler warning.  */
 }
 
@@ -797,33 +1096,37 @@ ipa_print_all_tree_maps (FILE * f)
     }
 }
 
-/* Print modified_flags data structures of all functions in the
-   callgraph to F.  */
+/* Print param_flags data structures of the NODE to F.  */
 void
-ipa_print_all_params_modified (FILE * f)
+ipa_print_node_param_flags (FILE * f, struct cgraph_node *node)
 {
   int i, count;
-  bool temp;
-  struct cgraph_node *node;
+  struct ipa_node_params *info;
 
-  fprintf (f, "\nMODIFY PRINT\n");
-  for (node = cgraph_nodes; node; node = node->next)
+  if (!node->analyzed)
+    return;
+  info = IPA_NODE_REF (node);
+  fprintf (f, "PARAM FLAGS of function  %s: \n", cgraph_node_name (node));
+  count = ipa_get_param_count (info);
+  for (i = 0; i < count; i++)
     {
-      struct ipa_node_params *info;
-
-      if (!node->analyzed)
-	continue;
-      info = IPA_NODE_REF (node);
-      fprintf (f, "function  %s :: \n", cgraph_node_name (node));
-      count = ipa_get_param_count (info);
-      for (i = 0; i < count; i++)
-	{
-	  temp = info->param_flags[i].modified;
-	  if (temp)
-	    fprintf (f, " param [%d] true \n", i);
-	  else
-	    fprintf (f, " param [%d] false \n", i);
-	}
+      fprintf (f, "   param [%d]", i);
+      if (ipa_is_ith_param_modified (info, i))
+	fprintf (f, " modified");
+      if (ipa_is_ith_param_called (info, i))
+	fprintf (f, " called");
+      fprintf (f, "\n");
     }
 }
 
+/* Print param_flags data structures of all functions in the
+   callgraph to F.  */
+void
+ipa_print_all_param_flags (FILE * f)
+{
+  struct cgraph_node *node;
+
+  fprintf (f, "\nIPA PARAM FLAGS DUMP\n");
+  for (node = cgraph_nodes; node; node = node->next)
+    ipa_print_node_param_flags (f, node);
+}
Index: tinln/gcc/ipa-prop.h
===================================================================
--- tinln.orig/gcc/ipa-prop.h
+++ tinln/gcc/ipa-prop.h
@@ -119,13 +119,34 @@ struct ipa_param_flags
 {
   /* 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;
+};
+
+/* 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
+{
+  /* Index of the parameter that is called.  */
+  unsigned int formal_id;
+  /* Statement that contains the call to the parameter above.  */
+  gimple stmt;
+  /* Expected number of executions: calculated in profile.c.  */
+  gcov_type count;
+  /* 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.  */
+  int loop_nest;
 
+  /* Linked list's next */
+  struct ipa_param_call_note *next;
 };
 
 /* ipa_node_params stores information related to formal parameters of functions
    and some other information for interprocedural passes that operate on
    parameters (such as ipa-cp).  */
-
 struct ipa_node_params
 {
   /* Number of formal parameters of this function.  When set to 0,
@@ -138,6 +159,8 @@ struct ipa_node_params
   tree *param_decls;
   /* Various flags describing individual parameters.  */
   struct ipa_param_flags *param_flags;
+  /* 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;
@@ -153,6 +176,8 @@ struct ipa_node_params
   unsigned called_with_var_arguments : 1;
   /* Whether the modification analysis has already been performed. */
   unsigned modification_analysis_done : 1;
+  /* Whether the param uses analysis has already been performed.  */
+  unsigned uses_analysis_done : 1;
 };
 
 /* ipa_node_params access functions.  Please use these to access fields that
@@ -190,6 +215,15 @@ ipa_is_ith_param_modified (struct ipa_no
   return info->param_flags[i].modified;
 }
 
+/* Returns the called flag corresponding o the ith paramterer.  Note 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_ith_param_called (struct ipa_node_params *info, int i)
+{
+  return info->param_flags[i].called;
+}
+
 /* Flag this node as having callers with variable number of arguments.  */
 static inline void
 ipa_set_called_with_variable_arg (struct ipa_node_params *info)
@@ -342,10 +376,12 @@ void ipa_count_arguments (struct cgraph_
 void ipa_count_formal_params (struct cgraph_node *);
 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 *);
 
 /* Debugging interface.  */
 void ipa_print_all_tree_maps (FILE *);
-void ipa_print_all_params_modified (FILE *);
+void ipa_print_node_param_flags (FILE * f, struct cgraph_node *node);
+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);
 
Index: tinln/gcc/ipa-inline.c
===================================================================
--- tinln.orig/gcc/ipa-inline.c
+++ tinln/gcc/ipa-inline.c
@@ -1594,6 +1594,10 @@ inline_indirect_intraprocedural_analysis
   ipa_count_formal_params (node);
   ipa_create_param_decls_array (node);
   ipa_detect_param_modifications (node);
+  ipa_analyze_params_uses (node);
+
+  if (dump_file)
+    ipa_print_node_param_flags (dump_file, node);
 
   for (cs = node->callees; cs; cs = cs->next_callee)
     {