Comparing types at LTO time

Comparing types at LTO time

[Gary Oblock]

There doesn't seem to be a way to compare types at LTO time. The functions
same_type_p and comptypes are front end only if I'm not totally confused
(which is quite possible) and type_hash_eq doesn't seem to apply for
structure types. Please, any advice would be welcome.

Thanks,

Gary Oblock

Re: Comparing types at LTO time

[Jan Hubicka]

> There doesn't seem to be a way to compare types at LTO time. The functions
> same_type_p and comptypes are front end only if I'm not totally confused
> (which is quite possible) and type_hash_eq doesn't seem to apply for
> structure types. Please, any advice would be welcome.

At LTO time it is bit hard to say what really is the "same type".  We
have multiple notions of equivalence:
 1) TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2)
    means that both types were equal in tree merging at stream in, this
    means that their IL representaiton is identical.

    This will lead to "false" for types that are same bud did not get
    merged for various reasons. One such valid reason, for example, is
    visibility of associated virtual tables
 2) types_types_same_for_odr returns true if types are considered same
    by C++ one definition rule.  This is reliable but works only for C++
    types with names (structures and unions)
 3) same_type_for_tbaa returns true if types are equivalent for type
    based alias analysis.  It returns true in much more cases than 1
    but is too coarse if you want to do datastructure changes.

So in general this is quite hard problem (and in fact I started to play
with ODR types originally to understand it better).  I would suggest
starting with 1 if you want to rewrite types and eventually add a new
comparsion once pass does something useful.

Richard may have some extra insights.

Honza
> 
> Thanks,
> 
> Gary Oblock
> 

Re: Comparing types at LTO time

[Richard Biener]

On Thu, Jan 9, 2020 at 9:53 AM Jan Hubicka <hubicka@ucw.cz> wrote:
>
> > There doesn't seem to be a way to compare types at LTO time. The functions
> > same_type_p and comptypes are front end only if I'm not totally confused
> > (which is quite possible) and type_hash_eq doesn't seem to apply for
> > structure types. Please, any advice would be welcome.
>
> At LTO time it is bit hard to say what really is the "same type".  We
> have multiple notions of equivalence:
>  1) TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2)
>     means that both types were equal in tree merging at stream in, this
>     means that their IL representaiton is identical.
>
>     This will lead to "false" for types that are same bud did not get
>     merged for various reasons. One such valid reason, for example, is
>     visibility of associated virtual tables
>  2) types_types_same_for_odr returns true if types are considered same
>     by C++ one definition rule.  This is reliable but works only for C++
>     types with names (structures and unions)
>  3) same_type_for_tbaa returns true if types are equivalent for type
>     based alias analysis.  It returns true in much more cases than 1
>     but is too coarse if you want to do datastructure changes.
>
> So in general this is quite hard problem (and in fact I started to play
> with ODR types originally to understand it better).  I would suggest
> starting with 1 if you want to rewrite types and eventually add a new
> comparsion once pass does something useful.
>
> Richard may have some extra insights.

My advice would be to not go down the route that requires comparing types
since I'm not sure you can do that conservatively since you at the same
time may not say two types are equal when they are not nor miss two
equal types.  For example if you have a C TU and a Fortran TU there's
defined interoperability but the actual type representations are distinct
enough so that Honzas equality according to 1) doesn't trigger (nor does 2),
but 3) does, but that will identify too many types as equal.

Richard.

> Honza
> >
> > Thanks,
> >
> > Gary Oblock
> >

Re: [EXT] Re: Comparing types at LTO time

[Gary Oblock]

Richard,

Alas, when doing structure reorg I have to be able to know some
arbitrary use of variable X in some GIMPLE expression is of a
type that needs to be transformed in that given expression. I see no
way around this.
________________________________
From: Richard Biener <richard.guenther@gmail.com>
Sent: Thursday, January 9, 2020 3:51 AM
To: Jan Hubicka <hubicka@ucw.cz>
Cc: Gary Oblock <goblock@marvell.com>; gcc@gcc.gnu.org <gcc@gcc.gnu.org>
Subject: [EXT] Re: Comparing types at LTO time

External Email

