Optimizing Reversible Programs

Niklas Deworetzki, Martin Kutrib, Uwe Meyer, Pia-Doreen Ritzke

In: International Conference on Reversible Computation, RC 2022, Urbino, Italy

https://doi.org/10.1007/978-3-031-09005-9_16

June 28, 2022

Abstract

Reversible programming languages have been a focus of research for more than the last decade mostly due to the work of Glück, Yokoyama, Mogensen, and many others. In this paper we report about our recent activities to optimize reversible code with respect to execution time. Based on our rc3-compiler which compiles Janus to reversible static-single-assignment form RSSA, we had explored and implemented optimization algorithms for local common-subexpression elimination, constant propagation, and folding and have presented those at SOAP 2021. This paper focuses on new achievements for procedure inlining as well as elimination of dead code. Our compiler is—to our knowledge—the first optimizing compiler for reversible languages. Whereas these optimizations are well established for “traditional” languages, programs that can be executed forwards and backwards require different and novel approaches.