[TIL/크래프톤 정글] DAY 28

배재준·2025년 4월 6일
8기TILkrafton jungleweek04컴퓨터 시스템

크래프톤 정글 - TIL

목록 보기
21/93
post-thumbnail

2025.04.06

TIL(TODAY I LEARN)

  • WEEK04 :
    동적 프로그래밍, 그리디 알고리즘
    CSAPP 3장. 프로그램의 기계 수준 표현 (특히 3.4, 3.7, 3.8)

  • 3.6 ,3.7 공부

3.6 제어문

  • C 언어에는 조건문, 반복문, switch문처럼 조건적 실행이 필요한 구조가 있음.
  • jump 인스트럭션이 존재
  • 기계어 코드에서는 이를 위해 조건 검사 → 제어 흐름 또는 데이터 흐름 변경 두 가지 방식 제공.

3.6.1 조건 코드

  • CPU는 산술/논리 연산의 결과에 따라 단일 비트 조건 코드(Condition Codes) 를 설정함.
  • 이후 분기 명령에서 이 플래그들을 검사하여 조건부 제어 흐름 구현 가능.

Condition Codes:

이름의미용도
CF (Carry Flag)가장 상위 비트에서 캐리(자리 올림)가 발생했는가?Unsigned overflow 판별
ZF (Zero Flag)연산 결과가 0인가?결과가 0인지 확인
SF (Sign Flag)결과가 음수인가?결과 부호 판단
OF (Overflow Flag)부호 있는 2의 보수 오버플로우 발생 여부Signed overflow 판별

예외적인 명령어:

  • leaq: 주소 계산용이므로 condition code 변경 안 함
  • xor: 논리 연산 → CF, OF는 0으로 설정
  • shl, shr: CF는 밀려나간 비트, OF는 0
  • inc, dec: ZF, OF 설정하지만 CF는 유지됨

  • cmp: sub처럼 작동하지만 결과 저장 안 함, 조건 코드만 설정
    • ZF가 1이면 두 피연산자가 같음
  • test: and처럼 작동하지만 결과 저장 안 함, 비트가 설정되었는지 검사
    • 예: testq %rax, %rax → %rax가 0인지, 음수인지 확인 가능

3.6.2 조건 코드 사용하기

Condition Code를 활용하는 3가지 방법:

  1. set 명령어로 0 또는 1을 저장

    → 조건 만족 여부를 바이트로 저장 (0 or 1)

  2. 조건부 jump

    → 조건에 따라 코드의 흐름을 다른 위치로 분기

  3. 조건부 데이터 이동 (CMOV 등)

    → 조건 만족 시 특정 레지스터나 메모리로 값 이동

set 명령어(setX)

  • 특정 조건이 참이면 1, 거짓이면 0을 저장
  • 저장 위치: 1바이트 레지스터 또는 메모리
  • 조건에 따라 접미사(suffix)가 바뀜 → 예: setl (signed less), setb (unsigned below)
  • 주의: 접미사는 조건을 의미, 크기와 무관함

  • Machine code는 타입 구분 X → 같은 연산 명령어를 signed/unsigned 모두에 사용
  • 차이는 condition code 해석 방식에서 생김
    → ex. cmpq a, b는 같지만, setl(signed) vs setb(unsigned)는 다르게 동작

3.6.3 점프(jump) 인스트럭션

Jump 명령어 종류

1. 무조건 점프 (Unconditional Jump)

명령어형태설명
jmp LabelDirect(직접)해당 라벨로 바로 이동
jmp *OperandIndirect(간접)레지스터나 메모리에 저장된 주소로 이동
  • Direct 예시:
    jmp .L1     // .L1 위치로 이동
  • Indirect 예시:
    jmp *%rax      // %rax에 저장된 주소로 이동
jmp *(%rax)    // %rax가 가리키는 메모리 주소로 jump

