コマ6: 関数呼び出し・再帰

int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

int main() {
    return fib(10);
}

この回で扱う範囲

対象にするプログラムは、main に加えてユーザー定義関数を含むものに限定する。

これまでに扱ったすべての機能（変数、式、制御構文）を、main 以外の関数内でも使用できる。

scalar_type ::= 'int'            /* ポインタはコマ7、char はコマ8 */
obj_type    ::= scalar_type
ret_type    ::= scalar_type      /* void はコマ7 */

program       ::= external_decl { external_decl }
external_decl ::= func_proto
                | func_def       /* struct 定義はコマ12、グローバル変数はコマ13 */
var_decl      ::= obj_type IDENT ';'

param       ::= scalar_type IDENT
param_list  ::= param { ',' param }
func_proto  ::= ret_type IDENT '(' [ param_list ] ')' ';'   /* '...' はコマ10 */
func_def    ::= ret_type IDENT '(' [ param_list ] ')' func_body
func_body   ::= '{' { var_decl } { stmt } '}'

stmt        ::= expr_stmt
              | block
              | if_stmt
              | while_stmt
              | for_stmt
              | 'break' ';'
              | 'continue' ';'
              | 'return' expr ';'
expr_stmt   ::= [ expr ] ';'
block       ::= '{' { stmt } '}'
if_stmt     ::= 'if' '(' expr ')' stmt [ 'else' stmt ]
while_stmt  ::= 'while' '(' expr ')' stmt
for_stmt    ::= 'for' '(' [ expr ] ';' [ expr ] ';' [ expr ] ')' stmt

expr        ::= assign_expr
assign_expr ::= unary_expr '=' assign_expr   /* 右結合 */
              | cond_expr
cond_expr   ::= binary_expr [ '?' expr ':' cond_expr ]   /* 右結合 */
binary_expr ::= unary_expr { bin_op unary_expr }
bin_op      ::= '*' | '/' | '%'  /* 論理 && || はコマ13 */
              | '+' | '-'
              | '<' | '>' | '<=' | '>='
              | '==' | '!='
unary_expr  ::= primary_expr
              | '-'  unary_expr
              | '++' unary_expr
              | '--' unary_expr
primary_expr ::= INT_LITERAL
               | IDENT '(' [ arg_list ] ')'
               | IDENT
               | '(' expr ')'
arg_list    ::= assign_expr { ',' assign_expr }

AST を確認する

関数定義

python3 scaffold/parse_viewer.py sessions/06_functions_recursion/tests/target.c

target.c の中身は、冒頭に挙げた fib のプログラムと同じである。

(program
  (funcdef "fib" :type int
    (params (param "n" :type int))
    (block
      (if
        (cond
          (le (var "n") (num 1)))
        (then
          (block
            (return (var "n")))))
      (return
        (add
          (call "fib"
            (args
              (sub (var "n") (num 1))))
          (call "fib"
            (args
              (sub (var "n") (num 2))))))))
  (funcdef "main" :type int (params)
    (block
      (return
        (call "fib"
          (args (num 10)))))))

新しく登場するノードは次の通り。

ND_CALL は式である。 codegen() で処理し、結果は a0 に置く。

相互再帰のAST

python3 scaffold/parse_viewer.py sessions/06_functions_recursion/tests/mutual_rec.c

このプログラムは、冒頭に宣言だけを2つ置き、そのあとに定義が続く（以下は本体を1行に詰めて示す）。

int is_even(int n);
int is_odd(int n);

int is_even(int n) { if (n == 0) { return 1; } return is_odd(n - 1); }
int is_odd(int n)  { if (n == 0) { return 0; } return is_even(n - 1); }

int main() { return is_even(10) + is_odd(7) * 10; }

S式の全文は上の parse_viewer.py で確認できる。見どころは冒頭で、 定義より先に宣言が funcproto として現れる点である。

(program
  (funcproto "is_even" :type int
    (params (param "n" :type int)))
  (funcproto "is_odd" :type int
    (params (param "n" :type int)))
  (funcdef "is_even" ...)   ; 中身は fib と同じ形（if と call）
  (funcdef "is_odd" ...)
  (funcdef "main" ...))

