TT Lab
Get started
Learn Learning paths Courses

Compilers — Build a Small Language from Start to Finish

Lower to x86-64 and Actually Build It

Continue in TT Lab

Goal

You translate a Mini program into x86-64 assembly (GNU as, AT&T syntax), bake it with gcc, and run it. You translate expressions with %rax and the stack and functions with the System V calling convention, and you align the stack to 16 bytes even for calls in the middle of a computation.

Why it matters

Native code is read directly by the CPU without a VM loop, but in exchange the compiler must make all the decisions the VM used to make — where values go, frames, passing arguments — and to call the C library and be called by it, it must keep the ABI's promises. Code that breaks those promises usually runs well and then dies only for certain inputs.

The rules

받는 부분집합  함수는 맨 바깥에서만 선언하고 이름으로 직접 부른다 · 인자 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' 를 붙인다(실행 가능한 스택이 필요 없다는 표시)

Steps

  1. In Codegen in /root/mini/codegen.py, fill in emit, label, push, pop, call, expr (integers and booleans), stmt (print, expression statements), function, and new_slot — make the program run with only main and output.
  2. Fill in arith — unary, binary, and comparison, with / % ^ going to the runtime helpers.
  3. Fill in lookup, expr_more, and stmt_more — global variables and assignment.
  4. Fill in stmt_block — block local variables (slots) and shadowing.
  5. Fill in expr_control and stmt_control — short-circuit evaluation, if/else, and while.
  6. Fill in expr_call and stmt_function — functions, argument registers, and return. In this step's test programs, the number of slots pushed at the moment of the call is even.
  7. Check that call keeps the alignment — the grader runs programs that call in the middle of an argument and inside a right operand.
  8. Fill in the module's generate(program) and build(src, out_path). The grader bakes the fixed programs and 25 random programs and compares them against the interpreter.

Notes

main and output

function builds the body first, learns how many slots were used, and then attaches the prologue in front. An integer is movabs $value, %rax, and a boolean is mov $1 (or 0), %rax. print moves the value to %rdi and, depending on the type, calls mini_print_int or mini_print_bool.

Arithmetic and runtime helpers

Left → push → right → mov %rax, %rcx → pop so that the left ends up in %rax and the right in %rcx. AT&T's sub %rcx, %rax is rax = rax - rcx. For / % ^, load the two values in %rdi and %rsi and the line and column in %rdx and %rcx, and call the helper.

Global variables go in .data

If scopes is empty (the top of main), let is global. Append one line 'mini_g_: .quad 0' to data (where is the variable name), and write the value with mov %rax, mini_g_(%rip). When reading, mov from the address that lookup returned. To print a boolean variable as true/false, remember the type too.

Block local variables and the frame

Push an empty dictionary onto scopes for each block and discard it at the end. A local let gets a slot from new_slot and writes to -8*(slot+1)(%rbp). lookup looks from the innermost dictionary. The frame size must round the number of slots times 8 up to a multiple of 16 for the alignment at the start of the body to be right.

Labels and jumps

if is condition → cmp $0, %rax → je other → then → jmp end → other: → else → end:. while recomputes the condition every time at start:. For &&, if the left side is 0 (je), jump to the end and use the 0 in %rax directly as the result. Make labels like .L1 and .L2 so they do not collide.

Functions and the calling convention

fn first writes the name in functions (for recursion) and builds with function('mini_f_', parameters, body). The parameters are moved from %rdi %rsi … into slots after the prologue. A call pushes the arguments in turn, pops them in reverse to load the registers, and does call.

Calls in the middle of a computation and 16-byte alignment

push and pop keep counting pushed, so just before a call, check whether that number is odd. If it is odd, align with sub $8, %rsp, call, and restore with add $8, %rsp. 1 + f(2) calls f while the left side 1 is pushed, so it falls into this case.

Bake the whole program

generate makes main with a single Codegen as function(…, main=True) and joins .text, the finished functions, .data, and the GNU-stack marking. build writes the assembly to a temporary file after parsing and semantic analysis and links it with the runtime using gcc -O0 -fno-omit-frame-pointer.