Comment puis-je vérifier si gcc effectue une optimisation de la récursion de la queue?

Comment savoir si gcc (plus spécifiquement, g ++) optimise la récursion de la queue dans une fonction particulière ? (Parce que c’est arrivé plusieurs fois: je ne veux pas tester si gcc peut optimiser la récursion de la queue en général. Je veux savoir si cela optimise ma fonction récursive de la queue.)

Si votre réponse est “regardez l’assembleur généré”, j’aimerais savoir exactement ce que je cherche et si je pourrais écrire un programme simple qui examine l’assembleur pour voir s’il y a optimisation.

PS Je sais que cela apparaît dans le cadre de la question: Quels compilateurs C ++, le cas échéant, utilisent-ils pour optimiser la récursion de la queue? il y a 5 mois. Cependant, je ne pense pas que cette partie de la question ait reçu une réponse satisfaisante. (La réponse était “Le moyen le plus simple de vérifier si le compilateur a fait l’optimisation (à ma connaissance) est d’effectuer un appel qui entraînerait un débordement de stack – ou d’examiner la sortie de l’assemblage.”)

Utilisons l’exemple de code de l’autre question . Comstackz-le, mais dites à gcc de ne pas assembler:

 gcc -std = c99 -S -O2 test.c

Regardons _atoi fonction _atoi dans le fichier test.s résultant (gcc 4.0.1 sous Mac OS 10.5):

  .text .align 4,0x90 _atoi: pushl %ebp testl %eax, %eax movl %esp, %ebp movl %eax, %ecx je L3 .align 4,0x90 L5: movzbl (%ecx), %eax testb %al, %al je L3 leal (%edx,%edx,4), %edx movsbl %al,%eax incl %ecx leal -48(%eax,%edx,2), %edx jne L5 .align 4,0x90 L3: leave movl %edx, %eax ret 

Le compilateur a effectué une optimisation de l’appel de queue sur cette fonction. On peut dire qu’il n’y a pas call instruction d’ call dans ce code alors que le code C d’origine avait clairement un appel de fonction. De plus, on peut voir l’instruction jne L5 , qui saute en arrière dans la fonction, indiquant une boucle quand il n’y avait clairement aucune boucle dans le code C. Si vous recomstackz avec l’optimisation désactivée, vous verrez une ligne qui call _atoi , et vous ne verrez pas non plus de sauts en arrière.

Si vous pouvez automatiser cela est une autre affaire. Les spécificités du code assembleur dépendent du code que vous comstackz.

Je pense que vous pourriez le découvrir par programmation. Faites en sorte que la fonction imprime la valeur actuelle du pointeur de stack (registre ESP sur x86). Si la fonction imprime la même valeur pour le premier appel que pour l’appel récursif, le compilateur a effectué l’optimisation de l’appel de queue. Cette idée nécessite toutefois de modifier la fonction que vous souhaitez observer, ce qui peut affecter la manière dont le compilateur choisit d’optimiser la fonction. Si le test réussit (imprime la même valeur ESP les deux fois), je pense qu’il est raisonnable de supposer que l’optimisation serait également effectuée sans votre instrumentation, mais si le test échoue, nous ne saurons pas si la défaillance est due à ajout du code d’instrumentation.

EDIT Mon article original a également empêché GCC de procéder à des éliminations d’appel. J’ai ajouté quelques astuces supplémentaires ci-dessous qui empêchent GCC de faire de toute façon l’élimination des appels de queue.

En développant la réponse de Steven, vous pouvez vérifier par programme si vous avez le même frame de stack:

 #include  // We need to get a reference to the stack without spooking GCC into turning // off tail-call elimination int oracle2(void) { char oracle; int oracle2 = (int)&oracle; return oracle2; } void myCoolFunction(params, ..., int tailRecursionCheck) { int oracle = oracle2(); if( tailRecursionCheck && tailRecursionCheck != oracle ) { printf("GCC did not optimize this call.\n"); } // ... more code ... // The return is significant... GCC won't eliminate the call otherwise return myCoolFunction( ..., oracle); } int main(int argc, char *argv[]) { myCoolFunction(..., 0); return 0; } 

