[其他]通過雙色布石進行寄存器分配和指定

無效

• 申請號: 86107764
• 申請日: 1986-11-14
• 公開（公告）號: CN86107764A
• 公開（公告）日: 1987-07-01
• 發明（設計）人: 阿施法·阿布杜里曼·穆施;卡爾·馬克斯·施姆普福
• 申請（專利權）人: 國際商用機器公司
• 主分類號: G06F12/02
• 分類號: G06F12/02
• 代理公司: 中國國際貿易促進委員會專利代理部
• 代理人: 余剛

1、一種用于分配寄存器并優化所述分配的方法，是在一個無向量或向量處理器中將源代碼編譯成可執行代碼的優化階段里，對不含“基本程序塊”的分支的代碼區域進行優化，每個基本程序塊具有定義計算的語句，

每個處理器包括用于存貯可執行代碼序列和數據的存貯器，以及用于訪問所述存貯器并執行任何被訪問代碼的裝置；存貯器被設計為兩級模式，包括有限數量P的寄存器和一個相對無限的內存貯器，所述寄存器的訪問時間快于內存貯器，

這些步驟的特征在于：

(a)確定一個基本程序塊的數據相關圖特性；

(b)根據該基本程序塊中的全部計算產生對p個寄存器中的q個的分配和指定，其步驟為

(b1)沿葉-根節點方向，選擇具有最大后繼節點數(支配者)的圖的節點集合；

(b2)確定上述所選集合的每個緊隨后繼點的覆蓋費用，為該集合中覆蓋費用最小的緊隨后繼點指定一個寄存器；以及

(b3)在缺少任何可用可分配寄存器的情況下，將由計算在該節點產生的中間或最后結果寫到內存貯器，以后根據需要將其裝回可用寄存器。

2、一種在無向量或向量處理器中將源代碼編譯成可執行代碼期間分配并優化寄存器分配的方法，

源代碼包括不具分支的稱為“基本程序塊”的代碼區域，每個基本程序塊具有定義計算的語句，

每個處理器包括用于存貯可執行代碼序列和數據的存貯器，以及用于訪問所述存貯器并執行任何被訪問代碼的裝置;存貯器被設計為兩級模式，包括有限數量P的寄存器和一個相對無限的內存貯器，所述寄存器的訪問時間快于對內存貯器的訪問。

其步驟的特征在于：

（a）確定每個基本程序塊的數據相關圖特性;

（b）根據每個基本程序塊中的全部計算，對P個寄存器中的q個產生局部寄存器分配和指定，其步驟為

（b1）沿葉-根的節點方向，選擇具有最大后繼節點數（支配者）的圖的節點集合;

（b2）確定上述所選集合的每個緊隨后繼節點的覆蓋費用，并為該集合中覆蓋費用最小的緊隨后繼點指定一寄存器;以及

（b3）在缺少任何可用可分配寄存器的情況下，將由計算在該節點產生的中間或最后結果寫到內存貯器，以后根據需要將其裝回一可用寄存器。

（c）在基本程序塊的流程圖式表示上進行活變量分析，并在（p-q）個剩余寄存器中相應產生全程寄存器分配和指定，假定在基本程序塊的流程圖中所表示的循環是最有意義的優化實體。