On Fri, Apr 13, 2012 at 12:56 PM, Tom de Vries <tom_devr...@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_devr...@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 <t...@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. >>> >
