As we can see, even in the case of a single inheritance, the LLVM IR that is generated can appear to be very verbose. Although the general procedure of generating a dynamic call to a method does not sound very efficient, most CPU architectures can perform this dynamic call with just two instructions.
Moreover, to turn a function into a method, a reference to the object’s data is required. This is implemented by passing the pointer to the data as the first parameter of the method. In Oberon-2, this is the explicit receiver. In languages similar to C++, it is the implicit this pointer.
With the vtable, we have a unique address in memory for each class. Does this help with the runtime-type test, too? The answer is that it helps only in a limited way. To illustrate the problem, let’s extend the class hierarchy with an Ellipse class, which inherits from the Circle class. This is not the classical is-a relationship in the mathematical sense.
If we have a shape variable of the Shape type, then we could implement the shape IS Circle type test as a comparison of the vtable pointer stored in the shape variable with the vtable pointer of the Circle class. This comparison only results in true if shape has the exact Circle type. However, if shape is indeed of the Ellipse type, then the comparison returns false, even if an object of the Ellipse type can be used in all places where only an object of the Circle type is required.
Clearly, we need to do more. The solution is to extend the virtual method table with runtime-type information. How much information you need to store depends on the source language. To support the runtime-type check, it is enough to store a pointer to the vtable of the base class, which then looks like in Figure 5.2:
Figure 5.2 – Class and vtable layout supporting simple type tests
If the test fails as described earlier, then the test is repeated with the pointer to the vtable of the base class. This is repeated until the test yields true or, if there is no base class, false. In contrast to calling a dynamic function, the type test is a costly operation because, in the worst-case scenario, the inheritance hierarchy is walked up to the root class.
If you know the whole class hierarchy, then an efficient approach is possible: you number each member of the class hierarchy in a depth-first order. Then, the type test becomes compare-against-a-number or an interval, which can be done in constant time. In fact, that is the approach of LLVM’s own runtime-type test, which we learned about in the previous chapter.
To couple runtime-type information with the vtable is a design decision, either mandated by the source language or just as an implementation detail. For example, if you need detailed runtime-type information because the source language supports reflection at runtime, and you have data types without a vtable, then coupling both is not a good idea. In C++, the coupling results in the fact that a class with virtual functions (and therefore no vtable) has no runtime-type data attached to it.
Often, programming languages support interfaces which are a collection of virtual methods. Interfaces are important because they add a useful abstraction. We will look at possible implementations of interfaces in the next section.
