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

[Tom de Vries]

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.

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

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.
>>