# Ćwiczenia 3, grupa cz. 14-16, 24. marca 2022

###### tags: `SYK21` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Kamil Banaś | | | | | | | | |
Mateusz Burdyna | | | | | | | | |
Dariusz Ciesielski | | | | | | | | |
Dawid Dudek | X | X | X | X | X | X | | |
Mikołaj Dworszczak | | | | | | | | |
Przemysław Grochal | | | | | | | | |
Adam Jarząbek | X | | | | | | | |
Anna Karykowska | X | X | X | X | X | | | |
Oleś Kulczewicz | | | | | | | | |
Pola Marciniak | X | X | X | X | X |==X==| | |
Mikołaj Mroziuk | | | | | | | | |
Marcelina Oset | | | | | | | | |
Natalia Piasta | X | ==X== | X | X | X | X | | |
Krzysztof Piekarczyk | X | X | | | | | | |
Marcin Płaza | X | X | | X | | | X | |
Paweł Richert | ==X== | X| X | X | X | | | |
Rafał Starypan | X | X | X | ==X== | X | X | X | |
Dawid Strojek | X | X | X | | X | | | |
Mateusz Suszek | X | X | | X | | | X | |
Wojciech Śniady | X | X | X | X | X | | | |
Volha Tsekalo | X | X | X | X | X | | | |
Yana Vashkevich | X | X | X | X | X | | | |
Konrad Woźniak | X | X | X | X | X | | | |
Natalia Czerep | | | | | | | | |
Joanna Stachowicz | X | X | X | | X | | ==X== | |
Marcelina Oset | x | x |==x==| x | x | x |x
:::

**Tutaj można do-deklarować zad. 9 z listy 2.:**
...

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1

:::success
Autor: Paweł Richert
:::


## Zadanie 2

:::success
Autor: Natalia Piasta
:::
Dla programu z poprzedniego zadania ułóż równania dla zbiorów $RD_∘(𝑙)$ oraz $RD_⦁(𝑙)$, dla 𝑙∈{1,..., 9}. Następnie sprawdź,że zbiory wyliczone w poprzednim zadaniu spełniają te równania.



## Zadanie 3

:::success
Autor: Konrad Woźniak
:::


$\#RD_{\circ}(1) = \{(x,?), (y,?), (z,?), (i,?), (t,?)\}$
$\#RD_{\bullet}(1) = RD_{\circ}(1) \setminus \{(x,?)\} \bigcup \{(x,1)\} =\{(x,1), (y,?), (z,?), (i,?), (t,?)\}$

$\#RD_{\circ}(2) = RD_{\bullet}(1)$
$\#RD_{\bullet}(2) = RD_{\circ}(2) \setminus \{(y,?)\} \bigcup \{(y,2)\} =\{(x,1), (y,2), (z,?), (i,?), (t,?)\}$

$\#RD_{\circ}(3) = RD_{\bullet}(2)$
$\#RD_{\bullet}(3) = RD_{\circ}(3) \setminus \{(i,?)\} \bigcup \{(i,3)\} =\{(x,1), (y,2), (z,?), (i,3), (t,?)\}$

$RD_{\circ}(4) = RD_{\bullet}(3) \bigcup RD_{\bullet}(8)$
$RD_{\bullet}(4) = RD_{\circ}(4) =\{(x,1), (y,2), (z,?), (i,3), (t,?)\}$

$RD_{\circ}(5) = RD_{\bullet}(4)$
$RD_{\bullet}(5) = RD_{\circ}(5) \setminus \{(t,?)\} \bigcup \{(t,5)\} =\{(x,1), (y,2), (z,?), (i,3), (t,5)\}$

$RD_{\circ}(6) = RD_{\bullet}(5)$
$RD_{\bullet}(6) = RD_{\circ}(6) \setminus \{(x,1)\} \bigcup \{(x,6)\} =\{(x,6), (y,2), (z,?), (i,3), (t,5)\}$

$RD_{\circ}(7) = RD_{\bullet}(6)$
$RD_{\bullet}(7) = RD_{\circ}(7) \setminus \{(y,2)\} \bigcup \{(y,7)\} =\{(x,6), (y,7), (z,?), (i,3), (t,5)\}$

$RD_{\circ}(8) = RD_{\bullet}(7)$
$\#RD_{\bullet}(8) = RD_{\circ}(8) \setminus \{(i,3)\} \bigcup \{(i,8)\} =\{(x,6), (y,7), (z,?), (i,8), (t,5)\}$

$RD_{\circ}(9) = RD_{\bullet}(4)$
$RD_{\bullet}(9) = RD_{\circ}(9) \setminus \{(y,2)\} \bigcup \{(y,9)\} =\{(x,1), (y,2), (z,?), (i,3), (t,?)\}$

$\#RD_{\circ}(4) = RD_{\bullet}(3) \bigcup RD_{\bullet}(8)$
$\#RD_{\bullet}(4) = RD_{\circ}(4) =\{(x,1), (y,2), (i,3), (t,?), (x,6), (y,7), (z,?), (i,8), (t,5)\}$

