[lto] set alias info, poorly

[lto] set alias info, poorly

[Nathan Froyd]

First, the good news about this patch: it fixes a few failing testcases.

The bad news is that it does it with a very heavy hammer.  We say that
every type can alias every other type.  Obviously this wreaks havoc with
all the clever alias analysis that has gone into GCC over the years.

There are better, cleverer, more involved ways that you could fix this.
But this demonstrably works right now.  Ideas on what to do in the
future welcome.

Committed to the LTO branch.

-Nathan

2007-12-06  Nathan Froyd  <froydnj@codesourcery.com>

	* lto.c (lto_read_DIE): Set TYPE_ALIAS_SET where necessary.

Index: lto.c
===================================================================
--- lto.c	(revision 130663)
+++ lto.c	(working copy)
@@ -3253,7 +3253,13 @@ lto_read_DIE (lto_info_fd *fd, lto_conte
 	  /* If this DIE refers to a type, cache the value so that future
 	     references to the type can be processed quickly.  */
 	  if (val && TYPE_P (val))
-	    lto_cache_store_DIE (fd, die, val);
+	    {
+	      /* In the absence of a better solution, say that we alias
+		 everything FIXME.  */
+	      TYPE_ALIAS_SET (val) = 0;
+
+	      lto_cache_store_DIE (fd, die, val);
+	    }
 
           context->skip_non_parameters = saved_skip_non_parameters;
 	}

Re: [lto] set alias info, poorly

[Richard Guenther]

On Dec 6, 2007 11:29 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
> First, the good news about this patch: it fixes a few failing testcases.
>
> The bad news is that it does it with a very heavy hammer.  We say that
> every type can alias every other type.  Obviously this wreaks havoc with
> all the clever alias analysis that has gone into GCC over the years.
>
> There are better, cleverer, more involved ways that you could fix this.
> But this demonstrably works right now.  Ideas on what to do in the
> future welcome.

I believe we have to write out the alias sets and the conflict map and at the
point we combine types of different translation units we have to merge the
alias sets and conflict maps properly.

Or not rely on TBAA for LTO, which is what your patch does (so I guess for
completeness you should disable strict aliasing as well).

Richard.

Re: [lto] set alias info, poorly

[Jakub Jelinek]

On Fri, Dec 07, 2007 at 11:47:46AM +0100, Richard Guenther wrote:
> On Dec 6, 2007 11:29 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
> > First, the good news about this patch: it fixes a few failing testcases.
> >
> > The bad news is that it does it with a very heavy hammer.  We say that
> > every type can alias every other type.  Obviously this wreaks havoc with
> > all the clever alias analysis that has gone into GCC over the years.
> >
> > There are better, cleverer, more involved ways that you could fix this.
> > But this demonstrably works right now.  Ideas on what to do in the
> > future welcome.
> 
> I believe we have to write out the alias sets and the conflict map and at the
> point we combine types of different translation units we have to merge the
> alias sets and conflict maps properly.

Yeah, basically write LTO's own get_alias_set langhook, which will act as
the C one for C CUs, as C++ for C++ CUs, as Fortran for Fortran CUs etc. and
additionally define what kind of aliasing is/is not possible for types
passed from one language to a different one.

	Jakub

Re: [lto] set alias info, poorly

[Kenneth Zadeck]

Jakub Jelinek wrote:
> On Fri, Dec 07, 2007 at 11:47:46AM +0100, Richard Guenther wrote:
>   
>> On Dec 6, 2007 11:29 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
>>     
>>> First, the good news about this patch: it fixes a few failing testcases.
>>>
>>> The bad news is that it does it with a very heavy hammer.  We say that
>>> every type can alias every other type.  Obviously this wreaks havoc with
>>> all the clever alias analysis that has gone into GCC over the years.
>>>
>>> There are better, cleverer, more involved ways that you could fix this.
>>> But this demonstrably works right now.  Ideas on what to do in the
>>> future welcome.
>>>       
>> I believe we have to write out the alias sets and the conflict map and at the
>> point we combine types of different translation units we have to merge the
>> alias sets and conflict maps properly.
>>     
>
> Yeah, basically write LTO's own get_alias_set langhook, which will act as
> the C one for C CUs, as C++ for C++ CUs, as Fortran for Fortran CUs etc. and
> additionally define what kind of aliasing is/is not possible for types
> passed from one language to a different one.
>
> 	Jakub
>   
What Nathan did not say was that he was doing this at the direction of
Diego, Mark and myself.
We had a conference call to discuss how to deal with this issue, both in
the short term and the long term.  This was the short term solution and
all of us understood that this is not a particularly good short term
solution.

