On Sun, Nov 14, 2010 at 11:45 AM, Reid Kleckner <reid.kleckner at gmail.com> wrote:> On Sun, Nov 14, 2010 at 11:17 AM, Kenneth Uildriks <kennethuil at gmail.com> wrote: >> To fix that and compile C++ correctly while aggressively >> devirtualizing it, we would need to apply "noalias" to the result of >> placement-new in all cases, even when placement-new is inlined. More >> generally, when inlining any function with a "noalias" return, the >> inlined result needs to have "noalias" applied to it. > > Is that the right way to go? It seems like that might cause other > optimizers to introduce invalid transformations. For example, if the > instruction scheduler knows that those pointers don't alias, it might > reschedule a store to the memory after the constructor call from the > placement new. > > struct Foo { > int a; > Foo(int a) : a(a) {} > }; > > int main(void) { > Foo f; > f.a = 1; > Foo *p = new (&f) Foo(2); > // what does p->a contain? 1 or 2? > } > > There's a lot of problems with this example, but I don't know enough > optimizer details to construct a better one. > > Can you get by with a MayAlias? It seems like you can divirtualize > everything that MustAlias and ignore the rest.I see what you mean. If the placement new result mayalias its original pointer, we can hold both vptrs invariant and have everything else reloaded from memory as appropriate. Now if the placement-new is known to place an object of a different type from the original object, the front-end can NoAlias them instead because pointers to the old object become invalid according to the standard and any use of them while the new object is in that memory slot is allowed to cause undefined behavior. So I guess we need to be able to force either MayAlias or NoAlias as appropriate. The trouble comes if placement-new overlays an object of a different type, we allow the result of placement-new to MustAlias the input to placement-new (which they most certainly will if placement-new is inlined), and we try to hold the vptrs invariant. In that case, the optimizer might assume that the new vptr is equal to the original vptr, which is *not* a valid assumption to make.> > If I understood the last discussion on this, the reason you don't need > to worry about placement new getting called within callees is that you > have to use the pointer returned by placement new, or you get > undefined behavior, so you can safely assume the vptr is immutable. > > Reid >You're allowed to safely assume the vptr is immutable every time you reuse a given pointer to the object. The trouble comes when AA can prove that two different pointers to two different objects actually point to the same address - the standard allows both pointers to coexist and both objects to exist in that memory at different times, as long as a pointer to one object is never used when the memory contains the other object - and AA can't (currently) prove any such thing with respect to a pointer returned from a callee.
On Sun, Nov 14, 2010 at 2:37 PM, Kenneth Uildriks <kennethuil at gmail.com> wrote:> On Sun, Nov 14, 2010 at 11:45 AM, Reid Kleckner <reid.kleckner at gmail.com> wrote: >> On Sun, Nov 14, 2010 at 11:17 AM, Kenneth Uildriks <kennethuil at gmail.com> wrote: >>> To fix that and compile C++ correctly while aggressively >>> devirtualizing it, we would need to apply "noalias" to the result of >>> placement-new in all cases, even when placement-new is inlined. More >>> generally, when inlining any function with a "noalias" return, the >>> inlined result needs to have "noalias" applied to it. >> >> Is that the right way to go? It seems like that might cause other >> optimizers to introduce invalid transformations. For example, if the >> instruction scheduler knows that those pointers don't alias, it might >> reschedule a store to the memory after the constructor call from the >> placement new. >> >> struct Foo { >> int a; >> Foo(int a) : a(a) {} >> }; >> >> int main(void) { >> Foo f; >> f.a = 1; >> Foo *p = new (&f) Foo(2); >> // what does p->a contain? 1 or 2? >> } >> >> There's a lot of problems with this example, but I don't know enough >> optimizer details to construct a better one. >> >> Can you get by with a MayAlias? It seems like you can divirtualize >> everything that MustAlias and ignore the rest. > > I see what you mean. If the placement new result mayalias its > original pointer, we can hold both vptrs invariant and have everything > else reloaded from memory as appropriate. Now if the placement-new is > known to place an object of a different type from the original object, > the front-end can NoAlias them instead because pointers to the old > object become invalid according to the standard and any use of them > while the new object is in that memory slot is allowed to cause > undefined behavior. So I guess we need to be able to force either > MayAlias or NoAlias as appropriate.I don't think that was quite my meaning. I'm saying that NoAlias isn't what you want, because it allows other optimizations to make invalid transformations. In this example, with your suggestion after inlining, my example might look like: int main(void) { Foo f; f.a = 1; Foo *p = noalias(&f); // magic aliasing intrinsic p->a = 2; } Now, because &f must not alias p, it would be valid to perform this transformation: int main(void) { Foo f; Foo *p = noalias(&f); // magic aliasing intrinsic p->a = 2; f.a = 1; } If you use MayAlias, this transformation is not legal. Like I said, it's a bad example, because it's not clear why that transformation could be profitable, but the point is that stores may be reordered unsafely. Using MayAlias forces other optimizations to be conservative. Devirtualization should still be able to work, because you it will only fire if it sees a MustAlias. Reid
On Sun, Nov 14, 2010 at 1:52 PM, Reid Kleckner <reid.kleckner at gmail.com> wrote:> On Sun, Nov 14, 2010 at 2:37 PM, Kenneth Uildriks <kennethuil at gmail.com> wrote: >> On Sun, Nov 14, 2010 at 11:45 AM, Reid Kleckner <reid.kleckner at gmail.com> wrote: >>> On Sun, Nov 14, 2010 at 11:17 AM, Kenneth Uildriks <kennethuil at gmail.com> wrote: >>>> To fix that and compile C++ correctly while aggressively >>>> devirtualizing it, we would need to apply "noalias" to the result of >>>> placement-new in all cases, even when placement-new is inlined. More >>>> generally, when inlining any function with a "noalias" return, the >>>> inlined result needs to have "noalias" applied to it. >>> >>> Is that the right way to go? It seems like that might cause other >>> optimizers to introduce invalid transformations. For example, if the >>> instruction scheduler knows that those pointers don't alias, it might >>> reschedule a store to the memory after the constructor call from the >>> placement new. >>> >>> struct Foo { >>> int a; >>> Foo(int a) : a(a) {} >>> }; >>> >>> int main(void) { >>> Foo f; >>> f.a = 1; >>> Foo *p = new (&f) Foo(2); >>> // what does p->a contain? 1 or 2? >>> } >>> >>> There's a lot of problems with this example, but I don't know enough >>> optimizer details to construct a better one. >>> >>> Can you get by with a MayAlias? It seems like you can divirtualize >>> everything that MustAlias and ignore the rest. >> >> I see what you mean. If the placement new result mayalias its >> original pointer, we can hold both vptrs invariant and have everything >> else reloaded from memory as appropriate. Now if the placement-new is >> known to place an object of a different type from the original object, >> the front-end can NoAlias them instead because pointers to the old >> object become invalid according to the standard and any use of them >> while the new object is in that memory slot is allowed to cause >> undefined behavior. So I guess we need to be able to force either >> MayAlias or NoAlias as appropriate. > > I don't think that was quite my meaning. I'm saying that NoAlias > isn't what you want, because it allows other optimizations to make > invalid transformations. In this example, with your suggestion after > inlining, my example might look like: > > int main(void) { > Foo f; > f.a = 1; > Foo *p = noalias(&f); // magic aliasing intrinsic > p->a = 2; > } > > Now, because &f must not alias p, it would be valid to perform this > transformation: > > int main(void) { > Foo f; > Foo *p = noalias(&f); // magic aliasing intrinsic > p->a = 2; > f.a = 1; > } > > If you use MayAlias, this transformation is not legal. Like I said, > it's a bad example, because it's not clear why that transformation > could be profitable, but the point is that stores may be reordered > unsafely. Using MayAlias forces other optimizations to be > conservative. Devirtualization should still be able to work, because > you it will only fire if it sees a MustAlias. > > Reid >And I suppose that would also apply to the store of the vptr if the constructor were inlined. Which means that even if we only NoAlias the vptrs themselves, we're still not safe. Good catch. We want the placement-new result to MayAlias the pointer passed into it. Then we can hold both vptr's invariant throughout their lifetimes, and each object pointer can assume its vptr will have the same value each time it's used. The rest of each object will be assumed to MayAlias the other and stores to one won't be reordered with respect to stores to the other.