Verzweigungsfreier Code in

Über Verzweigungsfreier Code

Das Konzept Bedingungen führt jcc ein, die Familie von Befehlen für bedingte Sprünge. Ein jcc überträgt die Ausführung nur dann an eine andere Stelle im Programm, wenn seine Bedingung erfüllt ist.

Moderne CPUs sind jedoch schnell und können viele Befehle parallel ausführen. Es wäre zu teuer, alle Arbeit anzuhalten, während die CPU auf eine Laufzeitprüfung einer Bedingung wartet.

Deshalb wartet die CPU intern nicht. Sie verwendet eine Sprungvorhersage, um das Ergebnis einer Bedingung zu erraten, und beginnt, den vorhergesagten Pfad spekulativ auszuführen.

Liegt die Vorhersage richtig, läuft die Ausführung weiter, als gäbe es keinen Sprung. Liegt sie jedoch falsch, muss die CPU die auf dem vorhergesagten Pfad geleistete Arbeit verwerfen und auf dem richtigen Pfad neu beginnen.

Das nennt man eine Sprungfehlvorhersage, und sie ist teuer: Sie verursacht eine Verzögerung.

Wenn ein Sprung schwer vorherzusagen ist, summieren sich diese Fehlvorhersagen. In solchen Fällen ist es manchmal besser, den Sprung ganz zu vermeiden, sodass unabhängig von der Bedingung dieselben Befehle ausgeführt werden. Code, der ohne jcc zwischen Werten auswählt, heißt sprungfrei.

Es gibt mehrere Möglichkeiten, Code so zu strukturieren, dass er seltener springt oder dass die Sprünge, die er enthält, besser vorhersagbar sind. Insbesondere stellt x86-64 zwei Befehlsfamilien bereit, die häufig für sprungfreien Code verwendet werden.

Bedingte Move-Befehle

Die Befehlsfamilie cmovcc kopiert den Quelloperanden nur dann ins Ziel, wenn eine bestimmte Bedingung erfüllt ist. Andernfalls bleibt das Ziel unverändert.

Das Suffix cc folgt derselben Namensgebung wie bei jcc und hat dieselbe Bedeutung:

Die Regeln ähneln denen von jcc:

1. l und g werden für vorzeichenbehaftete Vergleiche verwendet, b und a für vorzeichenlose.
2. Ein angehängtes e schließt Gleichheit mit ein.
3. Ein angehängtes n verneint die Bedingung.
4. Es gibt auch Varianten, die sich auf ein gesetztes Flag beziehen. Zum Beispiel cmovz und cmovc.

Betrachte den Betrag einer vorzeichenbehafteten Ganzzahl in rdi, der in rax zurückgegeben wird. Mit jcc geschrieben wählt die Funktion einen von zwei Pfaden:

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

Mit cmovcc geschrieben werden beide Kandidatenwerte bedingungslos berechnet, und das bedingte Move wählt einen davon aus:

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

Die sprungfreie Version führt immer dieselben Befehle aus. Es gibt kein jcc, das die Sprungvorhersage erraten könnte.

Das Ziel eines cmovcc muss ein Register sein. Die Quelle darf ein Register oder eine Speicherstelle sein, aber kein unmittelbarer Wert.

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

Bedingte Set-Befehle

Die Befehlsfamilie setcc setzt den Zieloperanden auf 1, wenn eine bestimmte Bedingung erfüllt ist, und andernfalls auf 0. Das Ziel ist immer ein 8-Bit-Operand.

Das Suffix cc folgt derselben Namensgebung wie bei jcc und cmovcc. Zum Beispiel setzt setz das Ziel auf 1, wenn ZF == 1 gilt, und andernfalls auf 0.

Da das Ziel 8 Bit breit ist, folgt auf setcc üblicherweise ein movzx, wenn ein breiterer Wert benötigt wird:

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

Das ist ein gängiges Idiom, um ein Vergleichsergebnis in eine Ganzzahl 0 oder 1 umzuwandeln.

Wann du sprungfreien Code verwenden solltest

Sprungfreier Code ist nicht immer schneller als Code mit Sprüngen. Ist ein Sprung gut vorhersagbar, liegt die Sprungvorhersage fast immer richtig und ein jcc kostet praktisch nichts. Sprungfreier Code, der einen solchen Sprung ersetzt, ist langsamer, weil er immer beide Kandidatenberechnungen ausführt.

Ein Schleifenzähler ist das klassische Beispiel. Betrachte eine Funktion, die rsi 64-Bit-Ganzzahlen ab rdi aufsummiert:

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

Das ist genau die Art von Muster, mit der Sprungvorhersagen gut zurechtkommen, der Sprung ist also praktisch kostenlos, egal wie viele Elemente sum_array verarbeitet.

Sprungfreier Code lohnt sich, wenn der Sprung schwer vorherzusagen ist oder wenn unabhängig von den Eingaben ein gleichbleibendes Zeitverhalten gefordert ist.