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

我在这里猜测，但可能可以手动完成。

第一个填充模板使用递归来填充缓冲区。第二个使用手工制作的尾递归来做同样的事情。

由于某种原因，这可能很糟糕，所以我建议谨慎使用。

例如。

#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++ 不被认为是完整的。