Ottimizzazione dei loop "statici"

Question

Sto scrivendo un linguaggio compilato per divertimento, e recentemente ho ottenuto un calcio per rendere il mio compilatore di ottimizzazione molto robusto. Ho trovato diversi modi per ottimizzare alcune cose, per esempio, 2 + 2 è sempre 4, quindi possiamo fare quella matematica in fase di compilazione, se (false) {...} può essere rimosso completamente, ecc., Ma ora Ho ottenuto loop. Dopo alcune ricerche, penso che quello che sto cercando di fare non è esattamente lo srotolamento del loop, ma è ancora una tecnica di ottimizzazione. Lasciatemi spiegare.

Prendere il seguente codice.

String s = ""; 
for(int i = 0; i < 5; i++){ 
    s += "x"; 
} 
output(s); 

Come essere umano, posso sedermi qui e dirvi che questo è il 100% del tempo sarà equivalente a

output("xxxxx"); 

Quindi, in altre parole, questo ciclo può essere "compilato fuori "interamente. Non è lo srotolamento del ciclo, ma quello che sto definendo "completamente statico", ovvero non ci sono input che potrebbero modificare il comportamento del segmento. La mia idea è che tutto ciò che è completamente statico può essere risolto con un singolo valore, tutto ciò che si basa sull'input o rende ovviamente non ottimizzabile l'output condizionale. Quindi, dal punto di vista della macchina, cosa devo considerare? Cosa rende un loop "completamente statico?"

Ho creato tre tipi di cicli che ho bisogno di capire come classificare. Cicli che finiranno sempre con lo stesso stato macchina dopo ogni corsa, indipendentemente da input, loop che NON si completeranno MAI e loop che non riesco a capire in un modo o nell'altro. Nel caso in cui non riesco a capirlo (cambia condizionatamente quante volte verrà eseguito in base agli input dinamici), non sono preoccupato dell'ottimizzazione. I loop che sono infiniti saranno un errore/avviso di compilazione a meno che non siano specificamente soppressi dal programmatore, e cicli che sono sempre gli stessi dovrebbero saltare direttamente alla messa nello stato corretto, senza loop.

Il caso principale naturalmente di ottimizzare è l'iterazione del ciclo statico, quando anche tutte le chiamate di funzione all'interno sono statiche. Determinare se un loop ha componenti dinamici è abbastanza facile, e se non è dinamico, immagino che debba essere statico. La cosa che non riesco a capire è come scoprire se sarà infinito o no. Qualcuno ha qualche idea su questo? So che questo è un sottoinsieme del problema dell'arresto, ma ritengo che sia risolvibile; il problema dell'arresto è un problema dovuto al fatto che per alcuni sottoinsiemi di programmi, non si può dire che potrebbe durare all'infinito, potrebbe non esserlo, ma non voglio prendere in considerazione quei casi, voglio solo considerare i casi dove si fermerà, o non si fermerà, ma prima devo distinguere tra i tre stati.

Answer 1

Questo sembra un tipo di risolutore simbolico che può essere definito per diverse classi, ma non in generale.

Restringiamo un po 'i requisiti: nessun numero di overflow, solo per loop (mentre a volte può essere trasformato in full loop, tranne quando si utilizza continue ecc.), Nessuna interruzione, nessuna modifica della variabile di controllo all'interno del ciclo for .

for (var i = S; E(i); i = U(i)) ...

dove E (i) e U (i) sono espressioni che possono essere manipolate simbolicamente.Ci sono diverse classi che sono relativamente facili:

U(i) = i + CONSTANT: n ciclo esimo il valore di i è S + n * CONSTANT

U(i) = i * CONSTANT: n ciclo esimo il valore di i è S * CONSTANT^n

U(i) = i/CONSTANT: n -esimo Ciclare il valore di è S * CONSTANT^-n

U(i) = (i + CONSTANT) % M: n ciclo -esimo il valore di i è (S + n * CONSTANT) % M

e alcune altre combinazioni abbastanza facile (e alcuni molto difficili)

Determinare se il ciclo termina è alla ricerca di n dove E(i(n)) è falso. Questo può essere fatto con alcune manipolazioni simboliche per molti casi, ma c'è molto lavoro nel fare il risolutore.

E.g.

• for(int i = 0; i < 5; i++),
• i(n) = 0 + n * 1 = n, E(i(n)) =>not(n < 5) =>
• n >= 5 => ferma per n = 5

---

• for(int i = 0; i < 5; i--),
• i(n) = 0 + n * -1 = -n, E(i(n)) =>not(-n < 5) =>-n >= 5 =>
• n < -5 - dal n è un numero intero non negativo questo non è mai vero - non si ferma mai

---

• for(int i = 0; i < 5; i = (i + 1) % 3),
• E(i(n)) = >not(n % 3 < 5) =>n % 3 >= 5 => questo non è mai vero => non si ferma mai

---

• for(int i = 10; i + 10 < 500; i = i + 2 * i) =>
• for(int i = 10; i < 480; i = 3 * i),
• i(n) = 10 * 3^n,
• E(i(n)) =>not(10 * 3^n < 480) =>10 * 3^n >= 480 =>3^n >= 48 =>n >= log3(48) =>n >= 3.5... =>
• poiché n è intero => si fermerà per n = 4

per altri casi sarebbe bene se possono ottenere trasformato a quelli che si possono già risolvere ...

molti trucchi per la manipolazione simbolica provengono da un'epoca Lisp, e non sono troppo difficili. Sebbene quelli descritti (o varianti) siano la pratica dei tipi più comuni, ci sono molti altri scenari difficili e/o impossibili da risolvere.