[JUNGLE] TIL_15. CSAPP 3.5 ~ 3.6

3.5 산술 및 논리 연산

x86-64의 주요 정수 및 논리 연산 명령어들은 대부분 다양한 크기의 피연산자를 처리할 수 있는 명령어 클래스(instruction classes)로 제공됩니다.

예를 들어, add 명령어 클래스는 데이터 크기에 따라 1바이트를 더하는 addb, 2바이트를 더하는 addw, 4바이트를 더하는 addl, 8바이트를 더하는 addq 네 가지 변형을 가집니다.

이러한 연산 명령어들은 기능에 따라 크게 네 그룹으로 나눌 수 있습니다.

1. 유효 주소 로드 (Load Effective Address): leaq
2. 단항 연산 (Unary Operations): 피연산자가 하나인 연산 (예: inc, dec, neg, not)
3. 이항 연산 (Binary Operations): 피연산자가 두 개인 연산 (예: add, sub, imul, xor, or, and)
4. 시프트 연산 (Shifts): 비트를 이동시키는 연산 (예: sal, sar, shl, shr)

3.5.1 유효 주소 로드 (Load Effective Address)

leaq (Load Effective Address) 명령어는 movq 명령어의 특별한 변형입니다.

1. 핵심 동작: 메모리 접근 없는 주소 계산

leaq는 메모리에서 데이터를 읽어오는 명령어처럼 보이지만, 실제로는 메모리에 전혀 접근하지 않습니다.

대신, 첫 번째 피연산자(소스)에 명시된 주소 계산식만 수행하여, 그 결과로 나온 '유효 주소(Effective Address)' 자체를 두 번째 피연산자(목적지 레지스터)에 저장합니다.

leaq S, D → D ← &S (S의 주소를 D에 저장하라)

비유: 내비게이션 경로 계산 🗺️

• movq (%rax), %rbx: "내비게이션(%rax)에 찍힌 주소로 실제로 찾아가서 물건(데이터)을 가져와라."
• leaq (%rax), %rbx: "내비게이션(%rax)에 찍힌 주소가 어디인지 그 주소값 자체만 계산해서 알려달라. (실제로 찾아가지는 마라)"

2. 주요 사용 용도

1. 포인터 생성

나중에 사용할 메모리 주소를 미리 계산하여 레지스터에 저장해 두는 용도로 사용됩니다.

2. 간단한 산술 연산 (⭐ 중요)

컴파일러는 leaq의 주소 계산 공식을 이용하여, 곱셈이나 덧셈을 매우 간결하고 빠르게 처리하는 최적화 기법으로 자주 사용합니다.

• 예시: %rdx 레지스터에 값 x가 들어있을 때

leaq 7(%rdx,%rdx,4), %rax

• 주소 계산 공식 적용:

Imm + R[rb] + R[ri] * s
→ 7 + %rdx + %rdx * 4
→ 7 + x + 4x
→ **5x + 7**

• 결과: 위 명령어 하나만으로 %rax 레지스터에 5x + 7의 계산 결과가 저장됩니다. 이는 여러 개의 mov, mul, add 명령어를 사용하는 것보다 훨씬 효율적입니다.

3.5.2 단항 및 이항 연산

1. 단항 연산 (Unary Operations)

단항 연산은 피연산자가 하나이며, 이 피연산자가 소스(source)이자 목적지(destination) 역할을 동시에 합니다. 피연산자로는 레지스터나 메모리 위치를 사용할 수 있습니다.

• 예시: incq (%rsp)
  • 스택의 가장 위에 있는 8바이트 값에 1을 더한 뒤, 그 결과를 다시 원래 위치에 덮어씁니다.
  • 이는 C언어의 ++ 또는 -- 연산자와 비슷하게 동작합니다.

---

2. 이항 연산 (Binary Operations)

이항 연산은 피연산자가 두 개이며, 두 번째 피연산자가 소스이자 목적지 역할을 합니다.

• 소스: 첫 번째와 두 번째 피연산자
• 목적지: 두 번째 피연산자

이는 C언어의 x -= y와 같은 할당 연산자와 비슷하지만, 소스가 먼저, 목적지가 나중에 온다는 점이 헷갈릴 수 있습니다.

• 예시: subq %rax, %rdx
  • "rdx에서 rax를 빼라" (rdx = rdx - rax) 로 읽는 것이 편합니다.
  • 소스1: %rax
  • 소스2/목적지: %rdx
  • 결과는 %rdx에 덮어쓰입니다.

제약사항: mov 명령어와 마찬가지로, 두 피연산자가 동시에 메모리일 수는 없습니다.

두번째 오퍼랜드가 메모리 위치일 때 프로세서가 메모리에서 값을 읽고, 연산을 하고, 그 결과를 다시 메모리에 써야한다는 점을 유의해야 합니다.

3.5.3 시프트 연산 (Shift Operations)

시프트 연산 명령어는 이동할 칸 수(shift amount)를 첫 번째 피연산자로, 시프트할 값을 두 번째 피연산자로 받습니다.

이동할 칸 수 지정 방법

이동할 칸 수는 두 가지 방식으로 지정할 수 있습니다.

1. 즉시 값 (Immediate): salq $4, %rax 처럼 이동할 칸 수를 상수로 직접 지정합니다.
2. %cl 레지스터: 이동할 칸 수를 변수처럼 사용하고 싶을 때, 그 값을 %cl 레지스터에 넣어서 지정합니다. (%cl은 %rcx 레지스터의 가장 낮은 1바이트 부분입니다.)

