Analisi del flusso di dati - Data-flow analysis

L'analisi del flusso di dati è una tecnica per raccogliere informazioni sul possibile insieme di valori calcolati in vari punti di un programma per computer . Il grafico del flusso di controllo di un programma (CFG) viene utilizzato per determinare quelle parti di un programma a cui potrebbe propagarsi un particolare valore assegnato a una variabile. Le informazioni raccolte vengono spesso utilizzate dai compilatori durante l' ottimizzazione di un programma. Un esempio canonico di analisi del flusso di dati sta raggiungendo le definizioni .

Un modo semplice per eseguire l'analisi del flusso di dati dei programmi consiste nell'impostare equazioni del flusso di dati per ciascun nodo del grafico del flusso di controllo e risolverli calcolando ripetutamente l'output dall'input localmente in ciascun nodo finché l'intero sistema non si stabilizza, ad es. , raggiunge un punto fisso .Questo approccio generale, noto anche come metodo di Kildall , è stato sviluppato da Gary Kildall mentre insegnava alla Naval Postgraduate School .

Principi di base

L'analisi del flusso di dati è il processo di raccolta di informazioni sul modo in cui vengono utilizzate le variabili, definito nel programma. Tenta di ottenere informazioni particolari in ogni punto di una procedura. Di solito, è sufficiente ottenere questa informazione ai confini dei blocchi di base , poiché da ciò è facile calcolare l'informazione nei punti del blocco di base. Nell'analisi del flusso in avanti, lo stato di uscita di un blocco è una funzione dello stato di ingresso del blocco. Questa funzione è la composizione degli effetti delle istruzioni nel blocco. Lo stato di entrata di un blocco è una funzione degli stati di uscita dei suoi predecessori. Questo produce una serie di equazioni del flusso di dati:

Per ogni blocco b:

${\displaystyle out_{b}=trans_{b}(in_{b})}$

${\displaystyle in_{b}=join_{p\in pred_{b}}(out_{p})}$

In questo, è la funzione di trasferimento del blocco . Funziona sullo stato di entrata , producendo lo stato di uscita . L' operazione di join combina gli stati di uscita dei predecessori di , ottenendo lo stato di ingresso di . ${\displaystyle trans_{b}}$${\displaystyle b}$${\displaystyle in_{b}}$${\displaystyle out_{b}}$ ${\displaystyle unisciti}$${\displaystyle p\in pred_{b}}$${\displaystyle b}$${\displaystyle b}$

Dopo aver risolto questo insieme di equazioni, gli stati di entrata e/o uscita dei blocchi possono essere utilizzati per derivare le proprietà del programma ai limiti del blocco. La funzione di trasferimento di ogni istruzione separatamente può essere applicata per ottenere informazioni in un punto all'interno di un blocco di base.

Ogni particolare tipo di analisi del flusso di dati ha la sua specifica funzione di trasferimento e operazione di unione. Alcuni problemi di flusso di dati richiedono l'analisi del flusso all'indietro. Questo segue lo stesso piano, tranne per il fatto che la funzione di trasferimento viene applicata allo stato di uscita che produce lo stato di entrata e l'operazione di unione funziona sugli stati di entrata dei successori per ottenere lo stato di uscita.

Il punto di ingresso (nel flusso in avanti) svolge un ruolo importante: poiché non ha predecessori, il suo stato di ingresso è ben definito all'inizio dell'analisi. Ad esempio, l'insieme delle variabili locali con valori noti è vuoto. Se il grafico del flusso di controllo non contiene cicli (non c'erano loop espliciti o impliciti nella procedura) la risoluzione delle equazioni è semplice. Il grafico del flusso di controllo può quindi essere ordinato topologicamente ; eseguendo nell'ordine di questo tipo, gli stati di entrata possono essere calcolati all'inizio di ogni blocco, poiché tutti i predecessori di quel blocco sono già stati elaborati, quindi i loro stati di uscita sono disponibili. Se il grafico del flusso di controllo contiene cicli, è necessario un algoritmo più avanzato.

