[CSAPP] x86-64 - Control

1. 컨디션 코드

1-1. 프로세서 상태 (x86-64)

x86-64 프로세서의 상태, 즉 현재 실행 중인 프로그램에 대한 정보들로는 무엇이 있을까? 가장 먼저 여러 임시 데이터들을 저장하는 %rax와 같은 범용 레지스터들과, 현재 런타임 스택의 스택 포인터를 저장하는 %rsp 레지스터가 있다. 그리고 다음 실행할 명령어의 메모리 주소를 저장함으로써 현재의 제어 위치를 나타내는 %rip 레지스터(PC 레지스터)도 이에 해당한다. 또한 조건 분기/이동에 사용되는 상태 값을 저장하는 컨디션 코드(Condition Code) 레지스터들도 있다. 

---

1-2. 컨디션 코드 (Condition Code)

x86-64의 컨디션 코드 레지스터는 총 4개이다. 첫째, 부호 없는 값의 Carry Out 발생 여부를 나타내는 CF(Carry Flag) 레지스터이다. 둘째, 부호 있는 값의 부호를 나타내는 SF(Sign Flag) 레지스터이다. 셋째, 값이 0인지를 나타내는 ZF(Zero Flag) 레지스터이다. 넷째, 부호 있는 값의 오버플로우 발생 여부를 나타내는 OF(Overflow Flag) 레지스터이다. 이러한 컨디션 코드들의 값은 이어서 설명할 암묵적인 방법 또는 명시적인 방법에 의해 적절히 세팅이 된다.

 

① CF : 연산 시 MSB로부터 Carry Out이 발생하거나 MSB로의 Borrow가 발생하면 세팅됨 (unsigned 연산에서만 의미 있음)
② ZF : 연산 결괏값이 0이면 세팅됨
③ SF : 연산 결괏값의 MSB가 1이면 세팅됨
④ OF : 연산 시 오버플로우가 발생하면 세팅됨 (signed 연산에서만 의미 있음)

---

1-3. 컨디션 코드 조작 : 암묵적 방법 (Implicit Setting)

값에 대한 특정 연산을 수행하는 계산 명령어가 실행되고 나면, 그 결괏값에 의해 컨디션 코드 레지스터들의 값이 자동으로 세팅된다(참고로 leaq 명령어는 컨디션 코드 레지스터들의 값을 바꾸지 않음). 예를 들어 "addq A, B" 명령어를 실행하여 (A + B)를 계산한다고 해보자. 그러면 각 컨디션 코드 레지스터는 다음과 같이 세팅이 된다.

 

① CF : 덧셈 시 MSB로부터 Carry Out이 발생하면 세팅됨

② ZF : (A + B == 0)이면 세팅됨

③ SF : (A + B)의 MSB가 1이면 세팅됨

④ OF : (A > 0 && B > 0 && (A + B) < 0) 또는 (A < 0 && B < 0 && (A + B) ≥ 0)이면 세팅됨

 

여기서 주목할 점은, CF는 부호 없는 값의 덧셈 시에 오버플로우를 감지하는 수단이 되고, OF는 부호 있는 값의 덧셈 시에 오버플로우를 감지하는 수단이 된다. 즉, CF는 부호 없는 값의 연산 시에만, OF는 부호 있는 값의 연산 시에만 의미 있는 플래그이다. CPU 입장에서는 피연산자가 부호 없는 값인지 부호 있는 값인지 구별하지 않으므로, 두 플래그를 독립적으로 세팅한다. 따라서 사용하는 입장에서 의미 있는 플래그가 무엇인지 스스로 잘 판별하여 사용해야 한다.

---

1-4. 컨디션 코드 조작 : 명시적 방법 (Explicit Setting)

위에서 말한 암묵적 방법 말고도, 컨디션 코드 레지스터들의 값을 직접 조작하기 위한 명령어들도 따로 존재한다. 대표적으로 두 값의 대소 비교 결괏값에 따라 컨디션 코드 레지스터들의 값을 세팅하는 Compare 명령어, 그리고 두 값의 AND 연산 결괏값에 따라 컨디션 코드 레지스터들의 값을 세팅하는 Test 명령어가 있다. 각각에 대해 알아보자.

 

1-4-1. Compare 명령어

cmpq B, A → (A - B)의 결과에 따라 컨디션 코드 레지스터들의 값을 세팅

① CF : 뺄셈 시 MSB로의 Borrow가 발생한 경우 세팅됨 (부호 없는 값의 비교에서 사용됨)

② ZF : (A - B == 0)이면 세팅됨

③ SF : (A - B)의 MBS가 1이면 세팅됨 (부호 있는 값의 비교에서 사용됨)