%cl의 특별 규칙:
CPU는 %cl 레지스터의 하위 비트들만 사용하여 실제 이동할 칸 수를 결정합니다. w비트 데이터를 시프트할 때, %cl의 하위 m비트만 사용합니다(여기서 $2^m$=w).

• 예: salq(64비트 시프트, $2^6=64$)는 %cl의 하위 6비트만 보므로, %cl의 값이 255(0xFF)라도 실제로는 63칸만 이동합니다.

---

시프트 명령어 종류

• sal / shl (Left Shift): 왼쪽 시프트
  • 두 명령어는 완전히 동일하게 동작합니다.
  • 비어있는 오른쪽 끝은 0으로 채워집니다.
• sar (Arithmetic Right Shift): 산술 오른쪽 시프트
  • 부호 있는(signed) 수에 사용됩니다.
  • 비어있는 왼쪽 끝은 원래의 부호 비트로 채워집니다.
• shr (Logical Right Shift): 논리 오른쪽 시프트
  • 부호 없는(unsigned) 수에 사용됩니다.
  • 비어있는 왼쪽 끝은 무조건 0으로 채워집니다.

시프트할 대상(두 번째 피연산자)은 레지스터 또는 메모리 위치가 될 수 있습니다.

3.5.4 논의 (Discussion)

지금까지 살펴본 대부분의 산술/논리 명령어들은 부호 없는(unsigned) 연산과 2의 보수(signed) 연산에 동일하게 사용될 수 있습니다. 부호 여부에 따라 별도의 명령어가 필요한 경우는 오른쪽 시프트뿐입니다. 이것이 바로 2의 보수 표현법이 부호 있는 정수 연산을 구현하는 표준 방식으로 채택된 이유 중 하나입니다.

C 코드와 어셈블리어 코드 예시

아래 코드는 여러 산술/논리 연산을 수행하는 C 함수와, 그에 대응하는 어셈블리어 코드입니다.

C 코드

long arith(long x, long y, long z) {
    long t1 = x ^ y;
    long t2 = z * 48;
    long t3 = t1 & 0x0F0F0F0F;
    long t4 = t2 - t3;
    return t4;
}

어셈블리어 코드

// x in %rdi, y in %rsi, z in %rdx
1 arith:
2   xorq    %rsi, %rdi            // t1 = x ^ y (결과가 %rdi에 저장됨)
3   leaq    (%rdx,%rdx,2), %rax   // %rax = z + z*2 = 3*z
4   salq    $4, %rax              // %rax = %rax << 4 = (3*z) * 16 = 48*z. t2 = z*48
5   andq    $68719476735, %rdi    // 0x0F0F0F0F = 68719476735. t3 = t1 & 0x0F0F0F0F
6   subq    %rdi, %rax            // %rax = %rax - %rdi = t2 - t3. t4 = t2 - t3
7   ret                           // %rax에 저장된 값을 반환

• 2~6번 라인: C 코드의 각 줄이 어셈블리어 명령어와 거의 일대일로 대응되는 것을 볼 수 있습니다.
• 3, 4번 라인: z * 48 이라는 곱셈을 더 빠른 leaq와 salq(왼쪽 시프트) 명령어의 조합으로 최적화했습니다.
• 레지스터 재사용: %rax 레지스터가 처음에는 3*z를, 그다음에는 z*48을, 마지막에는 최종 반환 값 t4를 저장하는 등, 컴파일러는 하나의 레지스터를 여러 다른 값을 저장하는 용도로 재사용하여 효율을 높입니다.

3.5.5 특별한 산술 연산

64비트 정수 두 개를 곱하면 최대 128비트 결과가 나올 수 있고, 나눗셈은 몫과 나머지를 함께 계산해야 하는 특별한 연산입니다. x86-64 명령어 집합은 이러한 128비트 연산을 제한적으로 지원합니다. (16바이트 양을 옥타 워드(oct word)라고 부릅니다.)

1. 128비트 곱셈

imulq는 이전에 본 것처럼 피연산자가 두 개인 일반적인 64비트 곱셈 명령어로도 쓰이지만, 128비트 전체 결과를 얻기 위한 피연산자가 하나인 특별한 형태로도 사용됩니다.

• imulq S (부호 있음) / mulq S (부호 없음)
  • 동작:
    1. 첫 번째 피연산자는 %rax 레지스터에 있어야 합니다.
    2. 두 번째 피연산자 S를 곱합니다.
    3. 128비트 결과 중 상위 64비트는 %rdx에, 하위 64비트는 %rax에 저장됩니다.
  • 구분: 어셈블러는 피연산자의 개수를 보고 두 가지 imulq 중 어떤 것인지 구별합니다.

2. 128비트 나눗셈

나눗셈 명령어는 피연산자가 하나이며, 몫과 나머지를 동시에 계산합니다.

• idivq S (부호 있음) / divq S (부호 없음)
  • 동작:
    1. 128비트 피제수(나눠지는 수)는 %rdx (상위 64비트)와 %rax (하위 64비트) 두 레지스터에 미리 준비되어 있어야 합니다.
    2. 피연산자 S로 나눕니다.
    3. 몫은 %rax에, 나머지는 %rdx에 저장됩니다.

나눗셈 준비: cqto 명령어

일반적으로 나눗셈은 64비트 값을 나누는 경우가 많습니다. 이때는 64비트 피제수를 %rax에 넣고, %rdx를 적절히 설정해야 합니다.

• %rax의 부호 비트를 %rdx의 모든 비트에 복사(부호 확장)해야 합니다.

cqto 명령어는 바로 이 부호 확장을 위한 전용 명령어입니다.