Un algoritmo iterativo

Il modo più comune per risolvere le equazioni del flusso di dati consiste nell'utilizzare un algoritmo iterativo. Inizia con un'approssimazione dell'in-state di ciascun blocco. Gli stati out vengono quindi calcolati applicando le funzioni di trasferimento sugli stati in. Da questi, gli in-state vengono aggiornati applicando le operazioni di join. Gli ultimi due passaggi si ripetono fino a raggiungere il cosiddetto punto fisso : la situazione in cui gli in-state (e gli out-state di conseguenza) non cambiano.

Un algoritmo di base per risolvere le equazioni del flusso di dati è l' algoritmo iterativo round-robin :

per i ← da 1 a N

inizializza il nodo i

mentre ( i set stanno ancora cambiando )

per i ← da 1 a N

ricalcolare gli insiemi al nodo i

Convergenza

Per essere utilizzabile, l'approccio iterativo dovrebbe effettivamente raggiungere un punto fisso. Ciò può essere garantito imponendo vincoli alla combinazione del dominio del valore degli stati, delle funzioni di trasferimento e dell'operazione di join.

Il dominio del valore dovrebbe essere un ordine parziale con altezza finita (cioè, non ci sono catene ascendenti infinite < < ...). La combinazione della funzione di trasferimento e dell'operazione di join dovrebbe essere monotona rispetto a questo ordine parziale. La monotonicità assicura che ad ogni iterazione il valore rimarrà lo stesso o crescerà più grande, mentre l'altezza finita assicura che non possa crescere indefinitamente. Quindi alla fine raggiungeremo una situazione in cui T(x) = x per ogni x, che è il punto fisso. ${\displaystyle x_{1}}$${\displaystyle x_{2}}$

L'approccio della lista di lavoro

È facile migliorare l'algoritmo di cui sopra notando che l'in-state di un blocco non cambierà se gli out-state dei suoi predecessori non cambiano. Pertanto, introduciamo un elenco di lavoro : un elenco di blocchi che devono ancora essere elaborati. Ogni volta che lo stato out di un blocco cambia, aggiungiamo i suoi successori all'elenco di lavoro. Ad ogni iterazione, viene rimosso un blocco dall'elenco di lavoro. Il suo stato out viene calcolato. Se lo stato out è cambiato, i successori del blocco vengono aggiunti all'elenco di lavoro. Per efficienza, un blocco non dovrebbe essere nell'elenco di lavoro più di una volta.

L'algoritmo viene avviato inserendo blocchi che generano informazioni nell'elenco di lavoro. Termina quando la lista di lavoro è vuota.

Ordinazione

L'efficienza della risoluzione iterativa delle equazioni del flusso di dati è influenzata dall'ordine in cui vengono visitati i nodi locali. Inoltre, dipende dal fatto che le equazioni del flusso di dati siano utilizzate per l'analisi del flusso di dati in avanti o all'indietro sul CFG. Intuitivamente, in un problema di flusso in avanti, sarebbe più veloce se tutti i predecessori di un blocco fossero stati elaborati prima del blocco stesso, da allora l'iterazione utilizzerà le informazioni più recenti. In assenza di loop è possibile ordinare i blocchi in modo tale che vengano calcolati gli out-state corretti elaborando ogni blocco una sola volta.

