* Comparing types at LTO time @ 2020-01-09 2:05 Gary Oblock 2020-01-09 8:53 ` Jan Hubicka 0 siblings, 1 reply; 7+ messages in thread From: Gary Oblock @ 2020-01-09 2:05 UTC (permalink / raw) To: gcc 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Comparing types at LTO time 2020-01-09 2:05 Comparing types at LTO time Gary Oblock @ 2020-01-09 8:53 ` Jan Hubicka 2020-01-09 11:51 ` Richard Biener 0 siblings, 1 reply; 7+ messages in thread From: Jan Hubicka @ 2020-01-09 8:53 UTC (permalink / raw) To: Gary Oblock; +Cc: gcc > 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 > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Comparing types at LTO time 2020-01-09 8:53 ` Jan Hubicka @ 2020-01-09 11:51 ` Richard Biener 2020-01-09 20:36 ` [EXT] " Gary Oblock 0 siblings, 1 reply; 7+ messages in thread From: Richard Biener @ 2020-01-09 11:51 UTC (permalink / raw) To: Jan Hubicka; +Cc: Gary Oblock, gcc 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 > > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [EXT] Re: Comparing types at LTO time 2020-01-09 11:51 ` Richard Biener @ 2020-01-09 20:36 ` Gary Oblock 2020-01-10 10:30 ` Richard Biener 0 siblings, 1 reply; 7+ messages in thread From: Gary Oblock @ 2020-01-09 20:36 UTC (permalink / raw) To: Richard Biener, Jan Hubicka; +Cc: gcc 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 > > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [EXT] Re: Comparing types at LTO time 2020-01-09 20:36 ` [EXT] " Gary Oblock @ 2020-01-10 10:30 ` Richard Biener 2020-01-10 23:47 ` Gary Oblock 0 siblings, 1 reply; 7+ messages in thread From: Richard Biener @ 2020-01-10 10:30 UTC (permalink / raw) To: Gary Oblock; +Cc: Jan Hubicka, gcc 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 > > > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [EXT] Re: Comparing types at LTO time 2020-01-10 10:30 ` Richard Biener @ 2020-01-10 23:47 ` Gary Oblock 2020-01-13 13:01 ` Richard Biener 0 siblings, 1 reply; 7+ messages in thread From: Gary Oblock @ 2020-01-10 23:47 UTC (permalink / raw) To: Richard Biener; +Cc: Jan Hubicka, gcc 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 > > > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [EXT] Re: Comparing types at LTO time 2020-01-10 23:47 ` Gary Oblock @ 2020-01-13 13:01 ` Richard Biener 0 siblings, 0 replies; 7+ messages in thread From: Richard Biener @ 2020-01-13 13:01 UTC (permalink / raw) To: Gary Oblock; +Cc: Jan Hubicka, gcc 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 > > > > ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2020-01-13 10:26 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-01-09 2:05 Comparing types at LTO time Gary Oblock 2020-01-09 8:53 ` Jan Hubicka 2020-01-09 11:51 ` Richard Biener 2020-01-09 20:36 ` [EXT] " Gary Oblock 2020-01-10 10:30 ` Richard Biener 2020-01-10 23:47 ` Gary Oblock 2020-01-13 13:01 ` Richard Biener
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).