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

[Tom de Vries]

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?

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr52734.2.patch
Type: text/x-patch
Size: 3254 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20120413/16412540/attachment.bin>