Re: [PR50878, PATCH] Fix for verify_dominators in -ftree-tail-merge

[Richard Guenther <richard dot guenther at gmail dot com>]

On Mon, Oct 31, 2011 at 9:19 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 10/30/2011 10:54 AM, Richard Guenther wrote:
>> On Sun, Oct 30, 2011 at 9:27 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>> On 10/30/2011 09:20 AM, Tom de Vries wrote:
>>>> Richard,
>>>>
>>>> I have a fix for PR50878.
>>>
>>> Sorry, with patch this time.
>>
>> Ok for now, but see Davids mail and the complexity issue with iteratively
>> updating dominators.
>
> I'm not sure which mail you mean.

The one I CCed you on, which complained about iterative dominator fixing
taking 70% of the compile-time in some GCC testsuite test.

>> It seems to me that we know exactly what to update
>> and how, and we should do that (well, if we need up-to-date dominators,
>> re-computing them once in the pass would be ok).
>>
>
> Indeed, in this example we know exactly what to update and how. However, PR50908
> popped up, and there that's not the case anymore.
>
> Consider the following cfg, where A is the direct dominator of I:
>
> ? ? ? ? ? ? ? ?A
> ? ? ? ? ? ? ? / \
> ? ? ? ? ? ? ?B ? \
> ? ? ? ? ? ? / \ ? \
> ? ? ? ? ? ? ? ?C ? D
> ? ? ? ? ? ? ? /| ? |\
> ? ? ? ? ? ? ? ?E ? F
> ? ? ? ? ? ? ? ?|\ /|
> ? ? ? ? ? ? ? ?| x |
> ? ? ? ? ? ? ? ?|/ \|
> ? ? ? ? ? ? ? ?G ? H
> ? ? ? ? ? ? ? ? \ /
> ? ? ? ? ? ? ? ? ?I
>
> Say E and F are duplicates, and F is removed. ?The cfg then looks like
> this:
>
> ? ? ? ? ? ? ? ?A
> ? ? ? ? ? ? ? / \
> ? ? ? ? ? ? ?B ? \
> ? ? ? ? ? ? / \ ? \
> ? ? ? ? ? ? ? ?C ? D
> ? ? ? ? ? ? ? / \ / \
> ? ? ? ? ? ? ? ? ?E
> ? ? ? ? ? ? ? ? / \
> ? ? ? ? ? ? ? ?G ? H
> ? ? ? ? ? ? ? ? \ /
> ? ? ? ? ? ? ? ? ?I
>
> E is now the new direct dominator of I.
>
> The patch for PR50878 did not address this example, since it uses the set of bbs
> directly dominated by the (single) predecessor of bb1 and bb2.
>
> The new patch calculates the updated dominator info by taking the nearest common
> dominator (A) of bb1 (F) and bb2 (E), and getting the set of bbs immediately
> dominated by it. ?Part of this set is now directly dominated by bb2.
>
> Ideally we would have a means to determine which bbs in the set are now
> directly dominated by bb2, and call set_immediate_dominator for those bbs, but
> we don't, so instead we let iterate_fix_dominators figure it out.
>
> Additionally, the patch makes sure it updates dominator info before updating the
> vuses, this fixes a latent bug.
>
> The patch fixes both PR50908 and PR50878.
>
> Bootstrapped and reg-tested on x86_64 and i686, and build and reg-tested on ARM
> and MIPS.
>
> Ok for trunk?

Ok, but please add testcases for all the bugs you fixed.  This helps adding test
coverage for these cases.

Thanks,
Richard.

> Thanks,
> - Tom
>
>> Richard.
>>
>>> Thanks,
>>> - Tom
>>>
>>>>
>>>> A simplified form of the problem from the test-case of the PR is shown in this
>>>> cfg. Block 12 has as direct dominator block 5.
>>>>
>>>> ? ? ? ? 5
>>>> ? ? ? ?/ \
>>>> ? ? ? / ? \
>>>> ? ? ?* ? ? *
>>>> ? ? ?6 ? ? 7
>>>> ? ? ?| ? ? |
>>>> ? ? ?| ? ? |
>>>> ? ? ?* ? ? *
>>>> ? ? ?8 ? ? 9
>>>> ? ? ? \ ? /
>>>> ? ? ? ?\ /
>>>> ? ? ? ? *
>>>> ? ? ? ?12
>>>>
>>>> tail_merge_optimize finds that blocks 6 and 7 are duplicates. After replacing
>>>> block 7 by block 6, the cfg looks like this:
>>>>
>>>> ? ? ? ? 5
>>>> ? ? ? ? |
>>>> ? ? ? ? |
>>>> ? ? ? ? *
>>>> ? ? ? ? 6
>>>> ? ? ? ?/ \
>>>> ? ? ? / ? \
>>>> ? ? ?* ? ? *
>>>> ? ? ?8 ? ? 9
>>>> ? ? ? \ ? /
>>>> ? ? ? ?\ /
>>>> ? ? ? ? *
>>>> ? ? ? ?12
>>>>
>>>> The new direct dominator of block 12 is block 6, but the current algorithm only
>>>> recalculates dominator info for blocks 6, 8 and 9.
>>>>
>>>> The patch fixes this by additionally recalculating the dominator info for blocks
>>>> immediately dominated by bb2 (block 6 in the example), if bb2 has a single
>>>> predecessor after replacement.
>>>>
>>>> Bootstapped and reg-tested on x86_64 and i686. Build and reg-tested on MIPS and ARM.
>>>>
>>>> Ok for trunk?
>>>>
>>>> Thanks,
>>>> - Tom
>>>>
>>>> 2011-10-30 ?Tom de Vries ?<tom@codesourcery.com>
>>>>
>>>> ? ? ? PR tree-optimization/50878
>>>> ? ? ? * tree-ssa-tail-merge.c (replace_block_by): Recalculate dominator info
>>>> ? ? ? for blocks immediately dominated by bb2, if bb2 has a single predecessor
>>>> ? ? ? after replacement.
>>>
>>>
>
> 2011-10-31 ?Tom de Vries ?<tom@codesourcery.com>
>
> ? ? ? ?PR tree-optimization/50908
> ? ? ? ?* tree-ssa-tail-merge.c (update_vuses): Now that edges are removed
> ? ? ? ?before update_vuses, test for 1 predecessor rather than two.
> ? ? ? ?(delete_block_update_dominator_info): New function, part of it factored
> ? ? ? ?out of ...
> ? ? ? ?(replace_block_by): Use delete_block_update_dominator_info. ?Call
> ? ? ? ?update_vuses after deleting bb1 and updating dominator info, instead of
> ? ? ? ?before.
>