Bug 19626 - Aliasing says stores to local memory do alias
Summary: Aliasing says stores to local memory do alias
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.0.0
: P3 enhancement
Target Milestone: 4.1.0
Assignee: Not yet assigned to anyone
URL:
Keywords: alias, missed-optimization, TREE
Depends on: 17141
Blocks:
  Show dependency treegraph
 
Reported: 2005-01-25 16:56 UTC by Richard Biener
Modified: 2005-06-09 16:32 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2005-04-07 22:55:38


Attachments
testcase (1.48 KB, text/plain)
2005-01-25 16:57 UTC, Richard Biener
Details
Revised testcase without confusing casts (1.43 KB, text/plain)
2005-04-07 10:30 UTC, Richard Biener
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Richard Biener 2005-01-25 16:56:29 UTC
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.
Comment 1 Richard Biener 2005-01-25 16:57:05 UTC
Created attachment 8062 [details]
testcase
Comment 2 Andrew Pinski 2005-01-25 17:15:45 UTC
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;
Comment 3 Andrew Pinski 2005-01-25 17:20:16 UTC
  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> *.
Comment 4 Richard Biener 2005-01-26 08:47:10 UTC
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?

Comment 5 Richard Biener 2005-02-10 13:18:08 UTC
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;
Comment 6 Richard Biener 2005-04-07 10:30:19 UTC
Created attachment 8554 [details]
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(?).
Comment 7 Daniel Berlin 2005-04-07 12:48:39 UTC
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.

> 

Comment 8 Richard Biener 2005-04-07 12:50:22 UTC
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/

Comment 9 Daniel Berlin 2005-04-07 16:43:43 UTC
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 :)


Comment 10 Andrew Pinski 2005-04-07 22:55:38 UTC
Confirmed.
Comment 11 Andrew Pinski 2005-05-13 13:18:42 UTC
Most of the problem is PR 17141, the other problem comes into play with struct aliasing issues.
Comment 12 Andrew Pinski 2005-05-17 17:35:56 UTC
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;
Comment 13 Richard Biener 2005-05-18 21:51:58 UTC
Nice.  Now it's really an aliasing problem only - and maybe bad timing for when
we end up with such nice state.
Comment 14 Andrew Pinski 2005-06-09 16:32:51 UTC
This has now been fixed.