[WPA PATCH 2/5] Enhanced jump functions

[Martin Jambor <mjambor at suse dot cz>]

This patch extends pass-through functions to allow one binary
operation with the incoming parameter being first and a constant
(is_gimple_ip_invariant) the second argument.  It also adds new type
of jump functions for locating fields representing ancestors within
objects which look like:

&this->ancestor_1->ancestor_2->...->ancestor_n.

I have changed the parameter indices to int from unsigned int because
there was no real reason for it, I personally do not like the stupid
typecasts-to-avoid-warnings and I might use negative values in the
future to denote that the incoming parameter should be the second
parameter of the operation.

Thanks,

Martin



2009-08-05  Martin Jambor  <mjambor@suse.cz>

	* ipa-prop.h (enum jump_func_type): New value IPA_JF_ANCESTOR, changed
	comments.
	(struct ipa_pass_through_data): New type.
	(struct ipa_ancestor_jf_data): New type.
	(union jump_func_value): Removed field formal_id, added fields
	pass_through and ancestor.
	(struct ipa_param_call_note): Changed type of formal_id to int from
	unsigned.
	* ipa-prop.c (ipa_print_node_jump_functions): Print pass through with
	operations jump functions and ancestor jump functions.
	(compute_complex_pass_through): New function.
	(compute_scalar_jump_functions): Call compute_complex_pass_through,
	reflect changes in the jump function strucutre.
	(update_jump_functions_after_inlining): Ignore complex pass-through
	and ancestor jump functions.
	* ipa-cp.c (ipcp_lattice_from_jfunc): Added support for ancestor and
	pass-through with operation jump functions.


Index: icln/gcc/ipa-cp.c
===================================================================
--- icln.orig/gcc/ipa-cp.c
+++ icln/gcc/ipa-cp.c
@@ -290,10 +290,45 @@ ipcp_lattice_from_jfunc (struct ipa_node
   else if (jfunc->type == IPA_JF_PASS_THROUGH)
     {
       struct ipcp_lattice *caller_lat;
+      tree cst;
 
-      caller_lat = ipcp_get_lattice (info, jfunc->value.formal_id);
+      caller_lat = ipcp_get_lattice (info, jfunc->value.pass_through.formal_id);
       lat->type = caller_lat->type;
-      lat->constant = caller_lat->constant;
+      if (caller_lat->type != IPA_CONST_VALUE)
+	return;
+      cst = caller_lat->constant;
+
+      /* !!! Remove this assert after testing.  */
+      gcc_assert (is_gimple_ip_invariant (cst));
+      if (jfunc->value.pass_through.operation != NOP_EXPR)
+	cst = fold_build2 (jfunc->value.pass_through.operation,
+			   TREE_TYPE (cst), cst,
+			   jfunc->value.pass_through.operand);
+      gcc_assert (is_gimple_ip_invariant (cst));
+      lat->constant = cst;
+    }
+  else if (jfunc->type == IPA_JF_ANCESTOR)
+    {
+      struct ipcp_lattice *caller_lat;
+      tree t;
+      bool ok;
+
+      caller_lat = ipcp_get_lattice (info, jfunc->value.ancestor.formal_id);
+      lat->type = caller_lat->type;
+      if (caller_lat->type != IPA_CONST_VALUE)
+	return;
+      if (TREE_CODE (caller_lat->constant) != ADDR_EXPR)
+	{
+	  /* This can happen when the constant is a NULL pointer.  */
+	  lat->type = IPA_BOTTOM;
+	  return;
+	}
+      t = TREE_OPERAND (caller_lat->constant, 0);
+      ok = build_ref_for_offset (&t, TREE_TYPE (t),
+				 jfunc->value.ancestor.offset,
+				 jfunc->value.ancestor.type, false);
+      gcc_assert (ok);
+      lat->constant = build_fold_addr_expr (t);
     }
   else
     lat->type = IPA_BOTTOM;
Index: icln/gcc/ipa-prop.c
===================================================================
--- icln.orig/gcc/ipa-prop.c
+++ icln/gcc/ipa-prop.c
@@ -293,8 +293,22 @@ ipa_print_node_jump_functions (FILE *f,
 	  else if (type == IPA_JF_PASS_THROUGH)
  	    {
 	      fprintf (f, "PASS THROUGH: ");
-	      fprintf (f, "%d\n", jump_func->value.formal_id);
+	      fprintf (f, "%d, op %s ",
+		       jump_func->value.pass_through.formal_id,
+		       tree_code_name[(int)
+				      jump_func->value.pass_through.operation]);
+	      if (jump_func->value.pass_through.operation != NOP_EXPR)
+		print_generic_expr (dump_file,
+				    jump_func->value.pass_through.operand, 0);
+	      fprintf (dump_file, "\n");
  	    }
+	  else if (type == IPA_JF_ANCESTOR)
+	    {
+	      fprintf (f, "ANCESTOR: ");
+	      fprintf (f, "%d, offset "HOST_WIDE_INT_PRINT_DEC"\n",
+		       jump_func->value.ancestor.formal_id,
+		       jump_func->value.ancestor.offset);
+	    }
 	}
     }
 }
