This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Fix for PR52734 (-ftree-tail-merge)


On Fri, Apr 13, 2012 at 12:56 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 13/04/12 11:13, Richard Guenther wrote:
>> On Fri, Apr 13, 2012 at 10:32 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>> Richard,
>>>
>>> this patch fixes PR52743.
>>>
>>> The problem is as follows: blocks 3 and 5, with successor 6 are considered equal
>>> and merged.
>>> ...
>>> ?# BLOCK 3 freq:6102
>>> ?# PRED: 2 [61.0%] ?(true,exec)
>>> ?# VUSE <.MEMD.1734_10>
>>> ?dddD.1710_3 = bbbD.1703;
>>> ?goto <bb 6>;
>>> ?# SUCC: 6 [100.0%] ?(fallthru,exec)
>>>
>>> ?# BLOCK 5 freq:2378
>>> ?# PRED: 4 [61.0%] ?(false,exec)
>>> ?# SUCC: 6 [100.0%] ?(fallthru,exec)
>>>
>>> ?# BLOCK 6 freq:10000
>>> ?# PRED: 3 [100.0%] ?(fallthru,exec) 7 [100.0%] ?(fallthru) 5 [100.0%]
>>> (fallthru,exec)
>>> ?# dddD.1710_1 = PHI <dddD.1710_3(3), 0(7), dddD.1710_4(5)>
>>> ?# .MEMD.1734_8 = PHI <.MEMD.1734_10(3), .MEMD.1734_11(7), .MEMD.1734_11(5)>
>>> ?# VUSE <.MEMD.1734_8>
>>> ?return dddD.1710_1;
>>> ?# SUCC: EXIT [100.0%]
>>> ...
>>>
>>> Tail merge considers 2 blocks equal if the effect at the tail is equal,
>>> meaning:
>>> - the sequence of side effects produced by each block is equal
>>> - the value phis are equal
>>>
>>> There are no side effects in block 3 and 5, and the phi alternatives of
>>> dddD.1710_1 for 3 (dddD.1710_3) ?and 5 (dddD.1710_4) ?are proven equal by gvn.
>>>
>>> The problem is that changing the (4->5) edge into a (4->3) edge changes the
>>> value of dddD.1710_3, because block 4 contains a store that affects the load in
>>> block 3.
>>> ...
>>> ?# BLOCK 4 freq:3898
>>> ?# PRED: 2 [39.0%] ?(false,exec)
>>> ?# VUSE <.MEMD.1734_10>
>>> ?dddD.1710_4 = bbbD.1703;
>>> ?# .MEMD.1734_11 = VDEF <.MEMD.1734_10>
>>> ?# USE = nonlocal null
>>> ?# CLB = nonlocal null
>>> ?D.1724_5 = aaaD.1705 ();
>>> ?if (D.1724_5 != 0)
>>> ? ?goto <bb 7>;
>>> ?else
>>> ? ?goto <bb 5>;
>>> ?# SUCC: 7 [39.0%] ?(true,exec) 5 [61.0%] ?(false,exec)
>>> ...
>>>
>>> Or, put differently, the incoming vuse of block 3 affects a value phi
>>> alternative for that block (dddD.1710_3), so the 2 blocks are equal only under
>>> the condition that the incoming vuses are equal.
>>>
>>> We could build an analysis that addresses that precisely, but for now I
>>> implemented a more coarse-grained fix: if the incoming vuses are not equal, and
>>> at least one of the vuses influenced a non-virtual result, we don't consider the
>>> blocks equal.
>>>
>>> Bootstrapped and reg-tested on x86_64.
>>>
>>> ok for trunk, 4.7.1?
>>
>> Hmm, I wonder if the proper observation would not be that while GVN considers
>> the PHI arguments in
>>
>>> ?# dddD.1710_1 = PHI <dddD.1710_3(3), 0(7), dddD.1710_4(5)>
>>
>> to be equal, their definitions are not in the blocks we try to merge, so their
>> value can be dependent on the status as it was on their predecessors.
>> GVN, after all, considers flow-sensitivity.
>>
>
> we are replacing block 5 by block 3. The phi alternative for block 3 is
> dddD.1710_3(3), which is defined in block 3. The problem is related to the vuse
> dependency of the def of dddD.1710_3(3).
>
> I'll try to reformulate. In tail_merge_optimize, we analyze:
> 1. if the blocks are equal (for which gvn might be used)
> 2. if the blocks can be merged. The blocks cannot be merged if the dependencies
> ? of the replacement block are not satisfied in the predecessors of the other
> ? blocks.
>
> We handle the dependencies for virtual and normal values differently.
>
> For normal values, we calculate BB_DEP_BB (The bb that either contains or is
> dominated by the dependencies of the bb). If BB_DEP_BB of the replacement block
> dominates the blocks that are replaced, the blocks can be merged.
>
> For virtual values, we don't check for dependencies.
>
> If we would check for virtual dependencies like normal dependencies, the
> original example pr43864.c would not work anymore: there are 2 blocks with
> identical result-less function calls, but with different incoming vuse.
> It's safe to merge the blocks, so we don't treat the vuses as dependencies.
>
> This test-case shows a case that the vuse is a dependency of the replacement
> block, which is not satisfied by the predecessor of the replaced block.
>
> We need an analysis of when a vuse needs to be considered a dependency.

Ah, ok.  That makes sense then.

> This patch implement such an analysis. Conservative, but simple. OK for trunk,
> 4.7.1?

Yes.

Thanks,
Richard.

> Thanks,
> - Tom
>
>> Richard.
>>
>>
>>> Thanks,
>>> - Tom
>>>
>>> 2012-04-13 ?Tom de Vries ?<tom@codesourcery.com>
>>>
>>> ? ? ? ?* tree-ssa-tail-merge.c (gsi_advance_bw_nondebug_nonlocal): Add
>>> ? ? ? ?parameters vuse and vuse_escaped.
>>> ? ? ? ?(find_duplicate): Init vuse1, vuse2 and vuse_escaped. ?Pass to
>>> ? ? ? ?gsi_advance_bw_nondebug_nonlocal. ?Return if vuse_escaped and
>>> ? ? ? ?vuse1 != vuse2.
>>>
>>> ? ? ? ?* gcc.dg/pr52734.c: New test.
>>>
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]