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

有效

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

1.一種動態二進制翻譯系統中超級塊的寄存器分配方法，其特征在于包括如下步驟：

1)初始化寄存器分配器的目標平臺，包括目標平臺的寄存器數目，目標平臺的寄存器之間的數據移動機器指令，內存到寄存器的數據移動機器指令以及寄存器到內存的數據移動機器指令；

2)初始化寄存器分配器內部數據結構，包括初始化目標平臺寄存器狀態的數據結構數據，所有目標平臺寄存器狀態設為空閑，所匹配的變量設為空，所在指令設為空；初始化所有超級塊變量所在位置為內存；清空用來存放超級塊指令干擾列表的隊列；初始化用來存放單條指令里變量干擾信息的干擾列表為空；初始化寄存器預分配結果表為空；

3)從每個超級塊尾部到頭部遍歷，依次查看每條指令的變量，從中先找到定義類型的變量，查看干擾列表里是否有這個變量，如果有，則從干擾列表里移除該變量，再找到使用類型的變量，查看干擾列表里是否有這個變量，如果沒有，則插入這個變量；遍歷完這條指令的所有變量后，把干擾列表插入到隊列頭部，并把該干擾列表作為產生下一條指令的干擾列表的基礎，直到超級塊的第一條指令為止，得到超級塊指令干擾列表組成的隊列，完成干擾信息的收集；

4)初始化干擾圖為不存在干擾邊；從隊首到隊尾遍歷超級塊指令干擾列表組成的隊列，依次處理隊列里的干擾列表，凡在同一個列表的兩個變量，都在干擾圖里對應這對變量的位置記錄一條干擾邊；直到隊列尾部的干擾列表被處理，干擾圖的生成過程結束；

5)通過干擾圖查看每個變量的干擾邊，如果干擾邊數目少于目標平臺寄存器數目，則把該變量入棧，并刪除干擾圖里與該變量相關的干擾邊，如果不少于目標平臺寄存器數目，則查看下一個變量，如果干擾圖里剩余變量的干擾邊都不少于目標平臺寄存器數目，則選擇其中一個變量作為犧牲變量，從干擾圖里刪?除，并刪除與之相關的干擾邊；然后再查看下一個變量，直到干擾圖所有變量入棧為止，干擾圖簡化過程結束；

6)從棧頂依次彈出變量，找到一個沒有分配給與其存在干擾關系變量的寄存器，分配給該變量，把結果記錄在預分配結果表里；直到?？諡橹梗拇嫫黝A分配結束；

7)根據不同翻譯需要對超級塊中的變量進行寄存器的分配，分為普通分配、強制要求特定寄存器分配、強制要求非特定寄存器分配；

8)對于普通分配，依次查看寄存器的狀態，如果有寄存器狀態是已被分配，并且被分配的對象是該變量，則繼續保持這種分配，否則查看預分配結果表；如果有寄存器分配給該變量，并且該寄存器狀態是已被分配，則查看干擾圖，如果被分配給的變量與當前變量不存在干擾關系，則直接分配該寄存器，如果該變量后續指令是被使用的，把變量對應內存的值裝載進該寄存器，如果存在干擾關系，保存該寄存器里的值到被分配給的變量對應的內存，然后分配該寄存器，如果該變量后續指令是被使用的，把變量的值裝載進該寄存器；如果該寄存器為受保護狀態，則查看所有的寄存器，如果存在空閑狀態的寄存器，則分配它，如果該變量后續指令是被使用的，把變量對應的內存里的值裝載進該寄存器，如果沒有空閑寄存器，則查找一個已被分配的寄存器，保存該已被分配的寄存器里的值到該已被分配的寄存器對應的變量的內存，然后分配該已被分配的寄存器，如果該變量后續指令是被使用的，把變量對應的內存里的值裝載進該寄存器；如果預分配結果里沒有寄存器分配給它，則找到一個非受保護狀態的寄存器，優先選擇空閑寄存器分配給該變量，如果找到的是空閑寄存器，且該變量后續指令是被使用的，把該變量對應內存里的值裝載進該寄存器，如果找到的是已被分配的寄存器，首先把該已給分配的寄存器的值保存在該已被分配的寄存器對應的變量的內存，如果該變量后續指令是被使用的，把該變量對應內存里的值裝載進該寄存器；

9)對于強制要求特定寄存器分配，如果強制要求寄存器已被分配的變量恰好是該變量，則繼續保持這種分配；如果強制要求寄存器被分配的變量不是該變量，?且被分配的變量與該變量存在干擾關系，則把強制要求特定寄存器的值保存到對應變量的內存，完成數據保護處理，把該強制要求特定寄存器分配給該變量，如果該變量后續指令是被使用的并且該變量在內存里，把該變量對應的內存的數據裝載到強制要求特定寄存器，如果該變量后續指令是被使用的并且該變量在寄存器里，把該變量對應的寄存器的數據裝載到強制要求特定寄存器；如果強制要求寄存器被分配的變量不是該變量，且被分配的變量與該變量不存在干擾關系，則把該強制要求特定寄存器分配給該變量，如果該變量后續指令是被使用的并且該變量在內存里，把該變量對應的內存的數據裝載到強制要求特定寄存器，如果該變量后續指令是被使用的并且該變量在寄存器里，把該變量對應的寄存器的數據裝載到強制要求特定寄存器；

10)對于強制要求非特定寄存器分配，先保存強制要求非特定寄存器的狀態到一個臨時變量，如果強制要求非特定寄存器已經分配給了該變量，則保存強制要求非特定寄存器到該變量對應的內存，更改臨時變量的狀態為空閑，更改強制要求非特定寄存器的狀態為受保護的，然后對該變量進行普通分配，將受保護的強制要求非特定寄存器改回臨時變量的值，并以普通分配的結果作為分配結果；如果強制要求非特定寄存器沒有分配給該變量，更改強制要求非特定寄存器的狀態為受保護的，然后對該變量進行普通分配，將受保護的強制要求非特定寄存器改回臨時變量的值，并以普通分配的結果作為分配結果。?