Come semplificare un'espressione aritmetica in stile C contenente variabili durante la generazione del codice?

Question

Sto cercando di ottimizzare la valutazione delle espressioni in un compilatore.

Le espressioni aritmetiche sono tutte in stile C e possono contenere variabili. Spero di semplificare il più possibile le espressioni.

Ad esempio, (3+100*A*B+100)*3+100 può essere semplificato in 409+300*A*B.

Dipende principalmente dalla legge distributiva, dalla legge associativa e dalla legge commutativa.

La principale difficoltà che incontro è come combinare queste leggi aritmetiche e gli algoritmi di valutazione dello stack-scan tradizionali.

Qualcuno può condividere esperienze relative a questo o problemi simili nel contesto della compilazione del compilatore?

Answer 1

Applicare constant folding combinato con riduzione della resistenza durante il passaggio di generazione del codice della compilazione. La maggior parte dei testi del compilatore fornirà un algoritmo per implementare questo.

Answer 2

I compilatori di solito hanno alcune regole di normalizzazione interne come "costanti a sinistra". Ciò significa che a + 3 verrà trasformato in 3 + a, ma non viceversa.

Nel tuo esempio, (3+100*A*B+100)*3+100 sarebbe normalizzato in (3+100+(100*A*B))*3+100. Ora è possibile ottimizzare 3+100.

Un'altra trasformazione potrebbe essere a*C1+C2 in (a+(C2/C1))*C1 a condizione che C1 e C2 siano costanti. Intuitivamente, questo normalizza "aggiungi prima di moltiplicare".

Queste normalizzazioni non sono ottimizzazioni. L'intenzione è principalmente di raggruppare le costanti insieme, quindi il piegamento costante è più efficace.