Compilers — Build a Small Language from Start to Finish

Lower to x86-64 and Actually Build It

한국어 원문으로 표시합니다.

목표

미니 프로그램을 x86-64 어셈블리(GNU as, AT&T 문법)로 옮겨 gcc 로 구워 실행합니다. 식은 %rax 와 스택으로, 함수는 System V 호출 규약으로 옮기고, 계산 도중의 호출에서도 스택을 16바이트에 맞춥니다.

왜 중요한가

네이티브 코드는 VM 의 반복문 없이 CPU 가 직접 읽지만, 그 대신 VM 이 해 주던 결정 — 값의 자리, 프레임, 인자 넘기기 — 을 컴파일러가 모두 내려야 하고, C 라이브러리와 서로 부르려면 ABI 의 약속을 지켜야 합니다. 그 약속을 어긴 코드는 대개 잘 돌다가 어떤 입력에서만 죽습니다.

규칙

받는 부분집합  함수는 맨 바깥에서만 선언하고 이름으로 직접 부른다 · 인자 6개까지 · 매개변수와 반환값은 정수
             (클로저·함수 값·실행 중 타입 오류·스택 넘침은 이 백엔드가 다루지 않는다)
값의 자리     모든 식의 값은 %rax. bool 은 0/1. 두 항: 왼쪽 → push %rax → 오른쪽 → mov %rax, %rcx → pop %rax → 연산
             정수 리터럴은 movabs(32비트를 넘는 즉시값) · 비교는 cmp %rcx, %rax → setl 등 → movzbq %al, %rax
             ! 는 xor $1, %rax · && 와 || 는 cmp $0 과 je/jne 로 오른쪽을 건너뛴다
이름의 자리   main 맨 위의 let → .data 의 mini_g_<이름>: .quad 0, 읽기·쓰기는 mini_g_<이름>(%rip)
             그 밖의 let 과 매개변수 → 프레임 슬롯 k 는 -8*(k+1)(%rbp). 슬롯은 함수마다 0 부터 하나씩(재사용 없음)
함수          mini_f_<이름>. 들어오면 push %rbp · mov %rsp, %rbp · sub $(슬롯 수×8 을 16의 배수로 올림), %rsp
             인자를 %rdi %rsi %rdx %rcx %r8 %r9 에서 자기 슬롯으로 옮긴다 · return: 값을 %rax 에 → leave · ret
             return 없이 끝나면 mov $0, %rax · leave · ret. main 은 .globl main, 맨 위 문장들을 차례로 실행
호출          인자를 왼쪽부터 계산해 push, 다 되면 거꾸로 pop 해 인자 레지스터에 싣고 call mini_f_<이름>
정렬          call 직전 %rsp 는 16의 배수. 지금 올려 둔 칸 수가 홀수면 sub $8, %rsp · call · add $8, %rsp
런타임        mini_print_int(v) · mini_print_bool(v) · mini_div/mini_mod/mini_pow(a, b, 줄, 칸)
             (/opt/fixtures/mini/runtime.c — 부를 때마다 정렬을 확인하고, 0 나누기 등은 인터프리터와 같은 글자로 끝낸다)
끝            '.section .note.GNU-stack,"",@progbits' 를 붙인다(실행 가능한 스택이 필요 없다는 표시)

단계

/root/mini/codegen.py 의 Codegen 에서 emit·label·push·pop·call·expr(정수·참거짓)·stmt(print·식 문장)·function·new_slot 을 채웁니다 — main 과 출력만으로 프로그램이 돌게 합니다.
arith 를 채웁니다 — 단항·두 항·비교, / % ^ 는 런타임 도우미로.
lookup·expr_more·stmt_more 를 채웁니다 — 전역 변수와 대입.
stmt_block 을 채웁니다 — 블록 지역 변수(슬롯)와 섀도잉.
expr_control·stmt_control 을 채웁니다 — 단락 평가, if/else, while.
expr_call·stmt_function 을 채웁니다 — 함수, 인자 레지스터, return. 이 단계의 시험 프로그램은 호출 순간 올려 둔 칸이 짝수입니다.
call 이 정렬을 지키는지 확인합니다 — 채점기가 인자 한가운데·오른쪽 피연산자 속에서 부르는 프로그램을 돌립니다.
모듈의 generate(program) 과 build(src, out_path) 를 채웁니다. 채점기가 고정 프로그램과 무작위 프로그램 25편을 구워 인터프리터와 대조합니다.

