[LLVMdev] Hash Table Virtual Calls with Conflict Resolution Stubs

[Stephen Cross]

Hi everyone,

I'm the developer of the Loci programming language (
http://loci-lang.org ), for which the compiler is a front-end for
LLVM. I would like to say that LLVM has been extremely useful for the
development of the compiler and so thank you everyone for building
this amazing system.

---- Virtual Method Calls ----

While most aspects of the language map well onto LLVM IR, it seems
non-trivial to generate the virtual method calls in LLVM. Loci uses a
concept called 'structural typing' [1], which basically means classes
don't have to explicitly implement interfaces; if a class has the
methods required by the interface then the class -> interface cast is
valid. A hash table is therefore used to represent the virtual method
table of an object, in which a virtual method call indexes the hash
table with a hash of the method name and then calls the function
pointer it finds in the corresponding slot.

Clearly there can be clashes in the hash table where two (or more)
method names map to the same hash table slot. There are various
approaches for conflict resolution but the cheapest seems to be
setting a hidden value (such as a register) on the caller side to a
larger integer hash value (a large enough space in which collisions
are assumed not to occur) and then generating a 'conflict resolution
stub', which does something like:

    conflict_resolution_stub:
           cmp eax, <METHOD 1 HASH>
           jne .method_2
    .method_1:
           jmp method_1
    .method_2:
           jmp method_2

So in this case 'eax' is being used for conflict resolution and a
simple comparison can distinguish the two methods. The nice aspect of
this approach is that collisions aren't expected to occur in most
cases so the method function can be directly placed in the vtable and
the hidden value will simply be ignored in those cases. Hence in
general the only overhead versus a C++ virtual call is setting the
hidden value, which is essentially a negligible cost. For more detail,
the basic elements of the virtual call mechanism are described in
'Invokeinterface Considered Harmless' [2] (albeit for Java).

---- Encoding calls in LLVM IR ----

Encoding this information in LLVM IR seems to be very difficult,
albeit I've noticed some recent developments (such as musttail) that
could be useful for this. There was a previous discussion of this
issue in 2011 [3] and the conclusion seemed to be that the mechanism
above couldn't be encoded in LLVM IR.

It is possible to generate the necessary inline assembly, but then
LLVM has no knowledge of the function calls and hence no inlining
occurs and all the optimisations hit this boundary. Ideally it would
be possible to generate safe LLVM IR that could be understood by
existing optimisation passes.

So I'm wondering:

* Is there anything in LLVM IR that could help?
* If this currently can't be encoded in LLVM IR, what changes do you
think would be necessary to support this?

I understand that LLVM may not have complete support for this use case
right now; I'd be very happy to do the necessary work and submit any
relevant patches for review. I am very keen *not* to fork LLVM but
instead to try to make upstream changes that are as broadly useful as
possible. I've added some notes below about what approach might be
taken and I'd be interested to know what you think.

Kind regards,
Stephen Cross

[1] http://loci-lang.org/StructuralTyping.html
[2] https://www.research.ibm.com/people/d/dgrove/papers/oopsla01.pdf
[3] http://marc.info/?l=llvm-dev&m=129594650017675

---- Notes about potential approaches ----

In terms of the approach, there are at least two parts to this problem:

* Setting/retrieving the hidden value
* Forwarding function arguments

For the former, two vague ideas I had were adding a new calling
convention (it might be useful if external projects could use hooks to
add in their own calling conventions) or modifying inreg to allow
specifying a particular register (albeit encoding target-specific
information like this isn't ideal). Another approach could be adding a
parameter attribute (e.g. 'hidden' or 'outofband') that puts the
parameter in some target-specific location. The 'llvm.read_register'
and 'llvm.write_register' intrinsics would only be useful if they
could guarantee the relevant register wasn't going to be overwritten
in the meantime (and they'd also need to support more registers than
currently).

As for forwarding arguments, it seems like the combination of
'musttail' and varargs come close to satisfying this. The only issue
is that it's not possible to forward a return value.