x86-64 に移して実際に焼く

目標

ミニのプログラムを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でアライメントを忘れる、の6つです。
セッションは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に2つの値、%rdx %rcxに行・桁を載せて、ヘルパーを呼びます。

グローバル変数は.dataに

scopesが空なら(mainのいちばん上)、letはグローバルです。dataに「mini_g_名前: .quad 0」を1行追加し、値は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を1つ使ってmainをfunction(…, main=True)で作り、.text・作り終えた関数たち・.data・GNU-stackの印をつなげます。buildは、構文解析・意味解析のあと、アセンブリを一時ファイルに書き、gcc -O0 -fno-omit-frame-pointerで、ランタイムといっしょにリンクします。