[RFC] Improve tree DSE

[Richard Biener]

On Wed, May 2, 2018 at 7:39 PM, Jeff Law <law@redhat.com> wrote:
> On 05/02/2018 11:36 AM, Richard Biener wrote:
>> On May 2, 2018 6:17:50 PM GMT+02:00, Jeff Law <law@redhat.com> wrote:
>>> On 05/02/2018 03:27 AM, Richard Biener wrote:
>>>> On Tue, Apr 10, 2018 at 2:52 AM, Kugan Vivekanandarajah
>>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>> I would like to queue this patch for stage1 review.
>>>>>
>>>>> In DSE, while in dse_classify_store, as soon as we see a PHI use
>>>>> statement that is part of the loop, we are immediately giving up.
>>>>>
>>>>> As far as I understand, this can be improved. Attached patch is
>>> trying
>>>>> to walk the uses of the PHI statement (by recursively calling
>>>>> dse_classify_store) and then making sure the obtained store is
>>> indeed
>>>>> redundant.
>>>>>
>>>>> This is partly as reported in one of the testcase from PR44612. But
>>>>> this PR is about other issues that is not handled in this patch.
>>>>>
>>>>> Bootstrapped and regression tested on aarch64-linux-gnu with no new
>>> regressions.
>>>>>
>>>>> Is this OK for next stage1?
>>>>
>>>>               if (temp
>>>>                   /* Make sure we are not in a loop latch block.  */
>>>>                   || gimple_bb (stmt) == gimple_bb (use_stmt)
>>>> -                 || dominated_by_p (CDI_DOMINATORS,
>>>> -                                    gimple_bb (stmt), gimple_bb
>>> (use_stmt))
>>>>                   /* We can look through PHIs to regions
>>> post-dominating
>>>>
>>>> you are removing part of the latch-block check but not the other.
>>>>
>>>> +                 /* If stmt dominates PHI stmt, follow the PHI stmt.
>>> */
>>>> +                 if (!temp)
>>>>
>>>> well, just do this check earlier.  Or rather, it's already done in
>>> the
>>>> test above.
>>>>
>>>> +                     /* Makesure the use stmt found is post
>>> dominated.  */
>>>> +                     && dominated_by_p (CDI_POST_DOMINATORS,
>>>> +                                        gimple_bb (stmt_outer),
>>>> gimple_bb (inner_use_stmt))
>>>>
>>>> I think that this check also covers gimple_bb (stmt_outer) ==
>>>> gimple_bb (inner_use_stmt)
>>>> so for that case you'd need to check stmt dominance.  But better just
>>> give up?
>>>>
>>>> Given the simple testcases you add I wonder if you want a cheaper
>>>> implementation,
>>>> namely check that when reaching a loop PHI the only aliasing stmt in
>>>> its use-chain
>>>> is the use_stmt you reached the PHI from.  That would avoid this and
>>> the tests
>>>> for the store being redundant and simplify the patch considerably.
>>> Yea,  but the ideas in the patch might be useful for some of the other
>>> DSE missed optimizations :-)
>>
>> Note that what we want in the end is some kind of general partial dead code elimination pass that also handles stores. There was a SSU PRE implementation as part of a gsoc project many years ago. I believe building on top of the ad-hoc DSE pass we have right now is not the very best thing to do long term. SSU PRE also performs store/code sinking thus merging with the also ad-hoc sinking pass...
> If we did good store sinking I think partial dead store elimination just
> falls out with the existing tree-ssa-dse.c implementation.  The cases I
> was thinking about are already fully redundant, but the structure of
> tree-ssa-dse isn't great for discovering them.

Yeah.

As a side-note - Kugan, you rely on post-dominance checks for
correctness but post-dominance
isn't what you expect when dealing with inifinite loops (with blocks
not reverse reachable from exit).
So relying on post-dominance for correctness is very fragile - we've
been bitten by this before.

Richard.

>
> jeff