¿Cómo puedo verificar si gcc está realizando una optimización de recursión de cola?

¿Cómo puedo saber si gcc (más específicamente, g ++) está optimizando la recursión de cola en una función particular ? (Porque ha aparecido varias veces: no quiero probar si gcc puede optimizar la recursividad de cola en general. Quiero saber si optimiza mi función recursiva de cola).

Si tu respuesta es “mira el ensamblador generado”, me gustaría saber exactamente lo que estoy buscando, y si podría o no escribir un progtwig simple que examine el ensamblador para ver si hay optimización.

PD. Sé que esto aparece como parte de la pregunta ¿Qué comstackdores de C ++, si hay alguno, hacen la optimización de recursión de cola? desde hace 5 meses. Sin embargo, no creo que esta parte de esa pregunta haya sido respondida satisfactoriamente. (La respuesta fue: “La forma más fácil de verificar si el comstackdor realizó la optimización (que yo sepa) es realizar una llamada que de lo contrario daría lugar a un desbordamiento de la stack, o mirando a la salida del conjunto”).

Usemos el código de ejemplo de la otra pregunta . Comstackrlo, pero decirle a gcc que no ensamble:

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

Ahora veamos la función _atoi en el archivo test.s resultante (gcc 4.0.1 en 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 

El comstackdor ha realizado una optimización de la cola de llamada en esta función. Podemos decir que no hay instrucción de call en ese código, mientras que el código C original tenía claramente una llamada de función. Además, podemos ver la instrucción jne L5 , que salta hacia atrás en la función, indicando un bucle cuando claramente no había bucle en el código C. Si recomstack con la optimización desactivada, verá una línea que dice call _atoi , y tampoco verá ningún salto hacia atrás.

Si puede automatizar esto es otro asunto. Los detalles del código del ensamblador dependerán del código que está comstackndo.

Podrías descubrirlo programáticamente, creo. Haga que la función imprima el valor actual del puntero de la stack (registrar ESP en x86). Si la función imprime el mismo valor para la primera llamada que para la llamada recursiva, entonces el comstackdor ha realizado la optimización de la llamada final. Sin embargo, esta idea requiere modificar la función que espera observar y eso podría afectar la forma en que el comstackdor elige optimizar la función. Si la prueba tiene éxito (imprime el mismo valor de ESP en ambas ocasiones), entonces creo que es razonable suponer que la optimización también se realizará sin su instrumentación, pero si la prueba falla, no sabremos si la falla se debió a la Además del código de instrumentación.

EDITAR Mi publicación original también evitó que GCC realmente hiciera eliminaciones de llamadas de cola. He añadido algunos trucos adicionales a continuación que engañan a GCC para que haga la eliminación de llamadas de todos modos.

Ampliando la respuesta de Steven, puede verificar programáticamente si tiene el mismo marco 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; } 

Cuando llame a la función de forma no recursiva, pase 0 al parámetro de verificación. De lo contrario, pasar en oracle. Si una llamada recursiva de cola que debería haberse eliminado no lo era, entonces se le informará en tiempo de ejecución.

Al probar esto, parece que mi versión de GCC no optimiza la primera llamada de cola, pero las llamadas de cola restantes están optimizadas. Interesante.

Mire el código ensamblado generado y vea si usa una instrucción call o jmp para la llamada recursiva en x86 (para otras architectures, busque las instrucciones correspondientes). Puede usar nm y objdump para obtener solo el conjunto correspondiente a su función. Considere la siguiente función:

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

Comstackr como

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

Luego, para probar si está utilizando recursividad de cola:

 # 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  if objdump --disassemble fact.o --start-address=$STARTADDR --stop-address=$STOPADDR | \ grep -qE 'call +[0-9a-f]+  

Cuando se ejecutó en la función anterior, este script imprime "hecho es cola recursiva". Cuando en lugar comstackdo con -O3 vez de -O2 , este curiosamente imprime "hecho NO es cola recursiva".

