標題: 以變數存活時間區段為考量基礎之暫存器配置法
Time Interval-Based Coloring Approach to Register Allocation
作者: 陳清偉
Ching-Wei Chen
鍾崇斌
Chung-Ping Chung
資訊科學與工程研究所
關鍵字: 暫存器配置; 圖形著色; 變數存活範圍; 動態執行次數; 時間區段溢出碼;reg. alloc.;graph coloring;live range of a variable; dynamic execut. count;time interval;spill code
公開日期: 1993
摘要: 暫存器配置的主要目的在當暫存器數目不足時,如何減少程式碼所額外插
入的溢出碼數目,進而使程式執行時,所需額外增加的執行時間亦相對的
減少。現存的暫存器配置演算法,幾乎皆以圖形塗色演算法來設計該演算
法。這種方法的好處是它將一個複雜的暫存器配置問題轉為一個簡單且優
美的圖形著色問題來處理。然而,將變數存活範圍之間的存活關係以一個
簡單的干擾圖來表示,將會失去一些程式碼的特性。而且,當暫存器用完
時,現存演算法主要考慮的是溢出碼的減少,甚少考慮到這些溢出碼的插
入位置。這些因素將會在程式執行時,影響溢出碼的真正執行次數。在本
論文中,我們提出了一個新的暫存器配置方法,稱為 IBRA ( Interval-
Based Register Allocator)。它將傳統干擾圖加入變數存活範圍時間因
素的考慮,使得著色配置時,亦涵蓋程式碼的特性。並且它考慮到程式執
行時的動態情形。由程式模擬的結果顯示, IBRA 在靜態上額外增加的指
令數目及動態上額外增加的指令執行時間,較 "每處插入溢出碼 " 技術
分別減少了百分之 37.7 及百分之 76.77 。而 "每處插入溢出碼"技術經
過最佳化步驟的改進後, IBRA 仍較改善後的版本分別減少了百分之
13.95 及百分之 64.87 對於程式動態上的執行時間而言, IBRA 的結果
令人滿意與鼓舞。
The main goals of register allocation are to minimize number of
spill codes and additional execution time caused by extra
codes, when the number of available registers is not
sufficient. The existing register allocation algorithms were
always based on graph coloring algorithm. The advantage is that
graph coloring allocation is an elegant approach if no spilling
is required. Unfortunately, it lost much information of a
program to represent the interference relation among the live
ranges with a simple interference graph. Moreover, when
spilling is necessary, the goal of the spilling decision of
existing algorithms is to minimize the number of spill codes,
but seldom consider the location of insertion. These
considerations decide execution count of spill codes. In this
thesis, we propose a technique that based on the time interval
and the flow of control of a variable, named IBRA (Interval-
Based Register Allocator). It improves the interference graph
by adding the time interval information, which exhibits the
characteristics of a program during the coloring stage.
Moreover, it takes profiling of a program into account. It
first allocates the live ranges in the main trace of a program,
then that in the other traces. With a small amount of
additional instructions, IBRA provides a better allocation.
Simulation results show that for some cases, the number of
additional codes increased with IBRA is more than previous
techniques do. Generally speaking, with IBRA technique, the
amount of spill code needed and that of extra execution time
are reduced about 37.7 percent and 76.71 percent , compared
with the technique of spilling. We also compare the modified
version with optimizations , the amount of spill code needed
and that of extra execution time are reduced about 13.95
percent and 64.87 percent. From viewpoint of dynamic execution
time, the results of IBRA are satisfactory.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT820392049
http://hdl.handle.net/11536/57855
顯示於類別:畢業論文