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

Question

Comment savoir si gcc (plus précisément, g++) optimise la récursion de queue dans une fonction particulière ? (Parce que cette question a été soulevée à plusieurs reprises : Je ne veux pas tester si gcc peut optimiser la récursion de queue en général. Je veux savoir s'il optimise mon 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 peux ou non écrire un programme simple qui examine l'assembleur pour voir s'il y a optimisation.

PS. Je sais que cela fait partie de la question Quels compilateurs C++, le cas échéant, optimisent la récursion de la queue ? d'il y a 5 mois. Cependant, je ne pense pas cette partie de cette question a reçu une réponse satisfaisante. (La réponse était la suivante : "Le moyen le plus simple de vérifier si le compilateur a effectué l'optimisation (à ma connaissance) est d'effectuer un appel qui entraînerait un dépassement de pile - ou de regarder la sortie de l'assemblage").

Answer 1

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

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

Voyons maintenant le _atoi dans la résultante test.s (gcc 4.0.1 sur 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 des appels de queue sur cette fonction. Nous pouvons le dire car il n'y a pas de call dans ce code alors que le code C original avait clairement un appel de fonction. De plus, nous pouvons voir le jne L5 qui saute en arrière dans la fonction, indiquant une boucle alors qu'il n'y avait clairement aucune boucle dans le code C. Si vous recompilez avec l'optimisation désactivée, vous verrez une ligne qui dit call _atoi et vous ne verrez pas non plus de sauts en arrière.

La possibilité de l'automatiser est une autre question. Les spécificités du code assembleur dépendront du code que vous compilez.

Vous pourriez le découvrir de manière programmatique, je pense. Faites en sorte que la fonction imprime la valeur actuelle du pointeur de pile (registre ESP sur x86). Si la fonction affiche la même valeur pour le premier appel que pour l'appel récursif, alors le compilateur a effectué l'optimisation du tail-call. Cette idée nécessite cependant de modifier la fonction que vous espérez observer, ce qui pourrait affecter la façon dont le compilateur choisit d'optimiser la fonction. Si le test réussit (il 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 l'échec est dû à l'ajout du code d'instrumentation.

Answer 2

EDIT Mon post original a également empêché GCC de faire réellement des éliminations de tail call. J'ai ajouté quelques astuces supplémentaires ci-dessous pour tromper le GCC et l'amener à éliminer les appels de queue de toute façon.

En développant la réponse de Steven, vous pouvez vérifier de manière programmatique si vous avez le même cadre de pile :

#include <stdio.h>

// 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, passez 0 comme paramètre de vérification. Sinon, passez dans oracle. Si un appel récursif de queue qui aurait dû être éliminé ne l'a pas été, vous en serez informé au moment de l'exécution.

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

Answer 3

Regardez le code assembleur généré et voyez s'il utilise un fichier call ou jmp pour l'appel récursif sur x86 (pour les autres architectures, consultez 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);
}

Compiler en tant que

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

Ensuite, pour tester s'il utilise la récursion de 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)
# strip 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 <fact+offset>
if objdump --disassemble fact.o --start-address=$STARTADDR --stop-address=$STOPADDR | \
    grep -qE 'call +[0-9a-f]+ <fact\+'
then
    echo "fact is NOT tail recursive"
else
    echo "fact is tail recursive"
fi

Lorsqu'il est exécuté sur la fonction ci-dessus, ce script imprime "fact is tail recursive". Lorsqu'il est compilé à la place avec -O3 au lieu de -O2 ce qui donne curieusement "fact is NOT tail recursive".

Notez que cela peut donner des faux négatifs, comme l'a souligné ehemient dans son commentaire. Ce script ne donnera la bonne réponse que si la fonction ne contient pas du tout d'appels récursifs à elle-même, et il ne détecte pas non plus la récursion entre frères (par exemple lorsque A() appelle B() qui appelle A() ). Je ne peux pas penser à une méthode plus robuste pour le moment qui n'implique pas qu'un humain regarde l'assemblage généré, mais au moins vous pouvez utiliser ce script pour récupérer facilement l'assemblage correspondant à une fonction particulière dans un fichier objet.

Answer 4

Pour approfondir 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 <foo>:
   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 <foo+0x23>
   d:   85 c0                   test   %eax,%eax
   f:   74 12                   je     23 <foo+0x23>
  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          call   1a <foo+0x1a>
  1e:   83 c4 10                add    $0x10,%esp
  21:   eb 02                   jmp    25 <foo+0x25>
  23:   01 d0                   add    %edx,%eax
  25:   c9                      leave
  26:   c3                      ret

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

00000000 <foo>:
   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 <foo+0x15>
   d:   85 c0                   test   %eax,%eax
   f:   74 04                   je     15 <foo+0x15>
  11:   48                      dec    %eax
  12:   4a                      dec    %edx
  13:   eb f4                   jmp    9 <foo+0x9>
  15:   5d                      pop    %ebp
  16:   01 d0                   add    %edx,%eax
  18:   c3                      ret

Dans le premier cas, <foo+0x11>-<foo+0x1d> pousse les arguments pour un appel de fonction, alors que dans le second cas, <foo+0x11>-<foo+0x14> modifie les variables et jmp à la même fonction, quelque part après le préambule. C'est ce que vous devez chercher.

Je ne pense pas que l'on puisse faire cela de manière programmatique ; il y a trop de variations possibles. La "chair" de la fonction peut être plus proche ou plus éloignée du début, et vous ne pouvez pas le distinguer jmp d'une boucle ou d'une conditionnelle sans la regarder. Il pourrait s'agir d'un saut conditionnel au lieu d'une jmp . gcc pourrait laisser un call dans certains cas, mais appliquer l'optimisation des appels entre frères et sœurs dans d'autres cas.

Pour votre information, les "appels fratries" de gcc sont légèrement plus généraux que les appels récursifs de queue -- en fait, tout appel de fonction où la réutilisation du même cadre de pile est acceptable est potentiellement un appel fratrie.

[modifier]

A titre d'exemple, lorsque l'on cherche simplement une auto-récursive call vous induira 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 de l'appel de la fratrie à deux sur les trois bar appels. Je dirais encore qu'il est optimisé pour les appels de queue, puisque cet appel unique non optimisé ne va jamais plus loin qu'un seul niveau, même si vous trouverez un fichier call <bar+..> dans l'assemblage généré.

Answer 5

Je suis bien trop paresseux pour regarder un démontage. Essayez ceci :

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

compiler et exécuter ce programme. S'il tourne éternellement, la récursion de queue a été optimisée. S'il explose la pile, ce n'est pas le cas.

EDIT : désolé, j'ai lu trop vite, l'OP veut savoir si sa fonction particulière a sa récursion de queue optimisée. OK...

...le principe est toujours le même - si la récursion de queue est optimisée, alors le cadre de la pile restera le même. Vous devriez être en mesure d'utiliser la fonction fonction backtrace pour capturer les trames de pile à l'intérieur de votre fonction, et déterminer si elles croissent ou non. Si la récursion de queue est optimisée, vous aurez un seul pointeur de retour dans le tampon .