On Mon, Oct 11, 2010 at 11:10 PM, John McCall <rjmccall at apple.com> wrote:> On Oct 11, 2010, at 2:01 PM, Kenneth Uildriks wrote: >> A better way for a front-end to declare that vtbl-ptr-hacking is not >> expected and not supported is for it to emit llvm.invariant.start and >> llvm.invariant.end calls for it. > > Some of us were talking about this apropos your earlier post. > @llvm.invariant.start/end aren't appropriate, because the memory *isn't* > invariant; the user is totally allowed to destruct the object in-place and > create a new object there. The only thing the standard tells us is that > old references and pointers are only considered to be automatically > "forwarded" to the new object (i.e. aren't just invalid) if the types match. > So we're allowed to assume that a pointer or reference validly formed > to an object of dynamic type T will always refer to an object of that > dynamic type.So does that mean that we're allowed to assume that, given an "old" pointer to that memory, the vtbl-ptr slot hasn't changed? Which allows us to devirtualize: Base* pT = GetMyObjectThatHappensToBeT(); // ... // stuff that we can't tell what it does to our memory // ... pT->A(); // more mysterious stuff pT->B(); // etc. as long as we can tell that a given pointer is actually pT and not another pointer copied from it or aliased to it?
On Tue, Oct 12, 2010 at 7:00 AM, Kenneth Uildriks <kennethuil at gmail.com> wrote:> On Mon, Oct 11, 2010 at 11:10 PM, John McCall <rjmccall at apple.com> wrote: >> On Oct 11, 2010, at 2:01 PM, Kenneth Uildriks wrote: >>> A better way for a front-end to declare that vtbl-ptr-hacking is not >>> expected and not supported is for it to emit llvm.invariant.start and >>> llvm.invariant.end calls for it. >> >> Some of us were talking about this apropos your earlier post. >> @llvm.invariant.start/end aren't appropriate, because the memory *isn't* >> invariant; the user is totally allowed to destruct the object in-place and >> create a new object there. The only thing the standard tells us is that >> old references and pointers are only considered to be automatically >> "forwarded" to the new object (i.e. aren't just invalid) if the types match. >> So we're allowed to assume that a pointer or reference validly formed >> to an object of dynamic type T will always refer to an object of that >> dynamic type. > > So does that mean that we're allowed to assume that, given an "old" > pointer to that memory, the vtbl-ptr slot hasn't changed? Which > allows us to devirtualize: > > Base* pT = GetMyObjectThatHappensToBeT(); > // ... > // stuff that we can't tell what it does to our memory > // ... > pT->A(); > // more mysterious stuff > pT->B(); > // etc. > > as long as we can tell that a given pointer is actually pT and not > another pointer copied from it or aliased to it? >For that matter, when you can find the *last* use of pT, you should be able to put an llvm.immutable.end marker right after it, right? Or have I forgotten something else in the standard? (entirely possible, it's enormous!) Do you do any processing of an IR Function after you've compiled it in clang?
On Oct 12, 2010, at 5:00 AM, Kenneth Uildriks wrote:> On Mon, Oct 11, 2010 at 11:10 PM, John McCall <rjmccall at apple.com> wrote: >> On Oct 11, 2010, at 2:01 PM, Kenneth Uildriks wrote: >>> A better way for a front-end to declare that vtbl-ptr-hacking is not >>> expected and not supported is for it to emit llvm.invariant.start and >>> llvm.invariant.end calls for it. >> >> Some of us were talking about this apropos your earlier post. >> @llvm.invariant.start/end aren't appropriate, because the memory *isn't* >> invariant; the user is totally allowed to destruct the object in-place and >> create a new object there. The only thing the standard tells us is that >> old references and pointers are only considered to be automatically >> "forwarded" to the new object (i.e. aren't just invalid) if the types match. >> So we're allowed to assume that a pointer or reference validly formed >> to an object of dynamic type T will always refer to an object of that >> dynamic type. > > So does that mean that we're allowed to assume that, given an "old" > pointer to that memory, the vtbl-ptr slot hasn't changed? Which > allows us to devirtualize:Yes, and also (POD) const member variables.> Base* pT = GetMyObjectThatHappensToBeT(); > // ... > // stuff that we can't tell what it does to our memory > // ... > pT->A(); > // more mysterious stuff > pT->B(); > // etc. > > as long as we can tell that a given pointer is actually pT and not > another pointer copied from it or aliased to it?Right, which is another reason I'm skeptical of (the current design of) the invariant intrinsics; I think using them will make the analysis much harder. But they have other benefits. John.
On Oct 12, 2010, at 5:31 AM, Kenneth Uildriks wrote:> On Tue, Oct 12, 2010 at 7:00 AM, Kenneth Uildriks <kennethuil at gmail.com> wrote: >> So does that mean that we're allowed to assume that, given an "old" >> pointer to that memory, the vtbl-ptr slot hasn't changed? Which >> allows us to devirtualize: >> >> Base* pT = GetMyObjectThatHappensToBeT(); >> // ... >> // stuff that we can't tell what it does to our memory >> // ... >> pT->A(); >> // more mysterious stuff >> pT->B(); >> // etc. >> >> as long as we can tell that a given pointer is actually pT and not >> another pointer copied from it or aliased to it?I should clarify my last response to say that copies of a pointer point to the same object. When a new object is created at that storage, all the old pointers may or may not forward; only the result of the new-expression actually automatically points to the new object. But we probably shouldn't rewrite invalid uses of stale pointers to unreachable just because we can. :)> For that matter, when you can find the *last* use of pT, you should be > able to put an llvm.immutable.end marker right after it, right? Or > have I forgotten something else in the standard? (entirely possible, > it's enormous!)I'm not sure why we would. Any workable approach based on invariant ranges will need to allow open ranges.> Do you do any processing of an IR Function after you've compiled it in clang?Nothing this sophisticated. John.
On 12 October 2010 05:00, Kenneth Uildriks <kennethuil at gmail.com> wrote:> On Mon, Oct 11, 2010 at 11:10 PM, John McCall <rjmccall at apple.com> wrote: > > On Oct 11, 2010, at 2:01 PM, Kenneth Uildriks wrote: > >> A better way for a front-end to declare that vtbl-ptr-hacking is not > >> expected and not supported is for it to emit llvm.invariant.start and > >> llvm.invariant.end calls for it. > > > > Some of us were talking about this apropos your earlier post. > > @llvm.invariant.start/end aren't appropriate, because the memory *isn't* > > invariant; the user is totally allowed to destruct the object in-place > and > > create a new object there. The only thing the standard tells us is that > > old references and pointers are only considered to be automatically > > "forwarded" to the new object (i.e. aren't just invalid) if the types > match. > > So we're allowed to assume that a pointer or reference validly formed > > to an object of dynamic type T will always refer to an object of that > > dynamic type. > > So does that mean that we're allowed to assume that, given an "old" > pointer to that memory, the vtbl-ptr slot hasn't changed?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> Which > allows us to devirtualize: > > Base* pT = GetMyObjectThatHappensToBeT(); > // ... > // stuff that we can't tell what it does to our memory > // ... > pT->A(); > // more mysterious stuff > pT->B(); > // etc. > > as long as we can tell that a given pointer is actually pT and not > another pointer copied from it or aliased to it? > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20101012/a28008e8/attachment.html>
> 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. > NickSo that means you're now saying that llvm.invariant.end ought to be left the way it is, right? I've been thinking about how to better take the invariant regions into account, and it quickly became clear that it would be easier to handle if we scanned forward instead of backwards. Any way you do it, there'd be a lot more scanning in memdep than there is at present... you can't tell just by looking at the instructions between a load and a preceding potential clobber that those two instructions are actually in an invariant region. Which led me to wonder if perhaps instead of tracing individual pointers on request with memdep, we should maybe create an generalization of mem2reg to handle all pointers mentioned in a function. A clobber outside of an invariant region would "unassign" the location and all of its may-aliases. A store would "assign" the location and all of its must-aliases and "unassign" all of its may-aliases. A load would then use the SSA assignment if one is unquestionably available, or remain in place as a load and then "assign" the load result back to the pointer. No attempt would be made to remove stores during this pass. AliasSetTracker would be helpful as soon as I could get it to optionally keep all of its sets "must alias" instead of downgrading them to "may alias" as soon as a may-alias of an existing set showed up. Then I'd use a "must alias" tracker and a "may alias" tracker so I could quickly answer "what are all of this pointer's MustAlias's?" and "what are all of this pointer's MayAlias's?". After such a pass runs, the loads that now get fed to memdep are already resolved as values whenever they can be and don't have to be traced again or cached separately.