[發明專利]動態二進制翻譯系統中超級塊的寄存器分配方法

有效

• 申請號: 200910050440.7
• 申請日: 2009-04-30
• 公開（公告）號: CN101546271A
• 公開（公告）日: 2009-09-30
• 發明（設計）人: 管海兵;梁阿磊;蔡戰舉;姜玲燕;李曉龍
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F9/45
• 分類號: G06F9/45
• 代理公司: 上海交達專利事務所
• 代理人: 毛翠瑩

技術領域

本發明涉及一種動態二進制翻譯系統中超級塊的寄存器分配方法，具備重定 向特性，能適用于多種目標平臺，尤其適用于多源多目標的二進制翻譯平臺。

背景技術

動態二進制翻譯是虛擬執行技術中應用最為廣泛的方法，是為遺留代碼提供 移植可能性和提高軟件的平臺適應性的一種有效手段，它在不需要可執行程序 的源代碼的情況下，可以動態地將源機器平臺上的二進制程序經過轉換，運行 于其他目標機器平臺上。對于動態二進制翻譯器自身而言，執行性能是一個非 常重要的衡量指標。所謂執行性能是指，以源程序在原架構下運行的效率為參 照，其在動態二進制翻譯器提供的運行環境下的效率損失度越低，翻譯器的執 行性能越好。

寄存器在計算機存儲體系結構里處于最上層，是訪問速度最快的存儲介質， 而且由于芯片大小的限制，通常寄存器數目不多，Intel的x86處理器只有8個 通用寄存器，有些RISC體系結構的寄存器數目稍多一些，但也只有幾十個左右 的寄存器，當然里面還包含很多特殊寄存器，能夠被翻譯器使用的就更少了。為 了提高翻譯器翻譯后的代碼的執行性能，動態二進制翻譯領域需要采用一種技 術，它使得翻譯后的代碼塊能夠盡可能高效的利用寄存器這一稀缺資源。但是 對于動態二進制翻譯領域，考慮到動態執行的實時性，分配方法開銷不能太高。 因此技術人員必須在更高效的使用目標平臺的寄存器和分配開銷之間尋求平 衡。動態二進制翻譯領域通常會有構造超級塊的技術，即把一些執行熱度比較 高的基本塊合起來，作為一個塊進行編碼，形成一個超級塊。所謂超級塊，是 指具有一個入口，一個或多個出口的代碼塊。對于超級塊內的寄存器的分配， 由于其執行的熱度較高，對目標代碼的質量要求也更高，因此需要采用一種優 良的寄存器分配方法。

目前，在動態二進制翻譯領域可以使用如下方法完成寄存器分配任務：

1、簡單的寄存器分配方法，這種分配算法通過對超級塊內的變量號按目標 機寄存器數目進行一次取模運算，得出的數字即是被分配的寄存器編號。如果 該寄存器被同一條指令的其他變量占用，則嘗試下一個編號的寄存器。如果該 寄存器沒有被同一條指令內的其他變量占用，則把該寄存器內容交換到內存， 然后分配該寄存器給當前變量。如果該寄存器空閑，直接分配該寄存器給當前 變量。這種方法簡單有效，開銷小，適用于動態二進制翻譯領域的及時性特性， 但沒有利用超級塊內變量的信息，使得分配結果不夠高效，寄存器使用效率不 高。

2、全局寄存器分配方法，這種方法把超級塊常用的一些變量存放在全局寄 存器中。全局變量是指在這個基本塊內被使用次數(use-frequency)最多的那個 變量，把這些變量存放在某些寄存器中，在整個超級塊的生存期，對它們都不 做替換。這種方法需要在分配前，先走查一下整個超級塊，收集超級塊內所有 變量的使用頻率信息。然后分配一些固定的寄存器給這些使用頻次最高的變量， 其余變量使用簡單的寄存器分配方法進行分配。這種方法利用了超級塊內變量 的信息，但使用不夠充分，只在開始階段利用收集到的信息固定分配了若干變 量，對后續變量的分配過程則完全丟棄了這些信息。

3、基于next-use信息的寄存器分配方法，這種方法根據超級塊內變量的 next-use信息進行寄存器分配，所謂next-use信息是指該變量下次被使用的位 置，這種方法簡單有效，適用于基本塊內寄存器分配。對于由若干基本塊組成 的超級塊，對變量信息的使用不夠充分，寄存器的分配結果不夠高效。

4、圖染色分配方法，這種方法在靜態編譯器領域有著重要的地位，它是一 種基于圖簡化思路的啟發式分配方法。它包括如下幾個步驟：

(1)變量活性信息的收集

(2)干擾圖的構造

(3)圖精簡以及寄存器分配

在靜態編譯器里，干擾信息的收集過程通常會經過多次迭代，才能達到穩定， 即活性信息在每個節點都不再變化。在圖精簡過程中遇到圖不能再精簡的情況 下通常會采用結合、冷凍、選擇溢出和實際溢出等各種高級手段來完善圖精簡 的過程。該方法復雜度太高，分配開銷太大。