Bug 52009 - Another missed tail merging opportunity
Summary: Another missed tail merging opportunity
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.7.0
: P3 minor
Target Milestone: ---
Assignee: vries
URL:
Keywords: missed-optimization
Depends on:
Blocks:
 
Reported: 2012-01-26 13:17 UTC by vries
Modified: 2012-07-06 11:13 UTC (History)
0 users

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2012-01-31 00:00:00


Attachments
tentative patch (2.06 KB, patch)
2012-01-30 20:09 UTC, vries
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description vries 2012-01-26 13:17:55 UTC
test-case pr51879-7.c:
...
int bar (int);
void baz (int);

int z;

void
foo (int y)
{
  int a;
  if (y == 6)
    {
      z = 5;
      a = bar (7);
    }
  else
    {
      z = 5;
      a = bar (7);
    }
  baz (a);
}
...

compile:
...
$ gcc -O2 -fdump-tree-all-all pr51879-7.c -S
...

representation at pr51879-7.c.094t.pre:
...
  # BLOCK 3 freq:1991
  # PRED: 2 [19.9%]  (true,exec)
  # .MEMD.1717_7 = VDEF <.MEMD.1717_6(D)>
  zD.1708 = 5;
  # .MEMD.1717_8 = VDEF <.MEMD.1717_7>
  # USE = nonlocal 
  # CLB = nonlocal 
  aD.1712_3 = barD.1703 (7);
  goto <bb 5>;
  # SUCC: 5 [100.0%]  (fallthru,exec)

  # BLOCK 4 freq:8009
  # PRED: 2 [80.1%]  (false,exec)
  # .MEMD.1717_9 = VDEF <.MEMD.1717_6(D)>
  zD.1708 = 5;
  # .MEMD.1717_10 = VDEF <.MEMD.1717_9>
  # USE = nonlocal 
  # CLB = nonlocal 
  aD.1712_4 = barD.1703 (7);
  # SUCC: 5 [100.0%]  (fallthru,exec)

  # BLOCK 5 freq:10000
  # PRED: 3 [100.0%]  (fallthru,exec) 4 [100.0%]  (fallthru,exec)
  # aD.1712_1 = PHI <aD.1712_3(3), aD.1712_4(4)>
  # .MEMD.1717_5 = PHI <.MEMD.1717_8(3), .MEMD.1717_10(4)>
  # .MEMD.1717_11 = VDEF <.MEMD.1717_5>
  # USE = nonlocal 
  # CLB = nonlocal 
  bazD.1705 (aD.1712_1);
  # VUSE <.MEMD.1717_11>
  return;
...

Blocks 3 and 4 are not merged, because .MEMD.1717_7 and .MEMD.1717_9 are not value numbered the same:
...
SCC consists of: .MEM_7 
Value numbering .MEM_7 stmt = z = 5;
RHS 5 simplified to 5
No store match
Value numbering store z to 5
Setting value number of .MEM_7 to .MEM_7 (changed)
...
SCC consists of: .MEM_9 
Value numbering .MEM_9 stmt = z = 5;
RHS 5 simplified to 5
No store match
Value numbering store z to 5
Setting value number of .MEM_9 to .MEM_9 (changed)
...
Comment 1 vries 2012-01-30 09:43:04 UTC
Value numbering of stores appears to be a bit different than what I expected.

pr51879-9.c:
...
int z;

void
foo (void)
{
  z = 5;
  z = 5;
}
...

pr51879-9.c.028t.fre:
...
SCC consists of: .MEM_1(D) 
Setting value number of .MEM_1(D) to .MEM_1(D) (changed)
SCC consists of: .MEM_2 
Value numbering .MEM_2 stmt = z = 5;
RHS 5 simplified to 5
No store match
Value numbering store z to 5
Setting value number of .MEM_2 to .MEM_2 (changed)
SCC consists of: .MEM_3 
Value numbering .MEM_3 stmt = z = 5;
RHS 5 simplified to 5
Store matched earlier value,value numbering store vdefs to matching vuses.
Setting value number of .MEM_3 to .MEM_2 (changed)
Value numbers:
.MEM_3 = .MEM_2
...

Value numbering .MEM_2 stmt = z = 5:
...
2796	        vn_reference_insert (lhs, op, vdef);
(gdb) call debug_generic_expr (lhs)
z
(gdb) call debug_generic_expr (op)
5
(gdb) call debug_generic_expr (vdef)
.MEM_2
...
or 5 = GVN<z, .MEM_2>

Value numbering .MEM_3 stmt = z = 5:
...
2761	  result = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_NOWALK, NULL);
(gdb) call debug_generic_expr (lhs)
z
(gdb) call debug_generic_expr (gimple_vuse (stmt))
.MEM_2
(gdb) n
(gdb) call debug_generic_expr (result)
5
...

The value numbering we need for this PR is more like:
.MEM_2 = GVN<z, 5, .MEM_1(D)>
Comment 2 vries 2012-01-30 20:09:10 UTC
Created attachment 26518 [details]
tentative patch
Comment 3 vries 2012-01-31 21:08:34 UTC
submitted patch: http://gcc.gnu.org/ml/gcc-patches/2012-01/msg01731.html
Comment 4 Andrew Pinski 2012-01-31 21:11:52 UTC
Confirmed.
Comment 5 vries 2012-07-06 11:07:36 UTC
Author: vries
Date: Fri Jul  6 11:07:32 2012
New Revision: 189321

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189321
Log:
2012-07-06  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/52009
	* tree-ssa-tail-merge.c (gimple_equal_p): For GIMPLE_ASSIGN, compare
	value numbers of gimple_vdef.
	* tree-ssa-sccvn.h (vn_reference_insert): Add vdef parameter to
	prototype.
	* tree-ssa-sccvn.c (copy_reference_ops_from_ref): Handle MODIFY_EXPR.
	(vn_reference_insert): Add and handle vdef parameter.
	(visit_reference_op_load): Add argument to vn_reference_insert call.
	(visit_reference_op_store): Find value number of vdef of store.  Insert
	value number of vdef of store.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-sccvn.c
    trunk/gcc/tree-ssa-sccvn.h
    trunk/gcc/tree-ssa-tail-merge.c
Comment 6 vries 2012-07-06 11:07:41 UTC
Author: vries
Date: Fri Jul  6 11:07:37 2012
New Revision: 189322

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189322
Log:
2012-07-06  Tom de Vries  <tom@codesourcery.com>

	PR tree-optimization/52009
	* gcc.dg/pr51879-7.c: New test.
	* gcc.dg/pr51879-18.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/pr51879-18.c
    trunk/gcc/testsuite/gcc.dg/pr51879-7.c
Modified:
    trunk/gcc/testsuite/ChangeLog
Comment 7 vries 2012-07-06 11:09:59 UTC
patch and test-cases checked in, closing bug.