시스템 프로그래밍 노트 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로 변경한다. 나머지는 건들지 않는다.

하위 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로 변경시킨다.

팁

다음 노트에서 다루겠지만 여기에서 다루는 아키텍쳐에서는 함수에 인자를 전달할 때 레지스터를 통해 전달한다.

%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