[Bug tree-optimization/19626] New: Aliasing says stores to local memory do alias

[Bug tree-optimization/19626] New: Aliasing says stores to local memory do alias

[rguenth at tat dot physik dot uni-tuebingen dot de]

Given the attached testcase, for reference, the interesting function is
this:

int loc_test(void)
{
	const Loc<2> dX(1, 0);
	const Loc<2> k(0, 1);
	return k[0].first() + dX[0].first();
}

aliasing tells us that the initializations of dX and k alias each
other:

<bb 0>:
  D.2540 = (struct Loc<1> *) &dX.D.2210.D.2166.domain_m.buffer;
  #   dX_357 = V_MAY_DEF <dX_318>;
  #   k_358 = V_MAY_DEF <k_317>;
  *&(&D.2540->D.2094)->D.2057.domain_m = 1;
  #   dX_365 = V_MAY_DEF <dX_357>;
  #   k_364 = V_MAY_DEF <k_358>;
  *&(&(D.2540 + 4B)->D.2094)->D.2057.domain_m = 0;
  D.2682 = (struct Loc<1> *) &k.D.2210.D.2166.domain_m.buffer;
  #   dX_337 = V_MAY_DEF <dX_365>;
  #   k_338 = V_MAY_DEF <k_364>;
  *&(&D.2682->D.2094)->D.2057.domain_m = 0;
  #   dX_361 = V_MAY_DEF <dX_337>;
  #   k_63 = V_MAY_DEF <k_338>;
  *&(&(D.2682 + 4B)->D.2094)->D.2057.domain_m = 1;
  D.2769 = (struct Loc<1> *) &k.D.2210.D.2166.domain_m.buffer;
  D.2791 = (struct Loc<1> *) &dX.D.2210.D.2166.domain_m.buffer;
  return (&D.2769->D.2094)->D.2057.domain_m + (&D.2791->D.2094)->D.2057.domain_m;

which is of course (trivially) not true.  This may be obfuscated by
the actual implementation of the template class Loc (see attached
complete testcase).

At the RTL level we are able to optimize this to just return 1, as
expected.  This pessimizes tree loop optimizations if such constructs
are used inside a loop and as induction variable.

-- 
           Summary: Aliasing says stores to local memory do alias
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at tat dot physik dot uni-tuebingen dot de
                CC: gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[rguenth at tat dot physik dot uni-tuebingen dot de]

------- Additional Comments From rguenth at tat dot physik dot uni-tuebingen dot de  2005-01-25 16:57 -------
Created an attachment (id=8062)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=8062&action=view)
testcase


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-25 17:15 -------
If you had used the correct types in the first place instead of this crazy uninitialized pointer this works 
(almost):
  dX.D.2220.D.2170.domain_m.buffer[0].D.2098.D.2055.domain_m = 1;
  dX.D.2220.D.2170.domain_m.buffer[1].D.2098.D.2055.domain_m = 0;
....
  k.D.2220.D.2170.domain_m.buffer[0].D.2098.D.2055.domain_m = 0;
  k.D.2220.D.2170.domain_m.buffer[1].D.2098.D.2055.domain_m = 1;
  return k.D.2220.D.2170.domain_m.buffer[0].D.2098.D.2055.domain_m + 
dX.D.2220.D.2170.domain_m.buffer[0].D.2098.D.2055.domain_m;

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
           Keywords|                            |alias, missed-optimization,
                   |                            |TREE
           Priority|P2                          |P3


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-25 17:20 -------
  D.2540 = (struct Loc<1> *) &dX.D.2210.D.2166.domain_m.buffer;
That confuses the aliasing mechanism
buffer is of type int* but you are casting it to Loc<1> *.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[rguenth at tat dot physik dot uni-tuebingen dot de]

------- Additional Comments From rguenth at tat dot physik dot uni-tuebingen dot de  2005-01-26 08:47 -------
Subject: Re:  Aliasing says stores to local
 memory do alias

>   D.2540 = (struct Loc<1> *) &dX.D.2210.D.2166.domain_m.buffer;
> That confuses the aliasing mechanism
> buffer is of type int* but you are casting it to Loc<1> *.

Telling it the truth by having an array of Loc<1> instead doesn't help.
I suppose you're talking about not decomposing Loc<2> into two
Loc<1> as intermediate step?  Well, yes, that's a design decision I
cannot change.  It looks superfluous for Loc<>, but makes sense for
the more complex domain objects like Interval and Range (but that's
a different story).

But in principle a compiler could determine that the two objects
cannot alias, even which this interwinded type structure?



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[rguenth at gcc dot gnu dot org]

------- Additional Comments From rguenth at gcc dot gnu dot org  2005-02-10 13:18 -------
Actually, exchanging loc_test for

int loc_test(void)
{
	const Loc<2> k(0, 1);
	return k[0].first();
}

shows the same problem:

<bb 0>:
  D.2541 = (struct Loc<1> *) &k.D.2190.D.2155.domain_m.buffer;
  #   k_160 = V_MAY_DEF <k_150>;
  *&(&D.2541->D.2101)->D.2064.domain_m = 0;
  #   k_63 = V_MAY_DEF <k_160>;
  *&(&(D.2541 + 4B)->D.2101)->D.2064.domain_m = 1;
  D.2628 = (struct Loc<1> *) &k.D.2190.D.2155.domain_m.buffer;
  return (&D.2628->D.2101)->D.2064.domain_m;