@@ -313,6 +327,67 @@ ipa_print_all_jump_functions (FILE *f)
     }
 }
 
+/* Determine passing ssa name NAME constitutes a pass-through function with a
+   simple operation embeded in it or getting an address of an acestor and if
+   so, write such a jump function to JFUNC.  INFO describes the caller.  */
+
+static void
+compute_complex_pass_through (struct ipa_node_params *info,
+			      struct ipa_jump_func *jfunc,
+			      tree name)
+{
+  HOST_WIDE_INT offset, size, max_size;
+  tree op1, op2, type;
+  int index;
+  gimple stmt = SSA_NAME_DEF_STMT (name);
+
+  if (!is_gimple_assign (stmt))
+    return;
+  op1 = gimple_assign_rhs1 (stmt);
+  op2 = gimple_assign_rhs2 (stmt);
+
+  if (op2)
+    {
+      if (TREE_CODE (op1) != SSA_NAME
+	  || !SSA_NAME_IS_DEFAULT_DEF (op1)
+	  || !is_gimple_ip_invariant (op2))
+	return;
+
+      index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op1));
+      if (index >= 0)
+	{
+	  jfunc->type = IPA_JF_PASS_THROUGH;
+	  jfunc->value.pass_through.formal_id = index;
+	  jfunc->value.pass_through.operation = gimple_assign_rhs_code (stmt);
+	  jfunc->value.pass_through.operand = op2;
+	}
+      return;
+    }
+
+  if (TREE_CODE (op1) != ADDR_EXPR)
+    return;
+  op1 = TREE_OPERAND (op1, 0);
+  type = TREE_TYPE (op1);
+
+  op1 = get_ref_base_and_extent (op1, &offset, &size, &max_size);
+  if (TREE_CODE (op1) != INDIRECT_REF)
+    return;
+  op1 = TREE_OPERAND (op1, 0);
+  if (TREE_CODE (op1) != SSA_NAME
+      || !SSA_NAME_IS_DEFAULT_DEF (op1))
+    return;
+
+  index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op1));
+  if (index >= 0)
+    {
+      jfunc->type = IPA_JF_ANCESTOR;
+      jfunc->value.ancestor.formal_id = index;
+      jfunc->value.ancestor.offset = offset;
+      jfunc->value.ancestor.type = type;
+    }
+}
+
+
 /* Determine the jump functions of scalar arguments.  Scalar means SSA names
    and constants of a number of selected types.  INFO is the ipa_node_params
    structure associated with the caller, FUNCTIONS is a pointer to an array of
@@ -336,15 +411,21 @@ compute_scalar_jump_functions (struct ip
 	  functions[num].type = IPA_JF_CONST;
 	  functions[num].value.constant = arg;
 	}
-      else if ((TREE_CODE (arg) == SSA_NAME) && SSA_NAME_IS_DEFAULT_DEF (arg))
+      else if (TREE_CODE (arg) == SSA_NAME)
 	{
-	  int index = ipa_get_param_decl_index (info, SSA_NAME_VAR (arg));
-
-	  if (index >= 0)
+	  if (SSA_NAME_IS_DEFAULT_DEF (arg))
 	    {
-	      functions[num].type = IPA_JF_PASS_THROUGH;
-	      functions[num].value.formal_id = index;
+	      int index = ipa_get_param_decl_index (info, SSA_NAME_VAR (arg));
+
+	      if (index >= 0)
+		{
+		  functions[num].type = IPA_JF_PASS_THROUGH;
+		  functions[num].value.pass_through.formal_id = index;
+		  functions[num].value.pass_through.operation = NOP_EXPR;
+		}
 	    }
+	  else
+	    compute_complex_pass_through (info, &functions[num], arg);
 	}
     }
 }
@@ -411,7 +492,8 @@ compute_pass_through_member_ptrs (struct
 	      if (!ipa_is_param_modified (info, index))
 		{
 		  functions[num].type = IPA_JF_PASS_THROUGH;
-		  functions[num].value.formal_id = index;
+		  functions[num].value.pass_through.formal_id = index;
+		  functions[num].value.pass_through.operation = NOP_EXPR;
 		}
 	      else
 		undecided_members = true;
@@ -876,7 +958,10 @@ ipa_analyze_params_uses (struct cgraph_n
 
 /* Update the jump functions associated 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.  */