• 동작: 피연산자 없이, 암묵적으로 %rax의 부호 비트를 읽어 %rdx 전체를 그 값으로 채웁니다. long을 oct word로 변환(Convert Long to Oct word)하는 역할을 합니다.
• 예시:
  long q = x / y;

movq    %rdi, %rax  ; 1. x를 %rax에 넣는다.
cqto                ; 2. %rax의 부호를 %rdx로 확장하여 128비트 피제수를 만든다.
idivq   %rsi        ; 3. y(%rsi)로 나눈다.
                    ; 4. 몫은 %rax에, 나머지는 %rdx에 저장된다.

3.6 제어 (Control)

지금까지는 명령어들이 순서대로 하나씩 실행되는 순차적 코드(straight-line code)만 다루었습니다. 하지만 C언어의 if (조건문), while (반복문), switch (선택문)와 같은 구문들은 데이터 값에 대한 테스트 결과에 따라 실행 흐름이 달라지는 조건부 실행(conditional execution)을 필요로 합니다.

기계어 코드는 이러한 조건부 동작을 구현하기 위해 두 가지 기본적인 저수준(low-level) 메커니즘을 제공합니다.

1. 데이터 값을 테스트한다.
2. 테스트 결과에 따라 제어 흐름 또는 데이터 흐름을 바꾼다.

이 중 데이터에 의존하는 제어 흐름 변경이 더 일반적인 방식입니다. 보통 명령어는 프로그램에 나타난 순서대로 실행되지만, 점프(jump) 명령어를 만나면 실행 순서가 프로그램의 다른 부분으로 넘어갈 수 있습니다. 컴파일러는 이 점프라는 저수준 메커니즘을 기반으로 C언어의 제어 구문들을 구현해야 합니다.

이 섹션에서는 먼저 조건부 연산을 구현하는 두 가지 방법을 다루고, 이어서 반복문과 선택문을 구현하는 방법을 설명하겠습니다.

3.6.1 조건 코드 (Condition Codes)

CPU는 정수 레지스터 외에도, 가장 최근에 수행된 산술 또는 논리 연산의 결과에 대한 속성을 담고 있는 단일 비트짜리 조건 코드 레지스터들을 유지합니다. 이 레지스터들의 값을 테스트하여 조건부 분기(conditional branch)를 수행할 수 있습니다.

가장 유용한 조건 코드는 다음과 같습니다.

• CF (Carry Flag): 부호 없는(unsigned) 연산에서 올림수(carry)가 발생했는지 나타냅니다. (오버플로우 탐지용)
• ZF (Zero Flag): 연산 결과가 0이 되었는지 나타냅니다.
• SF (Sign Flag): 연산 결과가 음수가 되었는지 나타냅니다. (결과의 최상위 비트와 동일)
• OF (Overflow Flag): 2의 보수(signed) 연산에서 오버플로우가 발생했는지 나타냅니다.

leaq를 제외한 대부분의 산술/논리 명령어는 이 조건 코드들을 설정합니다.

---

값 변경 없이 조건 코드만 설정하는 명령어

if (a == b)와 같은 비교를 위해, 다른 레지스터 값을 변경하지 않고 오직 조건 코드만 설정하는 특별한 명령어들이 있습니다.

1. CMP 명령어 (비교)

• 동작: cmp S₂, S₁는 내부적으로 S₁ - S₂ 뺄셈 연산을 수행하고, 그 결과에 따라 조건 코드를 설정합니다.
• 특징: sub 명령어와 달리, 뺄셈 결과를 어디에도 저장하지 않습니다.
  • ZF 플래그: S₁과 S₂가 같다면 1로 설정됩니다. (결과가 0이므로)
  • SF, CF, OF 플래그: 두 피연산자 사이의 크기 관계를 파악하는 데 사용됩니다.

2. TEST 명령어 (테스트)

• 동작: test S₂, S₁는 내부적으로 S₁ & S₂ AND 연산을 수행하고, 그 결과에 따라 조건 코드를 설정합니다.
• 특징: and 명령어와 달리, AND 연산 결과를 어디에도 저장하지 않습니다.
  • 용도:
    • 특정 값이 0인지, 양수인지, 음수인지 확인할 때 주로 사용됩니다. (예: testq %rax, %rax)
    • 특정 비트가 켜져 있는지 확인할 때 마스크(mask)와 함께 사용됩니다.

3.6.2 조건 코드 접근하기

CPU의 조건 코드를 직접 읽는 대신, 다음과 같은 세 가지 일반적인 방법으로 사용합니다.

1. 조건 코드의 조합에 따라 1바이트 값을 0 또는 1로 설정한다.
2. 조건에 따라 프로그램의 다른 위치로 점프한다.
3. 조건에 따라 데이터를 전송한다.

1. SET 명령어: 조건에 따라 0 또는 1 설정하기

SET 명령어 클래스는 조건 코드의 특정 조합에 따라, 목적지(1바이트 레지스터 또는 메모리)의 값을 0 또는 1로 설정하는 명령어들입니다.

• 특징: 명령어의 접미사(l, b 등)는 데이터 크기가 아닌 조건(condition)을 의미합니다. (예: setl은 "set less", setb는 "set below"를 의미)
• 목적지: 1바이트 레지스터(%al 등) 또는 1바이트 메모리 위치입니다.
• 32/64비트 결과 생성: SET 명령어는 1바이트만 설정하므로, 32비트나 64비트 결과(C언어의 true(1) 또는 false(0))를 만들려면 나머지 상위 비트들을 0으로 초기화하는 movzbl 같은 명령어가 추가로 필요합니다.

예시: a < b 계산

