Analisi degli alias - Alias analysis

L'analisi degli alias è una tecnica nella teoria del compilatore , utilizzata per determinare se è possibile accedere a una posizione di archiviazione in più di un modo. Si dice che due puntatori hanno un alias se puntano alla stessa posizione.

Le tecniche di analisi alias sono generalmente classificate in base alla sensibilità al flusso e alla sensibilità al contesto. Possono determinare le informazioni may-alias o must-alias. Il termine analisi alias viene spesso utilizzato in modo intercambiabile con analisi point-to , un caso specifico.

Gli analizzatori di alias intendono creare e calcolare informazioni utili per comprendere l' aliasing nei programmi.

Panoramica

In generale, l'analisi degli alias determina se i riferimenti di memoria separati puntano o meno alla stessa area di memoria. Ciò consente al compilatore di determinare quali variabili nel programma saranno influenzate da un'istruzione. Si consideri ad esempio la seguente sezione di codice che accede ai membri delle strutture: 

p.foo = 1;
q.foo = 2;
i = p.foo + 3;

Ci sono tre possibili casi di alias qui:

  1. Le variabili peq non possono essere alias (cioè, non puntano mai alla stessa posizione di memoria).
  2. Le variabili peq devono essere alias (cioè, puntano sempre alla stessa posizione di memoria).
  3. Non può essere determinato in modo definitivo in fase di compilazione se p e q si alias o meno.

Se p e q non possono essere alias, i = p.foo + 3; possono essere modificati in i = 4 . Se p e q devono essere alias, allora i = p.foo + 3; può essere cambiato in i = 5 because p.foo + 3 = q.foo + 3 . In entrambi i casi, siamo in grado di eseguire ottimizzazioni dalla conoscenza dell'alias (supponendo che nessun altro thread che aggiorna le stesse posizioni possa intercalarsi con il thread corrente, o che il modello di memoria del linguaggio consenta a quegli aggiornamenti di non essere immediatamente visibili al thread corrente in assenza di costrutti di sincronizzazione espliciti ). D'altra parte, se non si sa se p e q alias o meno, non è possibile eseguire alcuna ottimizzazione e per ottenere il risultato deve essere eseguito l'intero codice. Si dice che due riferimenti alla memoria abbiano una relazione may-alias se il loro alias è sconosciuto.

Esecuzione dell'analisi degli alias

Nell'analisi degli alias, dividiamo la memoria del programma in classi di alias . Le classi alias sono insiemi disgiunti di posizioni che non possono essere alias tra loro. Per la discussione qui, si presume che le ottimizzazioni fatte qui avvengano su una rappresentazione intermedia di basso livello del programma. Questo per dire che il programma è stato compilato in operazioni binarie, salti, si sposta tra i registri, si sposta dai registri alla memoria, si sposta dalla memoria ai registri, rami e chiamate / ritorni di funzioni.

Analisi degli alias basata sul tipo

Se il linguaggio da compilare è indipendente dai tipi , il controllo del tipo del compilatore è corretto e il linguaggio non ha la capacità di creare puntatori che fanno riferimento a variabili locali (come ML , Haskell o Java ), è possibile apportare alcune utili ottimizzazioni. Ci sono molti casi in cui sappiamo che due posizioni di memoria devono essere in classi di alias diverse:

  1. Due variabili di tipi diversi non possono essere nella stessa classe alias poichéèuna proprietà di linguaggi fortemente tipizzati, senza riferimenti di memoria (cioè, i riferimenti a posizioni di memoria non possono essere modificati direttamente) che due variabili di tipi diversi non possono condividere la stessa posizione di memoria contemporaneamente.
  2. Le allocazioni locali allo stack frame corrente non possono essere nella stessa classe alias di qualsiasi allocazione precedente da un altro stack frame. Questo è il caso perché le nuove allocazioni di memoria devono essere disgiunte da tutte le altre allocazioni di memoria.
  3. Ogni campo record di ogni tipo di record ha una propria classe di alias, in generale, perché la disciplina di digitazione di solito consente solo record dello stesso tipo di alias. Poiché tutti i record di un tipo verranno archiviati in un formato identico in memoria, un campo può essere alias solo a se stesso.
  4. Allo stesso modo, ogni array di un dato tipo ha la propria classe alias.

Quando si esegue l'analisi degli alias per il codice, ogni caricamento e archivio in memoria deve essere etichettato con la sua classe. Abbiamo quindi la proprietà utile, date le posizioni di memoria e con classi alias, che se allora può-alias , e se poi le posizioni di memoria non saranno alias.

Analisi degli alias basata sul flusso

L'analisi basata sul flusso può essere applicata a programmi in un linguaggio con riferimenti o type casting. L'analisi basata sul flusso può essere utilizzata al posto o per integrare l'analisi basata sul tipo. Nell'analisi basata sul flusso, vengono create nuove classi di alias per ciascuna allocazione di memoria e per ogni variabile globale e locale il cui indirizzo è stato utilizzato. I riferimenti possono puntare a più di un valore nel tempo e quindi possono essere in più di una classe di alias. Ciò significa che ogni posizione di memoria ha un insieme di classi alias invece di una singola classe alias.

Guarda anche

Riferimenti

  • Appel, Andrew W. (1998). Implementazione del compilatore moderno in ML . Cambridge, Regno Unito: Cambridge University Press. ISBN   0-521-60764-7 .

link esterno