トップ «前の日記(2007-08-08) 最新 次の日記(2007-08-15)» 編集

U-memo

2006|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|08|
2009|08|10|
2010|02|03|
2011|11|12|
2012|04|
2016|02|
All= / Today= / Yesterday=

2007-08-10 [長年日記]

_ [雑記] 末尾転送の最適化

#include<stdio.h>
int a(int x);
int b(int x);

int main()
{
  printf("%d\n",a(100));
}
int a(int x){
  void *m=malloc(x);
  free(m);
  return x>0 ? b(x-1) : x;
}
int b(int x){
  void *m=malloc(x*2);
  free(m);
  return x>0 ? a(x-1) : x;
}

普通の末尾転送な相互再帰(…にしたのは単にインライン展開を邪魔したかっただけ)。これを x86-64 環境で gcc -O4 (version 3.4.6) すると、以下のコードを吐く。b() だけ掲示すると

b:
.LFB14:
        pushq   %rbx
.LCFI0:
        movl    %edi, %ebx
        leal    (%rbx,%rbx), %edi
        movslq  %edi,%rdi
        call    malloc
        movq    %rax, %rdi
        xorl    %eax, %eax
        call    free
        testl   %ebx, %ebx
        jle     .L2
        leal    -1(%rbx), %edi
        popq    %rbx               ;; スタックを元に戻す
        jmp     a                  ;; call ではなく jmp
        .p2align 4,,7
.L2:
        movl    %ebx, %eax
        popq    %rbx
        ret

一般的に末尾「再帰」でなくても末尾転送 (関数の最後が return func() になっている) なら、最適化を強くすれば call ではなく単純分岐になる。 スタックに保存されている呼び元(リンクアドレス)がそのまま次の関数func()に引き継いで使えるようにスタックの状態を正しておく(&引数を設定など する)必要があるだけ。

なお、x86 じゃなくて SPARC だと delay slot があるので、

b:
   save 〜     ;; スタックフレーム確保
   (中略)
   call a
   restore 〜  ;; スタックフレームを戻す

と、call は相変わらず残って消さないんですがね。 ( call - restore の実行順になることで、もとの呼び元リンクアドレスが期待どおりに保存されるのでこういう芸当が出来る)

本日のツッコミ(全6件) [ツッコミを入れる]
_ うんの (2007-08-10 16:12)

やっぱり Control transfer は制御「転移」だと思うんですよねー。<br>中国人くらいしか同意してくれなさそうなんですが。(ちゃちゃ)

_ ukai (2007-08-10 23:34)

そしてもんだいは末尾転送(転移)と呼んだやつの正式な呼び方がそもそも不明だと言う点だったりして。

_ うんの (2007-08-11 00:55)

leaf なんとかかんとかいう!呼び名(←ほとんど情報量なし)を、<br>昔聞いたような。あれ(どれなんだか)は関係ないのかな。

_ うんの (2007-08-11 00:57)

あー、ごめんなさい。きっと関係ないです。

_ ukai (2007-08-11 01:22)

leaf subroutine はスタック確保しない(SPARCならsave/restoreのない)routine のことだす。<br>正式な用語かどうか分からないけど、「末尾転送」と書いたとおり tail transfer というコトバがありますです。

_ うんの (2007-08-11 10:10)

↑おっしゃるとおり。leaf subroutine という言葉は思い出さなかったんですが、スタック確保しない(しなくてもよい)場合を指す用語だったというのは思い出して「ごめんなさい」しました。