この例では、ソースの先頭に書いた関数プロトタイプが先に funcproto として現れる。 Parser は宣言を前方へ移動せず、ソースに書かれた外部宣言の順序を保存する。 相互に呼び合う関数は、呼び出しより前に相手のプロトタイプを宣言しておく。

RV64の関数呼び出し規約

関数呼び出しでは、呼び出す側と呼び出される側の間で、どのレジスタを何に使うかを決めておく必要がある。 この取り決めを ABI の一部として扱う。

この回で使う主な約束は次の通り。

関数を呼び出すとき、call f という命令を使う。

call fib

この命令は、次の2つのことを行う。

1. 次の命令のアドレスを ra に保存する
2. fib ラベルへジャンプする

呼び出された関数は、最後に ret を実行する。 ret は ra に保存されたアドレスへ戻る。

したがって、再帰を含む関数呼び出しを行うときは、自らの ra を関数の先頭で保存し、末尾で復元する必要がある。 これはコマ3のプロローグ・エピローグがすでに行っている。

関数を呼ぶたびに新しいフレームが低いアドレス側へ積まれ、ret するたびに1つ上のフレームへ戻る。 各呼び出しが自分専用の引数スロットを持つため、再帰しても n の値が混ざらない。

引数を受け取る側

関数が呼ばれた直後、引数は a0, a1, … に入っている。

int add(int a, int b) {
    return a + b;
}

この関数が add(3, 5) と呼ばれた場合、関数に入った直後は次の状態になる。

ただし、以後の計算で a0 や a1 はすぐ上書きされる。 そのため、関数の先頭で引数をローカル変数と同じようにスタックへ保存する。

gen_func() では、ローカル変数を集める前に、まず funcdef.params を self.alloc_local() で登録する （全体の手順は後述の「gen_func の変更点」にまとめてある）。

たとえば int add(int a, int b) なら、次のように配置できる。

s0 - 24   param a
s0 - 32   param b

プロローグ後に、引数レジスタを保存する。

sd a0, -24(s0)
sd a1, -32(s0)

これ以降、引数 a, b は通常のローカル変数と同じように codegen_lval() でアドレスを取り、ld で値を読める。

codegen_Call の生成パターン

呼び出す側は、call f を出す直前に第1引数を a0、第2引数を a1、…（最大 a7）へ置く。 戻ってくると戻り値は a0 に入っているので、ND_CALL の結果も他の式と同じく a0 に残る。

ただし、引数を左から順に評価すると、各引数の結果は毎回 a0 に入る。 そのままだと、次の引数を評価したときに前の引数が上書きされる。 そのため、各引数を評価したら一度スタックに保存する。

codegen_Call(node) は次の流れで実装する。

1. 引数を左から順に self.codegen する
2. 各引数の結果をスタックに積む（_push_a0）
3. 積んだ逆順に _pop_into で引数レジスタへ戻す（最後の引数から a0 まで）
4. _pop_into が sp と _depth を戻すため、引数分の sp の調整は追加しない
5. sp を16バイト境界へ揃える（次節。積んでいる一時値が奇数個なら 8 詰める）
6. call 関数名 を出す
7. 5 で詰めた分を戻す

引数を arg0, arg1, arg2 の順にpushすると、最後にpushしたものが一番上に来る。

sp + 0   arg2
sp + 8   arg1
sp + 16  arg0

そのため、3引数なら _pop_into('a2')、_pop_into('a1')、 _pop_into('a0') の順に戻す。各呼び出しは 0(sp) の値を読み、 sp を8バイト戻すと同時に _depth を1減らす。 一般には for i in reversed(range(len(node.args))) の順に self._pop_into(f'a{i}') を呼ぶ。

最後に push した引数が sp + 0 に来るため、レジスタへは逆順に読み出す。

call 前のスタックアラインメント

RV64の呼び出し規約では、call する時点で sp が16バイト境界に揃っている必要がある。 違反すると Illegal instruction や Bus error になり、原因の特定が難しい。

sp を動かしているのは次の2つだけである。

