Condition Codes
특정한 작업 결과에 따라 부차적으로 설정되는 플래그를 조건 코드(Condition code)라 한다.
| Flag | Name |
|---|
| CF | Carry Flag (for unsigned) |
| ZF | Zero Flag |
| SF | Sign Flag (for signed) |
| OF | Overflow Flag (for signed) |
x86은 조건 코드들을 저장하는 상태 레지스터를 가지고 있다.
Implicit Setting
산술 연산의 결괏값을 t라고 할 때, 각 조건 코드가 설정되는 조건은 다음과 같다.
| Flag | Condition |
|---|
| CF | unsigned overflow |
| ZF | t == 0 |
| SF | t < 0 |
| OF | signed overflow |
lea 명령어는 조건 코드를 설정하지 않는다.
Explicit Setting: Compare
cmpq b, a 명령은 a와 b의 값을 비교하여 조건 코드를 설정한다. (t = a - b)
| Flag | Condition |
|---|
| CF | unsigned overflow |
| ZF | a == b |
| SF | a - b < 0 |
| OF | signed overflow |
Explicit Setting: Test
testq b, a 명령은 a & b의 값에 따라 조건 코드를 설정한다. (t = a & b)
| Flag | Condition |
|---|
| ZF | a & b == 0 |
| SF | a & b < 0 |
Reading Condition Codes
setX 명령어를 통해 설정된 조건 코드의 값을 활용할 수 있다.
| Instruction | Condition | Description |
|---|
sete | ZF | Equal / Zero |
setne | ~ZF | Not Eqaul / Not Zero |
sets | SF | Negative |
setns | ~SF | Nonnegative |
setg | ~(SF^OF) & ~ZF | Greater (signed) |
setge | ~(SF^OF) | Greater or Equal (signed) |
setl | (SF^OF) | Less (signed) |
setle | (SF^OF) \| ZF | Less or Equal (signed) |
seta | ~CF & ~ZF | Above (unsigned) |
setb | CF | Below (unsigned) |
Reading Condition Codes Example
1
2
3
| int gt(long x, long y) {
return x > y;
}
|
1
2
3
4
| cmpq %rsi, %rdi
setg %al
movzbl %al, %eax
ret
|
| Register | Use |
|---|
%rdi | x |
%rsi | y |
%rax | 반환값 |
cmpq는 두 값을 비교하여 조건 코드를 설정한다.setg는 x > y가 참일 경우 %al(%rax의 최하위 바이트)의 값을 1로 설정한다.movzbl는 %al의 값을 %eax의 하위 바이트에 복사하고, 나머지 바이트를 0으로 채운다. 이때 %eax는 %rax의 하위 32비트이기에, %rax의 상위 32비트까지 0으로 채워진다. (mov + zb: zero extend + l: double word)
Conditional Branches
Jumping
jX 명령어를 통해 코드의 특정 위치로 건너뛸 수 있다.
| Instruction | Condition | Description |
|---|
jmp | 1 | Unconditional |
je | ZF | Equal / Zero |
jne | ~ZF | Not Equal / Not Zero |
js | SF | Negative |
jns | ~SF | Nonnegative |
jg | ~(SF^OF) & ~ZF | Greater (signed) |
jge | ~(SF^OF) | Greater or Equal (signed) |
jl | (SF^OF) | Less (signed) |
jle | (SF^OF) \| ZF | Less or Equal (signed) |
ja | ~CF & ~ZF | Above (unsigned) |
jb | CF | Below (unsigned) |
Conditional Branch Example
1
2
3
4
5
6
7
8
| long absdiff(long x, long y) {
long result;
if (x > y)
result = x - y;
else
result = y - x;
return result;
}
|
1
2
3
4
5
6
7
8
9
10
| absdiff:
cmpq %rsi, %rdi
jle .L2
movq %rdi, %rax
subq %rsi, %rax
ret
.L2:
movq %rsi, %rax
subq %rdi, %rax
ret
|
컴파일 최적화 단계: -Og
| Register | Use |
|---|
%rdi | x |
%rsi | y |
%rax | 반환값 |
cmpq로 두 값을 비교하여, x <= y일 경우 .L2로 점프한다.
Expressing with Goto Code
C 언어의 goto 구문은 어셈블리의 점프 명령어와 매우 유사한 구조를 가지고 있다.
1
2
3
4
5
6
7
8
9
10
11
| long absdiff_goto(long x, long y) {
long result;
int ntest = x <= y;
if (ntest) goto Else;
result = x - y;
goto Done;
Else:
result = y - x;
Done:
return result;
}
|
이러한 접근 방식은 컴파일러가 C 코드를 어셈블리 코드로 변환하는 과정을 이해하는 데 도움이 된다.
Conditional Move
현대의 프로세서는 명령어 파이프라이닝(Instruction pipelining)을 통해 이전 명령어 실행이 완료되기 전에 다음 명령어들을 미리 가져오는 방식으로 작동한다. 이때 조건 분기를 만나면, 조건이 평가될 때까지 기다리지 않고 분기 예측(Branch prediction)을 통해 가능성이 가장 높은 분기를 따라 실행한다. 분기 예측이 적중할 경우 매우 효율적이지만, 예측이 틀릴 경우 분기점으로 되돌아가 올바른 분기로 다시 시작해야 하므로 시간 지연이 발생한다.
조건부 이동(Conditional move)은 조건 분기를 처리할 때 적용할 수 있는 일종의 최적화 기법으로, 조건에 따라 계산되는 값들을 모두 계산한 뒤 마지막 순간에 한 값만을 선택하여 이동시킨다. 분기를 전환할 필요가 없으므로, 분기 예측이 어려운 경우에 특히 유용하다.
Conditional Move Example
1
2
3
4
5
6
7
8
| long absdiff(long x, long y) {
long result;
if (x > y)
result = x - y;
else
result = y - x;
return result;
}
|
1
2
3
4
5
6
7
8
| absdiff:
movq %rdi, %rdx
subq %rsi, %rdx
movq %rsi, %rax
subq %rdi, %rax
cmpq %rsi, %rdi
cmovg %rdx, %rax
ret
|
컴파일 최적화 단계: -O1
| Register | Use |
|---|
%rdi | x |
%rsi | y |
%rdx | result |
%rax | 반환값 |
cmovg = c(conditional) + mov + g(greater)
Bad Cases for Conditional Move
다음과 같은 경우에는 조건부 이동을 사용하지 않는다.
Loops
“Do-While” Translation
popcount()는 64비트 워드 x에 존재하는 비트 1의 개수를 반환하는 함수이다.
1
2
3
4
5
6
7
8
| long popcount_do(unsigned long x) {
long result = 0;
do {
result += x & 0x1;
x >>= 1;
} while (x);
return result;
}
|
1
2
3
4
5
6
7
8
| long popcount_do_goto(unsigned long x) {
long result = 0;
loop:
result += x & 0x1;
x >>= 1;
if (x) goto loop;
return result;
}
|
1
2
3
4
5
6
7
8
9
| popcount_do:
movl $0, %eax ; result = 0
.L2: ; loop:
movq %rdi, %rdx ; temp = x
andl $1, %edx ; temp &= 0x1
addq %rdx, %rax ; result += temp
shrq %rdi ; x >>= 1
jne .L2 ; if (x) goto loop
ret
|
“While” Translation #1
Jump-to-middle은 while 루프를 처리하는 하나의 방법으로, 바로 조건식으로 점프하여 평가 결과에 따라 본문의 실행 여부를 결정한다.
1
2
3
4
5
6
7
8
| long popcount_while(unsigned long x) {
long result = 0;
while (x) {
result += x & 0x1;
x >>= 1;
}
return result;
}
|
1
2
3
4
5
6
7
8
9
10
| long popcount_while_goto_jtm(unsigned long x) {
long result = 0;
goto test;
loop:
result += x & 0x1;
x >>= 1;
test:
if (x) goto loop;
return result;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| popcount_while:
movl $0, %eax
jmp .L2
.L3:
movq %rdi, %rdx
andl $1, %edx
addq %rdx, %rax
shrq %rdi
.L2:
testq %rdi, %rdi
jne .L3
ret
|
컴파일 최적화 단계: -Og
“While” Translation #2
또 하나의 방법은 while 루프를 do-while 루프로 변환하는 것이다. 이때 루프 시작 전에 초기 조건식을 도입하여 루프의 실행 여부를 결정한다.
1
2
3
4
5
6
7
8
9
10
| long popcount_while_goto_dw(unsigned long x) {
long result = 0;
if (!x) goto done;
loop:
result += x & 0x1;
x >>= 1;
if (x) goto loop;
done:
return result;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| popcount_while:
testq %rdi, %rdi
je .L4
movl $0, %eax
.L3:
movq %rdi, %rdx
andl $1, %edx
addq %rdx, %rax
shrq %rdi
jne .L3
ret
.L4:
movl $0, %eax
ret
|
컴파일 최적화 단계: -O1
“For” Loop Do-While Conversion
1
2
3
4
5
6
7
8
9
10
| #define WSIZE 8 * sizeof(int)
long pcount_for(unsigned long x) {
long result = 0;
for (size_t i = 0; i < WSIZE; i++) {
unsigned bit = (x >> i) & 0x1;
result += bit;
}
return result;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| long pcount_for_goto_dw(unsigned long x) {
size_t i;
long result = 0;
i = 0;
// if (!(i < WSIZE))
// goto done;
loop:
{
unsigned bit = (x >> 1) & 0x1;
result += bit;
}
i++;
if (i < WSIZE)
goto loop;
done:
return result;
}
|
for 구문의 초기 조건식은 참인 경우가 많으므로, -O1 옵션으로 컴파일하면 위의 주석 처리한 부분을 무시할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
| pcount_for:
movl $0, %edx
movl $0, %ecx
.L2:
movq %rdi, %rax
shrq %cl, %rax
andl $1, %eax
addq %rax, %rdx
addq $1, %rcx
cmpq $32, %rcx
jne .L2
movq %rdx, %rax
ret
|
Switch Statements
switch 구문에서는 점프 테이블(Jump table)을 이용하여 필요한 코드 블록으로 점프한다. 이는 배열 인덱싱과 유사한 방식으로, 상수 시간이 걸리므로 선형/로그 시간이 소요되는 연속적인 if-else 구문에 비해 효율적이다.
Jump Table Structure
| Jump Table | Targets |
|---|
| Address 0 | Code Block 0 |
| Address 1 | Code Block 1 |
| Address 2 | Code Block 2 |
| ⋮ | ⋮ |
| Address n-1 | Code Block n-1 |
컴파일러는 각 case의 코드 블록들을 모두 컴파일하여 메모리에 저장한 뒤, 각 코드 블록의 시작 위치를 담고 있는 점프 테이블을 생성한다.
Switch Statement Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| long switch_eg(long x, long y, long z) {
long w = 1;
switch (x) {
case 1:
w = y * z;
break;
case 2:
w = y / z;
/* Fall Through */
case 3:
w += z;
break;
case 5:
case 6:
w -= z;
break;
default:
w = 2;
}
return w;
}
|
1
2
3
4
5
| switch_eg:
movq %rdx, %rcx ; temp = z
cmpq $6, %rdi
ja .L8
jmp *.L4(,%rdi,8) ; goto *JTab[x]
|
| Register | Use |
|---|
%rdi | x |
%rsi | y |
%rdx | z |
%rax | 반환값(w) |
ja는 x의 값이 지정된 범위($0 \leq x \leq 6$)를 벗어난 경우 default(.L8)로 점프한다.jmp는 점프 테이블(.L4)을 통해 특정 코드 블록으로 점프한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| .section .rodata
.align 8
.L4:
.quad .L8 ; x = 0
.quad .L3 ; x = 1
.quad .L5 ; x = 2
.quad .L9 ; x = 3
.quad .L8 ; x = 4
.quad .L7 ; x = 5
.quad .L7 ; x = 6
.L3: ; case 1
movq %rsi, %rax ; w = y
imulq %rdx, %rax ; w *= z
ret
.L5: ; case 2
movq %rsi, %rax ; w = y
cqto
idivq %rcx ; w /= temp
jmp .L6
.L9: ; case 3
movl $1, %eax ; w = 1
.L6:
addq %rcx, %rax ; w += temp
ret
.L7: ; case 5, 6
movl $1, %eax ; w = 1
subq %rdx, %rax ; w -= z
ret
.L8: ; default
movl $2, %eax ; w = 2
ret
|
cqto는 %rax의 값을 128비트로 부호 확장하여 상위 64비트를 %rdx에, 하위 64비트를 %rax에 저장한다. (%rdx:%rax)idivq는 %rdx:%rax를 지정된 레지스터(%rcx)의 값으로 나누어 몫을 %rax에, 나머지를 %rdx에 저장한다.case의 최솟값이 0이 아닌 경우, 컴파일러는 바이어스(bias)를 추가하여 최솟값이 0이 되도록 조정한다.case 값이 분산되어 있는 경우, 컴파일러는 if-else 구문과 이진 탐색을 활용하여 로그 시간에 해결한다.
References