The longer term solution will be quite complex and is at this point not
well understood. 
Nathan's patch turns off the part of the alias analysis where the front
end gets to make the final decision if two types alias. 

My personal take on how to reimplement this langhook is that we will end
up tagging every type with an indication of which front end it came
from.  If you want to ask a question about two types, the first part of
that check will to see if the types come from the same front end.  If
they do, then this issue can be resolved by asking some language
dependent code that will be located in the middle end of the compiler. 

If the two types come from different front ends, then the question will
be resolved using a language dependent, and therefore relatively
pessimistic, structural test.  I do not like doing this, but the
aliasing rules for different languages are quite different and cost of
just ignoring them is quite high. 

I know that different people on that call have different takes on this
than mine.  At the very least this is something that requires a lot of
discussion by not just us, but the entire community as well the
resources to implement what is likely to be a lot of work.  We certainly
did not have a simple solution that did better. Writing out the alias
sets and then trying to merge them when the input comes from different
languages seems to me to be a bad way to go. 

However, the view of the people on the call was that we had to go for
correctness and coverage right now so that the community had something
stable to play with.

Kenny

Re: [lto] set alias info, poorly

[Toon Moene]

Kenneth Zadeck wrote:

> If you want to ask a question about two types, the first part of
> that check will to see if the types come from the same front end.  If
> they do, then this issue can be resolved by asking some language
> dependent code that will be located in the middle end of the compiler. 

Well, that will mean that it'll be a fascinating piece of "language 
dependent code [...] located in the middle end of the compiler".

The Fortran rules are basically:  If you don't *tell* the compiler 
(hence the front end) that two items alias, they don't.

I think this means that LTO *with* Fortran-sensible alias analysis will 
only work if the Fortran front end actually determines alias equivalence 
sets and passes that down to the middle end, which then (in this 
magically "language dependent code") has to do something intelligent 
with it ...

Hmmmm, magic ...

-- 
Toon Moene - e-mail: toon@moene.indiv.nluug.nl - phone: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
At home: http://moene.indiv.nluug.nl/~toon/
GNU Fortran's path to Fortran 2003: http://gcc.gnu.org/wiki/Fortran2003

Re: [lto] set alias info, poorly

[Kenneth Zadeck]

Toon Moene wrote:
> Kenneth Zadeck wrote:
>
>> If you want to ask a question about two types, the first part of
>> that check will to see if the types come from the same front end.  If
>> they do, then this issue can be resolved by asking some language
>> dependent code that will be located in the middle end of the compiler. 
>
> Well, that will mean that it'll be a fascinating piece of "language
> dependent code [...] located in the middle end of the compiler".
>
> The Fortran rules are basically:  If you don't *tell* the compiler
> (hence the front end) that two items alias, they don't.
>
> I think this means that LTO *with* Fortran-sensible alias analysis
> will only work if the Fortran front end actually determines alias
> equivalence sets and passes that down to the middle end, which then
> (in this magically "language dependent code") has to do something
> intelligent with it ...
And then we will need to "merge" that info as we bring in the code for
other fortran modules. 
i am not happy about going down this path, but the loss of that info is
not a good choice either. 

Consider the java case where two pointers cannot alias unless the type
of one pointer is derived from the other.  This means that most pointers
do not alias rather than the c/c++ case where most pointers can possibly
alias.

>
> Hmmmm, magic ...
>

Re: [lto] set alias info, poorly

[Richard Guenther]

On Dec 10, 2007 9:01 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> Toon Moene wrote:
> > Kenneth Zadeck wrote:
> >
> >> If you want to ask a question about two types, the first part of
> >> that check will to see if the types come from the same front end.  If
> >> they do, then this issue can be resolved by asking some language
> >> dependent code that will be located in the middle end of the compiler.
> >
> > Well, that will mean that it'll be a fascinating piece of "language
> > dependent code [...] located in the middle end of the compiler".
> >
> > The Fortran rules are basically:  If you don't *tell* the compiler
> > (hence the front end) that two items alias, they don't.
> >
> > I think this means that LTO *with* Fortran-sensible alias analysis
> > will only work if the Fortran front end actually determines alias
> > equivalence sets and passes that down to the middle end, which then
> > (in this magically "language dependent code") has to do something
> > intelligent with it ...
> And then we will need to "merge" that info as we bring in the code for
> other fortran modules.
> i am not happy about going down this path, but the loss of that info is
> not a good choice either.
>
> Consider the java case where two pointers cannot alias unless the type
> of one pointer is derived from the other.  This means that most pointers
> do not alias rather than the c/c++ case where most pointers can possibly
> alias.

