優(yōu)化的分類

• 機器無關優(yōu)化: 針對中間代碼
• 機器相關優(yōu)化: 針對目標代碼
• 局部代碼優(yōu)化: 單個基本塊范圍內的優(yōu)化
• 全局代碼優(yōu)化: 面向多個基本塊的優(yōu)化

常用的優(yōu)化方法

• 刪除公共子表達式
• 刪除無用代碼
• 常量合并
• 代碼移動
• 強度削弱
• 刪除歸納變量

方法一 刪除公共子表達式

公共子表達式

如果表達式x op y先前已被計算過，并且從先前的計算到現(xiàn)在，x op y中變量的值沒有改變，那么x op y的這次出現(xiàn)就稱為公共子表達式 (common subexpression)

例子

• B5基本塊

B5.png

B5.png

注：因為在B5中第一個4*i和4*j到第二個4*i和4*j，i和j的值并沒有改變，因此重復的4*i和4*j被刪除，a[t7]和a[10]分別被a[t6]和a[t8]代替。

B5.png

注：我們沿著B5的導入符逆流而上發(fā)現(xiàn)4*i的值在B2中已經計算過了，而且從B2的4*i到B5的4*i之間并沒有改變i的值。因此B5中的4*i還是公共子表達式。由于4*i的上一次計算是在另一個基本塊中進行，因此這個公共子表達式叫做全局公共子表達式。同理4*j也是全局公共子表達式。因此刪除這兩個公共表達式，在使用到t6和t8時用t2和t4代替。

B5.png

B5.png

注：經過變換另一個B5中的全局公共子表達式就顯露出來了，它就是a[t2]，a[t2]在基本塊B2中已經被計算過了。從B2到B5并沒有對a[t2]進行重新賦值，也沒有對數(shù)組元素重新賦值，因此a[t2]是全局公共子表達式，同理a[4]也是全局公共子表達式。因此可以將這兩個公共子表達式進行刪除，在使用a[t2]和a[t4]的時候我們可以使用t3和t5進行代替，由于t9是臨時變量因此t9也被刪除或被t5代替。

B5.png

• B6基本塊

B6.png

注：4*i和4*n都是局部公共子表達式，而這兩表達式已經在B1和B2中已經被計算過，因此它們是全局公共子表達式，可以將B6中的4條子表達式都刪除。其中4*i被t2替換，4*n被t1替換。

B6.png

注：B6中的a[2]在B2中已經被計算過與前面B5的情況類似，a[2]也是一個全局公共子表達式。

B6.png

注：事實上a[t1]在B1計算之后，從B1到B6之前有可能進入B5，而在B5中有對數(shù)組元素賦值，此時t2和t4有可能等于t1，因此B5中的操作有可能已經改變a[t1]的值。因此將a[t1]作為公共子表達式是不穩(wěn)妥的。

B6.png

B6.png

B6.png

方法二 刪除無用代碼

• 復制傳播
  復制傳播 ：在復制語句x = y之后盡可能地用y代替x，復制傳播給刪除無用代碼帶來機會。常用的公共子表達式消除算法和其它一些優(yōu)化算法會引入一些復制語句(形如x = y的賦值語句）

例.png

• 無用代碼(死代碼Dead-Code)：其計算結果永遠不會被使用的語句

例.png

例.png

方法三 常量合并(Constant Folding)

如果在編譯時刻推導出 一個表達式的值是常量 ，就可以使用該常量來替代這個表達式。該技術被稱為常量合并

例： l = 2*3.14*r

例.png

方法四 代碼移動(Code Motion)

這個轉換處理的是那些 不管循環(huán)執(zhí)行多少次都得到相同結果的表達式(即循環(huán)不變計算，loop-invariant computation)，在進入循環(huán)之前就對它們求值。

例.png

循環(huán)不變計算的相對性：對于多重嵌套的循環(huán)，循環(huán)不變計算是相對于某個循環(huán)而言的?？赡軐τ诟油鈱拥难h(huán)，它就不是循環(huán)不變計算，例：

for(i = 1; i<10; i++)
for( n=1; n<360/(5*i); n++ )
{ S=(5*i)/360*pi*r*r*n; ... }

方法五 強度削弱(Strength Reduction)

用較快的操作代替較慢的操作，如用加代替乘

例.png

循環(huán)中的強度削弱
歸納變量：對于一個變量x，如果存在一個正的或負的常數(shù)c使得每次x 被賦值時它的值總增加c，那么x就稱為歸納變量(Induction Variable)

例.png

例.png

刪除歸納變量

例.png

例.png

注：如何識別公共子表達式，無用代碼可參考基本塊的優(yōu)化