Compiler Construction of Idempotent Regions

Abstract

Recovery functionality has many applications in computing systems, from speculation recovery in modern microprocessors to fault recovery in high-reliability systems. Modern systems commonly recover using checkpoints. However, checkpoints introduce overheads, add complexity, and often conservatively save more state than necessary. This paper develops a compiler technique to recover program state without the overheads of explicit checkpoints. Our technique breaks programs into idempotent regions -- regions that can be freely re-executed -- which allows recovery without checkpointed state. Leveraging the property of idempotence, recovery can be obrained by simple re-execution. We develop static analysis techniques to construct these regions in a compiler, and demonstrate low overheads and large region sizes using an LLVM-based implementation. Across a set of diverse benchmark suites, we construct idempotent regions almost as large as those that could be obtained with perfect runtime information. Although the resulting code runs slower, typical execution time overheads are in the range of just 2-12%.