[發明專利]匯編級跨文件調度框架的構建方法

有效

• 申請號: 201310697997.6
• 申請日: 2013-12-18
• 公開（公告）號: CN103645930B
• 公開（公告）日: 2017-03-08
• 發明（設計）人: 朱浩;彭楚;王東輝;洪纓
• 申請（專利權）人: 中國科學院聲學研究所
• 主分類號: G06F9/45
• 分類號: G06F9/45;G06F9/46
• 代理公司: 北京億騰知識產權代理事務所11309
• 代理人: 陳霽

1.一種匯編級跨文件調度框架的構建方法，其特征在于，包括以下步驟：?

構建匯編級數據依賴圖ADDG，判斷、分析并描述匯編級寄存器內指令之間的數據依賴關系，并且利用偽相關檢測算法進行寄存器重新分配，避免臨時寄存器的復用帶來數據間的偽相關；以及?

構建匯編級控制依賴圖ACFG，控制數據依賴分析，并添加控制依賴圖CDG中刪除冗余信息的特性來輔助后續調度，構建基于多叉樹結構的謂詞分析方法，通過遍歷控制流圖，跨基本塊的分析條件判斷相關指令間的數據依賴關系來完成謂詞分析；以及?

構建匯編級程序調用圖APCG，組織管理全局源文件間的關系；?

所述APCG中每個節點對應一個所述ACFG，所述ACFG中每個節點可映射到一個匯編級基本塊，所述ACFG中每個節點對應一個獨立的ADDG。?

2.如權利要求1所述的匯編級跨文件調度框架的構建方法，其特征在于，所述ADDG包括數據依賴檢測算法、ADDG創建算法以及所述偽相關檢測算法，其中，?

所述數據依賴檢測算法用于判斷兩條指令之間為何種所述數據依賴關系；?

所述ADDG創建算法反映了匯編級基本塊內全部指令之間為何種所述數據依賴關系，并表現出來；?

所述偽相關檢測算法用于寄存器重新分配，避免偽相關帶來的數據依賴關系。?

3.如權利要求1或2所述的匯編級跨文件調度框架的構建方法，其特征在于，所述ADDG是一個有向無環圖DAG。?

4.如權利要求1所述的匯編級跨文件調度框架的構建方法，其特征在于，所述ACFG是一個有向有環圖DCG。?

5.如權利要求1所述的如權利要求1所述的匯編級跨文件調度框架的構建方法，其特征在于，所述構建基于多叉樹結構的謂詞分析方法是通過遍歷控制流圖，跨基本塊的分析條件判斷相關指令之間的數據依賴關系來完成謂詞分析。?

6.如權利要求1或2所述的匯編級跨文件調度框架的構建方法，其特征在于，所述寄存器重新分配包括以下步驟：?

函數棧框架分析，首先分析程序的棧框架，并統計函數內即將用到的同類寄存器；以及?

路徑分析，分析后文將介紹的ACFG統計當前匯編級基本塊的全部前驅動點對同類寄存器的使用情況；以及?

判斷所述路徑分析中同類寄存器是否全部被使用。?

7.如權利要求6所述的匯編級跨文件調度框架的構建方法，其特征在于，所述函數棧框架分析用于保存函數內使用到的臨時寄存器。?

8.如權利要求6所述的匯編級跨文件調度框架的構建方法，其特征在于，若所述路徑分析中同類寄存器全部被使用，則判斷修改棧結構時導致的指令帶來的影響是否小于對依賴關系的減少。?

9.如權利要求6所述的匯編級跨文件調度框架的構建方法，其特征在于，若所述路徑分析中同類寄存器未全部被使用，則任意選擇一個未使用的寄存器進行重新分配。?

10.如權利要求8所述的匯編級跨文件調度框架的構建方法，其特征在于，若所述修改棧結構時導致的指令帶來的影響小于對依賴關系的減少，則重新進行分配，否則放棄分配。?

11.如權利要求1所述的匯編級跨文件調度框架的構建方法，其特征在于，構建所述APCG的步驟包括：?

前端分析過程中收集全部的函數，并創建所述APCG的點集合；以及?

順序分析點集元素對應的匯編指令片段，分析其中的函數調用指令目標?地址，并在點元素之間添加邊；以及?

生成未經邊冗余刪除的APCG。?

12.如權利要求1或11所述的匯編級跨文件調度框架的構建方法，其特征在于，所述APCG是一個DCG。?