Re: [RFC] [alias, middle-end] Alias and data dependency export

[Richard Guenther <rguenther at suse dot de>]

On Wed, 13 May 2009, Andrey Belevantsev wrote:

> Hello,
> 
> The attached patch implements (again) the exporting of alias and data
> dependency information from Tree SSA and reusing it on RTL level. Looking
> back, I can tell that the previous attempt on this was quite good, as it
> solved all problems I had to solve with the current patch, but it was also too
> early to produce interesting results without Richard's alias improvements and
> oracle (thank you Richard!).  Also, the patch was much easier to complete
> after Michael's expand from SSA went in (thank you Michael!), though it still
> worked pretty good.
> 
> The patch adds MEM_ORIG_EXPR field to mem_attrs, which is initialized to a
> complete tree that was used to generate this mem from.  The MEM_EXPR field is
> retained for the sake of existing code, if there's any cleanups possible here,
> I can work on this as a followup.  For alias export, MEM_ORIG_EXPR is then
> basically passed to the refs_may_alias_p oracle, together with saved points-to
> information where applicable, when answering queries from alias.c functions.
> For data dependency export, MEM_ORIG_EXPR is used as a key for accessing saved
> data references and dependence relations, and this is also used for alias.c
> and for modulo scheduling.
> 
> When gathering information for export, we need to rebuild aliasing for alias
> export and to schedule an extra pass for computing data dependency info for
> ddg export.  The MEM_ORIG_EXPR field is initialized when memory attributes are
> computed in set_mem_attributes_minus_bitpos, it is also unshared so we can
> release trees coming into that function.  The points-to sets are also recorded
> during that time.
> 
> The alias oracle is a bit modified so that it allows for points-to sets and
> escaped solution to come from outside.  The current implementation for this is
> quite ugly (macros), but it worked, avoided code duplication, and made merges
> easier for me.  I'm happy to do here whatever Richi would suggest.
> 
> The interesting part of alias export is accounting for stack slot sharing
> info.  We need to make sure that all points-to sets that have some of stack
> partition variables set get all of them set, that all partitioned pointers
> have their points-to sets unified, and that all bases are rewritten to their
> stack partition representative.  Also, TREE_ADDRESSABLE bit should be
> propagated within a partition. Hopefully, I got it right after fixing all test
> suite failures :-)
> 
> The interesting part of ddg export is that, first, array accesses with
> non-zero distances are used for disambiguation for everything except passes
> that do pipelining (modulo-sched, sel-sched), and this doesn't happen after
> pipelining, as the information might become incorrect. Second, the information
> also becomes wrong after unrolling, so it is removed from insns of the new
> copy of the unrolled loop.
> 
> The patch bootstraps/regtests on x86-64 with all default languages and ada,
> producing about 800K new disambiguations for SPEC2k on x86-64.  The number of
> new disambiguations is reported via statistics infrastructure.
> Performance-wise, the patch is a steady win on ia64 last time I checked (~3%
> on SPEC2k FP with -O3, 634 vs 616, neutral on SPEC2k Int), and it had some ups
> and downs on SPEC2k6 x86-64 when Richi tested it last time, overall slightly
> positive (probably, I haven't seen the logs).  If somebody can help with
> performance testing on other architectures, that would be great.  We have
> SPEC2k6 sources now, so I can take a look on performance issues.
> 
> Also, there are some points on which I'd like an advice:
> 
> - I'm freeing the information from pass_clean_state, is this fine or do we
> want a general pass that frees on the side stuff like this and df?

pass_clean_state is good enough.

> - Are there any places that should be adding/removing MEM_ORIG_EXPRs except
> the ones I've fixed?  While writing the patch, we had a checking pass for
> that, which attributed each missing MEM_ORIG_EXPR to be fine wrt its
> usefulness (e.g., SYMBOL_REFs, byproducts of expanding calls, tablejumps,
> BLKmode mems, etc -- tree aliasing doesn't know about those anyways);

No idea.  I don't like the extra MEM_ORIG_EXPR too much anyway.

> - the fix in discover_nonconstant_array_refs_r that limits setting of
> TREE_ADDRESSABLE to BLKmode arrays was suggested by Richard and can be
> submitted separately; I don't know anything about it except that it works;

Please submit separately.

> - the fix for statistics.s can be also submitted separately;

Please do so.

> - the flags for alias/ddg export should probably be gone if the patch is
> accepted for trunk.

Indeed.

> Thoughts, comments?  OK for trunk?

Collected commens while skimming over the patch follow.  The main
cleanup opportunity is to delay delete_tree_ssa until pass_clean_state
and the partition decl replacement with indirect refs.  Oh, and of
course not adding MEM_ORIG_EXPRs ...

Thanks,
Richard.

---


Instead of saving the ESCAPED/CALLUSED solutions (where is the latter?)
please move them to struct function instead so they persist.

In struct ptr_info_def the vars bitmap is shared - you should not change
it but always allocate a new one.

In addition to adjusting the points-to sets wrt stack partitions you need
to make sure that all variables in a stack partitions have the same
TREE_ADDRESSABLE setting (thus, if one is addressable all should be
marked so).

Why do you need replace_var_in_datarefs?  Why do you need to unshare
the exprs anyway?

Why do you record points-to info for exprs?  Why not simply not release
SSA names and keep the information hanging off them?  Why not adjust
points-to sets wrt partitions at the time partitioning and stack var
expansion is done?  Same for the MEM_EXPRs.  (why is it all in a new file?)

Why do you need MEM_ORIG_EXPR?  Is using MEM_EXPR not enough?  Why?

add_partitioned_vars_to_ptset and record_stack_var_partition_for look
redundant.

It would be nice to have data-dependence export as a separate patch.
IMHO we should always export points-to information.

I don't like the way you handle stack partitions wrt replacing
ref bases with the partition representative.  A more scalable
and correct (wrt TBAA) way would be to replace the bases
with an INDIRECT_REF of a new pointer that you would assign
a points-to set to covering all members of the partition.
That should simplify the points-to set adjustments as well.

Please submit & test the discover_nonconstant_array_refs_r part
separately.

*************** ptr_deref_may_alias_decl_p (tree ptr, tr
*** 172,181 ****
        || TREE_CODE (ptr) == INTEGER_CST)
      return true;
  
!   gcc_assert (TREE_CODE (ptr) == SSA_NAME
!             && (TREE_CODE (decl) == VAR_DECL
!                 || TREE_CODE (decl) == PARM_DECL
!                 || TREE_CODE (decl) == RESULT_DECL));
  
    /* Non-aliased variables can not be pointed to.  */
    if (!may_be_aliased (decl))
--- 180,190 ----
        || TREE_CODE (ptr) == INTEGER_CST)
      return true;
  
!   gcc_assert ((TREE_CODE (ptr) == SSA_NAME
!                && (TREE_CODE (decl) == VAR_DECL
!                    || TREE_CODE (decl) == PARM_DECL
!                    || TREE_CODE (decl) == RESULT_DECL))
!               || current_ir_type () != IR_GIMPLE);

why that?  This and later changes should be not necessary if you
simply kept SSA_NAMEs around?

I see TMR_ORIGINAL is interesting ... it's a hack and should probably
simply go.

Re-building PTA after uncprop should hopefully not be necessary soon.

I would suggest to simply move delete_tree_ssa to after we finished
assembling the functions.  That also makes moving the escaped/callused
solutions to struct function unnecessary.