ventajas - Reducir el uso de la pila durante la recursión con GCC+ARM

recursividad java

Question

Tengo un analizador de descenso recursivo para un procesador ARM integrado (en C + GCC, para ARM Cortex M3).

Mientras lo ejecuto me he dado cuenta de que usa una gran cantidad de espacio de pila (incluso más de lo que cabría esperar) y bajo una inspección más cercana, he descubierto que esto está sucediendo:

extern int bar(int *p);
int foo() {
int z = foo(); // it''s an example!
int n[100]; // stack usage
return z+bar(n); // calling bar(n) stops n from being optimised out
}

Resultado de ejecutar arm-none-eabi-gcc -fomit-frame-pointer -S test.c

foo:
str lr, [sp, #-4]! ; Push link register
sub sp, sp, #412 ; Reserve space on stack, even if we don''t need it now!
bl foo ; Recurse
str r0, [sp, #404] ; Store result
...

Entonces, al comienzo de la función, empuja todo el marco de pila en la pila. Sin embargo, después de algunas iteraciones, tiene muchas cosas en la pila que aún no ha utilizado.

Idealmente, lo que me gustaría es que GCC genere:

foo:
str lr, [sp, #-4]! ; Push link register
; Don''t reserve space, because we don''t need it
bl foo ; Recurse
sub sp, sp, #412 ; Reserve space now
str r0, [sp, #404] ; Store result
...

(Esto probablemente no es correcto, pero espero que entiendas la idea)

Algo similar a esto se puede lograr con el siguiente código, pero es realmente desagradable (y si GCC pone a fooworker, ¡se rompe de nuevo!). ¿Debe haber una mejor manera?

int fooworker(int z) {
int n[100]; // stack usage
return z+bar(n); // calling bar(n) stops n from being optimised out
}
int foo() {
return fooworker(foo());
}

Entonces, ¿hay alguna forma de decirle a GCC que solo amplíe la pila al comienzo del bloque básico, o hay una declaración de ''barrera'' que ocasiona que se agreguen operaciones push / pop adicionales en ese punto? Supongo que GCC está utilizando uno de los tipos de llamadas estándar de ARM, pero ¿hay alguna manera de etiquetar estas funciones con otro tipo de llamada que sea un poco más eficiente con la pila, o hay alguna manera de reescribir las funciones de modo que la pila sea usado un poco más sensiblemente?

Por favor, no me diga que no use la recursión, no está respondiendo la pregunta.

Answer 1

int *n = alloca(sizeof(*n) * 100);

Es feo y yo personalmente dividí la función en dos partes, pero parece funcionar en mi gcc en amd64 en todos los niveles de optimización.

Answer 2

Todo esto es susceptible a la optimización, pero también podría tratar de introducir un nuevo alcance:

extern int bar(int *p);
int foo() {
int z = foo();
{
int n[100];
return z+bar(n);
}
}

La introducción del nuevo ámbito significa que n no debería vivir antes de que se llame a foo() . Una vez más, la optimización podría romper todo esto, como su propia solución o la aceptada.