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

Journal of Inforamtion Science and Engineering, Vol.8 No.3, pp.393-413 (September 1992)
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

Received July 15, 1991; revised July 27, 1992.
Communicated by Wen-Tsuen Chen.