On Mon, Oct 11, 2010 at 3:55 PM, John McCall <rjmccall at apple.com> wrote:> > On Oct 11, 2010, at 10:43 AM, Kenneth Uildriks wrote: > > On Mon, Oct 11, 2010 at 12:30 PM, John McCall <rjmccall at apple.com> wrote: > > On Oct 11, 2010, at 9:12 AM, Kenneth Uildriks wrote: > > 3. The front-end, recognizing that scribbling on an instance's vtbl > > pointer has undefined results, eliminated the loads of the vtbl > > pointer and replaced them with @classvtbl.TestVirtual. This would > > allow devirtualization within a function at least, but (I think) would > > do less to allow analysis to spot devirtualization opportunities > > across functions. (Although ArgPromotion could arrange to have the > > vtbl pointer passed in separately, and then inlining and/or partial > > specialization could be made to see that it's a pointer to a constant > > and thus add in the IndirectCallBonus) > > There are always going to be cases that can only be deduced with > > language knowledge. We already do some frontend de-virtualization; > > this may just be a missing case. Can you post your test? > > I compiled the attached c++ code to bitcode using clang++ -O3, then > ran it through opt -std-compile-opts. I got a reload of the vtbl > pointer after the printf call. The compiler is allowed to cache the > vtbl pointer as soon as the object is constructed or passed into a > function, right? > > Yes. This is [basic.life]p7, which lists the conditions under which a > pointer > or reference to an object are considered to automatically forward to a new > object that's created at that location (as opposed to formally still > pointing > at the destroyed object). One key constraint is that the objects have to be > of identical type, i.e. their pointers would have to match exactly. So this > is > a fair optimization as long as we make sure that we keep pointers separate. > For example, consider the following test case: > struct A { virtual void foo(); }; > struct B : A { virtual void foo(); }; > void test() { > A *a = new A(); > a->foo(); // 1 > a->foo(); // 2: can assume object type is still A > a->~A(); > A *b = new (a) B(); > a->foo(); // 3: illegal use after end of lifetime > b->foo(); // 4: okay, can assume object type is still B > } > Here we happen to be able to prove that 'a' and 'b' have identical values, > but they nonetheless have different properties for this optimization because > 'a' doesn't meet the criteria for having been forwarded, whereas 'b' points > to > the new object. > Right now, we don't have any good machinery for doing this kind of > language-specific optimization in the backend. Doing it in the front-end > for your test case would require inter-statement analysis, which we've tried > to avoid in clang. > So I think the best bet for this optimization for now is to do it based on > the > knowledge that printf doesn't modify that particular argument. > John.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. I tried putting that into my test code as well, and found that support for it could use some work. In particular, MemoryDependenceAnalysis seems to be the main consumer of it, and it only recognizes it if the entire invariant region is between a pointer store and a pointer load... it scans backward from the load, looking for llvm.invariant.end and starts skipping everything that precedes it until it finds a matching llvm.invariant.begin. It seems to me that the generally expected way for these markers to behave is to allow the region cover the entire range of instructions during which the invariance holds, including any loads of the memory, which MemoryDependenceAnalysis does *not* support at present. At any rate, having the front-end add those markers for the instance vtbl pointer shouldn't hurt anything, and should enable devirtualization in a variety of situations, including some cross-function scenarios. In your example above, the llvm.lifetime.start and llvm.lifetime.end would also be useful. llvm.lifetime.end would go after the destructor call, and llvm.lifetime.start would go right before the constructor calls. MemoryDependenceAnalysis also has code to look for those markers, but I haven't tested it. It looks like my best plan of attack given what parts of the system I understand is to improve the handling of those markers. It looks to me like those markers are exactly what clang needs to express vptr value lifetime & invariance, allowing better back-end optimization and avoiding inter-statement analysis.
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. One possibility is to attach metadata to the object pointer somehow, saying that it's to an object of a certain dynamic type; it would then be simple for a language-specific optimization to fold vtable loads from such pointers into the appropriate vtable pointer, which would in turn be subject to additional folding. The chief obstacle here is preventing other optimizations from merging two tagged pointers in a way that leaves only one of the tags in place, which could break semantics. To handle this, we could introduce an opaque readnone no-op intrinsic (@llvm.bless?) after constructor calls (its return value being the result of the new-expression) and before destructor calls (its return value becoming the dtor's 'this' pointer). That, however, has the disadvantage of interfering with memory optimizations between the ctor, lifetime, and dtor; but maybe those optimizations could be taught to look through blessings. (kudos to djg and sabre for the discussion earlier) John.
John McCall 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.Emit an invariant.end before the destructor and invariant.start before the constructor. Are there cases where you can't tell (in Clang) whether the callee is the destructor? For example, it is forbidden to take the address of a destructor in C++. Nick 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. > > One possibility is to attach metadata to the object pointer somehow, > saying that it's to an object of a certain dynamic type; it would then > be simple for a language-specific optimization to fold vtable loads > from such pointers into the appropriate vtable pointer, which would > in turn be subject to additional folding. The chief obstacle here is > preventing other optimizations from merging two tagged pointers > in a way that leaves only one of the tags in place, which could break > semantics. To handle this, we could introduce an opaque readnone > no-op intrinsic (@llvm.bless?) after constructor calls (its return value > being the result of the new-expression) and before destructor calls > (its return value becoming the dtor's 'this' pointer). That, however, > has the disadvantage of interfering with memory optimizations > between the ctor, lifetime, and dtor; but maybe those optimizations > could be taught to look through blessings. > > (kudos to djg and sabre for the discussion earlier) > > John. > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
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?