This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [WPA PATCH 2/5] Enhanced jump functions
Hi,
thanks for looking into this.
On Thu, Aug 06, 2009 at 05:47:42PM +0200, Jan Hubicka wrote:
> > 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 wonder how much restricting to single binary function is limiting us
> relative to general expression trees (either as trees or represented by
> the value numbering code). But since we are primarily interested in
> handling C++ inheritance, this seems fine.
Yes, the ancestral function is there for C++ classes. Unfortunately I
organized my work wrong way round and this was the last part I wrote
and wanted to do quickly something simple and so I do not know what we
would gain if we had even more complex polynomial functions. I plan
to find out but no sooner than September. Ditto for operations with
the incoming parameter as the second argument and unary operations.
>
> You handle NOP_EXPRs and CONVERT_EXPRs too, right?
>
I don't think I can encounter a NOP_EXPR this late. I don't handle
CONVERT_EXPRs in any special way so I would guess that no, I probably
don't.
> > + cst = fold_build2 (jfunc->value.pass_through.operation,
> > + TREE_TYPE (cst), cst,
> > + jfunc->value.pass_through.operand);
>
> Hmm, things are supposed to always fold, so perhaps fold_binary?
Uhm... right.
> > +/* 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,
>
> I think the original ipa-cp paper speaks of constant jump functions,
> pass through and polynomial (that are really expressions in GCC
> terminology). I think it is better to stick with the terminology used
> in literature.
>
> I relaize that you now handle pass through as special case of
> polynomial, so we will have pass through to either disappear from
> sources or we can still differentiate pass_through as the variant
> without any operation for some shortcuts same way as the paper does.
I would keep using pass through and note that it is a polynomial pass
through where the difference should be emphasized (in comments and
function names etc). I will adjust the comment. However, I don't
have any strong feelings about this, feel free to rename the stuff any
way you like.
>
> > + if (TREE_CODE (op1) != ADDR_EXPR)
> > + return;
>
> What about param->filed1? Is that handled somewhere?
No, only ¶m->field1. Without the ADDR_EXPR, it would rarely ever
give an ipa invariant and even if it did (from some initialized
read-only static structure, perhaps?) the code is not able to
reconstruct it.
>
> Otherwise patch seems fine and I think it would make a lot of sense to
> push it to mainline soon, before we resolve issues with the cost
> functions on clonning. It should bring immediate improvements to ipa-cp
> & indirect call handling, so it is win per se.
Yes, this part is fairly independent and can be (at least in theory)
quite beneficial so even if the rest of the patches don't go in now,
this can.
I'll try to add a testcase or two overnight. I am currently about to
bootstrap and test the patch below (just this one and the one making
build_ref_for_offset public, of course). OK for trunk with them if it
passes both?
Thanks,
Martin
2009-08-06 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
polynomial 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,43 @@ 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;
+
+ if (jfunc->value.pass_through.operation != NOP_EXPR)
+ cst = fold_binary (jfunc->value.pass_through.operation,
+ TREE_TYPE (cst), cst,
+ jfunc->value.pass_through.operand);
+ gcc_assert (cst && 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 whether passing ssa name NAME constitutes a polynomial
+ pass-through function 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