컴퓨터시스템 04: 기계 수준 프로그래밍 2: 제어문

글에 들어가기 앞서…

이 포스팅은 서울시립대학교 인공지능학과 백형부 교수님의 ‘컴퓨터시스템’ 강좌의 중간고사 이전 범위 수업 내용에 대한 정리를 담고 있습니다.

수업 자료 출처: Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, 3rd Edition

기계 수준 프로그래밍 II: 제어문

어셈블리 언어에서 제어문(조건문이나 반복문)을 다루는 것은 프로그램의 흐름을 제어하는 것을 의미합니다. 이는 일반적으로 분기 명령어와 점프 명령어를 사용하여 구현됩니다. 이러한 명령어들을 통해 프로그램은 특정 조건에 따라 코드의 다른 부분으로 이동하거나, 특정 코드 블록을 반복 실행할 수 있습니다.

제어문: 조건 코드

조건 코드란 CPU에서 연산의 결과에 따라 설정되는 특별한 플래그들을 말합니다. 이들은 프로그램의 흐름을 제어하는 데에 중요한 역할을 합니다. 구체적으로, 조건 코드는 CF(Carry Flag), ZF(Zero Flag), SF(Sign Flag), OF(Overflow Flag)의 네 가지로 구분됩니다. 이 플래그들은 연산의 결과에 따라 묵시적으로 설정되거나, 특정 명령어를 통해 명시적으로 설정될 수 있습니다.

1. CF(Carry Flag): 연산에서 최상위 비트를 넘어서는 캐리(또는 보로우)가 발생했는지를 나타냅니다. 주로 무부호 정수 연산에서 오버플로우를 검출하는 데 사용됩니다.

2. ZF(Zero Flag): 연산의 결과가 0인 경우에 설정됩니다. 주로 값의 비교 연산에서 사용되며, 결과가 0이라면 ZF는 1로 설정됩니다.

3. SF(Sign Flag): 연산 결과의 최상위 비트(부호 비트)를 나타냅니다. 이 플래그는 결과가 양수인지 음수인지를 나타내는 데 사용됩니다.

4. OF(Overflow Flag): 부호 있는 정수 연산에서 오버플로우가 발생했는지를 나타냅니다. 즉, 연산 결과가 해당 데이터 타입으로 표현할 수 있는 범위를 넘어섰는지를 검출하는 데 사용됩니다.

이러한 조건 코드들은 분기 명령어 등에서 조건 판별에 활용되어 프로그램의 흐름을 결정짓는 중요한 요소입니다. 예를 들어, 어떤 연산 후 ZF가 1로 설정된다면, 이는 연산 결과가 0임을 의미하며, 분기 명령어는 이 정보를 바탕으로 다음에 실행할 명령어를 결정할 수 있습니다.

묵시적 설정

addq는 어셈블리 언어에서 두 레지스터에 저장된 값을 더하는 연산을 수행합니다. 이 연산의 기본 목적은 명백하게 두 수의 합을 구하는 것입니다. 그러나 이 연산을 실행함으로써 여러 조건 코드들도 자동으로 변경됩니다. 이 조건 코드들은 연산의 결과에 따라 설정되며, 프로그램의 흐름을 제어하는 데에 사용될 수도 있고 그렇지 않을 수도 있습니다.

addq 명령어를 실행하면, 다음과 같은 조건 코드들이 묵시적으로 설정될 수 있습니다:

1. CF(Carry Flag): 연산의 결과에서 최상위 비트를 넘어선 캐리가 발생했는지 나타냅니다. 이는 무부호 정수 연산에서 오버플로우를 검출하는 데 사용됩니다.
2. ZF(Zero Flag): 연산의 결과가 0인 경우 설정됩니다. 값이 0인지 아닌지를 판별하는 데 사용됩니다.
3. SF(Sign Flag): 연산 결과의 최상위 비트(부호 비트)를 나타냅니다. 결과가 양수인지 음수인지를 나타내는 데 사용됩니다.
4. OF(Overflow Flag): 부호 있는 정수 연산에서 결과가 해당 데이터 타입으로 표현할 수 있는 범위를 넘어섰는지를 나타냅니다.

CF는 무보호 정수 연산에서의 오버플로우, OF는 부호 있는 정수 연산에서의 오버플로우를 검출합니다.

명시적 설정