④ OF : (A > 0 && B < 0  && (A - B) < 0)이거나 (A < 0 && B > 0 && (A - B) ≥ 0)이면 세팅됨

 

1-4-2. Test 명령어

testq B, A → (A & B)의 결과에 따라 컨디션 코드 레지스터들의 값을 세팅

① ZF : (A & B == 0)이면 세팅됨

② SF : (A & B)의 MBS가 1이면 세팅됨

---

1-5. 컨디션 코드 기반 명령어 : SetX

현재 컨디션 코드 레지스터들의 값이 어떠하냐에 따라서 달리 동작하는 명령어도 있다. 바로 SetX 명령어이다. 이는 현재 컨디션 코드 레지스터들의 값에 따라 목적지에 해당하는 레지스터의 하위 1바이트 값을 0 또는 1로 세팅한다(나머지 7바이트는 건드리지 않음). setX 명령어의 종류는 다음과 같다.

 

 

나머지 7바이트의 경우는 보통 movzbl과 같은 명령어를 통해 0으로 채워주게 된다. 참고로 movzbl 또는 movsbl의 쓰임새는 다음과 같다. 또한 기억해둬야 할 점은, l로 끝나는 32비트 명령어는 자동으로 상위 32비트를 0으로 채운다는 것이다. 이러한 동작 방식은 w로 끝나는 16비트 명령어, b로 끝나는 8비트 명령어에도 동일하게 적용된다.

movzbl A, B → A를 Zero Extenstion 한 결과를 B에 넣는다 (32비트 명령어)
mobsbl A, B → A를 Sign Extenstion 한 결과를 B에 넣는다 (32비트 명령어)

 

다음 예시를 보며 위에서 설명한 내용을 직접 이해해보도록 하자.

 

 

2. 조건 분기/이동

2-1. 조건 분기 (Conditional Branch)

x86-64에서는 분기를 위한 명령어로 jX를 제공한다. 여기에는 무조건 분기와 조건 분기가 모두 포함되어 있다. 조건 분기의 경우, 컨디션 코드 레지스터들의 값에 따라서 분기 여부를 결정하게 된다. 다음 표를 참고하자.

 

 

위의 명령어를 이용하여 C 언어의 if 문을 번역한 결과는 대략 다음과 같다.

 

또한 C 언어의 goto문을 이용하면 어셈블리어로 번역되는 결과와 유사한 형태로 바꿀 수 있다. 다음 예시를 참고하자.

 

---

2-2. 조건 이동 (Conditional Move)

유사한 방식으로, 컨디션 코드 레지스터들의 값이 특정 조건을 만족할 때만 값을 이동시키는 cmovX 명령어도 존재한다. 이는 1995년 이후에 나온 x86 CPU에서부터 지원되는 것으로, 컴파일러가 조건문을 조건 이동으로 안전하게 번역할 수 있다고 판단하는 경우에는 jX 명령어가 아닌 cmovX 명령어를 사용하게 된다. 왜 그럴까? 뒤에서 배우겠지만, CPU의 명령어 실행 구현 방식 중 하나인 파이프라인 방식은 분기가 많으면 많을수록 성능이 저하된다. 반면에 조건 이동은 분기를 실제로 수행하지 않기 때문에 성능 저하를 일으키지 않는다. 예컨대 C 언어의 삼항 연산자는 다음과 같은 형태로 번역이 될 수 있다. 빨간색으로 표시된 부분이 cmovX 명령어의 역할에 해당한다.

 

 

이제 실제로 C 언어의 조건문을 cmovX 명령어로 번역하는 경우를 살펴보도록 하자.

 

 

참고로 조건 이동 사용을 자제해야 하는 경우도 있다. 대표적으로 세 경우가 있는데, 첫 번째 경우는 Then에 해당하는 값과 Else에 해당하는 값 둘 다 계산량이 많은 경우이다. 이 경우 불필요한 값까지 계산하느라 시간이 많이 낭비된다는 단점이 있다. 두 번째는 포인터가 무슨 값인지를 모르고 계산을 행하는 경우이다. 예를 들어, "p ? *p : 0"이라는 표현식을 생각해 보자. p라는 값이 만약 올바른 메모리 주소가 아니라면 *p를 계산하는 순간 에러가 발생하게 된다. 마지막으로 세 번째 경우는 값을 계산할 때 Side Effect가 발생하는 경우이다. 예를 들어 "x > 0 ? x *= 7 : x += 3"이라는 표현식을 생각해 보자. 미리 계산하는 과정에서 x의 값이 예상치 못하게 바뀔 수 있는 것이다.

 

3. 루프 번역

3-1. do while 문