----------------------------------------------------------------------
On Thu, Jan 9, 2020 at 9:53 AM Jan Hubicka <hubicka@ucw.cz> wrote:
>
> > There doesn't seem to be a way to compare types at LTO time. The functions
> > same_type_p and comptypes are front end only if I'm not totally confused
> > (which is quite possible) and type_hash_eq doesn't seem to apply for
> > structure types. Please, any advice would be welcome.
>
> At LTO time it is bit hard to say what really is the "same type".  We
> have multiple notions of equivalence:
>  1) TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2)
>     means that both types were equal in tree merging at stream in, this
>     means that their IL representaiton is identical.
>
>     This will lead to "false" for types that are same bud did not get
>     merged for various reasons. One such valid reason, for example, is
>     visibility of associated virtual tables
>  2) types_types_same_for_odr returns true if types are considered same
>     by C++ one definition rule.  This is reliable but works only for C++
>     types with names (structures and unions)
>  3) same_type_for_tbaa returns true if types are equivalent for type
>     based alias analysis.  It returns true in much more cases than 1
>     but is too coarse if you want to do datastructure changes.
>
> So in general this is quite hard problem (and in fact I started to play
> with ODR types originally to understand it better).  I would suggest
> starting with 1 if you want to rewrite types and eventually add a new
> comparsion once pass does something useful.
>
> Richard may have some extra insights.

My advice would be to not go down the route that requires comparing types
since I'm not sure you can do that conservatively since you at the same
time may not say two types are equal when they are not nor miss two
equal types.  For example if you have a C TU and a Fortran TU there's
defined interoperability but the actual type representations are distinct
enough so that Honzas equality according to 1) doesn't trigger (nor does 2),
but 3) does, but that will identify too many types as equal.

Richard.

> Honza
> >
> > Thanks,
> >
> > Gary Oblock
> >

Re: [EXT] Re: Comparing types at LTO time

[Richard Biener]

On Thu, Jan 9, 2020 at 9:36 PM Gary Oblock <goblock@marvell.com> wrote:
>
> Richard,
>
> Alas, when doing structure reorg I have to be able to know some
> arbitrary use of variable X in some GIMPLE expression is of a
> type that needs to be transformed in that given expression. I see no
> way around this.

Sure, if you view it as it transforming a type.  I see it as transforming
the layout of a specific object so all you need to know is whether an
arbitrary memory access accesses the very object - which you could,
if you face accesses you can't analyze, even check at runtime to some
extent (worst case by providing a copy in/out to a temporary with the
old layout).

Richard.

> ________________________________
> From: Richard Biener <richard.guenther@gmail.com>
> Sent: Thursday, January 9, 2020 3:51 AM
> To: Jan Hubicka <hubicka@ucw.cz>
> Cc: Gary Oblock <goblock@marvell.com>; gcc@gcc.gnu.org <gcc@gcc.gnu.org>
> Subject: [EXT] Re: Comparing types at LTO time
>
> External Email
>
> ----------------------------------------------------------------------
> On Thu, Jan 9, 2020 at 9:53 AM Jan Hubicka <hubicka@ucw.cz> wrote:
> >
> > > There doesn't seem to be a way to compare types at LTO time. The functions
> > > same_type_p and comptypes are front end only if I'm not totally confused
> > > (which is quite possible) and type_hash_eq doesn't seem to apply for
> > > structure types. Please, any advice would be welcome.
> >
> > At LTO time it is bit hard to say what really is the "same type".  We
> > have multiple notions of equivalence:
> >  1) TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2)
> >     means that both types were equal in tree merging at stream in, this
> >     means that their IL representaiton is identical.
> >
> >     This will lead to "false" for types that are same bud did not get
> >     merged for various reasons. One such valid reason, for example, is
> >     visibility of associated virtual tables
> >  2) types_types_same_for_odr returns true if types are considered same
> >     by C++ one definition rule.  This is reliable but works only for C++
> >     types with names (structures and unions)
> >  3) same_type_for_tbaa returns true if types are equivalent for type
> >     based alias analysis.  It returns true in much more cases than 1
> >     but is too coarse if you want to do datastructure changes.
> >
> > So in general this is quite hard problem (and in fact I started to play
> > with ODR types originally to understand it better).  I would suggest
> > starting with 1 if you want to rewrite types and eventually add a new
> > comparsion once pass does something useful.
> >
> > Richard may have some extra insights.
>
> My advice would be to not go down the route that requires comparing types
> since I'm not sure you can do that conservatively since you at the same
> time may not say two types are equal when they are not nor miss two
> equal types.  For example if you have a C TU and a Fortran TU there's
> defined interoperability but the actual type representations are distinct
> enough so that Honzas equality according to 1) doesn't trigger (nor does 2),
> but 3) does, but that will identify too many types as equal.
>
> Richard.
>
> > Honza
> > >
> > > Thanks,
> > >
> > > Gary Oblock
> > >