Di seguito vengono discussi alcuni ordini di iterazione per risolvere le equazioni del flusso di dati (un concetto correlato all'ordine di iterazione di un CFG è l' attraversamento dell'albero di un albero ).

• Ordine casuale : questo ordine di iterazione non è a conoscenza se le equazioni del flusso di dati risolvono un problema di flusso di dati in avanti o all'indietro. Pertanto, le prestazioni sono relativamente scarse rispetto agli ordini di iterazione specializzati.
• Postorder - Questo è un tipico ordine di iterazione per problemi di flusso di dati all'indietro. In iterazione postorder , un nodo viene visitato dopo che tutti i nodi successori sono stati aperti. In genere, l' iterazione post - ordine viene implementata con lastrategia depth-first .
• Post - ordine inverso : questo è un tipico ordine di iterazione per problemi di flusso di dati in avanti. In inversa postorder iterazione , un nodo viene visitato prima di qualsiasi dei suoi nodi successori è stato visitato, tranne quando il successore viene raggiunto da un bordo posteriore. (Nota che il postorder inverso non è lo stesso del preorder .)

Inizializzazione

Il valore iniziale degli in-state è importante per ottenere risultati corretti e accurati. Se i risultati sono usati per le ottimizzazioni del compilatore, dovrebbero fornire informazioni conservative , cioè quando si applicano le informazioni, il programma non dovrebbe cambiare la semantica. L'iterazione dell'algoritmo del punto fisso assumerà i valori nella direzione dell'elemento massimo. L'inizializzazione di tutti i blocchi con l'elemento massimo non è quindi utile. Almeno un blocco inizia in uno stato con un valore inferiore al massimo. I dettagli dipendono dal problema del flusso di dati. Se l'elemento minimo rappresenta un'informazione totalmente conservativa, i risultati possono essere utilizzati in sicurezza anche durante l'iterazione del flusso di dati. Se rappresenta le informazioni più accurate, il punto fisso dovrebbe essere raggiunto prima che i risultati possano essere applicati.

Esempi

Di seguito sono riportati esempi di proprietà dei programmi per computer che possono essere calcolati mediante l'analisi del flusso di dati. Si noti che le proprietà calcolate dall'analisi del flusso di dati sono in genere solo approssimazioni delle proprietà reali. Questo perché l'analisi del flusso di dati opera sulla struttura sintattica del CFG senza simulare l'esatto flusso di controllo del programma. Tuttavia, per essere ancora utile nella pratica, un algoritmo di analisi del flusso di dati è tipicamente progettato per calcolare un'approssimazione superiore o inferiore delle proprietà reali del programma.

Analisi in avanti

L' analisi della definizione di raggiungimento calcola per ogni punto del programma l'insieme di definizioni che potrebbero potenzialmente raggiungere questo punto del programma.

  if b==4 then
     a = 5;
  else 
     a = 3;
  endif
 
  if  a < 4 then
     ...

Analisi a ritroso

L' analisi delle variabili in tempo reale calcola per ogni punto del programma le variabili che potrebbero essere potenzialmente lette in seguito prima del successivo aggiornamento di scrittura. Il risultato viene in genere utilizzato dall'eliminazione del codice morto per rimuovere le istruzioni che assegnano a una variabile il cui valore non viene utilizzato in seguito.

L'in-state di un blocco è l'insieme di variabili che sono attive all'inizio di esso. Inizialmente contiene tutte le variabili live (contenute) nel blocco, prima che venga applicata la funzione di trasferimento e vengano calcolati i valori contenuti effettivi. La funzione di trasferimento di un'istruzione viene applicata uccidendo le variabili scritte all'interno di questo blocco (rimuovendole dall'insieme delle variabili attive). Lo stato out di un blocco è l'insieme delle variabili che sono attive alla fine del blocco ed è calcolato dall'unione degli stati in successori del blocco.

Codice iniziale:

b1: a = 3; 
    b = 5;
    d = 4;
    x = 100;
    if a > b then
b2:    c = a + b;
       d = 2;
b3: endif
    c = 4;
    return b * d + c;

Analisi a ritroso:

// in: {}
b1: a = 3; 
    b = 5;
    d = 4;
    x = 100; //x is never being used later thus not in the out set {a,b,d}
    if a > b then
// out: {a,b,d}    //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d}  