プロローグは常に16の倍数なので、call の時点で sp がずれるかどうかは そのとき何個の一時値を積んでいるかだけで決まる。

call 時の sp のずれ = 積んでいる一時値の個数 × 8
→ 奇数個なら 8 バイトずれている

ここで注意したいのは、引数の個数ではなく、呼び出しを囲む式が積んだ一時値が効くという点である。 codegen_Call() は積んだ引数をレジスタへ戻して sp も戻すので、 引数のpushは call の時点では消えている。残るのは外側の式の分である。

return n * fact(n - 1);   // * の左辺 n を1個積んだまま fact を呼ぶ → 8 ずれる

そこで、積んでいる個数を数えておき、call の直前で判定する。

_push_a0()  で depth += 1
_pop_into() で depth -= 1

# codegen_Call の最後、引数を戻したあと
pad = 8 if depth is odd else 0
self.emit(f"  addi sp, sp, -{pad}")   ← 奇数のときだけ
self.emit(f"  call {name}")
self.emit(f"  addi sp, sp, {pad}")    ← 呼び出しから戻ったら元へ

引数の積み下ろし（前節の図）やフレームの積み重なり（「RV64の関数呼び出し規約」の図）とは別の場面で、 ここで見ているのは call を出す瞬間に sp が16バイト境界のどこに居るかである。

depth は関数ごとに0に戻す。関数を出し終えた時点で0でなければ pushとpopの数が合っていないので、その場で気づける。

再帰呼び出しで壊れやすい点

次の式を考える。

return fib(n - 1) + fib(n - 2);

左側の fib(n - 1) を呼ぶと、戻り値は a0 に入る。 しかし、右側の fib(n - 2) を呼ぶと、その呼び出しでも a0 が使われる。 つまり、左側の結果は右側の呼び出しで上書きされる。

これはコマ2から使っている二項演算の退避パターンで解決する。

左辺を codegen する  → a0 に fib(n-1) の結果
左辺の結果 a0 をスタックに退避する
右辺を codegen する  → a0 に fib(n-2) の結果
退避していた左辺を a1 に戻す
add a0, a1, a0       → a0 = fib(n-1) + fib(n-2)

ND_CALL も普通の式と同じように結果を a0 に残すため、既存の二項演算パターンがそのまま再帰呼び出しにも効く。

なお、右辺の fib(n - 2) を呼ぶ時点では左辺の結果を1個積んだままである。 前節のアラインメント調整が要るのは、まさにこの状態で call を出すときである。

関数プロトタイプ

相互再帰では、関数定義の前に関数宣言が現れることがある。

int is_even(int n);
int is_odd(int n);

Parser はこれを ND_FUNCPROTO として返す。

(funcproto "is_even" :type int
  (params (param "n" :type int)))

コマ6では、関数プロトタイプに対してアセンブリを出す必要はない。 main() の最後のループでは、ND_FUNCDEF だけを gen_func() すればよい。

gen_func の変更点

gen_func(node) に、引数関連の処理を追加する。 新しいスキャフォールドでは、gen_func の流れは _reset_func_state → _emit_func_prologue → _emit_func_body → _emit_func_epilogue のフックメソッドで構成されている。

1. _reset_func_state() で self._locals と self._stack_offset を初期化する
2. return用の共通ラベルを作る
3. _alloc_params() で funcdef.params を self.alloc_local() する  ← コマ6で追加
4. self.collect_decls(funcdef.body) でローカル変数を集める
5. frame_size = align_to(self._stack_offset, 16) を計算する
6. プロローグを出す
7. a0, a1, ... を params のスロットへ sd する  ← コマ6で追加
8. 関数本体の各文を self.gen_stmt(node) で出力する
9. return用ラベルを出力する
10. エピローグを出力する

編集するファイル

• mycc.py

importlib でコマ5 の Codegen05 を継承した Codegen06 に、以下の機能を追加する（スケルトンにあらかじめ書かれている）。

主な追加・変更点は次の通り。

実装手順