// a in %rdi, b in %rsi
1 cmpq    %rsi, %rdi      // a와 b를 비교 (내부적으로 a - b 수행)
2 setl    %al             // less, 즉 a < b 조건이 참이면 %al을 1로, 아니면 0으로 설정
3 movzbl  %al, %eax       // %al을 %eax로 0 확장 이동 (나머지 비트를 0으로 초기화)

2. 부호 있는 비교와 부호 없는 비교

CMP 명령어(a-b 연산) 이후, SET 명령어들은 조건 코드를 조합하여 결과를 판단합니다.

• sete (같을 때): a와 b가 같으면 a-b의 결과는 0이므로, ZF(Zero Flag)가 1인지를 확인합니다.
• setl (작을 때, signed): 부호 있는 비교는 복잡합니다. 오버플로우 발생 여부(OF)와 부호(SF)를 함께 고려해야 합니다. a < b가 참인 조건은 SF ^ OF (SF와 OF의 XOR)가 1일 때입니다.
• setb (작을 때, unsigned): 부호 없는 비교는 더 간단합니다. a < b는 a - b 연산 시 올림수/빌림수(Carry)가 발생했는지로 판단합니다. 따라서 CF(Carry Flag)를 확인합니다.

1. sete (Set if Equal): ZF 플래그

• 같음(==)을 비교하는 가장 간단한 경우입니다.
• 핵심 원리: 두 숫자 a와 b가 같다면, a - b의 결과는 항상 0입니다.
• 동작:
  1. cmpq %rsi, %rdi 명령어는 내부적으로 a - b를 계산합니다. (a는 %rdi, b는 %rsi에 있다고 가정)
  2. 만약 a와 b가 같다면, 계산 결과는 0이 됩니다.
  3. CPU는 결과가 0일 때 ZF(Zero Flag)를 1로 설정합니다.
  4. sete 명령어는 이 ZF가 1인지 아닌지만 확인합니다. ZF가 1이면 목적지에 1(참)을, 아니면 0(거짓)을 저장합니다.

---

2. setb (Set if Below): CF 플래그

• 부호 없는 수(unsigned)의 '작음'(<)을 비교합니다. ("Below"는 부호 없는 수 비교에 사용되는 관용적 표현입니다.)
• 핵심 원리: 부호 없는 수 a와 b에 대해 a - b를 계산할 때, 만약 a가 b보다 작다면 뺄셈 과정에서 '빌림(borrow)'이 발생합니다.
• 동작:
  1. cmpq %rsi, %rdi는 a - b를 계산합니다.
  2. 만약 a가 b보다 작아서 윗자리에서 빌림이 발생했다면, CPU는 CF(Carry Flag)를 1로 설정합니다. (뺄셈에서의 Carry는 빌림을 의미합니다.)
  3. setb 명령어는 이 CF가 1인지 아닌지만 확인합니다. CF가 1이면 a가 b보다 작았다는 뜻이므로, 목적지에 1(참)을 저장합니다.

---

3. setl (Set if Less): SF ^ OF 플래그 조합

• 부호 있는 수(signed)의 '작음'(<)을 비교합니다. ("Less"는 부호 있는 수 비교에 사용됩니다.) 부호가 있기 때문에 오버플로우 가능성을 고려해야 해서 가장 복잡합니다.
• 핵심 원리: a < b인지 판단하려면, a - b의 결과 부호만 봐서는 안 되고, 계산 과정에서 오버플로우가 발생했는지도 함께 고려해야 합니다.

경우 1: 오버플로우가 발생하지 않은 경우 (OF = 0)

• a - b의 결과가 음수이면 a < b가 맞습니다.
• 이때 setl의 조건 SF ^ OF는 SF ^ 0이 되어, 결과는 SF와 같습니다. 즉, SF가 1(음수)이면 참이 됩니다.

경우 2: 오버플로우가 발생한 경우 (OF = 1)

• 덧셈 오버플로우처럼, 뺄셈 오버플로우는 결과의 부호를 뒤집어 버립니다.
  • 예시 (4비트, 범위: -8 ~ 7): a=-7, b=4. a < b는 참입니다.
  • a - b = -7 - 4 = -11. 이는 4비트 범위를 벗어나는 오버플로우입니다.
  • 컴퓨터 계산 결과: -7 - 4 → 1001 - 0100 → 0101 (즉, 양수 5).
• 결과가 양수이므로 SF는 0이 됩니다. 하지만 오버플로우가 발생했으므로 OF는 1이 됩니다.
• 이때 setl의 조건 SF ^ OF는 0 ^ 1이 되어, 결과는 1(참)이 됩니다.

---

결론: SF ^ OF (SF와 OF의 XOR 연산)라는 조건은, 오버플로우가 발생했든 안 했든 상관없이 항상 a < b가 맞는지 정확하게 판단해주는 마법 같은 공식입니다. setl 명령어는 바로 이 공식을 확인하여 결과를 결정합니다.

3. 기계어 코드와 자료형

기계어 코드는 C언어와 달리 값에 자료형을 연관시키지 않습니다. 대부분의 산술 연산은 부호 있는 수와 없는 수에 대해 비트 수준 동작이 동일하므로 같은 명령어를 사용합니다.

하지만 오른쪽 시프트, 곱셈/나눗셈, 그리고 SET 명령어처럼 조건 코드를 해석하는 방식 등 일부 경우에는 부호 여부에 따라 서로 다른 명령어나 규칙을 사용해야 합니다.

3.6.3 점프 명령어 (Jump Instructions)