// in: {a,b}
b2: c = a + b;
    d = 2;
// out: {b,d}

// in: {b,d}
b3: endif
    c = 4;
    return b * d + c;
// out:{}

Lo stato in b3 contiene solo b e d , poiché c è stato scritto. Lo stato out di b1 è l'unione degli stati in b2 e b3. La definizione di c in b2 può essere rimossa, poiché c non è vivo immediatamente dopo l'istruzione.

La risoluzione delle equazioni del flusso di dati inizia con l'inizializzazione di tutti gli stati in e out sull'insieme vuoto. La lista di lavoro viene inizializzata inserendo il punto di uscita (b3) nella lista di lavoro (tipico per il flusso a ritroso). Il suo stato calcolato differisce da quello precedente, quindi i suoi predecessori b1 e b2 vengono inseriti e il processo continua. I progressi sono riassunti nella tabella seguente.

Si noti che b1 è stato inserito nell'elenco prima di b2, il che ha forzato l'elaborazione di b1 due volte (b1 è stato reinserito come predecessore di b2). L'inserimento di b2 prima di b1 avrebbe consentito il completamento anticipato.

L'inizializzazione con l'insieme vuoto è un'inizializzazione ottimistica: tutte le variabili iniziano come morte. Si noti che gli stati out non possono ridursi da un'iterazione all'altra, sebbene lo stato out possa essere più piccolo di quello in. Questo può essere visto dal fatto che dopo la prima iterazione lo stato out può cambiare solo con un cambiamento dello stato in. Poiché lo stato inizia come set vuoto, può crescere solo in ulteriori iterazioni.

Altri approcci

Nel 2002, Markus Mohnen ha descritto un nuovo metodo di analisi del flusso di dati che non richiede la costruzione esplicita di un grafico del flusso di dati, basandosi invece sull'interpretazione astratta del programma e mantenendo un set funzionante di contatori di programma. Ad ogni branch condizionale, entrambe le destinazioni vengono aggiunte al working set. Ogni percorso viene seguito per il maggior numero di istruzioni possibile (fino alla fine del programma o fino a quando non è stato eseguito il ciclo senza modifiche), quindi rimosso dall'insieme e recuperato il contatore del programma successivo.

Una combinazione di analisi del flusso di controllo e analisi del flusso di dati si è dimostrata utile e complementare nell'identificare regioni di codice sorgente coerenti che implementano le funzionalità di un sistema (ad es. caratteristiche , requisiti o casi d'uso ).

Classi speciali di problemi

Ci sono una varietà di classi speciali di problemi di flusso di dati che hanno soluzioni efficienti o generali.

Problemi con i bit vettoriali

Gli esempi sopra sono problemi in cui il valore del flusso di dati è un insieme, ad esempio l'insieme delle definizioni di raggiungimento (usando un bit per una posizione di definizione nel programma), o l'insieme delle variabili live. Questi insiemi possono essere rappresentati in modo efficiente come vettori di bit , in cui ogni bit rappresenta l'appartenenza all'insieme di un particolare elemento. Utilizzando questa rappresentazione, le funzioni di join e trasferimento possono essere implementate come operazioni logiche bit per bit. L'operazione di join è in genere unione o intersezione, implementata da logical or e logical and . La funzione di trasferimento per ogni blocco può essere scomposta nei cosiddetti set gen e kill .

Ad esempio, nell'analisi di variabili live, l'operazione di join è union. Il kill set è l'insieme delle variabili che vengono scritte in un blocco, mentre il gen set è l'insieme delle variabili che vengono lette senza essere prima scritte. Le equazioni del flusso di dati diventano

${\displaystyle out_{b}=\bigcup _{s\in succ_{b}}in_{s}}$

${\displaystyle in_{b}=(out_{b}-kill_{b})\cup gen_{b}}$

Nelle operazioni logiche, questo si legge come

