Elágazás nélküli kód ebben a kurzusban:

A(z) Elágazás nélküli kód fogalomról

A feltételes utasítások fogalom bemutatja a jcc-t, azt az utasításcsaládot, amely feltételtől függően ágazik el. Egy jcc csak akkor adja át a végrehajtást a program egy másik pontjára, ha a feltétele teljesül.

A modern CPU-k azonban gyorsak, és sok utasítást képesek párhuzamosan végrehajtani. Túl költséges lenne leállítani minden munkát, amíg a CPU egy feltétel futásidejű ellenőrzésére vár.

Ezért a CPU belül nem vár. Egy elágazás-előrejelzőt használ, hogy megtippelje egy feltétel kimenetelét, és elkezdi spekulatívan végrehajtani a megjósolt útvonalat.

Ha az előrejelzés helyes, a végrehajtás úgy folytatódik, mintha nem is lenne elágazás. Ha viszont az előrejelzés téves, a CPU-nak el kell dobnia a megjósolt útvonalon végzett munkát, és újra kell kezdenie a helyes úton.

Ezt elágazás-előrejelzési hibának nevezik, és költséges, mert késleltetéssel jár.

Amikor egy elágazást nehéz előrejelezni, ezek a hibák összeadódnak. Ilyen esetekben néha jobb teljesen elkerülni az elágazást, hogy ugyanazok az utasítások hajtódjanak végre a feltételtől függetlenül. Az olyan kódot, amely jcc nélkül választ az értékek között, elágazásmentesnek nevezik.

Többféleképpen is felépíthető a kód úgy, hogy ritkábban ágazzon el, vagy hogy a meglévő elágazásai kiszámíthatóbbak legyenek. Az x86-64 különösen két utasításcsaládot kínál, amelyeket gyakran használnak elágazásmentes kód írásához.

Feltételes mozgatások

A cmovcc utasításcsalád csak akkor másolja a forrásoperandust a céloperandusba, ha egy adott feltétel teljesül. Ellenkező esetben a cél változatlan marad.

A cc utótag ugyanazt az elnevezést követi, mint a jcc esetében, ugyanazzal a jelentéssel:

A szabályok hasonlóak a jcc-hez:

1. Az l és a g az előjeles összehasonlításokhoz használatos; a b és az a az előjel nélküliekhez.
2. Ha egy utótaghoz hozzáadjuk az e-t, az az egyenlőséget is magában foglalja.
3. Az n hozzáadása tagadja a feltételt.
4. Vannak olyan változatok is, amelyek a beállított jelzőre hivatkoznak. Például a cmovz és a cmovc.

Tekintsük egy rdi-ben lévő előjeles egész szám abszolút értékét, amelyet rax-ban adunk vissza. jcc-vel megírva a függvény két útvonal közül választ:

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

cmovcc-vel megírva mindkét lehetséges értéket feltétel nélkül kiszámítjuk, és a feltételes mozgatás választ közülük egyet:

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

Az elágazásmentes változat mindig ugyanazokat az utasításokat hajtja végre. Nincs olyan jcc, amit az előrejelzőnek meg kellene tippelnie.

Egy cmovcc céloperandusa csak regiszter lehet. A forrás lehet regiszter vagy memóriabeli hely, de nem lehet azonnali érték.

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

Feltételes beállítás

A setcc utasításcsalád a céloperandust 1-re állítja, ha egy adott feltétel teljesül, egyébként pedig 0-ra. A cél mindig 8 bites operandus.

A cc utótag ugyanazt az elnevezést követi, mint a jcc és a cmovcc esetében. Például a setz a célt 1-re állítja, ha ZF == 1, egyébként pedig 0-ra.

Mivel a cél 8 bites, gyakori, hogy a setcc-t egy movzx követi, amikor szélesebb értékre van szükség:

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

Ez egy gyakori idióma arra, hogy egy összehasonlítás eredményét 0 vagy 1 egész számmá alakítsuk.

Mikor érdemes elágazásmentes kódot használni

Az elágazásmentes kód nem mindig gyorsabb az elágazásokat használó kódnál. Amikor egy elágazás jól előrejelezhető, az előrejelző szinte mindig helyesen tippel, és a jcc gyakorlatilag semmibe sem kerül. Az ilyen elágazást helyettesítő elágazásmentes kód lassabb, mert mindig mindkét lehetséges számítást végrehajtja.

A ciklusszámláló a klasszikus példa. Vegyünk egy függvényt, amely rsi darab 64 bites egész számot ad össze, rdi-től kezdve:

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

Ez pontosan az a fajta minta, amelyet az elágazás-előrejelzők jól kezelnek, így az elágazás gyakorlatilag ingyenes, függetlenül attól, hogy a sum_array hány elemet dolgoz fel.

Az elágazásmentes kód akkor térül meg, amikor az elágazást nehéz előrejelezni, vagy amikor a bemenetektől függetlenül következetes időzítésre van szükség.