LoginSignup
37
22

More than 5 years have passed since last update.

@YoshikuniJujo

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

Last updated at Posted at 2018-08-14

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

想定される読者

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

はじめに

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

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

まちがい等々ありましたら、やさしく、ご指摘ください。

ここで紹介するコードは以下から入手できます。

C--とは

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

C--: a portable assembly language that supports garbage collection

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

高級言語のコンパイラを作成しようというときに、それぞれのハードウェアに対して、それぞれの機械語を生成するのではなく、ハードウェアに共通する中間的な表現を生成して、それをそれぞれの機械語のコードに変換するほうが効率がいい。そのような「共通する中間的な表現」として、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"
                "movq %%rbp, 8(%%rsp)\n\t"
                "movq %%rsp, %%rbp\n\t"
                "movq $print_ret, (%%rbp)\n\t"
                "jmp foo\n"
        "print_ret:\n\t"
                "movq 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(20000, 0);
        return(ret);
}

乗算を和算に変えた。とりあえずnを20000にしてみた。試してみよう。

% 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(20000, 0);
        return(ret);
}

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

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

全然、余裕だ。それでは20000ではなく100000000(1億)で試してみよう。

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

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

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

まとめ

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

37
22
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
37
22