Hardware atomicity for compiler-directed control speculation

This dissertation introduces the atomic region as a novel compiler abstraction which eases the development of speculative compiler optimizations. As this dissertation will show, speculation enables a compiler writer to exploit dynamically occurring opportunities which would otherwise be difficult or even impossible to expose. Despite their potential, speculative optimizations typically involve complex implementation and significant compiler re-engineering. In comparison, the atomic region abstraction is both simple to incorporate into a compiler infrastructure and also exposes speculative opportunity to existing and unmodified optimizations. The utility of the atomic region abstraction largely derives from its use of hardware atomicity---the execution of a region of code either completely, and as if all operations in the region occurred at one instant, or not at all. Hardware atomicity is an architectural primitive which provides software with a simple and intuitive model of execution, namely the ability to either explicitly commit or rollback a region of code. The atomic region abstraction leverages hardware atomicity to enable a compiler writer to easily reason about and implement speculative optimization. In the atomic region abstraction, the compiler encapsulates commonly executed regions of the program using the hardware atomicity primitive. This permits the compiler to generate a speculative version of the code where uncommonly executed code paths are completely removed such that they do not need to be considered in (and hence do not constrain) a region's optimization. Pruned paths are converted into assert operations that trigger an abort in the uncommon case that one of these paths is needed. On an abort, hardware reverts state back to the beginning of the region and transfers control to a non-speculative version of the code. Two implementations of the atomic region abstraction are also presented, the first of which demonstrates potential for a 10-15% average performance improvement in the context of a Java Virtual Machine, albeit running on simulated hardware. Incorporation of the atomic region abstraction is shown to be a simple and, thereby, a cost-effective means for exposing speculative optimization opportunities to the compiler. The second implementation leverages a real system to demonstrate that at least some of these gains are achievable in practice. By incorporating the atomic region abstraction into the dynamic translator of the Transmeta Efficeon processor, practical concerns related to the identification of speculative opportunities and adaptation to misspeculations are explored. In the context of this real system, a straightforward implementation using simple control mechanisms is shown to be sufficient to achieve a 3% average performance improvement