Register Liveness Analysis for Optimizing Dynamic Binary Translation

Mark Probst and Andreas Krall and Bernhard Scholz

CD Laboratory for Compilation Techniques
Institut für Computersprachen
Technische Universität Wien
Argentinierstraße 8
A-1040 Wien, Austria


Dynamic binary translators compile machine code from a source architecture to a target architecture at run time. Due to the hard time constraints of just-in-time compilation only highly efficient optimization algorithms can be employed. Common problems are an insufficient number of registers on the target architecture and the different handling of condition codes in source and target architecture. Without optimizations useless stores and computations are generated by the dynamic binary translator and cause significant performance losses. In order to eliminate these useless operations, a very fast liveness analysis is required.

We present a dynamic liveness analysis algorithm that trades precision for fast execution and conducted experiments with the SpecInt95 benchmark suite using our PowerPC to Alpha translator. The optimizations reduced the number of stores by about 50 percent. This resulted in a speed-up of 10 to 30 percent depending on the target machine. The dynamic liveness analysis results are very close to the most precise solution.