[發(fā)明專利]指令調度方法及裝置

有效

• 申請?zhí)枺?/td>: 201210307180.9
• 申請日: 2012-08-24
• 公開（公告）號: CN102830954A
• 公開（公告）日: 2012-12-19
• 發(fā)明（設計）人: 朱浩;王東輝;洪纓;王德濱
• 申請（專利權）人: 北京中科信芯科技有限責任公司
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 北京億騰知識產權代理事務所 11309
• 代理人: 陳霽

1.一種指令調度方法，其特征在于，所述方法包括：

根據(jù)匯編指令建立匯編級數(shù)據(jù)流圖和匯編級控制流圖;

根據(jù)所述匯編級數(shù)據(jù)流圖找出偽相關指令，并根據(jù)所述匯編級控制流圖將可用的寄存器分配給所述偽相關指令，根據(jù)寄存器重新分配后的指令建立新的匯編級數(shù)據(jù)流圖；

在所述新的匯編級數(shù)據(jù)流圖中加入?yún)R編指令序，并從所述新的匯編級數(shù)據(jù)流圖中查找最佳路徑，根據(jù)所述最佳路徑進行指令調度。

2.如權利要求1所述的方法，其特征在于，所述最佳路徑是指最佳哈密爾頓路徑。

3.如權利要求1所述的方法，其特征在于，所述根據(jù)匯編指令建立匯編級數(shù)據(jù)流圖具體包括：

按序遍歷基本塊中的每條指令i，并逐個分析所述指令i的所有前驅指令p與所述指令i的關系；

當所述指令i和所述前驅指令p是連續(xù)存儲指令，或是有依賴關系的指令時，在所述匯編級數(shù)據(jù)流圖中添加從i到p的邊，其中，當所述指令i不是存儲指令并且寄存器的絕對依賴關系已經完全建立時，則所述匯編級數(shù)據(jù)流圖構建完成。

4.如權利要求1所述的方法，其特征在于，所述根據(jù)匯編指令建立匯編級控制流圖具體包括：

對匯編代碼建立關于謂詞寄存器的三值邏輯真值表；

通過基本塊內的跳轉目標地址或基本塊的標識來判斷函數(shù)中可能出現(xiàn)的循環(huán)體；

沿著分支指令進行有效路徑提取，根據(jù)所述有效據(jù)路徑標識對匯編級控制流圖進行邊著色，其中，當沿著分支指令進行有效路徑提取時，檢查所述分支指令的謂詞寄存器的當前值是否與真值表中的對應值沖突，并保存真值表的副本。

5.如權利要求1所述的方法，其特征在于，所述在新的匯編級數(shù)據(jù)流圖中加入?yún)R編指令序，并從所述新的匯編級數(shù)據(jù)流圖中查找最佳路徑，根據(jù)所述最佳路徑進行指令調度具體為：

在所述新的匯編級數(shù)據(jù)流圖中添加頭節(jié)點和尾節(jié)點；

對所述新的匯編級數(shù)據(jù)流圖中不存在數(shù)據(jù)相關的節(jié)點加入兩條邊；

逐個評估所述新的匯編級數(shù)據(jù)流圖中節(jié)點的并行性，查找出最佳路徑。

6.一種指令調度裝置，其特征在于，所述裝置包括：

建立單元，用于根據(jù)匯編指令建立匯編級數(shù)據(jù)流圖和匯編級控制流圖；

分配單元，用于根據(jù)所述匯編級數(shù)據(jù)流圖找出偽相關指令，并根據(jù)所述匯編級控制流圖將可用的寄存器分配給所述偽相關指令，根據(jù)寄存器重新分配后的指令建立新的匯編級數(shù)據(jù)流圖；

調度單元，用于在所述新的匯編級數(shù)據(jù)流圖中加入?yún)R編指令序，并從所述新的匯編級數(shù)據(jù)流圖中查找最佳路徑，根據(jù)所述最佳路徑進行指令調度。

7.如權利要求6所述的裝置，其特征在于，所述最佳路徑是指最佳哈密爾頓路徑。

8.如權利要求6所述的裝置，其特征在于，所述建立單元具體用于：

按序遍歷基本塊中的每條指令i，并逐個分析所述指令i的所有前驅指令p于所述指令i的關系；

當所述指令i和所述前驅指令p是連續(xù)存儲指令，或是有依賴關系的指令時，在匯編級數(shù)據(jù)流圖中添加從i到p的邊，其中，當所述指令i不是存儲指令并且寄存器的絕對依賴關系已經完全建立時，則所述匯編級數(shù)據(jù)流圖構建完成。

9.如權利要求6所述的裝置，其特征在于，所述建立單元具體用于：

對匯編代碼建立關于謂詞寄存器的三值邏輯真值表；

通過基本塊內的跳轉目標地址或基本塊的標識來判斷函數(shù)中可能出現(xiàn)的循環(huán)體；

沿著分支指令進行有效路徑提取，根據(jù)所述有效據(jù)路徑標識對匯編級數(shù)據(jù)流圖進行邊著色，其中，當沿著分支指令進行有效路徑提取時，檢查所述分支指令的謂詞寄存器的當前值是否與真值表中的對應值沖突，并保存真值表的副本。

10.如權利要求6所述的裝置，其特征在于，所述調度單元具體用于：

在所述新的匯編級數(shù)據(jù)流圖中添加頭節(jié)點和尾節(jié)點；

對所述新的匯編級數(shù)據(jù)流圖中存在數(shù)據(jù)相關的節(jié)點加入兩條邊；

逐個評估所述新的匯編級數(shù)據(jù)流圖中節(jié)點的并行性，查找出最佳路徑。