Lorsque vous appelez la fonction de manière non récursive, entrez 0 le paramètre check. Sinon passez en oracle. Si un appel récursif de queue qui aurait dû être éliminé ne l’était pas, vous en serez informé lors de l’exécution.

En testant cela, il semble que ma version de GCC n’optimise pas le premier appel de queue, mais les appels de queue restants sont optimisés. Intéressant.

Examinez le code assembleur généré et vérifiez s’il utilise une instruction call ou jmp pour l’appel récursif sur x86 (pour les autres architectures, recherchez les instructions correspondantes). Vous pouvez utiliser nm et objdump pour obtenir uniquement l’assemblage correspondant à votre fonction. Considérons la fonction suivante:

 int fact(int n) { return n <= 1 ? 1 : n * fact(n-1); } 

Comstackr comme

 gcc fact.c -c -o fact.o -O2 

Ensuite, pour tester si elle utilise la récursion de la queue:

 # get starting address and size of function fact from nm ADDR=$(nm --print-size --radix=d fact.o | grep ' fact$' | cut -d ' ' -f 1,2) # ssortingp leading 0's to avoid being interpreted by objdump as octal addresses STARTADDR=$(echo $ADDR | cut -d ' ' -f 1 | sed 's/^0*\(.\)/\1/') SIZE=$(echo $ADDR | cut -d ' ' -f 2 | sed 's/^0*//') STOPADDR=$(( $STARTADDR + $SIZE )) # now disassemble the function and look for an instruction of the form # call addr  if objdump --disassemble fact.o --start-address=$STARTADDR --stop-address=$STOPADDR | \ grep -qE 'call +[0-9a-f]+  

Lorsqu'il est exécuté sur la fonction ci-dessus, ce script imprime "fact est tail récursif". À la place compilé avec -O3 au lieu de -O2 , cette curieusement imprime "fact est NOT queue recursive".

Notez que cela pourrait donner des faux négatifs, comme ehemient souligné dans son commentaire. Ce script ne donnera la bonne réponse que si la fonction ne contient aucun appel récursif, et ne détecte pas non plus la récursivité fraternelle (par exemple, où A() appelle B() qui appelle A() ). Je ne peux pas penser à une méthode plus robuste pour le moment qui ne nécessite pas d'avoir un regard humain sur l'assemblage généré, mais au moins vous pouvez utiliser ce script pour saisir facilement l'assembly correspondant à une fonction particulière dans un fichier object.

En développant la réponse de PolyThinker, voici un exemple concret.

 int foo(int a, int b) { if (a && b) return foo(a - 1, b - 1); return a + b; } 

i686-pc-linux-gnu-gcc-4.3.2 -Os -fno-optimize-sibling-calls sortie:

  00000000 :
    0: 55 push% ebp
    1: 89 e5 mov% esp,% ebp
    3: 8b 55 08 mov 0x8 (% ebp),% edx
    6: 8b 45 0c mov 0xc (% ebp),% eax
    9: 85 d2 test% edx,% edx
    b: 74 16 je 23 
    d: 85 c0 test% eax,% eax
    f: 74 12 je 23 
   11: 51 push% ecx
   12: 48 dec% eax
   13: 51 push% ecx
   14: 50 push% eax
   15: 8d 42 ff lea -0x1 (% edx),% eax
   18: 50 push% eax
   19: e8 fc ff ff ff appel 1a 
   1e: 83 c4 10 append $ 0x10,% esp
   21: eb 02 jmp 25 
   23: 01 d0 ajoute% edx,% eax
   25: c9 partir
   26: c3 ret

