Nick Lewycky
2013-May-10 01:34 UTC
[LLVMdev] "load groups" IR feature to improve C++ devirtualization
I'm looking into how we can improve devirtualization in clang, and there a language in C++ feature I'd like to take advantage of which would let us perform elimination of more vptr loads. In this code: Cls *p = new Cls; p->virtual_method1(); p->method_changing_vptr(); // uses placement new to legally change the vptr p->virtual_method2(); // invalid! Cls *q = p; q->virtual_method2(); // this must get a new vptr lookup. there is no need to reload p's vptr, even if the method did update the vptr. C++ [basic.life] gives us a guarantee that a pointer will only update to point to a new object allocated at the same place in memory under certain circumstances. If the C++ code uses the same pointer, reference or name to refer to the object, then we can prove that the vptr and any const members did not change. I'd like clang to compute whether a load is eligible for this treatment per the rules in C++, and encode that in LLVM IR for further optimization. (Note that this is different from @llvm.invariant because method_changing_vptr_through_placement_new may be inlined and is required to see the updated vptr.) To implement this, I propose a new intrinsic in LLVM: declare {}* @llvm.load.group() and new metadata on loads: !load.group %group where %group must be the result of a call to llvm.load.group. Any two loads with the same %group value are known to produce the same value. We can then choose to eliminate the latter of the loads as redundant in GVN, or in the event of high register pressure we could choose to reload without spilling to the stack. For clang, let us say that two expressions E1 and E2 of the same type denote the same value if: * E1 and E2 both name the same variable, which is either of class or reference-to-class type or const pointer-to-class type, or is of non-const pointer type and is known to have not changed between the evaluations of E1 and E2. (By introductory text in [basic.life]). * E1 and E2 are of the form E3.x and E4.x, or E3->x and E4->x, or E3[x] and E4[x], for the same x, and E3 and E4 denote the same value, and the denoted subobject either has a const-qualified type or is a reference. (By bullet 3, ibid). * (Fudging a bit on E1 and E2 being expressions...) E1 and E2 are both references to the same vptr slot. (By bullet 2 or 4, ibid). Let me know if you think this design can be improved, or if there are cases it doesn't handle (or gets wrong). An explicit non-goal is the "constructor not defined in TU" problem. Nick -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130509/f4728a42/attachment.html>
John McCall
2013-May-10 02:13 UTC
[LLVMdev] [cfe-dev] "load groups" IR feature to improve C++ devirtualization
On May 9, 2013, at 6:34 PM, Nick Lewycky <nlewycky at google.com> wrote:> I'm looking into how we can improve devirtualization in clang, and there a language in C++ feature I'd like to take advantage of which would let us perform elimination of more vptr loads. In this code: > > Cls *p = new Cls; > p->virtual_method1(); > p->method_changing_vptr(); // uses placement new to legally change the vptr > p->virtual_method2(); // invalid! > Cls *q = p; > q->virtual_method2(); // this must get a new vptr lookup.This is not how I understand the [basic.life] rules. The question is whether a pointer value, reference, or name is formally forwarded to point to the new object. Because the dynamic type is different, the pointer value held in 'p' is not updated. Copying that value into 'q' does not change the fact that the pointer value still refers to a non-existent object. It is unclear what, exactly, under the rules constitutes forming a valid pointer to the newly-constructed object except using the result of the new-expression itself. I think an explicit cast might, ignoring all "object-ness" of the source pointer and simply treating it formally as a pointer to some storage that you are casting to the type of an object stored there? John.
Nick Lewycky
2013-May-10 04:22 UTC
[LLVMdev] [cfe-dev] "load groups" IR feature to improve C++ devirtualization
On 9 May 2013 19:13, John McCall <rjmccall at apple.com> wrote:> On May 9, 2013, at 6:34 PM, Nick Lewycky <nlewycky at google.com> wrote: > > I'm looking into how we can improve devirtualization in clang, and there > a language in C++ feature I'd like to take advantage of which would let us > perform elimination of more vptr loads. In this code: > > > > Cls *p = new Cls; > > p->virtual_method1(); > > p->method_changing_vptr(); // uses placement new to legally change > the vptr > > p->virtual_method2(); // invalid! > > Cls *q = p; > > q->virtual_method2(); // this must get a new vptr lookup. >I bungled my example, and I want to fix that first. I was thinking: Derived *p = new Derived; p->virtual_method1(); p->method_changing_vptr(); // uses placement new to legally change the vptr to Base p->virtual_method2(); // invalid! Base *q = p; q->virtual_method2(); // this must get a new vptr lookup. which doesn't address your concerns. This is not how I understand the [basic.life] rules. The question is> whether a pointer value, reference, or name is formally forwarded to point > to the new object. Because the dynamic type is different, the pointer > value held in 'p' is not updated. Copying that value into 'q' does not > change the fact that the pointer value still refers to a non-existent > object. >I'm actually okay with the simple copy not forming a new object pointer. However, "Base *q = reinterpret_cast<Base*>(p);" really ought to. It is unclear what, exactly, under the rules constitutes forming a valid> pointer to the newly-constructed object except using the result of the > new-expression itself. I think an explicit cast might, ignoring all > "object-ness" of the source pointer and simply treating it formally as a > pointer to some storage that you are casting to the type of an object > stored there? >I want to make optimizations to the program that people can't object to through a cursory reading of the standard, which is made difficult by the standard being contradictory on many relevant points here. Ultimately I've chosen to be very liberal about what I'm allowing to be considered a newly formed valid pointer. BTW, Richard came up with a wonderful example. What do you make of this?: char alignas(A, B) buffer[max(sizeof(A), sizeof(B))]; A *a = reinterpret_cast<A*>(buffer); B *b = reinterpret_cast<B*>(buffer); new(buffer) A; a->vfn(); new(buffer) B; b->vfn(); Valid? Nick -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130509/06228a9a/attachment.html>
Rafael EspĂndola
2013-May-22 18:44 UTC
[LLVMdev] [cfe-dev] "load groups" IR feature to improve C++ devirtualization
> where %group must be the result of a call to llvm.load.group. Any two loads > with the same %group value are known to produce the same value. We can then > choose to eliminate the latter of the loads as redundant in GVN, or in the > event of high register pressure we could choose to reload without spilling > to the stack.What mark would GVN leave on the IR for the register allocator to use when rematerializing the load?> NickCheers, Rafael
Nick Lewycky
2013-May-22 23:27 UTC
[LLVMdev] [cfe-dev] "load groups" IR feature to improve C++ devirtualization
On 22 May 2013 11:44, Rafael EspĂndola <rafael.espindola at gmail.com> wrote:> > where %group must be the result of a call to llvm.load.group. Any two > loads > > with the same %group value are known to produce the same value. We can > then > > choose to eliminate the latter of the loads as redundant in GVN, or in > the > > event of high register pressure we could choose to reload without > spilling > > to the stack. > > What mark would GVN leave on the IR for the register allocator to use > when rematerializing the load? >It's something novel we would have to create, probably by slapping metadata on the load. This proposal is dead, in favour of my newer proposal for @llvm.newobject (in the same thread). That proposal is stalled because it relies on picking a certain interpretation of the C++ standard in an area where the standard is self-contradictory. There are other issues in devirtualization which I can make progress on (PR11331 is one, and "knowing the initial value of the vtable post-constructor where the constructor is not defined in this translation unit" is another), but I think I need to drop the category of "same pointer implies same vtable" optimizations until there are language changes that support it. Nick -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130522/2201cd44/attachment.html>
Maybe Matching Threads
- [LLVMdev] [cfe-dev] "load groups" IR feature to improve C++ devirtualization
- [LLVMdev] [cfe-dev] "load groups" IR feature to improve C++ devirtualization
- [LLVMdev] [cfe-dev] "load groups" IR feature to improve C++ devirtualization
- [LLVMdev] Missed devirtualization opportunities
- [LLVMdev] [cfe-dev] "load groups" IR feature to improve C++ devirtualization