[System Programming] 2. Machine Control

윤호·2022년 10월 15일
0

System Programming

목록 보기
3/7
post-thumbnail

Condition codes

CPU의 register에는 앞선 게시물에서 작성했던 64-bit size의 register 외에도 single bit condition code가 존재합니다. x86-64 architecture에는 다음과 같은 4가지 condition code가 있습니다.

  • CF: carry flag. arithmetic operation에 의해 발생하는 MSB(Most Significant Bit)의 carry/borrow out을 감지. unsigned overflow를 감지하기 위한 flag
  • ZF: zero flag. operation의 결과가 zero인 경우를 감지.
  • SF: sign flag. operation의 결과가 negative value인 경우를 감지.
  • OF: overflow flag: 2's complement operation의 arithmetic operation에 의해 발생하는 overflow를 감지.

condition codes는 implicit, explicit하게 setting될 수 있습니다. implicit하게 setting되는 경우는 arithmetic operation이 진행된 이후입니다. 예를 들어, t = a + b의 operation이 진행된다고 했을 때, t == 0이면 ZF가, t < 0이면 SF가, overflow가 발생하면 a, b의 data type에 따라 CF, OF가 setting됩니다.

explicit하게 setting은 compare instruction이 수행될 때 진행됩니다. 예를 들어, cmpq b, a instruction은 a - b 연산이 수반되는 logical operation이므로 해당 연산의 결과에 맞는 condition code setting이 진행됩니다. 또 주로 사용되는 instruction으로 두 operand의 and 연산을 진행하는 testq b, a가 있으며 특히 testq %rax, %rax와 같이 %rax의 value가 0인지 check하기 위해 주로 사용합니다.

Condition codes는 set instruction을 이용해 explicit하게 read할 수도 있습니다. setX Dest instruction은 condition code를 Dest의 low-order byte에 저장합니다. setX instruction의 종류는 다음과 같습니다.

setX
condition
description
seteZFEqual / Zero
setne~ZFNot equal / Not zero
setsSFNegative
setns~SFNonnegative
setg~(SF^OF)&~ZFGreater (signed)
setge~(SF^OF)Greater or Equal (signed)
setlSF^OFLess (signed)
setle(SF^OF) | ZFLess or Equal (signed)
seta~CF&~ZFAbove (unsigned)
setbCFBelow (unsigned)

Conditional branches

x86-64 architecture에서 conditional branch에는 jX instruction을 사용합니다. jump는 condition code의 값에 따라서 code의 다른 부분으로 %rip를 바꾸는 역할을 합니다. jX address의 형식으로 작성하며 해당 jX instruction에 해당하는 condition code가 1이면 해당 code로 jump하고 그렇지 않으면 다음 code line을 수행합니다. jX instruction의 종류는 다음과 같습니다.

jX
condition
description
jmpZFEqual / Zero
jeZFEqual / Zero
jne~ZFNot equal / Not zero
jsSFNegative
jns~SFNonnegative
jg~(SF^OF)&~ZFGreater (signed)
jge~(SF^OF)Greater or Equal (signed)
jlSF^OFLess (signed)
jle(SF^OF) | ZFLess or Equal (signed)
ja~CF&~ZFAbove (unsigned)
jbCFBelow (unsigned)

condition code와 conditional branch의 이해를 돕기 위해 example을 보겠습니다. 아래 c code는 x와 y의 차이를 구하기 위한 code이며 이를 assembly code로 만들면 그 아래의 code와 같이 나타납니다.

long absdiff(long x, long y) {
	long result;
    if (x > y) result = x - y;
    else result = y - x;
    return result;
}
absdiff:
	cmpq	%rsi, %rdi	# x:y
    jle		.L4
    movq	%rdi, %rax
    subq	%rsi, %rax
    ret
.L4:		# x <= y
	movq	%rsi, %rax
    subq	%rdi, %rax
    ret