1. スケルトンの Codegen06 がコマ5 の Codegen を importlib で継承していることを確認する。コマ2〜5 で埋めた codegen_Num / codegen_Var / codegen_Assign / codegen_Neg / _binary_value / codegen_Add〜codegen_Le と、codegen() のディスパッチ・_reset_func_state()・gen_func() はコマ6 のスケルトンに完成形として書かれている。この回で書き直すものは無い
2. _alloc_params(node) を実装する（node.params の各パラメータ（Decl ノード）の name を self.alloc_local() に渡し、ローカル変数と同じスロットを確保する。_reset_func_state() が self.collect_decls(node.body) より先にこれを呼ぶ形はあらかじめ書かれている）
3. _emit_func_prologue(name, frame_size) の末尾を埋める（_reset_func_state() が置いた self._current_params を先頭から見て、i 番目のパラメータを a{i} から self.lookup_var() のオフセットへ sd する。フレーム確保と ra/s0 の退避まではあらかじめ書かれている）
4. codegen_Call(node) を実装する（self._gen_call(node.name, node.args) に委譲するだけ）
5. _gen_call(name, args) の引数の並べ方を実装する（引数を左から順に codegen し、そのつど self._push_a0() で積む。先に評価した値をレジスタへ直接置くと後続の引数評価で壊れるためである。積み終えたら積んだ順の逆から self._pop_into(f'a{i}') で a0〜a7 へ戻し、call {name} を emit する）
6. _gen_call の call の直前に 16 バイト境界へのそろえを入れる（ずれるかどうかは引数の個数ではなく、そのとき外側の式が積んでいる一時値の個数 self._depth の偶奇で決まる。pad = 8 if self._depth % 2 else 0 とし、pad が 0 でなければ call の前に addi sp, sp, -pad、戻ってきたら addi sp, sp, pad を出す）

tests/

上から順に通していくと、どこで詰まっているかが1機能ぶんに絞られる。 「通る目安」は実装手順の番号である。

call_add.c だけが通って他が落ちるときは、手順6 のアラインメントを疑う。 call_add.c の add(3, 4) は return 直下にあり、self._depth が 0 なので padding を出さなくても偶然通ってしまうからである。

テスト

python3 scaffold/test_runner.py sessions/06_functions_recursion

tests/target.c がコンパイルでき、終了コード 55 になれば基本形は成功。

個別に動かす場合は、次のようにする。

python3 sessions/06_functions_recursion/mycc.py sessions/06_functions_recursion/tests/target.c \
  | riscv64-linux-gnu-gcc -x assembler -static - -o out

qemu-riscv64 ./out
echo $?

注意

Core仕様では、宣言・定義の固定仮引数と呼出しの実引数は最大8個である。 提供Parserが9個以上を診断するため、a8やスタック渡しを生成する必要はない。 この回では、引数は最大8個まで扱う。 9個以上のスタック渡し・可変長引数・型チェック・末尾呼び出し最適化などは扱わない。 この回の外にある話題の一覧は rv64_reference.md の「呼び出し規約」にまとめてある。

ND_CALL の引数は1個もない場合もある。 引数なしの関数呼び出しでは、引数をpushせず、直接 call を出す。

main 関数も ND_FUNCDEF の1つである。 main にはパラメータがないため、gen_func() の引数処理部分は特に影響しない。

main 以外の関数の return も、コマ4と同じく共通エピローグラベルへジャンプする。 各関数が独立した _ret_label を持つことに注意する。

ここまでで着手できる発展課題

関数呼び出しまで学んだので、測定基盤なしで始められる最適化入門 B1・B2・ B3と、&&/|| の短絡評価を仕様へ寄せる S1 に着手できる。

S1の概念の学習と check.py による単体検査は、この回から始められる。 構造体・malloc を使う実行テストにはコマ12までの実装が必要で、 golden.py の完走にはコマ15で完成させた final/mycc.py が必要になる。

関数呼び出し前後で ra や引数レジスタがどう退避されるかを1命令ずつ確認したいときは、学習ツールの実行表示 に貼り付ける。

この回の完成形に相当する OCaml 版参考実装が ../../workbook/ocaml/README.md にある。完成相当の実装なので、まず自分の実装方針を検討してから確認すること。

この資料の原稿を見る