Academia has spent much effort into making context-sensitive
{\em analyses} practical, with great profit.
However, the implementation of context-sensitive {\em optimizations}, in
contrast to analyses, is still not practical, due to code-size explosion.
This growth happens because current technology requires the cloning of full
paths in the Calling Context Tree.
In this paper, we present a solution to this problem.
We combine finite state machines and dynamic dispatching to allow fully
context-sensitive specialization while cloning only functions that are
effectively optimized.
This technique makes it possible to apply very liberal optimizations, such as
context-sensitive constant propagation, in large programs—something that
could not have been easily done before.
We demonstrate the viability of our idea by formalizing it in Prolog, and
implementing it in LLVM.
As a proof of concept, we have used our state machines to implement
context-sensitive constant propagation in LLVM.
The binaries produced by traditional full cloning are 2.63 times larger than
the binaries that we generate with our state machines.
When applied on Mozilla Firefox, our optimization increases binary size from 7.2MB to 9.2MB.
Full cloning, in contrast, yields a binary of 34MB.