Efficient and General On-Stack Replacement for Aggressive Program Specialization

Sunil Soman and Chandra Krintz
2006 International Conference on Programming Languages and Compilers (PLC'06), June 26-29, Las Vegas, NV



In this paper, we address the problem of efficient invalidation and dynamic replacement of executing code, i.e., on-stack replacement (OSR). Our goal with this research, is to facilitate effective, aggressive, specialization of object-oriented programs that are dynamically loaded, incrementally compiled, and garbage collected. Extant approaches to OSR restrict the performance potential of program specialization since their implementations are special-purpose and prohibit compiler optimization at and across points at which OSR may occur.

We present a novel, general-purpose, version of OSR that is more amenable to optimization than prior approaches. In particular, we decouple the OSR implementation from the optimization process and update the necessary OSR program state information incrementally as the compiler performs optimizations. As a result, our OSR implementation is efficient enough to enable the use of code specializations that are invalidated by any event -- including those external to program code execution. Our results indicate that our implementation can improve execution performance by improving code quality over an extant, state-of-the-art, OSR implementation by 1-42% (9% on average).

We also present results that demonstrate the generality of our OSR implementation for three OSR-based techniques: (1) Aggressive specializations designed for a system that switches between different garbage collectors dynamically, (2) a novel specialization for write-barrier avoidance for generational garbage collection, and, (3) an existing, commonly used, specialization that speculatively inlines virtual method calls. Our experiments indicate that performance improvements of up to 16% for these techniques are possible.