Fast static analysis of C++ virtual function calls

TLDR

Virtual functions simplify code reuse but hinder compiler analysis. The study evaluates three static analysis algorithms that resolve virtual function calls to reduce compiled code size and program complexity. The most precise algorithm resolves 71 % of virtual function calls, cuts compiled code size by 25 %, processes 3,300 source lines per second on an 80 MHz PowerPC 601, and is an excellent candidate for production compilers.

Abstract

Virtual functions make code easier for programmers to reuse but also make it harder for compilers to analyze. We investigate the ability of three static analysis algorithms to improve C++ programs by resolving virtual function calls, thereby reducing compiled code size and reducing program complexity so as to improve both human and automated program understanding and analysis. In measurements of seven programs of significant size (5000 to 20000 lines of code each) we found that on average the most precise of the three algorithms resolved 71% of the virtual function calls and reduced compiled code size by 25%. This algorithm is very fast: it analyzes 3300 source lines per second on an 80 MHz PowerPC 601. Because of its accuracy and speed, this algorithm is an excellent candidate for inclusion in production C++ compilers.