レジスタ、フレーム、そして 16 バイト — 呼び出し規約

一言でいうと

ネイティブコード生成は、木をCPUの命令(ここではx86-64のGNU asの構文)に移すことです。式の値はレジスター(%rax)に置き、足りなければスタックに一時的に積み、関数は呼び出し規約(System V AMD64)が定めるとおりに、引数をレジスターで渡してフレームを作ります。その約束のうち、いちばん静かに破られるのが、callの直前にスタックを16バイト境界に合わせるという規則です。

なぜ必要なのか

モジュール6のVMは、命令を1つ実行するたびに、Pythonのループが1周します。ネイティブコードには、そのループがありません。CPUが命令を直接読むからです。その代わり、VMが代わりにしてくれていたことを、コンパイラーがすべて決める必要があります。値をどのレジスターに置くか、ローカル変数をメモリのどこに置くか、関数を呼ぶとき引数をどこに渡して、戻り先をどう守るか。

この決定の一部は、自由には決められません。自分たちが作ったコードが、Cライブラリ(printf)や、ほかのコンパイラーが作ったコードと互いに呼び合うには、同じ約束を守る必要があります。Linux x86-64では、その約束がSystem V AMD64 ABIです。

どう動くのか

式は%raxに、足りなければスタックに。このコースのコード生成器は、いちばん単純な方式を使います。すべての式の値は%raxに置きます。二項演算は、左を計算してpush %raxでスタックに積んでおき、右を計算して%rcxに移したあと、左をpop %raxで降ろして演算します。レジスターを節約する方法(モジュール9のレジスター割り当て)は使わないので遅いですが、どんな式でも間違いなく移せます。

print 1 + 2 * 3;                           main 의 프레임
    movabs $1, %rax                        높은 주소
    push %rax          ← 왼쪽(1)을 올림     │ 돌아갈 주소        │  call 이 넣음
    movabs $2, %rax                        │ 이전 %rbp          │  ← %rbp
    push %rax          ← 왼쪽(2)을 올림     │ 지역 변수 슬롯 0    │  -8(%rbp)
    movabs $3, %rax                        │ 지역 변수 슬롯 1    │  -16(%rbp)
    mov %rax, %rcx                         │ (16의 배수로 맞춤)  │
    pop %rax           ← 2                 │ 식 계산용 push …    │  ← %rsp
    imul %rcx, %rax    ← 6                 낮은 주소
    mov %rax, %rcx
    pop %rax           ← 1
    add %rcx, %rax     ← 7
    mov %rax, %rdi     ← 첫 인자
    call mini_print_int

呼び出し規約。整数の引数は%rdi %rsi %rdx %rcx %r8 %r9の順に、戻り値は%raxで渡します。受ける側は、push %rbp · mov %rsp, %rbp · sub $N, %rspでフレームを作り、引数を自分のスロット(-8(%rbp)…)に移しておきます。本体を計算している間、それらのレジスターがほかの呼び出しに使われるからです。終わったらleave · retでフレームを片付けて戻ります。引数を左から計算して順にpushしておき、全部計算したあとで逆順にpopしてレジスターに載せれば、引数の計算中の呼び出しがレジスターを上書きしても安全です。

16バイトアライメント。ABIは、callする瞬間に%rspが16の倍数であることを求めます。関数に入ると、戻りアドレス(8バイト)のせいで8ずれていて、push %rbpでまた合い、フレームサイズを16の倍数にすれば、本体の先頭では合っている状態です。そのあと、式の計算用のpushが1つ増えるたびに、8バイトずつ、ずれたり合ったりします。そのため、今積んである値の数が奇数のままcallすると規則を破ります。1 + f(2)のように、左を積んだまま右で呼ぶ場合です。そのときは、sub $8, %rspで合わせてから呼び、戻ってきたらadd $8, %rspで元に戻します。

この規則は、破っても、たいてい静かです。printfの中で、16バイトアライメントを要求するSSE命令(movaps)に出会う日にだけ、セグメンテーションフォルトで落ちます。ある入力では動き、ある入力では動かない、いちばん悪い種類のバグです。このラボのランタイムヘルパー(/opt/fixtures/mini/runtime.c)は、呼ばれるたびにアライメントを確認して、すぐに知らせます。

ランタイムヘルパー。0による除算・INT64_MIN / -1・負の指数の検査は、コード生成器が式ごとにばらまいて書くのではなく、Cで書いたヘルパー(mini_div・mini_mod・mini_pow)に、行・桁といっしょに渡します。idivはINT64_MIN / -1でCPU例外(SIGFPE)を出すので、そのまま使うとインタプリターと意味が分かれます。

現場での姿

• gcc -O0 -Sの出力の形。最適化しないgccの出力も、この方式に似ています。すべてのローカル変数が-8(%rbp)のようなスタックの段にあり、使うたびに読み書きします。モジュール10で-O2の出力と並べて見ると、レジスター割り当てと最適化が何を取り除くかが見えます。
• アライメントの事故。手で書いたアセンブリや、JITが作ったコードがC関数を呼ぶときに、アライメントを破ってmovapsで落ちることは、実際によくあります。スタックのアライメントは、バグ報告に「ある入力でだけprintfの中でセグメンテーションフォルト」という形で現れます。
• ほかのABI。Windows x64は、引数レジスターが%rcx %rdx %r8 %r9で、呼ぶ側が32バイトの「シャドウスペース」を用意しなければなりません。同じCPUでも、OSごとに約束が違うことが、クロスコンパイルでよくぶつかる点です。

次のラボですること

codegen.pyに、mainと出力、算術・比較・ランタイムヘルパーの呼び出し、グローバル変数(.data)、ブロックのローカル変数(フレームのスロット)、if・while・短絡評価(ラベルとジャンプ)、関数と引数レジスターを順に作り、計算の途中での呼び出しでスタックのアライメントを守れているか確認したあと、プログラム全体をアセンブリに移してgccで焼くbuildまで作ります。採点ツールは、毎ステップ、自分のアセンブリを実際に焼いて実行し、インタプリターと同じ行を出力するかを確認します。