🦥

C--で末尾再帰最適化を試してみる

に公開
Haskell
GHC
末尾再帰最適化
cmm
tech

想定される読者

  • Haskellの処理系であるGHCをインストールしたことがある
    • 処理系がハードディスクに残っている
  • C言語は、まあまあ読める
  • 言語の処理系そのものに興味がある
  • アセンブリ言語についても、おおまかには知っている

はじめに

Haskellの代表的な処理系であるGHCでは、ソースコードはC--(を構文木にしたもの)にコンパイルされる。CではなくC--を使う理由のひとつとして、処理系の流れのコントロールをより自由にできることがある。一例としてC--では末尾再帰の(明示的な)最適化が非常にわかりやすく表現できることを示す。

一例を示すのみで、構文の説明などはしない。また、著者の環境(x86-64, Linux)の例であり、それ以外の環境では調整が必要かもしれない。

まちがい等々がありましたら「やさしく」ご指摘ください。ここで紹介するコードは以下から入手できます。

https://github.com/YoshikuniJujo/cmm/tree/master/qiita/tail_call_opt

C--とは

C--がどんな感じなのかは、以下の論文にまとめられている。

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/ppdp.pdf

かんたんに説明すると、つぎのようになる。

高級言語のコンパイラを作成しようというときに、それぞれのハードウェアに対して、それぞれの機械語を生成するのではなく、どのハードウェアについても共通する中間的な表現を生成して、それをそれぞれの機械語のコードに変換するほうが効率がいい。そのような「共通する中間的な表現」として、C言語が使われることがあった。C言語のコンパイラは広く普及していたので、悪くない選択ではある。しかし、C言語はそのような「中間的な表現」として設計されているわけではないので、いろいろと問題が生じる。そのような問題を解決できるような「表現」が求められた。そこで設計されたのがC言語とアセンブラの中間的な表現であるC--である。

C--のコンパイラは独立したプロジェクトとして、いくつか開発されていたが、現在ではいずれもメンテナンスされていない。なので、メンテナンスされているC--の処理系として、GHCを使うことにする。

Cの関数mainから呼び出す

Cの関数mainから呼び出して、C--からの返り値を表示してみよう。以下のようなコードを用意する。

fun.cmm
foo()
{
	return(123);
}

fooという手続き(ブロック)を用意する。これは返り値として123を返す。つぎに、fooを呼び出すC言語のコードを用意しよう。

call_cmm.c
#include <stdio.h>

int
main(int argc, char *argv[])
{
	long ret;

	__asm__(
		"addq $-16, %%rsp\n\t"
		"moveq %%rbp, 8(%%rsp)\n\t"
		"moveq %%rsp, %%rbp\n\t"
		"moveq $print_ret, (%%rbp)\n\t"
		"jmp foo\n"
	"print_ret:\n\t"
		"moveq 8(%%rsp), %%rbp\n\t"
		"addq $16, %%rsp\n"
	: "=b"(ret)
	:
	: );

	printf("ret: %ld\n", ret);
	return 0;
}

関数mainのなかで、C--のfooを呼び出している。C--では%rbpをスタックポインタとして使うので、%rbpが指すアドレスにラベルprint_retの値を代入している。%rsp, %rbpはこの前後で値を変化させたくないので、つぎのような処理を行っている。

  • %rspから16減算する
  • %rspの値に8加算したアドレスに%rbpの値を代入
  • %rspの値を%rbpにコピーする
  • %rbpの値が指すアドレスにprint_retの値を代入
  • fooへジャンプ
  • fooからは%rbpの値が指すアドレスであるprint_retに処理がもどる
  • %rspの値に8加算したアドレスから%rbpに値をもどす
  • %rspに16加算する

たぶん、これで安全にC--の処理を呼び出すことができる(と思う)。コンパイルして試してみよう。

% ghc fun.cmm -no-hs-main call_cmm.c -o fun
% ./fun
ret: 123

GHCはデフォルトではCの関数mainを用意してくれる。今回は自前のmainを使いたいので-no-hs-mainオプションが必要だ。

末尾再帰の最適化とは

つぎのような階乗を求める処理があるとする。

  • 処理の名前はfactorial
  • 引数はnとsのふたつ
  • nが0より大きければn - 1とs * nを引数にしてfactorialを呼び出す
  • nが0ならばsの値をかえす

この処理はnを1ずつ小さくしていき、sはその都度n倍になる。つまり返り値はnの階乗になる。これをC言語の「関数呼び出し」で実装すると、factorialを呼ぶたびにスタックに「もどりアドレス」が積まれていき、nが0になったところで、そのスタックに積まれたアドレスに、順に処理がかえっていく。

