[RFC] [alias, middle-end] Alias and data dependency export
Andrey Belevantsev
abel@ispras.ru
Wed May 13 11:13:00 GMT 2009
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?
- 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);
- 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;
- the fix for statistics.s can be also submitted separately;
- the flags for alias/ddg export should probably be gone if the patch is
accepted for trunk.
Thoughts, comments? OK for trunk?
Andrey
2009-05-13 Andrey Belevantsev <abel@ispras.ru>
Dmitry Melnik <dm@ispras.ru>
Alexander Monakov <amonakov@ispras.ru>
Dmitry Zhurikhin <zhur@ispras.ru>
Alias and data dependency export.
* Makefile.in (OBJS-common): Add alias-export.o.
(tree-ssa.o): Depend on alias-export.h.
(tree-ssa-loop-ivopts.o): Likewise.
(tree-ssa-alias.o): Likewise.
(emit-rtl.o): Likewise.
(loop-unroll.o): Likewise.
(alias.o): Likewise.
(modulo-sched.o): Likewise.
(sel-sched.o): Likewise.
(final.o): Likewise.
* alias-export.c: New file.
* alias-export.h: New file.
* rtl.h (struct mem_attrs): New field orig_expr.
(MEM_ORIG_EXPR): New access macro.
* tree-ssa-uncprop.c (pass_uncprop): Set TODO_rebuild_alias.
* tree-ssa.c: Include alias-export.h.
(delete_tree_ssa): Only release ssa names when not exporting info.
Record escaped solution for alias export.
* tree-ssa-loop-ivopts.c: Include alias-export.h.
(copy_ref_info): Record new reference in ddg export data.
* tree-ssa-alias.c: Include alias-export.h.
(GET_PTR_INFO_FOR, GET_ESCAPED_SOLUTION): New macros.
(ptr_deref_may_alias_decl_p): Add expi and exescaped parameters.
Use them to access PTA data. Adjust assert to include RTL case.
(ptr_derefs_may_alias_p): Add expi1, expi2, exescaped parameters.
Use them to access PTA data. Adjust assert to include RTL case.
(indirect_ref_may_alias_decl_p): Add expi1 and exescaped parameters.
Use them to access PTA data.
(indirect_refs_may_alias_p): Add expi1, expi2, exesaped parameters.
Use them to access PTA data.
(refs_may_alias_p_1): Likewise. Adjust assert to include RTL case.
* tree-ssa-alias.h (refs_may_alias_p_1, pt_solution_includes_1,
pt_solutions_intersect_1): Export.
* tree-ssa-structalias.c (pt_solution_includes_1,
pt_solutions_intersect_1): Add escaped parameter, make global.
* cfgexpand.c: Include alias-export.h.
(union_stack_vars): Promote TREE_ADDRESSABLE to the merged partition
representative.
(record_stack_var_partitions): New.
(expand_used_vars): Call it.
(discover_nonconstant_array_refs_r): Make only BLKmode arrays addressable.
(gimple_expand_cfg): Also set MEM_ORIG_EXPR to NULL.
* expr.c (expand_expr_real_1): When expanding TARGET_MEM_REF,
set MEM_ORIG_EXPR to its TMR_ORIGINAL.
* function.c (assign_parms_unsplit_complex): Also set MEM_ORIG_EXPR
for parm.
* emit-rtl.c: Include alias-export.h.
(mem_attrs_htab_hash, get_mem_attrs, set_mem_attrs_from_reg,
set_mem_alias_set, set_mem_align, set_mem_expr, set_mem_offset,
set_mem_size, change_address, offset_address,
widen_memory_access, get_spill_slot_decl,
set_mem_attrs_for_spill): Account for MEM_ORIG_EXPR.
(set_mem_orig_expr): New.
(set_mem_attributes_minus_bitpos): Record MEM_ORIG_EXPR.
(adjust_address_1): When we make a wider address, nullify MEM_ORIG_EXPR.
* emit-rtl.h (set_mem_orig_expr): Export.
* final.c: Include alias-export.h.
(rest_of_clean_state): Free exported information.
* alias.c: Include alias-export.h.
(query_alias_export_info): New.
(walk_mems_2): Also query ddg export info.
(true_dependence): Use query_alias_export_info.
(canon_true_dependence, write_dependence_p): Likewise.
* loop-unroll.c: Include alias-export.h.
(apply_opt_in_copies): Clear exported ddg data on insns in unrolled
loop.
* modulo-sched.c: Include alias-export.h.
(rest_of_handle_sms): Call ddg_export_set_pipelining_completed.
* sel-sched.c: Include alias-export.h.
(sel_global_finish): Call ddg_export_set_pipelining_completed.
* common.opt (falias-export, fddg-export): New options.
* dbgcnt.def (alias_export, ddg_export): New counter.
* tree-pass.h (pass_gather_ddg_info): Export.
* builtins.c (get_memory_rtx): Also set MEM_ORIG_EXPR to NULL.
* passes.c (init_optimization_passes): Schedule pass for ddg export.
* statistics.c (statistics_counter_event): Do not record event in pass
dump if its number == -1.
(curr_statistics_hash): Add assert that we never get passes with static
number == -1.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: current-ae.diff
Type: text/x-patch
Size: 91002 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20090513/ffa99b59/attachment.bin>
More information about the Gcc-patches
mailing list