c++ - Visual C++ テール コールの最適化

Question

その質問への回答によると 、末尾再帰の最適化を行う C++ コンパイラはありますか? コンパイラは末尾再帰の最適化を行う必要があるようです。

しかし、提案されたオプションを試してみましたが、テンプレート関数の場合、コンパイラはこの最適化を実行できないようです。どうにかして修正できますか？

Answer 1

私は MS コンパイラを使用しませんが、GCC は確かにテンプレートの末尾再帰の最適化を行うことができます。この関数を考えると：

template <typename T>
T f( T t ) {
   cout << t << endl;
   if ( t == 0 ) {
      return t;
   }
   return f( t - 1 );
}

生成されるコードは次のとおりです。

    5   T f( T t ) {
    6       cout << t << endl;
-   0x401362    <main+22>:      mov    %esi,0x4(%esp)
-   0x401366    <main+26>:      movl   $0x4740c0,(%esp)
-   0x40136d    <main+33>:      call   0x448620 <_ZNSolsEi>
-   0x401372    <main+38>:      mov    %eax,%ebx
    7      if ( t == 0 ) {
-   0x4013a5    <main+89>:      test   %esi,%esi
-   0x4013a7    <main+91>:      je     0x4013c8 <main+124>
    8         return t;
    9      }
    10     return f( t - 1 );
-   0x4013a9    <main+93>:      dec    %esi
-   0x4013aa    <main+94>:      jmp    0x401362 <main+22>
    11  }

再帰呼び出しが関数の先頭に戻るジャンプになっていることがわかります。この最適化は、コードが最適化を有効にしてコンパイルされている場合 (この場合は -O2)、GCC によってのみ実行されます。おそらく、MS C++ についても同じことが当てはまりますか?

Answer 2

ここでは推測していますが、手動で行うことは可能かもしれません。

最初のフィル テンプレートは、再帰を使用してバッファーをフィルします。2 つ目は、手作りの末尾再帰を使用して同じことを行います。

これは何らかの理由で悪い可能性があるため、注意して使用することをお勧めします。

例えば。

#include <stdio.h>

template <class myType>

// fill a buffer with n v's

void fill( myType *p , int n , myType v ){
    if ( n <= 0 ) return;
    *p = v;
    fprintf( stderr , "[%x] = %d\n" , (unsigned) p , *p );
    fill( p+1 , n-1 , v );
}

template <class myType>

// fill a buffer with n v's

void fillTail( myType *p , int n , myType v ){
    tail:
    if ( n <= 0 ) return;
    *p = v;
    fprintf( stderr , "[%x] = %d\n" , (unsigned) p , *p );
    // hand crafted tail call
    p++;
    n--;
    goto tail;
}

int main(){
  int   buf[100];
  int   v = 12;
  fill( buf , 10 , v );
  for ( int i=0; i<10 ; i++ ){
    fprintf( stderr , "[%d] = %d\n" , i , buf[i] );
  }
  v = 13;
  fill( buf , 10 , v );
  for ( int i=0; i<10 ; i++ ){
    fprintf( stderr , "[%d] = %d\n" , i , buf[i] );
  }
}

編集：

アセンブラを追加することをお勧めします。わかりやすくするために、いくつかのラベルを変更しました。

私は単にg++ file.cppコンパイルしg++ -S file.cppてアセンブラを取得するだけでした。

fill:
        pushl   %ebp
LCFI0:
        movl    %esp, %ebp
LCFI1:
        subl    $24, %esp
LCFI2:
        cmpl    $0, 12(%ebp)
        jle     L4
        movl    8(%ebp), %edx
        movl    16(%ebp), %eax
        movl    %eax, (%edx)
        movl    12(%ebp), %edx
        decl    %edx
        movl    8(%ebp), %ecx
        addl    $4, %ecx
        movl    16(%ebp), %eax
        movl    %eax, 8(%esp)
        movl    %edx, 4(%esp)
        movl    %ecx, (%esp)
        call    fill
L4:
        leave
        ret

fillTail:
        pushl   %ebp
LCFI3:
        movl    %esp, %ebp
LCFI4:
        subl    $8, %esp
LCFI5:
        jmp     L6
L10:
        movl    8(%ebp), %edx
        movl    16(%ebp), %eax
        movl    %eax, (%edx)
        addl    $4, 8(%ebp)
        leal    12(%ebp), %eax
        decl    (%eax)
L6:
        cmpl    $0, 12(%ebp)
        jg      L10
L9:
        leave
        ret

Answer 3

Llvm プロジェクトは、広範な最適化メカニズム (テール コールの最適化) を備えたコンパイラを作成するためのフレームワークです。c++ は完全とは見なされませんが、c および c++ コンパイラを提供します。