Performance Comparison of Register Allocation Algorithms in Dynamic Binary Translation

This paper presents performance comparison of register allocation algorithms in DBT (dynamic binary translation). A group of register allocation algorithms including SRA (simple register allocation), GRA (global register allocation), NRA (next-use register allocation) and SGRA (simplified graph-coloring register allocation) are implemented in a DBT system and evaluated. SGRA is a simplified version of graph-coloring register allocation method proposed by us. NRA and GRA are also an optimization versions based on the target platform. From the experimental result, SGRA has the best performance on all the six programs chosen from SPEC CINT2000. The improvement of SGRA is 7.3% on average over SRA. And based on comparison of the performance of DBT system with super block technique switching on or off, we find SGRA has better performance in big allocation scope, such as super blocks and traces.