|
|
|
| A Register Allocation Algorithm Based on Regions Priority |
| Yue Feng Pang Jian-min Zhao Rong-cai |
| PLA Information Engineering University, Zhengzhou 450002, China |
|
|
|
|
Abstract 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.
|
|
Received: 26 October 2012
|
|
|
|
Corresponding Authors:
Yue Feng
E-mail: firstchoiceyf@sina.com
|
|
|
|
|
|
|
2013, Vol. 35 
