在各種編程語言里,邏輯運算符都是要短路的。
以C語言為例:
if (p && p->x > 0) p->x++;
當指針p是NULL的時候,對成員變量p->x的讀寫會導致段錯誤,所以如果&&之前的條件p是NULL就要把後面的p->x跳過去。
這樣才能保證代碼的正常運行。
如果語言本身不支持邏輯運算符的短路,那麼代碼就只能這麼寫了:
if (p) {
if (p->x > 0) p->x++;
}
要多寫一個if條件。
邏輯運算符的結果只有0或1兩種。
在編程里,邏輯運算符既可以作為if / while / for的條件表達式,還可以參與普通運算。
if (i > 0 && j > 1 && k > 2) return -1; // 條件表達式
n = i > 0 && j > 1 && k > 2; // 普通運算
在對邏輯運算符進行優化時,必須同時考慮這兩種情況。
第2種情況下,如果邏輯運算符在計算前2個條件時短路了,必須把計算結果寫入最後一個邏輯運算符對應的臨時變量。
最後一個邏輯運算符的計算結果,才是整個表達式的結果,也是對n賦值的結果。
如果只是在if語句里作為條件表達式,邏輯運算的結果不需要寫到臨時變量里,直接根據比較結果跳轉到對應的分支就可以了。
賦值運算的語法樹
第2種情況的語法樹如圖,參與賦值運算的是第2個&&對應的臨時變量。
如果在i > 0 或 j > 1時短路的話,它們設置的是第1個&&的值:編譯器在短路跳轉時必須給第2個&&設置運算結果,否則之後的n = ...的結果就不對了。
在給邏輯運算符生成中間代碼的時候,實際上並不知道它的結果以後會被怎麼使用[捂臉]
從上圖中也可以看出=號在更上面(if也是在更上面),實際上,在處理&&運算符時只能看到它的2個條件表達式,看不到更上層的程序邏輯。
if條件的語法樹
如果硬要去看更高層的邏輯,就會破壞模塊的封裝性,讓遍歷語法樹生成中間代碼的代碼變得複雜、難看。
scf框架在這裡的處理是:
1,先給所有邏輯運算符的臨時變量設置上結果,把進一步的優化放到以後。
if的情況
最初的中間代碼是這樣的,可以看到每個cmp或teq運算之後都緊跟着setcc。
其中cmp是比較大小,結果可以是>、==、<、>=、<=、!=。
teq是比較是不是0,結果只有2種:== 0,!= 0。
賦值的情況
在有邏輯運算符的情況下,在cmp之後必然跟着teq去判斷邏輯結果是不是0。
例如上圖中的:
cmp i, 0
setgt v_8_16/&&
jle : teq v_8_16/&&
跳轉的目標代碼是:
teq v_8_16/&&
setnz v_8_25/&&
jz : assign v_8_6/n; v_8_25/&&
數字表示的是行列號,v_8_16/&&表示第8行第16列的&&運算符對應的臨時變量。
可以看出,在最初的中間代碼里,邏輯運算符並沒有“真正的短路”:雖然跳過了第2個比較條件,但並沒有跳過邏輯運算。
之所以這樣,就是因為(生成中間代碼時)沒法確定邏輯結果接下來還有沒有用。
既然沒法確定,編譯器就只能先當它有用:代碼里遇到這種情況,是一定會做保守處理的。
所以說,不管是程序員還是數學家,一般都是悲觀主義者[捂臉]
2,在跳轉優化時,對這個問題進一步的優化。
如果一個跳轉的目標位置是一個絕對跳轉,就可以把它優化成跳轉到這個絕對跳轉的目標位置。
if a jcc's destination is a jmp, then optimize its destination to the jmp's.
這是對跳轉的基本優化。
實際上,如果跳轉之前對邏輯結果設置了false,而跳轉的目標又是檢測這個結果的話,那麼檢測結果也是false[呲牙]這是跳轉優化的另一條規則。
所以說,在cmp觸發了jle (<=) 的情況下,那麼它倆之間的setgt (>) 就肯定是0:
進而導致目標位置的teq也是0,
進而導致目標位置的setnz也是0,
進而導致目標位置的jz被觸發,
所以,jle的地址就是jz的地址!
但在jle之前要把setnz的目標變量也設置一下,使用的設置指令是setgt:與最初觸發跳轉的條件一致。
跳轉優化之後的中間代碼
從上圖可以看出,經過跳轉優化之後,測試邏輯結果的teq運算消失了,與teq對應的jz跳轉也消失了:
邏輯運算符被短路到了接下來的賦值運算。
賦值運算只使用最後一個臨時變量v_8_25。
對中間臨時變量v_8_16的設置是多餘的,接下來的問題是怎麼消除它。
如果邏輯運算只是作為if的條件的話,那麼最後一個邏輯結果也是不需要的。
3,基於活躍變量分析的優化,
算術運算會使用最後一個邏輯結果的臨時變量,if條件不使用任何邏輯結果的臨時變量,這在臨時變量的活躍度上可以體現出來。
把不活躍的臨時變量從DAG上去掉就行了。
最終的優化結果
對n的賦值運算只使用臨時變量v_8_25,可以看出它是前面基本塊的出口活躍變量,被保留了下來。
如果是if條件,因為所有的臨時變量都不活躍,在DAG優化之後就只剩下比較和跳轉了[呲牙]
如下圖:
if最終的圖
上圖是if條件的最終的圖,下圖是跳轉優化之後、DAG優化之前的圖。
可以看到,所有的setgt都被去掉了。
if之前的圖