gcc - recursive - recursividad valor

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

Question

¿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 programa simple que examine el ensamblador para ver si hay optimización.

PD. Sé que esto aparece como parte de la pregunta ¿Qué compiladores 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 compilador realizó la optimización (que yo sepa) es realizar una llamada que de lo contrario daría lugar a un desbordamiento de la pila, o mirando a la salida del conjunto").

Answer 1

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

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

En el primer caso, <foo+0x11>-<foo+0x1d> empuja los argumentos para una llamada de función, mientras que en el segundo caso, <foo+0x11>-<foo+0x14> 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 pila 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 <bar+..> en el ensamblado generado.

Answer 2

Mire el código ensamblado generado y vea si usa una instrucción call o jmp para la llamada recursiva en x86 (para otras arquitecturas, 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);
}

Compilar 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 <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

Cuando se ejecutó en la función anterior, este script imprime "hecho es cola recursiva". Cuando en lugar compilado 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.

Answer 3

Otra forma en que revisé esto es:

1. Compila 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 this

Answer 4

Podrías crear datos de entrada que podrían llevar al desbordamiento de la pila 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.

Answer 5

Un método simple: cree un programa 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".

Answer 6

Usemos el código de ejemplo de la otra pregunta . Compilarlo, 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 compilador 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 recompila 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á compilando.

Podrías descubrirlo programáticamente, creo. Haga que la función imprima el valor actual del puntero de la pila (registrar ESP en x86). Si la función imprime el mismo valor para la primera llamada que para la llamada recursiva, entonces el compilador 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 compilador 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.

Answer 7

soy demasiado perezoso para mirar un desmontaje. Prueba esto:

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

compilar y ejecutar este programa. Si funciona para siempre, la recursión de cola se optimizó. si sopla la pila, 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 pila seguirá siendo el mismo. Debería poder usar la función backtrace para capturar los fotogramas de pila 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 .

Answer 8

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

#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;
}

Cuando llame a la función de forma no recursiva, pase 0 al parámetro de verificación. De lo contrario, pasar en oráculo. 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.