$\#RD_{\circ}(5) = RD_{\bullet}(4)$
$\#RD_{\bullet}(5) = RD_{\circ}(5) \setminus \{(t,?), (t,5)\} \bigcup \{(t,5)\} =\{(x,1), (y,2), (i,3), (x,6), (y,7), (z,?), (i,8), (t,5)\}$

$\#RD_{\circ}(6) = RD_{\bullet}(5)$
$\#RD_{\bullet}(6) = RD_{\circ}(6) \setminus \{(x,1), (x,6)\} \bigcup \{(x,6)\} =\{(y,2), (i,3), (x,6), (y,7), (z,?), (i,8), (t,5)\}$

$\#RD_{\circ}(7) = RD_{\bullet}(6)$
$\#RD_{\bullet}(7) = RD_{\circ}(7) \setminus \{(y,2), (y,7)\} \bigcup \{(y,7)\} =\{(i,3), (x,6), (y,7), (z,?), (i,8), (t,5)\}$

$\#RD_{\circ}(8) = RD_{\bullet}(7)$
$\#RD_{\bullet}(8) = RD_{\circ}(8) \setminus \{(i,3), (i,8)\} \bigcup \{(i,8)\} =\{(x,6), (y,7), (z,?), (i,8), (t,5)\}$

$\#RD_{\circ}(9) = RD_{\bullet}(4)$
$\#RD_{\bullet}(9) = RD_{\circ}(9) \setminus \{(y,2), (y,7)\} \bigcup \{(y,9)\} =\{(x,1), (i,3), (t,?), (x,6), (y,9), (z,?), (i,8), (t,5)\}$

$\#$ - wartość ostateczna

## Zadanie 4

:::success
Autor: Rafał Starypan
:::


$kill_{RD}([x:=0]^{1}) = \{(x,?),(x,1),(x,6)\}$
$kill_{RD}([y:=1]^{2}) = \{(y,?),(y,2),(y,7),(y,9)\}$
$kill_{RD}([i:=1]^{3}) = \{(i,?),(i,3),(i,8)\}$
$kill_{RD}([i<z]^{4}) = \emptyset$
$kill_{RD}([t:=x+y]^{5}) = \{(t,?)\}$
$kill_{RD}([x:=y]^{6}) = \{(x,?),(x,1),(x,6)\}$
$kill_{RD}([y:=t]^{7}) = \{(y,?),(y,2),(y,7),(y,9)\}$
$kill_{RD}([i:=i+1]^{8}) = \{(i,?),(i,3),(i,8)\}$
$kill_{RD}([y:=x]^{9}) = \{(y,?),(y,2),(y,7),(y,9)\}$

$gen_{RD}([x:=0]^{1}) = \{(x,1)\}$
$gen_{RD}([y:=1]^{2}) = \{(y,2)\}$
$gen_{RD}([i:=1]^{3}) = \{(i,3)\}$
$gen_{RD}([i<z]^{4}) = \emptyset$
$gen_{RD}([t:=x+y]^{5}) = \{(t,5)\}$
$gen_{RD}([x:=y]^{6}) = \{(x,6)\}$
$gen_{RD}([y:=t]^{7}) = \{(y,7)\}$
$gen_{RD}([i:=i+1]^{8}) = \{(i,8)\}$
$gen_{RD}([y:=x]^{9}) = \{(y,9)\}$

2) Analogicznie jak przy wykonaniu przypisania do zmiennej x:
$kill_{RD}([read(x)]^{l}) = \{(x,?)\} \cup \{(x, l') \,|\, B' jest \, przypisaniem\, lub\, wczytaniem\,do \, x\}$
$gen_{RD}([read(x)]^{l}) = \{(x,l)\}$

3) Algorytm wyliczający zbiory RD(l).


1. Ustawiam $RD_{exit}$ dla każdego wierzchołka (bloczka z instrukcją) na zbiór pusty.
2. Dodaję wszystkie wierzchołki do zbioru $Changed$ (zbiór wierzchołków dla których zbiory RD mogły ulec zmianie).
3. Dopóki $!Changed.empty()$:
a) wybieram wierzchołek $x$ ze zbioru $Changed$ i usuwam go z $Changed$
b) Ustawiam $RD_{entry}(x)$ na zbiór pusty
c) Przechodzę po wszystkich "przodkach" $x$ (wierzchołkach posiadających krawędź wychodzącą kończącą się w $x$) i uaktualniam $RD_{entry}(x)$ licząc sumę zbiorów.
d) Zapisuję pomocniczo starą wartość $RD_{exit}(x)$, aby móc porównać ją z nową.
e) Obliczam nową wartość $RD_{entry}(x)$ przy użyciu funkcji $kill$ i $gen$.
f) Jeżeli nowa wartość $RD_{entry}(x)$ różni się od starej:
aa) Dodaję wszystkie "dzieci" $x$ do zbioru $Changed$

## Zadanie 5

:::success
Autor: Anna Karykowska
:::




Program nigdy nie wejdzie do instrukcji 4, bo x na początku ustalamy jako 1 i to jest większe od 0. W takim razie nie potrzebujemy (y, 4) i nasze rozwiązanie nie jest optymalne.

