[LLVMdev] Implementing devirtualization

[Nick Lewycky]

John McCall wrote:
> On Dec 8, 2011, at 10:03 PM, Nick Lewycky wrote:
>> Noalias returns, nocapture, SCC refinement, linkonce_odr and
>> available_externally were added with the goal of making devirtualization
>> in LLVM happen, but as orthogonal independent optimizations. I think
>> LLVM should continue with this design. If you want to implement a single
>> substantial optimization pass, I would suggest FSIPSCCP as the largest
>> thing you should write.
>
> This is a lot of work that is going to be completely foiled by the presence
> of almost any opaque call at all.

Yes, but it's still useful.

Also, anything based on knowing the type hierarchy could be foiled by 
new derivations in other translation units, or that show up with dlopen.

> What's needed here is a language-independent way to exploit
> language-specific guarantees like C++ [basic.life]p7, i.e. that certain
> provenances of pointer guarantee that certain members have known,
> immutable values.  There are analogous guarantees basically everywhere;
> for example, Java arrays have a length, ADTs in System F have a
> discriminator, etc.
>
> I would suggest an intrinsic like
>    declare i8* @llvm.bless.known.memory(i8*, …) nounwind readnone
> where the … is a sequence of offset/value pairs.  The load peephole is
> then quite obvious.
>
> An interesting extra case from [basic.life]p7 is that we can also state
> that 'const' fields are invariant after the "blessing point", although
> (unlike ivars) we can't necessarily assign a fixed value to them right
> then.

There's two things going on in your proposal, one is taking advantage of 
the C++ guarantee that the vptr (or const fields) can't change after 
construction is complete, and the other is noting down what we know the 
vptr is equal to. I'm separating these because we can more often solve 
the fact that the vptr didn't change in a function regardless of what 
its callees do, than we can know what the vptr is on entry to the function.

You don't know what the vptr really is unless you can track from the 
point where the object was constructed. Without that, the program could 
add a new derived type in a plugin, then pass it to your function. 
That's why I'm advocating constant propagation as the fix here, just 
start at the point of allocation and propagate outwards.

As for immutability of the vptr and const fields, that's what I was 
aiming for with the invariant intrinsics:
   http://llvm.org/docs/LangRef.html#int_invariant_start
but it's generally considered that the design of these intrinsics isn't 
quite right. (A secondary goal of those intrinsics is to allow LICM to 
hoist things out, then in the event of register pressure have the 
backend reload by loading through the invariant pointer, saving us a 
spill onto the stack.)

Nick