묵시적 조건 코드 설정과는 달리, 명시적 조건 코드 설정은 프로그래머가 직접 조건을 지정하고 이에 따라 조건 코드를 설정하는 경우를 말합니다. 이런 명시적 설정을 수행하는 대표적인 어셈블리 명령어 중 하나가 cmpq입니다.

cmpq

cmpq 명령어는 두 값을 비교하고, 그 결과에 따라 CF(Carry Flag), ZF(Zero Flag), SF(Sign Flag), OF(Overflow Flag)를 다음과 같이 설정합니다:

1. CF(Carry Flag): 비교 연산에서 빼기를 수행했을 때 빼기의 결과가 캐리(또는 보로우)를 생성하면 CF가 설정됩니다. 이는 무부호 연산에서 첫 번째 피연산자가 두 번째 피연산자보다 작을 때 주로 발생합니다.

2. ZF(Zero Flag): 두 피연산자의 값이 동일하여 비교 연산의 결과가 0이 되면 ZF가 설정됩니다. 즉, 두 값이 같다는 것을 나타냅니다.

3. SF(Sign Flag): 비교 연산의 결과가 음수일 경우 SF가 설정됩니다. 이는 비교 연산의 결과가 부호 있는 정수로서 음수를 나타내는 최상위 비트가 1인 경우에 발생합니다.

4. OF(Overflow Flag): 비교 연산에서 빼기를 수행했을 때, 부호 있는 정수 연산에서 오버플로우가 발생하면 OF가 설정됩니다. 이는 연산의 결과가 해당 데이터 타입으로 표현할 수 있는 범위를 벗어났을 때 일어납니다.

cmpq 명령어를 사용함으로써, 프로그래머는 명시적으로 두 값을 비교하고, 비교 결과에 따라 조건 분기나 다른 조건 기반의 명령을 수행할 수 있습니다.

testq

testq 명령어는 어셈블리 언어에서 두 레지스터나 메모리 위치의 값을 비트 단위로 AND 연산을 수행합니다. 하지만 실제로는 두 피연산자의 값을 변경하지 않고, 연산 결과에 기반하여 플래그를 설정하는 데 주로 사용됩니다. 이 명령어는 주로 조건 분기 이전에 특정 비트 또는 비트 그룹의 상태를 검사하는 데 사용됩니다.

testq 명령어를 실행할 때, 주로 관심 있는 플래그는 ZF(Zero Flag)와 SF(Sign Flag)입니다. 이들은 다음과 같은 조건으로 설정됩니다:

1. ZF(Zero Flag): testq 연산의 결과가 0이면 ZF가 설정됩니다. 즉, 두 피연산자를 AND 연산했을 때 모든 비트가 0이라는 것을 의미하며, 이는 두 피연산자 간에 공통된 설정된(1인) 비트가 없음을 나타냅니다. 예를 들어, 특정 비트 패턴이나 플래그가 설정되어 있는지를 검사할 때 유용하게 사용될 수 있습니다.
2. SF(Sign Flag): testq 연산의 결과가 음수(즉, 결과의 최상위 비트가 1)일 경우 SF가 설정됩니다. 이는 AND 연산의 결과가 부호 있는 정수로 해석했을 때 음수임을 나타냅니다. testq 명령어의 경우, 두 피연산자 모두에서 해당 비트가 설정되어 있어야만 결과도 해당 비트가 설정될 수 있으므로, SF가 설정된다는 것은 두 피연산자 모두에서 최상위 비트가 1, 음수였음을 의미합니다.

조건 분기

어셈블리 언어에서 프로그램은 여러 블록으로 나누어 구성되며, 실행 흐름은 조건에 따라 다양한 블록으로 점프하면서 연산을 수행합니다. 이러한 점프를 가능하게 하는 명령어들을 ‘점프 코드(Jumping code)’라고 합니다. 점프 코드는 종종 명시적 조건 코드를 설정하는 명령어, 예를 들어 cmpq y, x와 같은 코드 바로 다음에 사용됩니다. 이때, 점프 조건은 cmpq 명령어의 두 번째 인자인 x를 기준으로 명명되며 해석됩니다.

예를 들어, jge 명령어는 x가 y보다 크거나 같은 경우에 해당 점프 코드로 점프합니다. 이러한 점프 명령어의 사용은 프로그램의 실행 흐름을 제어하는 데 매우 중요합니다. 주의해야 할 중요한 점은, cmpq 명령어에서 비교의 기준이 되는 변수가 명령어의 두 번째 인자라는 것입니다. 즉, cmpq y, x에서 x가 비교의 기준점으로 사용됩니다.

