Source-code Transformations for Efficient Reversibility

Abstract

An approach based on source-to-source compilation is presented for
\nefficiently realizing reversibility of programs, in the context of the C
\nlanguage. The implementation of this approach in a portable "reverse C
\ncompiler" called rcc is described. The compiler takes arbitrary C
\nfunctions as input, and renders them reversible, and, in addition,
\nautomatically generates their reverse functions. The system is sufficiently
\ngeneral to correctly handle complex data types and to handle complex control
\nflow such as recursion and inter-mixing jump instructions. The compiler is
\ndesigned to be general-purpose, to be used in any application requiring
\nefficient reverse execution capability. A simple macro interface is used to
\nhelp retarget the compiler to different application domains. As a case
\nstudy, the application of rcc to optimistic parallel simulation is
\npresented. Optimizations, such as "message-send slicing", are presented
\nthat help in reducing the overheads that may be added for achieving
\nreversibility.