2. 조건부 점프 (Conditional Jump)

  • 특정 Condition Code 조합이 참이면 점프
  • 조건이 거짓이면 다음 명령어로 그냥 넘어감
  • 오직 직접 점프(Direct)만 가능

3.6.4 점프 인스트럭션 인코딩

점프 명령어의 주소 지정 방식

  • 어셈블리 코드에서는 점프 대상이 라벨(label)로 표현됨.
  • 하지만 실제 머신코드에서는 점프 주소를 숫자로 인코딩해야 함.
  • 주로 쓰는 방식은 PC-relative addressing.

PC-relative Addressing (프로그램 카운터 상대 주소 지정)

  • 점프 대상은 현재 명령어 다음 주소로부터의 오프셋(offset)으로 표현됨.
  • 오프셋은 1, 2, 또는 4바이트로 인코딩 가능.
  • 오프셋은 2의 보수 형식으로 표현됨 (앞으로는 양수, 뒤로는 음수).
  • 왜 쓰냐
    • 코드 이동 가능성 확보: 메모리 위치가 바뀌어도 jump 인코딩을 바꿀 필요가 없음.
    • 명령어 크기 절약: 대부분의 jump는 짧은 거리 → 1~2바이트면 충분.

역어셈블된 코드 분석 예

0x03: eb 03        // jmp +3 (→ 0x08)
0x0b: 7f f8        // jg -8 (→ 0x05)

`jmp`는 현재 위치(0x03) 다음(0x05) 기준 +3 → `0x08`에 jump
`jg`는 현재 위치(0x0b) 다음(0x0d) 기준 -8 → `0x05`에 jump

3.6.5 조건부 분기를 조건제어로 구현하기

핵심 개념:

  • C의 if/else 구문은 보통 조건부 점프(jcc) + 무조건 점프(jmp)의 조합으로 구현됨
  • 복잡한 분기 흐름을 이해하기 쉽게 C의 **goto 스타일 코드**로 표현 가능 → 실제 어셈블리 흐름과 구조가 비슷해짐

Practice Problem 3.16

🧪 주어진 C 코드:

void cond(short a, short *p) {
    if (a && *p < a)
        *p

🔧 주어진 어셈블리:

testq %rdi, %rdi         ; if (a == 0) → je .L1
je .L1

cmpq %rsi, (%rdi)        ; if (*p >= a) → jle .L1
jle .L1

movq %rdi, (%rsi)        ; *p = a
.L1:
rep; ret

✏️ A. goto 스타일 C 코드:

void cond_goto(short a, short *p) {
    if (!a)
        goto done;
    if (*p >= a)
        goto done;
    *p = a;
done:
    return;
}

🤔 B. 왜 조건 분기가 2번일까?

  • if ((a) && (*p < a))는 사실 두 조건을 순차적으로 검사해야 함:
    1. a != 0 확인
    2. p < a 확인
  • 이 논리식을 그대로 어셈블리로 바꾸면 각각 따로 검사하는 것이 효율적임 → 그래서 test와 cmp 두 개의 조건 분기가 생긴 것
  • if-else
    • 컴파일러는 else-문과 then-문에 대해 별도의 코드 블록을 생성한다.
    • 정확한 블록이 실행되도록 조건부와 무조건 분기를 삽입한다

3.6.6 조건부 이동으로 조건부 분기 구현하기

1. 기존 방식: 조건 분기 (Conditional Branch)

  • if문은 보통 jcc 명령어로 분기함
  • 조건이 맞으면 한쪽 코드 실행, 아니면 다른 쪽 실행
  • 단점: 분기 예측 실패(branch misprediction) 시 성능 저하 (15~30 사이클 손해)

2. 대안 방식: 조건 이동 (cmov)

  • cmov는 분기 없이 데이터만 선택적으로 이동
  • 둘 다 계산해놓고, 조건에 따라 한 쪽만 복사
  • 예:
    result = (x < y) ? (y - x) : (x - y);
    은 다음처럼 구현:
    subq %rdi, %rsi         ; y - x → %rax
subq %rsi, %rdi         ; x - y → %rdx
cmpq %rsi, %rdi
cmovge %rdx, %rax       ; if x >= y → result = x - y

3. 장단점 비교

항목조건부 분기 (jcc)조건부 이동 (cmov)
분기 예측필요함필요 없음
성능예측 실패 시 느림일정함
사용 조건제한 없음부작용 없고 가벼운 계산만 가능
대표 명령je, jg, jl 등cmove, cmovg, cmovl 등

4. 주의점

  • cmov는 양쪽 표현식 모두 실행됨 → 예: 포인터 역참조, 함수 호출, 부작용 있는 연산은 사용 불가
  • 간단한 수식일 때만 성능상 유리

3.6.7 반복문

  • 어셈블리에는 루프 명령어가 없고, 조건 검사 + 분기(jump) 조합으로 구현
  • do-while
    C 코드:
do {
    body;
} while (cond);

goto 변환:
loop:
    body;
    if (cond)
        goto loop;
  • while
방식 1: **Jump-to-Middle (JTM)**
goto test;
loop:
    body;
test:
    if (cond)
        goto loop;
  • 루프 들어가기 전 조건 검사 수행
  • GCC는 Og 수준에서 이 방식 사용
방식 2: **Guarded-Do (GD)**
if (!cond)
    goto done;
loop:
    body;
    if (cond)
        goto loop;
done:
  • 초기 조건 검사해서 바로 스킵 가능
  • GCC는 O1 이상에서 이 방식 사용
  • for
    • while 변환 후 goto 변환
    • 최적화 수준에 따라 while 루프의 번역 전략중 하나를 따름

3.6.8 Switch문

switch는 다중 분기(multiway branching) 구조

  • 여러 개의 if-else보다 간결하고 빠름

  • Jump table을 사용하면 분기 시간이 일정 (O(1))

  • Jump Table 방식

  • 점프 테이블 크기 = (최댓값 - 최솟값 + 1)

  • switch 인덱스 값으로 점프 테이블을 인덱싱하여 해당 주소로 jump

  • n이 100~106 사이일 때 → index = n - 100

    • index = switch_expr - base_case

  • 범위 초과하면 default case로 이동

    • if (index > max) goto default

  • 수백 개 case도 일정한 시간에 처리 가능

  • 중복 case label(같은 label에 매핑), 누락된 case, fall-through(goto 없이 다음 label 실행) 등도 처리 가능

상황점프 테이블 쓰나?
case 값 연속적, 개수 많음switch (n) {

case 1: ...
case 2: ...
case 3: ...
case 4: ...
} | ✅ 사용함 |
| case 값 띄엄띄엄, 개수 적음 | switch (n) {
case 1: ...
case 1000: ...
} | ❌ 조건문 사용 |
| 범위 너무 넓어서 테이블 낭비 심함 | | ❌ 조건문 사용 |

3.7 프로시저

  • 절차(Procedure)는 소프트웨어에서 중요한 추상화 기법 특정 기능을 수행하는 코드를 하나의 단위로 묶은 것 지정된 인자와 선택적 반환값을 통해 호출할 수 있게 함.
    • 코드 재사용
    • 내부 구현은 감추고 외부에는 명확한 인터페이스만 제공
    • 프로그램의 구조화와 가독성 향상
  • 절차 호출시 처리해야할 메커니즘
    • 제어권 전달
      • 호출 시: 프로그램 카운터(PC)를 Q의 시작 주소로 변경
      • 복귀 시: P의 다음 명령어 주소로 되돌림
    • 데이터 전달
      • P가 Q에게 인자(parameter)를 전달
      • Q가 결과 값을 P에게 반환
    • 메모리 할당과 반납
      • Q가 지역 변수를 위한 공간을 할당
      • Q가 종료되면 해당 공간을 해제

3.7.1 런타임 스택

  • 후입선출 메모리
  • 프로시저 호출 시 필요한 정보를 저장하는데 사용
  • 호출이 끝나면 자동으로 해당 정보 제거
  • 함수 호출 예시: P → Q P가 Q를 호출하면:
    • P는 일시 중지되고
    • Q만 실행되며, 필요한 지역 변수나 다른 함수 호출을 위해 자신만의 공간을 가짐
    • Q가 끝나면, 자신이 쓴 메모리를 반납하고, 다시 P로 복귀
  • Q를 호출했을때 P의 가장 상단에 return address를 저장해두어 돌아갈 수 있게 함
  • x86-64의 경우
    • 인자가 6개 이하 → 전부 레지스터로 처리 가능 (스택 필요 없음)
    • 지역 변수 없음, 다른 함수 호출 없음 → 스택 프레임 생략 가능 (leaf procedure)

3.7.2 제어의 이동

  • P → Q 프로시저 호출을 했을 때 돌아올 위치를 갖고 있어야함
    • call 명령어: 현재 명령어 다음 주소(=복귀 주소)를 스택에 push하고, 호출 함수의 주소로 점프
    • ret 명령어: 스택에서 복귀 주소를 pop해서, 그 주소로 점프

3.7.3 데이터 전송

  • 최대 6개의 정수형/포인터 인자 → 레지스터로 전달
인자 번호123456
64비트%rdi%rsi%rdx%rcx%r8%r9
32비트%edi%esi%edx%ecx%r8d%r9d
16비트%di%si%dx%cx%r8w%r9w
8비트%dil%sil%dl%cl%r8b%r9b
  • 6개 초과 인자 → 스택에 저장 (8바이트 단위로 정렬됨)
  • 반환값 : 항상 %rax를 사용
자료형크기 (바이트)크기 (비트)레지스터 사용 예
char1바이트8비트%al, %sil 등
short2바이트16비트%ax, %dx 등
int4바이트32비트%eax, %edi 등
long8바이트64비트%rax, %rdi 등
pointer8바이트64비트%rsi, %rdx 등

3.7.4 스택에서의 지역저장공간

  • 레지스터만으로는 부족해서 스택에 공간을 확보해야 해:

    1. 레지스터가 부족할 때

      → 많은 지역 변수를 저장해야 할 경우

    2. 주소 연산자(&)를 쓸 때

      → &x처럼 변수의 주소를 요구하면 메모리에 있어야 함

    3. 배열이나 구조체를 사용할 때

      → 메모리에 저장되어야 접근 가능

3.7.5 레지스터를 이용하는 지역저장소

  • 레지스터는 함수 간에 공유되는 자원이기 때문에 규칙(convention)이 필요
  • x86-64에서 레지스터 분류:
분류레지스터특징
callee-saved%rbx, %rbp, %r12–%r15호출된 함수(Q)가 책임지고 복구해야 함
caller-saved나머지 (예: %rax, %rcx, %rdx, %rsi, %rdi, %r8–%r11)호출하는 함수(P)가 저장하고 복구해야 함
스택 포인터%rsp항상 예외, 조작 시 매우 주의 필요

3.7.6 재귀 프로시저

재귀 호출에서도 스택 프레임이 각각 따로 생기기 때문에, 각 호출은 자기만의 지역 저장 공간을 갖고 충돌하지 않음.

x86-64에서 재귀 함수 호출 시:

  • 각 호출마다 리턴 주소 + 지역 변수 + 저장된 레지스터가 스택에 저장됨
  • 스택은 후입선출(LIFO)이므로, 호출 순서와 복귀 순서가 자연스럽게 맞아떨어짐
  • callee-saved 레지스터는 함수가 직접 저장/복원해줘야 함
profile
배재준
^_^
이전 포스트

[TIL/크래프톤 정글] DAY 27

다음 포스트

[TIL/크래프톤 정글] DAY 29

0개의 댓글