Data Flow Analysis

Static Analysis: Control Flow Graph

1. Ogni nodo del CFG rappresenta un istruzione.

2. Variabili ed argomenti di funzioni vengono trattati allo stesso modo, come simboli temporanei.

3. Un arco $p \rightarrow q$ può essere eseguito subito dopo $q$. In questo caso $p$ è il predecessore di $q$.

4. Il punto di ingresso non ha predecessori, è chiamato nodo iniziale.

5. Il punto di uscita (return) non ha successori, è chiamato nodo finale.

6. Istruzioni non condizionali hanno al più un successore, mentre le istruzioni condizionali ne hanno due (punti di biforcazione). Un nodo con due o più predecessori è chiamato punto di confluenza.

7. Il CFG può essere visto come un FSA il cui alfabeto di terminali è l'insieme delle istruzioni $I$, ed il linguaggio delle stringhe generate da uno specifico CFG è l'insieme dei percorsi dallo stato iniziale allo stato finale.

$\text{Def}$, $\text{Use}$ sets

Un assegnamento di una variabile è chiamato definizione, mentre un occorrenza all'interno di un espressione viene chiamata uso.

Ogni nodo $p$ del CFG ha due insiemi di variabili: $\operatorname{def}(p)$ e $u\operatorname{use}(p)$. Ad esempio, se il nodo contiene la seguente istruzione:

$p : a := a \oplus b$

I suoi insiemi di definizioni ed utilizzi saranno:

$$\operatorname{def}(p) = \{a\} \\ \operatorname{use}(p) = \{a, b\}$$

Esempio di CFG con usi e definizioni

Definiamo l'insieme delle definizioni e l'insieme degli utilizzi di una generica variabile $a$ come: $D(a) \subseteq I$ e $U(a) \subseteq I$, ad esempio $D(a)=\{1,4\}$ e $U(a)=\{2,5\}$ nell'esempio sottostante:

Esempio di CFG con insiemi di usi e definizioni

Liveness Analysis: Data Flow Equations

Possibili utilizzi di liveness analysis:

• Useless Definitions: Eliminazioni di definizioni di variabili che non vengono mai usate

• Common Subexpressions: Se un espressione è già stata computata, può essere memorizzata in un temporary e riutilizzata in seguito. Simile a liveness analysis, ma non considera le singole variabili ma le combinazioni di essere nelle espressioni.

• Constant Folding: La computazione di espressioni con operandi constanti può essere effettuata a compile time.

• Constant Propagation: Simile a constant folding, ma se una temporary è costante le sue occorrenze succesive sono rimpiazzate con tale costante.

Arc Liveness

Prendiamo in considerazione un CFG e un arco $p \rightarrow q_{1}$. Una variabile è live sull'arco se $\exists$ un percorso $p \rightarrow q_{1} \rightarrow \ldots \rightarrow q_{n}$, con $n \geq 1$, che raggiunge $q_{n}$ e tale che:

1. $a \in \operatorname{use} \left(q_{n}\right)$,

2. Nessuno dei nodi $q_{j}$ sul percorso $p \rightarrow q_{1} \rightarrow \ldots q_{j} \rightarrow \ldots \rightarrow q_{n}$, ad eccezione di $p$ e $q_{n}$, contengono una definizione di $a$.

Idea: controllo bottom-up che alcune definizioni siano live in un percorso specifico del CFG. Con liveness si fa riferimento alla persistenza di uno specifico assegnamento di una variabile in una certa sequenza di istruzioni.

Note

• $q_{n}$ può coincidere con $p$.

• Se $p$ ha due successori, $a$ è live all'uscita di $p$ se è live su uno dei due archi.

• $a$ è live all'ingresso di $p$ se è live su tutti i vertici che entrano in $p$.

• Il fatto che $a$ sia live all'uscita di $p$ non implica che $a \in \operatorname{def}(p)$.

Liveness Property

La liveness property di $a$ all'uscita di un nodo $p$ è definita dalla seguente condizione:

Nel linguaggio $L(A)$ esiste una stringa (un percorso) composta da:

• Un generico percorso dal nodo iniziale

• $p$

• Un generico percorso in cui $a$ non è mai definita: $v \cap D(a) = 0$

• Un nodo $q$ che utilizza $a$: $a \in \operatorname{use} \left(q\right)$

• Un generico percorso fino al nodo finale

L'insieme di tutte le stringhe che rispettano questa condizione formano un linguaggio regolare. Questa strategia non è molto efficiente, esiste un metodo più pratico.

Data Flow Equations

Sistema di equazioni tali per cui per ogni nodo $p$ abbiamo:

1. Un equazione che correla le variabili live all'ingresso e live all'uscita di esso.