실제로는 return 구문 하나로 나타나는 것이 일반적이지만, 이해를 돕기 위해 naive하게 작성했습니다. c에서는 주석을 // 뒤에 작성하는 것과 달리 assembly file에서는 # 뒤에 작성하는 것을 유의하고 보겠습니다. assembly code에서 cmpq instruction을 수행하면 %rsi%rdi의 value에 따라 condition code가 결정될 것입니다. 이후 jle instruction에서 위의 표에서의 definition에 나타낸 condition code가 1인 경우 .L4로 jump할 것이고, 그렇지 않은 경우 그 다음 line을 수행하게 될 것입니다.


Loop

assembly에서 loop의 구현은 앞선 conditional branch를 활용합니다. loop의 condition을 check하는 부분을 condition code로 확인해 조건이 맞는 경우 loop의 맨 앞으로 jump하는 형태로 구현할 수 있습니다. c의 loop는 do-while, while, for의 세 가지 형태가 존재하며, 각각이 어떻게 assembly로 작성되는지 확인해보겠습니다.

Do-While loop

do-while loop는 구문의 형태가 goto와 매우 유사합니다. 아래 code는 동일한 것을 c code, goto version, assembly로 나타낸 것입니다.

// C code
long pcount(unsigned long x) {
	long result = 0;
    do {
    	result += x & 0x1;
        x >>= 1;
    } while (x);
    return result;
}
// goto version
long pcount(unsigned long x) {
	long result = 0;
loop:
    result += x & 0x1;
    x >>= 1;
    if(x) goto loop;
    return result;
}
pcount:
	xorq	%rax, %rax	# result
    .L2					# loop:
    movq	%rdi, %rdx
    andl	$1, %edx	# t = x & 0x1
    addq	%rdx, %rax	# result += t
    shrq	%rdi		# x >>= 1
    jne		.L2			# if(x) goto loop
    ret

assembly와 goto 구문을 비교하면 매우 유사함을 확인할 수 있습니다. goto의 loop:if 문이 각각 assembly의 .L2jne instruction으로 대응시킬 수 있습니다.

While

while문의 경우 goto와는 다르게 처음부터 condition check를 진행해야 합니다. 따라서 goto version으로 변형 시 중간에 test point를 설정해 loop 시작 지점에서 해당 지점으로 jump하는 구문이 필요합니다. 이를 code로 표현하면 다음과 같습니다.

// c code
long fact(long n) {
	long result = 1;
    while (n > 1) {
    	result *= n;
        n = n - 1;
    }
    return result;
}
// goto version
long fact(long n) {
	long result = 1;
    goto test;
loop:
	result *= n;
    n = n - 1;
test:
	if (n > 1) goto loop;
    return result;
}
fact:
	movl	$1 %rax		# result
    jmp		.L5			# goto test
    .L6					# loop:
    imulq	%rdi, %rax	# result *= n
    subq	$1, %rdi	# n = n - 1
    .L5					# test:
    cmpq	$1, %rdi	# compare n:1
    jg		.L6			# if(n > 1) goto loop
    ret

앞의 do-while과는 다르게 loop의 시작부터 test:로 jump하는 것을 볼 수 있습니다. condition check를 먼저 확인하는 것으로 loop를 시작하기 위해 다음과 같은 code가 작성되는 것을 볼 수 있습니다.

For

for 구문은 loop에 initialize, test, update가 모두 혼합되어 있는 형태로 작성됩니다. 여기서 initialize는 loop에 들어가기 이전에 먼저 진행하는 것으로 구현이 가능하며, test는 while과 마찬가지로 test point 설정을 통해 구현할 수 있습니다. 또한 update 구문은 test 지점 직전에 추가함으로써 loop body가 모두 수행된 이후에 update가 진행되고 이를 기반으로 test가 진행될 수 있도록 작성할 수 있습니다. 즉, 기본적인 뼈대는 while과 동일하고 적절한 위치에 init, update가 추가된 형태로 볼 수 있어 while과 비슷하게 구현이 가능합니다.


Reference
Computer System: A Programmer's Perspective, 3rd ed (CS:APP3e), Pearson, 2016

0개의 댓글