La tua ottimizzazione preferita per l'albero della sintassi astratta

Question

Se costruissi un compilatore, quale ottimizzazione a livello di AST sarebbe la migliore da avere?

Answer 1

Un'ottimizzazione che è più facile da fare sull'AST (piuttosto che, per esempio, sul CFG) è l'ottimizzazione di coda: se vedi una sottostruttura del modulo:

RETURN
    CALL f
        ARGS x, y, ...

Puoi sostituirlo con un salto a f. Se f(a, b) è la funzione in cui appare la coda, la sostituzione è semplice come:

a = x; b = y
JUMP to root of tree

Trovo più semplice rappresentare quel salto come un " speciale; riavvio " , che la traduzione AST - > CFG considera come un limite al primo nodo. Saltare ad altre funzioni è un po 'più complicato poiché non si possono semplicemente impostare variabili locali, è necessario pensare in anticipo al modo in cui gli argomenti vengono passati e prepararsi a tradurlo a un livello inferiore. Ad esempio, l'AST potrebbe aver bisogno di un nodo speciale in grado di indicare un passaggio successivo per sovrascrivere il frame dello stack corrente con gli argomenti e saltare di conseguenza.

Answer 2

Principalmente non puoi fare interessanti ottimizzazioni a livello di AST, perché hai bisogno di informazioni su come i dati fluiscono da una parte del programma a un'altra. Mentre il flusso di dati è implicito nel significato di AST, non è facilmente determinabile ispezionando solo l'AST, motivo per cui le persone che compilano compilatori e ottimizzatori costruiscono altre rappresentazioni di programma (tra cui tabelle di simboli, grafici di flusso di controllo, definizione di definizioni, flusso di dati e moduli SSA, ecc.).

Avere un parser per una lingua è la parte facile dell'analisi / manipolazione di quella lingua. Hai bisogno di tutte le altre cose per fare un buon lavoro.

Se hai hai tutte quelle altre rappresentazioni, puoi pensare di fare ottimizzazioni a livello di AST. La maggior parte delle persone che costruiscono compilatori non si preoccupano; si convertono in una rappresentazione del flusso di dati e la ottimizzano semplicemente. Ma se si desidera riprodurre il codice sorgente con modifiche, è necessario l'AST. Avrai anche bisogno di una stampante carina per permetterti di rigenerare il codice sorgente. Se vai così lontano, finirai con una fonte-a-fonte sistema di trasformazione del programma.

Il DMS Software Reengineering Toolkit è un sistema che trasforma gli AST, usando tutti queste altre rappresentazioni per consentire le analisi necessarie alle trasformazioni.

Answer 3

Uno dei vantaggi dell'applicazione delle ottimizzazioni nell'AST è che può ridurre i tempi di esecuzione di alcuni passaggi di ottimizzazione del back-end. Tuttavia, credo che queste ottimizzazioni debbano essere fatte con parsimonia perché potresti ostacolare ulteriori ottimizzazioni nel codice.

Detto questo, l'IMO una ottimizzazione semplice ma interessante da applicare a livello di AST o durante la generazione di IR è la semplificazione dell'espressione booleana del modulo (1 || 2) o (2 < 3 || A), ecc. Al loro risultato netto. Credo che anche alcune semplici ottimizzazioni di spioncino possano valere la pena.