14. Propagazione delle espressioni
La disponibilità di informazioni sulla vivacità per ciascuna istruzione aiuta enormemente a comprimere più espressioni semplici in espressioni più complesse. Ciò è particolarmente vero nei chip RISC, dove ogni singola istruzione opera su qualche registro, ma è vero anche per i chip CISC con pochi registri.
Possiamo ora comprimere le varie sequenze di istruzioni senza preoccuparci di rimuovere un riferimento a un registro che possa essere utilizzato in una successiva istruzione. Ad esempio saremo in grado di distinguere il caso sicuro:
R1 = var_1
R2 = R1 + 1
var_2 = R2
a così:
var_2 = var_1 + 1
La propagazione dell’espressione migliora anche la strutturazione del codice, poiché crea espressioni valide dalle istruzioni e le espressioni possono essere unite tramite && e || operatori:
MOV R1, var_1 if(var_1
CMP R1,#10 != 10
JEQ L1 &&
MOV R1, var_2 var_2 if(var_1 != 10 && var_2 != 20)
CMP R1,#20 != 20)
JNE L2 goto L2; goto L2;
L1: ... L1: ...
L2: L2:
Diverse espressioni complesse possono essere costruite scansionando l’elenco delle istruzioni e salvando per ogni assegnazione in un registro sul lato destro dell’assegnazione. Successivamente, quando il registro viene utilizzato, possiamo sostituirlo con il lato destro che abbiamo salvato in precedenza.
Ecco un algoritmo che utilizza questo approccio:
PropagateExpressions(){
for each block in CFG
b.savedRegs = new BitSet(processor.getNumberOfRegs)
for each block in CFG
for each instruction i in block
replaceUses(i.op1)
replaceUses(i.op2)
if i.op == Assign && isRegister(i.dest)
// remember rhs
saveDefinition(block, i)
continue
replaceUses(block, i.dest) // e.g. for indexed addr. modes
}
saveDefinition(Block b, Node i){
b.savedRegs[i.dest.regnum] = i
}
replaceUses(Block b, Node n){
if n == null
return null
n.op1 = replaceUses(n.op1)
n.op2 = replaceUses(n.op2)
if n.op == Register && b.savedRegs[n.regnum] != null
reg = n.regnum
if n.liveout.isSet(reg)
b.savedRegs[reg] = 0 // keep assignment to reg
return n
n = b.savedRegs[reg].op1 // get rhs of original assignment
b.savedRegs[reg] = 0 // remove original assignment to reg
return n
}
Questo è ancora un algoritmo semplicistico, che funziona solo su un blocco di base alla volta. I miglioramenti all’algoritmo consisterebbero nel consentire alle espressioni salvate di propagarsi ad altri blocchi di base. Tuttavia, dobbiamo fare attenzione a non consentire la propagazione tra istruzioni che potrebbero modificare qualsiasi valore presente nell’array salvato. Questo è un problema comune, indicato nella letteratura sull’implementazione del compilatore come problema di rilevamento degli alias .
Considera il seguente codice:
R1 = var_1
*R2 = 0 *R2 = 0
var_2 = R1 var_2 = var_1 ?
In questo codice, non possiamo spostare il riferimento a var_1 nell’istruzione finale a meno che non sappiamo per certo che l’ assegnazione *R2 = 0 non cambierà la posizione di var_1 . Poiché R2 contiene un puntatore, dobbiamo assicurarci che R2 non contenga il valore &var_1 , altrimenti il programma decompilato risultante non si comporterebbe come il codice binario di input.
Questo problema è molto difficile da risolvere; anche un compilatore avanzato non può sempre decidere se una variabile “ha ricevuto un alias” da un puntatore. In questo caso, dobbiamo essere prudenti, evitando così di spostare var_1 all’ultima istruzione.
Si può lavorare molto per decidere se è sicuro mantenere la definizione di R1 o se rimuoverla. L’approccio conservativo consiste nell’invalidare la voce savedRegs per R1 (e in realtà per tutti gli altri registri) ogni volta che c’è un’assegnazione tramite un puntatore indiretto. È sempre sicuro mantenere i riferimenti a valori costanti, compresi i riferimenti a indirizzi fissi, che per definizione non possono essere aliasati.
Un altro caso in cui è difficile decidere cosa ricordare e cosa dimenticare è quando ci sono chiamate di funzione in una delle istruzioni:
R1 = local_1
call f f()
var_2 = R1 var_2 = local_1 ?
In questo caso va bene mantenere local_1 in R1 durante la chiamata a f(), ma solo a determinate condizioni:
- nessun puntatore al frame locale viene passato a
f()o viene salvato in una variabile globale che può essere utilizzata daf() f()non cambia il valore di R1
È molto difficile, anche se non impossibile, tenere traccia di quale indirizzo viene salvato nelle variabili globali e quale viene utilizzato da un’altra funzione. Questo caso è molto raro, quindi dovrebbe essere lecito ritenere che una funzione non modifichi posizioni alias nella memoria globale (ad esempio, possiamo analizzare la funzione e decidere che non scrive alcuna posizione di memoria globale).
La seconda condizione è un po’ più facile da calcolare, anche se anche in questo caso ci sono casi comuni in cui non si sa quali registri vengono modificati dalla funzione. Esistono 2 modi per calcolare l’utilizzo del registro da parte di una funzione:
- eseguire un’analisi del flusso di dati globale sulla funzione, calcolando le informazioni di liveness al punto di ingresso e al punto di uscita della funzione. Questo approccio è complicato dal fatto che la maggior parte delle funzioni salva e ripristina un certo numero di registri durante il loro codice di prologo ed epilogo, quindi potrebbe essere necessario modificare l’algoritmo standard della durata di vita per tenere conto del layout del frame della funzione.
- determinare quale di un insieme di convenzioni di chiamata standard viene utilizzato dalla funzione. Le convenzioni di chiamata vengono impostate da un writer del compilatore o da un fornitore di sistemi operativi, in modo che il codice compilato da fornitori diversi possa comunicare in base a un insieme fisso di regole. Queste regole di solito definiscono quali registri possono essere modificati da una chiamata di funzione e quali registri devono essere conservati durante la chiamata, rendendo così possibile decidere se è corretto spostare un’assegnazione attraverso un’istruzione di chiamata di funzione.
