Devirtualization in C++, part 4 (analyzing the type inheritance graph for fun and profit)

Last time I described the construction of the type inheritance graph, a main datastructure used by special purpose devirtualization algorithms. Now it is time for some real optimization fun! In this post I will review the most elementary transformations and will show some real world data.

Devirtualization in C++, part 3 (building the type inheritance graph)

Having covered the basic optimizations done by the C++ frontend and the way how generic middle-end optimizations may devirtualize. It is a time to dive into an wonderful world if special-purpose middle-end devirtualization techniques.

Topic of optimization of polymorphic calls is seemingly well covered by the literature with active research since the advent of object oriented programming (see, for example, DF Bacon, PF Sweeney: Fast static analysis of C++ virtual function calls and the numerous papers citing thisone). Pretty much all of the techniques are based on constructing and analyzing the type inheritance graph.

Unfortunately most of the research papers make assumptions that are not met in modern C++ programs. Here the situation is complicated by many C++ features including interesting implementation details of multiple and virtual inheritance partly described in this post and ability to make dynamic type changes. Important is also the fact that the compiler hardly ever see the whole program at once. Even with the link-time optimization one has to take into account the presence of shared libraries. Because shared libraries are supposed to be upgradeable without recompiling programs that use them, the compiler can not make any analysis beyond what it is given in the header files and as explained last time sometimes not even that. Moreover shared libraries are also often dynamically loaded as plugins. Contemporary C++ programs are really a lot more dynamic than most of the research assume.

Today I thus cover the seemingly simple topic of building and walking the type inheritance graph and show details one has to think about. It may seem exhausting, but so was my way to gain all this wisdom. :) I promise that next time I finally get to some real optimization fun.

Devirtualization in C++, part 2 (low-level middle-end devirtualization by forwarding stores to loads)

In the first part of the series we saw low level implementation of a polymorphic call. It is a common belief that devirtualization can be done well by the generic middle-end optimization techniques - combination of the constant propagation, store-to-load forwarding and indirect call removal. (See, for example, this post on llvm-dev, GCC developers tends to share similar sentiments.) This time I show how this is implemented and why one needs special purpose devirtualization code in the middle-end to really optimize well.

Devirtualization in C++, part 1

Devirtualization is an optimization turning polymorphic calls into direct calls. In these series I would like to describe of calls in C++ programs.  This area of compiler optimization is not really well covered by literature (it seems like all research is done on Java or interpreted languages). I will explain in detail how devirtualization works in GCC. Later I will also show some statistics collected from bigger applications, like Firerox or Libreoffice and it is quite clear that C++ programmers tends to abuse the use of virtual keyword in C++ and have various (non)-realistic assumptions on the resulting code.

Hello World!

This is freshly created blog of Honza Hubička. I plan to write here on compilers, math, history of photography and perhaps more.

Why I am creating a blog? 

This week I moved to Calgary for a post-doc in mathematics. In addition to that I am also co-running Šechtl & Voseček Museum of Photography and develop GCC. These activities usually keeps me busy. For some reason I believe that after my move I will have plenty time to sit down and write something interesting here.

Last time I did something similar was in 90's when the word "blog" did not exist. Here is what remained from my activity back then. Lets see if I find enough of persistence to get this going.