[發明專利]一種針對混合長度指令集的寄存器分配方法

有效

• 申請號: 201110333460.2
• 申請日: 2011-10-28
• 公開（公告）號: CN102360280A
• 公開（公告）日: 2012-02-22
• 發明（設計）人: 李瑩;閆衛斌;吳朝暉;尹建偉;鄧水光;吳健
• 申請（專利權）人: 浙江大學
• 主分類號: G06F9/30
• 分類號: G06F9/30;G06F9/318
• 代理公司: 杭州裕陽專利事務所(普通合伙) 33221
• 代理人: 江助菊

1.一種針對混合長度指令集的寄存器分配方法，其特征在于，包括如下步驟：

1）查找函數中的所有生命周期，通過設置標志位是否置位來判斷設該生命期為A類生命期還是B類生命期；

2）執行圖著色寄存器分配方法的Renumber₁、build₁、coalesce₁、spill?cost₁、和simplify₁五個過程，為所有A類生命期分配lo-regs寄存器，得到未進行任何溢出操作的沖突圖G₁；

3）計算空閑lo-regs寄存器數m，如果所述沖突圖G_1?非空，則空閑lo-regs寄存器數m為0，如果所述沖突圖G_1?為空圖，則執行圖著色寄存器分配方法的select₁過程，并根據生成的寄存器分配方案計算空閑的lo-regs寄存器數m，并記錄空閑寄存器信息；

4）執行圖著色寄存器分配方法的Renumber₂、build₂、coalesce₂、simplify_2?、spill?code₂和select₂過程，為B類生命期分配hi-regs寄存器和m個空閑的lo-regs寄存器，并根據生成的分配方案計算空閑的hi-regs寄存器數量n，并記錄空閑寄存器信息；

5）執行圖著色寄存器分配方法的spill?code₁和select₁過程，如果select₁過程已經在步驟3）執行則結束所有步驟，如果沒有，則重復執行spill?code_1?、Renumber₁、build₁、coalesce₁、spill?cost₁、simplify_1???過程直到所述沖突圖G_1?為空，然后執行select₁過程為A類生命期生成寄存器分配方案；

Renumber₁、build₁、coalesce₁、spill?cost₁、simplify_1??、spill?code₁?、select₁、Renumber₂、build₂、coalesce₂、spill?cost₂、simplify_2?、spill?code₂和select₂過程均為圖著色寄存器分配方法的步驟；

所述圖著色寄存器分配方法包括如下步驟：

11）Renumber：在數據流分析的基礎上，找到函數中的所有生命期，并為其分配唯一的編號，其中一個生命期從一個變量的一次定值開始，到對該值的最后一次使用結束；

12)?build:建立沖突圖G，所述沖突圖G中的結點為生命期，邊則表示通過其相連的兩個生命期有沖突，不能為它們分配同一個寄存器；

13）coalesce：判斷是否需要合并生命期，如需要則通過合并生命期刪除不必要的復制語句，合并后返回，重新執行步驟12），如不需要合并，則執行步驟14）；

14）spill?cost：計算每個生命期的溢出代價；

15）simplify：對所述沖突圖G進行簡化，反復地檢查圖G，刪除G中度數小于可用寄存器數k的節點，刪除的同時將該節點壓入棧s；

16）spill?code：當所述沖突圖G中所有節點的度都大于等于k時，需要將溢出代價最小的生命期溢出，即刪除其節點，將其壓入棧s，并將其標記為溢出，溢出一個生命期之后返回執行步驟11）；

17）select：當所述沖突圖G為空時，將棧s中的生命期彈出，為其分配寄存器，并為標記為溢出的生命期插入溢出代碼；

所述lo-regs寄存器為短指令可尋址的寄存器，剩下的為所述hi-regs寄存器，所述標志位是否置位的標準為：將有A類指令引用的生命期設為置位，將只有B類指令引用的生命期設為不置位；

所述A類指令為一條指令最終生成的機器指令是長指令還是短指令取決于其分配到的寄存器；

所述B類指令為不論其寄存器操作數分配到哪個寄存器，其必然生成一條長指令，或者必然生成一條短指令。