On Wed, Oct 13, 2010 at 6:49 PM, John McCall <rjmccall at apple.com> wrote:> > On Oct 13, 2010, at 4:35 AM, Kenneth Uildriks wrote: > >> On Wed, Oct 13, 2010 at 12:45 AM, Nick Lewycky <nicholas at mxc.ca> wrote: >>> Kenneth Uildriks wrote: >>>>> >>>>> You're right, I hadn't thought this through. The whole point of making >>>>> them >>>>> local is to say that "I'm sure these callees won't modify that memory" >>>>> regardless of what functions actually get called, even indirectly. We >>>>> can't >>>>> know that they won't modify the vptr in advance, so invariant doesn't >>>>> work >>>>> here. Making it non-local just means that we would need to know the >>>>> static >>>>> call graph, which we don't because we haven't devirtualized yet so all >>>>> the >>>>> calls are indirect. >>>>> Nick >>>> >>>> So that means you're now saying that llvm.invariant.end ought to be >>>> left the way it is, right? >>> >>> I have no idea how to make use of llvm.invariant to help devirtualization. >>> If no use or other use case for them can be found, maybe they should be >>> removed. >> >> Apply invariant to the vtpr as long as the corresponding instance >> pointer is in use within a function. With an invariant vtpr (and >> better invariant support, and a front-end that uses it), >> devirtualization happens more or less automatically with >> -std-compile-opts. > > Even if this works, it still requires us to inline the constructor to do any good. > And as long as llvm.invariant is defined in terms of memory (in C++ standards > parlance, "storage"), it won't work, because the language doesn't actually > guarantee that the memory is invariant. > > John.But I believe the language does allow "undefined behavior" if there's a use of pT when the pointed-to object isn't actually of type T. It's an invalid use in that case, right?
On Oct 13, 2010, at 5:09 PM, Kenneth Uildriks wrote:> But I believe the language does allow "undefined behavior" if there's > a use of pT when the pointed-to object isn't actually of type T. It's > an invalid use in that case, right?Yes, but not for an arbitrary pointer which aliases pT. That's why it's a problem that llm.invariant is specified in terms of memory; if we get a pointer that we can prove aliases the invariant memory, we start making assumptions we aren't allowed to make. This C++ code might be well-formed, depending on what 'foo' does to its argument: A *a = new A(); a->~A(); B *b = new (a) B(); foo(b); a->bar(); AFAICT, your proposed IR will look like this (in pseudocode): %ptr = call i8* @operator new(...) %a = bitcast %ptr to %A* call void @A::A(%a) call void @llvm.invariant.begin(%a) call void @llvm.invariant.end(%a) call void @A::~A(%a) %b = bitcast %a to %B* call void @B::B(%b) call void @llvm.invariant.begin(%b) call void @foo(%b) %b.vtbl = gep %a, 1 %vtbl = load %b.vtbl %fn.ptr = gep %vtbl, <offset> %fn = load %fn.ptr call %fn(%a) ... What's stopping us here from (incorrectly) replacing %vtbl with B's vtable pointer? John.
On Wed, Oct 13, 2010 at 7:26 PM, John McCall <rjmccall at apple.com> wrote:> On Oct 13, 2010, at 5:09 PM, Kenneth Uildriks wrote: >> But I believe the language does allow "undefined behavior" if there's >> a use of pT when the pointed-to object isn't actually of type T. It's >> an invalid use in that case, right? > > Yes, but not for an arbitrary pointer which aliases pT. That's why it's > a problem that llm.invariant is specified in terms of memory; if we get > a pointer that we can prove aliases the invariant memory, we start > making assumptions we aren't allowed to make. > > This C++ code might be well-formed, depending on what 'foo' does to its > argument: > A *a = new A(); > a->~A(); > B *b = new (a) B(); > foo(b); > a->bar();I see the problem now. My proposed rule would extend A's invariance past A->bar, which would mess up any virtual calls through b before foo was called... Any way you cut it, you've gotta have different pointers to the same memory assume different contents depending on which one is being used at any particular point. And since they can alternate.... ugh. Now if alias analysis denied that a and b MustAlias... let's take a few cases: 1. Placement new inside the function: we have to tell AA that a and b don't alias. 2. Placement new inside a callee... we see a pointer returned from the callee, but don't know what its value is. alias analysis says that a MayAlias b, unless the callee's return value is marked noalias, in which case alias analysis says that a NoAlias b. With either of these results, the invariance on a->vtblptr is not applied to any loads of b->vtblptr. It is, however, applied to loads a->vtblptr, which is exactly what we want. And the reverse is true for any invariance applied to b->vtblptr. If the callee is ever inlined, we're back to case 1. So now we need a way to arrange for pointers returned from placement new to not alias pointers passed to placement new. Preferably without declaring placement new "noinline".