[發明專利]一種匯編級靜態路徑剖析方法及裝置

有效

• 申請號: 201310313989.7
• 申請日: 2013-07-24
• 公開（公告）號: CN103399741A
• 公開（公告）日: 2013-11-20
• 發明（設計）人: 朱浩;彭楚;應歡;王東輝;洪纓
• 申請（專利權）人: 中國科學院聲學研究所
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 北京億騰知識產權代理事務所 11309
• 代理人: 陳霽

技術領域

本發明涉及性能分析技術，尤其涉及一種匯編級靜態路徑剖析方法及裝置。?

背景技術

路徑剖析（Programs?Profiling）在性能分析領域占據十分重要的地位，它用于分析、統計應用程序中全部執行路徑以及各路徑的執行次數。這些性能數據被廣泛的應用在編譯優化等多項研究工作中。?

現有技術進行路徑剖析的方法較為統一，基本都是結合控制流圖（Control?Flow?Graph,CFG）分析向應用程序中插入樁代碼，最后通過回收、計算樁代碼統計的性能信息來得出各條路徑及執行次數。現有方案中，如處理無回邊（backedge）路徑時，Ball等人提出的過程內單變量剖析方法（Efficient?Path?Profiling,EPP）；處理環路路徑時，Tallam提出的近似剖析方法以及Roy等人在此基礎上提出的改進方法都取得了很好的效果。然而，當應用程序結構相對復雜、循環體較多時，這些方法仍有不足。歸其原因，不難發現它們均是從高層語言的行為級著手處理，并受限于語義分析前端以及目標處理器的指令功能，無法進一步擴展應用范圍。?

除此之外，現有剖析技術主要是基于動態分析實現，而進行動態分析時過分的依賴輸入激勵，這就導致剖析得出的路徑信息并不能全面反映程序的執行路徑信息。?

發明內容

本發明的目的是提供一種匯編級靜態路徑剖析方法，它不依賴于輸入?激勵，并通過動態組合、謂詞分析等有效地完成了對靜態路徑的剖析。?

為實現上述目的，一方面，本發明提供了一種匯編級靜態路徑剖析方法，該方法包括以下步驟：?

挖掘出匯編程序中全部的基礎閉環路徑，基礎閉環路徑是一個首、尾節點相同的環路，并且不允許出現其它環路；?

挖掘出匯編程序中全部的基礎路徑，基礎路徑是指從入口基本塊到出口基本塊的最簡路徑，在基礎路徑中不允許出現環路，而且不允許出現重復節點；?

組合基礎閉環路徑以及基礎路徑完成路徑統計；?

對組合后的路徑進行謂詞條件判斷。?

另一方面，本發明提供了一種匯編級靜態路徑剖析裝置，該裝置包括：?

第一計算單元，用于挖掘出匯編程序中全部的基礎閉環路徑；?

第二計算單元，用于挖掘出匯編程序中全部的基礎路徑；?

統計單元，用于組合基礎閉環路徑以及基礎路徑完成路徑統計；?

判斷單元，用于對組合后的路徑進行謂詞條件判斷。?

本發明提供的一種匯編級靜態路徑剖析方法及裝置實現簡單，不依賴于輸入數據激勵，從匯編級著手，基于動態組合挖掘全部可能存在的靜態路徑。?

附圖說明

圖1為本發明實施例提供的一種匯編級靜態路徑剖析方法流程圖；?

圖2（a）為一段匯編代碼示例；?

圖2（b）為圖2（a）相應的基本控制流圖；?

圖3為本發明實施例提供的一種匯編級控制流圖；?

圖4為本發明實施例提供的一種匯編級靜態路徑剖析裝置結構框圖。?

具體實施方式

下面通過附圖和實施例，對本發明的技術方案做進一步的詳細描述。?

在描述本發明實施例提供的一種匯編級靜態路徑剖析方法之前，需針對匯編級控制流圖作一下簡單介紹：?

假設存在一條途經節點i與j的控制路徑，其中節點j是除節點i以外全部其它節點的后必經節點，那么就稱節點i控制依賴（control?dependence）于節點j。控制依賴圖（Control?Dependence?Graph，CDG）是一個面向中間語言的有向無環圖（Directed?Acyclic?Graph，DAG），其中，邊集合描述了基本塊間的控制依賴關系；節點集合中的根節點、中間節點是由謂詞操作劃分出的基本塊，葉節點則一般是謂詞不敏感的基本塊。編譯器前端生成應用程序的控制流圖（control?flow?graph,CFG），而后端則根據分支和循環片段衍生出控制依賴子圖（control?dependence?sub?graph,CDSG）。然而，中間語言歷經代碼調度、代碼塊合并、指令映射等多遍操作后，謂詞相關操作被分布到多條指令甚至多個基本塊內，這增添了匯編級進行謂詞分析的難度。?