Di alto livello / ottimizzazione semantica

Question

Sto scrivendo un compilatore, e sto cercando le risorse per l'ottimizzazione. Sto compilando in codice macchina, quindi tutto in fase di esecuzione è fuori questione.

Quello che ho cercato ultimamente è l'ottimizzazione del codice di meno e l'ottimizzazione a livello di high più semantico /. Ad esempio:

free(malloc(400)); // should be completely optimized away

Anche se queste funzioni sono state completamente inline, potrebbero finalmente chiamare le funzioni di memoria del sistema operativo che non può mai essere inline. Mi piacerebbe essere in grado di eliminare completamente questa affermazione senza costruire regole speciali di casi nel compilatore (dopo tutto, malloc è solo un'altra funzione).

Un altro esempio:

string Parenthesize(string str) {
    StringBuilder b; // similar to C#'s class of the same name
    foreach(str : ["(", str, ")"])
        b.Append(str);
    return b.Render();
}

In questa situazione mi piacerebbe essere in grado di inizializzare la capacità di b a str.Length + 2 (abbastanza per contenere il risultato esattamente, senza sprecare memoria).

Per essere completamente onesto, non ho idea da dove cominciare ad affrontare questo problema, quindi speravo di un posto per iniziare. C'è stato qualche lavoro svolto in settori analoghi? Ci sono dei compilatori che hanno implementato qualcosa di simile, in senso generale?

Answer 1

Per fare un'ottimizzazione su 2 o più operazioni, dovete capire la relazione algebrica di queste due operazioni. Se si visualizzano le operazioni nella loro dominio del problema, spesso hanno tali rapporti.

Il libero (malloc (400)) è possibile perché gratuito e malloc sono inverse nel dominio allocazione dello storage. Un sacco di operazioni hanno inversi e l'insegnamento al compilatore che sono inversi, e dimostrando che i risultati di un flusso di dati incondizionatamente nell'altro, è ciò che è necessario. Bisogna fare in modo che i tuoi inverse sono davvero inverse e non c'è una sorpresa da qualche parte; a / x * x sembra solo il valore di una, ma se x è uguale a zero si ottiene una trappola. Se non si preoccupano la trappola, si tratta di un inversa; se si fa attenzione circa la trappola, allora l'ottimizzazione è più complessa:       (If (x == 0) allora trappola () else a) che è ancora una buona ottimizzazione se si pensa divario è costoso.

Altre attività "algebriche" sono possibili. Per esempio, ci sono può idempotente operazioni: azzeramento di un nulla (impostando la variabile allo stesso valore ripetutamente), ecc Ci sono operazioni in cui agisce un operando come un elemento di identità; X + 0 ==> X per qualsiasi 0. Se X e 0 sono matrici, questo è ancora vero e un risparmio di tempo grande.

Altre ottimizzazioni possono verificarsi quando si può ragionare in astratto su ciò che il codice sta facendo. "L'interpretazione astratta" è un insieme di tecniche per ragionare su valori di classificare i risultati in varie celle interessanti (per esempio, questo numero intero è sconosciuto, zero, negativo o positivo). Per fare questo è necessario decidere cosa bidoni sono utili, e quindi calcolare il valore astratto in ogni punto. Questo è utile quando ci sono prove su categorie (ad esempio, "se (x <0) {..." e si sa astrattamente che x è minore di zero; li è possibile ottimizzare via la condizionale.

Un altro modo è quello di definire ciò che un calcolo sta facendo simbolicamente, e simulare il calcolo di vedere il risultato. E 'così che si calcolata la dimensione effettiva del buffer richiesto; si calcolata la dimensione del buffer simbolicamente prima del ciclo iniziato, e simulato l'effetto di eseguire il ciclo per tutte le iterazioni. Per questo è necessario essere in grado di costruire formule simboliche che rappresenta le proprietà del programma, comporre queste formule, e spesso semplificare tali formule quando ottengono unusably complesse (i tipi di dissolvenze in astratto schema di interpretazione). Si vuole anche tale calcolo simbolico di prendere in considerazione le proprietà algebriche ho descritto sopra. Strumenti che fanno questo bene sono bravi a costruire formule, e sistemi di programma di trasformazione sono spesso buone basi per questo. Un sistema di programma di trasformazione source-to-source che può essere utilizzato per fare questo è il DMS Software Reengineering Toolkit .

Quello che è difficile è decidere quali ottimizzazioni sono la pena di fare, perché si può finire di tenere traccia di grandi quantità di roba, che non può pagare. cicli Computer sono sempre meno costosi, e quindi ha senso per tenere traccia più proprietà del codice nel compilatore.

Answer 2

Il quadro Broadway potrebbe essere in vena di quello che stai cercando. Articoli su "trasformazione source-to-source" sarà probabilmente anche essere illuminante.