일반적으로 명령어는 순서대로 실행되지만, 점프(jump) 명령어는 실행 흐름을 완전히 새로운 위치로 바꿀 수 있습니다. 어셈블리어에서 점프의 목적지는 보통 레이블(label)로 표시됩니다.

1. jmp: 무조건 점프

jmp 명령어는 조건 없이 무조건 지정된 위치로 실행 흐름을 이동시킵니다.

• 직접 점프 (Direct Jump): jmp .L1처럼 목적지 레이블을 코드에 직접 명시합니다.
• 간접 점프 (Indirect Jump): jmp *%rax나 jmp *(%rax)처럼, 점프할 목적지 주소를 레지스터나 메모리에서 읽어와 사용합니다.

2. 조건부 점프 (Conditional Jumps)

jmp를 제외한 나머지 점프 명령어들은 조건부로 동작합니다. 조건 코드(condition codes)의 상태에 따라 점프를 하거나, 그냥 다음 명령어를 순차적으로 실행합니다.

• 동작 원리: 이 명령어들의 이름과 점프 조건은 앞에서 본 SET 명령어들과 정확히 일치합니다. 예를 들어, sete가 ZF=1일 때 1을 설정했다면, je(Jump if Equal)는 ZF=1일 때 점프합니다.
• 제약사항: 조건부 점프는 항상 목적지가 코드에 명시된 직접 점프 방식만 가능합니다.

3.6.4 점프 명령어 인코딩

어셈블리어에서 점프 목적지는 .L1과 같은 레이블로 작성되지만, 실제 기계어 코드에서는 이 목적지가 숫자로 된 주소로 인코딩됩니다. 점프 주소를 인코딩하는 가장 일반적인 방식은 PC 상대 주소 지정(PC-relative addressing)입니다.

1. PC 상대 주소 지정 (PC-relative Addressing)

이 방식은 점프할 목적지의 절대 주소를 기록하는 대신, 현재 위치로부터 얼마나 멀리 떨어져 있는지 그 상대적인 거리(오프셋)를 기록합니다.

상대 주소 = 목적지 주소 - 다음 명령어의 주소

이때 기준이 되는 "현재 위치"는 점프 명령어 자체의 주소가 아니라, 점프 명령어 바로 다음 명령어의 주소입니다.

• 예시 1: 앞으로 점프 (jmp)

3: eb 03 jmp 8 <loop+0x8>
5: ... (다음 명령어)

• eb: jmp 명령어의 Opcode
• 03: 인코딩된 상대 주소 (목표까지 +3 바이트)
• 계산: 다음 명령어 주소(0x5) + 상대 주소(0x3) = 0x8 (최종 목적지 주소)
• 예시 2: 뒤로 점프 (jg)

b: 7f f8   jg 5 <loop+0x5>
d: ... (다음 명령어)

• 7f: jg 명령어의 Opcode
• f8: 인코딩된 상대 주소 (1바이트 2의 보수로 -8을 의미)
• 계산: 다음 명령어 주소(0xd) + 상대 주소(-8) = 0x5 (최종 목적지 주소)

2. PC 상대 주소 지정의 장점

1. 컴팩트한 인코딩: 전체 64비트 절대 주소를 다 기록할 필요 없이, 가까운 거리는 1~2바이트의 작은 오프셋만으로 표현할 수 있어 코드 크기가 작아집니다.
2. 재배치 가능 (Relocatable): 링커가 프로그램을 메모리의 다른 위치로 옮기더라도, 명령어들 사이의 '상대적인 거리'는 변하지 않습니다. 따라서 링커는 점프 명령어의 주소 부분을 수정할 필요 없이 코드를 그대로 사용할 수 있어 매우 효율적입니다.

3.6.5 조건부 제어를 이용한 조건 분기 구현

C언어의 if-else와 같은 조건문을 기계어 코드로 번역하는 가장 일반적인 방법은 조건부 점프와 무조건 점프를 조합하여 사용하는 것입니다.

1. C 코드와 어셈블리어 코드 비교

아래 코드는 두 수의 차이의 절댓값을 구하는 함수입니다.

• (a) 원본 C 코드 (if-else 사용)

long absdiff_se(long x, long y) {
    long result;
    if (x < y) {
        lt_cnt++;
        result = y - x;
    } else {
        ge_cnt++;
        result = x - y;
    }
    return result;
}

• (b) goto 버전 C 코드 (어셈블리어 흐름 모방)
  C언어의 goto문을 사용하여 어셈블리어의 제어 흐름을 묘사할 수 있습니다.

if (x >= y)
    goto x_ge_y; // x가 y보다 크거나 같으면 x_ge_y 레이블로 점프
lt_cnt++;
result = y - x;
return result;
x_ge_y:
    ge_cnt++;
    result = x - y;
    return result;

• (c) 생성된 어셈블리어 코드

// x in %rdi, y in %rsi
1 absdiff_se:
2   cmpq    %rsi, %rdi      // x와 y를 비교 (x - y)
3   jge     .L2             // x >= y 이면 .L2 레이블로 점프
4   addq    $1, lt_cnt(%rip) // lt_cnt++
5   movq    %rsi, %rax      
6   subq    %rdi, %rax      // result = y - x
7   ret
8 .L2:
9   addq    $1, ge_cnt(%rip) // ge_cnt++
10  movq    %rdi, %rax
11  subq    %rsi, %rax      // result = x - y
12  ret

보시는 것처럼, 컴파일러가 생성한 어셈블리어 코드의 제어 흐름은 goto문을 사용한 C 코드의 흐름과 거의 동일합니다.

2. if-else 문의 일반적인 번역 패턴

C언어의 일반적인 if-else문

