[LLVMdev] Implementing devirtualization

[John McCall]

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.

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.

John.