末尾呼び出し最適化 — 再帰をループに変える

この回の位置づけ

コマ6 の資料で「扱わない」とした末尾呼び出し最適化の回収である。 B1 は O7・O3 と、B2 は O4 と題材が重なるが、 末尾呼び出し最適化は O1〜O7 のどれにも出てこない。この回だけの題材である。 効果を命令数で見たいときは、O1 の物差し（静的／動的命令数）をそのまま使える。

末尾呼び出しとは

関数の最後の仕事が別の関数の呼び出しであるとき、それを末尾呼び出しという。

int sum_to(int n, int acc) {
    if (n == 0) { return acc; }
    return sum_to(n - 1, acc + n);   // 末尾呼び出し
}

対して、次は末尾呼び出しではない。

int fact(int n) {
    if (n == 0) { return 1; }
    return n * fact(n - 1);   // 呼び出しの後に掛け算が残っている
}

違いは「呼び出しから戻ってきた後に、まだやることがあるか」である。 やることが残っていないなら、呼び出し元のフレームはもう用済みである。

なぜジャンプに変えられるのか

sum_to が sum_to を呼ぶとき、いまのコンパイラは新しいフレームを積む。

sum_to(1000000, 0) のフレーム
  sum_to(999999, 1000000) のフレーム
    sum_to(999998, 1999999) のフレーム
      ...  100万段  →  スタックがあふれる

しかし各フレームは、呼び出しから戻った瞬間に「戻り値をそのまま返す」だけである。 つまりフレームを積む意味がない。引数だけ新しい値に書き換えて、 関数の先頭に戻れば、同じ計算ができる。

  # return sum_to(n - 1, acc + n);
  # 新しい引数を計算して、引数スロットに書き戻し…
  sd a0, -24(s0)      # n  ← n - 1
  sd a1, -32(s0)      # acc ← acc + n
  j .Ltc_sum_to       # フレームを積まずに先頭へ戻る

call が j になり、フレームが1つも増えない。再帰がループになった。

実装の3つの注意点

1. どこへ戻るか — プロローグの後

戻り先は関数の先頭ラベルではない。プロローグ（フレーム確保）と 引数の保存を飛ばした、本体の直前である。

sum_to:
  addi sp, sp, -32       ┐ プロローグ
  sd ra, 24(sp)          │  ここに戻ると
  ...                    │  フレームが増えてしまう
  sd a0, -24(s0)         ┘ 引数の保存
.Ltc_sum_to:             ← ここへ戻る
  # 本体

ラッパー tccc.py が、この位置にラベルを置いて cg.tc_label に入れてくれる。

2. 引数は「全部評価してから」書き戻す

return sum_to(n - 1, acc + n);

第1引数を先に n のスロットへ書き込んでしまうと、 第2引数の acc + n が新しい n を読んでしまう。 コマ2 以来の退避パターンと同じ理由で、 すべて評価して退避 → まとめて書き戻すの順にする。

3. 変換してよい形を厳しく判定する

「怪しいものは変換しない」— B1 と同じく、最適化の基本姿勢である。 判定が広すぎると fixed17 が壊れるので、そこで気づける。

実装

python3 tccc.py tests/deep_sum.c            # 生成結果を見る
python3 tccc.py tests/deep_sum.c | grep -c call   # call が減っているか

テスト

python3 check.py     # Step ごとの単体テスト(未実装は SKIP)
python3 golden.py    # 深い末尾再帰 + fixed17

golden.py は3つを続けて確認する。

1. 最適化なしで tests/deep_sum.c（100万回の末尾再帰）が落ちること
2. 最適化ありで同じテストが通ること
3. fixed17 が壊れていないこと

「落ちていたものが通るようになる」ので、効果が命令数より分かりやすい。

発展課題

1. 相互末尾再帰: is_even / is_odd のような相互再帰は、 自分自身ではないので今回の判定では変換されない。 別の関数への末尾呼び出しを変換するには何が必要か考える （フレームの解放、引数の渡し方、ra の扱い）
2. 末尾位置の拡張: if (c) return f(x); else return f(y); の両方が 末尾呼び出しであることは、いまの判定でも扱えている。 では return c ? f(x) : g(y); は？三項演算子は Core にあるので実際に試せる。 is_self_tail_call を Cond の両方の枝に再帰させる拡張を設計する
3. fact を末尾再帰に書き換える: fact(n) を累積引数つきの fact_acc(n, acc) に書き換え、深い階乗が動くことを確かめる
4. フレームサイズの計測: 最適化あり／なしで sp がどこまで下がるかを gdb-multiarch で観察する

この資料の原稿を見る