out(b) = 0
for s in succ(b)
    out(b) = out(b) or in(s)
in(b) = (out(b) and not kill(b)) or gen(b)

I problemi di flusso di dati che hanno insiemi di valori di flusso di dati che possono essere rappresentati come vettori di bit sono chiamati problemi di vettore di bit , problemi di gen-kill o problemi separabili localmente . Tali problemi hanno soluzioni tempo-polinomiale generiche.

Oltre alle definizioni di raggiungimento e ai problemi di variabili live menzionati sopra, i seguenti problemi sono istanze di problemi di bitvector:

• Espressioni disponibili
• Espressioni molto impegnate
• Catene di definizione d'uso

problemi IFDS

I problemi interprocedurali, finiti, distributivi, di sottoinsiemi o problemi IFDS sono un'altra classe di problemi con una generica soluzione tempo-polinomiale. Le soluzioni a questi problemi forniscono analisi del flusso di dati sensibili al contesto e al flusso.

Esistono diverse implementazioni di analisi del flusso di dati basate su IDFS per i linguaggi di programmazione più diffusi, ad esempio nei framework Soot e WALA per l'analisi Java.

Ogni problema di bitvector è anche un problema IDFS, ma ci sono diversi problemi IDFS significativi che non sono problemi di bitvector, incluse variabili realmente attive e variabili possibilmente non inizializzate.

sensibilità

L'analisi del flusso di dati è intrinsecamente sensibile al flusso. L'analisi del flusso di dati è in genere insensibile al percorso, sebbene sia possibile definire equazioni del flusso di dati che producono un'analisi sensibile al percorso.

• Un'analisi sensibile al flusso tiene conto dell'ordine delle istruzioni in un programma. Ad esempio, un'analisi dell'alias del puntatore non sensibile al flusso può determinare "le variabili x e y possono fare riferimento alla stessa posizione", mentre un'analisi sensibile al flusso può determinare "dopo l'istruzione 20, le variabili x e y possono fare riferimento alla stessa posizione".
• Un'analisi sensibile al percorso calcola diverse informazioni di analisi in base ai predicati nelle istruzioni di salto condizionale. Ad esempio, se un ramo contiene una condizione x>0, quindi sul percorso di fall-through , l'analisi assumerebbe che x<=0e sull'obiettivo del ramo presumerebbe che effettivamente x>0valga.
• Un'analisi sensibile al contesto è un'analisi interprocedurale che considera il contesto di chiamata durante l'analisi della destinazione di una chiamata di funzione. In particolare, utilizzando le informazioni di contesto è possibile tornare al sito di chiamata originale, mentre senza tali informazioni, le informazioni di analisi devono essere propagate a tutti i possibili siti di chiamata, perdendo potenzialmente precisione.

Elenco delle analisi del flusso di dati

• Raggiungere le definizioni
• Analisi della vitalità
• Analisi dell'assegnazione definita
• Espressione disponibile
• Propagazione costante

Guarda anche

• Interpretazione astratta
• Analisi del flusso di controllo
• XLT86

Riferimenti

Ulteriori letture

• Cooper, Keith D. ; Torczon, Linda (2003) [2002-01-01]. Progettazione di un compilatore . Morgan Kaufmann . ISBN 978-1-55860-698-2.
• Muchnick, Steven Stanley (1997). Progettazione e implementazione avanzate di compilatori . Morgan Kaufmann Editori . ISBN 978-1-55860-320-2.
• Hecht, Matthew S. (1977-05-03). Analisi del flusso di programmi per computer . Serie sui linguaggi di programmazione. 5 . Elsevier North-Holland Inc. ISBN 978-0-44400210-5.
• Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri (2009). Analisi del flusso di dati: teoria e pratica . CRC Press ( Taylor e Francis Group ).
• Nielson, Flemming; Nielson, Hanne Riis; Hankin, Chris (2005). Principi di analisi del programma . Springer Science+Business Media .