+   indirectly) inlined into CS->callee and that E has not been inlined.
+
+   We keep pass through functions only if they do not contain any operation.
+   This is sufficient for inlining and greately simplifies things.  */
 
 static void
 update_jump_functions_after_inlining (struct cgraph_edge *cs,
@@ -891,17 +976,26 @@ update_jump_functions_after_inlining (st
     {
       struct ipa_jump_func *src, *dst = ipa_get_ith_jump_func (args, i);
 
+      if (dst->type == IPA_JF_ANCESTOR)
+	{
+	  dst->type = IPA_JF_UNKNOWN;
+	  continue;
+	}
+
       if (dst->type != IPA_JF_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))
+      /* We must check range due to calls with variable number of arguments and
+	 we cannot combine jump functions with operations.  */
+      if (dst->value.pass_through.operation != NOP_EXPR
+	  || (dst->value.pass_through.formal_id
+	      >= ipa_get_cs_argument_count (top)))
 	{
 	  dst->type = IPA_JF_UNKNOWN;
 	  continue;
 	}
 
-      src = ipa_get_ith_jump_func (top, dst->value.formal_id);
+      src = ipa_get_ith_jump_func (top, dst->value.pass_through.formal_id);
       *dst = *src;
     }
 }
@@ -952,15 +1046,16 @@ update_call_notes_after_inlining (struct
 	continue;
 
       /* We must check range due to calls with variable number of arguments:  */
-      if (nt->formal_id >= (unsigned) ipa_get_cs_argument_count (top))
+      if (nt->formal_id >= ipa_get_cs_argument_count (top))
 	{
 	  nt->processed = true;
 	  continue;
 	}
 
       jfunc = ipa_get_ith_jump_func (top, nt->formal_id);
-      if (jfunc->type == IPA_JF_PASS_THROUGH)
-	nt->formal_id = jfunc->value.formal_id;
+      if (jfunc->type == IPA_JF_PASS_THROUGH
+	  && jfunc->value.pass_through.operation == NOP_EXPR)
+	nt->formal_id = jfunc->value.pass_through.formal_id;
       else if (jfunc->type == IPA_JF_CONST
 	       || jfunc->type == IPA_JF_CONST_MEMBER_PTR)
 	{
@@ -997,6 +1092,13 @@ update_call_notes_after_inlining (struct
 	    VEC_safe_push (cgraph_edge_p, heap, *new_edges, new_indirect_edge);
 	  top = IPA_EDGE_REF (cs);
 	}
+      else
+	{
+	  /* Ancestor jum functions and pass theoughs with operations should
+	     not be used on parameters that then get called.  */
+	  gcc_assert (jfunc->type == IPA_JF_UNKNOWN);
+	  nt->processed = true;
+	}
     }
   return res;
 }
