Author: Martin Jambor Date: To: GCC Patches CC: Jan Hubicka, Kenneth Zadeck, Razya Ladelsky Subject: [middle-end, patch 5/9] Rewritten jump functions computation
This patch is a rewrite of jump function computation. It uses SSA
form in a substantially cleaner way and is capable of finding member
pointer constant and pass through functions in the following simple
circumstances:
- A pass-through function is generated when a formal member pointer
parameter is passed as an actual argument and modification
analysis (from the previous patch) determined it is not modified
anywhere in the caller function.
- A constant jump function for member pointers is generated if the
member pointer is initialized with constant pointers to a method
and a constant delta in the same BB which the call is in
(obviously in statements preceeding the call).
- Otherwise a bottom jump functions is assumed.
2008-07-03 Martin Jambor <mjambor@???>
* ipa-cp.c (ipcp_print_all_jump_functions): Moved to ipa-prop.c.
(ipcp_print_all_lattices): Slight fprintf rearrangement.
(ipcp_lat_is_insertable): New function.
(ipcp_insert_stage): Use ipcp_lat_is_insertable, create replace maps
only for replacable scalars.
(ipcp_create_replace_map): Part of the condition moved to the caller,
removed unnecessary assert.
(ipcp_lattice_from_jfunc): Produces bottom lattices for unhandled jump
function types.
* ipa-prop.h (enum jump_func_type): Make explicit that we depend
on IPA_UNKNOWN being zero.
(enum jump_func_type): Added value IPA_CONST_MEMBER_PTR.
(struct ipa_member_ptr_cst): New structure.
(union jump_func_value): New field member_cst.
* ipa-prop.c (ipa_print_all_jump_functions): Moved here from
ipa-cp.c and split into two functions.
(ipa_print_node_jump_functions): New function.
(ipa_print_node_jump_functions): Provide for IPA_CONST_MEMBER_PTR.
(type_like_member_ptr_p): New function.
(compute_scalar_jump_functions): New function.
(compute_pass_through_member_ptrs): New function.
(is_cst_member_ptr): New function.
(compute_cst_member_ptr_arguments): New function.
(ipa_compute_jump_functions): Complete rewrite.
-/* Compute jump function for all arguments of callsite CS
- and insert the information in the jump_functions array
- in the ipa_edge_args corresponding to this callsite. */
+/* The following function prints the jump functions of all arguments on all
+ call graph edges going from NODE to file F. */
void
-ipa_compute_jump_functions (struct cgraph_edge *cs)
+ipa_print_node_jump_functions (FILE *f, struct cgraph_node *node)
{
- tree call_tree;
- tree arg, cst_decl;
- int arg_num;
- struct cgraph_node *mt;
- tree parm_decl;
- struct function *curr_cfun;
- call_expr_arg_iterator iter;
- struct ipa_edge_args *args = IPA_EDGE_REF (cs);
+ int i, count;
+ struct cgraph_edge *cs;
+ struct ipa_jump_func *jump_func;
+ enum jump_func_type type;
- FOR_EACH_CALL_EXPR_ARG (arg, iter, call_tree)
+ count = ipa_get_cs_argument_count (IPA_EDGE_REF (cs));
+ for (i = 0; i < count; i++)
+ {
+ jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
+ type = jump_func->type;
+
+ fprintf (f, " param %d: ", i);
+ if (type == IPA_UNKNOWN)
+ fprintf (f, "UNKNOWN\n");
+ else if (type == IPA_CONST || type == IPA_CONST_REF)
+ {
+ tree val = jump_func->value.constant;
+ fprintf (f, "CONST: ");
+ print_generic_expr (f, val, 0);
+ fprintf (f, "\n");
+ }
+ else if (type == IPA_CONST_MEMBER_PTR)
+ {
+ fprintf (f, "CONST MEMBER PTR: ");
+ print_generic_expr (f, jump_func->value.member_cst.pfn, 0);
+ fprintf (f, ", ");
+ print_generic_expr (f, jump_func->value.member_cst.delta, 0);
+ fprintf (f, "\n");
+ }
+ else if (type == IPA_PASS_THROUGH)
+ {
+ fprintf (f, "PASS THROUGH: ");
+ fprintf (f, "%d\n", jump_func->value.formal_id);
+ }
+ }
+ }
+}
+
+/* Print ipa_jump_func data structures of all nodes in the call graph to F. */
+void
+ipa_print_all_jump_functions (FILE *f)
+{
+ struct cgraph_node *node;
+
+ fprintf (f, "\nCALLSITE PARAM PRINT\n");
+ for (node = cgraph_nodes; node; node = node->next)
{
- /* If the formal parameter was passed as argument, we store
- IPA_PASS_THROUGH and its index in the caller as the jump function
- of this argument. */
- if ((TREE_CODE (arg) == SSA_NAME
- && TREE_CODE (SSA_NAME_VAR (arg)) == PARM_DECL)
- || TREE_CODE (arg) == PARM_DECL)
+ ipa_print_node_jump_functions (f, node);
+ }
+}
+
+/* The following function determines 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 jump function structures associated with CALL which
+ is the call statement being examined.*/
+static void
+compute_scalar_jump_functions (struct ipa_node_params *info,
+ struct ipa_jump_func *functions,
+ tree call)
+{
+ call_expr_arg_iterator iter;
+ tree arg;
+ int num = 0;
+
+ FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
+ {
+ if (TREE_CODE (arg) == INTEGER_CST
+ || TREE_CODE (arg) == REAL_CST
+ || TREE_CODE (arg) == FIXED_CST)
+ {
+ functions[num].type = IPA_CONST;
+ functions[num].value.constant = arg;
+ }
+ else if (TREE_CODE (arg) == ADDR_EXPR)
+ {
+ if (TREE_CODE (TREE_OPERAND (arg, 0)) == FUNCTION_DECL)
+ {
+ functions[num].type = IPA_CONST;
+ functions[num].value.constant = TREE_OPERAND (arg, 0);
+ }
+ else if (TREE_CODE (TREE_OPERAND (arg, 0)) == CONST_DECL)
+ {
+ tree cst_decl = TREE_OPERAND (arg, 0);
+
+ if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST
+ || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST
+ || TREE_CODE (DECL_INITIAL (cst_decl)) == FIXED_CST)
+ {
+ functions[num].type = IPA_CONST_REF;
+ functions[num].value.constant = cst_decl;
+ }
+ }
+ }
+ else if ((TREE_CODE (arg) == SSA_NAME) && SSA_NAME_IS_DEFAULT_DEF (arg))
{
- struct ipa_node_params *info;
- int index;
+ int index = ipa_get_param_decl_index (info, SSA_NAME_VAR (arg));
- mt = cs->caller;
- info = IPA_NODE_REF (mt);
- parm_decl = TREE_CODE (arg) == PARM_DECL ? arg : SSA_NAME_VAR (arg);
-
- index = ipa_get_param_decl_index (info, parm_decl);
- if (TREE_CODE (arg) == SSA_NAME && IS_VALID_JUMP_FUNC_INDEX (index))
+ if (index >= 0)
{
- curr_cfun = DECL_STRUCT_FUNCTION (mt->decl);
- if (!gimple_default_def (curr_cfun, parm_decl)
- || gimple_default_def (curr_cfun, parm_decl) != arg)
- info->param_flags[index].modified = true;
+ functions[num].type = IPA_PASS_THROUGH;
+ functions[num].value.formal_id = index;
}
- if (!IS_VALID_JUMP_FUNC_INDEX (index)
- || ipa_is_ith_param_modified (info, index))
- args->jump_functions[arg_num].type = IPA_UNKNOWN;
- else
+ }
+
+ num++;
+ }
+}
+
+/* This function inspects the given TYPE and returns true iff it has the same
+ structure (the same number of fields of the same types) as a C++ member
+ pointer. If METHOD_PTR and DELTA are non-NULL, the trees representing the
+ corresponding fields are stored there. */
+static bool
+type_like_member_ptr_p (tree type, tree *method_ptr, tree *delta)
+{
+ tree fld;
+
+ if (TREE_CODE (type) != RECORD_TYPE)
+ return false;
+
+ fld = TYPE_FIELDS (type);
+ if (!fld || !POINTER_TYPE_P (TREE_TYPE (fld))
+ || TREE_CODE (TREE_TYPE (TREE_TYPE (fld))) != METHOD_TYPE)
+ return false;
+
+ if (method_ptr)
+ *method_ptr = fld;
+
+ fld = TREE_CHAIN (fld);
+ if (!fld || INTEGRAL_TYPE_P (fld))
+ return false;
+ if (delta)
+ *delta = fld;
+
+ if (TREE_CHAIN (fld))
+ return false;
+
+ return true;
+}
+
+/* This function goes through arguments of the CALL and for every one that
+ looks like a member pointer, it checks whether it can be safely declared
+ pass-through and if so, marks that to the corresponding item of jum
+ FUNCTIONS . It returns true iff there were non-pass-through member pointers
+ within the arguments. INFO describes formal parameters of the caller. */
+static bool
+compute_pass_through_member_ptrs (struct ipa_node_params *info,
+ struct ipa_jump_func *functions,
+ tree call)
+{
+ call_expr_arg_iterator iter;
+ bool undecided_members = false;
+ int num = 0;
+ tree arg;
+
+ FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
+ {
+ if (type_like_member_ptr_p (TREE_TYPE (arg), NULL, NULL))
+ {
+ if (TREE_CODE (arg) == PARM_DECL)
{
- args->jump_functions[arg_num].type = IPA_PASS_THROUGH;
- args->jump_functions[arg_num].value.formal_id = index;
+ int index = ipa_get_param_decl_index (info, arg);
+
+ gcc_assert (index >=0);
+ if (!ipa_is_ith_param_modified (info, index))
+ {
+ functions[num].type = IPA_PASS_THROUGH;
+ functions[num].value.formal_id = index;
+ }
+ else
+ undecided_members = true;
}
+ else
+ undecided_members = true;
+ }
+
+ num++;
+ }
+
+ return undecided_members;
+}
+
+/* Simple function filling in a member pointer constant jump function (with PFN
+ and DELTA as the constant value) into JFUNC. */
+static void
+fill_member_ptr_cst_jump_function (struct ipa_jump_func *jfunc,
+ tree pfn, tree delta)
+{
+ jfunc->type = IPA_CONST_MEMBER_PTR;
+ jfunc->value.member_cst.pfn = pfn;
+ jfunc->value.member_cst.delta = delta;
+}
+
+/* The following function traverses statements from CALL_STMT backwards,
+ scanning whether the argument ARG which is a member pointer is filled in
+ with constant values. If it is, the jump function JFUNC is filled in
+ appropriately. METHOD_FIELD and DELTA_FIELD are fields of the record type
+ of the member pointer. */
+static void
+determine_cst_member_ptr (tree call_stmt, tree arg, tree method_field,
+ tree delta_field, struct ipa_jump_func *jfunc)
+{
+ block_stmt_iterator bsi;
+ tree method = NULL_TREE;
+ tree delta = NULL_TREE;
+
+ bsi = bsi_for_stmt (call_stmt);
+
+ bsi_prev (&bsi);
+ for (; !bsi_end_p (bsi); bsi_prev (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ tree lhs, rhs, op, fld;
+
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+ return;
+
+ rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+ if (TREE_CODE (rhs) == CALL_EXPR)
+ return;
+
+ lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ op = lhs;
+ while (handled_component_p (op))
+ {
+ if (TREE_CODE (op) == ARRAY_REF
+ || TREE_CODE (op) == ARRAY_RANGE_REF)
+ return;
+
+ op = TREE_OPERAND (op, 0);
}
- /* If a constant value was passed as argument,
- we store IPA_CONST and its value as the jump function
- of this argument. */
- else if (TREE_CODE (arg) == INTEGER_CST
- || TREE_CODE (arg) == REAL_CST
- || TREE_CODE (arg) == FIXED_CST)
+ if (TREE_CODE (op) == INDIRECT_REF)
+ return;
+
+ if (TREE_CODE (lhs) != COMPONENT_REF
+ || TREE_OPERAND (lhs, 0) != arg)
+ continue;
+
+ fld = TREE_OPERAND (lhs, 1);
+ if (!method && fld == method_field)
{
- args->jump_functions[arg_num].type = IPA_CONST;
- args->jump_functions[arg_num].value.constant = arg;
+ if (TREE_CODE (rhs) == ADDR_EXPR
+ && TREE_CODE (TREE_OPERAND (rhs, 0)) == FUNCTION_DECL
+ && TREE_CODE (TREE_TYPE (TREE_OPERAND (rhs, 0))) == METHOD_TYPE)
+ {
+ method = TREE_OPERAND (rhs, 0);
+ if (delta)
+ {
+ fill_member_ptr_cst_jump_function (jfunc, method, delta);
+ return;
+ }
+ }
+ else
+ return;
}
- /* This is for the case of Fortran. If the address of a const_decl
- was passed as argument then we store
- IPA_CONST_REF/IPA_CONST_REF and the constant
- value as the jump function corresponding to this argument. */
- else if (TREE_CODE (arg) == ADDR_EXPR
- && TREE_CODE (TREE_OPERAND (arg, 0)) == CONST_DECL)
+
+ if (!delta && fld == delta_field)
{
- cst_decl = TREE_OPERAND (arg, 0);
- if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST
- || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST
- || TREE_CODE (DECL_INITIAL (cst_decl)) == FIXED_CST)
+ if (TREE_CODE (rhs) == INTEGER_CST)
{
- args->jump_functions[arg_num].type = IPA_CONST_REF;
- args->jump_functions[arg_num].value.constant = cst_decl;
+ delta = rhs;
+ if (method)
+ {
+ fill_member_ptr_cst_jump_function (jfunc, method, delta);
+ return;
+ }
}
+ else
+ return;
}
- else
- args->jump_functions[arg_num].type = IPA_UNKNOWN;
- arg_num++;
}
+
+ return;
+}
+
+/* This function goies through the arguments of the call in CALL_STMT and for
+ every member pointer within tries to determine whether it is a constant. If
+ it is, a corresponding constant jump function is created in FUNCTIONS which
+ is an array of jump functions associated with the call. */
+static void
+compute_cst_member_ptr_arguments (struct ipa_jump_func *functions,
+ tree call_stmt)
+{
+ call_expr_arg_iterator iter;
+ int num = 0;
+ tree call = get_call_expr_in (call_stmt);
+ tree arg, method_field, delta_field;
+
+ FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
+ {
+ if (functions[num].type == IPA_UNKNOWN
+ && type_like_member_ptr_p (TREE_TYPE (arg), &method_field,
+ &delta_field))
+ determine_cst_member_ptr (call_stmt, arg, method_field,
+ delta_field, &functions[num]);
+
+ num++;
+ }
+}
+
+/* Compute jump function for all arguments of callsite CS and insert the
+ information in the jump_functions array in the ipa_edge_args corresponding
+ to this callsite. */
+void
+ipa_compute_jump_functions (struct cgraph_edge *cs)
+{
+ struct ipa_node_params *info = IPA_NODE_REF (cs->caller);
+ struct ipa_edge_args *arguments = IPA_EDGE_REF (cs);
+ tree call;
+
+ if (ipa_get_cs_argument_count (arguments) == 0 || arguments->jump_functions)
+ return;
+ arguments->jump_functions = XCNEWVEC (struct ipa_jump_func,
+ ipa_get_cs_argument_count (arguments));
+ call = get_call_expr_in (cs->call_stmt);
+
+ /* We will deal with constants and SSA scalars first: */
+ compute_scalar_jump_functions (info, arguments->jump_functions, call);
+
+ /* Let's check whether there are any potential member pointers and if so,
+ whether we can determine their functions as pass_through. */
+ if (!compute_pass_through_member_ptrs (info, arguments->jump_functions, call))
+ return;
+
+ /* Finally, let's check whether we actually pass a new constant membeer
+ pointer here... */
+ compute_cst_member_ptr_arguments (arguments->jump_functions, cs->call_stmt);
}
/* Reallocate the array of node param infos so that there's one for every
Index: iinln/gcc/ipa-prop.h
===================================================================
--- iinln.orig/gcc/ipa-prop.h
+++ iinln/gcc/ipa-prop.h
@@ -31,21 +31,23 @@ along with GCC; see the file COPYING3.
Constant - a constant is passed as an actual argument.
Unknown - neither of the above.
Integer and real constants are represented as IPA_CONST and Fortran
- constants are represented as IPA_CONST_REF. */
+ constants are represented as IPA_CONST_REF. Finally, IPA_CONST_MEMBER_PTR
+ stands for C++ member pointers constants. */
enum jump_func_type
{
- IPA_UNKNOWN,
+ IPA_UNKNOWN = 0, /* newly allocated and zeroed jump functions default */
IPA_CONST,
IPA_CONST_REF,
+ IPA_CONST_MEMBER_PTR,
IPA_PASS_THROUGH
};
/* All formal parameters in the program have a lattice associated with it
computed by the interprocedural stage of IPCP.
There are three main values of the lattice:
- TOP - unknown.
- BOTTOM - non constant.
- CONSTANT_TYPE - constant value.
+ IPA_TOP - unknown,
+ IPA_BOTTOM - non constant,
+ IPA_CONST_VALUE - simple scalar constant,
Cval of formal f will have a constant value if all callsites to this
function have the same constant value passed to f.
Integer and real constants are represented as IPA_CONST and Fortran
@@ -58,14 +60,24 @@ enum ipa_lattice_type
IPA_TOP
};
-/* Represents a value of a jump function.
- value represents a constant.
- formal_id is used only in jump function context and represents
- pass-through parameter (the formal of caller is passed as argument). */
+/* Structure holding a C++ member pointer constant. Holds a pointer to the
+ method and delta offset. */
+struct ipa_member_ptr_cst
+{
+ tree pfn;
+ 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. */
union jump_func_value
{
unsigned int formal_id;
tree constant;
+ struct ipa_member_ptr_cst member_cst;
};
/* A jump function for a callsite represents the values passed as actual
@@ -323,5 +335,7 @@ void ipa_detect_param_modifications (str
/* Debugging interface. */
void ipa_print_all_tree_maps (FILE *);
void ipa_print_all_params_modified (FILE *);
+void ipa_print_node_jump_functions (FILE *f, struct cgraph_node *node);
+void ipa_print_all_jump_functions (FILE * f);
