Re: [PATCH][RFC] Adjust the middle-end memory model

Re: [PATCH][RFC] Adjust the middle-end memory model

[Richard Guenther]

On Fri, 8 May 2009, Richard Guenther wrote:

> 
> This adjusts the middle-end memory model to properly honor type-based
> aliasing rules set by the C and C++ standards.
> 
> The bulk of the patch gets rid of our previous attempts to fix
> the issues around placement new and friends, CHANGE_DYNAMIC_TYPE_EXPR
> and DECL_NO_TBAA_P.  The core pieces are separated in the changelog.
> 
>  - We no longer prune points-to sets using TBAA (there is no noticable
>    slowdown because of this in SPEC 2000 or SPEC 2006).  This is
>    because we need unpruned points-to sets to compute anti and
>    output dependencies.  We could keep both pruned and unpruned sets,
>    but the only differences should be in disambiguating two accesses
>    via pointers.  Another advantage is that we can re-activate
>    merge_alias_info again with unpruned sets.
> 
>  - The instruction scheduler (or rather, anti_dependence and
>    output_dependence) no longer can use TBAA information.
> 
>  - The tree alias oracle got similar functionality, refs_anti_dependent
>    and refs_output_dependent and the tree level data dependence
>    analysis code makes use of these.
> 
> What remains to be done?
> 
>  - The alias warning code during points-to analysis needs to be
>    re-done again.  It relies on the availability of pruned points-to sets.

It looks like fixing the current flow-insensitive warning code will
not be particularly helpful as it will cause (as it does now) false
positives once you use placement new in C++.

Instead a flow-sensitive variant should be implemented and the
C frontend implementation be enhanced to warn about (the invalid in C
but valid in C++) type-punning of decls with a declared type.

I do not have time to do this at the moment but will file an
enhancement request and queue it in my TODO.

Thus, stay tuned for the final patch (appearantly there are no
objections in general looking at the responses to the original mail).

Thanks,
Richard.

Re: [PATCH][RFC] Adjust the middle-end memory model

[Mark Mitchell]

Richard Guenther wrote:

>>  - The tree alias oracle got similar functionality, refs_anti_dependent
>>    and refs_output_dependent and the tree level data dependence
>>    analysis code makes use of these.

Do we still use TBAA for the original motivating reason for adding it,
e.g.,:

  void f(float *f, int *n) {
    for (int i = 0; i < *n; ++i) {
      f[i] *= 2;
    }
  }

where here you want to know that "f[i]" does not modify "*n"?

(Yes, that code is kinda hokey, in that real-world code would probably
not pass n by-reference, but of course this happens with structures and
such...)

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH][RFC] Adjust the middle-end memory model

[Richard Guenther]

On Tue, 19 May 2009, Mark Mitchell wrote:

> Richard Guenther wrote:
> 
> >>  - The tree alias oracle got similar functionality, refs_anti_dependent
> >>    and refs_output_dependent and the tree level data dependence
> >>    analysis code makes use of these.
> 
> Do we still use TBAA for the original motivating reason for adding it,
> e.g.,:
> 
>   void f(float *f, int *n) {
>     for (int i = 0; i < *n; ++i) {
>       f[i] *= 2;
>     }
>   }
> 
> where here you want to know that "f[i]" does not modify "*n"?
> 
> (Yes, that code is kinda hokey, in that real-world code would probably
> not pass n by-reference, but of course this happens with structures and
> such...)

Yes, for the purpose of hoisting the load of *n out of the loop (if
a store to f[i] would clobber *n then you wouldn't be allowed to read
it back as int).  What matters for hoisting loads is whether there
is a true dependence between *n and f[i] which there is not, as we
still disambiguate using TBAA for true dependence queries.

The difference is if you want to sink a load from *n beyond the
store to f[i] - in which case you ask if there is an anti-dependence
which we cannot exclude in this case (no TBAA is allowed here).

The latter is to make placement new and friends work.

Richard.

Re: [PATCH][RFC] Adjust the middle-end memory model

[Mark Mitchell]

Richard Guenther wrote:

>>   void f(float *f, int *n) {
>>     for (int i = 0; i < *n; ++i) {
>>       f[i] *= 2;
>>     }
>>   }

> The difference is if you want to sink a load from *n beyond the
> store to f[i] - in which case you ask if there is an anti-dependence
> which we cannot exclude in this case (no TBAA is allowed here).

By "not allowed", you don't mean "would be an invalid optimization", but
rather "will no longer be done by GCC", right?

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH][RFC] Adjust the middle-end memory model

[Richard Guenther]

On Wed, 20 May 2009, Mark Mitchell wrote:

> Richard Guenther wrote:
> 
> >>   void f(float *f, int *n) {
> >>     for (int i = 0; i < *n; ++i) {
> >>       f[i] *= 2;
> >>     }
> >>   }
> 
> > The difference is if you want to sink a load from *n beyond the
> > store to f[i] - in which case you ask if there is an anti-dependence
> > which we cannot exclude in this case (no TBAA is allowed here).
> 
> By "not allowed", you don't mean "would be an invalid optimization", but
> rather "will no longer be done by GCC", right?

Right, not invalid in the above case but nevertheless no longer being
done by GCC.  This is to properly support

int i;
float f;
void foo()
{
  int *p = (int *)malloc(sizeof(int));
  *p = 1;
  i = *p;
  float *q = (float *)p;
  *q = 2.0;
  f = *q;
}

where we need to avoid scheduling the store via *q before the load
from *p.  The above is valid as I read C99 6.5/6, it is an object
with no declared type (obtained via malloc) and has type int
due to the store via *p "for that access and for subsequent accesses
_that do not modify the stored value_." (emphasis mine).  So for
objects without a declared type C can do "placement new" by simply
storing with a different type.  In C++ we of course have the
usual placement new situations.

Richard.

Re: [PATCH][RFC] Adjust the middle-end memory model

[Mark Mitchell]

Richard Guenther wrote:

> int i;
> float f;
> void foo()
> {
>   int *p = (int *)malloc(sizeof(int));
>   *p = 1;
>   i = *p;
>   float *q = (float *)p;
>   *q = 2.0;
>   f = *q;
> }

Yes, I think that's a valid program too.  I'm OK with giving up this
optimization; clearly we need to be correct first and foremost.

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH][RFC] Adjust the middle-end memory model

[Richard Guenther]

On Wed, 20 May 2009, Mark Mitchell wrote:

> Richard Guenther wrote:
> 
> > int i;
> > float f;
> > void foo()
> > {
> >   int *p = (int *)malloc(sizeof(int));
> >   *p = 1;
> >   i = *p;
> >   float *q = (float *)p;
> >   *q = 2.0;
> >   f = *q;
> > }
> 
> Yes, I think that's a valid program too.  I'm OK with giving up this
> optimization; clearly we need to be correct first and foremost.

Yes, that's the primary motivation of this patch.  Can I take this
as an approval for the C++ frontend changes?

Thanks,
Richard.

Re: [PATCH][RFC] Adjust the middle-end memory model

[Mark Mitchell]

Richard Guenther wrote:

> Yes, that's the primary motivation of this patch.  Can I take this
> as an approval for the C++ frontend changes?

OK.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713