Come può un compilatore applicare l'eliminazione delle funzioni alle funzioni impure?

Question

Spesso durante la scrittura del codice, mi ritrovo a utilizzare più volte un valore di una particolare chiamata di funzione. Mi sono reso conto che un'ovvia ottimizzazione sarebbe stata quella di catturare questi valori usati ripetutamente nelle variabili. Questa (pseudo codice):

function add1(foo){ foo + 1; } 
... 
do_something(foo(1)); 
do_something_else(foo(1)); 

diventa:

function add1(foo){ foo + 1; } 
... 
bar = foo(1); 
do_something(bar); 
do_something_else(bar); 

Tuttavia, questa operazione rende esplicito il codice meno leggibile nella mia esperienza. Supponevo che i compilatori non potessero fare questo tipo di ottimizzazione se il nostro linguaggio di scelta consente alle funzioni di avere effetti collaterali.

Recentemente ho esaminato questo e, se ho capito bene, questa ottimizzazione è/può essere fatta per le lingue in cui le funzioni devono essere pure. Questo non mi sorprende, ma presumibilmente questo può essere fatto anche per le funzioni impure. Con un paio di veloci ricerche su Google ho trovato questi frammenti: GCC 4.7 Fortran improvement

Quando si esegue front-end-ottimizzazione, l'opzione -faggressive-funzione di eliminazione consente la rimozione della funzione duplicato richiede anche per le funzioni impuri.

Compiler Optimization (Wikipedia)

Per esempio, in alcune funzioni lingue non sono autorizzati ad avere effetti collaterali. Pertanto, se un programma effettua più chiamate alla stessa funzione con gli stessi argomenti, il compilatore può immediatamente dedurre che il risultato della funzione deve essere calcolato una sola volta. Nelle lingue in cui le funzioni possono avere effetti collaterali, è possibile un'altra strategia. L'ottimizzatore può determinare quale funzione non ha effetti collaterali e limitare tali ottimizzazioni alle funzioni senza effetti collaterali. Questa ottimizzazione è possibile solo quando l'ottimizzatore ha accesso alla funzione chiamata.

Dalla mia comprensione, ciò significa che un ottimizzatore può determinare quando una funzione è o non è pura ed eseguire questa ottimizzazione quando la funzione è. Dico questo perché se una funzione produce sempre la stessa uscita quando ha lo stesso input ed è priva di effetti collaterali, soddisferebbe entrambe le condizioni per essere considerata pura.

Questi due frammenti sollevano due domande per me.

1. Come può un compilatore essere in grado di eseguire in modo sicuro questa ottimizzazione se una funzione non è pura? (come in -faggressive-funzione-eliminazione)
2. Come può un compilatore determinare se una funzione è pura o no? (Come nella strategia suggerita in questo articolo Wikipedia)

e infine:

• può questo tipo di ottimizzazione essere applicato a qualsiasi lingua, o solo quando si verificano determinate condizioni?
• Questa ottimizzazione è utile anche per funzioni estremamente semplici?
• Quanto sovraccarico si accumula e recupera un valore dallo stack?

Mi scuso se queste sono domande stupide o illogici. Sono solo alcune cose che sono stato curioso di recente. :)

Answer 1

Disclaimer: Non sono un compilatore/ottimizzatore, ho solo la tendenza a dare un'occhiata al codice generato e mi piace leggere su quella roba - quindi non è autorativo. Una rapida ricerca non si è rivelata molto efficace in termini di eliminazione della funzione aggressiva, quindi potrebbe fare un po 'di magia extra non spiegata qui.

---

Un ottimizzatore può

• tentativo all'inline la chiamata di funzione (generazione del codice fase di collegamento, questo funziona anche attraverso unità di compilazione)
• eseguire l'eliminazione delle sottoespressioni comuni, e, eventualmente, effetto collaterale riordino.

Modifica il tuo esempio un po ', e farlo in C++:

extern volatile int RW_A = 0; // see note below 

int foo(int a) { return a * a; } 
void bar(int x) { RW_A = x; } 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    bar(foo(2)); 
    bar(foo(2)); 
} 

risolve (pseudocodice)

<register> = 4; 
RW_A = register; 
RW_A = register; 

(Nota: la lettura e la scrittura di una variabile volatile è un "effetto collaterale osservabile", che l'ottimizzatore deve conservare nello stesso ordine indicato dal codice.)

---

Modificare l'esempio per foo per avere un effetto collaterale:

extern volatile int RW_A = 0; 
extern volatile int RW_B = 0; 
int accu = 1; 

int foo(int a) { accu *= 2; return a * a; } 
void bar(int x) { RW_A = x; } 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    bar(foo(2)); 
    bar(foo(2)); 

    RW_B = accu; 
    return 0; 
} 

genera pseudocodice seguente:

registerA = accu; 
registerA += registerA; 
accu = registerA; 

registerA += registerA; 
registerC = 4; 
accu = registerA; 

RW_A = registerC; 
RW_A = registerC; 

RW_B = registerA; 

Osserviamo che l'eliminazione comune subexpression è ancora fatto, e separato dagli effetti collaterali. Inlining e riordino consente di separare gli effetti collaterali dalla parte "pura".

Si noti che il compilatore legge e scrive con interesse su accu, che non sarebbe necessario. Non sono sicuro sulla logica qui.

---

Per concludere:

Un compilatore non ha bisogno di testare per la purezza. Può identificare gli effetti collaterali che devono essere preservati e quindi trasformare il resto a suo piacimento.

Tali ottimizzazioni sono utili, anche per funzioni banali, perché, tra gli altri,

• risorse della CPU e della memoria sono in comune, quello che si utilizza si potrebbe prendere lontano da qualcun altro
• La durata della batteria
• Ottimizzazioni minori possono essere gateway per quelle più grandi

L'overhead per un accesso alla memoria dello stack è in genere ~ 1 ciclo, poiché la parte superiore dello stack è in genere nella cache di Livello 1 già.Si noti che di solito dovrebbe essere in grassetto: può essere "ancora migliore", dal momento che la lettura/scrittura può essere ottimizzata, o può essere peggiore poiché l'aumento della pressione sulla cache L1 riporta alcuni altri dati importanti a L2.

Dov'è il limite?

In teoria, tempo di compilazione. In pratica, la prevedibilità e la correttezza dell'ottimizzatore sono ulteriori compromessi.

---

Tutti i test con VC2008, impostazioni di ottimizzazione predefinite per "Release" costruire.