The only maintainable way I see is to define middle-end rules (based on
structural analysis) that are a conservative approximation of the union of
the rules of all supported languages.  Or punt with TBAA completely for
LTO.

Richard.

Re: [lto] set alias info, poorly

[Kenneth Zadeck]

Richard Guenther wrote:
> On Dec 10, 2007 9:01 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>   
>> Toon Moene wrote:
>>     
>>> Kenneth Zadeck wrote:
>>>
>>>       
>>>> If you want to ask a question about two types, the first part of
>>>> that check will to see if the types come from the same front end.  If
>>>> they do, then this issue can be resolved by asking some language
>>>> dependent code that will be located in the middle end of the compiler.
>>>>         
>>> Well, that will mean that it'll be a fascinating piece of "language
>>> dependent code [...] located in the middle end of the compiler".
>>>
>>> The Fortran rules are basically:  If you don't *tell* the compiler
>>> (hence the front end) that two items alias, they don't.
>>>
>>> I think this means that LTO *with* Fortran-sensible alias analysis
>>> will only work if the Fortran front end actually determines alias
>>> equivalence sets and passes that down to the middle end, which then
>>> (in this magically "language dependent code") has to do something
>>> intelligent with it ...
>>>       
>> And then we will need to "merge" that info as we bring in the code for
>> other fortran modules.
>> i am not happy about going down this path, but the loss of that info is
>> not a good choice either.
>>
>> Consider the java case where two pointers cannot alias unless the type
>> of one pointer is derived from the other.  This means that most pointers
>> do not alias rather than the c/c++ case where most pointers can possibly
>> alias.
>>     
>
> The only maintainable way I see is to define middle-end rules (based on
> structural analysis) that are a conservative approximation of the union of
> the rules of all supported languages.  Or punt with TBAA completely for
> LTO.
>
> Richard.
>   
i think that you make a mistake to assume that just because type based
aliasing is mostly useless in c/c++, that it is useless in every
language.  it is not. I believe that giving up on this will be a mistake.

Kenny

Re: [lto] set alias info, poorly

[Richard Guenther]

On Dec 10, 2007 9:49 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>
> Richard Guenther wrote:
> > On Dec 10, 2007 9:01 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> >
> >> Toon Moene wrote:
> >>
> >>> Kenneth Zadeck wrote:
> >>>
> >>>
> >>>> If you want to ask a question about two types, the first part of
> >>>> that check will to see if the types come from the same front end.  If
> >>>> they do, then this issue can be resolved by asking some language
> >>>> dependent code that will be located in the middle end of the compiler.
> >>>>
> >>> Well, that will mean that it'll be a fascinating piece of "language
> >>> dependent code [...] located in the middle end of the compiler".
> >>>
> >>> The Fortran rules are basically:  If you don't *tell* the compiler
> >>> (hence the front end) that two items alias, they don't.
> >>>
> >>> I think this means that LTO *with* Fortran-sensible alias analysis
> >>> will only work if the Fortran front end actually determines alias
> >>> equivalence sets and passes that down to the middle end, which then
> >>> (in this magically "language dependent code") has to do something
> >>> intelligent with it ...
> >>>
> >> And then we will need to "merge" that info as we bring in the code for
> >> other fortran modules.
> >> i am not happy about going down this path, but the loss of that info is
> >> not a good choice either.
> >>
> >> Consider the java case where two pointers cannot alias unless the type
> >> of one pointer is derived from the other.  This means that most pointers
> >> do not alias rather than the c/c++ case where most pointers can possibly
> >> alias.
> >>
> >
> > The only maintainable way I see is to define middle-end rules (based on
> > structural analysis) that are a conservative approximation of the union of
> > the rules of all supported languages.  Or punt with TBAA completely for
> > LTO.
> >
> > Richard.
> >
> i think that you make a mistake to assume that just because type based
> aliasing is mostly useless in c/c++, that it is useless in every
> language.  it is not. I believe that giving up on this will be a mistake.

Well, I didn't suggest that this is the only way to go, but it is
certainly the easiest
one ;)  Note that we can easily retain some basic TBAA for example for
(arrays of)
scalars without requiring to figure out the common subset that works for
structural analysis.  Also whole-program PTA should reduce the effects of TBAA
even more, which I thought is one point why you want to have LTO.

Richard.