x86-64 플래그와 조건 분기 완전 이해

본 블로그 작성 글들은 강의를 목표로 제작되었습니다. 예제는 Intel 문법을 기준으로 하며 성능 특성은 CPU와 실제 입력 분포에 따라 측정해야 합니다.

cmp eax, edx는 결과를 어디에도 저장하지 않는데 다음 jl은 어떻게 대소 관계를 알까? 같은 비트 0xFFFFFFFF를 비교하면서 어떤 코드는 -1로, 어떤 코드는 4,294,967,295로 보는 이유는 무엇일까?

x86-64의 비교와 분기는 RFLAGS의 조건 플래그를 매개로 연결된다. 중요한 것은 플래그를 전부 외우는 것이 아니라 어느 명령이 플래그를 만들었고, 다음 명령이 signed와 unsigned 중 어떤 해석으로 소비하는지 추적하는 것이다.

자주 읽는 상태 플래그

RFLAGS에는 더 많은 상태·제어 플래그가 있지만 일반적인 컴파일러 출력의 조건 분기에서는 위 네 개, 특히 ZF, CF, SF, OF가 중심이다.

cmp는 결과를 버리는 sub처럼 동작한다

cmp rax, rdx

개념적으로 rax - rdx를 계산해 플래그만 갱신하고 rax와 rdx 값은 유지한다.

cmp eax, 10
je  equal_ten
jl  signed_less_than_ten

je는 ZF = 1을 본다. jl은 signed less 조건인 SF != OF를 본다. 두 분기 모두 가장 가까운 cmp라는 문법 규칙이 있는 것은 아니다. 사이에 플래그를 변경하는 명령이 있으면 그 새 플래그를 소비한다.

cmp eax, 10
add ecx, 1       ; 플래그가 바뀜
jl somewhere     ; 이제 cmp가 아니라 add 결과를 검사

이런 코드는 의도적일 수도 있지만, 분석할 때 플래그의 데이터 의존성을 놓치기 쉽다.

test는 결과를 버리는 and처럼 동작한다

test rax, rax
jz is_zero

rax & rax의 결과를 저장하지 않고 플래그만 만든다. 값이 0인지 검사할 때 흔하다.

test eax, 1
jnz is_odd

특정 비트가 켜졌는지도 검사할 수 있다. test는 CF와 OF를 0으로 만들고 ZF, SF, PF를 결과에 맞게 설정한다. cmp eax, 0과 test eax, eax는 zero 검사에서는 같은 분기 결과를 만들 수 있지만 모든 플래그가 완전히 같은 방식으로 정의된다고 일반화하지 않는다.

equality에는 signed와 unsigned 차이가 없다

비트가 같은지 다른지는 부호 해석과 무관하다.

je와 jz는 같은 조건 코드를 다른 관점으로 부르는 동의어다. cmp 뒤에서는 equal, test 뒤에서는 zero라는 이름이 읽기 쉬울 뿐이다.

대소 비교는 signed와 unsigned를 나눈다

cmp left, right 뒤의 대표 조건은 다음과 같다.

signed 비교는 SF와 OF, unsigned 비교는 CF와 ZF를 주로 조합한다.

mov eax, 0FFFFFFFFh
cmp eax, 1
jl signed_less       ; 참: -1 < 1
jb unsigned_below    ; 거짓: 4294967295 < 1이 아님

CPU가 eax에 signed 타입 꼬리표를 붙인 것이 아니다. 같은 cmp 결과를 어느 조건 분기로 해석하는지가 다르다.

포인터와 크기는 보통 unsigned 관점이다

배열 길이와 index가 size_t라면 unsigned 비교가 자연스럽다.

cmp rdx, rcx
jae out_of_range     ; index >= count

