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  }

Вы можете видеть, что рекурсивный вызов превратился в переход назад к началу функции. Эта оптимизация выполняется GCC, только если код скомпилирован с включенной оптимизацией (в данном случае -O2) - возможно, то же самое верно для MS C ++?

Answer 2

Проект Llvm - это структура для создания компиляторов, которая имеет обширный набор механизмов оптимизации (среди них оптимизация хвостовых вызовов). Он предоставляет компиляторы c и c ++, хотя c ++ не считается завершенным.

Answer 3

Я предполагаю, что здесь можно сделать это вручную.

Первый шаблон заполнения использует рекурсию для заполнения буфера. Второй использует рекурсию хвоста, созданную вручную, чтобы сделать то же самое.

Это может быть плохо по какой-то причине, поэтому я предлагаю использовать его с осторожностью.

например.

#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] );
  }
}

Edit:

Хорошая идея добавить ассемблер. Я изменил некоторые ярлыки, чтобы сделать их более понятными.

Я просто использовал 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