Analisi delle dipendenze - Dependence analysis

Nella teoria del compilatore , l' analisi delle dipendenze produce vincoli sull'ordine di esecuzione tra istruzioni / istruzioni. In generale, un'istruzione S2 dipende da S1 se S1 deve essere eseguita prima di S2 . In generale, ci sono due classi di dipendenze: dipendenze di controllo e dipendenze dai dati .

L'analisi delle dipendenze determina se è sicuro riordinare o parallelizzare le istruzioni.

Controlla le dipendenze

La dipendenza dal controllo è una situazione in cui viene eseguita un'istruzione di programma se l'istruzione precedente valuta in un modo che ne consente l'esecuzione.

Un'istruzione S2 dipende dal controllo da S1 (scritta ) se e solo se l' esecuzione di S2 è controllata condizionatamente da S1 . Il seguente è un esempio di tale dipendenza dal controllo: ${\ displaystyle S1 \ \ delta ^ {c} \ S2}$

S1       if x > 2 goto L1
S2       y := 3   
S3   L1: z := y + 1

Qui, S2 viene eseguito solo se il predicato in S1 è falso.

Vedi dipendenze dei dati per maggiori dettagli.

Dipendenze dai dati

Una dipendenza dai dati deriva da due istruzioni che accedono o modificano la stessa risorsa.

Flusso (vera) dipendenza

Una dichiarazione S2 è flusso dipende in S1 (scritto ) se e solo se S1 modifica una risorsa che S2 legge e S1 precede S2 in esecuzione. Di seguito è riportato un esempio di dipendenza dal flusso (RAW: lettura dopo scrittura): ${\ displaystyle S1 \ \ delta ^ {f} \ S2}$

S1       x := 10
S2       y := x + c

Antidependence

Una dichiarazione S2 è antidependent su S1 (scritto ) se e solo se S2 modifica una risorsa che S1 legge e S1 precede S2 in esecuzione. Quello che segue è un esempio di antidependence (WAR: Write After Read): ${\ displaystyle S1 \ \ delta ^ {a} \ S2}$

S1       x := y + c
S2       y := 10

Qui, S2 imposta il valore di y ma S1 legge un valore precedente di y .

Dipendenza dall'output

Un'istruzione S2 viene emessa dipendente da S1 (scritta ) se e solo se S1 e S2 modificano la stessa risorsa e S1 precede S2 in esecuzione. Di seguito è riportato un esempio di dipendenza dell'uscita (WAW: Write After Write): ${\ displaystyle S1 \ \ delta ^ {o} \ S2}$

S1       x := 10
S2       x := 20

Qui, S2 e S1 impostano entrambi la variabile x .

Dipendenza dall'input

Un'istruzione S2 è input dipendente da S1 (scritto ) se e solo se S1 e S2 leggono la stessa risorsa e S1 precede S2 in esecuzione. Di seguito è riportato un esempio di dipendenza dall'input (RAR: Read-After-Read): ${\ displaystyle S1 \ \ delta ^ {i} \ S2}$

S1       y := x + 3
S2       z := x + 5

Qui, S2 e S1 accedono entrambi alla variabile x . Questa dipendenza non proibisce il riordino.

Dipendenze del ciclo

Il problema del calcolo delle dipendenze all'interno dei cicli, che è un problema significativo e non banale, viene affrontato dall'analisi della dipendenza dai cicli , che estende la struttura delle dipendenze qui fornita.

Guarda anche

• Analisi del programma (informatica)
• Parallelizzazione automatica
• Vettorizzazione automatica
• Analisi della dipendenza dal loop
• Quadri a supporto del modello poliedrico
• Hazard (architettura del computer)
• Programma affettatura
• Eliminazione del codice guasto

Ulteriore lettura

• Cooper, Keith D .; Torczon, Linda. (2005). Progettazione di un compilatore . Morgan Kaufmann. ISBN   1-55860-698-X .
• Kennedy, Ken; Allen, Randy. (2001). Ottimizzazione dei compilatori per le architetture moderne: un approccio basato sulla dipendenza . Morgan Kaufmann. ISBN   1-55860-286-0 .
• Muchnick, Steven S. (1997). Progettazione e implementazione avanzate del compilatore . Morgan Kaufmann. ISBN   1-55860-320-4 .