[CS] Instructions III(Control Flow) - Computer System 3rd Edition by Bryant

Status Register

CPU에는 Status Register, PSW라는 아주 작은 레지스터를 지니고 있다.

이는 CPU의 current status를 저장하기 위한 레지스터이다. 

CPU는 이 레지스터를 통해 코드의 flow를 Control하게 된다.

Status Register는 인텔 x86 아키텍쳐에서는 Condition Code를 저장한다고 한다.

Condition Code는 Single Bit으로서 이를 통해 flag를 저장한다. 

이 Flags들은 operation의 결과에 따라 set된다.

일반적으로 많이 알려진 Condition Code에는

CF	Carry Flag
ZF	Zero Flag
SF	Sign Flag
OF	Overflow Flag

등이 존재한다. 앞선 포스팅에 나와있는 레지스터 말고 %eflags라는 레지스터에 이 상태들이 저장이 되는 것이다.

Condition Code에 대해 조금 더 자세히 알아보자면, 먼저 add B, A라는 instruction이 존재한다고 가정을 해보자.

임시적인 결과를 t = A + B라고 한다면 Condition Code는 이 연산 결과에 대한 flag를 레지스터에 저장을 하는 것이지, 결과값 자체에는 관심이 없다.

CF가 set되는 경우는 MSB에서 Carry가 발생했을때 set된다. 이는 당연하게도 unsigned overflow를 detect할 수 있다.

ZF가 set되는 경우는 t == 0일때 set된다.

SF는 t < 0일때 set 된다.

OF는 2의 보수체계, 즉 signed연산에선의 overflow가 났을 때 set된다.

 

Compare Instruction

cmp b, a

위의 instruction은 Condition Code를 명확하게 set할 수 있는 instruction이다.

cmp라는 말을 보아도 당연히 비교를 하는 것이다.

하지만 컴퓨터는 0과 1의 데이터만 저장하고 있을 뿐 추가적인 데이터를 저장하고 있지 않다.

따라서 컴퓨터는 어떤 값이 더 크다는 정보를 뺄셈을 통해 대소를 파악하게 된다.

비교연산은 a - b의 결과값을 특정 dst에 저장하지 않고 Condition Code만 set해주는 극단적인 instruction이다.

만약 a와 b가 같다면 Condition Code에는 ZF, 즉 Zero Flag가 저장이 될 것이다.

만약 결과가 작은 경우에는 (SF&~OF)|(~SF&OF), 즉 SF^OF 가 될것이다.

작거나 같은 경우에는 XOR한 결과에 ZF인지 OR연산만 해주면 되기 때문에 (SF^OF) | ZF가 될 것이다.

반대로 더 큰경우에는 ~((SF^OF)|ZF)가 될것이다. 

각 Flag들이 의미하는 바를 생각을 하면 왜 이렇게 되는 것인지 알 수 있을 것이다.

 

test b, a

물론 Condition Code를 set해주는 instruction에는 cmp instruction만 있는 것은 아니다.

test instuction은 단순히 a & b의 결과를 다른 dst에 저장하는 것이 아닌 ZF Flag 혹은 SF Flag를 설정해준다.

ZF Flag는 a와 b가 서로 같을 때, SF Flag는 a&b < 0일때 set 된다.

보통 test %rax, %rax를 해서 unconditional branch를 만들거나 다른 레지스터와의 비교를 통해 flow를 control하게 된다.

 

위의 두 개의 instruction도 앞서서 살펴본 instruction처럼 Byte단위로 연산을 할 수도 있다는 사실을 명심하자.

 

Using Condition Codes

Condition Code들을 set하는 방법을 알아보았으니 이제 이 Condition Code들을 활용을 해야한다.

대표적으로는 jmp, set, cmov 등의 instruction들이 사용이 된다.

jmp는 다른 instruction의 주소를 이동할 수 있게 해주고, 

set은 byte를 conditional하게 0 혹은 1로 set해주며,

cmov는 conditionally하게 data를 이동시킨다.

 