if (test-expr)
    then-statement
else
    else-statement

은 컴파일러에 의해 보통 아래와 같은 제어 흐름으로 번역됩니다.

    t = test-expr;
    if (!t)          // 만약 test-expr 조건이 '거짓'이면,
        goto false;  // false 레이블(else 블록)로 점프한다.
    
    // (조건이 '참'일 때 실행되는 코드)
    then-statement
    goto done;       // else 블록을 건너뛰고 끝으로 점프한다.

false:
    // (조건이 '거짓'일 때 실행되는 코드)
    else-statement

done:
    // (if-else문 다음 코드)

이처럼 컴파일러는 then 부분과 else 부분을 위한 별도의 코드 블록을 만들고, 조건부/무조건 점프를 적절히 삽입하여 올바른 코드 블록만 실행되도록 보장합니다.

3.6.6 조건부 이동을 이용한 조건 분기 구현

if-else와 같은 조건부 연산을 구현하는 전통적인 방식은 조건부 제어 이동(conditional control transfer), 즉 점프(jump)를 사용하는 것입니다. 이는 간단하고 일반적이지만, 현대 프로세서에서는 매우 비효율적일 수 있습니다.

이에 대한 대안으로 조건부 데이터 이동(conditional data transfer) 전략이 있습니다. 이 방식은 조건문의 두 가지 결과를 모두 미리 계산한 뒤, 조건의 참/거짓 여부에 따라 둘 중 하나를 선택하는 것입니다.

1. 조건부 이동의 장점: 파이프라인 효율성

현대의 CPU는 파이프라이닝(pipelining) 기술을 사용하여 여러 명령어의 각 단계를 겹쳐서 동시에 처리함으로써 높은 성능을 냅니다. 이를 위해서는 다음에 실행할 명령어를 미리 예측하여 파이프라인을 계속 채워둬야 합니다.

• 문제점 (조건부 점프): CPU가 조건부 점프(branch) 명령어를 만나면, 조건이 평가되기 전까지는 다음에 어떤 코드를 실행해야 할지 알 수 없습니다. CPU는 분기 예측(branch prediction)이라는 정교한 기술로 다음에 실행될 코드를 '추측'합니다.
  • 예측 성공 시: 파이프라인이 중단 없이 채워져 높은 성능을 유지합니다.
  • 예측 실패 시: 파이프라인에 미리 채워뒀던 모든 작업을 폐기하고, 올바른 위치부터 다시 파이프라인을 채워야 합니다. 이 분기 예측 실패 페널티는 수십 클럭 사이클의 시간을 낭비시켜 심각한 성능 저하를 유발합니다.
• 해결책 (조건부 이동): cmov(conditional move) 같은 조건부 이동 명령어는 점프를 사용하지 않습니다. CPU는 분기를 예측할 필요 없이, 일단 두 결과를 모두 계산한 뒤 조건 코드(flags)를 확인하여 최종적으로 레지스터에 값을 쓸지 말지만 결정하면 됩니다. 따라서 파이프라인이 중단될 위험이 없어 분기 예측이 어려운 상황에서 훨씬 더 높은 성능을 보입니다.

2. C 코드와 어셈블리어 코드 예시

아래 코드는 if-else문을 조건부 이동으로 구현한 예시입니다.

• (a) 원본 C 코드

long absdiff(long x, long y) {
    if (x < y)
        return y - x;
    else
        return x - y;
}

• (c) 생성된 어셈블리어 코드

// x in %rdi, y in %rsi
1 absdiff:
2   movq    %rsi, %rax  // rax = y (일단 y를 결과 후보1로 설정)
3   subq    %rdi, %rax  // rax = y - x
4   movq    %rdi, %rdx  // rdx = x (일단 x를 결과 후보2로 설정)
5   subq    %rsi, %rdx  // rdx = x - y
6   cmpq    %rsi, %rdi  // x와 y를 비교
7   cmovge  %rdx, %rax  // 만약 x >= y 이면, rax = rdx (결과를 후보2로 교체)
8   ret

• 코드 분석:
  1. y-x와 x-y 두 가지 결과를 모두 미리 계산하여 각각 %rax와 %rdx에 저장합니다.
  2. cmpq로 x와 y를 비교하여 조건 코드를 설정합니다.
  3. cmovge(Conditional Move if Greater or Equal) 명령어가 조건 코드를 확인하여, 만약 x >= y 조건이 참이면 %rdx의 값(x-y)을 %rax에 덮어씁니다. 조건이 거짓이면 아무 일도 하지 않습니다.
  4. 최종적으로 %rax에 담긴 값을 반환합니다.

3. 조건부 이동의 한계

조건부 이동은 항상 좋은 것은 아니며, 다음과 같은 제한된 경우에만 사용됩니다.

• 부작용(Side Effect) 문제: 만약 if나 else 블록에 값을 계산하는 것 외에 파일 입출력이나 전역 변수 변경 같은 부작용이 있다면, 조건부 이동을 사용할 수 없습니다. 두 블록이 모두 실행되어 원치 않는 부작용이 발생할 수 있기 때문입니다.
• 계산 비용 문제: if나 else 블록의 계산 과정이 매우 복잡하고 오래 걸린다면, 두 블록을 모두 계산하는 것은 낭비가 될 수 있습니다. 이 경우, 분기 예측 실패 페널티를 감수하더라도 조건부 점프를 사용하는 것이 더 효율적일 수 있습니다.

결론적으로, 컴파일러는 두 블록의 계산이 매우 간단할 때(예: 단일 add 명령어 등) 주로 조건부 이동을 사용하는 최적화를 수행합니다.

