源程式最佳化程式

源程式最佳化程式

源程式,是指未經編譯的,按照一定的程式設計語言規範書寫的,人類可讀的文本檔案。源程式最佳化程式是指對源程式的空間代價和時間代價進行最佳化的程式。源程式最佳化程式進行性能最佳化一般有兩個方向:選擇更合適的算法以及數據結構;讓編譯器或者解釋器能夠更好對你的代碼進行最佳化。

基本介紹

  • 中文名:源程式最佳化程式
  • 外文名:source program optimizer
  • 學科:計算機
  • 最佳化方向:時間、空間
  • 方法:算法、數據結構、代碼
  • 領域:程式設計
簡介,代碼最佳化,代碼最佳化過程,途徑,控制流分析,數據流分析,消除算法,疊代算法,收斂性分析,後向分析,

簡介

源程式最佳化程式是指對源程式的空間代價和時間代價進行最佳化的程式。最佳化是把程式變換為在時間、空間上改進了的而執行效果與原程式等價的高效執行程式的過程。其目標是設法從待最佳化程式中消除重複計算。最佳化的基礎是控制流分析、數據流分析。 可分為局部或全局的;依賴於機器或不依賴於機器;依賴於語言或不依賴於語言的最佳化。

代碼最佳化

所謂代碼最佳化是指對程式代碼進行等價(指不改變程式的運行結果)變換。程式代碼可以是中間代碼(如四元式代碼),也可以是目標代碼。等價的含義是使得變換後的代碼運行結果與變換前代碼運行結果相同。最佳化的含義是最終生成的目標代碼短(運行時間更短、占用空間更小),時空效率最佳化。原則上,最佳化可以在編譯的各個階段進行,但最主要的一類是對中間代碼進行最佳化,這類最佳化不依賴於具體的計算機
在不改變程式運行效果的前提下,對被編譯的程式進行等價變換,使之能生成更加高效的目標代碼。

代碼最佳化過程

等價:不改變程式執行效果;
變換:引起程式形式上的變動。

途徑

改進、提高程式途徑
1) 改進算法;
2) 在源程式級上等價變換;
3) 充分利用系統提供的程式庫;
4) 編譯時最佳化等。

控制流分析

控制流分析(Control flow analysis)簡稱CFA,是一種確認程式控制流程的靜態代碼分析技術。控制流程會以控制流圖來表示。對於函式程式語言及面向對象程式設計,CFA都是指計算控制流程的算法。
控制流分析一詞最早是由Neil D. Jones及Olin Shivers[2]開始使用。對於像是Scheme之類有高階函式的程式語言,不一定可以會程式中直接看出函式呼叫的目標,例如以下的程式片段
(lambda (f) (f x))
根據上述程式無法確認程式f是指什麼,此情形下的控制流分析需考慮何時會執行此程式碼,及當時的傳入值。抽象釋義、約束補償及型別系統都可以用來進行控制流分析。

數據流分析

數據流分析是一種用於收集電腦程式在不同點計算的值的信息的技術。一個程式的控制流圖(control flow graph, CFG)被用來確定對變數的一次賦值可能傳播到程式中的哪些部分。這些信息通常被編譯器用來最佳化程式。數據流分析的一個典型的例子就是可到達定義的計算。進行數據流分析的最簡單的一種形式就是對控制流圖的某個節點建立數據流方程,然後通過疊代計算,反覆求解,直到到達不動點。通過數據流分析,可以不必實際運行程式就能夠發現程式運行時的行為,這樣可以幫助大家理解程式。數據流分析被用於解決編譯最佳化、 程式驗證、調試、測試、並行、向量化和並行編程環境等問題。以下是數據流分析一些常見算法:

消除算法

消除算法通過利用流圖的結構屬性減少解決數據流問題所需要的大量工作。通過連續的套用圖的轉換使流圖歸約到一個點, 圖的轉換就是使用圖的分析或圖的分裂去分析區間以獲得一個派生圖。在一個區間內,數據流的屬性是由區間內頭節點的數據流的屬性來確定的。 這樣可以延遲替代聯立方程中的一些值。對於單向流問題,這些方法典型的複雜度為O(N) ,這裡N是在歸約圖序列中節點的總數。儘管它們已經被用於解決一類受限制的雙向問題,但消除算法不能被擴展到一般的雙向數據流問題。

疊代算法

最常用的用於求解數據流方程的方法是使用疊代算法。它由每個塊的近似入口狀態信息出發。然後套用轉移函式基於這些入口狀態信息計算出口狀態信息。然後,使用連線運算符更新入口狀態信息。最後兩步將一直進行下去直至到達不動點: 即此時入口狀態信息和出口狀態信息都不再改變。
一個基本的求解數據流方程的算法是循環疊代算法:
fori← 1 toN
初始化節點i
while (有集合發生了改變)
fori← 1 toN
重新計算節點i處的集合

收斂性分析

為了可用性的要求,疊代算法應該可以真正到達不動點。這可以通過對狀態的值域的聯合,轉移函式以及連線運算符加上限制條件來保證。
值域應該是有界的且有序。(比如,不存在一個無限的遞增鏈
< ...)。轉移函式和連線運算符應該是單調的。單調性保持了對值的每次疊代操作要么與之前一致,要么會變大,而有界性保證了它不會無限增大下去。因此最終我們會到達一個狀態對於所有的x,有T(x) = x,此時即是不動點。

後向分析

活性變數分析計算每個程式點上的那些在重新定義前可以被潛在的使用的變數。這個的典型套用是用於死碼刪除,移除那些給變數賦值但之後變數未被使用的語句。塊的入口狀態是在上個塊的末端仍然具有活性的變數的集合。

相關詞條

熱門詞條

聯絡我們