Optimisation de l'appel de queue Visual C++

Question

Selon les réponses à cette question: Which, if any, C++ compilers do tail-recursion optimization? Il semble que le compilateur devrait effectuer l'optimisation de la récurrence de la queue.

Mais j'ai essayé des options proposées et il semble que le compilateur ne peut pas faire cette optimisation en cas de fonctions de modèle. Pourrait-il être réparé en quelque sorte?

Answer 1

Je n'utilise pas les compilateurs MS, mais GCC peut certainement faire l'optimisation de la récurrence de la queue pour les modèles. Compte tenu de cette fonction:

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

Le code produit est:

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 } 

Vous pouvez voir que l'appel récursif a été transformé en un saut en arrière au début de la fonction. Cette optimisation est seulement effectuée par GCC si le code est compilé avec des optimisations activées (-O2 dans ce cas) - peut-être la même chose est vraie pour MS C++?

Answer 2

Je devine ici, mais il pourrait être possible de les faire manuellement.

Le premier modèle de remplissage utilise la récursivité pour remplir un tampon. La seconde utilise une récursivité de queue artisanale pour faire la même chose.

Cela peut être mauvais pour une raison quelconque, donc je suggère qu'il est à utiliser avec prudence.

par ex.

#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:

Bonne idée d'ajouter l'assembleur. J'ai changé certaines étiquettes pour le rendre plus clair. J'ai simplement utilisé g++ file.cpp pour compiler et g++ -S file.cpp pour obtenir l'assembleur.

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

Le Llvm project est un cadre pour créer des compilateurs qui a un vaste ensemble de mécanisme d'optimisation (optimisation sur mesure des appels entre eux). Il fournit des compilateurs c et C++, bien que C++ ne soit pas considéré comme complet.