無分支程式碼 在

關於 無分支程式碼

條件判斷概念介紹了jcc，這是用來依據條件分支的指令家族。 jcc只有在條件成立時，才會把執行流程轉移到程式中的另一個位置。

不過，現代 CPU 速度很快，能平行執行許多指令。 若為了等 CPU 在執行期檢查某個條件而讓所有工作停擺，代價實在太高。

因此，CPU 內部其實並不會停下來等。 它會用分支預測器猜測條件的結果，然後開始_預測性地_執行猜中的路徑。

如果猜對了，執行流程就會像沒有分支一樣繼續下去。 但如果猜錯了，CPU 就必須_丟棄在預測路徑上已完成的工作_，改從正確的路徑重新開始。

這稱為分支預測錯誤，代價很高，會造成延遲。

當某個分支不容易預測時，這些預測錯誤就會累積起來。 在這種情況下，有時最好完全避開分支，讓同一組指令無論條件為何都照樣執行。 不用jcc就能在值之間做選擇的程式碼，稱為無分支程式碼。

有幾種方式可以組織程式碼，讓分支發生的頻率降低，或讓現有的分支更容易預測。 特別是 x86-64 提供了兩個指令家族，常用來撰寫無分支程式碼。

條件搬移

cmovcc 指令家族只有在特定條件成立時，才會把來源運算元複製到目的運算元。 否則，目的運算元維持不變。

cc後綴的命名方式與jcc相同，意義也一樣：

規則和jcc類似：

1. l和g用於有號比較；b和a用於無號比較。
2. 在後綴加上e代表包含相等的情況。
3. 加上n會將條件取反。
4. 另外還有一些變體，是根據旗標是否設置來判斷。 例如cmovz和cmovc。

來看看求有號整數絕對值的例子：該整數放在rdi，結果以rax回傳。 用jcc撰寫時，這個函式會在其中兩條路徑中選擇一條：

abs_branch:
    mov rax, rdi
    cmp rax, 0
    jge .done
    neg rax
.done:
    ret

改用cmovcc撰寫時，兩個候選值都會無條件計算出來，再由條件搬移挑選其中一個：

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi
    cmp rdi, 0
    cmovge rax, rdi    ; if rdi >= 0, rax = rdi
                       ; otherwise rax stays = -rdi
    ; now rax = abs(rdi)
    ret

無分支版本永遠執行同一組指令。 沒有jcc讓分支預測器去猜。

cmovcc的目的運算元必須是暫存器。 來源可以是暫存器或記憶體位置，但不能是立即值。

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi. `neg` sets SF = 1 if the result is negative
    cmovs rax, rdi     ; if SF = 1 (i.e., rax < 0), replace rax with rdi
                       ; otherwise rax stays = -rdi, which is non-negative
    ; now rax = abs(rdi)
    ret

條件設置

setcc 指令家族會在特定條件成立時，把目的運算元設為1，否則設為0。 目的運算元一律是_8 位元運算元_。

cc後綴的命名方式與jcc和cmovcc相同。 例如，setz會在ZF == 1時把目的運算元設為1，否則設為0。

由於目的運算元只有 8 位元，當需要更寬的值時，通常會在setcc之後接一個movzx：

cmp rdi, rsi
setg al             ; al = 1 if rdi > rsi (signed), 0 otherwise
movzx eax, al       ; eax (and rax) = 1 or 0, with the upper bits cleared

這是把比較結果轉成整數0或1的常見慣用寫法。

何時該使用無分支程式碼

無分支程式碼不一定比有分支的程式碼快。 當某個分支非常容易預測時，分支預測器幾乎每次都猜對，jcc基本上不花什麼成本。 用無分支程式碼取代這種分支反而更慢，因為它總是會執行兩個候選計算。

迴圈計數器就是最典型的例子。 看看下面這個函式：它會從rdi開始，加總rsi個 64 位元整數：

sum_array:
    xor rax, rax
.loop:
    add rax, [rdi]
    add rdi, 8
    dec rsi
    jnz .loop          ; taken on every iteration except the last
    ret

這正是分支預測器最擅長處理的模式，所以無論sum_array處理多少個元素，這個分支基本上不花成本。

當分支難以預測，或無論輸入為何都必須維持穩定時間時，無分支程式碼才會帶來好處。