Loop Invariant Code Motion - Mi manca qualcosa?
-
05-11-2019 - |
Domanda
Ho implementato LICM per un progetto e mi sono imbattuto in una strana osservazione.
Diciamo che abbiamo un ciclo
int i = 10;
while (i > 0) {
a = 2;
i--;
}
Si può facilmente vederlo a = 2
è invariante. Quello che facciamo dopo è il controllo (per ogni candidato invariante) se il blocco di base contenente domina tutti gli usi di detta variabile e tutte le uscite del ciclo.
Il primo è chiaramente vero, come a
viene usato solo una volta. Quest'ultimo è quello che non mi sembra di ottenere. Il CFG dell'esempio sopra è
Guardando il grafico possiamo vedere chiaramente che il corpo del ciclo (che è solo un singolo blocco di base in questo caso) non domina tutte le uscite!
Dopo aver pensato a questo per un po 'di tempo, sono arrivato alla seguente conclusione:
In un caso generale, non possiamo sapere con certezza se il corpo di un ciclo verrà eseguito almeno una volta. Ciò implica che non si possono semplicemente spostare le istruzioni invarianti fuori dal ciclo, poiché verranno quindi eseguite in modo affidante dal valore effettivo della condizione di terminazione del ciclo.
Non ho visto questo indirizzato in nessuno dei materiali che coprono LICM, nonché in Articolo di Wikipedia. In effetti, il loro esempio, in cui si trasformano
for (int i = 0; i < n; ++i) {
x = y + z;
a[i] = 6 * i + x * x;
}
in
x = y + z;
t1 = x * x;
for (int i = 0; i < n; ++i) {
a[i] = 6 * i + t1;
}
sembra errato, poiché la condizione del loop generalmente avrebbe potuto essere false
alla prima iterazione, e così x = y + z
non avrebbe dovuto essere eseguito affatto.
La mia soluzione proposta
Tutto il codice considerato invariante dovrebbe essere inserito in un if (expr)
, dove expr
è la condizione di loop. Per il mio esempio originale, questo ci darebbe
int i = 10;
if (i > 0) {
a = 2;
}
while (i > 0) {
i--;
}
Nessuna soluzione corretta