DataFlow Analysis cheatsheet

Una definizione \(D\) raggiunge un punto \(P\) se esiste un percorso da \(D\) a \(P\) tale per cui \(D\) non è uccisa (sovrascritta). In forma SSA, la reaching definition di un'istruzione è l'istruzione stessa, semplicemente rappresentata in un'altro modo.

• Definizione localmente disponibile: ultima definizione di una variabile all'interno di un BB.

Un'espressione \(x \otimes y\) è available in un punto \(P\) se viene valutata in ogni percorso che da entry porta a P. Quando durante il flow di un programma viene richiesta della computazione per calcolare un valore, ci si chiede se quella particolare espressione è già stata calcolata in passato (con gli stessi operandi ovviamente). In tal caso, si possono evitare calcoli ridondanti.

Una variabile \(V\) è alive in un punto \(P\) se esiste almeno un percorso che da \(P\) porta a exit che usa il valore di quella variabile. (La variabile stessa se si considera la forma SSA). Altrimenti la variabile viene definita dead.

Un blocco \(B\) domina un blocco \(A\) se partendo da entry per arrivare ad \(A\) si passa necessariamente per \(B\).

Una espressione \(E\) è very busy in un punto \(P\) se \(E\) viene valutata in ogni percorso a partire da \(P\) prima che uno dei suoi operandi venga ridefinito. Il concetto è che se un'espressione è very busy in un certo punto \(P\), nel caso in cui ci siano più punti in cui essa viene valutata, si possono "accorpare" le varie valutazioni dell'espressione in una unica nel punto \(P\). Questo passo potrebbe essere propedeutico per la realizzazione di ulteriori ottimizzazioni.