Rematerialization-based register allocation through reverse computing

Reversible computing aims at keeping all information on input and intermediate values available at any step of the computation. Rematerialization in register allocation is an alternate solution to spilling where values are recomputed from available data instead of held in registers. In this paper we present the basic ideas of our algorithm for rematerialization with reverse computing. We use the memory demanding LQCD (Lattice Quantum ChromoDynamics) application to demonstrate that important gains of up to 33% on register pressure can be obtained. This in turn enables an increase in Instruction-Level Parallelism or in Thread-Level Parallelism. We demonstrate a 16.8% (statically timed) gain over a basic LQCD computation.