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

有效

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

技術領域

本發明涉及一種編譯技術，尤其涉及一種針對混合長度指令集的寄存器分配方法。

背景技術

嵌入式系統常采用RISC架構，其指令集一般為定長指令集，即只具有單一長度的指令。指令長度一般為整數個字節，例如，16位指令，32位指令。較長的指令長度可以編碼更多的操作數，尋址更多的寄存器，或者可使用更大的立即數等，故一般具有更好的性能；而較短的指令長度可以使得編譯生成的可執行程序更小。為了在具有長指令高性能的同時具有短指令的高代碼密度，現代的RISC處理器開始采用兩種或者兩種以上不同長度指令混合編碼的指令集。例如，ARM的thumb2指令集和中天微公司的cskyv2指令集都是16位與32位指令混合編碼的指令集（以下簡稱“混編指令集”）。

在混編指令集中，短指令相比長指令而言，尋址的操作數個數少，可編碼的立即數范圍小，或者單個地址只可使用部分寄存器。例如，在cskyv2指令集中，長指令可使用R0~R31全部共32個通用寄存器，而絕大多數短指令只可使用R0~R15共16個通用寄存器；長指令一般具有3操作數，而短指令最多只有2操作數。短指令在功能上是長指令的一個子集。通常，編譯器按照長指令的功能來生成匯編指令，而匯編器生成機器指令時，會根據指令的類型和其操作數來決定生成長指令還是短指令。

以cskyv2為例，如果一條指令的某個寄存器操作數被分配了R16~R31的寄存器，那么該指令將生成一條長指令（個別指令除外，下外將介紹）；但一條指令即使只使用R0~R15的寄存器，它也并不一定生成短指令，因為它可能使用了超出短指令可編碼范圍的立即數，或者使用了3個不同的操作數等等。以cskyv2為例，如果一條指令的某個寄存器操作數被分配了R16~R31的寄存器，那么該指令將生成一條長指令（個別指令除外，下外將介紹）；但一條指令即使只使用R0~R15的寄存器，它也并不一定生成短指令，因為它可能使用了超出短指令可編碼范圍的立即數，或者使用了3個不同的操作數，等等。如果一條指令最終生成的機器指令是長指令還是短指令取決于其分配到的寄存器（以下簡稱?A類指令）；反之，如果不論其寄存器操作數分配到哪個寄存器，其必然生成一條長指令，或者必然生成一條短指令（以下簡稱?B類指令）。如何以較小的代價使得所有的A類指令最終生成的機器指令為短指令，是技術人員需要克服的難點。

發明內容

針對上述技術難點，本發明的提出一種針對混合長度指令集的寄存器分配方法。

為了解決上述技術問題，本發明的技術方案如下：

一種針對混合長度指令集的寄存器分配方法，包括如下步驟：

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₁過程已經在