Come posso verificare se gcc sta eseguendo l'ottimizzazione della ricorsione della coda?
https://stackoverflow.com/questions/490324
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Come faccio a sapere se gcc (più specificamente, g ++) sta ottimizzando la ricorsione della coda in una particolare funzione ? (Perché è venuto fuori alcune volte: non voglio testare se gcc può ottimizzare la ricorsione della coda in generale. Voglio sapere se ottimizza la funzione ricorsiva della coda mia .
Se la tua risposta è " guarda l'assemblatore generato " ;, Vorrei sapere esattamente cosa sto cercando e se potrei scrivere un semplice programma che esamina assemblatore per vedere se c'è ottimizzazione.
PS. So che questo appare come parte della domanda Che, se ce ne sono, I compilatori C ++ ottimizzano la ricorsione della coda? da 5 mesi fa. Tuttavia, non credo che questa parte di tale domanda abbia avuto una risposta soddisfacente. (La risposta è stata & Quot; Il modo più semplice per verificare se il compilatore ha fatto l'ottimizzazione (di cui sono a conoscenza) è eseguire una chiamata che altrimenti comporterebbe un overflow dello stack & # 8211; o guardare l'assembly uscita quot. &;)
Soluzione
Usiamo il codice di esempio dell'altra domanda . Compilalo, ma dì a gcc di non assemblare:
gcc -std=c99 -S -O2 test.c
Ora diamo un'occhiata alla funzione _atoi nel risultante file test.s (gcc 4.0.1 su 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
Il compilatore ha eseguito l'ottimizzazione del tail-call su questa funzione. Possiamo dire perché non ci sono call istruzioni in quel codice mentre il codice C originale aveva chiaramente una chiamata di funzione. Inoltre, possiamo vedere l'istruzione jne L5, che salta all'indietro nella funzione, indicando un ciclo quando chiaramente non c'era nessun ciclo nel codice C. Se ricompili con l'ottimizzazione disattivata, vedrai una riga che dice call _atoi e inoltre non vedrai alcun salto all'indietro.
Se è possibile automatizzare questa è un'altra questione. Le specifiche del codice assembler dipenderanno dal codice che stai compilando.
Potresti scoprirlo programmaticamente, penso. Fai stampare la funzione al valore corrente del puntatore dello stack (registra ESP su x86). Se la funzione stampa lo stesso valore per la prima chiamata come per la chiamata ricorsiva, il compilatore ha eseguito l'ottimizzazione della coda. Questa idea richiede di modificare la funzione che speri di osservare, tuttavia, e ciò potrebbe influire sul modo in cui il compilatore sceglie di ottimizzare la funzione. Se il test ha esito positivo (stampa lo stesso valore ESP entrambe le volte), quindi penso che sia ragionevole presumere che l'ottimizzazione verrebbe eseguita anche senza la tua strumentazione, ma se il test fallisce, non sapremo se l'errore è dovuto al aggiunta del codice di strumentazione.
Altri suggerimenti
MODIFICA Il mio post originale ha anche impedito a GCC di eliminare effettivamente le chiamate in coda. Ho aggiunto un po 'di complicità di seguito che inganna GCC nel fare comunque l'eliminazione delle chiamate di coda.
Espandendo la risposta di Steven, puoi verificare a livello di codice se hai lo stesso frame di stack:
#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;
}
Quando si chiama la funzione in modo non ricorsivo, passare in 0 il parametro check. Altrimenti passa in oracolo. Se non è stata eliminata una chiamata ricorsiva di coda che avrebbe dovuto essere eliminata, verrai informato in fase di esecuzione.
Quando lo provo, sembra che la mia versione di GCC non ottimizzi la prima chiamata di coda, ma le chiamate di coda rimanenti sono ottimizzate. Interessante.
Guarda il codice assembly generato e vedi se usa un'istruzione call o jmp per la chiamata ricorsiva su x86 (per altre architetture, cerca le istruzioni corrispondenti). È possibile utilizzare nm e objdump per ottenere solo l'assieme corrispondente alla propria funzione. Considera la seguente funzione:
int fact(int n)
{
return n <= 1 ? 1 : n * fact(n-1);
}
Compila come
gcc fact.c -c -o fact.o -O2
Quindi, per verificare se utilizza la ricorsione della coda:
# 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
Quando eseguito sulla funzione sopra, questo script stampa " infatti è coda ricorsiva " ;. Se invece compilato con -O3 anziché -O2, questo stampa curiosamente & Quot; il fatto NON è ricorsivo di coda & Quot ;.
Nota che ciò potrebbe produrre falsi negativi, come sottolineato da ehemient nel suo commento. Questo script produrrà la risposta giusta solo se la funzione non contiene alcuna chiamata ricorsiva a se stessa e non rileva nemmeno la ricorsione del fratello (ad es. Dove A() chiama B() che chiama <=>). Al momento non riesco a pensare a un metodo più robusto che non implichi una visione umana dell'assembly generato, ma almeno puoi usare questo script per afferrare facilmente l'assembly corrispondente a una particolare funzione all'interno di un file oggetto.
Espandendo la risposta di PolyThinker, ecco un esempio 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 output:
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 output:
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
Nel primo caso, <foo+0x11>-<foo+0x1d> invia argomenti per una chiamata di funzione, mentre nel secondo caso, <foo+0x11>-<foo+0x14> modifica le variabili e jmp s nella stessa funzione, da qualche parte dopo il preambolo. Questo è quello che vuoi cercare.
Non penso che tu possa farlo in modo programmatico; c'è troppa variazione possibile. Il & Quot; carne & Quot; della funzione potrebbe essere più vicina o più lontana dall'inizio e non puoi distinguerla gcc da un loop o da un condizionale senza guardarla. Potrebbe essere un salto condizionale anziché un call. bar potrebbe lasciare un call <bar+..> in alcuni casi, ma applicare l'ottimizzazione delle chiamate tra fratelli in altri casi.
Cordiali saluti, gcc's " fratello chiama " è leggermente più generale delle chiamate ricorsive della coda: in effetti, qualsiasi chiamata di funzione in cui il riutilizzo dello stesso frame dello stack è corretto è potenzialmente una chiamata di pari livello.
[modifica]
Come esempio di quando cerchi un auto-ricorsivo <=> ti indurrà in errore,
int bar(int n) {
if (n == 0)
return bar(bar(1));
if (n % 2)
return n;
return bar(n / 2);
}
GCC applicherà l'ottimizzazione delle chiamate tra fratelli a due delle tre <=> chiamate. Lo definirei comunque ottimizzato per la coda, poiché quella singola chiamata non ottimizzata non va mai oltre un singolo livello, anche se troverai un <=> nell'assieme generato.
Sono troppo pigro per guardare uno smontaggio. Prova questo:
void so(long l)
{
++l;
so(l);
}
int main(int argc, char ** argv)
{
so(0);
return 0;
}
compila ed esegui questo programma. Se dura per sempre, la ricorsione della coda è stata ottimizzata. se fa esplodere la pila, non lo era.
EDIT: scusa, leggi troppo in fretta, l'OP vuole sapere se la sua particolare funzione ha la ricorsione della coda ottimizzata. OK ...
... il principio è sempre lo stesso: se la ricorsione della coda viene ottimizzata, il frame dello stack rimarrà lo stesso. Dovresti essere in grado di utilizzare la funzione backtrace per acquisire la funzione impila i frame dall'interno della tua funzione e determina se stanno crescendo o meno. Se la ricorsione della coda viene ottimizzata, avrai un solo puntatore di ritorno nel buffer .
Un altro modo in cui ho verificato questo è:
- Compila il tuo codice con 'gcc -O2'
- avvia 'gdb'
- Posiziona un punto di interruzione nella funzione che ti aspetti di ottimizzare / eliminare la ricorsione della coda
- esegui il tuo codice
- Se è stata eliminata la chiamata in coda, il punto di interruzione verrà colpito una sola volta o mai. Per ulteriori informazioni, consulta questo
Un metodo semplice: crea un semplice programma di ricorsione della coda, compilarlo e smontarlo per vedere se è ottimizzato.
Ho appena capito che lo avevi già nella tua domanda. Se sai leggere l'assemblea, è abbastanza facile da dire. Le funzioni ricorsive si chiameranno (con & Quot; chiama l'etichetta & Quot;) dall'interno del corpo della funzione e un loop sarà solo & Quot; etichetta jmp & Quot ;.
Potresti creare dati di input che porterebbero a un overflow dello stack a causa della ricorsione troppo profonda delle chiamate di tale funzione se non ci fosse ottimizzazione e vedere se succede. Naturalmente, questo non è banale e talvolta input abbastanza grandi faranno funzionare la funzione per un periodo di tempo intollerabilmente lungo.