예시 01

이 어셈블리 코드는 두 정수의 절대 차이(absdiff)를 계산하는 함수입니다. 여기서 사용된 레지스터 %rdi와 %rsi는 함수에 전달된 첫 번째와 두 번째 인자를 저장하는 데 사용되며, %rax는 함수의 반환 값을 저장하는 데 사용됩니다. 코드를 단계별로 살펴보겠습니다

1. cmpq %rsi, %rdi
   • 이 명령어는 %rdi (x)와 %rsi (y)를 비교합니다. cmpq 명령어는 첫 번째 인자에서 두 번째 인자를 빼는 연산을 수행하며, 그 결과에 따라 플래그를 설정합니다. 여기서는 x와 y를 비교하고, 그 결과에 따라 ZF(Zero Flag), SF(Sign Flag) 등의 플래그를 설정합니다.
2. jle .L4
   • jle (Jump if Less or Equal)는 조건부 점프 명령어로, 비교 연산의 결과가 ‘작거나 같음’(Less or Equal)을 의미할 때 지정된 레이블(.L4)로 점프합니다. 즉, x가 y보다 작거나 같으면, 실행 흐름은 .L4 레이블로 점프합니다.
3. movq %rdi, %rax
   • 이 명령어는 %rdi의 값을 %rax로 복사합니다. 즉, x의 값을 반환 값 레지스터 %rax로 이동시킵니다.
4. subq %rsi, %rax
   • %rsi의 값을 %rax에서 빼서 %rax에 저장합니다. 이는 x - y 연산을 수행하고, 그 결과를 %rax에 저장합니다. 이 시점에서 x가 y보다 크다는 것이 이미 확인되었으므로, 이 연산의 결과는 절대 차이에 해당합니다.
5. ret
   • 함수에서 반환합니다. 이 시점에서 %rax에 저장된 값이 함수의 반환 값이 됩니다.
6. .L4:
   • 이 레이블은 x가 y보다 작거나 같은 경우에 실행됩니다.
7. movq %rsi, %rax
   • y의 값을 반환 값 레지스터 %rax로 복사합니다.
8. subq %rdi, %rax
   • x의 값을 %rax에서 빼서 %rax에 저장합니다. 이는 y - x 연산을 수행하고, 그 결과를 %rax에 저장합니다. 이 시점에서 x가 y보다 작거나 같다는 것이 이미 확인되었으므로, 이 연산의 결과는 절대 차이에 해당합니다.
9. ret
   • 함수에서 반환합니다. 이 시점에서 %rax에 저장된 값이 함수의 반환 값이 됩니다.

결론적으로, 이 코드는 x와 y의 절대 차이(|x - y|)를 계산하고 그 결과를 반환합니다. 조건부 점프를 사용하여 x와 y의 대소 관계에 따라 적절한 연산을 수행하고, 결과를 %rax 레지스터를 통해 반환합니다.

goto 코드로 표현하기

어셈블리 언어에서 조건 분기를 구현하는 방법은 C 언어의 goto 문을 사용하여 유사하게 표현할 수 있습니다. 어셈블리 언어의 점프 명령어를 이용한 조건 분기와 C 언어의 goto 문을 사용한 코드는 구조적으로 매우 유사합니다. 예를 들어, 어셈블리 언어의 분기 명령어를 통해 특정 조건이 만족될 때 코드의 다른 부분으로 점프하는 것과 같이, C 언어에서도 goto 문을 사용하여 프로그램의 실행 흐름을 명시적으로 제어할 수 있습니다.

어셈블리 언어 예시를 C 언어의 goto 문을 사용하여 표현한 것은, 어셈블리 언어의 점프 코드를 통한 조건 분기와 구조적으로 유사함을 보여줍니다. 변환된 어셈블리 코드와 비교해 볼 때, 두 언어 모두 조건에 따라 프로그램의 실행 흐름을 변경하는 유사한 코드 구조를 가지고 있다는 것을 확인할 수 있습니다.

이러한 유사성은 프로그래머에게 더 낮은 수준의 프로그래밍 언어(어셈블리 언어)와 더 높은 수준의 언어(C 언어) 사이의 개념적 연결고리를 제공합니다. 그러나, 실제 프로그래밍에서 goto 문은 프로그램의 가독성과 유지 보수성을 저하시킬 수 있으므로, 사용에 주의가 필요합니다.

