LTO, Devirtualization, and Virtual Tables

Question

Comparing virtual functions in C++ and virtual tables in C, do compilers in general (and for sufficiently large projects) do as good a job at devirtualization?

Naively, it seems like virtual functions in C++ have slightly more semantics, thus may be easier to devirtualize.

Update: Mooing Duck mentioned inlining devirtualized functions. A quick check shows missed optimizations with virtual tables:

struct vtab {
    int (*f)();
};

struct obj {
    struct vtab *vtab;
    int data;
};

int f()
{
    return 5;
}

int main()
{
    struct vtab vtab = {f};
    struct obj obj = {&vtab, 10};

    printf("%d\n", obj.vtab->f());
}

My GCC will not inline f, although it is called directly, i.e., devirtualized. The equivalent in C++,

class A
{
public:
    virtual int f() = 0;
};

class B
{
public:
    int f() {return 5;}
};

int main()
{
    B b;
    printf("%d\n", b.f());
}

does even inline f. So there's a first difference between C and C++, although I don't think that the added semantics in the C++ version are relevant in this case.

Update 2: In order to devirtualize in C, the compiler has to prove that the function pointer in the virtual table has a certain value. In order to devirtualize in C++, the compiler has to prove that the object is an instance of a particular class. It would seem that the proof is harder in the first case. However, virtual tables are typically modified in only very few places, and most importantly: just because it looks harder, doesn't mean that compilers aren't as good in it (for otherwise you might argue that xoring is generally faster than adding two integers).

Answer 1

The difference is that in C++, the compiler can guarantee that the virtual table address never changes. In C then it's just another pointer and you could wreak any kind of havoc with it.

However, virtual tables are typically modified in only very few places

The compiler doesn't know that in C. In C++, it can assume that it never changes.

Answer 2

I tried to summarize in http://hubicka.blogspot.ca/2014/01/devirtualization-in-c-part-2-low-level.html why generic optimizations have hard time to devirtualize. Your testcase gets inlined for me with GCC 4.8.1, but in slightly less trivial testcase where you pass pointer to your "object" out of main it will not.

The reason is that to prove that the virtual table pointer in obj and the virtual table itself did not change the alias analysis module has to track all possible places you can point to it. In a non-trivial code where you pass things outside of the current compilation unit this is often a lost game.

C++ gives you more information on when type of object may change and when it is known. GCC makes use of it and it will make a lot more use of it in the next release. (I will write on that soon, too).

Answer 3

Yes, if it is possible for the compiler to deduce the exact type of a virtualized type, it can "devirtualize" (or even inline!) the call. A compiler can only do this if it can guarantee that no matter what, this is the function needed.
The major concern is basically threading. In the C++ example, the guarantees hold even in a threaded environment. In C, that can't be guaranteed, because the object could be grabbed by another thread/process, and overwritten (deliberately or otherwise), so the function is never "devirtualized" or called directly. In C the lookup will always be there.

struct A {
    virtual void func() {std::cout << "A";};
}
struct B : A {
    virtual void func() {std::cout << "B";}
}
int main() {
    B b;
    b.func(); //this will inline in optimized builds.
}

Answer 4

It depends on what you are comparing compiler inlining to. Compared to link time or profile guided or just in time optimizations, compilers have less information to use. With less information, the compile time optimizations will be more conservative (and do less inlining overall).

A compiler will still generally be pretty decent at inlining virtual functions as it is equivalent to inlining function pointer calls (say, when you pass a free function to an STL algorithm function like sort or for_each).