CPU의 register에는 앞선 게시물에서 작성했던 64-bit size의 register 외에도 single bit condition code가 존재합니다. x86-64 architecture에는 다음과 같은 4가지 condition code가 있습니다.
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 |
---|---|---|
sete | ZF | Equal / Zero |
setne | ~ZF | Not equal / 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) |
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 |
---|---|---|
jmp | ZF | Equal / Zero |
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) |
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을 수행하게 될 것입니다.
assembly에서 loop의 구현은 앞선 conditional branch를 활용합니다. loop의 condition을 check하는 부분을 condition code로 확인해 조건이 맞는 경우 loop의 맨 앞으로 jump하는 형태로 구현할 수 있습니다. c의 loop는 do-while
, while
, for
의 세 가지 형태가 존재하며, 각각이 어떻게 assembly로 작성되는지 확인해보겠습니다.
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의 .L2
와 jne
instruction으로 대응시킬 수 있습니다.
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
구문은 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