User account creation filtered due to spam.

Bug 13761 - [tree-ssa] component refs to the same struct should not alias
Summary: [tree-ssa] component refs to the same struct should not alias
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: tree-ssa
: P2 enhancement
Target Milestone: 4.4.0
Assignee: Daniel Berlin
URL:
Keywords: alias, missed-optimization, TREE
: 13765 (view as bug list)
Depends on:
Blocks: 16538 20121
  Show dependency treegraph
 
Reported: 2004-01-20 07:03 UTC by Dan Nicolaescu
Modified: 2008-03-14 17:37 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2006-10-26 13:03:05


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Dan Nicolaescu 2004-01-20 07:03:17 UTC
struct s {   int s;  int s2;  char p;  int arr[10];};

int foo0 (struct s * f)
{
  f->s = 1;
  f->s2 = 2;
  if (f->s != 1)
    link_error ();
}

The "if" is not optimized because, presumably, the 2 stores are not considered
not to alias.

The .optimized dump:

foo0 (f)
{
<bb 0>:
  f->s = 1;
  f->s2 = 2;
  if (f->s != 1) goto <L0>; else goto <L1>;

<L0>:;
  link_error ();

<L1>:;
  return;

}
Comment 1 Andrew Pinski 2004-01-20 15:13:06 UTC
Confirmed, even pta does not help.
Comment 2 Diego Novillo 2004-03-30 16:12:10 UTC
It's in my post-merge TODO list.
Comment 3 Dale Johannesen 2004-05-17 19:56:47 UTC
Here's another example (for lno).  The two inner loops should have identical code.

int x; int y;
struct { int x; int y; } global;
int foo() {
  int i;
  for ( i=0; i<10; i++)
    y += x*x;
  for ( i=0; i<10; i++)
    global.y += global.x*global.x;
}
Comment 4 Diego Novillo 2004-10-28 20:28:51 UTC
dberlin's field-based SSA work should help here.  Dan, want to take this one?
Comment 5 Diego Novillo 2004-10-28 20:34:32 UTC
*** Bug 13765 has been marked as a duplicate of this bug. ***
Comment 6 Daniel Berlin 2004-10-28 21:58:18 UTC
Subject: Re:  [tree-ssa] component refs to the
 same struct should not alias

> dberlin's field-based SSA work should help here.  Dan, want to take this one?

Sure.
Just reassign it to me
:)

Comment 7 Daniel Berlin 2004-12-20 16:35:11 UTC
The structure-aliasing branch now has code (or will as soon as cvs finishes
committing) that will fix dale's testcaes to the extent  i can.

We produce identical code for both loops, now.


I haven't quite fixed dan n's testcase yet, because it involves indirect_refs.
Comment 8 Daniel Berlin 2005-03-13 00:46:08 UTC
Dale's testcase is now fixed.
Comment 9 Steven Bosscher 2005-04-23 16:52:09 UTC
Will the second part of the struct alias merge fix Dann's original 
test case?  ("http://gcc.gnu.org/wiki/Structure Aliasing Part II") 
Comment 10 Daniel Berlin 2005-04-23 18:41:33 UTC
Subject: Re:  [tree-ssa] component refs to the
	same struct should not alias

On Sat, 2005-04-23 at 16:52 +0000, steven at gcc dot gnu dot org wrote:
> ------- Additional Comments From steven at gcc dot gnu dot org  2005-04-23 16:52 -------
> Will the second part of the struct alias merge fix Dann's original 
> test case?  ("http://gcc.gnu.org/wiki/Structure Aliasing Part II") 
> 

Yes, but not immediately.

structure aliasing part ii is really two parts

First, is a new alias analyzer to handle structure fields, allow
inteprocedural analysis.
Second is improving our representation to handle base+offset
dereferences.

The second is a lot harder than one would think.


Comment 11 Steven Bosscher 2005-07-25 15:28:44 UTC
The example from comment #3 now optimizes to identical inner loops: 
 
;; Function foo (foo) 
 
foo () 
{ 
  int i.54; 
  int lsm_tmp.32; 
  int lsm_tmp.31; 
  int i; 
  int D.1628; 
  int D.1627; 
  int D.1623; 
  int x.0; 
 
<bb 0>: 
  x.0 = x; 
  D.1623 = x.0 * x.0; 
  lsm_tmp.32 = y; 
  i.54 = 0; 
 
<L0>:; 
  lsm_tmp.32 = (int) ((unsigned int) D.1623 + (unsigned int) lsm_tmp.32); 
  i.54 = i.54 + 1; 
  if (i.54 != 10) goto <L0>; else goto <L12>; 
 
<L12>:; 
  y = lsm_tmp.32; 
  D.1627 = global.x; 
  D.1628 = D.1627 * D.1627; 
  lsm_tmp.31 = global.y; 
  i = 0; 
 
<L3>:; 
  lsm_tmp.31 = (int) ((unsigned int) lsm_tmp.31 + (unsigned int) D.1628); 
  i = i + 1; 
  if (i != 10) goto <L3>; else goto <L5>; 
 
<L5>:; 
  global.y = lsm_tmp.31; 
  return; 
 
} 
 
Comment 12 Steven Bosscher 2005-07-25 15:31:14 UTC
Oddly, the test case from comment #1 is not fixed.  Sorry for the 
inconvenience. 
Comment 13 Daniel Berlin 2005-07-25 15:40:51 UTC
Yes, it won't be fixed till 4.2, or the aliasing branch.
Comment 14 Richard Biener 2006-01-28 18:47:07 UTC
The copyprop enhancement patch I have in development handles the case where the stores are not constant.  I.e.

  int tmp = 1;
  f->s = tmp;
  f->s2 = 2;
  if (f->s != tmp)
    link_error ();

and -fno-tree-ccp.
Comment 15 Richard Biener 2006-03-06 14:39:22 UTC
The problem for the original testcase is that we don't even try to build SFTs required for structure aliasing analysis for incoming pointers:

foo0 (f)
{
  int D.1529;
  
<bb 2>:
  #   SMT.4_4 = V_MAY_DEF <SMT.4_3>;
  f_1->s = 1;
  #   SMT.4_5 = V_MAY_DEF <SMT.4_4>;
  f_1->s2 = 2;

which is required to turn these into V_MUST_DEFs.  Of course we still can do
propagation of the values in ccp or copyprop if we walk the virtual use-def
chains there and disabmiguate the offsets.
Comment 16 Richard Biener 2008-03-14 17:37:28 UTC
The original testcase is fixed by the alias-oracle.  The testcase in
comment #3 was fixed by SFTs.  I'll add a testcase for that (the important
part is the store sinking).
Comment 17 Richard Biener 2008-03-14 17:46:04 UTC
Subject: Bug 13761

Author: rguenth
Date: Fri Mar 14 17:45:20 2008
New Revision: 133224

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=133224
Log:
2008-03-14  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/13761
	* gcc.dg/tree-ssa/ssa-lim-3.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-3.c
Modified:
    trunk/gcc/testsuite/ChangeLog