이전에는 조건 분기를 위해 별도의 .L4 블록을 생성하여 사용했지만, 위의 어셈블리 코드는 cmovle 명령어를 이용해 별도의 블록 없이 같은 조건문을 구현합니다. cmovle는 조건부 이동(Conditional Move) 명령어로, 조건 코드를 참조하여 첫 번째 인자로 주어진 값을 두 번째 인자로 지정된 레지스터에 복사할지를 결정합니다. 여기서 mov는 이동(move)을 의미하고, le는 ‘less or equal’(이하)을 의미합니다. 따라서, 이 명령어는 cmpq에 의해 설정된 조건(두 번째 인자를 기준으로 한 비교)이 참일 경우에만 값을 이동합니다.

루프

루프는 프로그래밍 언어의 필수적인 구성 요소입니다. 아래에서는 이러한 루프를 어셈블리 언어에서 어떻게 구현하는지 살펴보겠습니다.

Do-While 루프

위 코드는 Do-While 루프의 동작을 Goto 문을 사용하여 구현한 예시입니다. 이 코드는 long 타입의 변수 x의 이진 표현에서 1로 설정된 비트의 개수를 세는 프로그램입니다. 이 구현에서 중요한 특징은 Goto 문이 루프의 내부에 위치하고 있으며, Goto 문이 지시하는 목표가 루프의 시작점이라는 점입니다. 이러한 구조를 통해서, 특정 조건이 만족될 때마다 이 루프를 계속해서 반복 실행될 수 있도록 합니다.

Goto 문을 어셈블리 코드로 변환하는 과정은 매우 직관적입니다. 이는 Goto가 어셈블리 언어의 점프 명령어와 직접적으로 대응되기 때문입니다.

결론적으로, Do-While 문은 위에서 설명한 바와 같이 Goto 문으로 변환될 수 있습니다.

While 루프

실제로 Do-While 문을 사용한 경험이 드물다고 느끼실 수 있습니다. 이는 Do-While 문이 특정한 비효율성을 내포하고 있기 때문입니다. 바로, 조건이 만족되지 않더라도 최소 한 번은 루프를 실행해야 한다는 점입니다. 이러한 특성 때문에 의도치 않은 에러가 발생할 가능성이 존재합니다. 따라서 대부분의 경우, 우리는 While 루프를 선호합니다. While 루프는 Do-While과 비교했을 때, 어셈블리 코드에서 약간의 차이를 보이며, 이는 실행 조건을 루프 실행 전에 검사한다는 점에서 기인합니다.

변환하는 방법 01

Goto 버전으로 변환한 코드를 살펴보면, 루프 실행 전에 조건문으로 직접 이동하는 구조를 볼 수 있습니다. 이와 같이 조건문 블록을 루프 아래에 배치하고, 처음에는 루프 블록을 실행하지 않고 바로 조건문 블록으로 이동함으로써, 조건을 먼저 검사합니다. 만약 조건이 만족되지 않는다면, 루프를 전혀 실행하지 않고 바로 다음 명령어로 넘어가는 구조입니다.

예시)

변환하는 방법 02

또한, While 루프를 If와 Do-While의 조합으로 해석할 수도 있습니다. 이 접근 방식에서는 Do-While이 Goto 문으로 변환되는 구조 이전에 조건문을 배치합니다. 이 조건문이 만족되지 않을 경우, Goto 문을 건너뛰어 루프의 실행을 생략하도록 설정합니다. 이 방법을 통해서도 While 루프를 효과적으로 변환할 수 있습니다.

예시)

For 루프

For 루프는 본질적으로 While 루프와 동일합니다. 차이점은 단지 변수의 초기화, 증감, 조건 확인을 통합하여 사용하기 편리하게 만든 문법일 뿐입니다. 따라서, For 문법을 While로 변환한 다음, 이를 Goto 문으로 다시 변환하면, 어셈블리 코드로의 변환이 간편해질 것입니다.

