Static Global Register Allocation for Dynamic Binary Translators

Abstract

Dynamic Binary Translators (DBTs) facilitate the execution of binaries across different Instruction Set Architectures (ISAs). Similar to a just-in-time compiler, they recompile machine code from one ISA to another, and subsequently execute the generated code. To achieve near-native execution speed, several challenges must be overcome. This includes the problem of register allocation (RA). In classical compiler engineering, RA is often performed by global methods. However, due to the nature of DBTs, established global methods like graph coloring or linear scan are hardly applicable. This is why state-of-the-art DBTs, like QEMU, use basic-block-local methods, which come with several disadvantages. Addressing these flaws, we propose a novel global method based on static target-to-host mappings. As most applications only work on a small set of registers, mapping them statically from host to target significantly reduces load/store overhead. In a case study using our RISC-V-on-ARM64 user-mode simulator RISE-SIM, we demonstrate speedups of up to 1.4 x compared to basic-block-local methods.

Authors 4

1. Niko Zurstraβen Aachen Institute for Communication Technologies and Embedded Systems

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Institute for Communication Technologies and Embedded Systems

2. Nils Bosbach Aachen Institute for Communication Technologies and Embedded Systems

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Institute for Communication Technologies and Embedded Systems

3. Lennart M. Reimann Aachen Institute for Communication Technologies and Embedded Systems

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Institute for Communication Technologies and Embedded Systems

4. Rainer Leupers Aachen Institute for Communication Technologies and Embedded Systems

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Institute for Communication Technologies and Embedded Systems