しかし、そんなことをする必要はない。nが0になった段階で一気にはじめの呼び出しもとにもどってしまえばいい。そうすればスタック領域を無駄にすることもない。

そのように、「スタックにもどりアドレスを積んでいく」という処理と「その積まれたアドレスを順にたどる」という処理とを省略するのが末尾再帰の最適化である(たぶん)。

階乗を計算する処理(最適化していないバージョン)

末尾再帰最適化をしないバージョンの「階乗を計算する処理」は、つぎのようになる。

fac_no_opt.cmm
factorial(bits64 n, bits64 s)
{
	if (n > 0) {
		(bits64 ret) = call factorial(n - 1, s * n);
		return(ret);
	} else {
		return(s);
	}
}

foo()
{
	(bits64 ret) = call factorial(10, 1);
	return(ret);
}

だいたいわかるかと思う。呼び出しもとになるC言語のソースコードはcall_cmm.cを流用する。

% ghc fac_no_opt.cmm -no-hs-main call_cmm.c -o fac_no_opt
% ./fac_no_opt
ret: 3628800

階乗を計算する処理(最適化したバージョン)

それでは、末尾再帰を最適化したバージョンを試してみよう。C--には処理を呼び出す方法にcallだけではなくjumpもあるというところがポイントだ。つぎのようになる。

fac_opt.cmm
factorial(bits64 n, bits64 s)
{
	if (n > 0) {
		jump factorial(n - 1, s * n);
	} else {
		return(s);
	}
}

foo()
{
	(bits64 ret) = call factorial(10, 1);
	return(ret);
}

nが0より大きかったときの処理がcallではなくてjumpになっている。jumpで飛んだときには処理はもどってこない。スタックにもどりアドレスが積まれることもない。そうしてn回factorialに飛んで、n + 1回目にreturn命令でfactorialをはじめに呼んだfooに処理がもどる。余計なスタックの消費や余計なジャンプが省略されている。コンパイルして試してみよう。

% ghc fac_opt.cmm -no-hs-main call_cmm.c -o fac_opt
% ./fac_opt
ret: 3628800

1からnまでの和を計算する処理で比較

「階乗」だと結果が大きくなりすぎるので1からnまでの総和という題材で最適化する前後の処理を比較する。

最適化なし

最適化なしでのコードはつぎのようになる。

sum_no_opt.cmm
summation(bits64 n, bits64 s)
{
	if (n > 0) {
		(bits64 ret) = call summation(n - 1, s + n);
		return(ret)
	} else {
		return(s);
	}
}

foo()
{
	(bits64 ret) = call summation(2000000, 0);
	return(ret);
}

乗算を和算に変えた。とりあえずnを2000000(200万)にしてみた。試してみよう。

% ghc sum_no_opt.cmm -no-hs-main call_cmm.c -o sum_no_opt
% ./sum_no_opt
zsh: segmentation fault ./sum_no_opt

スタックの領域を使い切ってしまったのだろう。セグメンテーションフォールトになっている。

最適化した場合

末尾再帰を最適化したコードはつぎのようになる。

sum_opt.cmm
summation(bits64 n, bits64 s)
{
	if (n > 0) {
		jump summation(n - 1, s + n);
	} else {
		return(s);
	}
}

foo()
{
	(bits64 ret) = call summation(2000000, 0);
	return(ret)
}

最適化していないバージョンでセグメンテーションフォールトになった2000000(200万)で試してみる。

% ghc sum_opt.cmm -no-hs-main call_cmm.c -o sum_opt
% ./sum_opt
ret: 2000001000000

全然、余裕だ。それでは2000000(200万)ではなく1000000000(10億)で試してみよう。

sum_opt.cmm
...
	(bits64 ret) = call summation(1000000000, 0);
...

% ghc sum_opt.cmm -no-hs-main call_camm.c -o sum_opt
% ./sum_opt
ret: 500000000500000000

10億回、呼び出してもビクともしない。

まとめ

高級言語のコンパイラを作成するときに、それぞれのハードウェアごとの機械語を生成するのは大変だ。そのようなときにC言語を中間言語として使うのは「あり」だ。しかし、C言語はもともとそのような用途に使うようには作られていないので、いろいろと問題がある。その問題のひとつに、末尾再帰の最適化が困難というものがある。C--は高級言語をコンパイルするときの中間優現として設計された言語である。中間表現として、C--がCに対して優れている点として「末尾再帰の最適化がかんたん」という点がある。処理のブロックを呼び出すときにcallというやりかたでなく、jumpというやりかたが用意してあるためだ。かんたんな例で、C--による末尾再帰の最適化の様子を示した。

Discussion