2. Un equazione che correla le variabili live all'uscita di $p$ con quelle live all'ingresso dei suoi immediate succesors.

Siano $\operatorname{live}{ }_{i n}(p)$ and $\operatorname{live}{ }_{\text {out }}(p)$ gli insiemi di variabili live all'ingresso e all'uscita di $p$, e $\operatorname{suc}(p), \operatorname{pred}(p)$ gli immediate successors e immediate predecessors di $p$:

Per un nodo finale $p$ :

$$\text { live }_{\text {out }}(p)=\emptyset$$

Per ogni altro nodo $p$ :

$$\begin{array}{rll} \operatorname{live}_{i n}(p)= & \text { use }(p) \cup\left(\text { live }_{\text {out }}(p) \backslash \operatorname{def}(p)\right) \\ \operatorname{live}_{\text {out }}(p)= & \bigsqcup_{\forall q \in \operatorname{succ}(p)} \text { live }_{\text {in }}(q) \end{array}$$

1. Equazione 1: nessuna variabile è live all'uscita del programma

2. Equazione 2: una variabile è live all'ingresso di $p$ se è utilizzata in $p$ o se è live all'uscita di $p$ e non è definita in esso.

3. Equazione 3: L'insieme delle variabili live all'uscita di $p$ è l'unione di tutte le variabili live all'ingresso dei successori di $p$.

Fixed Point Solution

Il sistema può essere risolto iterativamente, partendo dall'insieme vuoto all'iterazione iniziale ($i = 0$):

$$\forall p: \operatorname{live}_{i n}(p)=\emptyset ; \operatorname{live}_{\text {out }}(p)=\emptyset$$

I valori sono ricavati sostituendo le variabili sconosciute con gli insiemi vuoti, ottenendo una nuova iterazione. La soluzione è ricavata quando due iterazioni successive convergono (i.e. sono uguali).

Proprietà delle Data Flow Equations, Dimostrazione di terminazione

1. Cardinalità limitata: Sia $\operatorname{live}_{i n}(p)$ che $\operatorname{live}_{out}(p)$ hanno una cardinalità limitata, il cui limite superiore è la cardinalità dell'insieme delle variabili del programma. È importante fare in modo che questa proprietà sia rispettata quando gli insiemi delle proprietà vengono definiti.

2. Monotonicità: Non rimuoviamo mai variabili da un'approssimazione precedente, cioè non rimuoviamo mai una variabile dal'insieme corrente. Nello specifico la seconda equazione ($\operatorname{live}_{i n}(p)= \text { use }(p) \cup\left(\text { live }_{\text {out }}(p) \backslash \operatorname{def}(p)\right)$) Non deve mai rimuovere elementi dall'insieme.

3. Terminazione: Proprietà strutturale dell'algoritmo, se un iterazione non modifica il risultato ottenuto all'iterazione precedente, l'algoritmo si ferma.

Di conseguenza l'algoritmo può aggiungere al massimo tutte le variabili a tutti i live sets, e poi deve terminare dal momento che la proprietà di monotonicità gli impedisce di far ripartire il ciclo da un'altra soluzione.

Nota: questa dimostrazione è chiesta quasi sempre all'esame.

Esempio

Esempio di Data Flow Equations

Liveness Analysis, iterazioni dell'algoritmo

Time Complexity: Worst Case Analysis

for each $n$ $\begin{array}{ll}\operatorname{in}(n) \leftarrow \emptyset ; \quad & \text { out }(n) \leftarrow \emptyset ; \quad-\text { initialization } \\ \text { for each } n & \\ & \operatorname{in}^{\prime}(n) \leftarrow \operatorname{in}(n) ; \text { out }(n) \leftarrow \operatorname{out}(n) \\ & \operatorname{in}(n) \leftarrow \operatorname{cose}(n) \cup(\operatorname{out}(n) \backslash \operatorname{def}(n)) \\ & \operatorname{out}(n) \leftarrow \bigsqcup_{\forall q \in \operatorname{succ}(p)} \operatorname{in}(q) \\ \forall n: \operatorname{in}^{\prime}(n)= & \operatorname{in}(n) \wedge \operatorname{out}^{\prime}(n)=\operatorname{out}(n)\end{array}$

1. Ogni $\cup$ sugli insiemi live-in o live-out -> $O(N)$

2. Il ciclo interno calcola un numero costante di unioni per nodo -> $O(k)$

3. Ci sono $O(N)$ nodi -> il ciclo for ha complessità $O\left(N^{2}\right)$

4. Ogni iterazione deve aggiungere qualche elemento agli insiemi, ma ogn insieme ha cardinalità con limite superiore $N$. La somma delle cardinalità ha limite superiore $2N^2$ -> il loop può essere eseguito al più $O(N^2)$ volte.