i686-pc-linux-gnu-gcc-4.3.2 -Os sortie:

  00000000 :
    0: 55 push% ebp
    1: 89 e5 mov% esp,% ebp
    3: 8b 55 08 mov 0x8 (% ebp),% edx
    6: 8b 45 0c mov 0xc (% ebp),% eax
    9: 85 d2 test% edx,% edx
    b: 74 08 je 15 
    d: 85 c0 test% eax,% eax
    f: 74 04 je 15 
   11: 48 dec% eax
   12: 4a dec% edx
   13: eb f4 jmp 9 
   15: 5d pop% ebp
   16: 01 d0 ajoute% edx,% eax
   18: c3 ret

Dans le premier cas, - pousse les arguments pour un appel de fonction, tandis que dans le second cas, - modifie les variables et jmp s sur la même fonction , quelque part après le préambule. C’est ce que vous voulez rechercher.

Je ne pense pas que vous puissiez le faire par programmation; il y a trop de variation possible. La “viande” de la fonction peut être plus proche ou plus éloignée du début, et vous ne pouvez pas distinguer ce jmp d’une boucle ou d’un conditionnel sans le regarder. Ce pourrait être un saut conditionnel au lieu d’un jmp . gcc peut laisser un call dans certains cas mais appliquer l’optimisation des appels frères à d’autres cas.

FYI, les “appels frères” de gcc sont légèrement plus généraux que les appels récursifs – en réalité, tout appel de fonction où la réutilisation du même bloc de stack est correct est potentiellement un appel frère.

[modifier]

À titre d’exemple, il suffit de chercher un call auto-récursif pour vous induire en erreur,

 int bar(int n) { if (n == 0) return bar(bar(1)); if (n % 2) return n; return bar(n / 2); } 

GCC appliquera l’optimisation des appels fraternels à deux appels sur trois. Je l’appellerais toujours optimisé pour les appels de queue, car cet appel non optimisé ne dépasse jamais un seul niveau, même si vous trouvez un call dans l’assemblage généré.

Je suis trop paresseux pour regarder un déassembly. Essaye ça:

 void so(long l) { ++l; so(l); } int main(int argc, char ** argv) { so(0); return 0; } 

comstackr et exécuter ce programme. Si elle fonctionne pour toujours, la récursion de la queue a été optimisée. si ça fait sauter la stack, ça ne l’était pas.

EDIT: désolé, lu trop vite, le PO veut savoir si sa fonction particulière a sa récursivité optimisée. D’ACCORD…

… le principe est toujours le même – si la récursivité est optimisée, le cadre de la stack restra le même. Vous devriez être capable d’utiliser la fonction backtrace pour capturer les frameworks de stack dans votre fonction et déterminer s’ils sont en croissance ou non. Si la récursion de la queue est optimisée, vous ne disposerez que d’un seul pointeur de retour dans le tampon .

Une autre façon de vérifier ceci est:

  1. Comstackz votre code avec ‘gcc -O2’
  2. commencer ‘gdb’
  3. Placer un point d’arrêt dans la fonction que vous prévoyez d’être récursif optimisé / éliminé
  4. lance ton code
  5. Si l’appel de queue a été éliminé, le point d’arrêt ne sera atteint qu’une fois ou jamais. Pour plus d’informations, voir ceci

Une méthode simple: Construisez un programme simple de récursion de queue, comstackz-le et démontez-le pour voir s’il est optimisé.

Je viens de réaliser que vous aviez déjà cela dans votre question. Si vous savez lire l’assemblage, c’est assez facile à dire. Les fonctions récursives s’appelleront elles-mêmes (avec “libellé d’appel”) depuis le corps de la fonction, et une boucle sera simplement “étiquette jmp”.

Vous pourriez créer des données d’entrée qui entraîneraient un débordement de stack en raison d’une récursivité trop profonde des appels de cette fonction s’il n’y avait pas d’optimisation et voir si cela se produisait. Bien sûr, ce n’est pas anodin et des apports suffisamment importants pour que la fonction fonctionne pendant une période de temps intolérable.