반면 온도, 좌표, signed 정수처럼 음수가 의미 있는 값에는 jl, jge가 필요할 수 있다. 디스어셈블리에서 jae가 보인다는 사실은 원래 소스 타입이 unsigned였다는 강한 단서지만, 최적화와 값 범위 분석 때문에 항상 소스를 완전히 복원할 수 있는 것은 아니다.

CF와 OF는 서로 다른 오버플로를 말한다

8비트 예로 생각해 보자.

0xFF + 0x01 = 0x00

unsigned로는 255 + 1이 8비트를 넘었으므로 carry가 있다. signed로는 -1 + 1 = 0이라 정상 범위다. 반대로 다음을 보자.

0x7F + 0x01 = 0x80

unsigned 127 + 1 = 128은 정상이다. signed 127 + 1은 8비트 signed 최대값을 넘으므로 overflow다.

add al, 1
jc  unsigned_overflow
jo  signed_overflow

C/C++의 unsigned 정수는 2의 거듭제곱 모듈러 연산으로 정의되지만 signed overflow는 정의되지 않은 동작이다. 하드웨어가 OF를 제공한다는 사실이 C의 signed overflow를 자동으로 정의해 주지는 않는다.

산술 후 바로 조건을 읽을 수 있다

add, sub, inc, dec, neg, 논리 연산은 여러 플래그를 갱신한다. 단, 세부 차이가 있다. 예를 들어 inc와 dec는 CF를 보존한다. 이 때문에 multi-precision carry chain 주변에서는 add 1과 inc를 무심코 교체하면 의미가 달라질 수 있다.

sub rcx, 1
jnz loop_begin

별도 cmp rcx, 0 없이 감소 결과의 ZF를 사용한다. 컴파일러 출력에서 비교 명령이 보이지 않아도 앞선 산술이 플래그를 공급했는지 확인한다.

setcc는 조건을 0 또는 1로 만든다

cmp edi, esi
setl al
movzx eax, al
ret

signed edi < esi이면 al = 1, 아니면 0이다. setcc는 1바이트 목적지만 쓰므로 movzx 또는 사전 zeroing으로 상위 비트를 정리해야 한다.

xor eax, eax
cmp edi, esi
setl al
ret

이 패턴은 C의 boolean 비교 결과에서 흔히 보인다.

cmovcc는 분기 없이 값을 고른다

; eax = a, edx = b
cmp eax, edx
cmovl eax, edx      ; a < b이면 eax = b

조건 이동은 제어 흐름을 나누지 않고 조건이 참일 때만 레지스터 목적지를 갱신한다. max(a, b) 같은 작은 선택에서 유용할 수 있다.

하지만 cmovcc의 메모리 원본은 조건이 거짓이어도 주소 접근과 fault 관점에서 안전하다고 가정하면 안 된다. 또한 긴 dependency chain을 만들 수 있어 항상 분기보다 빠르지 않다.

branchless가 자동으로 빠른 것은 아니다

현대 CPU는 분기를 예측한다. 조건이 매우 잘 예측되면 jcc는 값싼 경로가 될 수 있다. 반대로 입력이 불규칙하고 양쪽 작업이 작다면 setcc, cmovcc, mask 연산이 misprediction 비용을 줄일 수 있다.

판단에는 다음이 필요하다.

• 실제 입력에서의 분기 방향 분포
• misprediction 빈도
• 양쪽 경로가 수행하는 작업량
• branchless 변환으로 늘어난 명령과 dependency
• compiler가 이미 만든 코드
• 대상 CPU와 측정 노이즈

소스의 if 개수나 어셈블리의 jmp 개수만 세어 성능을 결론 내리지 않는다.

루프의 제어 흐름을 복원한다

xor eax, eax          ; sum = 0
xor edx, edx          ; i = 0

loop_test:
    cmp rdx, rsi
    jae loop_done
    add eax, dword ptr [rdi + rdx*4]
    inc rdx
    jmp loop_test

loop_done:
    ret

control-flow graph로 보면 세 basic block이다.

