JISE


  [1] [2] [3] [4] [5] [6] [7] [8]


Journal of Information Science and Engineering, Vol. 8 No. 3, pp. 393-413


Register Allocation Via Dynamically Updated Information


Feipei Lai and Chia-Cheng Yeh and Hung-Chang Lee*
Dept. of Computer Science and Information 
Engineering & Dept. of Electrical Engineering 
National Taiwan University 
Taipei, Taiwan, R.O.C. 
*Dept. of Information Management 
Tamkang University, Tamsui 
Taipei, Taiwan, R.O.C.


    Register allocation is a necessary component of most compilers, especially those for RISC machines. The former graph-coloring technique [1,2] has been recognized as an effective method. However, techniques based on graph-coloring suffer from the long live range problem and that of manipulating the large interference graph [3,4]. In this paper, a different register allocation algorithm using dynamically updated information is introduced. With this method, the live range of a variable is viewed as a collection of spots, which are the coordinate distances where the variable is used. Together with the usage counts of a variable and the increased weight on a variable in the loop structure, we estimate the cost of each variable already in the register. In case a spill is not avoidable, the variable in the register with minimum cost is chosen. Primary results show that this method diminishes the number of load/stores by about 21%, when compared with Chow's [5] graph-coloring method.


Keywords: interference, graph-coloring, register allocation, spot, estimation function

  Retrieve PDF document (JISE_199203_04.pdf)