x86-64-Flags und bedingte Sprünge verstehen

Diese Blogartikel sind als Lehrmaterial gedacht. Die Beispiele verwenden Intel-Syntax. Performance muss auf der Ziel-CPU mit realer Eingabeverteilung gemessen werden.

cmp eax, edx speichert kein sichtbares Ergebnis. Woher weiß das folgende jl, welcher Wert kleiner ist? Warum können dieselben Bits 0xFFFFFFFF einmal -1 und einmal 4.294.967.295 bedeuten? Entscheidend sind RFLAGS und die signed- oder unsigned-Bedingung, die diese Flags auswertet.

Häufige Statusflags

Normale Verzweigungen kombinieren vor allem ZF, CF, SF und OF.

cmp und test

cmp rax, rdx

Konzeptionell wird rax-rdx berechnet, das Ergebnis verworfen und nur die Flags aktualisiert.

cmp eax, 10
je equal_ten
jl signed_less_than_ten

Ein Sprung ist nicht grammatisch an das nächste cmp gebunden. Ein dazwischenliegender flagsetzender Befehl ersetzt den Zustand.

cmp eax, 10
add ecx, 1
jl somewhere      ; wertet ADD aus

test verhält sich wie ein verworfenes bitweises AND und eignet sich für Null- und Maskenprüfungen.

test rax, rax
jz is_zero
test eax, 1
jnz is_odd

Gleichheit und Größenordnung

Gleichheit ist unabhängig vom Vorzeichen: je/jz prüft ZF=1, jne/jnz prüft ZF=0. Die Größenordnung muss dagegen getrennt werden.

mov eax, 0FFFFFFFFh
cmp eax, 1
jl signed_less       ; -1 < 1, wahr
jb unsigned_below    ; 4294967295 < 1, falsch

Das Register trägt kein signed-Typetikett. Die Auswertung derselben Vergleichsflags macht den Unterschied.

CF und OF beschreiben andere Überläufe

In acht Bit hat 0xFF+1=0x00 einen unsigned Carry, aber signed ist -1+1 korrekt. 0x7F+1=0x80 ist unsigned 128, überschreitet jedoch signed 127.

add al, 1
jc unsigned_overflow
jo signed_overflow

Unsigned-Arithmetik ist in C/C++ modulo definiert, signed Overflow ist undefiniertes Verhalten. Das Hardware-Flag OF ändert den Sprachvertrag nicht. Außerdem erhalten inc und dec das CF; sie sind bezüglich aller Flags nicht identisch zu add 1 und sub 1.

setcc und cmovcc

xor eax, eax
cmp edi, esi
setl al
ret

Der signed Vergleich wird zu 0 oder 1. setcc schreibt nur ein Byte, daher müssen die oberen Bits bewusst bereinigt werden.

cmp eax, edx
cmovl eax, edx

Ein Conditional Move wählt einen Wert ohne Verzweigung, kann aber Abhängigkeitsketten verlängern. Er ist nicht automatisch schneller.

Branchless bedeutet nicht automatisch schneller

Moderne CPUs sagen Sprünge voraus. Ein gut vorhersehbares jcc ist billig; bei unregelmäßigen Daten und kleinen Pfaden können setcc, cmovcc oder Masken helfen. Entscheidend sind reale Verteilung, Fehlvorhersagen, Arbeit beider Pfade, zusätzliche Befehle und Abhängigkeiten sowie Messungen auf der Ziel-CPU.

Schleifen und Short Circuit

xor eax, eax
xor edx, edx
loop_test:
    cmp rdx, rsi
    jae loop_done
    add eax, [rdi + rdx*4]
    inc rdx
    jmp loop_test
loop_done:
    ret

jae prüft unsigned i >= count. Optimierung kann die Form durch Rotation, Unrolling und Vektorisierung stark ändern.

test rcx, rcx
jz done
cmp byte ptr [rcx + READY_OFFSET], 0
je done
call use
done:

Dies ist eine mögliche Form von p != nullptr && p->ready. Der erste Sprung verhindert das Null-Dereferenzieren; die Reihenfolge ist Teil des Sicherheitsvertrags.

Sprungtabelle

sub eax, 3
cmp eax, 4
ja default_case
jmp qword ptr [table + rax*8]

Nach Normalisierung begrenzt ein unsigned Range Check den Tabellenindex. Diese Prüfung ist eine wichtige Sicherheitsgrenze vor dem indirekten Sprung.

Flags nicht über Funktionsaufrufe erwarten

cmp eax, edx
call helper
jl old_result       ; helper darf Flags ändern

Die Bedingung muss vor dem Aufruf in 0/1 umgewandelt oder danach neu berechnet werden.

Zusammenfassung

cmp und test erzeugen Flags, ohne ihr Rechenergebnis zu speichern. Gleichheit nutzt ZF; Größenvergleiche unterscheiden signed SF/OF von unsigned CF/ZF. Verfolgen Sie den letzten flagdefinierenden Befehl, die signedness der Bedingung und den möglichen Eingabebereich jeder Kontrollflusskante.

Offizielle Quellen

• Intel Software Developer's Manual
• AMD64 Programmer's Manual Volume 3
• Intel Optimization Reference Manual