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

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

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

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

например.

#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++ не считается завершенным.