Dynamic dispatch of context-sensitive optimizations

Abstract

The compilers community has dedicated much time and effort in making context-sensitive analyses scalable, with great profit. However, the implementation of context-sensitive optimizations remains a challenge. The main problem is code size growth. Both function cloning and inlining are based on creating copies of all functions in the call path that leads to each optimization, even when that involves copying functions that are not optimized. We propose a solution for that problem. Using a combination of dynamic dispatch and a state machine to dynamically control the transitions between calling contexts, our method implements fully context-sensitive optimizations only needing to copy optimized functions. Experiments in the LLVM Test Suite and SPEC CPU2006 show our method scales better than cloning, using 8.5x less bytes to implement the same optimizations. We have also observed speed-ups of up to 20% on top of LLVM -O3 using fully context-sensitive constant propagation.