Re: [EXT] Re: Comparing types at LTO time

[Gary Oblock]

Richard,

Let me see if I've got this straight. Are you saying it's the
shape of objects combined with the variables that point at these
objects (or some subpart of them) that should drive struct reorg?
It seems to be hard to understand how to proceed from that notion
without something like types to fall back on.

If the struct reorg lumps all the types with the same shape together
into sets, aren't each of those sets type like and couldn't the sets be used
to drive the optimization?

Gary
________________________________
From: Richard Biener <richard.guenther@gmail.com>
Sent: Friday, January 10, 2020 2:29 AM
To: Gary Oblock <goblock@marvell.com>
Cc: Jan Hubicka <hubicka@ucw.cz>; gcc@gcc.gnu.org <gcc@gcc.gnu.org>
Subject: Re: [EXT] Re: Comparing types at LTO time

On Thu, Jan 9, 2020 at 9:36 PM Gary Oblock <goblock@marvell.com> wrote:
>
> Richard,
>
> Alas, when doing structure reorg I have to be able to know some
> arbitrary use of variable X in some GIMPLE expression is of a
> type that needs to be transformed in that given expression. I see no
> way around this.

Sure, if you view it as it transforming a type.  I see it as transforming
the layout of a specific object so all you need to know is whether an
arbitrary memory access accesses the very object - which you could,
if you face accesses you can't analyze, even check at runtime to some
extent (worst case by providing a copy in/out to a temporary with the
old layout).

Richard.

> ________________________________
> From: Richard Biener <richard.guenther@gmail.com>
> Sent: Thursday, January 9, 2020 3:51 AM
> To: Jan Hubicka <hubicka@ucw.cz>
> Cc: Gary Oblock <goblock@marvell.com>; gcc@gcc.gnu.org <gcc@gcc.gnu.org>
> Subject: [EXT] Re: Comparing types at LTO time
>
> External Email
>
> ----------------------------------------------------------------------
> On Thu, Jan 9, 2020 at 9:53 AM Jan Hubicka <hubicka@ucw.cz> wrote:
> >
> > > There doesn't seem to be a way to compare types at LTO time. The functions
> > > same_type_p and comptypes are front end only if I'm not totally confused
> > > (which is quite possible) and type_hash_eq doesn't seem to apply for
> > > structure types. Please, any advice would be welcome.
> >
> > At LTO time it is bit hard to say what really is the "same type".  We
> > have multiple notions of equivalence:
> >  1) TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2)
> >     means that both types were equal in tree merging at stream in, this
> >     means that their IL representaiton is identical.
> >
> >     This will lead to "false" for types that are same bud did not get
> >     merged for various reasons. One such valid reason, for example, is
> >     visibility of associated virtual tables
> >  2) types_types_same_for_odr returns true if types are considered same
> >     by C++ one definition rule.  This is reliable but works only for C++
> >     types with names (structures and unions)
> >  3) same_type_for_tbaa returns true if types are equivalent for type
> >     based alias analysis.  It returns true in much more cases than 1
> >     but is too coarse if you want to do datastructure changes.
> >
> > So in general this is quite hard problem (and in fact I started to play
> > with ODR types originally to understand it better).  I would suggest
> > starting with 1 if you want to rewrite types and eventually add a new
> > comparsion once pass does something useful.
> >
> > Richard may have some extra insights.
>
> My advice would be to not go down the route that requires comparing types
> since I'm not sure you can do that conservatively since you at the same
> time may not say two types are equal when they are not nor miss two
> equal types.  For example if you have a C TU and a Fortran TU there's
> defined interoperability but the actual type representations are distinct
> enough so that Honzas equality according to 1) doesn't trigger (nor does 2),
> but 3) does, but that will identify too many types as equal.
>
> Richard.
>
> > Honza
> > >
> > > Thanks,
> > >
> > > Gary Oblock
> > >

Re: [EXT] Re: Comparing types at LTO time

[Richard Biener]

On Sat, Jan 11, 2020 at 12:47 AM Gary Oblock <goblock@marvell.com> wrote:
>
> Richard,
>
> Let me see if I've got this straight. Are you saying it's the
> shape of objects combined with the variables that point at these
> objects (or some subpart of them) that should drive struct reorg?