3.6.7 반복문 (Loops)

C언어는 do-while, while, for와 같은 여러 반복문을 제공하지만, 기계어에는 이에 직접 대응하는 명령어가 없습니다. 대신 조건부 테스트와 점프의 조합을 사용하여 반복문의 효과를 구현합니다.

1. do-while 반복문

do-while문의 일반적인 형태와 동작은 다음과 같습니다.

• 형태:

do
    body-statement
while (test-expr);

• 동작: body-statement를 최소 한 번 실행한 뒤, test-expr 조건을 평가하여 참(non-zero)이면 반복을 계속합니다.

이러한 do-while문은 다음과 같은 goto문 형태로 변환될 수 있습니다.

loop:
    body-statement
    t = test-expr;
    if (t)
        goto loop;

---

예시: 팩토리얼 계산 (do-while 사용)

아래는 do-while문을 사용하여 팩토리얼을 계산하는 함수와 그에 해당하는 어셈블리어 코드입니다.

• (a) 원본 C 코드

long fact_do(long n) {
    long result = 1;
    do {
        result *= n;
        n = n - 1;
    } while (n > 1);
    return result;
}

• (c) 생성된 어셈블리어 코드

// n in %rdi, result in %rax
1 fact_do:
2   movl    $1, %eax     // result = 1
3 .L2:                   // loop:
4   imulq   %rdi, %rax   // result *= n
5   subq    $1, %rdi     // n = n - 1
6   cmpq    $1, %rdi     // n과 1을 비교
7   jg      .L2          // 만약 n > 1 이면 .L2(loop)로 점프
8   rep; ret

코드 분석

• 레지스터 할당: 인자 n은 %rdi에, 지역 변수 result는 %rax에 할당되었습니다. %rax는 함수 반환 값을 저장하는 데 사용되므로, 최종적으로 반환될 result를 담는 데 최적입니다.
• 반복문 구현: jg .L2(Jump if Greater)라는 조건부 점프 명령어가 반복문의 핵심입니다. 6번 라인에서 n과 1을 비교한 결과, n > 1 조건이 참이면 3번 라인의 .L2 레이블로 다시 점프하여 루프를 계속 실행합니다. 조건이 거짓이면, 점프하지 않고 다음 명령어인 ret로 넘어가 함수를 종료합니다.

while 반복문

while문은 루프 본문을 실행하기 전에 조건을 먼저 검사한다는 점에서 do-while문과 다릅니다. GCC 컴파일러는 while문을 기계어 코드로 번역할 때 주로 두 가지 전략을 사용합니다.

1. 중간으로 점프 (Jump to Middle)

이 방식은 루프의 맨 끝에 있는 조건 검사 부분으로 무조건 점프하는 것으로 시작합니다. -Og 최적화 옵션을 사용할 때 주로 나타납니다.

• 변환 패턴:

goto test;
loop:
    body-statement
test:
    t = test-expr;
    if (t)
        goto loop;

• 동작:
  1. goto test;: 루프 본문을 실행하지 않고, 맨 끝의 조건 검사로 바로 점프합니다.
  2. test:: 조건을 검사합니다.
  3. if (t) goto loop;: 조건이 참이면, 루프의 시작인 loop:로 점프하여 본문을 실행합니다.

이 방식은 do-while문의 구조를 재사용하면서, 맨 앞에 점프 하나만 추가하여 while문의 '선(先)검사' 특징을 구현한 것입니다.

---

2. 보호된 do (Guarded-do)

이 방식은 while문을 if문과 do-while문의 조합으로 변환합니다. 높은 최적화 레벨(-O1 등)에서 주로 사용됩니다.

• 변환 패턴:

if (!test-expr) // 만약 초기 조건이 거짓이면,
    goto done;   // 루프 전체를 건너뛴다.

// (초기 조건이 참일 때만 실행되는 do-while 루프)
do
    body-statement
while (test-expr);

done:

• 동작:
  1. 루프에 들어가기 전에 조건을 먼저 한 번 검사합니다.
  2. 조건이 거짓이면 루프를 완전히 건너뜁니다.
  3. 조건이 참이면, 그 뒤는 일반적인 do-while 루프와 동일하게 동작합니다.

이 방식은 컴파일러가 초기 조건 검사 부분을 최적화할 여지를 더 많이 주기 때문에, 높은 최적화 레벨에서 선호됩니다. 예를 들어, 컴파일러는 루프의 조건이 항상 참이라는 것을 알아내고 불필요한 초기 검사를 생략할 수 있습니다.

for 반복문

C언어의 for 반복문은 다음과 같은 일반적인 형태를 가집니다.

for (init-expr; test-expr; update-expr)
    body-statement

C언어 표준에 따르면, for 루프는 아래와 같은 while 루프와 동일하게 동작합니다.

init-expr;
while (test-expr) {
    body-statement
    update-expr;
}

1. 초기화 (init-expr): 루프 시작 전에 단 한 번 실행됩니다.
2. 조건 검사 (test-expr): 루프 본문을 실행하기 전에 조건을 검사합니다.
3. 본문 실행 (body-statement): 조건이 참이면 실행됩니다.
4. 업데이트 (update-expr): 본문 실행 후에 실행됩니다.

---

for 루프의 컴파일 전략

GCC 컴파일러는 for 루프를 위와 같은 while 루프 형태로 변환한 뒤, 앞에서 설명한 while 루프의 두 가지 번역 전략(중간으로 점프, 보호된 do) 중 하나를 사용하여 기계어 코드를 생성합니다.

예시: 팩토리얼 계산 (for 사용)