do while 문은 조건 분기를 이용하여 다음과 같은 형태로 번역이 된다.

 

---

3-2. while 문

while 문은 조건 분기를 이용하여 번역할 수 있는 형태가 두 가지이다. 첫 번째는 "Jump-to-middle" 방식으로, 처음에 조건 테스트를 위한 부분으로 바로 점프하는 형태이다. 다음을 참고하자.

 

 

두 번째는 "Do-while" 방식으로, 우선 do while 문 형태로 고친 뒤 이를 다시 번역하는 것이다. 다음을 참고하자.

 

 

---

3-3. for 문

for 문은 다음에서 볼 수 있듯이 "Do-While" 방식으로 번역되는 while 문처럼 번역이 된다. 이때 for 문의 경우에는 첫 번째 조건 테스트가 불필요하다고 판단되는 경우 삭제될 수 있다. 이는 컴파일러의 자체적인 판단에 의한 최적화의 결과인 것이다.

 

 

4. 스위치 문 번역

4-1. switch 문 번역 원리 : 점프 테이블 (Jump Table)

아래의 왼쪽 그림에서 나타내는 C 언어의 일반적인 switch 문은 점프 테이블(Jump Table)이라는 것을 이용하여 구현된다. 점프 테이블은 switch 문의 각 경우에 해당하는 코드 블록의 시작 주소들을 저장하는 테이블이다. x86-64에서 메모리 주소는 64비트로 표현되므로 점프 테이블의 각 엔트리는 8바이트이다. 먼저 x의 값에 따라 실행해야 하는 코드 블록의 시작 주소를 점프 테이블에서 찾고, 그곳으로 점프하여 올바른 코드 블록을 실행하게 되는 것이다.

 

 

※ 참고 1 : 점프 테이블의 저장 위치

점프 테이블은 프로그램 코드와는 다른 메모리 영역에 로드된다. 구체적으로는 .rodata이라는 메모리 영역에 저장되는데, 이곳에는 리터럴 상수나 점프 테이블과 같은 읽기 전용(Read Only) 데이터가 저장이 된다.)

 

※ 참고 2 : 각 경우에 해당하는 값들이 조밀하지 않은 switch 문

점프 테이블이 아닌 결정 트리(Decision Tree)라는 것을 이용하여 구현한다. 하지만 해당 내용은 상당히 복잡하여 본 포스팅에서는 설명을 생략하기로 하였다.

---

4-2. switch 문 번역 예시

직접 번역 예시를 살펴보며 차근차근 이해해보자. 다음과 같은 C 언어 switch 문이 있다고 가정하자.

 

 

먼저 다음 부분을 살펴보자. x의 값이 6보다 크면 default 경우에 해당하는 코드 블록(시작 주소 : .L8)으로 점프한다. default 경우가 아니라면 점프 테이블을 참조하여 실행해야 하는 블록의 시작 주소를 찾고, 그곳으로 점프한다. 이렇듯 점프할 주소를 메모리에서 먼저 찾은 다음 그곳으로 점프하는 방식을 간접 점프(Indirect Jump)라고 한다. 반면 "jmp .L8"과 같이 점프할 주소를 명시적으로 적는 방식은 직접 점프(Direct Jump)라고 한다. 참고로 %rdi의 값(= x의 값)에 8을 곱하는 이유는 점프 테이블의 각 엔트리가 8바이트이기 때문이다. 또한 여기서 w가 초기화되지 않는다는 점에 주목하자. 이는 컴파일러가 자체적으로 판단하여 최적화를 한 결과로, 뒷부분을 모두 이해하고 나면 이 부분도 이해가 될 것이다. 또한 %rdx의 값(= z의 값)을 %rcx에 저장하는 이유도 뒷부분을 모두 이해하고 나면 고개를 끄덕이게 될 것이다.

 

 

이제 각 경우에 해당하는 코드 블록의 번역 결과를 살펴볼 것인데, 그전에 먼저 switch 문의 각 경우가 점프 테이블에 어떻게 반영되어 있는지 큰 그림을 파악해 보도록 하자. 다음 그림에 그 맵핑 정보가 나타나 있다.

 

 

먼저 x의 값이 1인 경우이다.

 

 

이번엔 x의 값이 2 또는 3인 경우이다. 2에 해당하는 코드 블록에서는 break문이 없기 때문에 아래로 내려간다는 것에 주목하자. 또한 여기서 cqto, idivq라는 생소한 명령어를 볼 수 있는데, 이에 대한 설명은 그 바로 아래에 나타나 있는 표를 참고하도록 하자.

 

 

마지막으로 x의 값이 5 또는 6인 경우, 그리고 default 경우이다.