1. 조건 검사 block
2. loop body와 증가 block
3. 반환 block

jae이므로 i >= count를 unsigned로 검사한다. jmp loop_test는 무조건 back edge다. 최적화되면 loop rotation, unrolling, vectorization으로 이 모양이 바뀔 수 있다.

short-circuit 조건은 여러 분기로 펼쳐진다

if (p != nullptr && p->ready)
    use(p);

가능한 형태는 다음과 같다.

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

첫 번째 분기가 null 역참조를 막는다. 분석하면서 두 조건을 순서를 바꿔 읽으면 안전성 의미를 놓친다. compiler가 특정 pointer가 null이 아니라고 증명하면 첫 검사를 제거할 수도 있다.

switch는 항상 연속된 비교가 아니다

case가 촘촘하면 jump table이 나올 수 있다.

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

먼저 최소 case 값을 빼고 범위를 unsigned로 검사한 뒤 table에서 목표 주소를 고른다. 범위 검사가 없다면 table 밖 간접 분기로 이어질 수 있으므로 역공학과 보안 검토에서 중요한 지점이다.

case가 드문드문 있으면 비교 체인이나 이진 검색 형태가 더 적합할 수 있다.

플래그는 함수 호출을 넘어 보존된다고 가정하지 않는다

일반적인 ABI는 호출자가 조건 플래그를 live 상태로 유지한 채 다른 함수를 호출하고 같은 값을 기대하는 인터페이스를 제공하지 않는다.

cmp eax, edx
call helper
jl old_comparison_result    ; helper가 플래그를 바꿨을 수 있음

비교 결과가 필요하면 호출 전에 0/1로 materialize하거나 호출 뒤 다시 비교한다.

자주 하는 실수

• jl과 jb, jg와 ja를 같은 뜻으로 생각한다.
• cmp가 왼쪽 레지스터 값을 실제로 뺀다고 생각한다.
• 비교와 분기 사이의 명령이 플래그를 덮어쓴 사실을 놓친다.
• inc와 add 1이 모든 플래그에서 같다고 생각한다.
• C signed overflow를 CPU wraparound 결과와 동일시한다.
• branchless라는 이유만으로 빠르다고 결론 낸다.
• setcc al 뒤의 상위 레지스터 상태를 무시한다.

직접 확인하는 실습

다음 네 함수를 signed와 unsigned 버전으로 컴파일한다.

int less_i32(int a, int b) { return a < b; }
int less_u32(unsigned a, unsigned b) { return a < b; }
int clamp_zero(int x) { return x < 0 ? 0 : x; }
unsigned count_nonzero(const int* p, size_t n);

확인할 항목은 다음과 같다.

1. signed와 unsigned 함수가 어떤 jcc 또는 setcc를 선택하는가?
2. clamp_zero가 분기와 cmov 중 무엇을 사용하는가?
3. 최적화 수준을 바꾸면 loop 모양이 어떻게 달라지는가?
4. INT_MIN, -1, 0, 1, INT_MAX와 unsigned 경계에서 결과가 맞는가?

정리

cmp와 test는 값을 저장하지 않고 조건 플래그를 만든다. equality는 ZF로 판단하지만 대소 관계는 signed의 SF/OF 조합과 unsigned의 CF/ZF 조합을 구분해야 한다. setcc와 cmovcc는 조건을 데이터로 바꾸지만 항상 분기보다 빠른 것은 아니다.

분기 코드를 읽을 때는 “가장 가까운 cmp”를 기계적으로 찾지 말고 플래그를 마지막으로 정의한 명령, 조건의 signedness, 각 분기에서 가능한 입력 범위를 함께 추적한다.

공식 참고 자료

• Intel 64 and IA-32 Architectures Software Developer's Manual
• AMD64 Architecture Programmer's Manual Volume 3
• Intel 64 and IA-32 Architectures Optimization Reference Manual