아래는 for 루프를 사용하여 팩토리얼을 계산하는 함수와 그에 해당하는 어셈블리어 코드입니다.

• C 코드:

long fact_for(long n) {
    long i;
    long result = 1;
    for (i = 2; i <= n; i++)
        result *= i;
    return result;
}

• 어셈블리어 코드 (Og 옵션):
  이 코드는 '중간으로 점프(Jump-to-middle)' 전략을 사용하여 번역되었습니다.

// n in %rdi, result in %eax, i in %edx
fact_for:
    movl    $1, %eax     // result = 1
    movl    $2, %edx     // i = 2
    jmp     .L8          // goto test (조건 검사로 점프)
.L9:                     // loop:
    imulq   %rdx, %rax   // result *= i (body-statement)
    addq    $1, %rdx     // i++ (update-expr)
.L8:                     // test:
    cmpq    %rdi, %rdx   // i와 n을 비교 (test-expr)
    jle     .L9          // 만약 i <= n 이면 .L9(loop)로 점-프
    rep; ret

코드 분석:
어셈블리어 코드는 C 코드를 while 루프로 변환하고, 다시 goto문 버전으로 변환한 흐름과 정확히 일치합니다.

1. 초기화(result=1, i=2)를 수행합니다.
2. jmp를 이용해 루프의 맨 끝에 있는 조건 검사(.L8)로 먼저 이동합니다.
3. jle 조건부 점프를 통해 조건(i <= n)이 참이면 루프 본문(.L9)으로 다시 돌아가고, 거짓이면 루프를 빠져나와 함수를 종료합니다.

3.6.8 Switch 문

switch문은 정수 인덱스 값에 따라 여러 경로로 분기하는 다중 분기(multiway branching) 기능을 제공합니다. 특히 가능한 결과의 수가 많을 때 if-else문을 길게 나열하는 것보다 코드 가독성을 높이고, 점프 테이블(Jump Table)이라는 자료구조를 통해 효율적인 구현을 가능하게 합니다.

1. 점프 테이블 (Jump Table)

점프 테이블은 배열이며, 배열의 i번째 항목에는 switch 인덱스 값이 i일 때 실행해야 할 코드 블록의 주소가 저장되어 있습니다.

• 동작: 프로그램은 switch문의 인덱스 값을 이용해 이 배열의 특정 위치에 접근하여, 그곳에 저장된 코드 주소로 점프합니다.
• 장점: if-else문은 조건의 개수에 따라 비교 시간이 길어질 수 있지만, 점프 테이블을 사용하면 케이스의 개수와 상관없이 한 번의 배열 접근과 한 번의 점프로 매우 빠르게 분기할 수 있습니다.

GCC 컴파일러는 케이스의 개수가 많고(보통 4개 이상) 값들이 좁은 범위에 분포할 때 switch문을 점프 테이블로 번역합니다.

---

2. C 코드와 어셈블리어 코드 예시

아래 코드는 switch문이 점프 테이블을 사용하는 어셈블리어 코드로 어떻게 번역되는지를 보여줍니다.

• (a) 원본 C 코드:
  다양한 특징을 가집니다. (중간에 빠진 케이스 101, 여러 레이블을 가진 케이스 104, 106, break가 없어 다음 케이스로 넘어가는 fall-through 102)
• (c) 생성된 어셈블리어 코드:

// n in %rsi
1 switch_eg:
2   subq    $100, %rsi         // index = n - 100
3   cmpq    $6, %rsi           // index와 6을 비교
4   ja      .L8                // 만약 index > 6 이면 loc_def (default)로 점프
5   jmp     *.L4(,%rsi,8)      // 점프 테이블 .L4에서 index번째 주소로 점프
...
(각 케이스에 해당하는 코드 블록들)

코드 분석

1. 인덱스 계산 (2번 라인): switch의 케이스 값들이 100부터 시작하므로, 컴파일러는 n-100을 계산하여 인덱스를 0부터 시작하도록 범위를 조정합니다.
2. 범위 검사 (3-4번 라인): 인덱스가 유효한 범위(0~6)를 벗어나는지(ja .L8) 확인하여, 벗어날 경우 default 케이스로 바로 점프합니다.
3. 점프 테이블을 이용한 점프 (5번 라인):
   • .L4(,%rsi,8) 이것이 점프 테이블을 사용하는 핵심 부분입니다.
   • .L4: 점프 테이블 배열의 시작 주소입니다.
   • %rsi: 인덱스 index 값입니다.
   • 8: 각 주소(포인터)의 크기(8바이트)입니다.
   • : 이 모든 계산 결과로 나온 주소로 점프하라는 의미입니다.
     이 명령어 하나로 index 값에 따라 해당하는 코드 블록(.L3, .L5 등)으로 즉시 분기할 수 있습니다.

점프 테이블의 구조

어셈블리어 코드에서 점프 테이블은 .rodata(읽기 전용 데이터) 섹션에 다음과 같이 8바이트 주소들의 배열로 선언됩니다.

.L4:
    .quad .L3     // index 0 (n=100)
    .quad .L8     // index 1 (n=101, 빠진 케이스 -> default)
    .quad .L5     // index 2 (n=102)
    .quad .L6     // index 3 (n=103)
    .quad .L7     // index 4 (n=104)
    .quad .L8     // index 5 (n=105, 빠진 케이스 -> default)
    .quad .L7     // index 6 (n=106, 중복 케이스 -> 104와 같은 곳으로)

이처럼 점프 테이블은 빠진 케이스는 default 주소로, 중복 케이스는 동일한 주소로 채워 넣어 모든 상황을 효율적으로 처리합니다.