# SYK 4

## Zadanie 1
Przypomnijmy równania z zadania 8:

$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = AE_{exit}(1)$
$AE_{entry}(3) = AE_{exit}(2)$
$AE_{entry}(4) = AE_{exit}(3) \cap AE_{exit}(8)$
$AE_{entry}(5) = AE_{exit}(4)$
$AE_{entry}(6) = AE_{exit}(5)$
$AE_{entry}(7) = AE_{exit}(6)$
$AE_{entry}(8) = AE_{exit}(7)$
$AE_{entry}(9) = AE_{exit}(4)$

$AE_{exit}(1) = AE_{entry}(1)$
$AE_{exit}(2) = AE_{entry}(2)$
$AE_{exit}(3) = AE_{entry}(3)$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \cup \{x+y\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus \{x+y\}$
$AE_{exit}(7) = AE_{entry}(7) \setminus \{x+y\}$
$AE_{exit}(8) = AE_{entry}(8) \setminus \{i+1\}$
$AE_{exit}(9) = AE_{entry}(9)$

### Stan początkowy (największy punkt stały)
$AE_{entry}(1) = ... = AE_{entry}(9) = \{x+y, i+1\}$
$AE_{exit}(1) = ... = AE_{exit}(9) = \{x+y, i+1\}$

### Iteracja 1
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \{x+y, i+1\}$
$AE_{entry}(3) = \{x+y, i+1\}$
$AE_{entry}(4) = \{x+y, i+1\}$
$AE_{entry}(5) = \{x+y, i+1\}$
$AE_{entry}(6) = \{x+y, i+1\}$
$AE_{entry}(7) = \{x+y, i+1\}$
$AE_{entry}(8) = \{x+y, i+1\}$
$AE_{entry}(9) = \{x+y, i+1\}$

$AE_{exit}(1) = \{x+y, i+1\}$
$AE_{exit}(2) = \{x+y, i+1\}$
$AE_{exit}(3) = \{x+y, i+1\}$
$AE_{exit}(4) = \{x+y, i+1\}$
$AE_{exit}(5) = \{x+y, i+1\}$
$AE_{exit}(6) = \{i+1\}$
$AE_{exit}(7) = \{i+1\}$
$AE_{exit}(8) = \{x+y\}$
$AE_{exit}(9) = \{x+y, i+1\}$

### Iteracja 2
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \{x+y, i+1\}$
$AE_{entry}(3) = \{x+y, i+1\}$
$AE_{entry}(4) = \{x+y\}$
$AE_{entry}(5) = \{x+y, i+1\}$
$AE_{entry}(6) = \{x+y, i+1\}$
$AE_{entry}(7) = \{i+1\}$
$AE_{entry}(8) = \{i+1\}$
$AE_{entry}(9) = \{x+y, i+1\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \{x+y, i+1\}$
$AE_{exit}(3) = \{x+y, i+1\}$
$AE_{exit}(4) = \{x+y, i+1\}$
$AE_{exit}(5) = \{x+y, i+1\}$
$AE_{exit}(6) = \{i+1\}$
$AE_{exit}(7) = \{i+1\}$
$AE_{exit}(8) = \{x+y\}$
$AE_{exit}(9) = \{x+y, i+1\}$

### Iteracja 3
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \{x+y, i+1\}$
$AE_{entry}(4) = \{x+y\}$
$AE_{entry}(5) = \{x+y, i+1\}$
$AE_{entry}(6) = \{x+y, i+1\}$
$AE_{entry}(7) = \{i+1\}$
$AE_{entry}(8) = \{i+1\}$
$AE_{entry}(9) = \{x+y, i+1\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \{x+y, i+1\}$
$AE_{exit}(3) = \{x+y, i+1\}$
$AE_{exit}(4) = \{x+y\}$
$AE_{exit}(5) = \{x+y, i+1\}$
$AE_{exit}(6) = \{i+1\}$
$AE_{exit}(7) = \{i+1\}$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \{x+y, i+1\}$

### Iteracja 4
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \{x+y, i+1\}$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \{x+y\}$
$AE_{entry}(6) = \{x+y, i+1\}$
$AE_{entry}(7) = \{i+1\}$
$AE_{entry}(8) = \{i+1\}$
$AE_{entry}(9) = \{x+y\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \{x+y, i+1\}$
$AE_{exit}(4) = \{x+y\}$
$AE_{exit}(5) = \{x+y, i+1\}$
$AE_{exit}(6) = \{i+1\}$
$AE_{exit}(7) = \{i+1\}$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \{x+y, i+1\}$

### Iteracja 5
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \{x+y, i+1\}$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \{x+y\}$
$AE_{entry}(6) = \{x+y, i+1\}$
$AE_{entry}(7) = \{i+1\}$
$AE_{entry}(8) = \{i+1\}$
$AE_{entry}(9) = \{x+y\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \{x+y, i+1\}$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{x+y\}$
$AE_{exit}(6) = \{i+1\}$
$AE_{exit}(7) = \{i+1\}$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \{x+y\}$

### Iteracja 6
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \emptyset$
$AE_{entry}(6) = \{x+y\}$
$AE_{entry}(7) = \{i+1\}$
$AE_{entry}(8) = \{i+1\}$
$AE_{entry}(9) = \emptyset$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \{x+y, i+1\}$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{x+y\}$
$AE_{exit}(6) = \{i+1\}$
$AE_{exit}(7) = \{i+1\}$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Iteracja 7
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \emptyset$
$AE_{entry}(6) = \{x+y\}$
$AE_{entry}(7) = \{i+1\}$
$AE_{entry}(8) = \{i+1\}$
$AE_{entry}(9) = \emptyset$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{x+y\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \{i+1\}$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Iteracja 8
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \emptyset$
$AE_{entry}(6) = \{x+y\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \{i+1\}$
$AE_{entry}(9) = \emptyset$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{x+y\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Iteracja 9
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \emptyset$
$AE_{entry}(6) = \{x+y\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \emptyset$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{x+y\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

Po kolejnej iteracji nie doszło do zmian - koniec algorytmu

## Zadanie 1 wersja skrócona
Przypomnijmy równania z zadania 8:

$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = AE_{exit}(1)$
$AE_{entry}(3) = AE_{exit}(2)$
$AE_{entry}(4) = AE_{exit}(3) \cap AE_{exit}(8)$
$AE_{entry}(5) = AE_{exit}(4)$
$AE_{entry}(6) = AE_{exit}(5)$
$AE_{entry}(7) = AE_{exit}(6)$
$AE_{entry}(8) = AE_{exit}(7)$
$AE_{entry}(9) = AE_{exit}(4)$

$AE_{exit}(1) = AE_{entry}(1)$
$AE_{exit}(2) = AE_{entry}(2)$
$AE_{exit}(3) = AE_{entry}(3)$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \cup \{x+y\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus \{x+y\}$
$AE_{exit}(7) = AE_{entry}(7) \setminus \{x+y\}$
$AE_{exit}(8) = AE_{entry}(8) \setminus \{i+1\}$
$AE_{exit}(9) = AE_{entry}(9)$

### Na początku
$AE_{entry}(1) = ... = AE_{entry}(9) = \{x+y, i+1\}$
$AE_{exit}(1) = ... = AE_{exit}(9) = \{x+y, i+1\}$

### W kolejnych iteracjach algorytmu stałopunktowego
$AE_{exit}(1) = AE_{entry}(1)=\emptyset$
$AE_{entry}(2) = AE_{exit}(1)=\emptyset$
$AE_{exit}(2) = AE_{entry}(2)=\emptyset$
$AE_{entry}(3) = AE_{exit}(2)=\emptyset$
$AE_{exit}(3) = AE_{entry}(3)=\emptyset$
$AE_{entry}(4) = AE_{exit}(3) \cap AE_{exit}(8)=\emptyset$
$AE_{exit}(4) = AE_{entry}(4)=\emptyset$
$AE_{entry}(5) = AE_{exit}(4)=\emptyset$
$AE_{exit}(5) = AE_{entry}(5) \cup \{x+y\}=\{x+y\}$
$AE_{entry}(6) = AE_{exit}(5)=\{x+y\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus \{x+y\}=\emptyset$
$AE_{entry}(7) = AE_{exit}(6)=\emptyset$
$AE_{exit}(7) = AE_{entry}(7) \setminus \{x+y\}=\emptyset$
$AE_{entry}(8) = AE_{exit}(7)=\emptyset$
$AE_{exit}(8) = AE_{entry}(8) \setminus \{i+1\}=\emptyset$
$AE_{entry}(9) = AE_{exit}(4)=\emptyset$
$AE_{exit}(9) = AE_{entry}(9)=\emptyset$

### Ostatecznie
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \emptyset$
$AE_{entry}(6) = \{x+y\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \emptyset$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{x+y\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

## Zadanie 2

Elementami zbiorów analizy są pary [EXPR, VAR], gdzie EXPR to wyrażenie dostępne w zmiennej VAR.

$kill_{AE}([ x:= a]^{l}) = \{<x, a'> | a' \in AExp_{*}\} \cup \{<l, a> | x \in a\}$
$kill_{AE}([skip]^{l}) = \emptyset$, nie ma przypisania - nic się nie zmienia
$kill_{AE}([b]^{l}) = \emptyset$, nie ma przypisania - nic się nie zmienia

$gen_{AE}([ x:= a]^{l}) = \{<x, a>\} \quad jeżeli \quad x \notin a \quad wpp. \{\}$
$gen_{AE}([skip]^{l}) = \emptyset$, nie ma przypisania - nic się nie zmienia
$gen_{AE}([b]^{l}) = \emptyset$, nie ma przypisania - nic się nie zmienia

Jest to analiza typu "MUST". Wynika to z faktu iż działamy analogicznie do klasycznej analizy 'Available Variables' (w szczególności widzimy że w definicji mamy zapis 'na WSZYSTKICH ścieżkach')

Jest to analiza typu "FORWARD", ponieważ analizujemy jakie wyrażenia zostały już WCZEŚNIEJ obliczone i przypisane do zmiennej (w szczególności bez późniejszych zmian itp.)

## Zadanie 3

Bazujemy na klasycznych analizach zmiennych dostępnych. Wystarczająca zmianą jest nowe zdefiniowanie $kill$ i $gen$:

Skoro analiza jest typu MUST to algorytm stałopunktowy na starcie "wypełniamy" zbiorami pełnymi.

Korzystamy z definicji KILL/GEN takich jak w z2. Przypomnijmy:

$kill_{AE}([ x:= a]^{l}) = \{<x, a'> | a' \in AExp_{*}\} \cup \{<l, a> | x \in a\}$
$kill_{AE}([skip]^{l}) = \emptyset$
$kill_{AE}([b]^{l}) = \emptyset$

$gen_{AE}([ x:= a]^{l}) = \{<x, a>\} \quad jeżeli \quad x \notin a \quad wpp. \emptyset$
$gen_{AE}([skip]^{l}) = \emptyset$
$gen_{AE}([b]^{l}) = \emptyset$

Bazujemy na równaniach:
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = AE_{exit}(1)$
$AE_{entry}(3) = AE_{exit}(2)$
$AE_{entry}(4) = AE_{exit}(3) \cap AE_{exit}(8)$
$AE_{entry}(5) = AE_{exit}(4)$
$AE_{entry}(6) = AE_{exit}(5)$
$AE_{entry}(7) = AE_{exit}(6)$
$AE_{entry}(8) = AE_{exit}(7)$
$AE_{entry}(9) = AE_{exit}(4)$

$AE_{exit}(1) = AE_{entry}(1) \setminus (\{<x, a'> | a' \in AExp_{*}\} \cup \{<l, a> | x \in a\})$
$AE_{exit}(2) = AE_{entry}(2) \setminus (\{<y, a'> | a' \in AExp_{*}\} \cup \{<l, a> | y \in a\})$
$AE_{exit}(3) = AE_{entry}(3) \setminus (\{<i, a'> | a' \in AExp_{*}\} \cup \{<i, a> | i \in a\})$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \setminus (\{<t, a'> | a' \in AExp_{*}\} \cup \{<l, a> | t \in a\}) \cup \{<t, x+y>\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus (\{<x, a'> | a' \in AExp_{*}\} \cup \{<l, a> | x \in a\})$
$AE_{exit}(7) = AE_{entry}(7) \setminus (\{<y, a'> | a' \in AExp_{*}\} \cup \{<l, a> | y \in a\})$
$AE_{exit}(8) = AE_{entry}(8) \setminus (\{<i, a'> | a' \in AExp_{*}\} \cup \{<l, a> | i \in a\})$
$AE_{exit}(9) = AE_{entry}(9) \setminus (\{<y, a'> | a' \in AExp_{*}\} \cup \{<l, a> | y \in a\})$

Przypisujemy jedynie do zmiennej t wartość x+y
oraz do zmiennej i wartość i+1

Które można (dla naszego zadania przekształcić do postaci):
$AE_{exit}(1) = AE_{entry}(1) \setminus \{<t, x+y>\}$
$AE_{exit}(2) = AE_{entry}(2) \setminus \{<t, x+y>\}$
$AE_{exit}(3) = AE_{entry}(3) \setminus \{<i, i+1>\}$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \setminus \{<t, x+y>\} \cup \{<t, x+y>\} = AE_{entry}(5) \cup \{<t, x+y>\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus \{<t, x+y>\}$
$AE_{exit}(7) = AE_{entry}(7) \setminus \{<t, x+y>\}$
$AE_{exit}(8) = AE_{entry}(8) \setminus \{<i, i+1>\} = AE_{entry}(8) \setminus \{<i, i+1>\}$
$AE_{exit}(9) = AE_{entry}(9) \setminus \{<t, x+y>\}$

Skracając:
$AE_{exit}(1) = AE_{entry}(1) \setminus \{<t, x+y>\}$
$AE_{exit}(2) = AE_{entry}(2) \setminus \{<t, x+y>\}$
$AE_{exit}(3) = AE_{entry}(3) \setminus \{<i, i+1>\}$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \cup \{<t, x+y>\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus \{<t, x+y>\}$
$AE_{exit}(7) = AE_{entry}(7) \setminus \{<t, x+y>\}$
$AE_{exit}(8) = AE_{entry}(8) \setminus \{<i, i+1>\}$
$AE_{exit}(9) = AE_{entry}(9) \setminus \{<t, x+y>\}$

Nigdy nie dodajemy <i, i+1> wieć można skrócić powyższe:

$AE_{exit}(1) = AE_{entry}(1) \setminus \{<t, x+y>\}$
$AE_{exit}(2) = AE_{entry}(2) \setminus \{<t, x+y>\}$
$AE_{exit}(3) = AE_{entry}(3)$
$AE_{exit}(4) = AE_{entry}(4)$
$AE_{exit}(5) = AE_{entry}(5) \cup \{<t, x+y>\}$
$AE_{exit}(6) = AE_{entry}(6) \setminus \{<t, x+y>\}$
$AE_{exit}(7) = AE_{entry}(7) \setminus \{<t, x+y>\}$
$AE_{exit}(8) = AE_{entry}(8)$
$AE_{exit}(9) = AE_{entry}(9) \setminus \{<t, x+y>\}$

Przepiszmy również:
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = AE_{exit}(1)$
$AE_{entry}(3) = AE_{exit}(2)$
$AE_{entry}(4) = AE_{exit}(3) \cap AE_{exit}(8)$
$AE_{entry}(5) = AE_{exit}(4)$
$AE_{entry}(6) = AE_{exit}(5)$
$AE_{entry}(7) = AE_{exit}(6)$
$AE_{entry}(8) = AE_{exit}(7)$
$AE_{entry}(9) = AE_{exit}(4)$

### Etap 0
$AE_{entry}(1) = ... = AE_{entry}(9) = \{<t, x+y>\}$
$AE_{exit}(1) = ... = AE_{exit}(9) = \{<t, x+y>\}$

### Etap 1
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \{<t, x+y>\}$
$AE_{entry}(3) = \{<t, x+y>\}$
$AE_{entry}(4) = \{<t, x+y>\}$
$AE_{entry}(5) = \{<t, x+y>\}$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \{<t, x+y>\}$
$AE_{entry}(8) = \{<t, x+y>\}$
$AE_{entry}(9) = \{<t, x+y>\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \{<t, x+y>\}$
$AE_{exit}(4) = \{<t, x+y>\}$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \{<t, x+y>\}$
$AE_{exit}(9) = \emptyset$

### Etap 2
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \{<t, x+y>\}$
$AE_{entry}(5) = \{<t, x+y>\}$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \{<t, x+y>\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \{<t, x+y>\}$
$AE_{exit}(4) = \{<t, x+y>\}$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \{<t, x+y>\}$
$AE_{exit}(9) = \emptyset$

### Etap 3
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \{<t, x+y>\}$
$AE_{entry}(5) = \{<t, x+y>\}$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \{<t, x+y>\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \{<t, x+y>\}$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Etap 4
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \{<t, x+y>\}$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \{<t, x+y>\}$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Etap 5
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \emptyset$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \emptyset$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Etap 6 (bez zmian)
$AE_{entry}(1) = \emptyset$
$AE_{entry}(2) = \emptyset$
$AE_{entry}(3) = \emptyset$
$AE_{entry}(4) = \emptyset$
$AE_{entry}(5) = \emptyset$
$AE_{entry}(6) = \{<t, x+y>\}$
$AE_{entry}(7) = \emptyset$
$AE_{entry}(8) = \emptyset$
$AE_{entry}(9) = \emptyset$

$AE_{exit}(1) = \emptyset$
$AE_{exit}(2) = \emptyset$
$AE_{exit}(3) = \emptyset$
$AE_{exit}(4) = \emptyset$
$AE_{exit}(5) = \{<t, x+y>\}$
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

## Zadanie 4

Zmienna jest żywa na wyjściu z danej etykiety, jeśli istnieje od niej ścieżka do jej użycia, które nie jest redefinicją. Zmienna jest zemdlona, jeśli jest martwa lub jeśli jest używana
wyłącznie do obliczenia wartości zmiennych zemdlonych. W przeciwnym przypadku zmienną nazwiemy silnie żywą.

Bazujemy na standardowych równaniach, dziedziną zbiorów są zmienne występujące w programie



Musimy jedynie inaczej zdefiniować funkcję generującą w przypadku przypisania wartości do zmiennej

$gen_{lv}([x := a]) = \{\\ \quad FV(a),\, jeśli \; x \in LV_{\bullet}(l) \\ \quad \emptyset,\, w\,przeciwnym\,wypadku \\\}$

Nie generujemy zmiennych silnie żywych, jeśli zmienna x jest zemdlona

Typ analizy:
- backwards, ponieważ to, czy zmienna jest silnie żywa, zależy od przyszłych bloków
- may, ponieważ zmienna silnie żywa nie musi być silnie żywa na wszystkich ścieżkach wychodzących z danego bloku, wystarczy z jednego

## Zadanie 5
a) 1. 𝑤ℎ𝑖𝑙𝑒 (𝑏) { ... }

$L:\ if\ B==0\ goto\ E$
$\qquad ...$
$\qquad goto\ L$
$E:$

---
b) 2. 𝑓𝑜𝑟 (𝑖 = 0; 𝑖 < 𝑛; 𝑖 ++) { ... }

$\qquad i:=0$
$L:\ \ if\ i>=n\ goto\ E$
$\qquad ...$
$\qquad i:=i+1$
$\qquad goto\ L$
$E:$

---
c) 3. 𝑑𝑜 {...} 𝑤ℎ𝑖𝑙𝑒 (𝑏)

$L:\ \ ...$
$\qquad...$
$if\ b\;{!=}\;0\ goto\ L$

## Zadanie 6
$t1:=a*a$
$t1:=t1*a$
$x:=t1$

$t1:=4*a$
$t1:=t1*a$
$t1:=t1*b$
$x:=x+t1$

$t1:=4*a$
$t1:=t1*b$
$t1:=t1*b$
$x:=x+t1$

$t1:=b*b$
$t1:=t1*b$
$x:=x+t1$

---
$mem[4]:=a*a$
$mem[4]:=mem[4]*a$
$mem[0]:=mem[4]$

$mem[4]:=4*a$
$mem[4]:=mem[4]*a$
$mem[4]:=mem[4]*b$
$mem[0]:=mem[0]+mem[4]$

$mem[4]:=4*a$
$mem[4]:=mem[4]*b$
$mem[4]:=mem[4]*b$
$mem[0]:=mem[0]+mem[4]$

$mem[4]:=b*b$
$mem[4]:=mem[4]*b$
$x:=mem[0]+mem[4]$

## Zadanie 7
$\qquad i:=0$
$\qquad mxi:=n-1$
$L1:\ if\ i>=mxi\ goto\ E1$
$\qquad\ j:=0$
$\qquad\ mxj:=n1-i$
$\qquad\ L2:\ if\ j>=mxj\ goto\ E2$
$\qquad\qquad\ j1:=j+1$
$\qquad\qquad\ tmp:=t[j]$
$\qquad\qquad\ tmp1:=t[j1]$
$\qquad\qquad\ if\ tmp<=tmp1\ goto\ IE$
$\qquad\qquad\qquad\ t[j]=tmp1$
$\qquad\qquad\qquad\ t[j1]=tmp$
$\qquad IE:\ j:=j+1$
$\qquad\qquad\ goto\ L2$
$E2:\ i:=i+1$
$\qquad\ goto\ L1$
$E1:$