## Zadanie 6

:::success
Autor: Marcelina Oset
:::

Zmienna jest **żywa** jeśli na wyjściu z etykiety istnieje ścieżka z tej etykiety do użycia tej zmiennej, która nie redefiniuje tej zmiennej.

Analiza żywych zmiennych określa dla każdego punktu w programie, które zmienne mogą być żywe na wyjściu z programu.


Algorytm:

$LV_{\bullet}(l)$ =
* $\emptyset$ dla $l \in final(S_{*})$
* $\Large\cup\normalsize\{LV_{\circ}(l')\ |\ (l', l) \in flow^{R}(S_{*})\}$ w.p.p.

$LV_{\circ}(l) = (LV_{\bullet}(l) \setminus kill_{LV}(B^l)) \cup gen_{LV}(B^l)$
gdzie $B^l \in blocks(S_{*})$

$kill_{LV}([x := a]^l) = {x}$
$kill_{LV}([skip]^l) = \emptyset$
$kill_{LV}([b]^l) = \emptyset$

$gen_{LV}([x := a]^l) = FV(a)$
$gen_{LV}([skip]^l) = \emptyset$
$gen_{LV}([b]^l) = FV(b)$
*FV(a) to jest zbiór wszystkich zmiennych występujących w wyrażeniu a*

Układ równań:

$LV_{\bullet}(9) = \emptyset$
$LV_{\circ}(9) = LV_{\bullet}(9) \setminus \{y\} \cup \{x\} = \{x\}$
$LV_{\bullet}(8) = LV_{\circ}(4)$
$LV_{\circ}(8) = LV_{\bullet}(8) \setminus \{i\} \cup \{i\}$
$LV_{\bullet}(7) = LV_{\circ}(8)$
$LV_{\circ}(7) = LV_{\bullet}(7) \setminus \{y\} \cup \{t\}$
$LV_{\bullet}(6) = LV_{\circ}(7)$
$LV_{\circ}(6) = LV_{\bullet}(6) \setminus \{x\} \cup \{y\}$
$LV_{\bullet}(5) = LV_{\circ}(6)$
$LV_{\circ}(5) = LV_{\bullet}(5) \setminus \{t\} \cup \{x, y\}$
$LV_{\bullet}(4) = LV_{\circ}(5) \cup LV_{\circ}(9)$
$LV_{\circ}(4) = LV_{\bullet}(4) \setminus \emptyset \cup \{i, z\}$
$LV_{\bullet}(3) = LV_{\circ}(4)$
$LV_{\circ}(3) = LV_{\bullet}(3) \setminus \{i\} \cup \emptyset$
$LV_{\bullet}(2) = LV_{\circ}(3)$
$LV_{\circ}(2) = LV_{\bullet}(2) \setminus \{y\} \cup \emptyset$
$LV_{\bullet}(1) = LV_{\circ}(2)$
$LV_{\circ}(1) =LV_{\bullet}(1) \setminus \{x\} \cup \emptyset$

Na razie nie mamy wyliczonego $LV_{\circ}(5)$ więc załóżmy, że jest równy $\emptyset$

$LV_{\bullet}(4) = \{x\}$
$LV_{\circ}(4) = \{x, i, z\}$

$LV_{\bullet}(8) = \{x, i, z\}$
$LV_{\circ}(8) = \{x, i, z\}$
$LV_{\bullet}(7) = \{x, i, z\}$
$LV_{\circ}(7) = \{x, i, z, t\}$
$LV_{\bullet}(6) = \{x, i, z, t\}$
$LV_{\circ}(6) = \{y, i, z, t\}$
$LV_{\bullet}(5) = \{y, i, z, t\}$
$LV_{\circ}(5) = \{y, i, z, x\}$

---
$LV_{\bullet}(4) = \{x, y, i, z\}$
$LV_{\circ}(4) = \{x, y, i, z\}$

$LV_{\bullet}(8) = \{x, y, i, z\}$
$LV_{\circ}(8) = \{x, y, i, z\}$
$LV_{\bullet}(7) = \{x, y, i, z\}$
$LV_{\circ}(7) = \{x, t, i, z\}$
$LV_{\bullet}(6) = \{x, t, i, z\}$
$LV_{\circ}(6) = \{y, i, z, t\}$
$LV_{\bullet}(5) = \{y, i, z, t\}$
$LV_{\circ}(5) = \{y, i, z, x\}$

$LV_{\bullet}(3) = \{x, y, i, z\}$
$LV_{\circ}(3) = \{x, y, z\}$
$LV_{\bullet}(2) = \{x, y, z\}$
$LV_{\circ}(2) = \{x, z\}$
$LV_{\bullet}(1) = \{x, z\}$
$LV_{\circ}(1) = \{z\}$

## Zadanie 7

:::success
Autor: Joanna Stachowicz
:::

## Zadanie 8

:::success
Autor: Dawid Dudek (do-deklarowane)
:::


### Jak działa analiza:

Jesteśmy w jakimś punkcie i chcemy wiedzieć jakie wyrażenia w tym punkcie mamy już policzone żeby się nie powtarzać.