One problem might be, that PRE does not recognize the redundant
(struct Loc<1>D.1872 *) &kD.1965.D.2190.D.2155.domain_mD.2002.bufferD.2015
in

<L0>:;
  currIndex_114 = 1;
  D.2554_122 = (struct Loc<1> *) &k.D.2190.D.2155.domain_m.buffer;
  n.6_123 = 0; 
  D.2556_124 = 0;
  D.2557_125 = 0B;
  D.2548_126 = D.2554_122;
  this_130 = &D.2548_126->D.2101;
  dom_133 = &this_130->D.2064.domain_m;
  #   k_160 = V_MAY_DEF <k_150>;
  *dom_133 = 0;
  D.2540_141 = 1;
  
<L29>:;
  currIndex_79 = 2;
  n.6_88 = 1;
  D.2604_89 = 4;
  D.2605_90 = 4B;
  D.2596_91 = D.2554_122 + 4B;
  this_95 = &D.2596_91->D.2101;
  dom_98 = &this_95->D.2064.domain_m;
  #   k_63 = V_MAY_DEF <k_160>;
  *dom_98 = 1;
  D.2588_106 = 1;
  D.2641_47 = (struct Loc<1> *) &k.D.2190.D.2155.domain_m.buffer;
  this_55 = &D.2641_47->D.2101;
  #   VUSE <TMT.12_38>;
  #   VUSE <k_63>;
  d_57 = this_55->D.2064.domain_m;
  return d_57;


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[rguenth at gcc dot gnu dot org]

------- Additional Comments From rguenth at gcc dot gnu dot org  2005-04-07 10:30 -------
Created an attachment (id=8554)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=8554&action=view)
Revised testcase without confusing casts

This changes the testcase to not cast int* to Loc<1>*, but use Loc<1>[2] as
storage for Loc<2> while retaining the initialization properties.  It requires
the testcase be compiled with tree-level loop-unrolling enabled, as the empty
constructors/destructors for array members are created as loops by the C++
frontend.

Other than that, struct aliasing (or just removing the casts) doesn't fix the
aliasing problems - though struct aliasing doesn't handle array elements at
the moment(?).

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
Attachment #8062 is|0                           |1
           obsolete|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-04-07 12:48 -------
Subject: Re:  Aliasing says stores to local
	memory do alias


> Other than that, struct aliasing (or just removing the casts) doesn't fix the
> aliasing problems - though struct aliasing doesn't handle array elements at
> the moment(?).

Correct, it does not.

> 



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[rguenth at tat dot physik dot uni-tuebingen dot de]

------- Additional Comments From rguenth at tat dot physik dot uni-tuebingen dot de  2005-04-07 12:50 -------
Subject: Re:  Aliasing says stores to local
 memory do alias

On 7 Apr 2005, dberlin at dberlin dot org wrote:

>
> ------- Additional Comments From dberlin at gcc dot gnu dot org  2005-04-07 12:48 -------
> Subject: Re:  Aliasing says stores to local
> 	memory do alias
>
>
> > Other than that, struct aliasing (or just removing the casts) doesn't fix the
> > aliasing problems - though struct aliasing doesn't handle array elements at
> > the moment(?).
>
> Correct, it does not.

Ok, at least the RTL optimizers figure out that these stack locals
cannot alias.  Hope we get this for the tree optimizers, too.

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-04-07 16:43 -------
Subject: Re:  Aliasing says stores to local
	memory do alias

> >
> >
> > > Other than that, struct aliasing (or just removing the casts) doesn't fix the
> > > aliasing problems - though struct aliasing doesn't handle array elements at
> > > the moment(?).
> >
> > Correct, it does not.
> 
> Ok, at least the RTL optimizers figure out that these stack locals
> cannot alias.  Hope we get this for the tree optimizers, too.

It's already in my plans. It's just the implementation is a bit trickier
than one would like :)




-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-04-07 22:55 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-04-07 22:55:38
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-13 13:18 -------
Most of the problem is PR 17141, the other problem comes into play with struct aliasing issues.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |17141


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[law at redhat dot com]

-- 
Bug 19626 depends on bug 17141, which changed state.

Bug 17141 Summary: *&a->b is not folded
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17141

           What    |Old Value                   |New Value
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-17 17:35 -------
We now get:
  dX.D.2296.D.2252.domain_m[0].D.2209.D.2200.D.2154.domain_m = 1;
  dX.D.2296.D.2252.domain_m[1].D.2209.D.2200.D.2154.domain_m = 0;
  k.D.2296.D.2252.domain_m[0].D.2209.D.2200.D.2154.domain_m = 0;
  k.D.2296.D.2252.domain_m[1].D.2209.D.2200.D.2154.domain_m = 1;
  return k.D.2296.D.2252.domain_m[0].D.2209.D.2200.D.2154.domain_m + 
dX.D.2296.D.2252.domain_m[0].D.2209.D.2200.D.2154.domain_m;

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[rguenth at gcc dot gnu dot org]

------- Additional Comments From rguenth at gcc dot gnu dot org  2005-05-18 21:51 -------
Nice.  Now it's really an aliasing problem only - and maybe bad timing for when
we end up with such nice state.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626

[Bug tree-optimization/19626] Aliasing says stores to local memory do alias

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-06-09 16:32 -------
This has now been fixed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.1.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19626