Tenga en cuenta que esto podría arrojar falsos negativos, como señaló ehemient en su comentario. Este script solo arrojará la respuesta correcta si la función no contiene llamadas recursivas, y tampoco detecta la recursión entre hermanos (por ejemplo, cuando A() llama a B() que llama a A() ). No puedo pensar en un método más sólido en este momento que no implique tener un aspecto humano del ensamblaje generado, pero al menos puede usar este script para tomar fácilmente el ensamblado correspondiente a una función particular dentro de un archivo de objeto.

Ampliando la respuesta de Poly Thinking, aquí hay un ejemplo concreto.

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

  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 call 1a 
   1e: 83 c4 10 agregue $ 0x10,% esp
   21: eb 02 jmp 25 
   23: 01 d0 agregar% edx,% eax
   25: c9 deja
   26: ret c3

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

  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 agrega% edx,% eax
   18: ret c3

En el primer caso, - empuja los argumentos para una llamada de función, mientras que en el segundo caso, - modifica las variables y jmp s para la misma función , en algún lugar después del preámbulo. Eso es lo que quieres buscar.

No creo que puedas hacer esto programáticamente; hay demasiada variación posible. La “carne” de la función puede estar más cerca o más alejada del inicio, y no se puede distinguir ese jmp de un bucle o condicional sin mirarlo. Puede ser un salto condicional en lugar de un jmp . gcc puede dejar una call en algunos casos pero aplicar la optimización de llamadas de hermanos a otros casos.

Para su información, las “llamadas entre hermanos” de gcc son ligeramente más generales que las llamadas recursivas de cola; de hecho, cualquier llamada a función en la que reutilizar el mismo marco de stack sea correcto es potencialmente una llamada entre hermanos.

[editar]

Como un ejemplo de cuando solo estás buscando una call auto-recursiva te confundirá,

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

GCC aplicará la optimización de llamadas entre hermanos en dos de las tres llamadas a la bar . Aún así lo llamo tail-call-optimized, ya que esa única llamada no optimizada nunca va más allá de un solo nivel, aunque encontrará una call en el ensamblado generado.

soy demasiado perezoso para mirar un desassembly. Prueba esto:

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

comstackr y ejecutar este progtwig. Si funciona para siempre, la recursión de cola se optimizó. si sopla la stack, no lo fue.

EDITAR: lo siento, lea demasiado rápido, el OP quiere saber si su función particular tiene su recursión de cola optimizada. DE ACUERDO…

… el principio sigue siendo el mismo: si la recursión de cola se está optimizando, el marco de stack seguirá siendo el mismo. Debería poder usar la función backtrace para capturar los fotogtwigs de stack desde su función y determinar si están creciendo o no. Si la recursividad de cola se está optimizando, solo tendrá un puntero de retorno en el búfer .

Otra forma en que revisé esto es:

  1. Comstack tu código con ‘gcc -O2’
  2. comenzar ‘gdb’
  3. Coloque un punto de interrupción en la función que espera que sea recursiva optimizada / eliminada
  4. ejecuta tu código
  5. Si se ha eliminado la llamada de cola, entonces el punto de ruptura se golpeará solo una vez o nunca. Para más información sobre esto, mira esto

Un método simple: cree un progtwig simple de recursión de cola, compílelo y disimúltelo para ver si está optimizado.

Solo me di cuenta de que ya tenías eso en tu pregunta. Si sabes leer el ensamblaje, es bastante fácil de decir. Las funciones recursivas se llamarán a sí mismas (con “etiqueta de llamada”) desde dentro del cuerpo de la función, y un bucle será simplemente “etiqueta jmp”.

Podrías crear datos de entrada que podrían llevar al desbordamiento de la stack debido a una recursión demasiado profunda de las llamadas a esa función si no hubiera optimización y ver si sucede. Por supuesto, esto no es trivial y, a veces, entradas suficientemente grandes harán que la función se ejecute durante un período de tiempo intolerablemente largo.