Complessità totale del caso pessimo: $O\left(N^{4}\right)$.

Rappresentazione in memoria dei $\text{in}$, $\text{out}$ sets

1. Bit Vectors: array di bits in cui ogni bit rappresenta un elemento. Dato $N$, servono $\frac{N}{\text{wordsize}}$ words per rappresentare un insieme. Se $N$ è relativamente fissato, la complessità per effettuare l'unione diventa costante.

2. Linked lists: elementi rappresentati da una linked list. In questo caso il costo dell'unione è proporzionale ad $N$, e tale operazione è effettuata unendo le due liste senza elementi ripetuti. Non sono quasi mai più veloci dei bit vectors.

Quando i set sono sparsi è preferibile il secondo caso, altrimenti il primo.

Reaching Definitions

Definizioni ambigue e non ambigue

Definizione di una variabile che raggiunge (reaching) un certo punto nel programma. Tipologia di analisi collegata a SSA in quanto il contenuto delle $\phi$ functions sono le definizioni delle variabili che raggiungono un certo nodo $p$.

L'istruzione $p : a := a \oplus b$ definisce $a$. Denotiamola come $a_p$.

• Una definizione ambigua è una definizione della variabile $a$ che potrebbe non assegnare un valore ad essa.

• Insieme delle definizioni di $a$ nel programma: $D(a)$. Una definizione certa (o non ambigua) di $a$ in un istruzione $q$, chiamiamola $a_q$, è una definizione che raggiunge l'ingresso di un istruzione $p$ (che può coincidere con $q$) se esiste nel CFG un percorso da $q$ a $p$ che non attraversa un nodo in cui $a$ viene ridefinita, e di conseguenza $p$ userà il valore $a_q$.

$\text{gen}$, $\text{kill}$ sets

Dato uno generico nodo $p$ definiamo:

• $\operatorname{gen}(p) = \{ a_p \}$, contiene cioè le variabili definite da $p$.

• $\operatorname{kill}(p) = \operatorname{D}(a) \backslash \{ a_p \}$. cioè l'insieme di tutte le variabili ridefinite da $p$, cioè variabili che sono sia definite da $p$, sia definite da almeno un altro nodo, chiamamolo $q$, tale per cui $p \neq q$.

Più formalmente, dato $I$, l'insieme delle istruzioni del programma, consideriamo un istruzione $p$ che definisce una variabile (i.e. produce $a_p$) e sovrascrive (kills) ogni altra definizione di $a_q$, $q \neq p$:

$$\begin{gathered} \operatorname{gen}(p)=\left\{a_{p}\right\} \\ \left\{\begin{array}{rlr} \operatorname{kill}(p)= & \left\{a_{q} \mid q \in I \wedge q \neq p\right. & \\ & \wedge a \in \operatorname{def}(q) \wedge a \in \operatorname{def}(p)\}, & \text { if } \operatorname{def}(p) \neq \emptyset \\ \operatorname{kill}(p) = & \emptyset, & \text { if } \operatorname{def}(p)=\emptyset \end{array}\right. \end{gathered}$$

Computazione delle $\text{in}$, $\text{out}$ equations

Gli insiemi delle definizioni che raggiungono l'ingresso e l'uscita di $p$ sono chiamati rispettivamente $\operatorname{in}$ e $\operatorname{out}$. Per un generico nodo $p$ definiamo $\text{in}(p)$ come l'unione degli insiemi $\text{out}(q)$ $\forall q$ predecessore di $p$, e $\text{out}(p)$ come l'unione tra l'insieme delle variabili definite da $p$ e l'insieme risultante dalla differenza tra $\text{in}(p)$ e $\text{kill}(p)$.

• Per il nodo iniziale $1:$

$$\operatorname{in}(1)=\emptyset$$

• Per ogni altro nodo $p$ :

$$\begin{aligned} \operatorname{out}(p) &=\operatorname{gen}(p) \cup(\operatorname{in}(p) \backslash \operatorname{kill}(p)) \\ \operatorname{in}(p) &=\bigsqcup_{\forall q \in \operatorname{pred}(p)} \operatorname{out}(q) \end{aligned}$$

Dove $\operatorname{pred}(p)$ definisce i predecessori immediati di $p$ nel CFG. Inoltre:

• Da $\operatorname{in}(1)=\emptyset$ notiamo che gli argomenti del programma non sono tenuti in cosiderazione.

• Per quanto riguarda la liveness, le equazioni possono essere risolte iterativamente terminando all'iterazione in cui tutti gli insiemi delle incognite sono vuoti, con l'eccezione di $\operatorname{in}(1)$, che è sempre vuoto.