Re: Strenghten assumption about dynamic type changes (placement new)
On Wed, Jul 23, 2014 at 6:29 PM, Jan Hubicka hubi...@ucw.cz wrote: On July 23, 2014 4:42:22 PM CEST, Jan Hubicka hubi...@ucw.cz wrote: On Tue, Jul 22, 2014 at 5:17 PM, Jan Hubicka hubi...@ucw.cz wrote: I don't see why long x[1024]; Q *q = new (x) Q; q-~Q (); new (x) T; would be invalid. I also don't see why Q q; q.~Q (); new (q) T; would be. Object lifetime is precisely specified and I don't see where it is tied to (static) storage lifetime. This is precisely the testcase I posted on beggining of this thread. I do not see how the testcases can work with aliasing rules in the case Q's and T's memory is known to not alias. It works because of the well-defined memory model (with regarding to TBAA) in the middle-end. Every store changes the dynamic type of a memory location which means that you can only use TBAA for true-dependence checks (not anti-dependence or write-dependence checks). I see, I did not notice this change - it seems like quite a big hammer though, limiting scheduling (and loop opts) quite noticeably for all languages. Are there any other motivations for this besides placement new? Aggregate copies and memcpy transferring the dynamic type for example. Being able to tbaa union accesses for another. And yes, placement new. It's not so much an optimization preventing thing as you still can move loads up and stores down with the help of tbaa. well, but you lose extra parallelism like *shortptr = exp longer dependency chain with shortptr var = *shortptr *intptr = exp longer dependency chain with intptr var = *intptr Yes (that is, you can't hoist the *intptr = exp store above the var = *shortptr load with TBAA only). You can probably still hoist the longer dependency chain with intptr, it's not clear from your example. That said, being able to optimize union accesses with TBAA at all is still nice (esp. for GCC). Now, the C frontend still forces alias-set zero for this case because of the RTL alias oracle disfunctionality which doesn't treat a must-alias as an alias if it can TBAA disambiguate. Richard. Honza
Re: Strenghten assumption about dynamic type changes (placement new)
*shortptr = exp longer dependency chain with shortptr var = *shortptr *intptr = exp longer dependency chain with intptr var = *intptr Yes (that is, you can't hoist the *intptr = exp store above the var = *shortptr load with TBAA only). You can probably still hoist the longer dependency chain with intptr, it's not clear from your example. Well, this is placement new version of this, where of course the movement is not desirable. Obvioulsy the chains can not overlap: #include new #include stdio.h struct A {short a; short b; A(){a=1;}}; struct B {int a; B(){a=2;}}; struct A a; struct A *pa = a; struct B *pb = reinterpret_caststruct B *(a); int main() { int sum; struct A *ppa = pa; struct B *ppb = pb; if (!pa || !pb) return 1; ppa-~A(); new (ppa) A(); asm (#asm1:=m(ppa-a):m(ppa-a)); sum = ppa-a*11; new (ppb) B(); asm (#asm2:=m(ppb-a):m(ppb-a)); sum += ppb-a*11; printf (%i\n,sum); return 0; } Of course it makes us i.e. in t(short *a, short *b, int *c) { int i; for (i=0;i100;i++) c[i]=a[i]+b[i]; } generate the fallback case when vectorizing where c is overlapping with a or b, while clang doesn't. Honza That said, being able to optimize union accesses with TBAA at all is still nice (esp. for GCC). Now, the C frontend still forces alias-set zero for this case because of the RTL alias oracle disfunctionality which doesn't treat a must-alias as an alias if it can TBAA disambiguate. Richard. Honza
Re: Strenghten assumption about dynamic type changes (placement new)
On Thu, Jul 24, 2014 at 11:23 AM, Jan Hubicka hubi...@ucw.cz wrote: *shortptr = exp longer dependency chain with shortptr var = *shortptr *intptr = exp longer dependency chain with intptr var = *intptr Yes (that is, you can't hoist the *intptr = exp store above the var = *shortptr load with TBAA only). You can probably still hoist the longer dependency chain with intptr, it's not clear from your example. Well, this is placement new version of this, where of course the movement is not desirable. Obvioulsy the chains can not overlap: #include new #include stdio.h struct A {short a; short b; A(){a=1;}}; struct B {int a; B(){a=2;}}; struct A a; struct A *pa = a; struct B *pb = reinterpret_caststruct B *(a); int main() { int sum; struct A *ppa = pa; struct B *ppb = pb; if (!pa || !pb) return 1; ppa-~A(); new (ppa) A(); asm (#asm1:=m(ppa-a):m(ppa-a)); sum = ppa-a*11; new (ppb) B(); asm (#asm2:=m(ppb-a):m(ppb-a)); sum += ppb-a*11; printf (%i\n,sum); return 0; } Of course it makes us i.e. in t(short *a, short *b, int *c) { int i; for (i=0;i100;i++) c[i]=a[i]+b[i]; } generate the fallback case when vectorizing where c is overlapping with a or b, while clang doesn't. Yep. I bet clang gets it wrong with placement new (but then for PODs simply writing to a storage location ends lifetime of the old object in there and starts lifetime of a new object, so placement new is not needed to make an overlap valid as far as I read the standard(s)). So I don't think omitting the runtime alias check is valid for the above case. Richard. Honza That said, being able to optimize union accesses with TBAA at all is still nice (esp. for GCC). Now, the C frontend still forces alias-set zero for this case because of the RTL alias oracle disfunctionality which doesn't treat a must-alias as an alias if it can TBAA disambiguate. Richard. Honza
Re: Strenghten assumption about dynamic type changes (placement new)
On Thu, Jul 24, 2014 at 11:53 AM, Richard Biener richard.guent...@gmail.com wrote: On Thu, Jul 24, 2014 at 11:23 AM, Jan Hubicka hubi...@ucw.cz wrote: *shortptr = exp longer dependency chain with shortptr var = *shortptr *intptr = exp longer dependency chain with intptr var = *intptr Yes (that is, you can't hoist the *intptr = exp store above the var = *shortptr load with TBAA only). You can probably still hoist the longer dependency chain with intptr, it's not clear from your example. Well, this is placement new version of this, where of course the movement is not desirable. Obvioulsy the chains can not overlap: #include new #include stdio.h struct A {short a; short b; A(){a=1;}}; struct B {int a; B(){a=2;}}; struct A a; struct A *pa = a; struct B *pb = reinterpret_caststruct B *(a); int main() { int sum; struct A *ppa = pa; struct B *ppb = pb; if (!pa || !pb) return 1; ppa-~A(); new (ppa) A(); asm (#asm1:=m(ppa-a):m(ppa-a)); sum = ppa-a*11; new (ppb) B(); asm (#asm2:=m(ppb-a):m(ppb-a)); sum += ppb-a*11; printf (%i\n,sum); return 0; } Of course it makes us i.e. in t(short *a, short *b, int *c) { int i; for (i=0;i100;i++) c[i]=a[i]+b[i]; } generate the fallback case when vectorizing where c is overlapping with a or b, while clang doesn't. Yep. I bet clang gets it wrong with placement new (but then for PODs simply writing to a storage location ends lifetime of the old object in there and starts lifetime of a new object, so placement new is not needed to make an overlap valid as far as I read the standard(s)). So I don't think omitting the runtime alias check is valid for the above case. Btw, we don't create a runtime test here. The argument is as simple as overlap may only happen during iteration 0, otherwise you have an invalid read via short of sth stored via int. Thus if you are in loops you are usually fine to use TBAA. Richard. Richard. Honza That said, being able to optimize union accesses with TBAA at all is still nice (esp. for GCC). Now, the C frontend still forces alias-set zero for this case because of the RTL alias oracle disfunctionality which doesn't treat a must-alias as an alias if it can TBAA disambiguate. Richard. Honza
Re: Strenghten assumption about dynamic type changes (placement new)
Aggregate copies and memcpy transferring the dynamic type for example. Being able to tbaa union accesses for another. And yes, placement new. I see that if we previously dropped all union accesses to 0, the current scheme is nice improvement. But it seem to me it may be in use only when one of accesses is through union. How the memcpy case works? I always tought that memcpy does readswrites in set 0 that makes it to introduce the necessary conflicts. Similarly can't we make set 0 clobber of the memory retyped by placement new? If the clobber is hidden in external function call, we still have it as a side effect of the call. It would have to survive all the way down to RTL... Honza
Re: Strenghten assumption about dynamic type changes (placement new)
On Thu, Jul 24, 2014 at 12:46 PM, Jan Hubicka hubi...@ucw.cz wrote: Aggregate copies and memcpy transferring the dynamic type for example. Being able to tbaa union accesses for another. And yes, placement new. I see that if we previously dropped all union accesses to 0, the current scheme is nice improvement. But it seem to me it may be in use only when one of accesses is through union. How the memcpy case works? I always tought that memcpy does readswrites in set 0 that makes it to introduce the necessary conflicts. Yes, that's possible now (with MEM_REF), previously it was not and the memory model fixed it. Similarly can't we make set 0 clobber of the memory retyped by placement new? We don't have a way to do that, but yes, we could. But as said, for PODs you don't even need placement new. You can just store with a new type. Richard. If the clobber is hidden in external function call, we still have it as a side effect of the call. It would have to survive all the way down to RTL... Honza
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/23/2014 07:29 AM, Richard Biener wrote: On Wed, Jul 23, 2014 at 12:44 PM, Jason Merrill ja...@redhat.com wrote: On 07/22/2014 02:34 PM, Richard Biener wrote: As discussed during the Cauldron keeping some builtin doesn't help because you are not forced to access the newly created object via the pointer returned by the placement new. That is, template T struct Storage { char x[sizeof(T)]; Storage() { new (x) T; } T get() { return reinterpret_cast T (x); } }; is valid Yes. (and used in this way in Boost - with a type different from 'char' to force bigger alignment). But I don't think that should be valid, unless the type contains a char array at offset 0, as {std,boost}::aligned_storage; the C++ standard needs improvement in this area. Why especially at offset 0? I'm constructing in the place of 'x', not 'this'. Right, and I'm talking about the type of 'x', not the type of *this. Do you say that template class T struct Storage { T get(i) { return new (x + sizeof (T) * i) T; } Storage (int n_) n (n_) {} int n; char x[sizeof (T)]; }; and doing Storage *s = new (malloc (sizeof (int) * 4)) Storage (4); s-get (2); isn't valid? That's fine. Looks like the small buffer optimization in boost::spirit::hold_any would need to be tweaked, as it uses a void* to store anything the same size or smaller, but that's the only dodgy case I see. I've seen other odd cases in GCC bugreports ultimately coming from Boost friends (mpl or whatnot). Very likely older Boost versions of course. Btw, any reason why the standard treats 'char' and 'unsigned char' special but not 'signed char'? I think we'd prefer to only treat unsigned char specially, but plain char is also allowed for historical reasons. That said, as a matter of QOI I think only special-casing character types would be a bad thing (see your hold_any example). Well, there's a tradeoff between expressiveness and optimization. But perhaps you have a better sense of that than I. Jason
Re: Strenghten assumption about dynamic type changes (placement new)
On Tue, Jul 22, 2014 at 5:17 PM, Jan Hubicka hubi...@ucw.cz wrote: I don't see why long x[1024]; Q *q = new (x) Q; q-~Q (); new (x) T; would be invalid. I also don't see why Q q; q.~Q (); new (q) T; would be. Object lifetime is precisely specified and I don't see where it is tied to (static) storage lifetime. This is precisely the testcase I posted on beggining of this thread. I do not see how the testcases can work with aliasing rules in the case Q's and T's memory is known to not alias. It works because of the well-defined memory model (with regarding to TBAA) in the middle-end. Every store changes the dynamic type of a memory location which means that you can only use TBAA for true-dependence checks (not anti-dependence or write-dependence checks). That has been the way we operate since GCC 4.3 (if I remember correctly). That's also the reason we don't have to special-case unions in any tricky way (yeah, we still do - because of that type-punning special case and RTL alias analysis not dealing with it). Either we need to define what is and is not supported or go for speculative devirt more often. The GCC middle-end (which also has to deal with cross-language cases!) has this specified very clearly. Richard. Honza
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/22/2014 02:34 PM, Richard Biener wrote: As discussed during the Cauldron keeping some builtin doesn't help because you are not forced to access the newly created object via the pointer returned by the placement new. That is, template T struct Storage { char x[sizeof(T)]; Storage() { new (x) T; } T get() { return reinterpret_cast T (x); } }; is valid Yes. (and used in this way in Boost - with a type different from 'char' to force bigger alignment). But I don't think that should be valid, unless the type contains a char array at offset 0, as {std,boost}::aligned_storage; the C++ standard needs improvement in this area. Looks like the small buffer optimization in boost::spirit::hold_any would need to be tweaked, as it uses a void* to store anything the same size or smaller, but that's the only dodgy case I see. Jason
Re: Strenghten assumption about dynamic type changes (placement new)
On Wed, Jul 23, 2014 at 12:44 PM, Jason Merrill ja...@redhat.com wrote: On 07/22/2014 02:34 PM, Richard Biener wrote: As discussed during the Cauldron keeping some builtin doesn't help because you are not forced to access the newly created object via the pointer returned by the placement new. That is, template T struct Storage { char x[sizeof(T)]; Storage() { new (x) T; } T get() { return reinterpret_cast T (x); } }; is valid Yes. (and used in this way in Boost - with a type different from 'char' to force bigger alignment). But I don't think that should be valid, unless the type contains a char array at offset 0, as {std,boost}::aligned_storage; the C++ standard needs improvement in this area. Why especially at offset 0? I'm constructing in the place of 'x', not 'this'. Do you say that template class T struct Storage { T get(i) { return new (x + sizeof (T) * i) T; } Storage (int n_) n (n_) {} int n; char x[sizeof (T)]; }; and doing Storage *s = new (malloc (sizeof (int) * 4)) Storage (4); s-get (2); isn't valid? Looks like the small buffer optimization in boost::spirit::hold_any would need to be tweaked, as it uses a void* to store anything the same size or smaller, but that's the only dodgy case I see. I've seen other odd cases in GCC bugreports ultimately coming from Boost friends (mpl or whatnot). Very likely older Boost versions of course. Btw, any reason why the standard treats 'char' and 'unsigned char' special but not 'signed char'? That said, as a matter of QOI I think only special-casing character types would be a bad thing (see your hold_any example). Richard. Jason
Re: Strenghten assumption about dynamic type changes (placement new)
On Tue, Jul 22, 2014 at 5:17 PM, Jan Hubicka hubi...@ucw.cz wrote: I don't see why long x[1024]; Q *q = new (x) Q; q-~Q (); new (x) T; would be invalid. I also don't see why Q q; q.~Q (); new (q) T; would be. Object lifetime is precisely specified and I don't see where it is tied to (static) storage lifetime. This is precisely the testcase I posted on beggining of this thread. I do not see how the testcases can work with aliasing rules in the case Q's and T's memory is known to not alias. It works because of the well-defined memory model (with regarding to TBAA) in the middle-end. Every store changes the dynamic type of a memory location which means that you can only use TBAA for true-dependence checks (not anti-dependence or write-dependence checks). I see, I did not notice this change - it seems like quite a big hammer though, limiting scheduling (and loop opts) quite noticeably for all languages. Are there any other motivations for this besides placement new? That has been the way we operate since GCC 4.3 (if I remember correctly). That's also the reason we don't have to special-case unions in any tricky way (yeah, we still do - because of that type-punning special case and RTL alias analysis not dealing with it). Either we need to define what is and is not supported or go for speculative devirt more often. The GCC middle-end (which also has to deal with cross-language cases!) has this specified very clearly. Yep, the cross language support is bit more limited when you speak of polymorphic types. But indeed with the aliasing hack above I can imagine one can destroy one object and build new one on a given location. I will push things towards speculative types to allow implementing super-safe devirt and we could have flag strenghtening assumptions declaring that placement new is not used to change polymorphic type to other polymorphic type and we can see hw important it is in practice. Honza Richard. Honza
Re: Strenghten assumption about dynamic type changes (placement new)
On July 23, 2014 4:42:22 PM CEST, Jan Hubicka hubi...@ucw.cz wrote: On Tue, Jul 22, 2014 at 5:17 PM, Jan Hubicka hubi...@ucw.cz wrote: I don't see why long x[1024]; Q *q = new (x) Q; q-~Q (); new (x) T; would be invalid. I also don't see why Q q; q.~Q (); new (q) T; would be. Object lifetime is precisely specified and I don't see where it is tied to (static) storage lifetime. This is precisely the testcase I posted on beggining of this thread. I do not see how the testcases can work with aliasing rules in the case Q's and T's memory is known to not alias. It works because of the well-defined memory model (with regarding to TBAA) in the middle-end. Every store changes the dynamic type of a memory location which means that you can only use TBAA for true-dependence checks (not anti-dependence or write-dependence checks). I see, I did not notice this change - it seems like quite a big hammer though, limiting scheduling (and loop opts) quite noticeably for all languages. Are there any other motivations for this besides placement new? Aggregate copies and memcpy transferring the dynamic type for example. Being able to tbaa union accesses for another. And yes, placement new. It's not so much an optimization preventing thing as you still can move loads up and stores down with the help of tbaa. That has been the way we operate since GCC 4.3 (if I remember correctly). That's also the reason we don't have to special-case unions in any tricky way (yeah, we still do - because of that type-punning special case and RTL alias analysis not dealing with it). Either we need to define what is and is not supported or go for speculative devirt more often. The GCC middle-end (which also has to deal with cross-language cases!) has this specified very clearly. Yep, the cross language support is bit more limited when you speak of polymorphic types. But indeed with the aliasing hack above I can imagine one can destroy one object and build new one on a given location. I will push things towards speculative types to allow implementing super-safe devirt and we could have flag strenghtening assumptions declaring that placement new is not used to change polymorphic type to other polymorphic type and we can see hw important it is in practice. Yeah. Thanks, Richard. Honza Richard. Honza
Re: Strenghten assumption about dynamic type changes (placement new)
On July 23, 2014 4:42:22 PM CEST, Jan Hubicka hubi...@ucw.cz wrote: On Tue, Jul 22, 2014 at 5:17 PM, Jan Hubicka hubi...@ucw.cz wrote: I don't see why long x[1024]; Q *q = new (x) Q; q-~Q (); new (x) T; would be invalid. I also don't see why Q q; q.~Q (); new (q) T; would be. Object lifetime is precisely specified and I don't see where it is tied to (static) storage lifetime. This is precisely the testcase I posted on beggining of this thread. I do not see how the testcases can work with aliasing rules in the case Q's and T's memory is known to not alias. It works because of the well-defined memory model (with regarding to TBAA) in the middle-end. Every store changes the dynamic type of a memory location which means that you can only use TBAA for true-dependence checks (not anti-dependence or write-dependence checks). I see, I did not notice this change - it seems like quite a big hammer though, limiting scheduling (and loop opts) quite noticeably for all languages. Are there any other motivations for this besides placement new? Aggregate copies and memcpy transferring the dynamic type for example. Being able to tbaa union accesses for another. And yes, placement new. It's not so much an optimization preventing thing as you still can move loads up and stores down with the help of tbaa. well, but you lose extra parallelism like *shortptr = exp longer dependency chain with shortptr var = *shortptr *intptr = exp longer dependency chain with intptr var = *intptr Honza
Re: Strenghten assumption about dynamic type changes (placement new)
On Sat, Jul 19, 2014 at 5:44 PM, Jan Hubicka hubi...@ucw.cz wrote: On 07/18/2014 11:03 AM, Jan Hubicka wrote: I really only care about types containing virtual table pointers to not change, so non-PODs are out of game. Current propagation is built around assumption that once polymorphic type is constructed on a given location it won't change to completely different type, only possibly repetitively construct destruct. This is based on our earlier conversation where the outcome was that changing non-POD variable by placement new to different type is not defined. For a variable, yes. If I have a char array buffer (possibly wrapped in a class, e.g. std::aligned_storage), it is OK to construct one non-POD object, destroy it, then construct one of a different type in the same space, just like if we have two automatic variables in different blocks that happen to occupy the same location on the stack. Again, this really needs to be specified better in the standard. To support this safely I really think we will need to mark placement new in the gimple code via builtin for a short while. As discussed today. I may make a difference in between objects allocated in char buffers and objects allocated via normal new and propagate only across the second ones, but that seems a bit slipperly, too. Anything weaker will probably need some cooperation from the frontend - I suppose best tie we have is the fact that you can't use 'a' to call foo after changing object. If placement news was marked for some time by a builtin, we could effectively thread the re-allocated objects as a new memory locations. My concern about treating them as different memory locations is danger of code reordering causing the lifetimes of the old and new objects to overlap. I still do not see how this can work with aliasing rules - if the two objects allocated do not overlap, we will freely overlap the old and new objects. But adding extra builtin that will (for some time) keep the two pointer distinct should not make it any worse. As discussen during the Cauldron keeping some builtin doesn't help because you are not forced to access the newly created object via the pointer returned by the placement new. That is, template T struct Storage { char x[sizeof(T)]; Storage() { new (x) T; } T get() { return reinterpret_cast T (x); } }; is valid (and used in this way in Boost - with a type different from 'char' to force bigger alignment). Richard. Honza Where I find current wording of DR1116? http://open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1116 Jason
Re: Strenghten assumption about dynamic type changes (placement new)
As discussen during the Cauldron keeping some builtin doesn't help because you are not forced to access the newly created object via the pointer returned by the placement new. That is, template T struct Storage { char x[sizeof(T)]; Storage() { new (x) T; } T get() { return reinterpret_cast T (x); } }; This indeed looks like sensible use of placement new... is valid (and used in this way in Boost - with a type different from 'char' to force bigger alignment). This testcase with char replaced to long or other POD type is still fine for my analysis. I would like to assume that once a polymorphic type is built at a given location, it can not be changed to other, that is: template T struct Storage { Q x; Storage() { new (x) T; } T get() { return reinterpret_cast T (x); } }; Where both T and Q are polymorphic types. I think essentially aliasing rules disallows this (for Q and T being different types at least, not sure if one inherits other) because Q gets constructed and thus accessed. But it is sliperly indeed, as whole concept of placement new. I believe easiest way to go forward is to extend polymorphic_call_context to also hold speculative information about outer type. In the cases I can detect a dynamic type but can not prove it did not changed, I still can use the speculative path. This is not perfect, but will improve code quality. I am still hoping we can get sensible rules for placement new :) Honza
Re: Strenghten assumption about dynamic type changes (placement new)
On Tue, Jul 22, 2014 at 3:54 PM, Jan Hubicka hubi...@ucw.cz wrote: As discussen during the Cauldron keeping some builtin doesn't help because you are not forced to access the newly created object via the pointer returned by the placement new. That is, template T struct Storage { char x[sizeof(T)]; Storage() { new (x) T; } T get() { return reinterpret_cast T (x); } }; This indeed looks like sensible use of placement new... is valid (and used in this way in Boost - with a type different from 'char' to force bigger alignment). This testcase with char replaced to long or other POD type is still fine for my analysis. I would like to assume that once a polymorphic type is built at a given location, it can not be changed to other, that is: template T struct Storage { Q x; Storage() { new (x) T; } T get() { return reinterpret_cast T (x); } }; Where both T and Q are polymorphic types. I think essentially aliasing rules disallows this (for Q and T being different types at least, not sure if one inherits other) because Q gets constructed and thus accessed. But it is sliperly indeed, as whole concept of placement new. I believe easiest way to go forward is to extend polymorphic_call_context to also hold speculative information about outer type. In the cases I can detect a dynamic type but can not prove it did not changed, I still can use the speculative path. This is not perfect, but will improve code quality. I am still hoping we can get sensible rules for placement new :) I don't see why long x[1024]; Q *q = new (x) Q; q-~Q (); new (x) T; would be invalid. I also don't see why Q q; q.~Q (); new (q) T; would be. Object lifetime is precisely specified and I don't see where it is tied to (static) storage lifetime. Richard. Honza
Re: Strenghten assumption about dynamic type changes (placement new)
I don't see why long x[1024]; Q *q = new (x) Q; q-~Q (); new (x) T; would be invalid. I also don't see why Q q; q.~Q (); new (q) T; would be. Object lifetime is precisely specified and I don't see where it is tied to (static) storage lifetime. This is precisely the testcase I posted on beggining of this thread. I do not see how the testcases can work with aliasing rules in the case Q's and T's memory is known to not alias. Either we need to define what is and is not supported or go for speculative devirt more often. Honza
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/18/2014 11:03 AM, Jan Hubicka wrote: I really only care about types containing virtual table pointers to not change, so non-PODs are out of game. Current propagation is built around assumption that once polymorphic type is constructed on a given location it won't change to completely different type, only possibly repetitively construct destruct. This is based on our earlier conversation where the outcome was that changing non-POD variable by placement new to different type is not defined. For a variable, yes. If I have a char array buffer (possibly wrapped in a class, e.g. std::aligned_storage), it is OK to construct one non-POD object, destroy it, then construct one of a different type in the same space, just like if we have two automatic variables in different blocks that happen to occupy the same location on the stack. Again, this really needs to be specified better in the standard. Anything weaker will probably need some cooperation from the frontend - I suppose best tie we have is the fact that you can't use 'a' to call foo after changing object. If placement news was marked for some time by a builtin, we could effectively thread the re-allocated objects as a new memory locations. My concern about treating them as different memory locations is danger of code reordering causing the lifetimes of the old and new objects to overlap. Where I find current wording of DR1116? http://open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1116 Jason
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/18/2014 11:03 AM, Jan Hubicka wrote: I really only care about types containing virtual table pointers to not change, so non-PODs are out of game. Current propagation is built around assumption that once polymorphic type is constructed on a given location it won't change to completely different type, only possibly repetitively construct destruct. This is based on our earlier conversation where the outcome was that changing non-POD variable by placement new to different type is not defined. For a variable, yes. If I have a char array buffer (possibly wrapped in a class, e.g. std::aligned_storage), it is OK to construct one non-POD object, destroy it, then construct one of a different type in the same space, just like if we have two automatic variables in different blocks that happen to occupy the same location on the stack. Again, this really needs to be specified better in the standard. To support this safely I really think we will need to mark placement new in the gimple code via builtin for a short while. As discussed today. I may make a difference in between objects allocated in char buffers and objects allocated via normal new and propagate only across the second ones, but that seems a bit slipperly, too. Anything weaker will probably need some cooperation from the frontend - I suppose best tie we have is the fact that you can't use 'a' to call foo after changing object. If placement news was marked for some time by a builtin, we could effectively thread the re-allocated objects as a new memory locations. My concern about treating them as different memory locations is danger of code reordering causing the lifetimes of the old and new objects to overlap. I still do not see how this can work with aliasing rules - if the two objects allocated do not overlap, we will freely overlap the old and new objects. But adding extra builtin that will (for some time) keep the two pointer distinct should not make it any worse. Honza Where I find current wording of DR1116? http://open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1116 Jason
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/08/2014 02:50 PM, Jan Hubicka wrote: I am looking into tracking dynamic types now. Obviously I need to set very exact rules about when these may change. Let me first say that this area is somewhat in flux in the standard; if we have a model of what we want the rules to be for GCC, there's a good chance of getting them into the standard. There are several unresolved DRs in this area already (1027, 1116, 1776). I think b variants are invalid Yes, by 3.8/7; we can't use 'a' to call foo after we've changed the object there to a C. currently we also assume t1 to be invalid, but t2 to be valid. I think the compiler ought to be able to treat both as undefined, because 'a' is either defined (t1) or allocated (t2) as a B, and B does not contain an array of char, so changing the dynamic type of that memory before the end of its storage duration ought to be undefined. But the standard doesn't currently say that, though it's along the lines of my proposed drafting for 1116 (which needs reworking). And I suppose that my notion of 'allocated type' can really only apply when using the library allocation functions in 18.6.1.1 and 18.6.1.2, not the inline placement new. Thanks! I guess we will have chance to chat about this on the Cauldron? As you probably know, for middle-end analysis it would be good if types was as sticky as possible. The sucess of type based devirtualization is largely based on the fact that it is hard to track a value of memory location by alias analysis (as calls to external functions are generally believed to change it) but it is easier to track type of a memory location, because the ways it can change are limited to construcition/destruction and placement news. I really only care about types containing virtual table pointers to not change, so non-PODs are out of game. Current propagation is built around assumption that once polymorphic type is constructed on a given location it won't change to completely different type, only possibly repatively construct destruct. This is based on our arlier conversation where the outcome was that chaning non-POD variable by placement new to different type is not defined. Anything weakter will probably need some cooperation from the frontend - I suppose best tie we have is the fact that you can't use 'a' to call foo after changing object. If placement news was marked for some time by a builtin, we could effectively thread the re-allocated objects as a new memory locations.. So perhaps we can go with my dynamic type patch enforcing the strong interpretation (no changes beyond construction/destruction once polymorphic type lands on a given location) and document it (do we have convenient place in the user documentation). If it turns out to be impractical, we can always carefuly relax it? Where I find current wording of DR1116? Honza Jason
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/08/2014 02:50 PM, Jan Hubicka wrote: I am looking into tracking dynamic types now. Obviously I need to set very exact rules about when these may change. Let me first say that this area is somewhat in flux in the standard; if we have a model of what we want the rules to be for GCC, there's a good chance of getting them into the standard. There are several unresolved DRs in this area already (1027, 1116, 1776). I think b variants are invalid Yes, by 3.8/7; we can't use 'a' to call foo after we've changed the object there to a C. currently we also assume t1 to be invalid, but t2 to be valid. I think the compiler ought to be able to treat both as undefined, because 'a' is either defined (t1) or allocated (t2) as a B, and B does not contain an array of char, so changing the dynamic type of that memory before the end of its storage duration ought to be undefined. But the standard doesn't currently say that, though it's along the lines of my proposed drafting for 1116 (which needs reworking). And I suppose that my notion of 'allocated type' can really only apply when using the library allocation functions in 18.6.1.1 and 18.6.1.2, not the inline placement new. Jason
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/02/2014 01:18 PM, Jan Hubicka wrote: We propagate types from places we know instances are created across pointers passed to functions. Once non-POD type is created at a given memory location, one can not change its type by placement_new into something else. Hmm. If the memory location is untyped (i.e. from malloc) or a character array, or a union, you can indeed destroy an object of one type and create an object of a different type in that location. Jason, this assumes that one can not destroy the type and re-construct same type at the same spot. That is an invalid assumption; you can destroy one object and construct a new one in the same location. Doing it within a method would be unusual, but I don't think there's a rule against it. Jason, I am looking into tracking dynamic types now. Obviously I need to set very exact rules about when these may change. Can you take a few minutes and tell me what of these sequences are valid? I think b variants are invalid, currently we also assume t1 to be invalid, but t2 to be valid. With placement news, I wonder if we can arrange them to do before return: ptr = __builtin_placement_new (ptr) this builtin would be folded away after IPA wwhen we no longer need to track types same way as builtin_constant. That way I won't get two different dynamic types mixed at one pointer location, since these will look as two pointers until after inlining. But given that C++ makes placement new to be written by hand, perhaps this is not possible? It would be useful to know rules in these testcases. I am attaching WIP patch for detecting dynamic type of heap allocated objects. It basically takes Martin's detect_type_change code from ipa-prop and adds discovery of constructor calls. I however need to know if I need to plan extra safe when propagating these types. #include stdio.h inline void* operator new(__SIZE_TYPE__, void* __p) throw() { return __p;} struct A { virtual void foo() {printf (A\n);} }; struct B: A { virtual void foo() {printf (B\n);} }; struct C: A { virtual void foo() {printf (C\n);} }; struct A * type(struct B *a) { struct C *b; ((struct B *)a)-~B(); b = new (a) C; return b; } struct A * type_back(struct A *a) { struct B *b; ((struct C *)a)-~C(); b = new (a) B; return b; } void t1() { struct B a; struct A *b; a.foo(); b=type(a); b-foo(); b=type_back (b); a.foo(); } void t1b() { struct B a; a.foo(); type(a); ((struct A *)a)-foo(); type_back (a); ((struct A *)a)-foo(); } void t2() { struct B *a = new (B); struct A *b; a-foo(); b=type(a); b-foo(); } void t2b() { struct B *a = new (B); struct A *b; a-foo(); type(a); ((struct A *)a)-foo(); } main() { t1(); t1b(); t2(); t2b(); } Index: gimple-fold.c === --- gimple-fold.c (revision 212546) +++ gimple-fold.c (working copy) @@ -372,7 +372,7 @@ tree val = OBJ_TYPE_REF_EXPR (rhs); if (is_gimple_min_invariant (val)) return val; - else if (flag_devirtualize virtual_method_call_p (val)) + else if (flag_devirtualize virtual_method_call_p (rhs)) { bool final; vec cgraph_node *targets Index: ipa-devirt.c === --- ipa-devirt.c(revision 212546) +++ ipa-devirt.c(working copy) @@ -2092,6 +2113,26 @@ return true; } +/* See if OP is SSA name initialized as a copy or by single assignment. + If so, walk the SSA graph up. */ + +static tree +walk_ssa_copies (tree op) +{ + STRIP_NOPS (op); + while (TREE_CODE (op) == SSA_NAME + !SSA_NAME_IS_DEFAULT_DEF (op) + SSA_NAME_DEF_STMT (op) + gimple_assign_single_p (SSA_NAME_DEF_STMT (op))) +{ + if (gimple_assign_load_p (SSA_NAME_DEF_STMT (op))) + return op; + op = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op)); + STRIP_NOPS (op); +} + return op; +} + /* Given REF call in FNDECL, determine class of the polymorphic call (OTR_TYPE), its token (OTR_TOKEN) and CONTEXT. CALL is optional argument giving the actual statement (usually call) where @@ -2120,16 +2161,9 @@ /* Walk SSA for outer object. */ do { - if (TREE_CODE (base_pointer) == SSA_NAME - !SSA_NAME_IS_DEFAULT_DEF (base_pointer) - SSA_NAME_DEF_STMT (base_pointer) - gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer))) + base_pointer = walk_ssa_copies (base_pointer); + if (TREE_CODE (base_pointer) == ADDR_EXPR) { - base_pointer = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (base_pointer)); - STRIP_NOPS (base_pointer); - } - else if (TREE_CODE (base_pointer) == ADDR_EXPR) - { HOST_WIDE_INT size,
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/02/2014 01:18 PM, Jan Hubicka wrote: We propagate types from places we know instances are created across pointers passed to functions. Once non-POD type is created at a given memory location, one can not change its type by placement_new into something else. Hmm. If the memory location is untyped (i.e. from malloc) or a character array, or a union, you can indeed destroy an object of one type and create an object of a different type in that location. Jason, this assumes that one can not destroy the type and re-construct same type at the same spot. That is an invalid assumption; you can destroy one object and construct a new one in the same location. Doing it within a method would be unusual, but I don't think there's a rule against it. Jason, I am looking into tracking dynamic types now. Obviously I need to set very exact rules about when these may change. Can you take a few minutes and tell me what of these sequences are valid? I think b variants are invalid, currently we also assume t1 to be invalid, but t2 to be valid. With placement news, I wonder if we can arrange them to do before return: ptr = __builtin_placement_new (ptr) this builtin would be folded away after IPA wwhen we no longer need to track types same way as builtin_constant. That way I won't get two different dynamic types mixed at one pointer location, since these will look as two pointers until after inlining. But given that C++ makes placement new to be written by hand, perhaps this is not possible? #include stdio.h inline void* operator new(__SIZE_TYPE__, void* __p) throw() { return __p;} struct A { virtual void foo() {printf (A\n);} }; struct B: A { virtual void foo() {printf (B\n);} }; struct C: A { virtual void foo() {printf (C\n);} }; struct A * type(struct B *a) { struct C *b; ((struct B *)a)-~B(); b = new (a) C; return b; } struct A * type_back(struct A *a) { struct B *b; ((struct C *)a)-~C(); b = new (a) B; return b; } void t1() { struct B a; struct A *b; a.foo(); b=type(a); b-foo(); b=type_back (b); a.foo(); } void t1b() { struct B a; a.foo(); type(a); ((struct A *)a)-foo(); type_back (a); ((struct A *)a)-foo(); } void t2() { struct B *a = new (B); struct A *b; a-foo(); b=type(a); b-foo(); } void t2b() { struct B *a = new (B); struct A *b; a-foo(); type(a); ((struct A *)a)-foo(); } main() { t1(); t1b(); t2(); t2b(); }
Re: Strenghten assumption about dynamic type changes (placement new)
On Tue, Jul 8, 2014 at 2:50 PM, Jan Hubicka hubi...@ucw.cz wrote: On 07/02/2014 01:18 PM, Jan Hubicka wrote: We propagate types from places we know instances are created across pointers passed to functions. Once non-POD type is created at a given memory location, one can not change its type by placement_new into something else. Hmm. If the memory location is untyped (i.e. from malloc) or a character array, or a union, you can indeed destroy an object of one type and create an object of a different type in that location. Jason, this assumes that one can not destroy the type and re-construct same type at the same spot. That is an invalid assumption; you can destroy one object and construct a new one in the same location. Doing it within a method would be unusual, but I don't think there's a rule against it. Jason, I am looking into tracking dynamic types now. Obviously I need to set very exact rules about when these may change. Can you take a few minutes and tell me what of these sequences are valid? I think b variants are invalid, currently we also assume t1 to be invalid, but t2 to be valid. With placement news, I wonder if we can arrange them to do before return: ptr = __builtin_placement_new (ptr) this builtin would be folded away after IPA wwhen we no longer need to track types same way as builtin_constant. That way I won't get two different dynamic types mixed at one pointer location, since these will look as two pointers until after inlining. But given that C++ makes placement new to be written by hand, perhaps this is not possible? #include stdio.h inline void* operator new(__SIZE_TYPE__, void* __p) throw() { return __p;} struct A { virtual void foo() {printf (A\n);} }; struct B: A { virtual void foo() {printf (B\n);} }; struct C: A { virtual void foo() {printf (C\n);} }; struct A * type(struct B *a) { struct C *b; ((struct B *)a)-~B(); b = new (a) C; return b; } struct A * type_back(struct A *a) { struct B *b; ((struct C *)a)-~C(); b = new (a) B; return b; } void t1() { struct B a; struct A *b; a.foo(); b=type(a); b-foo(); b=type_back (b); a.foo(); } void t1b() { struct B a; a.foo(); type(a); ((struct A *)a)-foo(); type_back (a); ((struct A *)a)-foo(); } void t2() { struct B *a = new (B); struct A *b; a-foo(); b=type(a); b-foo(); } void t2b() { struct B *a = new (B); struct A *b; a-foo(); type(a); ((struct A *)a)-foo(); } main() { t1(); t1b(); t2(); t2b(); } Hi, Below test also fails on arm-none-linux-gnueabi(hf): NA-FAIL: g++.dg/ipa/imm-devirt-2.C -std=gnu++11 scan-tree-dump einline C NA-FAIL: g++.dg/ipa/imm-devirt-2.C -std=gnu++1y scan-tree-dump einline C NA-FAIL: g++.dg/ipa/imm-devirt-2.C -std=gnu++98 scan-tree-dump einline C Reported at https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61748 Thanks, bin
Re: Strenghten assumption about dynamic type changes (placement new)
On Thu, Jul 3, 2014 at 4:20 AM, Jason Merrill ja...@redhat.com wrote: On 07/02/2014 06:30 PM, Jan Hubicka wrote: But this is one of things that was not quite clear to me. I know that polymorphic type A was created at a give memory location. THis means that accesses to that location in one alias class has been made. Now I destroy A and turn it into B, construct B and make memory accesses in different alias set. I see this has chance to work if one is base of another, but if B is completely different type, I think strick aliasin should just make those accesses to not alias and in turn make whole thing undefined? Right, if they're unrelated types the accesses don't alias (3.10p10). On the subject of aliasing, there's a proposal to add explicit alias sets to C++: http://open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf Any thoughts? Well, but deleting the object at *p and constructing a new one with different alias set there doesn't make it valid for GCC to move loads/stores across that destruction/construction point, no? With placement new / delete they will basically be a no-op and be invisible in the IL - so what avoids GCC, for example from insn scheduling, to mess things up here? (the GCC middle-end memory model does - but as far as I understand Honza want's to play tricks to get around that, no?) Richard. Jason
Re: Strenghten assumption about dynamic type changes (placement new)
Jan Hubicka hubi...@ucw.cz writes: * cgraph.c (cgraph_create_indirect_edge): Update call of get_polymorphic_call_info. * ipa-utils.h (get_polymorphic_call_info): Add parameter CALL. (possible_polymorphic_call_targets): Add parameter call. (decl_maybe_in_construction_p): New predicate. (get_polymorphic_call_info): Add parameter call; use decl_maybe_in_construction_p. * gimple-fold.c (fold_gimple_assign): Update use of possible_polymorphic_call_targets. (gimple_fold_call): Likewise. * ipa-prop.c: Inlcude calls.h (ipa_binfo_from_known_type_jfunc): Check that known type is record. (param_type_may_change_p): New predicate. (detect_type_change_from_memory_writes): Break out from ... (detect_type_change): ... this one; use param_type_may_change_p. (detect_type_change_ssa): Use param_type_may_change_p. (compute_known_type_jump_func): Use decl_maybe_in_construction_p. This breaks g++.dg/ipa/pr61085.C on ia64. (gdb) bt #0 0xa0040721 in __kernel_syscall_via_break () #1 0x204331d0 in *__GI_raise (sig=optimized out) at ../nptl/sysdeps/unix/sysv/linux/raise.c:67 #2 0x20435ab0 in *__GI_abort () at abort.c:92 #3 0x49e0 in C::m_virt (this=0x4760 main()+96) at /usr/local/gcc/gcc-20140707/gcc/testsuite/g++.dg/ipa/pr61085.C:26 #4 0x4760 in m_foo (this=0x600eee40) at /usr/local/gcc/gcc-20140707/gcc/testsuite/g++.dg/ipa/pr61085.C:20 #5 ~B (__vtt_parm=optimized out, this=0x600eee40, __in_chrg=optimized out) at /usr/local/gcc/gcc-20140707/gcc/testsuite/g++.dg/ipa/pr61085.C:14 #6 ~C (this=0x600eee40, __in_chrg=optimized out, __vtt_parm=optimized out) at /usr/local/gcc/gcc-20140707/gcc/testsuite/g++.dg/ipa/pr61085.C:24 #7 main () at /usr/local/gcc/gcc-20140707/gcc/testsuite/g++.dg/ipa/pr61085.C:32 Andreas. -- Andreas Schwab, SUSE Labs, sch...@suse.de GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE 1748 E4D4 88E3 0EEA B9D7 And now for something completely different.
Re: Strenghten assumption about dynamic type changes (placement new)
Jan Hubicka hubi...@ucw.cz writes: Index: testsuite/g++.dg/ipa/imm-devirt-2.C === --- testsuite/g++.dg/ipa/imm-devirt-2.C (revision 212278) +++ testsuite/g++.dg/ipa/imm-devirt-2.C (working copy) @@ -1,7 +1,7 @@ /* Verify that virtual calls are folded even early inlining puts them into one function with the definition. */ /* { dg-do run } */ -/* { dg-options -O2 -fdump-tree-fre1-details } */ +/* { dg-options -O2 -fdump-tree-einline } */ extern C void abort (void); @@ -91,5 +91,6 @@ int main (int argc, char *argv[]) return 0; } -/* { dg-final { scan-tree-dump converting indirect call to function fre1 } } */ -/* { dg-final { cleanup-tree-dump fre1 } } */ +/* We fold into thunk of C. Eventually we should inline the thunk. */ +/* { dg-final { scan-tree-dump C::_ZThn24_N1C3fooEi ( einline } } */ FAIL: g++.dg/ipa/imm-devirt-2.C -std=gnu++11 scan-tree-dump einline C::_ZThn24_N1C3fooEi \\( Andreas. -- Andreas Schwab, SUSE Labs, sch...@suse.de GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE 1748 E4D4 88E3 0EEA B9D7 And now for something completely different.
Re: Strenghten assumption about dynamic type changes (placement new)
On Fri, Jul 04, 2014 at 11:39:52PM +0200, Jan Hubicka wrote: Bootstrapped/regtested x86_64-linux, will commit it after bit more testing. ... * g++.dg/ipa/imm-devirt-1.C: Update testcase. * g++.dg/ipa/imm-devirt-2.C: Update testcase. These testcases fail: ERROR: g++.dg/ipa/imm-devirt-1.C -std=gnu++98: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced ERROR: g++.dg/ipa/imm-devirt-1.C -std=gnu++11: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced ERROR: g++.dg/ipa/imm-devirt-1.C -std=gnu++1y: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced ERROR: g++.dg/ipa/imm-devirt-2.C -std=gnu++98: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced ERROR: g++.dg/ipa/imm-devirt-2.C -std=gnu++11: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced ERROR: g++.dg/ipa/imm-devirt-2.C -std=gnu++1y: error executing dg-final: couldn't compile regular expression pattern: parentheses () not balanced I'm fixing that with the following (will commit as obvious). 2014-07-06 Marek Polacek pola...@redhat.com * g++.dg/ipa/imm-devirt-1.C: Fix regexp in dg-final. * g++.dg/ipa/imm-devirt-2.C: Likewise. diff --git gcc/testsuite/g++.dg/ipa/imm-devirt-1.C gcc/testsuite/g++.dg/ipa/imm-devirt-1.C index 115277f..85f1a8f 100644 --- gcc/testsuite/g++.dg/ipa/imm-devirt-1.C +++ gcc/testsuite/g++.dg/ipa/imm-devirt-1.C @@ -62,6 +62,6 @@ int main (int argc, char *argv[]) a direct call. */ /* { dg-final { scan-tree-dump Inlining int middleman_1 einline } } */ /* { dg-final { scan-tree-dump Inlining int middleman_2 einline } } */ -/* { dg-final { scan-tree-dump B::foo ( einline } } */ +/* { dg-final { scan-tree-dump B::foo \\( einline } } */ /* { dg-final { scan-tree-dump-times OBJ_TYPE_REF 2 einline } } */ /* { dg-final { cleanup-tree-dump einline } } */ diff --git gcc/testsuite/g++.dg/ipa/imm-devirt-2.C gcc/testsuite/g++.dg/ipa/imm-devirt-2.C index 58af089..db85487 100644 --- gcc/testsuite/g++.dg/ipa/imm-devirt-2.C +++ gcc/testsuite/g++.dg/ipa/imm-devirt-2.C @@ -92,5 +92,5 @@ int main (int argc, char *argv[]) } /* We fold into thunk of C. Eventually we should inline the thunk. */ -/* { dg-final { scan-tree-dump C::_ZThn24_N1C3fooEi ( einline } } */ +/* { dg-final { scan-tree-dump C::_ZThn24_N1C3fooEi \\( einline } } */ /* { dg-final { cleanup-tree-dump einline } } */ Marek
Re: Strenghten assumption about dynamic type changes (placement new)
I'm fixing that with the following (will commit as obvious). Marek, With your patch g++.dg/ipa/imm-devirt-2.C sitll fails in 32 bit mode because the mangling is C::_ZThn16_N1C3fooEi. This is fixed by something such as --- ../_clean/gcc/testsuite/g++.dg/ipa/imm-devirt-2.C 2014-07-05 23:22:52.0 +0200 +++ gcc/testsuite/g++.dg/ipa/imm-devirt-2.C 2014-07-06 18:03:59.0 +0200 @@ -92,5 +92,5 @@ int main (int argc, char *argv[]) } /* We fold into thunk of C. Eventually we should inline the thunk. */ -/* { dg-final { scan-tree-dump C::_ZThn24_N1C3fooEi ( einline } } */ +/* { dg-final { scan-tree-dump C::_ZThn\(16|24\)_N1C3fooEi \\( einline } } */ /* { dg-final { cleanup-tree-dump einline } } */ Dominique
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/02/2014 01:18 PM, Jan Hubicka wrote: We propagate types from places we know instances are created across pointers passed to functions. Once non-POD type is created at a given memory location, one can not change its type by placement_new into something else. Hmm. If the memory location is untyped (i.e. from malloc) or a character array, or a union, you can indeed destroy an object of one type and create an object of a different type in that location. Jason, this assumes that one can not destroy the type and re-construct same type at the same spot. That is an invalid assumption; you can destroy one object and construct a new one in the same location. Doing it within a method would be unusual, but I don't think there's a rule against it. Hi, this is updated patch that does the legwork needed to prove we are not re-constructing an object in the same location as we created previous one. Currenlty we track only objects places in declarations, but I would really like to understand how precisely the rules of the game differs when the object lives in dynamically allocated memory - i.e. I work out the dynamic type by spotting either virtual table store or constructor call. Bootstrapped/regtested x86_64-linux, will commit it after bit more testing. * cgraph.c (cgraph_create_indirect_edge): Update call of get_polymorphic_call_info. * ipa-utils.h (get_polymorphic_call_info): Add parameter CALL. (possible_polymorphic_call_targets): Add parameter call. (decl_maybe_in_construction_p): New predicate. (get_polymorphic_call_info): Add parameter call; use decl_maybe_in_construction_p. * gimple-fold.c (fold_gimple_assign): Update use of possible_polymorphic_call_targets. (gimple_fold_call): Likewise. * ipa-prop.c: Inlcude calls.h (ipa_binfo_from_known_type_jfunc): Check that known type is record. (param_type_may_change_p): New predicate. (detect_type_change_from_memory_writes): Break out from ... (detect_type_change): ... this one; use param_type_may_change_p. (detect_type_change_ssa): Use param_type_may_change_p. (compute_known_type_jump_func): Use decl_maybe_in_construction_p. * g++.dg/ipa/devirt-26.C: Update testcase. * g++.dg/ipa/imm-devirt-1.C: Update testcase. * g++.dg/ipa/imm-devirt-2.C: Update testcase. Index: cgraph.c === --- cgraph.c(revision 212278) +++ cgraph.c(working copy) @@ -967,7 +967,7 @@ cgraph_create_indirect_edge (struct cgra get_polymorphic_call_info (caller-decl, target, otr_type, otr_token, -context); +context, call_stmt); /* Only record types can have virtual calls. */ gcc_assert (TREE_CODE (otr_type) == RECORD_TYPE); Index: testsuite/g++.dg/ipa/devirt-26.C === --- testsuite/g++.dg/ipa/devirt-26.C(revision 212278) +++ testsuite/g++.dg/ipa/devirt-26.C(working copy) @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options -O3 -fdump-ipa-devirt-details } */ +/* { dg-options -O3 -fdump-tree-ccp1 } */ struct A { int a; @@ -23,7 +23,6 @@ int test(void) return d-foo()+b-foo(); } /* The call to b-foo() is perfectly devirtualizable because C can not be in construction - when c was used, but we can not analyze that so far. Test that we at least speculate - that type is in the construction. */ -/* { dg-final { scan-ipa-dump speculatively devirtualizing devirt } } */ -/* { dg-final { cleanup-ipa-dump devirt } } */ + when c was used. */ +/* { dg-final { scan-tree-dump-not OBJ_TYPE_REF ccp1 } } */ +/* { dg-final { cleanup-tree-dump ccp1 } } */ Index: testsuite/g++.dg/ipa/imm-devirt-1.C === --- testsuite/g++.dg/ipa/imm-devirt-1.C (revision 212278) +++ testsuite/g++.dg/ipa/imm-devirt-1.C (working copy) @@ -1,7 +1,7 @@ /* Verify that virtual calls are folded even early inlining puts them into one function with the definition. */ /* { dg-do run } */ -/* { dg-options -O2 -fdump-tree-fre1-details } */ +/* { dg-options -O2 -fdump-tree-einline } */ extern C void abort (void); @@ -58,5 +58,10 @@ int main (int argc, char *argv[]) return 0; } -/* { dg-final { scan-tree-dump converting indirect call to function virtual int B::foo fre1 } } */ -/* { dg-final { cleanup-tree-dump fre1 } } */ +/* middleman_2 gets early inlined and the virtual call should get turned to + a direct call. */ +/* { dg-final { scan-tree-dump Inlining int middleman_1 einline } } */ +/* { dg-final { scan-tree-dump Inlining int middleman_2 einline } } */ +/* { dg-final { scan-tree-dump B::foo ( einline } } */ +/* { dg-final { scan-tree-dump-times
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/02/2014 06:30 PM, Jan Hubicka wrote: But this is one of things that was not quite clear to me. I know that polymorphic type A was created at a give memory location. THis means that accesses to that location in one alias class has been made. Now I destroy A and turn it into B, construct B and make memory accesses in different alias set. I see this has chance to work if one is base of another, but if B is completely different type, I think strick aliasin should just make those accesses to not alias and in turn make whole thing undefined? Right, if they're unrelated types the accesses don't alias (3.10p10). On the subject of aliasing, there's a proposal to add explicit alias sets to C++: http://open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf Any thoughts? Thanks! I will take a look. I would like to decide what to do with this approach. I can see 1) I can start explicitly tracking if type came from a declaration or was detected dynamically (by seeing a vtable write or constructor call). Currently we don't do the second, but I would like to understand if these make difference 2) The code in question first detect that a type in a given variable is fully constructed and then starts tracking it across function calls. If needed I can check if my unwind stack contains some additional constructors/destructors that may possibly be currently destructing the type if it is valid to call destructor and construct same type there again. If one can there destruct the type and build completely different type, we need updates elsewhere in devirt machinery, too. Thanks! Honza Jason
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/02/2014 01:18 PM, Jan Hubicka wrote: We propagate types from places we know instances are created across pointers passed to functions. Once non-POD type is created at a given memory location, one can not change its type by placement_new into something else. Hmm. If the memory location is untyped (i.e. from malloc) or a character array, or a union, you can indeed destroy an object of one type and create an object of a different type in that location. Jason, this assumes that one can not destroy the type and re-construct same type at the same spot. That is an invalid assumption; you can destroy one object and construct a new one in the same location. Doing it within a method would be unusual, but I don't think there's a rule against it. Jason
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/02/2014 01:18 PM, Jan Hubicka wrote: We propagate types from places we know instances are created across pointers passed to functions. Once non-POD type is created at a given memory location, one can not change its type by placement_new into something else. Hmm. If the memory location is untyped (i.e. from malloc) or a character array, or a union, you can indeed destroy an object of one type and create an object of a different type in that location. Jason, this assumes that one can not destroy the type and re-construct same type at the same spot. That is an invalid assumption; you can destroy one object and construct a new one in the same location. Doing it within a method would be unusual, but I don't think there's a rule against it. The types get currently are one comming from declarations of variables and parameters passed by reference. Can I really destroy it/allocate new type/destroy new type/allocate back the original type (or terminate the program) so the destruction at the end of the lifetimate of the variable apsses? I suppose we should keep track if memory location is comming from declaration or it is dynamically typed (i.e. type seen from calling constructor)? Currently we don't deal with dynamic types, but I have patches for that. Honza Jason
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/02/2014 01:18 PM, Jan Hubicka wrote: We propagate types from places we know instances are created across pointers passed to functions. Once non-POD type is created at a given memory location, one can not change its type by placement_new into something else. Hmm. If the memory location is untyped (i.e. from malloc) or a character array, or a union, you can indeed destroy an object of one type and create an object of a different type in that location. Jason, this assumes that one can not destroy the type and re-construct same type at the same spot. That is an invalid assumption; you can destroy one object and construct a new one in the same location. Doing it within a method would be unusual, but I don't think there's a rule against it. The types get currently are one comming from declarations of variables and parameters passed by reference. Can I really destroy it/allocate new type/destroy new type/allocate back the original type (or terminate the program) so the destruction at the end of the lifetimate of the variable apsses? I suppose we should keep track if memory location is comming from declaration or it is dynamically typed (i.e. type seen from calling constructor)? Currently we don't deal with dynamic types, but I have patches for that. But this is one of things that was not quite clear to me. I know that polymorphic type A was created at a give memory location. THis means that accesses to that location in one alias class has been made. Now I destroy A and turn it into B, construct B and make memory accesses in different alias set. I see this has chance to work if one is base of another, but if B is completely different type, I think strick aliasin should just make those accesses to not alias and in turn make whole thing undefined? honza
Re: Strenghten assumption about dynamic type changes (placement new)
On 07/02/2014 06:30 PM, Jan Hubicka wrote: But this is one of things that was not quite clear to me. I know that polymorphic type A was created at a give memory location. THis means that accesses to that location in one alias class has been made. Now I destroy A and turn it into B, construct B and make memory accesses in different alias set. I see this has chance to work if one is base of another, but if B is completely different type, I think strick aliasin should just make those accesses to not alias and in turn make whole thing undefined? Right, if they're unrelated types the accesses don't alias (3.10p10). On the subject of aliasing, there's a proposal to add explicit alias sets to C++: http://open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3988.pdf Any thoughts? Jason