참고

python3 /root/mini/mini.py asm 파일.mini 는 어셈블리를, python3 /root/mini/mini.py build 파일.mini -o prog && ./prog 는 실행 파일을 만듭니다.
1–7단계에서 채점기는 Codegen().function("main", [], 문장들, main=True) 로 main 을 만들고 done·data 를 이어 붙여 굽습니다. generate 는 8단계에서 채웁니다.
흔한 실수: 64비트 즉시값을 32비트 mov 로 싣는 것, sub 의 피연산자 순서(AT&T 는 sub 원본, 대상), 인자 레지스터를 거꾸로 싣는 것, return 에 leave 를 빠뜨리는 것, 프레임 크기를 16의 배수로 맞추지 않는 것, 계산 도중의 call 에서 정렬을 잊는 것.
세션은 60분에 시작해 ＋시간으로 늘릴 수 있고, 끝나면 /root/mini 가 사라집니다.

main 과 출력

function 은 몸체를 먼저 만들어 쓴 슬롯 수를 안 뒤 프롤로그를 앞에 붙입니다. 정수는 movabs $값, %rax, 참거짓은 mov $1(또는 0), %rax. print 는 값을 %rdi 로 옮기고 타입에 따라 mini_print_int 또는 mini_print_bool 을 부릅니다.

산술과 런타임 도우미

왼쪽 → push → 오른쪽 → mov %rax, %rcx → pop 으로 %rax 에 왼쪽, %rcx 에 오른쪽이 오게 합니다. AT&T 의 sub %rcx, %rax 는 rax = rax - rcx 입니다. / % ^ 는 %rdi %rsi 에 두 값, %rdx %rcx 에 줄·칸을 싣고 도우미를 부릅니다.

전역 변수는 .data 에

scopes 가 비어 있으면(main 의 맨 위) let 은 전역입니다. data 에 'mini_g_이름: .quad 0' 을 한 줄 붙이고, 값을 mov %rax, mini_g_이름(%rip) 로 씁니다. 읽을 때는 lookup 이 돌려준 주소에서 mov 합니다. 참거짓 변수를 true/false 로 찍으려면 타입도 함께 기억합니다.

블록 지역 변수와 프레임

블록마다 scopes 에 빈 사전을 쌓고 끝나면 버립니다. 지역 let 은 new_slot 으로 슬롯을 받고 -8*(슬롯+1)(%rbp) 에 씁니다. lookup 은 안쪽 사전부터 봅니다. 프레임 크기는 슬롯 수×8 을 16의 배수로 올려야 몸체 처음의 정렬이 맞습니다.

이름표와 점프

if 는 조건 → cmp $0, %rax → je 다른쪽 → then → jmp 끝 → 다른쪽: → else → 끝:. while 은 처음: 에서 조건을 매번 다시 계산합니다. && 는 왼쪽이 0 이면(je) 끝으로 뛰어 %rax 의 0 을 그대로 결과로 씁니다. 이름표는 .L1, .L2 처럼 겹치지 않게 만듭니다.

함수와 호출 규약

fn 은 functions 에 이름을 먼저 적고(재귀) function('mini_f_이름', 매개변수, 몸체) 로 만듭니다. 매개변수는 프롤로그 뒤에 %rdi %rsi … 에서 슬롯으로 옮깁니다. 호출은 인자를 차례로 push 한 뒤 거꾸로 pop 해 레지스터에 싣고 call 합니다.

계산 도중의 호출과 16바이트 정렬

push 와 pop 이 pushed 를 세고 있으니 call 직전에 그 수가 홀수인지 봅니다. 홀수면 sub $8, %rsp 로 맞춘 뒤 부르고 add $8, %rsp 로 되돌립니다. 1 + f(2) 는 왼쪽 1 을 올려 둔 채 f 를 부르므로 이 경우에 걸립니다.

프로그램 전체를 굽는다

generate 는 Codegen 하나로 main 을 function(…, main=True) 로 만들고 .text · 다 만든 함수들 · .data · GNU-stack 표시를 잇습니다. build 는 파싱·의미 분석 뒤 어셈블리를 임시 파일에 쓰고 gcc -O0 -fno-omit-frame-pointer 로 런타임과 함께 링크합니다.