시스템 프로그래밍 노트 4 - 상태 코드
상태 코드와 관련된 어셈블리 Instructions과 c에서 루프가 어셈블리어로 어떻게 구현되는지 살펴본다.
1. 프로세서 상태
- %rsp는 stack의 위치이다. 이와 관련해서는 다음 노트에서 다룬다.
- %rip는 프로그램 카운터, 즉 현재 실행되고 있는 코드의 위치를 가리키는 레지스터이다.
- CF, ZF, SF, OF의 Condition Codes가 존재한다.
1.1. Condition Codes
단일 비트 레지스터이다.
CF
는 Carry Flag로, unsigned overflow가 일어났을 때 설정된다. 즉, MSB가 튀어나오고 버려지면 1이 된다.ZF
는 Zero Flag로, 0일 때 설정된다.SF
는 Sign Flag로, 음수일 때 설정된다.OF
는 Overflow Flag로, signed overflow가 일어났을 때 설정된다. 예를 들어t=a+b
를 수행할 때 다음을 확인한다:(a> 0 && bb >0 && t<0) || (a<0 && b<0 && t>=0)
condition codes를 변경하는 경우에 대한 설명은 다음과 같다:
- 대부분의 어셈블리 명령 이후에 condition이 설정된다. 단,
leaq
은 예외적으로 무시한다. cmpq
와 같은 비교 명령에 대해서는cmpq b,a
를 한다면a-b
에 대해 flag를 설정한다.testq
에 대해서는testq b,a
을 한다면a&b
에 대해 flag를 설정한다. 이 명령은 한쪽이 mask가 될 때 주로 사용된다.- testq %rax, %rax 후 je가 자주 사용된다. %rax가 0인지 체크하고 맞으면 %rip를 이동시킨다.
2. Instructions Based On Condition Codes
2.1. SetX
setX Dest
의 형태로 사용된다. condition codes에 따라 dest의 마지막 바이트를 0이나 1로 변경한다. 나머지는 건들지 않는다.
SetX | Condition | Description |
---|---|---|
sete | ZF | Equal |
setne | ~ZF | Notequal |
sets | SF | Negative |
setns | ~SF | Nonnegative |
setg | ~(SF^OF)&~ZF | Greater (Signed) |
setge | ~(SF^OF) | Greater of Equal (Signed) |
setl | (SF^OF) | Less (Signed) |
setle | (SF^OF) | ZF | Less or Equal (signed) |
seta | ~CF&~ZF | Above (unsigned) |
setb | CF | Below(unsigned) |
하위 1바이트만 변경하기 때문에 그것에만 집중하는 레지스터가 많이 사용된다. 예를 들면
cmpq %rsi, %rdi
setg %als
movzbl %al, %eax ;movzbl is the instruction for zero extending byte to 32bits.
ret
2.2. jX
jX Dest
의 형태로 사용된다. condition codes에 따라 program counter를 Dest로 변경시킨다.
jX | Condition | Description |
---|---|---|
jmp | 1 | Unconditional |
je | ZF | Equal |
jne | ~ZF | Not Equal |
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) |
팁
다음 노트에서 다루겠지만 여기에서 다루는 아키텍쳐에서는 함수에 인자를 전달할 때 레지스터를 통해 전달한다.
%rdi, %rsi, %rdx
가 순서대로 첫 번째 인자, 두 번째 인자, 세 번째 인자이다.
3. Implementing Conditional Branches
goto는 코드를 읽고 디버깅하기 힘들기 때문에 나쁜 코드 스타일이다. 코드의 control flow를 설명할 때만 여기서는 사용될 예정이다.
if contidion
result = expr1;
else
result = expr2;
return result
3.1. Conditional Control
전통적인 방법으로, 위 코드를 이 방식으로 컴파일할 때 동등한 goto 코드는 다음과 같다.
ncondition = !condition;
if ncondition goto Else;
result = expr1;
goto Done;
Else:
result = expr2;
Done:
return result;
와 같다. 이 형태의 control flow에서 어셈블리를 까보면 cmpX, jX
의 (un)conditional jump 명령이 포함되고 각 if, else에 대해 코드 영역이 분리되어 있다.
3.2. Conditional Move
하지만 현대 프로세서에게 더 효율적인 형태는 conditional move이다.
result = expr1;
result_ = expr2;
ncondition = !condition;
if (ncondition) result = result;
return result;
로, conditional move 명령을 통해 더 좋은 성능을 보여준다. 어셈블리로 까보면 jX
대신에 cmovX
명령이 사용된다. condition codes에 기초하여 mov 명령을 수행한다. 더 효율적인 이유는 대충 조건과 관계없이 실행할 수 있는 명령이 많기 대문이다. 하지만 무조건 좋다고 볼 수는 없는게,
-
각 expr을 계산하는데 비용이 많이 든다.
- 어떤 expr은 조건이 성립되지 않으면 위험하다.
val = p ? *p : 0
- 계산을 할 때 예측하지 못한 부가 효과가 생긴다.
val = x > 0 ? x*=7 : x+=3
4. Implementing Loops (While, For, …)
4.1. Do-While
Do-While 문은 루프를 만들어 루프 끝에서 조건을 체크하고, 조건이 맞으면 다시 되돌아가는 형태이다.
long pcount_do(unsigned long x) {
long result = 0;
do {
result += x & 0x1;
x >>= 1;
} while (x);
return result;
}
long pcount_goto(unsigned long x) {
long result = 0;
loop:
result += x & 0x1;
x >> =1;
if (x) goto loop;
return result;
}
; %rdi is x, %rax is result
pcountdo_do:
xor %rax, %rax ; movl $0, %eax
.L1:
movq %rdi, %rdx
andq $1, %rdx
addq %rdx, %rax
shrq $1, %rdi ; can be replaced to shr %rdi
jne .L1
ret
4.2. While
while (Test)
Body
오히려 while 문이 어셈블리 레벨에서는 더 복잡한데, 두 가지 방법이 존재한다. 각 방법의 이름은 gcc에서 컴파일할 때 주는 flag를 의미한다.
4.2.1. -Og Translation
jump-to-middle. 조건을 체크하는 부분으로 먼저 가버린다.
goto test;
loop:
Body
test:
if (Test)
goto loop;
done:
4.2.2. -O1 Translation
초기 상태를 확인하고 do-while을 사용한다.
In Do-While,
if (!Test)
goto done;
do
Body
while (Test);
done:
In Goto,
if (!Test)
goto done;
loop:
Body
if (Test)
goto loop;
done:
4.3. For
for (Init; Test; Update)
Body
는 While 버전으로 바꿀 수 있다:
Init;
while (Test) {
Body
Update
}
또한 Do-While로 바꿀 수도 있는데 예를 들면 다음과 같다:
long pcount_for(unsigned long x){
size_t i;
long result = 0;
for (i = 0; i < WSIZE; i++)
{
unsigned bit = (x >> i) & 0x1;
result += bit;
}
return result;
}
long pcount_for(unsigned long x){
size_t i = 0;
long result = 0;
if (!(i < WSIZE))
return result;
do{
unsigned bit = (x >> i) & 0x1;
result += bit;
i++;
} while (i < WSIZE);
return result;
}
경우에 따라 초기 테스트는 생략 가능하기도 하다. 결국 while을 초기 조건 확인 + do-while 문으로 생각하는 -O1 Translation을 거친 결과다.
5. Switch Statement
동시에 여러 조건을 확인하는 경우 if-else를 계속 사용하는 것보다 switch-case 문이 효율적이다.
long switch_eg (long x, long y, long z){
long w = 1;
swith(x) {
case 1:
w = y*z;
break;
case 2:
w = y/z;
case 3:
w += z;
break;
case 5:
case 6:
w -= z;
break;
default:
w = 2;
}
return w;
}
이런 식으로 생겼고, 어셈블리에서는 Jump Table을 통해 관리된다. 루프 포인터를 한 번에 모아서 x값에 따라 서로 다른 루프로 대응시킨다.
.section .rodata
.align 8
.L4:
.quad .L8
.quad .L3
.quad .L5
.quad .L9
.quad .L8
.quad .L7
.quad .L7
switch_eg:
movq %rdx, %rcx ;backup.
cmpq $6, %rdx
ja .L8
jmp *.L4(,%rdi, 8)
.L3:
movq %rsi, %rax
imulq %rdx, %rax
ret
.L5:
movq %rsi, %rax
cqto ; sign extend %rax into octaword %rdx:%rax
idivq %rcx ; signed divide %rdx:%rax by %rbx. q in %rax, r in %rdx
jmp .L6
.L9:
movq $1, %rax
.L6:
addq %rcx, %rax
ret
.L7:
movq $1, %rax
subq %rcx, %rax
ret
.L8:
movq $1, $rax
ret
Leave a comment