Domande sulle ottimizzazioni del compilatore

Question

1. Quali sono alcuni dei modi in cui un compilatore elimina i ripetuti calcoli delle sottoespressioni? Come tenere traccia delle sottoespressioni? E come si identificano quelli ripetuti?
2. Oltre all'utilizzo di operatori bit a bit, quali sono alcune delle tecniche di riduzione della forza utilizzate dai compilatori comuni?

Answer 1

1. Credo che molti compilatori utilizzino SSAPRE (eliminazione di ridondanza parziale parziale di assegnazione statica) per eliminare espressioni ripetute. Ciò richiede che il codice sia in modulo SSA , consentendo molte più ottimizzazioni.

2. Non ne sono davvero sicuro, ma guarda questo elenco di passaggi LLVM . LLVM è un IR ottimizzante per i compilatori che è spesso più veloce di persino GCC. C'è una piccola spiegazione di ogni passaggio. Se hai bisogno di maggiori informazioni, guarda l'origine LLVM per questi passaggi. È scritto in C ++ ma è abbastanza pulito e comprensibile.

Modifica: A proposito, se stai sviluppando un compilatore, consiglio vivamente LLVM, è molto facile da usare e genera codice altamente ottimizzato.

Answer 2

Per 1, Il nome dell'ottimizzazione che stai cercando è l'eliminazione della sottoespressione comune (CSE). A seconda della tua rappresentazione, questo può essere abbastanza facile. Di solito, un compilatore avrà una rappresentazione intermedia di un programma in cui le operazioni sono suddivise il più possibile e linearizzate. Ad esempio, l'espressione c = a * b + a * b potrebbe essere suddivisa in:

v1 = a * b
v2 = a * b
c = v1 + v2

Quindi potresti fare CSE a un livello molto basso cercando operazioni con lo stesso operatore e operandi. Quando si incontra un duplicato (v2 in questo caso), si sostituisce tutte le istanze di esso con l'originale. Quindi potremmo semplificare il codice sopra riportato:

v1 = a * b
c = v1 + v1

Questo generalmente presuppone che ogni variabile venga assegnata una sola volta (singolo modulo di assegnazione statico), ma è possibile implementare qualcosa del genere senza tale restrizione. Ciò diventa più complicato quando si tenta di eseguire questa ottimizzazione tra i vari rami. Come menziona Zifre, esamina l'eliminazione della ridondanza parziale.

Ad ogni modo, ottieni alcuni miglioramenti di base e tutto ciò che devi tenere traccia delle espressioni di base. Potresti voler fare un ulteriore passo avanti e cercare identità aritmetiche. Ad esempio, a * b è uguale a b * a . Inoltre, x * (y + z) = x * y + x * z . Questo rende la tua ottimizzazione più complicata e non è chiaro che ti darebbe così tanto miglioramento delle prestazioni. Aneddoticamente, la maggior parte dei vantaggi di un'ottimizzazione CSE deriva dai calcoli degli indirizzi come gli accessi agli array e non avrete bisogno di identità complicate come quelle sopra.

Per 2, quali riduzioni di forza sono utili dipende in realtà dall'architettura per cui si compila. Di solito questo comporta solo la trasformazione di moltiplicazioni e divisioni in turni, aggiunte e sottrazioni.

Answer 3

Consiglio vivamente due riferimenti stampati su questi argomenti:

1. Advanced Compiler Design & amp; Implementazione di Steven S. Muchnick
2. Creazione di un compilatore di ottimizzazione di Robert Morgan

Il libro di Muchnick è formale, ma è molto leggibile e ha buone descrizioni di tutte le importanti tecniche di ottimizzazione. Il libro Morgan ha un aspetto molto più pratico e sarebbe un'ottima base per un progetto di compilatore incentrato sulle tecniche di ottimizzazione. Nessuno dei due libri ha molto da dire sull'analisi lessicale o sull'analisi, si presuppone la conoscenza di questi argomenti.

Answer 4

Per aggiungere un altro libro all'elenco dei consigli, controlla " Hacker's Delight " ; di Henry S. Warren. È un ottimo compendio di tecniche per l'ottimizzazione di operazioni comuni, come la trasformazione di divisioni intere in moltiplicazioni.

Answer 5

Stai cercando l'eliminazione della ridondanza parziale (PRE). Sia CSE (dalle altre risposte) che il moto del codice invariante al ciclo sono inclusi in PRE. (Una variante di PRE è Lazy Code Motion, che credo sia ottimale).

Guarda Appunti di lezione di Keith Cooper , che sembra descrivere molto bene le tecniche.

NON usa SSAPRE. AFAIK, ciò richiede una particolare forma di SSA nota come HSSA, che presenta alcuni aspetti negativi:

• È piuttosto complicato
• Richiede la numerazione globale dei valori (e quindi SSAPRE non fornisce la numerazione dei valori, poiché dovrebbe già esistere).
• Non fornisce nulla se la tua lingua non supporta i puntatori per impilare le variabili (e in tal caso, smetti di scrivere la tua analisi e usa LLVM o gcc).
• gcc ha usato HSSA per un po ', ma si sono allontanati da esso.
• LLVM l'ha provato, ma AFAIK non lo usano più.

EDIT:

Il libro di Muchnick ha una descrizione dettagliata, collegata in un'altra risposta.