Yes.  Shape of objects and accesses of that objects (directly or
indirectly via pointers).  For allocated objects that requires exact tracking
of object instances through tracking of the pointers.

> It seems to be hard to understand how to proceed from that notion
> without something like types to fall back on.
>
> If the struct reorg lumps all the types with the same shape together
> into sets, aren't each of those sets type like and couldn't the sets be used
> to drive the optimization?

Well sure.  But as said you need to be conservative in conflicting ways,
first you may not miss any "same shape"-ness _and_ you may not
detect any excess "same shape"-ness.  That's really hard to get correct.

With objects and pointers to objects the correctness boils down to conservative
tracking of objects which I think is well understood and can be even amended
with runtime checking.  The actual layout transform is then a bijection of
offset/size.

Yes, tracking pointers is difficult but you have to do that also for type-based
approaches.

Richard.

> Gary
> ________________________________
> From: Richard Biener <richard.guenther@gmail.com>
> Sent: Friday, January 10, 2020 2:29 AM
> To: Gary Oblock <goblock@marvell.com>
> Cc: Jan Hubicka <hubicka@ucw.cz>; gcc@gcc.gnu.org <gcc@gcc.gnu.org>
> Subject: Re: [EXT] Re: Comparing types at LTO time
>
> On Thu, Jan 9, 2020 at 9:36 PM Gary Oblock <goblock@marvell.com> wrote:
> >
> > Richard,
> >
> > Alas, when doing structure reorg I have to be able to know some
> > arbitrary use of variable X in some GIMPLE expression is of a
> > type that needs to be transformed in that given expression. I see no
> > way around this.
>
> Sure, if you view it as it transforming a type.  I see it as transforming
> the layout of a specific object so all you need to know is whether an
> arbitrary memory access accesses the very object - which you could,
> if you face accesses you can't analyze, even check at runtime to some
> extent (worst case by providing a copy in/out to a temporary with the
> old layout).
>
> Richard.
>
> > ________________________________
> > From: Richard Biener <richard.guenther@gmail.com>
> > Sent: Thursday, January 9, 2020 3:51 AM
> > To: Jan Hubicka <hubicka@ucw.cz>
> > Cc: Gary Oblock <goblock@marvell.com>; gcc@gcc.gnu.org <gcc@gcc.gnu.org>
> > Subject: [EXT] Re: Comparing types at LTO time
> >
> > External Email
> >
> > ----------------------------------------------------------------------
> > On Thu, Jan 9, 2020 at 9:53 AM Jan Hubicka <hubicka@ucw.cz> wrote:
> > >
> > > > There doesn't seem to be a way to compare types at LTO time. The functions
> > > > same_type_p and comptypes are front end only if I'm not totally confused
> > > > (which is quite possible) and type_hash_eq doesn't seem to apply for
> > > > structure types. Please, any advice would be welcome.
> > >
> > > At LTO time it is bit hard to say what really is the "same type".  We
> > > have multiple notions of equivalence:
> > >  1) TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2)
> > >     means that both types were equal in tree merging at stream in, this
> > >     means that their IL representaiton is identical.
> > >
> > >     This will lead to "false" for types that are same bud did not get
> > >     merged for various reasons. One such valid reason, for example, is
> > >     visibility of associated virtual tables
> > >  2) types_types_same_for_odr returns true if types are considered same
> > >     by C++ one definition rule.  This is reliable but works only for C++
> > >     types with names (structures and unions)
> > >  3) same_type_for_tbaa returns true if types are equivalent for type
> > >     based alias analysis.  It returns true in much more cases than 1
> > >     but is too coarse if you want to do datastructure changes.
> > >
> > > So in general this is quite hard problem (and in fact I started to play
> > > with ODR types originally to understand it better).  I would suggest
> > > starting with 1 if you want to rewrite types and eventually add a new
> > > comparsion once pass does something useful.
> > >
> > > Richard may have some extra insights.
> >
> > My advice would be to not go down the route that requires comparing types
> > since I'm not sure you can do that conservatively since you at the same
> > time may not say two types are equal when they are not nor miss two
> > equal types.  For example if you have a C TU and a Fortran TU there's
> > defined interoperability but the actual type representations are distinct
> > enough so that Honzas equality according to 1) doesn't trigger (nor does 2),
> > but 3) does, but that will identify too many types as equal.
> >
> > Richard.
> >
> > > Honza
> > > >
> > > > Thanks,
> > > >
> > > > Gary Oblock
> > > >