[llvm-dev] Proposal: virtual constant propagation

[Pete Cooper via llvm-dev]

Hi Hans

The prototype Mehdi and I worked on (which I hope we can contribute on its own, or as patches to Peter’s implementation), is able to handle your use case.

I’d be interested if Peter’s is able to handle this too, but i confess I don’t yet know how his code is implemented.

Our code uses metadata to encode what is the most derived class you could be at a point in time.  Paired with complete class hierarchy in metadata, this allows us to work out which classes we could possibly be at a given call site.

For example, and I hope this is similar to what you are describing:

class Base {
  virtual void foo();
}

class A : public Base {
  void foo override();
}

class B : public A {
  // no override of foo()
}

A *p;
...
p->foo();

The call to foo here is known to be an ‘A’ or any class derived from it.  As we have the full hierarchy, we know it can only be [A, B].

Now we can look at the vtable entries on A and B, and see that both contain the same &foo in the slot we are reading from, and so devirtualize as only a single foo could possibly be called from here (otherwise UB).

We are also able to look at the users of the vtable globals themselves and see which ones are ever used.  If one isn’t used, then no-one can be one of those classes, and we can remove it from the hierarchy.  This could reduce the set of possible classes (or possible called functions at a given site) to 1, and we can devirtualize.  That sounds like it might be the case for the WebScrolBar you mention where the only possible implementation in the hierarchy is a single derived class.

Peter, i’d be interested in discussing this further, but i don’t want to digress the conversation any further from what you are trying to discuss here.  FWIW, I really like the proposal you have here and think we should get it in tree.

Cheers,
Pete
> On Jan 28, 2016, at 8:47 AM, Hans Wennborg via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> On Wed, Jan 27, 2016 at 7:57 PM, Peter Collingbourne <peter at pcc.me.uk> wrote:
>> The pass that applies this transformation will be placed early in the LTO
>> pipeline, before most of the regular optimization passes. The pass could later
>> be extended to do general devirtualization based on the bitset information:
>> 
>> - The pass can implement single-deriver (i.e. only one derived class with a
>>   non-pure virtual function definition) and single-implementation
>>   (i.e. multiple derived classes all sharing a virtual function definition
>>   from a base class) devirtualization by checking that each of the possible
>>   values loaded from the vtables in the bitset are either identical or
>>   __cxa_pure_virtual (calls to pure virtuals are UB, so we’d be fine
>>   disregarding them), and propagating the identical address into the
>>   function callee.
> 
> In addition to the constant value propagation, which looks fantastic,
> I'm also very interested in this aspect.
> 
> For example, Blink/WebKit public interface is full of classes like
> [0], which have a single implementation (sometimes there's also a mock
> implementation used in tests). In many classes (like [1]), the methods
> are not pure-virtual but have dummy implementations, but we should be
> able to figure out that the base class constructor is never called
> except when constructing the single implementation class.
> 
> Most of this interface might not be very hot, but optimizing the
> virtual barrier away seems looks like a juicy opportunity for binary
> size and inlining (and start-up time if we can drop the vtables and
> void the dynamic relocations).
> 
> Cheers,
> Hans
> 
> [0]. https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit/public/platform/WebScrollbar.h
> [1]. https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit/public/platform/WebScrollbarBehavior.h
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160128/fa41c9fa/attachment.html>