Multiple interface vtable design

Beginners
1

Hi, this is perhaps more a design question than an LLVM question (let me know if I should post it elsewhere):

I’m implementing interfaces in my toy language, and are wondering how to design my vtable layout.
The way I envision it is like this:
Every interface defines a set of functions, and a vtable containing those function signatures as a type. Each class then defines its implementation of the vtable type (function pointers) and hold a pointer to the vtable within each instance. I should then at runtime be able to look up the implementation of a function given an instance and its implemented vtable.

My question concerns the situation where multiple interfaces are implemented, and a function which accepts an interface as argument: How do I know which vtable to look in?

If classA implements IFoo and IBar, and classB only implements IBar, and I’m compiling a function which takes an IBar instance, then classA and classB will (probably) hold their IBar vtable pointer at different indices in their structs.

Here’s my toy language scenario:

interface IFoo {
    fooFunction(Int a, Int b): Int
}

interface IBar {
    barFunction(Int a): None
}

class ClassA implements IFoo, IBar {
    fooFunction(Int a, Int b): Int {
        ...
    }

    barFunction(Int a): None {
        ...
    }
}

class ClassB implements IBar {
    barFunction(Int a): None {
        ...
    }
}

functionTakesInterface(IBar x): None {
    x.barFunction(2)
    // How can I ask x where to find its IBar vtable pointer?
}

One idea I had: All types have a unique “index”, e.g. stored in a global array. For every interface, make a list of pointers where the index corresponds to the type and the value is the vtable pointer for that type (to that interface). Then I only have to ask the instance for its type-index at runtime, but it might not scale well if only 3 of 10000 types implement the interface.

Thank you in advance!

2

It’s relevant to generating LLVM IR, so it’s close enough to being on-topic, I think…

You probably want to look at what other languages are doing for inspiration. A few different takes on this I’m familiar with (writing quickly, so take what I’ve written with a grain of salt):

For C++, the way multiple inheritance works is that the pointer doesn’t point to the beginning of the object; it points to the vtable pointer. See Itanium C++ ABI for the gory details.

Rust traits doesn’t embed vtable pointers into objects at all; instead, the vtable pointer is passed alongside the object pointer. See rust - What is a "fat pointer"? - Stack Overflow for a brief description.

Objective-C protocols don’t involve vtables at all; the runtime dynamically computes the called method.

3

Thank you for your reply!

I think I will try to implement something similar to the fat pointer, so a ‘this’ pointer and the relevant vtable pointer in a structure. Not sure how to do the same with the C++ model, e.g. getting the ‘this’ pointer given the address of the vtable pointer.

4

@efriedma-quic Thanks, I think I got it working with fat pointers. The code above now produce this IR:

// Stores 'this' pointer and vtable pointer
%FatPointer = type { i64*, i64* }

%IBar_vtable = type { void (i64*, i32)* }
%IFoo_vtable = type { i32 (i64*, i32, i32)* }

%ClassA = type {}
@ClassA_IBar_vtable = constant %IBar_vtable { void (%ClassA*, i32)* @ClassA_barFunction }
@ClassA_IFoo_vtable = constant %IFoo_vtable { i32 (%ClassA*, i32, i32)* @ClassA_fooFunction }

%ClassB = type {}
@ClassB_IBar_vtable = constant %IBar_vtable { void (%ClassB*, i32)* @ClassB_barFunction }

define i32 @ClassA_fooFunction(%ClassA* %this, i32 %a, i32 %b) {
  ...
}

define void @ClassA_barFunction(%ClassA* %this, i32 %a) {
  ...
}

define void @ClassB_barFunction(%ClassB* %this, i32 %a) {
  ...
}

define void @functionTakesInterface(%FatPointer* %x) {
functionTakesInterface_body:
  %0 = getelementptr %FatPointer, %FatPointer* %x, i32 0, i32 0
  %1 = load i64*, i64** %0, align 8
  %2 = bitcast i64* %1 to i64*
  %3 = getelementptr %FatPointer, %FatPointer* %x, i32 0, i32 1
  %4 = load i64*, i64** %3, align 8
  %5 = bitcast i64* %4 to %IBar_vtable*
  %6 = getelementptr %IBar_vtable, %IBar_vtable* %5, i32 0, i32 0
  %7 = load void (i64*, i32)*, void (i64*, i32)** %6, align 8
  call void %7(i64* %2, i32 2)
  ret void
}

Calling functions I now inspect if the target parameter is an interface, and then pass the fat-pointer instead:

// functionTakesInterface(new ClassA())

define i32 @main() {
entrypoint:
  %malloccall = tail call i8* @malloc(i64 0)
  %0 = bitcast i8* %malloccall to %ClassA*
  call void @ClassA_constructor(%ClassA* %0)

  // Store 'this'
  %1 = alloca %FatPointer, align 8
  %2 = getelementptr %FatPointer, %FatPointer* %1, i32 0, i32 0
  %3 = bitcast %ClassA* %0 to i64*
  store i64* %3, i64** %2, align 8

  // Store 'vtable'
  %4 = getelementptr %FatPointer, %FatPointer* %1, i32 0, i32 1
  %5 = bitcast %IBar_vtable* @ClassA_IBar_vtable to i64*
  store i64* %5, i64** %4, align 8
  call void @functionTakesInterface(%FatPointer* %1)
  ret i32 0
}

I’m not sure all the bitcasting is correct or necessary, but I guess I will find out later. :stuck_out_tongue: