[PATCH PR68030/PR69710][RFC]Introduce a simple local CSE interface and use it in vectorizer

[Bin.Cheng]

On Fri, May 27, 2016 at 11:45 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Wed, May 25, 2016 at 1:22 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>> Hi,
>> As analyzed in PR68303 and PR69710, vectorizer generates duplicated computations in loop's pre-header basic block when creating base address for vector reference to the same memory object.  Because the duplicated code is out of loop, IVOPT fails to track base object for these vector references, resulting in missed strength reduction.
>> It's agreed that vectorizer should be improved to generate optimal (IVOPT-friendly) code, the difficult part is we want a generic infrastructure.  After investigation, I tried to introduce a generic/simple local CSE interface by reusing existing algorithm/data-structure from tree-ssa-dom (tree-ssa-scopedtables).  The interface runs local CSE for each basic block in a bitmap, customers of this interface only need to record basic blocks in the bitmap when necessary.  Note we don't need scopedtables' unwinding facility since the interface runs only for single basic block, this should be good in terms of compilation time.
>> Besides CSE issue, this patch also re-associates address expressions in vect_create_addr_base_for_vector_ref, specifically, it splits constant offset and adds it back near the expression root in IR.  This is necessary because GCC only handles re-association for commutative operators in CSE.
>>
>> I checked its impact on various test cases.
>> With this patch, PR68030's generated assembly is reduced from ~750 lines to ~580 lines on x86_64, with both pre-header and loop body simplified.  But,
>> 1) It doesn't fix all the problem on x86_64.  Root cause is computation for base address of the first reference is somehow moved outside of loop's pre-header, local CSE can't help in this case.  Though split_constant_offset can back track ssa def chain, it causes possible redundant when there is no CSE opportunities in pre-header.
>> 2) It causes regression for PR68030 on AArch64.  I think the regression is caused by IVOPT issues which are exposed by this patch.  Checks on offset validity in get_address_cost is wrong/inaccurate now.  It considers an offset as valid if it's within the maximum offset range that backend supports.  This is not true, for example, AArch64 requires aligned offset additionally.  For example, LDR [base + 2060] is invalid for V4SFmode, although "2060" is within the maximum offset range.  Another issue is also in get_address_cost.  Inaccurate cost is computed for "base + offset + INDEX" address expression.  When register pressure is low, "base+offset" can be hoisted out and we can use [base + INDEX] addressing mode, whichhis is current behavior.
>>
>> Bootstrap and test on x86_64 and AArch64.  Any comments appreciated.
>
> It looks quite straight-forward with the caveat that it has one
> obvious piece that is not in the order
> of the complexity of a basic-block.  threadedge_initialize_values
> creates the SSA value array
I noticed this too, and think it's better to get rid of this init/fini
functions by some kind re-design.  I found it's quite weird to call
threadege_X in tree-vrp.c.  I will keep investigating this.
> which is zero-initialized (upon use).  That's probably a non-issue for
> the use you propose for
> the vectorizer (call cse_bbs once per function).  As Ideally I would
> like this facility to replace
> the loop unrollers own propagate_constants_for_unrolling it might
> become an issue though.
> In that regard the unroller facility is also more powerful because it
> handles regions (including
> PHIs).
With the current data-structure, I think it's not very hard to extend
the interface to regions.  I will keep investigating this too.  BTW,
if it's okay, I tend to do that in following patches.
>
> Note that in particular for SLP vectorization the vectorizer itself
> may end up creating quite
> some redundancies so I wonder if it's worth to CSE the vectorized loop
> body as well
Maybe.  The next step is condition block created by vectorizer.  Both
prune_runtime_alias_test_list and generated alias checks are
sub-optimal now, even worse, somehow computations in alias checks can
be propagated to loop pre-header.  With help of this interface, alias
checks (and later code) can be simplified.

> (and given we have PHIs eventually CSE the whole vectorized loop with
> pre-header as a region...)
>
> Thanks,
> Richard.
>
>> Thanks,
>> bin
>>
>> 2016-05-17 Bin Cheng  <bin.cheng@arm.com>
>>
>>         PR tree-optimization/68030
>>         PR tree-optimization/69710
>>         * tree-ssa-dom.c (cse_bbs): New function.
>>         * tree-ssa-dom.h (cse_bbs): New declaration.
>>         * tree-vect-data-refs.c (vect_create_addr_base_for_vector_ref):
>>         Re-associate address by splitting constant offset.
>>         (vect_create_data_ref_ptr, vect_setup_realignment): Record changed
>>         basic block.
>>         * tree-vect-loop-manip.c (vect_gen_niters_for_prolog_loop): Record
>>         changed basic block.
>>         * tree-vectorizer.c (tree-ssa-dom.h): Include header file.
>>         (changed_bbs): New variable.
>>         (vectorize_loops): Allocate and free CHANGED_BBS.  Call cse_bbs.
>>         * tree-vectorizer.h (changed_bbs): New declaration.