[PATCH, pretty-ipa merge 3/4] The IPA-SRA itself.
Richard Guenther
rguenther@suse.de
Fri Jul 3 09:49:00 GMT 2009
On Thu, 2 Jul 2009, Martin Jambor wrote:
> Hi,
>
> again, thanks for the review.
>
> On Sun, Jun 28, 2009 at 03:47:24PM +0200, Richard Guenther wrote:
> > On Wed, 24 Jun 2009, Martin Jambor wrote:
> >
> > > Hi,
> > >
> > > this patch contains the implementation of IPA-SRA which is built on
> > > top of the new intraprocedural SRA (with which it shares most of the
> > > analysis stage) as it is in the pretty-ipa now.
> > >
> > > Thanks,
> > >
> > > Martin
> > >
> > >
> > > 2009-06-23 Martin Jambor <mjambor@suse.cz>
> > >
> > > * tree-sra.c: Include cgraph.h.
> > > (enum sra_mode): Added SRA_MODE_EARLY_IPA.
> > > (struct access): Added members bb, stmt, always_safe,
> > > grp_maybe_modified and grp_scalar_ptr.
> > > (func_param_count): New variable.
> > > (encountered_va_start): New variable.
> > > (encountered_external_throw): New variable.
> > > (no_accesses_representant): New variable.
> > > (+no_accesses_p): New function.
> > > (dump_access): Dump the new access members.
> > > (sra_initialize): Initialize encountered_va_start and
> > > encountered_external_throw.
> > > (get_ssa_base_param): New function.
> > > (create_access): Caring for INIDRECT_REFs and different handling of
> > > varialble length accesses in early IPA SRA. Store tthe basic block and
> > > stmt - new parameter - to the new access.
> > > (disqualify_base_of_expr): Take care of INDIRECT_REFs and look through
> > > SSA_NAMES in IPA_SRA.
> > > (disqualify_direct_ptr_params): New function.
> > > (disqualify_all_direct_ptr_params): New function.
> > > (build_access_from_expr_1): Call disqualify_direct_ptr_params, handle
> > > INDIRECT_REFs and ADDR_EXPRs. New parameter stmt passed to
> > > create_access.
> > > (disqualify_ops_if_throwing_stmt): Trigger only in intraprocedural
> > > passes.
> > > (build_accesses_from_assign): Check statements that are not single
> > > assignments for disallowed uses of parameters. Do not create assign
> > > links in the interprocedural pass.
> > > (scan_phi_nodes): New function.
> > > (scan_function): In the interprocedural pass analysis scan phi nodes,
> > > check for externally throwing statements and va_start, make sure to
> > > disqualify all direct uses in statement types which arew not handled
> > > explicitely.
> > > (build_ref_for_offset): Not static any more.
> > > (find_param_candidates): New function.
> > > (mark_maybe_modified): New function.
> > > (analyze_modified_params): New function.
> > > (process_dominator_bb): New function.
> > > (fake_edges_required_p): New function.
> > > (analyze_caller_dereference_legality): New function.
> > > (unmodified_by_ref_scalar_representative): New function.
> > > (splice_param_accesses): New function.
> > > (decide_one_param_reduction): New function.
> > > (is_unused_scalar_param): New function.
> > > (enum ipa_splicing_result): New type.
> > > (splice_all_param_accesses): New function.
> > > (get_param_index): New function.
> > > (turn_representatives_into_notes): New function.
> > > (analyze_all_param_acesses): New function.
> > > (get_replaced_param_substitute): New function.
> > > (replace_removed_params_ssa_names): New function.
> > > (sra_ipa_modify_expr): New function.
> > > (sra_ipa_modify_assign): New function.
> > > (convert_callers): New function.
> > > (modify_function): New function.
> > > (ipa_early_sra): New function.
> > > (ipa_early_sra_gate): New function.
> > > (pass_early_ipa_sra): New variable.
> > > * tree-pass.h (pass_early_ipa_sra): Declare.
> > > * passes.c (init_optimization_passes): Add pass_early_ipa_sra to the
> > > early passes.
> > > * Makefile.in (tree-sra.o): Add cgraph.h to dependencies.
> > >
> > > Index: mine/gcc/tree-sra.c
> > > ===================================================================
> > > --- mine.orig/gcc/tree-sra.c
> > > +++ mine/gcc/tree-sra.c
> > > @@ -78,6 +78,7 @@ along with GCC; see the file COPYING3.
> > > #include "tm.h"
> > > #include "tree.h"
> > > #include "gimple.h"
> > > +#include "cgraph.h"
> > > #include "tree-flow.h"
> > > #include "ipa-prop.h"
> > > #include "diagnostic.h"
> > > @@ -89,8 +90,9 @@ along with GCC; see the file COPYING3.
> > > #include "flags.h"
> > >
> > > /* Enumeration of all aggregate reductions we can do. */
> > > -enum sra_mode { SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
> > > - SRA_MODE_INTRA }; /* late intraprocedural SRA */
> > > +enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
> > > + SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
> > > + SRA_MODE_INTRA }; /* late intraprocedural SRA */
> > >
> > > /* Global variable describing which aggregate reduction we are performing at
> > > the moment. */
> > > @@ -128,6 +130,11 @@ struct access
> > > /* Type. */
> > > tree type;
> > >
> > > + /* The basic block of this access. */
> > > + basic_block bb;
> > > + /* The statement this access belongs to. */
> > > + gimple stmt;
> > > +
> > > /* Next group representative for this aggregate. */
> > > struct access *next_grp;
> > >
> > > @@ -156,6 +163,9 @@ struct access
> > >
> > > /* Is this particular access write access? */
> > > unsigned write : 1;
> > > + /* in IPA-SRA, is it guaranteed that an access to this or bigger offset is
> > > + always performed when the function is run? */
> > > + unsigned always_safe : 1;
> > >
> > > /* Is this access currently in the work queue? */
> > > unsigned grp_queued : 1;
> > > @@ -178,11 +188,18 @@ struct access
> > > /* Does this access and/or group contain a write access through a
> > > BIT_FIELD_REF? */
> > > unsigned grp_partial_1 : lhs;
> > > -
> > > /* Set when a scalar replacement should be created for this variable. We do
> > > the decision and creation at different places because create_tmp_var
> > > cannot be called from within FOR_EACH_REFERENCED_VAR. */
> > > unsigned grp_to_be_replaced : 1;
> > > +
> > > + /* Is it possible that the group refers to data which might be (directly or
> > > + otherwise) modified? */
> > > + unsigned grp_maybe_modified : 1;
> > > + /* Set when this is a representative of a pointer to scalar (i.e. by
> > > + reference) parameter which we consider for turning into a plain scalar
> > > + (i.e. a by value parameter). */
> > > + unsigned grp_scalar_ptr : 1;
> > > };
> >
> > Please keep the vertical space.
>
> The one in between grp_partial_lhs and grp_to_be_replaced? Should I
> put vertical spaces in between all the flags?
Yes, just have vertical space everywhere.
> >
> > > typedef struct access *access_p;
> > > @@ -217,6 +234,27 @@ static struct obstack name_obstack;
> > > propagated to their assignment counterparts. */
> > > static struct access *work_queue_head;
> > >
> > > +/* Number of parameters of the analyzed function when doing early ipa SRA. */
> > > +static int func_param_count;
> > > +
> > > +/* scan_function sets the following to true if it encounters a call to
> > > + __builtin_va_start. */
> > > +static bool encountered_va_start;
> > > +/* scan_function sets the following to true whenever it encounters a statement
> > > + that can throw externally. */
> > > +static bool encountered_external_throw;
> > > +
> > > +/* Representative of no accesses at all. */
> > > +static struct access no_accesses_representant;
> > > +
> > > +/* Predicate to test the special value. */
> > > +
> > > +static inline bool
> > > +no_accesses_p (struct access *access)
> > > +{
> > > + return access == &no_accesses_representant;
> > > +}
> > > +
> > > /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
> > > representative fields are dumped, otherwise those which only describe the
> > > individual access are. */
> > > @@ -263,13 +301,15 @@ dump_access (FILE *f, struct access *acc
> > > if (grp)
> > > fprintf (f, ", grp_write = %d, grp_read = %d, grp_covered = %d, "
> > > "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
> > > - "grp_partial_lhs = %d, grp_to_be_replaced = %d\n",
> > > + "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
> > > + "grp_maybe_modified = %d\n",
> > > access->grp_write, access->grp_read, access->grp_covered,
> > > access->grp_unscalarizable_region, access->grp_unscalarized_data,
> > > - access->grp_partial_lhs, access->grp_to_be_replaced);
> > > + access->grp_partial_lhs, access->grp_to_be_replaced,
> > > + access->grp_maybe_modified);
> > > else
> > > - fprintf (f, ", write = %d, grp_partial_lhs = %d\n", access->write,
> > > - access->grp_partial_lhs);
> > > + fprintf (f, ", write = %d, grp_partial_lhs = %d, always_safe = %d\n",
> > > + access->write, access->grp_partial_lhs, access->always_safe);
> > > }
> > >
> > > /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
> > > @@ -465,6 +505,8 @@ sra_initialize (void)
> > > link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
> > > base_access_vec = pointer_map_create ();
> > > memset (&sra_stats, 0, sizeof (sra_stats));
> > > + encountered_va_start = false;
> > > + encountered_external_throw = false;
> > > }
> > >
> > > /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
> > > @@ -554,34 +596,76 @@ type_internals_preclude_sra_p (tree type
> > > }
> > > }
> > >
> > > +/* If T is an SSA_NAME, return NULL if it is not a default def or return its
> > > + base variable if it is. Return T if it is not an SSA_NAME. */
> > > +
> > > +static tree
> > > +get_ssa_base_param (tree t)
> > > +{
> > > + if (TREE_CODE (t) == SSA_NAME)
> > > + {
> > > + if (SSA_NAME_IS_DEFAULT_DEF (t))
> > > + return SSA_NAME_VAR (t);
> > > + else
> > > + return NULL_TREE;
> > > + }
> > > + return t;
> > > +}
> >
> > Huh. Well, let's see how you use that beast ...
>
> It may look weird at the first glance but it actually makes sense. In
> IPA-SRA I have to inspect default_def SSA_NAMES of PARM_DECLs and
> should ignore all the others so that I don't for example disqualify
> parm in
>
> int foo (int *parm)
> {
> v = *parm;
> parm = &something;
> globalvar = parm;
> }
>
> Similarly, in the following example I can replace the first parm->foo
> with a new variable but not the second:
>
> int bar (struct blah *parm)
> {
> a = parm->foo;
> ...
> parm = some_global_pointer;
> ..
> b = parm->foo;
> }
>
> So I either have to check for various places for default_def-ness or
> factor it into the function that looks through SSA_NAMES which is what
> I did and I believe is the right thing to do.
>
>
> > > + if (!base)
> > > + return NULL;
> > > + ptr = true;
> > > + }
> > > + else
> > > + ptr = false;
> > > +
> > > if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
> > > return NULL;
> > >
> > > - if (size != max_size)
> > > + if (sra_mode == SRA_MODE_EARLY_IPA)
> > > {
> > > - size = max_size;
> > > - unscalarizable_region = true;
> > > + if (size < 0 || size != max_size)
> > > + {
> > > + disqualify_candidate (base, "Encountered a variable sized access.");
> > > + return NULL;
> > > + }
> > > + if ((offset % BITS_PER_UNIT) != 0 || (size % BITS_PER_UNIT) != 0)
> > > + {
> > > + disqualify_candidate (base,
> > > + "Encountered an acces not aligned to a byte.");
> > > + return NULL;
> > > + }
> > > }
> > > -
> > > - if (size < 0)
> > > + else
> > > {
> > > - disqualify_candidate (base, "Encountered an unconstrained access.");
> > > - return NULL;
> > > + if (size != max_size)
> > > + {
> > > + size = max_size;
> > > + unscalarizable_region = true;
> > > + }
> > > + if (size < 0)
> > > + {
> > > + disqualify_candidate (base, "Encountered an unconstrained access.");
> > > + return NULL;
> > > + }
> >
> > Why distinguish SRA_MODE_EARLY_IPA for these disqualifications? At
> > least size < 0 / size != max_size seem to be common code (of course
> > I might miss sth, the unified diff is confusing here).
>
> In intraprocedural SRA, if size != max_size, we use the max_size to
> mark the part of the aggregate as unscalarizable but happily scalarize
> the rest. However, in IPA-SRA, having an unscalarizable but used part
> of a parameter means that chucking bits out of it elsewhere is no good
> since we would have to pass also the whole aggregate anyway.
>
> The pass currently has no way of dealing with regions where size and
> max_size differ but if a constant max_size means that is an array
> access, I might simply create an access for the array with not so much
> special handling (in the modification part of the pass)... I guess I
> will experiment with that but it is not the top priority at the
> moment.
Ok.
> >
> > > }
> > >
> > > access = (struct access *) pool_alloc (access_pool);
> > > @@ -594,6 +678,8 @@ create_access (tree expr, bool write)
> > > access->type = TREE_TYPE (expr);
> > > access->write = write;
> > > access->grp_unscalarizable_region = unscalarizable_region;
> > > + access->stmt = stmt;
> > > + access->bb = gimple_bb (stmt);
> >
> > So bb is indeed redundant information.
>
> Apparently yes, silly me.
>
> >
> > > slot = pointer_map_contains (base_access_vec, base);
> > > if (slot)
> > > @@ -619,16 +705,67 @@ disqualify_base_of_expr (tree t, const c
> > > while (handled_component_p (t))
> > > t = TREE_OPERAND (t, 0);
> > >
> > > - if (DECL_P (t))
> > > + while (TREE_CODE (t) == INDIRECT_REF)
> > > + t = TREE_OPERAND (t, 0);
> >
> > No need for a loop here. Use
> >
> > if (INDIRECT_REF_P (t))
> > t = TREE_OPERAND (t, 0);
>
> OK
>
> >
> > > + if (sra_mode == SRA_MODE_EARLY_IPA)
> > > + t = get_ssa_base_param (t);
> >
> > in fact, INDIRECT_REF seems to be relevant for SRA_MODE_EARLY_IPA only,
> > so put it inside that if as well.
>
> Right.
>
> > This is the 2nd use with INDIRECT_REFs, maybe the helper should just
> > cover the INDIRECT_REF as well.
>
> It's also used to disqualify direct uses.
>
> >
> > > + if (t && DECL_P (t))
> > > disqualify_candidate (t, reason);
> > > }
> > >
> > > +/* See if OP is an undereferenced use of pointer parameters and if it is,
> > > + exclude it from the candidates and return true, otherwise return false. */
> > > +
> > > +static bool
> > > +disqualify_direct_ptr_params (tree op)
> > > +{
> > > + bool addr_taken;
> > > +
> > > + if (!op)
> > > + return false;
> > > + if (TREE_CODE (op) == ADDR_EXPR)
> > > + {
> > > + do
> > > + op = TREE_OPERAND (op, 0);
> > > + while (handled_component_p (op));
> >
> > Add {} braces.
>
> Hmm, I must have misremembered the GNU standard, apparently it does
> require braces and I am happier with them too.
>
> >
> > > + addr_taken = true;
> >
> > op can be still *parm here, so
> >
> > > + }
> > > + else
> >
> > this else looks wrong and above or in that fn you should strip
> > INDIRECT_REFs. Or use disqualify_base_of_expr above like you do below
> > for ADDR_EXPRs.
>
> INDIRECT_REF is fine here and is not a bases for disqualifying. This
> function only wants to disqualify direct uses ...and was a bit misused
> to catch ADDR_EXPRs of PARM_DECLs which are gimple_val's and thus can
> appear in two-operand assignments. However, I have now reworked it to
> use the TREE_ADDRESSABLE flag and removed the condition.
Thanks.
> >
> > > + {
> > > + op = get_ssa_base_param (op);
> > > + addr_taken = false;
> > > + }
> > > +
> > > + if (op && TREE_CODE (op) == PARM_DECL
> > > + && (addr_taken || POINTER_TYPE_P (TREE_TYPE (op))))
> > > + {
> > > + disqualify_candidate (op, " Direct use of its pointer value or "
> > > + "invariant addr_expr.");
> > > + return true;
> > > + }
> > > + return false;
> > > +}
> > > +
> > > +/* A callback for walk_gimple_op. Disqualifies SSA_NAMEs of default_defs of
> > > + params and does not descend any further into the tree structure. */
> > > +
> > > +static tree
> > > +disqualify_all_direct_ptr_params (tree *tp, int *walk_subtrees,
> > > + void *data ATTRIBUTE_UNUSED)
> > > +{
> > > + *walk_subtrees = 0;
> > > + disqualify_direct_ptr_params (*tp);
> > > + return NULL_TREE;
> > > +}
> > > +
> > > /* Scan expression EXPR and create access structures for all accesses to
> > > candidates for scalarization. Return the created access or NULL if none is
> > > created. */
> > >
> > > static struct access *
> > > -build_access_from_expr_1 (tree *expr_ptr, bool write)
> > > +build_access_from_expr_1 (tree *expr_ptr, gimple stmt, bool write)
> > > {
> > > struct access *ret = NULL;
> > > tree expr = *expr_ptr;
> > > @@ -644,6 +781,9 @@ build_access_from_expr_1 (tree *expr_ptr
> > > else
> > > partial_ref = false;
> > >
> > > + if (sra_mode == SRA_MODE_EARLY_IPA)
> > > + disqualify_direct_ptr_params (expr);
> > > +
> > > /* We need to dive through V_C_Es in order to get the size of its parameter
> > > and not the result type. Ada produces such statements. We are also
> > > capable of handling the topmost V_C_E but not any of those buried in other
> > > @@ -660,13 +800,23 @@ build_access_from_expr_1 (tree *expr_ptr
> > >
> > > switch (TREE_CODE (expr))
> > > {
> > > + case INDIRECT_REF:
> > > + if (sra_mode != SRA_MODE_EARLY_IPA)
> > > + return NULL;
> > > + /* fall through */
> > > case VAR_DECL:
> > > case PARM_DECL:
> > > case RESULT_DECL:
> > > case COMPONENT_REF:
> > > case ARRAY_REF:
> > > case ARRAY_RANGE_REF:
> > > - ret = create_access (expr, write);
> > > + ret = create_access (expr, stmt, write);
> > > + break;
> > > +
> > > + case ADDR_EXPR:
> > > + if (sra_mode == SRA_MODE_EARLY_IPA)
> > > + disqualify_base_of_expr (TREE_OPERAND (expr, 0),
> > > + "Is used in an ADDR_EXPR.");
> > > break;
> > >
> > > default:
> > > @@ -688,7 +838,7 @@ build_access_from_expr (tree *expr_ptr,
> > > gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, bool write,
> > > void *data ATTRIBUTE_UNUSED)
> > > {
> > > - return build_access_from_expr_1 (expr_ptr, write) != NULL;
> > > + return build_access_from_expr_1 (expr_ptr, gsi_stmt (*gsi), write) != NULL;
> > > }
> > >
> > > /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
> > > @@ -699,7 +849,8 @@ build_access_from_expr (tree *expr_ptr,
> > > static bool
> > > disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
> > > {
> > > - if (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt))
> > > + if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
> > > + && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
> > > {
> > > disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
> > > if (rhs)
> > > @@ -731,8 +882,26 @@ build_accesses_from_assign (gimple *stmt
> > > tree *lhs_ptr, *rhs_ptr;
> > > struct access *lacc, *racc;
> > >
> > > - if (!gimple_assign_single_p (stmt))
> > > - return SRA_SA_NONE;
> > > + if (sra_mode == SRA_MODE_EARLY_IPA)
> > > + {
> > > + if (TREE_CODE (gimple_assign_rhs1 (stmt)) == CONSTRUCTOR)
> > > + {
> > > + disqualify_base_of_expr (gimple_assign_lhs (stmt),
> > > + "Assignment to a constructor.");
> >
> > "... from a constructor."
>
> Right. But so far everything works with this special handling
> removed. I don't remember what problems I had with constructors but
> hopefully they are gone.
It can be only zeroing, so as long as that is preserved...
> >
> > > + return SRA_SA_NONE;
> > > + }
> > > +
> > > + if (!gimple_assign_single_p (stmt))
> > > + {
> > > + disqualify_direct_ptr_params (gimple_assign_rhs1 (stmt));
> > > + if (gimple_assign_rhs2 (stmt))
> > > + disqualify_direct_ptr_params (gimple_assign_rhs2 (stmt));
> > > + return SRA_SA_NONE;
> > > + }
> >
> > This again looks like poor factoring to me.
>
> Why? This is the only place where I handle two operand assigns and I
> need to disqualify parameters if I find direct uses of default def ssa
> nemes in them. I could facter more by calling
>
> walk_gimple_op (stmt, disqualify_all_direct_ptr_params, NULL);
>
> on such statements but you don't seem to like that either.
Yeah... ;) Maybe my suggestions in the follow-up mails make
some things here redundant...
>
> >
> > > + }
> > > + else
> > > + if (!gimple_assign_single_p (stmt))
> > > + return SRA_SA_NONE;
> > >
> > > lhs_ptr = gimple_assign_lhs_ptr (stmt);
> > > rhs_ptr = gimple_assign_rhs1_ptr (stmt);
> > > @@ -740,10 +909,11 @@ build_accesses_from_assign (gimple *stmt
> > > if (disqualify_ops_if_throwing_stmt (stmt, *lhs_ptr, *rhs_ptr))
> > > return SRA_SA_NONE;
> > >
> > > - racc = build_access_from_expr_1 (rhs_ptr, false);
> > > - lacc = build_access_from_expr_1 (lhs_ptr, true);
> > > + racc = build_access_from_expr_1 (rhs_ptr, stmt, false);
> > > + lacc = build_access_from_expr_1 (lhs_ptr, stmt, true);
> > >
> > > if (lacc && racc
> > > + && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
> > > && !lacc->grp_unscalarizable_region
> > > && !racc->grp_unscalarizable_region
> > > && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
> > > @@ -766,6 +936,52 @@ build_accesses_from_assign (gimple *stmt
> > > return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
> > > }
> > >
> > > +/* If ANALYSIS_STAGE is true disqualify all parameters that have their address
> > > + taken in a phi node of basic block BB and, if non-NULL, call HANDLE_SSA_DEFS
> > > + on each such phi node. Return true iff any call to HANDLE_SSA_DEFS did
> > > + so. */
> >
> > Do you at any point handle address takens on params? If not why not
> > check TREE_ADDRESSABLE on the param? Note that you will never
> > see ¶m->x in PHI nodes.
> >
> > That said, the following function looks superfluous to me.
>
> It's certainly better than handling ADDR_EXPRs in gimple_val's.
> However, I still have to have a look at the SSA_NAMEs in the PHI nodes
> to check whether there are any default def parm ssa names and
> re-create SSA_NAME when removing a parameter.
If you remove a parameter then there should be no uses in the function,
no? Or do you mean the case where you replace a pointer argument
with pointed-to pieces?
If it is unused parameter removal you could simply leave the default
def in PHI nodes - they will now be uninitialized uses, but you
better have proven that they were before anyway. Or maybe I am
confused here ...
> >
> > > +static bool
> > > +scan_phi_nodes (basic_block bb, bool analysis_stage,
> > > + bool (*handle_ssa_defs)(gimple, void *), void *data)
> > > +{
> > > + gimple_stmt_iterator gsi;
> > > + bool ret = false;
> > > + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> > > + {
> > > + gimple phi = gsi_stmt (gsi);
> > > + use_operand_p arg_p;
> > > + ssa_op_iter i;
> > > + bool any = false;
> > > +
> > > + if (analysis_stage)
> > > + FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
> > > + {
> > > + tree op = USE_FROM_PTR (arg_p);
> > > + if (TREE_CODE (op) == ADDR_EXPR)
> > > + {
> > > + op = TREE_OPERAND (op, 0);
> > > + if (DECL_P (op))
> > > + disqualify_candidate (op,
> > > + "Address taken in a phi node.");
> > > + }
> > > + else
> > > + disqualify_direct_ptr_params (op);
> > > + }
> > > +
> > > + if (handle_ssa_defs)
> > > + ret |= handle_ssa_defs (phi, data);
> > > + if (any)
> > > + {
> > > + ret = true;
> > > +
> > > + if (!analysis_stage)
> > > + update_stmt (phi);
> > > + }
> > > + }
> > > + return ret;
> > > +}
> > > +
> > > /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
> > > GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
> > >
> > > @@ -811,6 +1027,9 @@ scan_function (bool (*scan_expr) (tree *
> > > {
> > > bool bb_changed = false;
> > >
> > > + if (sra_mode == SRA_MODE_EARLY_IPA)
> > > + scan_phi_nodes (bb, analysis_stage, handle_ssa_defs, data);
> > > +
> > > gsi = gsi_start_bb (bb);
> > > while (!gsi_end_p (gsi))
> > > {
> > > @@ -818,6 +1037,8 @@ scan_function (bool (*scan_expr) (tree *
> > > enum scan_assign_result assign_result;
> > > bool any = false, deleted = false;
> > >
> > > + if (stmt_can_throw_external (stmt))
> > > + encountered_external_throw = true;
> > > switch (gimple_code (stmt))
> > > {
> > > case GIMPLE_RETURN:
> > > @@ -835,6 +1056,11 @@ scan_function (bool (*scan_expr) (tree *
> > > break;
> > >
> > > case GIMPLE_CALL:
> > > + if (analysis_stage
> > > + && (gimple_call_fndecl (stmt)
> > > + == built_in_decls[BUILT_IN_VA_START]))
> > > + encountered_va_start = true;
> >
> > So, va-start is special exactly why? Shouldn't you instead simply
> > disqualify all functions with varargs only or do you want to
> > catch functions with a va_list param as well?
>
> I thought that this was a reliable way of detecting any uses of
> variable number of parameters.
>
> However, recently I have come accross this patch:
>
> http://gcc.gnu.org/ml/gcc-patches/2009-06/msg02049.html
>
> and will try using cfun->stdarg flag instead for this purpose. On the
> other hand, the patch also scans the function body in order to detect
> builtin function __builtin_apply_args. It seems that I also should
> not touch parameters of a function calling this one. So I am about to
> rework the code that way too.
Ok.
> >
> > > /* Operands must be processed before the lhs. */
> > > for (i = 0; i < gimple_call_num_args (stmt); i++)
> > > {
> > > @@ -873,19 +1099,21 @@ scan_function (bool (*scan_expr) (tree *
> > > }
> > >
> > > default:
> > > + if (analysis_stage && sra_mode == SRA_MODE_EARLY_IPA)
> > > + walk_gimple_op (stmt, disqualify_all_direct_ptr_params, NULL);
> >
> > too much random disqualification again ;) But this complaint I already
> > had for the intra-SRA, no? ;)
>
> Yes but this time I added it only after I found it necessary so it's
> not really that random. The callback function also never recurses
> deeper into the operand trees so it should not be very costly.
>
> The reason why I added is that I need to disqualify the parameter in
> cases like the following:
>
> int foo (int *parm)
> {
> a = *parm;
> if (parm == some_other_pointer)
> ...
> }
>
> So I need to check GIMPLE_COND. And probably also GIMPLE_SWITCH. And
> maybe others + each future new statement types that might do something
> with pointer SSA_NAMES.
>
> Alternatively, I can check all gimple kinds that somehow use SSA_NAMEs
> individually.
Yes, see my followup mail suggestion.
> >
> > > break;
> > > }
> > >
> > > if (any)
> > > {
> > > ret = true;
> > > - bb_changed = true;
> > >
> > > if (!analysis_stage)
> > > {
> > > + bb_changed = true;
> > > update_stmt (stmt);
> > > - if (!stmt_could_throw_p (stmt))
> > > - remove_stmt_from_eh_region (stmt);
> > > + if (sra_mode == SRA_MODE_EARLY_IPA)
> > > + maybe_clean_or_replace_eh_stmt (stmt, stmt);
> >
> > No need for the other SRAs? Why would you ever be able to SRA
> > sth whos access may throw?
>
> The problem with intra-SRAing accesses which may throw is that I may
> end up adding statements after the one in question. That is not
> possible because the throwing access has to be the last one in its BB.
> With intra-SRA I never need to care for sub-accesses because they
> don't exist and so never need to append any statements.
>
> By SRAing accesses that may throw I simply push the possibility to
> throw to the callers. The dominator check should also make sure I
> don't introduce any new exceptions.
>
> In fact, I believe I removed the eh handling from intra-SRA at your
> request.
Probably.
> >
> > > }
> > > }
> > > if (deleted)
> > > @@ -896,7 +1124,7 @@ scan_function (bool (*scan_expr) (tree *
> > > ret = true;
> > > }
> > > }
> > > - if (!analysis_stage && bb_changed)
> > > + if (!analysis_stage && bb_changed && sra_mode == SRA_MODE_EARLY_IPA)
> > > gimple_purge_dead_eh_edges (bb);
> >
> > Likewise.
> >
> > > }
> > >
> > > @@ -2382,6 +2610,1003 @@ struct gimple_opt_pass pass_sra_early =
> > > }
> > > };
> > >
> > > +
> > > +/* Identify candidates for reduction for IPA-SRA based on their type and mark
> > > + them in candidate_bitmap. Note that these do not necessarily include
> > > + parameter which are unused and thus can be removed. Return true iff any
> > > + such candidate has been found. */
> > > +static bool
> > > +find_param_candidates (void)
> > > +{
> > > + tree parm;
> > > + int count = 0;
> > > + bool ret = false;
> > > +
> > > + for (parm = DECL_ARGUMENTS (current_function_decl);
> > > + parm;
> > > + parm = TREE_CHAIN (parm))
> > > + {
> > > + tree type;
> > > +
> > > + count++;
> > > + if (TREE_THIS_VOLATILE (parm))
> > > + continue;
> > > +
> > > + type = TREE_TYPE (parm);
> > > + if (POINTER_TYPE_P (type))
> > > + {
> > > + type = TREE_TYPE (type);
> > > +
> > > + if ((!is_gimple_reg_type (type) && !AGGREGATE_TYPE_P (type))
> >
> > is_gimple_reg_type is !AGGREGATE_TYPE_P () at the moment, so the
> > above cannot be true ;)
>
> Hm, I wonder how that got there... but naturally the pass works
> without it.
>
> >
> > > + || TREE_CODE (type) == FUNCTION_TYPE
> > > + || TYPE_VOLATILE (type))
> > > + continue;
> > > + }
> > > + else if (!AGGREGATE_TYPE_P (type))
> > > + continue;
> >
> > ok, so unused scalar parameters that are not pointers are dealt with
> > in some other way?
>
> Yes. The reason is that they can be identified just by looking at the
> declaration and seeing it has no default def SSA name. So I do that
> test. But I will re-add a test here too so that we can bail out early
> if there's evidently nothing to do.
>
> >
> > > + if (!COMPLETE_TYPE_P (type)
> > > + || TREE_ADDRESSABLE (type)
> > > + || !host_integerp (TYPE_SIZE (type), 1)
> > > + || tree_low_cst (TYPE_SIZE (type), 1) == 0)
> > > + continue;
> > > +
> > > + if (AGGREGATE_TYPE_P (type)
> > > + && type_internals_preclude_sra_p (type))
> > > + continue;
> > > +
> > > + bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
> > > + ret = true;
> > > + if (dump_file)
> > > + {
> > > + fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
> > > + print_generic_expr (dump_file, parm, 0);
> > > + fprintf (dump_file, "\n");
> > > + }
> > > + }
> > > +
> > > + func_param_count = count;
> > > + return ret;
> > > +}
> >
> > Comment missing before function.
>
> I see.
>
> >
> > > +static bool
> > > +mark_maybe_modified (tree ref ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
> > > + void *data)
> > > +{
> > > + struct access *repr = (struct access *) data;
> > > +
> > > + repr->grp_maybe_modified = 1;
> > > + return true;
> > > +}
> > > +
> > > +
> > > +/* Analyze what representatives (in linked lists accessible from
> > > + REPRESENTATIVES) can be modified by side effects of statements in the
> > > + current function. */
> > > +
> > > +static void
> > > +analyze_modified_params (VEC (access_p, heap) *representatives)
> > > +{
> > > + int i;
> > > +
> > > + for (i = 0; i < func_param_count; i++)
> > > + {
> > > + struct access *repr = VEC_index (access_p, representatives, i);
> > > + VEC (access_p, heap) *access_vec;
> > > + int j, access_count;
> > > + tree parm;
> > > +
> > > + if (!repr || no_accesses_p (repr))
> > > + continue;
> > > + parm = repr->base;
> > > + if (!POINTER_TYPE_P (TREE_TYPE (parm))
> > > + || repr->grp_maybe_modified)
> > > + continue;
> > > +
> > > + access_vec = get_base_access_vector (parm);
> > > + access_count = VEC_length (access_p, access_vec);
> > > + for (j = 0; j < access_count; j++)
> > > + {
> > > + struct access *access;
> > > + access = VEC_index (access_p, access_vec, j);
> > > +
> > > + walk_aliased_vdefs (access->expr, gimple_vuse (access->stmt),
> > > + mark_maybe_modified, repr, NULL);
> >
> > Wow, this is going to be expensive.
>
> I try to make sure this is run only when necessary.
>
> > And I don't understand
> > what you are doing here anyway. You seem to be marking repr (the
> > representative for a param) as modified whenever you find a
> > reaching definition of an access of it (the base access vector includes
> > stores, does it?).
>
> Yes. And yes, I was doing this for stores too which is I understand
> is wrong.
>
> >
> > I don't see how this can be complete. As you handle pointer-to-struct
> > params you can get aliases and so need to walk _all_ accesses, not
> > just that with the exact same base as the param. Or do you think
> > you have excluded aliases somehow? Imagine
> >
> > int foo (struct X *p, struct X *q)
> > {
> > q->x = 0;
> > return p->x;
> > }
> >
> > you cannot pass p->x instead of p.
>
> Unfortunately, I don't really understand the above, I am probably not
> excluding anything. As you have noted in the previous paragraph, I
> call walk_aliased_vdefs for all access expressions of the parameter, I
> thought that the walker function would be called for all references
> that might clobber it, including the one in your example. But perhaps
> I don't understand what parameters walk_aliased_vdefs expects. What
> would I have to do to handle the example above? access->base?
Yes, walk_aliased_vdefs would reach q->x = 0 when walking from the
read of p->x. I am mainly confused about what the base access vector
contains. I would expect that it for ipa-sra contains only reads
that may be scalarized (so, no direct stores anywhere). Then what
needs to be checked is if there are any other stores that may
alias those.
Now you have
for each function param
for each load from that param
walk_aliased_vdefs ()
which indeed looks correct on a second thought. You could make
the walking cheaper (note I reworked the walk_aliased_vdefs interface
slightly...) by not doing the walk for all accesses but for the
base only - that would make it
for each function param
walk_aliased_vdefs (base-of-param)
which would of course not catch
struct X { int i; int j } *p;
foo (struct X *q)
{
store p->j;
load q->i;
}
anymore where you could pass q->i instead of q.
> The only user of this function so far is DCE. I haven't read it
> top-down but I don't see what i do differently.
>
> >
> > > + if (repr->grp_maybe_modified)
> > > + break;
> > > + }
> > > + }
> > > +}
> > > +
> > > +/* Process BB which is a dominator of EXIT for parameter PARM by searching for
> > > + an access to parm that dereference it and if there is one, marking all
> > > + accesses to that or smaller offset as possible to dereference. */
> >
> > I think we discussed at the summit that this sounds fishy. What you
> > need to prove is that there is that on every path from function entry
> > to exit there is at least one dereference of parm.
>
> Yes.
>
> >
> > This is trivially the case if you find one dereference that
> > post-dominates the entry basic-block and dominates the exit
> > basic-block
>
> If on the way to theat BB there is a loop which might never end, then
> I still might introduce a segfault to a program by moving it before
> that infinite loop. So I need to add fake edges to the loops,
> meaning, this is where the function might also "stop" progressing.
>
> I also do not understand why post-dominating the entry block is
> necessary too. If some block dominates the exit then it is surely on
> all paths from the entry to exit, or not?
No. Consider
if (foo)
abort ();
<bb x>
return;
bb x does dominate exit but does not post-dominate the entry. With
post-dominators I believe you can get away without the fake edges.
> > (which is only not true if there is no path to the
> > exit at all).
>
> No, a BB may not dominate the exit and still there may be a plenty of
> paths from it to the exit... the obvious scenario is the diamond one.
> Or am I somehow seriously confused here too?
I was refering to a block that post-dominates the entry but not
dominates exit. I think that can only happen if there are multiple
entries ...
But again, my suggestion was to simplify the logic by only relying
on post-dominance info which avoids the fake edges.
> > It might be true in non-trivial ways as well,
> > but likely proving it would be equivalent to solving the halting
> > problem.
>
> Sure, I want a reasonably fast conservative approximation.
>
> >
> > > +static void
> > > +process_dominator_bb (tree parm, basic_block bb)
> > > +{
> > > + int i, access_count;
> > > + VEC (access_p, heap) *access_vec;
> > > + bool hit = false;
> > > + HOST_WIDE_INT offset = 0;
> > > +
> > > + access_vec = get_base_access_vector (parm);
> > > + if (!access_vec)
> > > + return;
> > > + access_count = VEC_length (access_p, access_vec);
> > > +
> > > + for (i = 0; i < access_count; i++)
> > > + {
> > > + struct access *access = VEC_index (access_p, access_vec, i);
> > > +
> > > + if (access->bb != bb)
> > > + continue;
> > > +
> > > + hit = true;
> > > + if (access->offset > offset)
> > > + offset = access->offset;
> > > + }
> > > +
> > > + if (!hit)
> > > + return;
> > > +
> > > + for (i = 0; i < access_count; i++)
> > > + {
> > > + struct access *access = VEC_index (access_p, access_vec, i);
> > > +
> > > + if (access->offset <= offset)
> > > + access->always_safe = 1;
> > > + }
> > > + return;
> > > +}
> > > +
> > > +/* Determine whether we would need to add fake edges in order to guarantee
> > > + dereference legality in callers. See the fixme in a comment in
> > > + analyze_caller_dereference_legality for some insight why we do not actually
> > > + add the edges. */
> > > +static bool
> > > +fake_edges_required_p (void)
> > > +{
> > > + basic_block bb;
> > > +
> > > + if (encountered_external_throw)
> > > + return true;
> > > +
> > > + FOR_EACH_BB (bb)
> > > + {
> > > + edge_iterator ei;
> > > + edge e;
> > > +
> > > + FOR_EACH_EDGE (e, ei, bb->succs)
> > > + {
> > > + if (e->flags & EDGE_DFS_BACK)
> >
> > This flag is not always up-to-date.
>
> Is that documented somewhere? How can I check whether it si up to
> date and/or bring it up to date?
there is mark_dfs_back_edges, various comments before users of that
function suggest that EDGE_DFS_BACK may be stale or incomplete.
Maybe someone else can confirm this.
> >
> > > + return true;
> > > + }
> > > + }
> > > + return false;
> > > +}
> > > +
> > > +/* Determine what reduced parameters passed by reference are definitely
> > > + dereferenced so that the dereferencing can be safely moved to the caller. */
> > > +
> > > +static void
> > > +analyze_caller_dereference_legality (void)
> > > +{
> > > + basic_block entry = ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun);
> > > + basic_block bb = EXIT_BLOCK_PTR_FOR_FUNCTION (cfun);
> > > +
> > > + /* FIXME: Dominance does not work for the EXIT block. Until this is fixed,
> > > + we can use instead it's only predecessor If it has only one. In other
> > > + cases, we'll just check the first basic block.
> > > +
> > > + Moreover, when there are statements which can throw externally or loops
> > > + (which might just never terminate) we would normally need to add a fake
> > > + edge from such block to the exit block. That would, however, make the
> > > + exit block have multiple predecessors and so in such cases, we also just
> > > + check the first basic block.
> > > + */
> > > + if (!single_pred_p (bb) || fake_edges_required_p ())
> > > + {
> > > + tree parm;
> > > + for (parm = DECL_ARGUMENTS (current_function_decl);
> > > + parm;
> > > + parm = TREE_CHAIN (parm))
> > > + {
> > > + if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
> > > + process_dominator_bb (parm, single_succ (entry));
> >
> > no need to do this if parm is not a pointer.
>
> I see.
>
> My current WIP patch is below. The dereferencing-legality checks and
> especially the aliasing detection are only slightly amended. The rest
> of the comments should be addressed. It's currently bootstrapping but
> I expect it to bootstrap and test fine (the last round did and I did
> not make any big changes since then).
>
> I haven't updated the change log yet.
>
> A context diff (converted from the unified one by emacs) is attached.
Thanks. Did you consider simplifying of the disqualification via
walking the immediate uses of pointer arguments?
Thanks,
Richard.
> Thanks a lot,
>
> Martin
>
>
>
> Index: mine/gcc/tree-sra.c
> ===================================================================
> --- mine.orig/gcc/tree-sra.c
> +++ mine/gcc/tree-sra.c
> @@ -78,6 +78,7 @@ along with GCC; see the file COPYING3.
> #include "tm.h"
> #include "tree.h"
> #include "gimple.h"
> +#include "cgraph.h"
> #include "tree-flow.h"
> #include "ipa-prop.h"
> #include "diagnostic.h"
> @@ -89,8 +90,9 @@ along with GCC; see the file COPYING3.
> #include "flags.h"
>
> /* Enumeration of all aggregate reductions we can do. */
> -enum sra_mode { SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
> - SRA_MODE_INTRA }; /* late intraprocedural SRA */
> +enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */
> + SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */
> + SRA_MODE_INTRA }; /* late intraprocedural SRA */
>
> /* Global variable describing which aggregate reduction we are performing at
> the moment. */
> @@ -128,6 +130,9 @@ struct access
> /* Type. */
> tree type;
>
> + /* The statement this access belongs to. */
> + gimple stmt;
> +
> /* Next group representative for this aggregate. */
> struct access *next_grp;
>
> @@ -156,6 +161,9 @@ struct access
>
> /* Is this particular access write access? */
> unsigned write : 1;
> + /* in IPA-SRA, is it guaranteed that an access to this or bigger offset is
> + always performed when the function is run? */
> + unsigned always_safe : 1;
>
> /* Is this access currently in the work queue? */
> unsigned grp_queued : 1;
> @@ -178,11 +186,18 @@ struct access
> /* Does this access and/or group contain a write access through a
> BIT_FIELD_REF? */
> unsigned grp_partial_lhs : 1;
> -
> /* Set when a scalar replacement should be created for this variable. We do
> the decision and creation at different places because create_tmp_var
> cannot be called from within FOR_EACH_REFERENCED_VAR. */
> unsigned grp_to_be_replaced : 1;
> +
> + /* Is it possible that the group refers to data which might be (directly or
> + otherwise) modified? */
> + unsigned grp_maybe_modified : 1;
> + /* Set when this is a representative of a pointer to scalar (i.e. by
> + reference) parameter which we consider for turning into a plain scalar
> + (i.e. a by value parameter). */
> + unsigned grp_scalar_ptr : 1;
> };
>
> typedef struct access *access_p;
> @@ -217,6 +232,27 @@ static struct obstack name_obstack;
> propagated to their assignment counterparts. */
> static struct access *work_queue_head;
>
> +/* Number of parameters of the analyzed function when doing early ipa SRA. */
> +static int func_param_count;
> +
> +/* scan_function sets the following to true if it encounters a call to
> + __builtin_apply_args. */
> +static bool encountered_apply_args;
> +/* scan_function sets the following to true whenever it encounters a statement
> + that can throw externally. */
> +static bool encountered_external_throw;
> +
> +/* Representative of no accesses at all. */
> +static struct access no_accesses_representant;
> +
> +/* Predicate to test the special value. */
> +
> +static inline bool
> +no_accesses_p (struct access *access)
> +{
> + return access == &no_accesses_representant;
> +}
> +
> /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true,
> representative fields are dumped, otherwise those which only describe the
> individual access are. */
> @@ -263,13 +299,15 @@ dump_access (FILE *f, struct access *acc
> if (grp)
> fprintf (f, ", grp_write = %d, grp_read = %d, grp_covered = %d, "
> "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, "
> - "grp_partial_lhs = %d, grp_to_be_replaced = %d\n",
> + "grp_partial_lhs = %d, grp_to_be_replaced = %d, "
> + "grp_maybe_modified = %d\n",
> access->grp_write, access->grp_read, access->grp_covered,
> access->grp_unscalarizable_region, access->grp_unscalarized_data,
> - access->grp_partial_lhs, access->grp_to_be_replaced);
> + access->grp_partial_lhs, access->grp_to_be_replaced,
> + access->grp_maybe_modified);
> else
> - fprintf (f, ", write = %d, grp_partial_lhs = %d\n", access->write,
> - access->grp_partial_lhs);
> + fprintf (f, ", write = %d, grp_partial_lhs = %d, always_safe = %d\n",
> + access->write, access->grp_partial_lhs, access->always_safe);
> }
>
> /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */
> @@ -465,6 +503,8 @@ sra_initialize (void)
> link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16);
> base_access_vec = pointer_map_create ();
> memset (&sra_stats, 0, sizeof (sra_stats));
> + encountered_apply_args = false;
> + encountered_external_throw = false;
> }
>
> /* Hook fed to pointer_map_traverse, deallocate stored vectors. */
> @@ -554,34 +594,76 @@ type_internals_preclude_sra_p (tree type
> }
> }
>
> +/* If T is an SSA_NAME, return NULL if it is not a default def or return its
> + base variable if it is. Return T if it is not an SSA_NAME. */
> +
> +static tree
> +get_ssa_base_param (tree t)
> +{
> + if (TREE_CODE (t) == SSA_NAME)
> + {
> + if (SSA_NAME_IS_DEFAULT_DEF (t))
> + return SSA_NAME_VAR (t);
> + else
> + return NULL_TREE;
> + }
> + return t;
> +}
> +
> /* Create and insert access for EXPR. Return created access, or NULL if it is
> not possible. */
>
> static struct access *
> -create_access (tree expr, bool write)
> +create_access (tree expr, gimple stmt, bool write)
> {
> struct access *access;
> void **slot;
> VEC (access_p,heap) *vec;
> HOST_WIDE_INT offset, size, max_size;
> tree base = expr;
> - bool unscalarizable_region = false;
> + bool ptr, unscalarizable_region = false;
>
> base = get_ref_base_and_extent (expr, &offset, &size, &max_size);
>
> + if (sra_mode == SRA_MODE_EARLY_IPA && TREE_CODE (base) == INDIRECT_REF)
> + {
> + base = get_ssa_base_param (TREE_OPERAND (base, 0));
> + if (!base)
> + return NULL;
> + ptr = true;
> + }
> + else
> + ptr = false;
> +
> if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base)))
> return NULL;
>
> - if (size != max_size)
> + if (sra_mode == SRA_MODE_EARLY_IPA)
> {
> - size = max_size;
> - unscalarizable_region = true;
> + if (size < 0 || size != max_size)
> + {
> + disqualify_candidate (base, "Encountered a variable sized access.");
> + return NULL;
> + }
> + if ((offset % BITS_PER_UNIT) != 0 || (size % BITS_PER_UNIT) != 0)
> + {
> + disqualify_candidate (base,
> + "Encountered an acces not aligned to a byte.");
> + return NULL;
> + }
> }
> -
> - if (size < 0)
> + else
> {
> - disqualify_candidate (base, "Encountered an unconstrained access.");
> - return NULL;
> + if (size != max_size)
> + {
> + size = max_size;
> + unscalarizable_region = true;
> + }
> + if (size < 0)
> + {
> + disqualify_candidate (base, "Encountered an unconstrained access.");
> + return NULL;
> + }
> }
>
> access = (struct access *) pool_alloc (access_pool);
> @@ -594,6 +676,7 @@ create_access (tree expr, bool write)
> access->type = TREE_TYPE (expr);
> access->write = write;
> access->grp_unscalarizable_region = unscalarizable_region;
> + access->stmt = stmt;
>
> slot = pointer_map_contains (base_access_vec, base);
> if (slot)
> @@ -619,16 +702,54 @@ disqualify_base_of_expr (tree t, const c
> while (handled_component_p (t))
> t = TREE_OPERAND (t, 0);
>
> - if (DECL_P (t))
> + if (sra_mode == SRA_MODE_EARLY_IPA)
> + {
> + if (INDIRECT_REF_P (t))
> + t = TREE_OPERAND (t, 0);
> + t = get_ssa_base_param (t);
> + }
> +
> + if (t && DECL_P (t))
> disqualify_candidate (t, reason);
> }
>
> +/* See if OP contains a direct use use of a pointer parameter or an ADDR_EXPR
> + of the parameter declaration. If so, disqualify the parameter. This
> + function is intended to handle gimple_val uses of parameters which are bases
> + for disqualification. */
> +
> +/* !!! */
> +
> +static bool
> +disqualify_direct_param_use (tree op)
> +{
> + op = get_ssa_base_param (op);
> + if (op && TREE_CODE (op) == PARM_DECL && POINTER_TYPE_P (TREE_TYPE (op)))
> + {
> + disqualify_candidate (op, " Direct use of its pointer value. ");
> + return true;
> + }
> + return false;
> +}
> +
> +/* A callback for walk_gimple_op. Disqualifies SSA_NAMEs of default_defs of
> + params and does not descend any further into the tree structure. */
> +
> +static tree
> +disqualify_all_direct_ptr_params (tree *tp, int *walk_subtrees,
> + void *data ATTRIBUTE_UNUSED)
> +{
> + *walk_subtrees = 0;
> + disqualify_direct_param_use (*tp);
> + return NULL_TREE;
> +}
> +
> /* Scan expression EXPR and create access structures for all accesses to
> candidates for scalarization. Return the created access or NULL if none is
> created. */
>
> static struct access *
> -build_access_from_expr_1 (tree *expr_ptr, bool write)
> +build_access_from_expr_1 (tree *expr_ptr, gimple stmt, bool write)
> {
> struct access *ret = NULL;
> tree expr = *expr_ptr;
> @@ -644,6 +765,9 @@ build_access_from_expr_1 (tree *expr_ptr
> else
> partial_ref = false;
>
> + if (sra_mode == SRA_MODE_EARLY_IPA)
> + disqualify_direct_param_use (expr);
> +
> /* We need to dive through V_C_Es in order to get the size of its parameter
> and not the result type. Ada produces such statements. We are also
> capable of handling the topmost V_C_E but not any of those buried in other
> @@ -660,13 +784,23 @@ build_access_from_expr_1 (tree *expr_ptr
>
> switch (TREE_CODE (expr))
> {
> + case INDIRECT_REF:
> + if (sra_mode != SRA_MODE_EARLY_IPA)
> + return NULL;
> + /* fall through */
> case VAR_DECL:
> case PARM_DECL:
> case RESULT_DECL:
> case COMPONENT_REF:
> case ARRAY_REF:
> case ARRAY_RANGE_REF:
> - ret = create_access (expr, write);
> + ret = create_access (expr, stmt, write);
> + break;
> +
> + case ADDR_EXPR:
> + if (sra_mode == SRA_MODE_EARLY_IPA)
> + disqualify_base_of_expr (TREE_OPERAND (expr, 0),
> + "Is used in an ADDR_EXPR.");
> break;
>
> default:
> @@ -688,7 +822,7 @@ build_access_from_expr (tree *expr_ptr,
> gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, bool write,
> void *data ATTRIBUTE_UNUSED)
> {
> - return build_access_from_expr_1 (expr_ptr, write) != NULL;
> + return build_access_from_expr_1 (expr_ptr, gsi_stmt (*gsi), write) != NULL;
> }
>
> /* Disqualify LHS and RHS for scalarization if STMT must end its basic block in
> @@ -699,7 +833,8 @@ build_access_from_expr (tree *expr_ptr,
> static bool
> disqualify_ops_if_throwing_stmt (gimple stmt, tree lhs, tree rhs)
> {
> - if (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt))
> + if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
> + && (stmt_can_throw_internal (stmt) || stmt_ends_bb_p (stmt)))
> {
> disqualify_base_of_expr (lhs, "LHS of a throwing stmt.");
> if (rhs)
> @@ -731,8 +866,20 @@ build_accesses_from_assign (gimple *stmt
> tree *lhs_ptr, *rhs_ptr;
> struct access *lacc, *racc;
>
> - if (!gimple_assign_single_p (stmt))
> - return SRA_SA_NONE;
> + if (sra_mode == SRA_MODE_EARLY_IPA)
> + {
> + /* !!! if passes testing, rework conditions */
> + if (!gimple_assign_single_p (stmt))
> + {
> + disqualify_direct_param_use (gimple_assign_rhs1 (stmt));
> + if (gimple_assign_rhs2 (stmt))
> + disqualify_direct_param_use (gimple_assign_rhs2 (stmt));
> + return SRA_SA_NONE;
> + }
> + }
> + else
> + if (!gimple_assign_single_p (stmt))
> + return SRA_SA_NONE;
>
> lhs_ptr = gimple_assign_lhs_ptr (stmt);
> rhs_ptr = gimple_assign_rhs1_ptr (stmt);
> @@ -740,10 +887,11 @@ build_accesses_from_assign (gimple *stmt
> if (disqualify_ops_if_throwing_stmt (stmt, *lhs_ptr, *rhs_ptr))
> return SRA_SA_NONE;
>
> - racc = build_access_from_expr_1 (rhs_ptr, false);
> - lacc = build_access_from_expr_1 (lhs_ptr, true);
> + racc = build_access_from_expr_1 (rhs_ptr, stmt, false);
> + lacc = build_access_from_expr_1 (lhs_ptr, stmt, true);
>
> if (lacc && racc
> + && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA)
> && !lacc->grp_unscalarizable_region
> && !racc->grp_unscalarizable_region
> && AGGREGATE_TYPE_P (TREE_TYPE (*lhs_ptr))
> @@ -766,6 +914,36 @@ build_accesses_from_assign (gimple *stmt
> return (lacc || racc) ? SRA_SA_PROCESSED : SRA_SA_NONE;
> }
>
> +/* If ANALYSIS_STAGE is true disqualify all parameters that have their address
> + taken in a phi node of basic block BB and, if non-NULL, call HANDLE_SSA_DEFS
> + on each such phi node. Return true iff any call to HANDLE_SSA_DEFS did
> + so. */
> +
> +static bool
> +scan_phi_nodes (basic_block bb, bool analysis_stage,
> + bool (*handle_ssa_defs)(gimple, void *), void *data)
> +{
> + gimple_stmt_iterator gsi;
> + bool ret = false;
> + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> + {
> + gimple phi = gsi_stmt (gsi);
> + use_operand_p arg_p;
> + ssa_op_iter i;
> +
> + if (analysis_stage)
> + FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
> + {
> + tree op = USE_FROM_PTR (arg_p);
> + disqualify_direct_param_use (op);
> + }
> +
> + if (handle_ssa_defs)
> + ret |= handle_ssa_defs (phi, data);
> + }
> + return ret;
> +}
> +
> /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine
> GIMPLE_ASM operands with memory constrains which cannot be scalarized. */
>
> @@ -811,6 +989,9 @@ scan_function (bool (*scan_expr) (tree *
> {
> bool bb_changed = false;
>
> + if (sra_mode == SRA_MODE_EARLY_IPA)
> + scan_phi_nodes (bb, analysis_stage, handle_ssa_defs, data);
> +
> gsi = gsi_start_bb (bb);
> while (!gsi_end_p (gsi))
> {
> @@ -818,6 +999,8 @@ scan_function (bool (*scan_expr) (tree *
> enum scan_assign_result assign_result;
> bool any = false, deleted = false;
>
> + if (stmt_can_throw_external (stmt))
> + encountered_external_throw = true;
> switch (gimple_code (stmt))
> {
> case GIMPLE_RETURN:
> @@ -835,6 +1018,15 @@ scan_function (bool (*scan_expr) (tree *
> break;
>
> case GIMPLE_CALL:
> + if (analysis_stage)
> + {
> + tree dest = gimple_call_fndecl (stmt);
> + if (dest
> + && DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL
> + && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS)
> + encountered_apply_args = true;
> + }
> +
> /* Operands must be processed before the lhs. */
> for (i = 0; i < gimple_call_num_args (stmt); i++)
> {
> @@ -873,19 +1065,21 @@ scan_function (bool (*scan_expr) (tree *
> }
>
> default:
> + if (analysis_stage && sra_mode == SRA_MODE_EARLY_IPA)
> + walk_gimple_op (stmt, disqualify_all_direct_ptr_params, NULL);
> break;
> }
>
> if (any)
> {
> ret = true;
> - bb_changed = true;
>
> if (!analysis_stage)
> {
> + bb_changed = true;
> update_stmt (stmt);
> - if (!stmt_could_throw_p (stmt))
> - remove_stmt_from_eh_region (stmt);
> + if (sra_mode == SRA_MODE_EARLY_IPA)
> + maybe_clean_or_replace_eh_stmt (stmt, stmt);
> }
> }
> if (deleted)
> @@ -896,7 +1090,7 @@ scan_function (bool (*scan_expr) (tree *
> ret = true;
> }
> }
> - if (!analysis_stage && bb_changed)
> + if (!analysis_stage && bb_changed && sra_mode == SRA_MODE_EARLY_IPA)
> gimple_purge_dead_eh_edges (bb);
> }
>
> @@ -2395,6 +2589,1046 @@ struct gimple_opt_pass pass_sra_early =
> }
> };
>
> +
> +/* Return true iff PARM (which must be a parm_decl) is an unused scalar
> + parameter. */
> +
> +static bool
> +is_unused_scalar_param (tree parm)
> +{
> + tree name;
> + return (is_gimple_reg (parm)
> + && (!(name = gimple_default_def (cfun, parm))
> + || has_zero_uses (name)));
> +}
> +
> +/* Identify candidates for reduction for IPA-SRA based on their type and mark
> + them in candidate_bitmap. Note that these do not necessarily include
> + parameter which are unused and thus can be removed. Return true iff any
> + such candidate has been found. */
> +
> +static bool
> +find_param_candidates (void)
> +{
> + tree parm;
> + int count = 0;
> + bool ret = false;
> +
> + for (parm = DECL_ARGUMENTS (current_function_decl);
> + parm;
> + parm = TREE_CHAIN (parm))
> + {
> + tree type;
> +
> + count++;
> + if (TREE_THIS_VOLATILE (parm)
> + || TREE_ADDRESSABLE (parm))
> + continue;
> +
> + if (is_unused_scalar_param (parm))
> + {
> + ret = true;
> + continue;
> + }
> +
> + type = TREE_TYPE (parm);
> + if (POINTER_TYPE_P (type))
> + {
> + type = TREE_TYPE (type);
> +
> + if (TREE_CODE (type) == FUNCTION_TYPE
> + || TYPE_VOLATILE (type))
> + continue;
> + }
> + else if (!AGGREGATE_TYPE_P (type))
> + continue;
> +
> + if (!COMPLETE_TYPE_P (type)
> + || !host_integerp (TYPE_SIZE (type), 1)
> + || tree_low_cst (TYPE_SIZE (type), 1) == 0)
> + continue;
> +
> + if (AGGREGATE_TYPE_P (type)
> + && type_internals_preclude_sra_p (type))
> + continue;
> +
> + bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
> + ret = true;
> + if (dump_file)
> + {
> + fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
> + print_generic_expr (dump_file, parm, 0);
> + fprintf (dump_file, "\n");
> + }
> + }
> +
> + func_param_count = count;
> + return ret;
> +}
> +
> +/* Callback of walk_aliased_vdefs, marks the access passed as DATA as
> + maybe_modified. */
> +
> +static bool
> +mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
> + void *data)
> +{
> + struct access *repr = (struct access *) data;
> +
> + repr->grp_maybe_modified = 1;
> + return true;
> +}
> +
> +/* Analyze what representatives (in linked lists accessible from
> + REPRESENTATIVES) can be modified by side effects of statements in the
> + current function. */
> +
> +static void
> +analyze_modified_params (VEC (access_p, heap) *representatives)
> +{
> + int i;
> +
> + for (i = 0; i < func_param_count; i++)
> + {
> + struct access *repr = VEC_index (access_p, representatives, i);
> + VEC (access_p, heap) *access_vec;
> + int j, access_count;
> + tree parm;
> +
> + if (!repr || no_accesses_p (repr))
> + continue;
> + parm = repr->base;
> + if (!POINTER_TYPE_P (TREE_TYPE (parm))
> + || repr->grp_maybe_modified)
> + continue;
> +
> + access_vec = get_base_access_vector (parm);
> + access_count = VEC_length (access_p, access_vec);
> + for (j = 0; j < access_count; j++)
> + {
> + struct access *access;
> + ao_ref ar;
> +
> + access = VEC_index (access_p, access_vec, j);
> + if (access->write)
> + continue;
> +
> + ao_ref_init (&ar, access->expr);
> + walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
> + mark_maybe_modified, repr, NULL);
> + if (repr->grp_maybe_modified)
> + break;
> + }
> + }
> +}
> +
> +/* Process BB which is a dominator of EXIT for parameter PARM by searching for
> + an access to parm that dereference it and if there is one, marking all
> + accesses to that or smaller offset as possible to dereference. */
> +
> +static void
> +process_dominator_bb (tree parm, basic_block bb)
> +{
> + int i, access_count;
> + VEC (access_p, heap) *access_vec;
> + bool hit = false;
> + HOST_WIDE_INT offset = 0;
> +
> + access_vec = get_base_access_vector (parm);
> + if (!access_vec)
> + return;
> + access_count = VEC_length (access_p, access_vec);
> +
> + for (i = 0; i < access_count; i++)
> + {
> + struct access *access = VEC_index (access_p, access_vec, i);
> +
> + if (gimple_bb (access->stmt) != bb)
> + continue;
> +
> + hit = true;
> + if (access->offset > offset)
> + offset = access->offset;
> + }
> +
> + if (!hit)
> + return;
> +
> + for (i = 0; i < access_count; i++)
> + {
> + struct access *access = VEC_index (access_p, access_vec, i);
> +
> + if (access->offset <= offset)
> + access->always_safe = 1;
> + }
> + return;
> +}
> +
> +/* Determine whether we would need to add fake edges in order to guarantee
> + dereference legality in callers. See the fixme in a comment in
> + analyze_caller_dereference_legality for some insight why we do not actually
> + add the edges. */
> +static bool
> +fake_edges_required_p (void)
> +{
> + basic_block bb;
> +
> + if (encountered_external_throw)
> + return true;
> +
> + FOR_EACH_BB (bb)
> + {
> + edge_iterator ei;
> + edge e;
> +
> + FOR_EACH_EDGE (e, ei, bb->succs)
> + {
> + if (e->flags & EDGE_DFS_BACK)
> + return true;
> + }
> + }
> + return false;
> +}
> +
> +/* Determine what reduced parameters passed by reference are definitely
> + dereferenced so that the dereferencing can be safely moved to the caller. */
> +
> +static void
> +analyze_caller_dereference_legality (void)
> +{
> + basic_block entry = ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun);
> + basic_block bb = EXIT_BLOCK_PTR_FOR_FUNCTION (cfun);
> +
> + /* FIXME: Dominance does not work for the EXIT block. Until this is fixed,
> + we can use instead it's only predecessor If it has only one. In other
> + cases, we'll just check the first basic block.
> +
> + Moreover, when there are statements which can throw externally or loops
> + (which might just never terminate) we would normally need to add a fake
> + edge from such block to the exit block. That would, however, make the
> + exit block have multiple predecessors and so in such cases, we also just
> + check the first basic block.
> + */
> + if (!single_pred_p (bb) || fake_edges_required_p ())
> + {
> + tree parm;
> + for (parm = DECL_ARGUMENTS (current_function_decl);
> + parm;
> + parm = TREE_CHAIN (parm))
> + {
> + if (POINTER_TYPE_P (TREE_TYPE (parm))
> + && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
> + process_dominator_bb (parm, single_succ (entry));
> + }
> + return;
> + }
> +
> + bb = single_pred (bb);
> + while (bb && bb != entry)
> + {
> + tree parm;
> + for (parm = DECL_ARGUMENTS (current_function_decl);
> + parm;
> + parm = TREE_CHAIN (parm))
> + {
> + if (POINTER_TYPE_P (TREE_TYPE (parm))
> + && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
> + process_dominator_bb (parm, bb);
> + }
> +
> + bb = get_immediate_dominator (CDI_DOMINATORS, bb);
> + }
> +
> + return;
> +}
> +
> +/* Return the representative access for the parameter declaration PARM if it is
> + a scalar passed by reference which is not written to and the pointer value
> + is not used directly. Thus, if it is legal to dereference it in the caller
> + and we can rule out modifications through aliases, such parameter should be
> + turned into one passed by value. Return NULL otherwise. */
> +
> +static struct access *
> +unmodified_by_ref_scalar_representative (tree parm)
> +{
> + int i, access_count;
> + struct access *access;
> + VEC (access_p, heap) *access_vec;
> +
> + access_vec = get_base_access_vector (parm);
> + gcc_assert (access_vec);
> + access_count = VEC_length (access_p, access_vec);
> +
> + for (i = 0; i < access_count; i++)
> + {
> + access = VEC_index (access_p, access_vec, i);
> + if (access->write)
> + return NULL;
> + }
> +
> + access = VEC_index (access_p, access_vec, 0);
> + access->grp_read = 1;
> + access->grp_scalar_ptr = 1;
> + return access;
> +}
> +
> +/* Sort collected accesses for parameter PARM, identify representatives for
> + each accessed region and link them together. Return NULL if there are no
> + accesses or if there are different but overlapping accesses, return the
> + special ptr value meaning there are no accesses for this parameter if that
> + is the case and return the first representative otherwise. If non-NULL, set
> + *RO_GRP if there is a group of accesses with only read (i.e. no write)
> + accesses. */
> +
> +static struct access *
> +splice_param_accesses (tree parm, bool *ro_grp)
> +{
> + int i, j, access_count, group_count;
> + int agg_size, total_size = 0;
> + struct access *access, *res, **prev_acc_ptr = &res;
> + VEC (access_p, heap) *access_vec;
> +
> + access_vec = get_base_access_vector (parm);
> + if (!access_vec)
> + return &no_accesses_representant;
> + access_count = VEC_length (access_p, access_vec);
> +
> + /* Sort by <OFFSET, SIZE>. */
> + qsort (VEC_address (access_p, access_vec), access_count, sizeof (access_p),
> + compare_access_positions);
> +
> + if (dump_file)
> + {
> + fprintf (dump_file, "Splicing PARAM accesses for ");
> + print_generic_expr (dump_file, parm, 0);
> + fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
> + for (i = 0; i < access_count; i++)
> + dump_access (dump_file, VEC_index (access_p, access_vec, i), false);
> + }
> +
> + i = 0;
> + total_size = 0;
> + group_count = 0;
> + while (i < access_count)
> + {
> + bool modification;
> + access = VEC_index (access_p, access_vec, i);
> + modification = access->write;
> +
> + /* Access is about to become group representative unless we find some
> + nasty overlap which would preclude us from breaking this parameter
> + apart. */
> +
> + j = i + 1;
> + while (j < access_count)
> + {
> + struct access *ac2 = VEC_index (access_p, access_vec, j);
> + if (ac2->offset != access->offset)
> + {
> + /* All or nothing law for parameters. */
> + if (access->offset + access->size > ac2->offset)
> + return NULL;
> + else
> + break;
> + }
> + else if (ac2->size != access->size)
> + return NULL;
> +
> + modification |= ac2->write;
> + j++;
> + }
> +
> + group_count++;
> + access->grp_maybe_modified = modification;
> + if (!modification && ro_grp)
> + *ro_grp = true;
> + *prev_acc_ptr = access;
> + prev_acc_ptr = &access->next_grp;
> + total_size += access->size;
> + i = j;
> + }
> +
> + if (POINTER_TYPE_P (TREE_TYPE (parm)))
> + agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
> + else
> + agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
> + if (total_size >= agg_size)
> + return NULL;
> +
> + gcc_assert (group_count > 0);
> + return res;
> +}
> +
> +/* Decide whether parameters with representative accesses given by REPR should
> + be reduced into components. */
> +
> +static int
> +decide_one_param_reduction (struct access *repr)
> +{
> + int total_size, cur_parm_size, agg_size, new_param_count;
> + bool by_ref;
> + tree parm;
> +
> + parm = repr->base;
> + gcc_assert (TREE_CODE (parm) == PARM_DECL);
> + cur_parm_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (parm)), 1);
> + gcc_assert (cur_parm_size > 0);
> +
> + if (POINTER_TYPE_P (TREE_TYPE (parm)))
> + {
> + by_ref = true;
> + agg_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))), 1);
> + }
> + else
> + {
> + by_ref = false;
> + agg_size = cur_parm_size;
> + }
> +
> + if (dump_file)
> + {
> + struct access *acc;
> + fprintf (dump_file, "Evaluating PARAM group sizes for ");
> + print_generic_expr (dump_file, parm, 0);
> + fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
> + for (acc = repr; acc; acc = acc->next_grp)
> + dump_access (dump_file, acc, true);
> + }
> +
> + total_size = 0;
> + new_param_count = 0;
> +
> + for (; repr; repr = repr->next_grp)
> + {
> + gcc_assert (parm == repr->base);
> + new_param_count++;
> +
> + if (!by_ref || (!repr->grp_maybe_modified && repr->always_safe))
> + total_size += repr->size;
> + else
> + total_size += cur_parm_size;
> + }
> +
> + gcc_assert (new_param_count > 0);
> + /* FIXME: 2 probably needs to be replaced by a parameter */
> + if (total_size < agg_size
> + && total_size <= 2 * cur_parm_size)
> + {
> + if (dump_file)
> + fprintf (dump_file, " ....will be split into %i components\n",
> + new_param_count);
> + return new_param_count;
> + }
> + else
> + return 0;
> +}
> +
> +/* The order of the following enums is important, we need to do extra work for
> + UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */
> +enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
> + MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
> +
> +/* Identify representatives of all accesses to all candidate parameters for
> + IPA-SRA. Return result based on what representatives have been found. */
> +
> +static enum ipa_splicing_result
> +splice_all_param_accesses (VEC (access_p, heap) **representatives)
> +{
> + enum ipa_splicing_result result = NO_GOOD_ACCESS;
> + tree parm;
> + struct access *repr;
> +
> + *representatives = VEC_alloc (access_p, heap, func_param_count);
> +
> + for (parm = DECL_ARGUMENTS (current_function_decl);
> + parm;
> + parm = TREE_CHAIN (parm))
> + {
> + if (is_unused_scalar_param (parm))
> + {
> + VEC_quick_push (access_p, *representatives,
> + &no_accesses_representant);
> + if (result == NO_GOOD_ACCESS)
> + result = UNUSED_PARAMS;
> + }
> + else if (POINTER_TYPE_P (TREE_TYPE (parm))
> + && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
> + && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
> + {
> + repr = unmodified_by_ref_scalar_representative (parm);
> + VEC_quick_push (access_p, *representatives, repr);
> + if (repr)
> + result = UNMODIF_BY_REF_ACCESSES;
> + }
> + else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
> + {
> + bool ro_grp = false;
> + repr = splice_param_accesses (parm, &ro_grp);
> + VEC_quick_push (access_p, *representatives, repr);
> +
> + if (repr && !no_accesses_p (repr))
> + {
> + if (POINTER_TYPE_P (TREE_TYPE (parm)))
> + {
> + if (ro_grp)
> + result = UNMODIF_BY_REF_ACCESSES;
> + else if (result < MODIF_BY_REF_ACCESSES)
> + result = MODIF_BY_REF_ACCESSES;
> + }
> + else if (result < BY_VAL_ACCESSES)
> + result = BY_VAL_ACCESSES;
> + }
> + else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
> + result = UNUSED_PARAMS;
> + }
> + else
> + VEC_quick_push (access_p, *representatives, NULL);
> + }
> +
> + if (result == NO_GOOD_ACCESS)
> + {
> + VEC_free (access_p, heap, *representatives);
> + *representatives = NULL;
> + return NO_GOOD_ACCESS;
> + }
> +
> + return result;
> +}
> +
> +/* Return the index of BASE in PARMS. Abort if it i not found. */
> +
> +static inline int
> +get_param_index (tree base, VEC(tree, heap) *parms)
> +{
> + int i, len;
> +
> + len = VEC_length (tree, parms);
> + for (i = 0; i < len; i++)
> + if (VEC_index (tree, parms, i) == base)
> + return i;
> + gcc_unreachable ();
> +}
> +
> +/* Convert the decisions made at the representative level into compact
> + parameter adjustments. REPRESENTATIVES are pointers to first
> + representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
> + final number of adjustments. */
> +
> +static ipa_parm_adjustment_vec
> +turn_representatives_into_adjustments (VEC (access_p, heap) *representatives,
> + int adjustments_count)
> +{
> + VEC (tree, heap) *parms;
> + ipa_parm_adjustment_vec adjustments;
> + tree parm;
> + int i;
> +
> + gcc_assert (adjustments_count > 0);
> + parms = ipa_get_vector_of_formal_parms (current_function_decl);
> + adjustments = VEC_alloc (ipa_parm_adjustment_t, heap, adjustments_count);
> + parm = DECL_ARGUMENTS (current_function_decl);
> + for (i = 0; i < func_param_count; i++, parm = TREE_CHAIN (parm))
> + {
> + struct access *repr = VEC_index (access_p, representatives, i);
> +
> + if (!repr || no_accesses_p (repr))
> + {
> + struct ipa_parm_adjustment *adj;
> +
> + adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
> + memset (adj, 0, sizeof (*adj));
> + adj->base_index = get_param_index (parm, parms);
> + adj->base = parm;
> + if (!repr)
> + adj->copy_param = 1;
> + else
> + adj->remove_param = 1;
> + }
> + else
> + {
> + struct ipa_parm_adjustment *adj;
> + int index = get_param_index (parm, parms);
> +
> + for (; repr; repr = repr->next_grp)
> + {
> + adj = VEC_quick_push (ipa_parm_adjustment_t, adjustments, NULL);
> + memset (adj, 0, sizeof (*adj));
> + gcc_assert (repr->base == parm);
> + adj->base_index = index;
> + adj->base = repr->base;
> + adj->type = repr->type;
> + adj->offset = repr->offset;
> + adj->by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
> + && (repr->grp_maybe_modified
> + || !repr->always_safe));
> +
> + }
> + }
> + }
> + VEC_free (tree, heap, parms);
> + return adjustments;
> +}
> +
> +/* Analyze the collected accesses and produce a plan what to do with the
> + parameters in the form of adjustments, NULL meaning nothing. */
> +
> +static ipa_parm_adjustment_vec
> +analyze_all_param_acesses (void)
> +{
> + enum ipa_splicing_result repr_state;
> + bool proceed = false;
> + int i, adjustments_count = 0;
> + VEC (access_p, heap) *representatives;
> + ipa_parm_adjustment_vec adjustments;
> +
> + repr_state = splice_all_param_accesses (&representatives);
> + if (repr_state == NO_GOOD_ACCESS)
> + return NULL;
> +
> + /* If there are any parameters passed by reference which are not modified
> + directly, we need to check whether they can be modified indirectly. */
> + if (repr_state == UNMODIF_BY_REF_ACCESSES)
> + {
> + analyze_caller_dereference_legality ();
> + analyze_modified_params (representatives);
> + }
> +
> + for (i = 0; i < func_param_count; i++)
> + {
> + struct access *repr = VEC_index (access_p, representatives, i);
> +
> + if (repr && !no_accesses_p (repr))
> + {
> + if (repr->grp_scalar_ptr)
> + {
> + adjustments_count++;
> + if (!repr->always_safe || repr->grp_maybe_modified)
> + VEC_replace (access_p, representatives, i, NULL);
> + else
> + proceed = true;
> + }
> + else
> + {
> + int new_components = decide_one_param_reduction (repr);
> +
> + if (new_components == 0)
> + {
> + VEC_replace (access_p, representatives, i, NULL);
> + adjustments_count++;
> + }
> + else
> + {
> + adjustments_count += new_components;
> + proceed = true;
> + }
> + }
> + }
> + else
> + {
> + if (no_accesses_p (repr))
> + proceed = true;
> + adjustments_count++;
> + }
> + }
> +
> + if (!proceed && dump_file)
> + fprintf (dump_file, "NOT proceeding to change params.\n");
> +
> + if (proceed)
> + adjustments = turn_representatives_into_adjustments (representatives,
> + adjustments_count);
> + else
> + adjustments = NULL;
> +
> + VEC_free (access_p, heap, representatives);
> + return adjustments;
> +}
> +
> +/* If a parameter replacement identified by ADJ does not yet exist in the form
> + of declaration, create it and record it, otherwise return the previously
> + created one. */
> +
> +static tree
> +get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
> +{
> + tree repl;
> + if (!adj->new_ssa_base)
> + {
> + char *pretty_name = make_fancy_name (adj->base);
> +
> + repl = make_rename_temp (TREE_TYPE (adj->base), "ISR");
> + DECL_NAME (repl) = get_identifier (pretty_name);
> + obstack_free (&name_obstack, pretty_name);
> +
> + get_var_ann (repl);
> + add_referenced_var (repl);
> + adj->new_ssa_base = repl;
> + }
> + else
> + repl = adj->new_ssa_base;
> + return repl;
> +}
> +
> +/* Callback for scan_function. If the statement STMT defines an SSA_NAME of a
> + parameter which is to be removed because its value is not used, replace the
> + SSA_NAME with a one relating to a created VAR_DECL and replace all of its
> + uses too. DATA is a pointer to an adjustments vector. */
> +
> +static bool
> +replace_removed_params_ssa_names (gimple stmt, void *data)
> +{
> + VEC (ipa_parm_adjustment_t, heap) *adjustments;
> + tree lhs, decl;
> + int i, len;
> +
> + adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
> + if (gimple_code (stmt) == GIMPLE_PHI)
> + lhs = gimple_phi_result (stmt);
> + else if (is_gimple_assign (stmt))
> + lhs = gimple_assign_lhs (stmt);
> + else if (is_gimple_call (stmt))
> + lhs = gimple_call_lhs (stmt);
> + else
> + gcc_unreachable ();
> +
> + if (TREE_CODE (lhs) != SSA_NAME)
> + return false;
> + decl = SSA_NAME_VAR (lhs);
> + if (TREE_CODE (decl) != PARM_DECL)
> + return false;
> +
> + len = VEC_length (ipa_parm_adjustment_t, adjustments);
> + for (i = 0; i < len; i++)
> + {
> + tree repl, name;
> + struct ipa_parm_adjustment *adj;
> +
> + adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
> + if (adj->copy_param || adj->base != decl)
> + continue;
> +
> + gcc_assert (!SSA_NAME_IS_DEFAULT_DEF (lhs));
> + repl = get_replaced_param_substitute (adj);
> + name = make_ssa_name (repl, stmt);
> +
> + if (dump_file)
> + {
> + fprintf (dump_file, "replacing SSA name of removed param ");
> + print_generic_expr (dump_file, lhs, 0);
> + fprintf (dump_file, " with ");
> + print_generic_expr (dump_file, name, 0);
> + fprintf (dump_file, "\n");
> + }
> +
> + if (is_gimple_assign (stmt))
> + gimple_assign_set_lhs (stmt, name);
> + else if (is_gimple_call (stmt))
> + gimple_call_set_lhs (stmt, name);
> + else
> + gimple_phi_set_result (stmt, name);
> +
> + replace_uses_by (lhs, name);
> + return true;
> + }
> + return false;
> +}
> +
> +/* Callback for scan_function. If the expression *EXPR should be replaced by a
> + reduction of a parameter, do so. DATA is a pointer to a vector of
> + adjustments. */
> +
> +static bool
> +sra_ipa_modify_expr (tree *expr, gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED,
> + bool write ATTRIBUTE_UNUSED, void *data)
> +{
> + VEC (ipa_parm_adjustment_t, heap) *adjustments;
> + int i, len;
> + struct ipa_parm_adjustment *adj, *cand = NULL;
> + HOST_WIDE_INT offset, size, max_size;
> + tree base, src;
> +
> + adjustments = (VEC (ipa_parm_adjustment_t, heap) *) data;
> + len = VEC_length (ipa_parm_adjustment_t, adjustments);
> + while (TREE_CODE (*expr) == NOP_EXPR
> + || TREE_CODE (*expr) == VIEW_CONVERT_EXPR)
> + expr = &TREE_OPERAND (*expr, 0);
> +
> + if (handled_component_p (*expr))
> + {
> + base = get_ref_base_and_extent (*expr, &offset, &size, &max_size);
> + if (!base || size == -1 || max_size == -1)
> + return false;
> +
> + if (TREE_CODE (base) == INDIRECT_REF)
> + base = TREE_OPERAND (base, 0);
> +
> + base = get_ssa_base_param (base);
> + if (!base || TREE_CODE (base) == INTEGER_CST)
> + return false;
> + }
> + else if (TREE_CODE (*expr) == INDIRECT_REF)
> + {
> + tree tree_size;
> + base = TREE_OPERAND (*expr, 0);
> +
> + base = get_ssa_base_param (base);
> + if (!base || TREE_CODE (base) == INTEGER_CST)
> + return false;
> +
> + offset = 0;
> + tree_size = TYPE_SIZE (TREE_TYPE (base));
> + if (tree_size && host_integerp (tree_size, 1))
> + size = max_size = tree_low_cst (tree_size, 1);
> + else
> + return false;
> + }
> + else
> + return false;
> +
> + gcc_assert (DECL_P (base));
> + for (i = 0; i < len; i++)
> + {
> + adj = VEC_index (ipa_parm_adjustment_t, adjustments, i);
> +
> + if (adj->base == base &&
> + (adj->offset == offset || adj->remove_param))
> + {
> + cand = adj;
> + break;
> + }
> + }
> + if (!cand || cand->copy_param || cand->remove_param)
> + return false;
> +
> + if (cand->by_ref)
> + {
> + tree folded;
> + src = build1 (INDIRECT_REF, TREE_TYPE (TREE_TYPE (cand->reduction)),
> + cand->reduction);
> + folded = gimple_fold_indirect_ref (src);
> + if (folded)
> + src = folded;
> + }
> + else
> + src = cand->reduction;
> +
> + if (dump_file)
> + {
> + fprintf (dump_file, "About to replace expr ");
> + print_generic_expr (dump_file, *expr, 0);
> + fprintf (dump_file, " with ");
> + print_generic_expr (dump_file, src, 0);
> + fprintf (dump_file, "\n");
> + }
> +
> + if (!useless_type_conversion_p (TREE_TYPE (*expr), cand->type))
> + {
> + tree vce = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (*expr), src);
> + *expr = vce;
> + }
> + else
> + *expr = src;
> + return true;
> +}
> +
> +/* Callback for scan_function to process assign statements. Performs
> + essentially the same function like sra_ipa_modify_expr. */
> +
> +static enum scan_assign_result
> +sra_ipa_modify_assign (gimple *stmt_ptr,
> + gimple_stmt_iterator *gsi ATTRIBUTE_UNUSED, void *data)
> +{
> + gimple stmt = *stmt_ptr;
> + bool any = false;
> +
> + if (!gimple_assign_single_p (stmt))
> + return SRA_SA_NONE;
> +
> + any |= sra_ipa_modify_expr (gimple_assign_rhs1_ptr (stmt), gsi, false,
> + data);
> + any |= sra_ipa_modify_expr (gimple_assign_lhs_ptr (stmt), gsi, true, data);
> +
> + return any ? SRA_SA_PROCESSED : SRA_SA_NONE;
> +}
> +
> +/* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */
> +
> +static void
> +convert_callers (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
> +{
> + tree old_cur_fndecl = current_function_decl;
> + struct cgraph_edge *cs;
> + basic_block this_block;
> +
> + for (cs = node->callers; cs; cs = cs->next_caller)
> + {
> + current_function_decl = cs->caller->decl;
> + push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
> +
> + if (dump_file)
> + fprintf (dump_file, "Adjusting call %s -> %s\n",
> + cgraph_node_name (cs->caller),
> + cgraph_node_name (cs->callee));
> +
> + ipa_modify_call_arguments (cs, cs->call_stmt, adjustments);
> + compute_inline_parameters (cs->caller);
> +
> + pop_cfun ();
> + }
> + current_function_decl = old_cur_fndecl;
> + FOR_EACH_BB (this_block)
> + {
> + gimple_stmt_iterator gsi;
> +
> + for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
> + {
> + gimple stmt = gsi_stmt (gsi);
> + if (gimple_code (stmt) == GIMPLE_CALL
> + && gimple_call_fndecl (stmt) == node->decl)
> + {
> + if (dump_file)
> + fprintf (dump_file, "Adjusting recursive call");
> + ipa_modify_call_arguments (NULL, stmt, adjustments);
> + }
> + }
> + }
> +
> + return;
> +}
> +
> +/* Perform all the modification required in IPA-SRA for NODE to have parameters
> + as given in ADJUSTMENTS. */
> +
> +static void
> +modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
> +{
> + ipa_modify_formal_parameters (current_function_decl, adjustments, "ISRA");
> + scan_function (sra_ipa_modify_expr, sra_ipa_modify_assign,
> + replace_removed_params_ssa_names, false, adjustments);
> + convert_callers (node, adjustments);
> + cgraph_make_node_local (node);
> + return;
> +}
> +
> +/* Return false the function is apparently unsuitable for IPA-SRA based on it's
> + attributes, return true otherwise. NODE is the cgraph node of the current
> + function. */
> +
> +static bool
> +ipa_sra_preliminary_function_checks (struct cgraph_node *node)
> +{
> + if (!cgraph_node_can_be_local_p (node))
> + {
> + if (dump_file)
> + fprintf (dump_file, "Function not local to this compilation unit.\n");
> + return false;
> + }
> +
> + if (DECL_VIRTUAL_P (current_function_decl))
> + {
> + if (dump_file)
> + fprintf (dump_file, "Function is a virtual method.\n");
> + return false;
> + }
> +
> + if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
> + && node->global.size >= MAX_INLINE_INSNS_AUTO)
> + {
> + if (dump_file)
> + fprintf (dump_file, "Function too big to be made truly local.\n");
> + return false;
> + }
> +
> + if (!node->callers)
> + {
> + if (dump_file)
> + fprintf (dump_file,
> + "Function has no callers in this compilation unit.\n");
> + return false;
> + }
> +
> + if (cfun->stdarg)
> + {
> + if (dump_file)
> + fprintf (dump_file, "Function uses stdarg. \n");
> + return false;
> + }
> +
> + return true;
> +}
> +
> +/* Perform early interprocedural SRA. */
> +
> +static unsigned int
> +ipa_early_sra (void)
> +{
> + struct cgraph_node *node = cgraph_node (current_function_decl);
> + ipa_parm_adjustment_vec adjustments;
> + int ret = 0;
> +
> + if (!ipa_sra_preliminary_function_checks (node))
> + return 0;
> +
> + sra_initialize ();
> + sra_mode = SRA_MODE_EARLY_IPA;
> +
> + if (!find_param_candidates ())
> + {
> + if (dump_file)
> + fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
> + goto out;
> + }
> +
> + scan_function (build_access_from_expr, build_accesses_from_assign,
> + NULL, true, NULL);
> + if (encountered_apply_args)
> + {
> + if (dump_file)
> + fprintf (dump_file, "Function calls __builtin_apply_args().\n");
> + goto out;
> + }
> +
> + adjustments = analyze_all_param_acesses ();
> + if (!adjustments)
> + goto out;
> + if (dump_file)
> + ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
> +
> + modify_function (node, adjustments);
> + VEC_free (ipa_parm_adjustment_t, heap, adjustments);
> + ret = TODO_update_ssa;
> +
> + out:
> + sra_deinitialize ();
> + return ret;
> +}
> +
> +/* Return if early ipa sra shall be performed. */
> +static bool
> +ipa_early_sra_gate (void)
> +{
> + return flag_ipa_sra;
> +}
> +
> +struct gimple_opt_pass pass_early_ipa_sra =
> +{
> + {
> + GIMPLE_PASS,
> + "eipa_sra", /* name */
> + ipa_early_sra_gate, /* gate */
> + ipa_early_sra, /* execute */
> + NULL, /* sub */
> + NULL, /* next */
> + 0, /* static_pass_number */
> + TV_IPA_SRA, /* tv_id */
> + 0, /* properties_required */
> + 0, /* properties_provided */
> + 0, /* properties_destroyed */
> + 0, /* todo_flags_start */
> + TODO_dump_func | TODO_dump_cgraph /* todo_flags_finish */
> + }
> +};
> +
>
> struct gimple_opt_pass pass_sra =
> {
> Index: mine/gcc/tree-pass.h
> ===================================================================
> --- mine.orig/gcc/tree-pass.h
> +++ mine/gcc/tree-pass.h
> @@ -327,6 +327,7 @@ extern struct gimple_opt_pass pass_clean
> extern struct gimple_opt_pass pass_fixup_cfg;
> extern struct gimple_opt_pass pass_sra;
> extern struct gimple_opt_pass pass_sra_early;
> +extern struct gimple_opt_pass pass_early_ipa_sra;
> extern struct gimple_opt_pass pass_tail_recursion;
> extern struct gimple_opt_pass pass_tail_calls;
> extern struct gimple_opt_pass pass_tree_loop;
> Index: mine/gcc/passes.c
> ===================================================================
> --- mine.orig/gcc/passes.c
> +++ mine/gcc/passes.c
> @@ -563,6 +563,7 @@ init_optimization_passes (void)
> NEXT_PASS (pass_copy_prop);
> NEXT_PASS (pass_merge_phi);
> NEXT_PASS (pass_cd_dce);
> + NEXT_PASS (pass_early_ipa_sra);
> NEXT_PASS (pass_tail_recursion);
> NEXT_PASS (pass_convert_switch);
> NEXT_PASS (pass_cleanup_eh);
> Index: mine/gcc/Makefile.in
> ===================================================================
> --- mine.orig/gcc/Makefile.in
> +++ mine/gcc/Makefile.in
> @@ -2801,8 +2801,9 @@ tree-ssa-ccp.o : tree-ssa-ccp.c $(TREE_F
> $(TREE_DUMP_H) $(BASIC_BLOCK_H) $(TREE_PASS_H) langhooks.h \
> tree-ssa-propagate.h value-prof.h $(FLAGS_H) $(TARGET_H) $(TOPLEV_H)
> tree-sra.o : tree-sra.c $(CONFIG_H) $(SYSTEM_H) coretypes.h alloc-pool.h \
> - $(TM_H) $(TREE_H) $(GIMPLE_H) $(TREE_FLOW_H) $(IPA_PROP_H) $(DIAGNOSTIC_H) \
> - statistics.h $(TREE_DUMP_H) $(TIMEVAR_H) $(PARAMS_H) $(TARGET_H) $(FLAGS_H)
> + $(TM_H) $(TREE_H) $(GIMPLE_H) $(CGRAPH_H) $(TREE_FLOW_H) $(IPA_PROP_H) \
> + $(DIAGNOSTIC_H) statistics.h $(TREE_DUMP_H) $(TIMEVAR_H) $(PARAMS_H) \
> + $(TARGET_H) $(FLAGS_H)
> tree-switch-conversion.o : tree-switch-conversion.c $(CONFIG_H) $(SYSTEM_H) \
> $(TREE_H) $(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TREE_INLINE_H) \
> $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(GIMPLE_H) \
>
--
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex
More information about the Gcc-patches
mailing list