DOI: 10.3724/SP.J.1146.2012.01382

Journal of Electronics & Information Technology (电子与信息学报) 2013/35:12 PP.3005-3010

A Register Allocation Algorithm Based on Regions Priority

Compiling speed and code quality are two key factors to evaluate the performance of register allocation. Modern Just In Time (JIT) compilers desire the best code in least time. Neither traditional graph coloring algorithm nor linear scan algorithm can satisfy the condition perfectly. A regions priority algorithm is proposed in this paper, which does not pursue the perfect register allocation in theory but takes greedy design method. The program is divided by loop region, on which physical register allocation is implemented by dealing lifetime length priority queue and spill weight priority queue. Then the allocation extends to the whole program. This algorithm creates high quality code in linear time and is applied to the compiler which compiles PTX instructions in SSA to traditional multicore platform. The experiment based on this compiler verifies the effectiveness of the algorithm.

Key words:Compiler,Register allocation,Loop region divide,Greedy,Lifetime length priority,Spill weight priority

ReleaseDate:2014-07-21 17:04:26