將條件分支轉換爲跳轉的優化過程

在優化編譯器中，冗餘代碼可以被不同的算法多次檢測和消除，如值編號，稀疏條件常量傳播等。在這種情況下，我有興趣檢測多餘的分支。假設目標代碼是將條件分支轉換爲跳轉的優化過程

block1: 
    cmp r1, r2 
    jne block3 

block2: 
    cmp r1, r2 
    je block4 

block3: 
    ...  
block4: 
    ...  
...

在這種情況下，如果控制達到block2這意味着r1和r2是相等的，所以je block4可以通過jmp block4代替。此外，如果在block2中代替jne block4，那麼我們可以完全刪除je。

然後，我的問題是，什麼優化過程趕上這樣的代碼？我想價值編號可以擴展到解決這個問題，但從未在參考書目中看到它，所以也許有更好的方法。

編輯：修正第一跳，它說je block3應該說jne block3

來源

2014-09-26 melkyades

那麼，假設沒有其他分支到從其他地方塊2，編譯器的布爾傳播應該趕上。當然，根據編譯器的不同，其他各個階段也可以進行優化。

根據布爾道具算法，有什麼事情發生的是塊3舉辦的「R1！= R2」，將獲得傳播到它下面所有的塊數據流量值。塊2將類似地具有「R1 == R2」的值，該值也將被傳播到隨後的塊（根據數據流），從而在其途中消除死分支。

希望這會有所幫助。

來源

2014-09-26 21:02:58 drivingon9

我不知道優化過程的名稱是完全標準化的，我不能在此刻找到我的Muchnick副本，但在我去年工作的編譯器，你所描述的情況將分兩個階段進行檢測 - 一次優化過程會檢測到二次比較是多餘的，並將其刪除，隨後的一次通過將檢測到相同的跳轉不需要有條件。

但並非每個編譯器都會執行此類優化。

來源

2014-09-26 21:03:21

優化通常發生長時間你到組裝前，而是某種形式的中間表示的。

不同形式的IR的變化，但是一種典型的方面是它們對無限組寄存器進行操作，而不是寄存器的內容，使得每個寄存器不能被改變，只是初始化一次。（如果您需要可變變量，您需要通過alloca指針堆棧然後load/store通過它。第一個也是最困難的優化階段是從基於alloca的轉換爲基於SSA的，以便所有其他優化，如這其中，可以做到）

此示例使用LLVM IR。

define void @func2(i32 %r1, i32 %r2) { 
block1: 
    %0 = icmp ne i32 %r1, %r2 
    br i1 %0, label %block3, label %block2 

block2:           ; preds = %block1 
    %1 = icmp eq i32 %r1, %r2 
    br i1 %1, label %block4, label %block3 

block3:           ; preds = %block2, %block1 
    unreachable 

block4:           ; preds = %block2 
    unreachable 
}

它現在應該是很直觀的認爲的%1定義可以%1 = xor i1 %1, true被替換（這是一個布爾not的樣子），然後不斷可以在那條通向block2鞋底邊緣傳輸完畢。

來源

2014-09-26 22:00:08 o11c

將條件分支轉換爲跳轉的優化過程

回答

相關問題