어떤 말인지 감이 잘 오지 않을 수 있으므로, 코드를 보면서 이해를 해보자.

long func1(long temp) {
    if (temp > 1) return 1;
    return 0;
}

간단한 코드이면서 어셈블리도 그렇게 복잡하지 않다.

먼저 우선적으로 수행해야 할 것은 temp - 1을 하는 것이다.

만약 결과가 작다면, if문의 body를 탈출을 하게 된다.

if문의 body를 수행하고, 빠져나온다.

 

이를 간단하게 assembly로 작성한다면, 아래와 같이 assembly가 작성될 것이다.

cmp &0x1, %rdi
jle ~~~~~~(body의 바깥 부분의 주소)

못보던 instruction이 하나 생겼는데 jle (jump less or equal)는 같거나 작은 경우에 그 주소로 jump하라는 의미이다. 

그래서 이게 말이 되는 것이다. 컨디션 코드가 작거나 같은 경우에는 if문의 body 부분을 수행하는 것이 아니라 벗어 나가 다른 instruction을 수행한다. 조금은 헷갈릴 수도 있겠지만, 주어진 코드의 반대의 개념이라고 생각하면 이해하는데에 있어서 조금은 용이할 것이다. 

위에 적어본 assembly코드는 완벽하지 않다. 실제로 각각의 body 부분을 수행하는 부분도 적혀있지 않고, 이동해야하는 주소도 적혀있지 않다. 임의로 이를 설정해서 적어보면 아래처럼 적을 수 있다.

순서대로 다시 flow를 따라가보자. 먼저 rdi 레지스터가 temp라고 가정을 하면 temp와 1은 cmp연산을 통해 비교하게 되고, 비교의 결과는 Status Register에 저장이 된다. 

jle는 그 Status를 읽어 어디로 이동해야할지 판단을 한다. 만약 Condition에 맞는 경우에는 밑으로 코드를 진행한다.

그것이 아니라면, 즉 Condition Code가 less or equal이라면 0xc의 주소로 이동하게 된다. 

조건과 맞지 않아 0xc로 이동했다고 해보자. %rax 즉 %eax는 return value를 담는 레지스터이다. 따라서 숫자 0을 eax레지스터에 전달하고 0x11에서는 return을 하게 된다.

조건에 맞은 경우에는 숫자1을 eax 레지스터에 담고 return하게된다.

 

이해가 되었다면 다행이지만 다른 코드를 통해 조금 더 이해해보자. 이번에는 if ~ else문이다.

long func2(long x, long y) {
    long result;
    if (x > y) result = x + y;
    else result = x - y;
    
    result = 6 * result;
    return result;
}

x가 %rdi, y가 %rsi, result가 %rax라고 가정을 해보자. 임의로 작성한 assembly 코드는 아래와 같다.

마찬가지로 코드를 한번 따라가보자.

먼저 x-y를 통해 cmp operation을 수행한다.

먼저 else 부분을 보게 되면 0xd의 주소로 이동하게 된다. 이때 x - y를 수행하고,

다음 instruction에서는 6배 해준 값을 rax에 저장해 return한다.

이번에는 성공하는 경우를 보자. 우선 x + y를 해주고, rsi로 컨트롤 해주기 위해 값을 복사한다.

그 다음에는 jmp를 통해 0x10으로 이동하게 된다. 이러한 unconditional jump가 필요한 이유는 만약 이 코드가 없다면 sub %rsi, %rdi 코드가 무지성으로 수행이 될 것이다.

불상사를 막기 위해서는 else 부분의 코드를 지나친 다음 6배를 하는 코드로 이동시켜줘야 하기 때문에 jmp instruction을 수행한다. 이렇게 무조건적인 jmp를 unconditional jump라고 한다.

 

주소를 무조건적으로 메모리로 적어야하는 것은 아니다. (실제 위 코드도 64bit으로 적었어야하는데 32bit으로 적었다)

Symbolic Label을 사용해서 이를 간소화 해줄 수 있다.

Symbolic Label은 너무나도 긴 주소를 대체해주는 것으로 생각하면 되겠다. 

