Non so se questa domanda abbia una risposta semplice o no, ma devo solo chiedere.
Sto leggendo questo tutorial (non so se si tratta di una serie ben nota, ma si tratta di un nome è 'Costruiamo un compilatore!' di Jack Crenshaw). È una serie piacevole in cui impari gradualmente come costruire un compilatore (è una cosa che impara da fare, in realtà).
Già nel secondo capitolo, ho sentito il bisogno di ottimizzare alcune cose. Nella serie, vengono fatte alcune concessioni, per mantenere le cose semplici: non c'è differenza tra lo scanner lessicale (anche se credo che sia introdotto più avanti nella serie) e la generazione del codice: sono fatte in un colpo solo. Inoltre, l'autore fa molto affidamento sullo stack per creare il codice per gestire le espressioni. (Inoltre, l'output è codice assembly, non so se questo è normale per i compilatori, quindi ho pensato di parlarne ...)
Ad esempio, l'analisi dell'espressione 5 + (7 * 3 - 21/3) (e la memorizzazione del risultato in eax) risulta approssimativamente nel seguente codice (io uso x86 asm, al contrario della serie, quindi questo è il codice assembly che il mio compilatore ha dato):
push 5 ; These lines is generated by a simple number parser
push 7 ; This parser pushes its result to the stack
push 3 ; (like most other parsing functions)
pop eax ; Code for multiplication
pop ebx
mul ebx
push eax
push 21 ; Result of parsing these numbers
push 3
pop ebx ; Division code
pop eax
div ebx
push eax
pop ebx ; Subtraction code
pop eax
sub eax, ebx
push eax
pop eax ; Addition code
pop ebx
add eax, ebx
push eax
Come puoi vedere, il codice per gestire l'addizione, la sottrazione, la moltiplicazione, ecc. può rimanere lo stesso ogni volta che l'operazione viene utilizzata. Questo è molto conveniente, ma ovviamente il codice assembly generato è molto lento ed esoterico. Quando scrivi a mano, preferisci scrivere qualcosa come:
mov eax, 21
div 3
mov ebx, eax
mov eax, 7
mul 3
sub eax, ebx
add 5
La mia domanda è se c'è un modo per ottimizzare l'output del compilatore. Certo che c'è, ma c'è un modo specifico per rendere il mio codice più simile al secondo, cioè: non usare lo stack così intensamente, ma affidarsi invece ai registri per passare i valori.
Io stesso ho pensato di analizzare l'intera espressione e rappresentarla internamente come una struttura ad albero (suppongo che sia il tipo di cosa che fa un parser lessicale) prima di generare il codice, ma non sono del tutto sicuro di come procedere. D'altra parte, c'è l'ottimizzazione dello spioncino e la possibilità di ottimizzare il codice assembler dopo che è stato generato, ma non ho idea di quanto sarà efficace. Generare codice migliore in primo luogo sembra logico e più fattibile per me.
So che ci sono molte tecniche disponibili per ottimizzare il mio codice (ad esempio, il folding costante, che ridurrebbe l'intera espressione a 19. Non ho deliberatamente usato questo tipo di ottimizzazione per migliorare il mio punto di vista), spero per una singola tecnica che è adatta per questo tipo di cose.