On-stack replacement is the process of interrupting a running program, optimizing some portion of that program, and then continuing execution from the point of interruption. It dynamically implements a mixed-code approach [1], in which part of the program is compact and slow, and part is expanded and fast. This approach takes advantage of the observation that programs tend to spend most of their time in a tiny fraction of their code.

The authors of this paper demonstrate an implementation of on-stack replacement in the context of LLVM, a virtual machine whose instruction set is close to that of conventional hardware. Their explanation of the implementation is clear, with well-chosen flow graphs and code snippets. Given their goals, however, the implementation is complex and therefore the description demands careful attention. A reader will need to be familiar with the basic concepts of code generation and optimization to understand this paper.

The implementation was evaluated on 16 programs, by measuring the differences in average running time with and without replacements. Six of the programs never actually performed a replacement, so these cases measured the overhead imposed by the technique (one percent or less). Of the remaining ten programs, three showed improvements of one to four percent and one was sped up by a factor of two. This indicates that the implementation is not particularly costly, and can sometimes provide a significant gain.

Although the authors’ description follows their implementation, their technique is quite general. It’s easy to imagine using the same approach in a wide variety of compilation or execution contexts.