Visual C++ で末尾再帰の最適化を確認する

Visual C++ で末尾再帰の最適化を確認します。

動作確認環境

Windows 10 Home 21H2, 64bit
Visual Studio Community 2019

普通の再帰プログラムを書く

1 から 100 までの数を合計するプログラムを、再帰を使って書きます。
ループで書くなり計算で求めたりしたほうが効率的ですが、実験のため再帰を使います。

#include <stdio.h>

long long f(int n)
{
    printf("n=%d\n", n); 

    if (n == 1) { 
        return 1; // ここで再帰の打ち切り
    }
    else {
        return n + f(n - 1); // ここで再帰
    }
}

int main()
{
    long long ans;

    ans = f(100);
    printf("ans=%I64d\n", ans);

    return 0;
}

コンパイルして、実行します。Zi は「デバッグ情報生成」の意味です。

C:\tmp>cl /Zi test.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.28.29913 for x86
...

C:\tmp>test
n=100
n=99
n=98
...
n=3
n=2
n=1
ans=5050

1 から 100 までの合計である 5050 が表示されました。問題ありません。

再帰呼び出しの回数を増やすとスタックオーバーフロー

プログラムを少し変更し、1 から 100 ではなく、1 から 100000 までの合計を計算するようにします。

【変更前】 ans = f(100);

【変更後】 ans = f(100000);

コンパイルして、実行します。

C:\tmp>cl /Zi test.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.28.29913 for x86
...

C:\tmp>test
n=100000
n=99999
n=99998
...
n=48589
n=48588
n=48554
→ ここでプログラムが異常終了

「n=1」に達することなく、途中で例外が発生しました。

WinDbg で例外の詳細を確認します。

0:000> !analyze -v
...
ExceptionCode: c00000fd (Stack overflow) 
...
→ Stack overflow とある

0:000> k
...
0f 00a04ac4 00f26efb test!f+0x3b [C:\tmp\test.c @ 11] 
10 00a04ad8 00f26efb test!f+0x3b [C:\tmp\test.c @ 11] 
11 00a04aec 00f26efb test!f+0x3b [C:\tmp\test.c @ 11] 
12 00a04b00 00f26efb test!f+0x3b [C:\tmp\test.c @ 11] 
13 00a04b14 00f26efb test!f+0x3b [C:\tmp\test.c @ 11] 
14 00a04b28 00f26efb test!f+0x3b [C:\tmp\test.c @ 11] 
15 00a04b3c 00f26efb test!f+0x3b [C:\tmp\test.c @ 11] 
16 00a04b50 00f26efb test!f+0x3b [C:\tmp\test.c @ 11] 
17 00a04b64 00f26efb test!f+0x3b [C:\tmp\test.c @ 11] 
18 00a04b78 00f26efb test!f+0x3b [C:\tmp\test.c @ 11] 
...
→ 同じ個所からの呼び出しが延々と続いている

0:000> !teb
TEB at 009c7000
    StackBase:            00b00000
    StackLimit:           00a01000

0:000> r esp
esp=00a03000

→ スタックの消費量は約 1MB。Visual C++ のスタックサイズの既定値と同じ。

再帰呼び出しにより約 1MB のスタックを消費しきって、スタックオーバーフローになっています。

再帰のプログラムを最適化する

同じプログラムを /O1 オプション付きでコンパイルし、実行します。/O1 は「最大限の最適化（スペースを優先）」の意味です。

C:\tmp>cl /O1 /Zi test.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.28.29913 for x86
...

C:\tmp>test
n=100000
n=99999
n=99998
...
n=35730
n=35729
n=35728
→ ここでプログラムが異常終了

最適化の効果はなく、スタックオーバーフローの例外が発生します。

末尾再帰に書き換える

例外の発生するプログラムを、末尾再帰に書き換えます。

#include <stdio.h>

long long f(int n, long long acc) // 引数 2 つに変更
{
    printf("n=%d\n", n); 

    if (n == 1) { 
        return acc; // ここで再帰の打ち切り
    }
    else {
        return f(n - 1, acc + n); // ここで末尾再帰
    }
}

int main()
{
    long long ans;

    ans = f(100000, 1);
    printf("ans=%I64d\n", ans);

    return 0;
}

コンパイルして、実行します。

C:\tmp>cl /Zi test.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.28.29913 for x86
...

C:\tmp>test
n=100000
n=99999
n=99998
...
n=48604
n=48603
n=48602
→ ここでプログラムが異常終了

相変わらずスタックオーバーフローの例外が発生します。末尾再帰に書き換えた効果が見られません。

末尾再帰のプログラムを最適化する

末尾再帰のプログラムも再帰に変わりはなく、字句通りに実行すると再帰呼び出しの繰り返しによりスタックがオーバーフローします。
そこで、/O1 オプションを付けて最適化します。

C:\tmp>cl /O1 /Zi test.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.28.29913 for x86
...

C:\tmp>test
n=100000
n=99999
n=99998
n=99997
...
n=3
n=2
n=1
ans=5000050000

今度はスタックオーバーフローが発生することなく、1 から 100000 までの合計である 5000050000 が表示されました。

生成されるコードの比較

末尾再帰のプログラムについて、最適化なしの場合とありの場合のコンパイル結果を比較します。

【最適化なし】
_f  PROC // 関数 f の定義
    ...
    call    _f // ここで再帰
    ...
_f  ENDP

【最適化あり】
_f  PROC // 関数 f の定義
    ...
$LN14@f:
    ...
    jmp     SHORT $LN14@f // 再帰が jmp に変換されている
    ...
_f  ENDP

最適化なしの場合は、再帰呼び出しがそのまま call 文に変換されていますが、最適化ありの場合は、jmp 文に変換されています。
ジャンプなのでスタックを消費することなく、何度でも呼び出せます。