Index: icln/gcc/ipa-prop.h
===================================================================
--- icln.orig/gcc/ipa-prop.h
+++ icln/gcc/ipa-prop.h
@@ -31,18 +31,26 @@ along with GCC; see the file COPYING3.
 
 /* A jump function for a callsite represents the values passed as actual
    arguments of the callsite. There are three main types of values :
-   Formal - the caller's formal parameter is passed as an actual argument.
-   Constant - a constant is passed as an actual argument.
-   Unknown - neither of the above.
-   Integer and real constants are represented as IPA_JF_CONST.
-   Finally, IPA_JF_CONST_MEMBER_PTR stands for C++ member pointers
-   constants.  */
+
+   Pass-through - the caller's formal parameter is passed as an actual
+                  argument, possibly one simple operation performed on it.
+   Constant     - a constant (is_gimple_ip_invariant)is passed as an actual
+                  argument.
+   Unknown      - neither of the above.
+
+   IPA_JF_CONST_MEMBER_PTR stands for C++ member pointers, other constants are
+   represented with IPA_JF_CONST.
+
+   In addition to "ordinary" pass through functions represented by
+   IPA_JF_PASS_THROUGH, IPA_JF_ANCESTOR represents getting addresses of of
+   ancestor fields in C++ (e.g. &this_1(D)->D.1766.D.1756).  */
 enum jump_func_type
 {
   IPA_JF_UNKNOWN = 0,  /* newly allocated and zeroed jump functions default */
   IPA_JF_CONST,
   IPA_JF_CONST_MEMBER_PTR,
-  IPA_JF_PASS_THROUGH
+  IPA_JF_PASS_THROUGH,
+  IPA_JF_ANCESTOR
 };
 
 /* All formal parameters in the program have a lattice associated with it
@@ -61,6 +69,36 @@ enum ipa_lattice_type
   IPA_TOP
 };
 
+
+/* Structure holding data required to describe a pass-through jump function.  */
+
+struct ipa_pass_through_data
+{
+  /* If an operation is to be performed on the original parameter, this is the
+     second (constant) operand.  */
+  tree operand;
+  /* Number of the caller's formal parameter being passed.  */
+  int formal_id;
+  /* Operation that is performed on the argument before it is passed on.
+     NOP_EXPR means no operation.  Otherwise oper must be a simple binary
+     arithmetic operation where the caller's parameter is the first operand and
+     operand field from this structure is the second one.  */
+  enum tree_code operation;
+};
+
+/* Structure holding data required to describe and ancestor pass throu
+   funkci.  */
+
+struct ipa_ancestor_jf_data
+{
+  /* Offset of the field representing the ancestor.  */
+  HOST_WIDE_INT offset;
+  /* TYpe of the result.  */
+  tree type;
+  /* Number of the caller's formal parameter being passed.  */
+  int formal_id;
+};
+
 /* Structure holding a C++ member pointer constant.  Holds a pointer to the
    method and delta offset.  */
 struct ipa_member_ptr_cst
@@ -69,15 +107,14 @@ struct ipa_member_ptr_cst
   tree delta;
 };
 
-/* Represents a value of a jump function.  formal_id is used only in jump
-   function context and represents pass-through parameter (the formal parameter
-   of the caller is passed as argument).  constant represents the actual
-   constant in constant jump functions and member_cst holds constant c++ member
-   functions.  */
+/* Represents a value of a jump function.  pass_through is used only in jump
+   function context.  constant represents the actual constant in constant jump
+   functions and member_cst holds constant c++ member functions.  */
 union jump_func_value
 {
-  unsigned int formal_id;
   tree constant;
+  struct ipa_pass_through_data pass_through;
+  struct ipa_ancestor_jf_data ancestor;
   struct ipa_member_ptr_cst member_cst;
 };
 
@@ -109,7 +146,7 @@ struct ipa_param_call_note
   /* Statement that contains the call to the parameter above.  */
   gimple stmt;
   /* Index of the parameter that is called.  */
-  unsigned int formal_id;
+  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