책에 있는 예시를 가져왔다. .L1이라는 주소로 명시적으로 코드의 가독성을 위해 사용이 된다.

    movq $0, %rax
    jmp .L1
    movq (%rax), %rdx
.L1:
    popq %rdx

Various Jumps

jle 뿐만 아니라 jump operation에는 다양한 operation들이 존재한다.

그도 그럴것이 Condition Code가 4개나 있는데 이를 조합해서 만들 수 있는 경우가 많기 때문이다.

Loop에 들어가기 전에 아래의 표를 보고 jump instruction들을 보고 들어가는 것이 좋을 것 같아 정리했다.

Loops

While(do-while)

do-while을 먼저 살펴보는 이유는 이 구조가 매우 간단하기 때문이다. do-while의 구조는 body를 먼저 수행한 이후에 조건을 비교해서 loop을 빠져나올것인지 결정을 하게된다. 아래의 코드와 어셈블리를 통해 이를 살펴보자.

long func3(long cnt) {
    do {
    	cnt--;
    } while(cnt > 10);
    return 2 * cnt;
}

이쯤되었으면 슬슬 감이 올거라고 생각이 된다. 

sub말고 decq를 사용할 수도 있지만 가독성을 위해 사용했고, 2배 해주는 부분은 shl을 사용해줘도 되지만 그렇게 되면 추가적인 instruction 개수가 늘어나 lea를 사용했다.

cmp를 통해 여전히 값이 10보다 크면 다시 loop으로 돌아가게 된다.

While

반면에 while문은 조건을 먼저 확인하는 작업을 하고서야 body에 들어가기 때문에 instruction의 개수가 늘어난다.

long func4(long cnt) {
    while(cnt > 10) cnt--;
    return 2 * cnt;
}

For

for문은 while문보다는 조금 복잡하다. 

기본적으로 for문은 조건체크 - body 수행 - iterator handle 이런 순으로 코드가 작동한다.

먼저 arr의 시작 주소를 %rdi, n은 %rsi, local i는 %rdx에, return value는 %rax에 있다고 하자.

long func5(long arr[], long n) {
    long total = 0, i = 0;
    for (i; i < n; i += 2) {
    	total += arr[i];
    }
    return total - 1;
}

코드가 많이 복잡하지만 같이 따라가보면 이해가 될 것이다. 

rdx, rax 즉 i와 return value를 먼저 초기화해준다. 

그 다음 0x14로 들어가서 조건을 확인한다. 만약 i값이 n보다 작다면 다시 0xc로 이동해서 body를 수행한다.

이때 rdx에 왜 8을 곱하냐고 의문이 들 수 있는데, 우리가 앞서서 배운 배열을 생각하면 쉽게 이해가 된다.

현재 배열은 long type, 즉 8byte이다. 그런데 i는 constant이기 때문에 실제 메모리에서 상수 바이트만큼 이동하면 segmentation fault등의 메모리 관련 에러가 날 것이다. 

따라서 이를 해당 매열에 맞는 사이즈를 곱해주어 indexing해야한다. 

다시 돌아와서 arr[i]값을 return value에 계속 더해주고 +=2 작업을 수행해준다. 

이 작업을 계속 반복해주기 위해 다시 조건을 비교해준다. 

마지막으로 rax에 저장되어 있는 값에서 1을 빼준 후 return해준다.

 

Wrapping Up

assembly는 매우 어렵다. 그러나 asssembly를 공부하는 것은 매우 중요하다.

이를 통해서 register 최적화에 대해서 고민해볼 수 있고, 현재 컴퓨터구조론을 risc-v로 배우고 있는데,

시스템프로그래밍에서 공부한 assembly가 정말 많은 도움이 되었다.

천천히 코드를 하나하나 뜯어가면서 공부를 하다보면 이해가 될 것이다.

 

Reference

Randal E. Bryant, & David R. O’Hallaron. (2016). Computer Systems A Programmer’s Perspective Third edition. Carnegie Mellon University: Pearson.