以變數存活時間區段為考量基礎之暫存器配置法

Abstract

暫存器配置的主要目的在當暫存器數目不足時，如何減少程式碼所額外插 入的溢出碼數目，進而使程式執行時，所需額外增加的執行時間亦相對的 減少。現存的暫存器配置演算法，幾乎皆以圖形塗色演算法來設計該演算 法。這種方法的好處是它將一個複雜的暫存器配置問題轉為一個簡單且優 美的圖形著色問題來處理。然而，將變數存活範圍之間的存活關係以一個 簡單的干擾圖來表示，將會失去一些程式碼的特性。而且，當暫存器用完 時，現存演算法主要考慮的是溢出碼的減少，甚少考慮到這些溢出碼的插 入位置。這些因素將會在程式執行時，影響溢出碼的真正執行次數。在本 論文中，我們提出了一個新的暫存器配置方法，稱為 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.