위 코드는 For 루프를 While으로 변환하는 방법 02를 사용하여, 루프 이전에 조건문을 배치한 예시입니다. 하지만, 이 변환 과정에서 사실상 루프 이전의 조건문은 불필요할 수 있습니다. 이는 조건문이 변수 i에 대한 것이기 때문인데, i가 처음부터 그 한계에 도달한 경우는 일반적으로 발생하지 않습니다(물론 그러한 상황을 설정할 수는 있겠지만, 대부분의 경우에는 그렇지 않습니다).

스위치

스위치 문은 변수의 값에 따라 다양한 조건 분기를 실행할 수 있게 해주는 프로그래밍 구조입니다. 위 코드가 어셈블리 언어에서 어떻게 구현될 수 있는지 살펴보겠습니다.

스위치 문을 구현할 때, 종종 점프 테이블이 사용됩니다. 점프 테이블은 스위치 문의 각 케이스에 해당하는 연산을 수행할 코드 블록의 주소를 모아놓은 데이터 구조입니다. 즉, 스위치 문에 주어진 변수의 값에 따라 점프 테이블에서 해당하는 코드 블록의 주소로 점프하여 실행하는 방식으로 동작합니다.

이 예제에서는 switch_eg라는 함수의 어셈블리 코드를 보여줍니다. 먼저, %rdx의 값을 %rcx로 이동시킵니다. 그 다음, $6과 %rdi를 비교하는 cmpq 명령어를 사용하여, %rdi가 6을 초과하는지 확인합니다. 만약 6을 초과한다면 .L8으로 점프합니다. 이는 switch 문이 6 이하의 케이스만을 고려한다는 것을 의미합니다. 변수가 6 이하의 값일 경우, 점프 테이블인 .L4로 점프합니다. 여기서, *.L4(,%rdi,8) 구문은 점프 테이블의 주소 계산에 사용되며, %rdi 값에 8을 곱한 결과에 .L4의 시작 주소를 더해 해당 주소로 점프하라는 의미입니다.

함수 내에서 long w = 1;로 w에 대한 초기 할당이 이루어지지만, 실제 어셈블리 코드에서는 w에 대한 명시적인 할당이 없습니다. 이는 컴파일러 최적화 과정에서 w의 할당이 케이스별로 필요하지 않을 수 있다고 판단되었기 때문입니다. 예를 들어, 어떤 케이스에서는 w += 1이 필요할 수 있고, 다른 케이스에서는 w = x * y와 같이 w를 직접 계산해야 할 수 있습니다. 이러한 경우, w를 미리 1로 설정하는 대신, 각 케이스에서 필요에 따라 w를 직접 계산하거나 할당하게 됩니다.

점프 테이블은 x의 값에 따라 다른 명령문을 가리키는 구조를 가집니다. x의 값에 해당하는 명령문이 가리키는 코드 블록으로 이동합니다.

switch_eg 함수와 그에 해당하는 어셈블리 코드를 살펴보면, w의 초기값 설정이 특정 상황에 한정되어 이루어짐을 확인할 수 있습니다. 이는 함수 내에서 long w = 1; 로 w를 초기화하는 코드와 달리, 어셈블리 코드에서는 w의 값이 모든 경우에 1로 설정되지 않는다는 것을 의미합니다.

• x가 0일 경우, .L8로 이동하여 eax에는 2가 할당됩니다. 이는 스위치 문의 default 케이스에 해당하며, 여기서 w = 1이라는 초기화는 필요 없습니다.

• x가 1일 경우, .L3에서 y와 z를 곱한 결과가 직접 rax에 저장됩니다. 이 경우에도 w = 1의 초기화는 별도로 이루어지지 않습니다.

• x가 2일 경우, .L5와 .L6을 통해 연산이 수행됩니다. 특히, case 2에서 case 3으로 넘어가는 “Fall Through” 과정에서 w의 초기값을 1로 설정하는 대신, 바로 연산에 들어갑니다.

• x가 3일 경우, .L9에서 eax에 1을 할당하는 것을 볼 수 있습니다. 이는 w += z 연산을 수행하기 전에 w의 값을 1로 설정해야 하는 상황에 해당합니다.

• x가 5 또는 6일 경우, .L7에서도 eax에 1이 할당됩니다. 이는 w -= z 연산을 수행하기 전에 w의 초기값을 설정해야 하는 경우입니다.

결론적으로, 어셈블리 코드에서 w의 값이 1로 설정되는 것은 특정 연산을 수행하기 직전에만 이루어집니다. 이는 컴파일러 최적화 과정에서 불필요한 할당을 줄이기 때문입니다.