末尾再帰呼び出しの最適化

末尾再帰呼び出しと最適化によるループの実験。

fact 階乗だと、スタックあふれが起こる前に、整数型の型あふれをおこしてしまうので、以下のような1づつ足し算のプログラムで実験してみた。

引数 1000000 だと、普通はスタックあふれで Segmentation fault となる。
でも、gcc -O3 でコンパイルすると、最適化で再帰呼び出しをしないので、動く。

((( add.c )))
#include <stdio.h>

int add( int x ) {
   if ( x == 0 )
      return 0 ;
   else
      return 1 + add( x - 1 ) ;
}
int main() {
   printf( "%d\n" , 10000000 ) ;
   return 0 ;
}
((( コンパイルと実行
$ gcc -O0 add.c            # 最適化なしでコンパイル
$ ./a.out
Segmentation fault ./a.out # 再帰が深くてスタックあふれで異常終了

$ gcc -O3 add.c            # -O3 で最適化を実行。
$ ./a.out                  # 末尾再帰呼び出しのループ化が行われる。
10000000                   # 同じプログラムだけど答えが求まる。

ちなみに、どんな命令になったかの確認で、アセンブリのソースを吐かせる。

((( gcc -O0 -S add.c / 最適化なし )))
add:
.LFB0:
        .cfi_startproc
        endbr64
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        subq    $16, %rsp
        movl    %edi, -4(%rbp)
        cmpl    $0, -4(%rbp)
        jne     .L2
        movl    $0, %eax
        jmp     .L3
.L2:
        movl    -4(%rbp), %eax
        subl    $1, %eax
        movl    %eax, %edi
        call    add        # 再帰になってる
        addl    $1, %eax
.L3:
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc

((( gcc -O3 -S add.c / 最適化あり )))
add:
.LFB23:
        .cfi_startproc
        endbr64
        movl    %edi, %eax # ループさえしていない...
        ret
        .cfi_endproc

この例だと、カウントダウンしながらループという処理さえ最適化されて、引数そのものが答え…になってる。これでは、ループ最適化となることさえわからない。

元も子もないので、fact で実験

((( fact.c )))
#include <stdio.h>

int fact( int x ) {
   if ( x == 0 )
      return 1 ;
   else
      return x * fact( x - 1 ) ;
}
int main() {
   printf( "%d\n" , fact( 50 ) ) ;
   return 0 ;
}
((( gcc -O0 fact.s fact.c / 最適化なし )))
fact:
.LFB0:
        .cfi_startproc
        endbr64
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        subq    $16, %rsp
        movl    %edi, -4(%rbp)
        cmpl    $0, -4(%rbp)
        jne     .L2
        movl    $1, %eax
        jmp     .L3
.L2:
        movl    -4(%rbp), %eax
        subl    $1, %eax
        movl    %eax, %edi
        call    fact    # 再帰になってる
        imull   -4(%rbp), %eax
.L3:
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc

((( gcc -O3 fact.s fact.c / 最適化あり )))
fact:
.LFB23:
        .cfi_startproc
        endbr64
        movl    $1, %eax
        testl   %edi, %edi
        je      .L1
        .p2align 3
        .p2align 4
        .p2align 3
.L2:
        imull   %edi, %eax
        subl    $1, %edi
        jne     .L2      # 単純な掛け算ループに最適化
.L1:
        ret
        .cfi_endproc