[RFC] Improve tree DSE

[Jeff Law]

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 :-)

Jeff