# Ćwiczenia 4, grupa cz. 10-12, 21 marca 2024

###### tags: `SYK24` `ć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 |
| ----------------------:| -----| --- | --- | --- | --- |
Borys Adamiak | X | X | | X | X |
Michał Chawar | X | X | X | X | X |
Julia Cygan | X | X | | X | X |
Maciej Dengusiak | ==X== | X | X | X | X |
Patryk Flama | X | X | X | ==X== | X |
Szymon Fluder | | | | | |
Aleksandra Jędrzejak | X | X | | X | |
Mikołaj Karapka | X | X | | X | X |
Viktoriia Kashpruk | X | X | X | X | X |
Wiktor Małek | X | ==X== | X | X | X |
Błażej Molik | X | X | X | X | X |
Andrzej Morawski | | | | | |
Konrad Oleksy | | | | | |
Lucjan Pucelak | X | X | | X | X |
Aleksandra Sęk | X | | | | |
Radosław Śliwiński | | | | | |
Piotr Traczyński | X | X | X | X | X |
Katarzyna Trzos | X | X | | X | X |
Piotr Warząchowski | X | X | | X | X |
Olga Zaborska | X | X | X | X | ==X== |
:::

Tu można zadeklarować zadania **3** i **4** z **listy 3**:

:::danger
| | 3.3 | 3.4 |
| ----------------------:| -----| -----|
Borys Adamiak | | |
Michał Chawar | | |
Julia Cygan | | |
Maciej Dengusiak | | |
Patryk Flama | | |
Szymon Fluder | | |
Aleksandra Jędrzejak | | |
Mikołaj Karapka | | |
Viktoriia Kashpruk | X | |
Wiktor Małek | | |
Błażej Molik | | |
Andrzej Morawski | | |
Konrad Oleksy | | |
Lucjan Pucelak | | |
Aleksandra Sęk | | |
Radosław Śliwiński | | |
Piotr Traczyński | | |
Katarzyna Trzos | | |
Piotr Warząchowski | | |
Olga Zaborska | | |
:::

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

## Zadanie 1
:::success
Autor: Maciej Dengusiak


Po przeprowadzeniu analizy programu i wypisaniu zbioru faktów wychodzą nam następujące równania definiujące zbiory $RD_{∘}(l)$ i $RD_{⦁}(l)$, dla $l∈$ {1,...,9}:

### Równania:

$RD_{⦁}(1)$ = $RD_{∘}(1)$ \ {(x, l) : $l∈$ **Lab**} ∪ {(x, 1)}
$RD_{⦁}(2)$ = $RD_{∘}(2)$ \ {(y, l) : $l∈$ **Lab**} ∪ {(y, 2)}
$RD_{⦁}(3)$ = $RD_{∘}(3)$ \ {(i, l) : $l∈$ **Lab**} ∪ {(i, 3)}
$RD_{⦁}(4)$ = $RD_{∘}(4)$
$RD_{⦁}(5)$ = $RD_{∘}(5)$ \ {(t, l) : $l∈$ **Lab**} ∪ {(t, 5)}
$RD_{⦁}(6)$ = $RD_{∘}(6)$ \ {(x, l) : $l∈$ **Lab**} ∪ {(x, 6)}
$RD_{⦁}(7)$ = $RD_{∘}(7)$ \ {(y, l) : $l∈$ **Lab**} ∪ {(y, 7)}
$RD_{⦁}(8)$ = $RD_{∘}(8)$ \ {(i, l) : $l∈$ **Lab**} ∪ {(i, 8)}
$RD_{⦁}(9)$ = $RD_{∘}(9)$ \ {(y, l) : $l∈$ **Lab**} ∪ {(y, 9)}

$RD_{∘}(1)$ = {(x, ?), (y, ?), (i, ?), (t, ?)}
$RD_{∘}(2)$ = $RD_{⦁}(1)$
$RD_{∘}(3)$ = $RD_{⦁}(2)$
$RD_{∘}(4)$ = $RD_{⦁}(3)$ ∪ $RD_{⦁}(8)$
$RD_{∘}(5)$ = $RD_{⦁}(4)$
$RD_{∘}(6)$ = $RD_{⦁}(5)$
$RD_{∘}(7)$ = $RD_{⦁}(6)$
$RD_{∘}(8)$ = $RD_{⦁}(7)$
$RD_{∘}(9)$ = $RD_{⦁}(8)$

### Zbiory z zadania 6


#### Łatwo sprawdzić że te zbiory spełniają powyższe równania.
:::
:::

## Zadanie 2
:::success
Autor: Wiktor Małek
:::
Inicjalizacja: Wszystkie zbiory puste

I iteracja:

$$RD_{in}(1)=\{(x, ?), (y, ?), (i, ?), (t, ?)\}$$
$$RD_{out}(1)=\{(x, 1), (y, ?), (i, ?), (t, ?)\}$$

$$RD_{in}(2)=\{(x, 1), (y, ?), (i, ?), (t, ?)\}$$
$$RD_{out}(2)=\{(x, 1), (y, 2), (i, ?), (t, ?)\}$$

$$RD_{in}(3)=\{(x, 1), (y, 2), (i, ?), (t, ?)\}$$
$$RD_{out}(3)=\{(x, 1), (y, 2), (i, 1), (t, ?)\}$$

$$RD_{in}(4)=\{(x, 1), (y, 2), (i, 1), (t, ?)\}$$
$$RD_{out}(4)=\{(x, 1), (y, 2), (i, 1), (t, ?)\}$$

$$RD_{in}(5)=\{(x, 1), (y, 2), (i, 1), (t, ?)\}$$
$$RD_{out}(5)=\{(x, 1), (y, 2), (i, 1), (t, 5)\}$$

$$RD_{in}(6)=\{(x, 1), (y, 2), (i, 1), (t, 5)\}$$
$$RD_{out}(6)=\{(x, 6), (y, 2), (i, 1), (t, 5)\}$$

$$RD_{in}(7)=\{(x, 6), (y, 2), (i, 1), (t, 5)\}$$
$$RD_{out}(7)=\{(x, 6), (y, 7), (i, 1), (t, 5)\}$$

$$RD_{in}(8)=\{(x, 6), (y, 7), (i, 1), (t, 5)\}$$
$$RD_{out}(8)=\{(x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(9)=\{(x, 1), (y, 2), (i, 1), (t, ?)\}$$

II iteracja:

linie 1,2,3 się nie zmienią więc pomijam

$$RD_{in}(4)=\{(x, 1), (y, 2), (i, 1), (t, ?), (x, 6), (y, 7), (i, 8), (t, 5)\}$$
$$RD_{out}(4)=\{(x, 1), (y, 2), (i, 1), (t, ?), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(5)=\{(x, 1), (y, 2), (i, 1), (t, ?), (x, 6), (y, 7), (i, 8), (t, 5)\}$$
$$RD_{out}(5)=\{(x, 1), (y, 2), (i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(6)=\{(x, 1), (y, 2), (i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$
$$RD_{out}(6)=\{(y, 2), (i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(7)=\{(y, 2), (i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$
$$RD_{out}(7)=\{(i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(8)=\{(i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$
$$RD_{out}(8)=\{(x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(9)=\{(x, 1), (y, 2), (i, 1), (t, ?), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

Po II iteracji już nic się nie zmieni, więc zatrzymujemy się.

## Zadanie 3
:::success
Autor: Michał Chawar
:::


**1.** Wystąpienia funkcji $kill$ i $gen$ pojawiają się w równaniach $RD_{\bullet}$, które są postaci $RD_{\bullet}(*) = RD_{\circ}(*) \setminus kill \cup gen$.
Np. w
$RD_{\bullet}(3) = RD_{\circ}(3) \setminus \{ (i, \ell) \mid \ell \in Lab \} \cup \{ (i, 3) \}$
wystąpienie funkcji $kill$ to $\{ (i, \ell) \mid \ell \in Lab \} = \{ (i, ?) \}$, a funkcji $gen$ to $\{ (i, 3) \}$.

**2.** Dla instrukcji $read$ funkcja $kill$ powinna usuwać wszystkie poprzednie przypisania zmiennej $x$, bo instrukcją $read$ nadpisujemy ją bezwarunkowo. Instrukcja $gen$ powinna więc generować informację o nadpisaniu tej zmiennej przez siebie.

$$
kill_{RD}([read(x)]^{\ell}) = \{ (x, ?) \} \cup \{ (x, \ell') \mid \text{w instrukcji $\ell'$ jest przypisanie do $x$} \}
$$

$$
gen_{RD}([read(x)]^{\ell}) = \{ (x, \ell) \}
$$

Okazuje się, że w zakresie instrukcji $kill$ i $gen$ instrukcja $read$ nie różni się od zwykłego przypisania do zmiennej.

**3.** Z pliku `slides2.pdf` (slajd $19$) mamy

$$
RD_{\circ}(\ell) = \begin{cases}
\ \ \ \ \ \{ (x, ?) \ \ \ \ \mid x \in FV \} & \text{gdy $\ell$ = 1}\\
\bigcup \ \{ RD_{\bullet}(\ell') \mid \text{$\ell'$ przechodzi do $\ell$} \} & \text{w przeciwnym przypadku}
\end{cases}
$$

$$
RD_{\bullet}(\ell) = [ RD_{\circ}(\ell) \setminus kill_{RD}([...]^\ell) ] \cup gen_{RD}([...]^\ell)
$$

($FV$ to zbiór wszystkich zmiennych występujących w programie).

Widzimy więc, że zbiory $RD_{\circ}$ i $RD_{\bullet}$ można obliczyć tylko na podstawie informacji o przypisaniach do zmiennych w programie i wiedzy o kolejności wykonywania instrukcji.
Stąd wystarczy przejść po przepływie sterowania, odnotowując wszystkie nadpisania zmiennych w instrukcjach, po czym przejść jeszcze raz i wygenerować te zbiory na podstawie zebranych danych.

## Zadanie 4
:::success
Autor: Patryk Flama
:::
W faktycznym wykonaniu naszego programu druga opcja if'a nigdy nie zajdzie, więc policzona krotka (y, 4) jest zbędna. Otrzymaliśmy więc rozwiązanie bezpieczne, a nie dokładne.

## Zadanie 5
:::success
Autor: Olga Zaborska
:::


Zmienne żywe to te, których program użyje zanim nadpisze im nową wartość
Na przykładzie z wykładu
Widzimy, że pierwsze wystąpienie $x$ nie jest żywe, ponieważ jego wartość zostanie nadpisana przed pierwszym użyciem.

Schemat działania:


Wracając do przykładu:

Teraz dla zadania:

| l | $kill_{LV}(l)$ | $gen_{LV}(l)$ |
| -------- | -------- | -------- |
| 1 | {x} | $\emptyset$ |
| 2 | {y} | $\emptyset$ |
| 3 | {i} | $\emptyset$ |
| 4 | $\emptyset$ | {i,z} |
| 5 | {t} | {x,y} |
| 6 | {x} | {y} |
| 7 | {y} | {t} |
| 8 | {i} | {i} |
| 9 | {y} | {x} |

Kolejny krok


Dla przykładu

Dla programu z treści zadania

| l | $kill_{LV}(l)$ | $gen_{LV}(l)$ |$LV_{entry}$ |$LV_{exit}$ |
| -------- | -------- | -------- | --- | ---|
| 1 | {x} | $\emptyset$ | {z} | {x,z} |
| 2 | {y} | $\emptyset$ | {x,z} | {x,y,z} |
| 3 | {i} | $\emptyset$ | {x,y,z} | {x,y,z,i} |
| 4 | $\emptyset$ | {i,z} | {x,y,z,i} | {x,y,z,i} |
| 5 | {t} | {x,y} | {x,y,z,i} | {t,y,z,i} |
| 6 | {x} | {y} | {t,y,z,i} | {x,t,z,i} |
| 7 | {y} | {t} | {x,t,z,i} | {x,y,z,i} |
| 8 | {i} | {i} | {x,y,z,i} | {x,y,z,i} |
| 9 | {y} | {x} | {x} | $\emptyset$ |

$LV_{in}(1) = LV_{out}(1) \setminus{\{x\}}$
$LV_{out}(1) = LV_{in}(2)$

$LV_{in}(2) = LV_{out}(2) \setminus{\{y\}}$
$LV_{out}(2) = LV_{in}(3)$

$LV_{in}(3) = LV_{out}(3) \setminus{\{i\}}$
$LV_{out}(3) = LV_{in}(4)$

$LV_{in}(4) = LV_{out}(4) \cup{\{z,i\}}$
$LV_{out}(4) = LV_{in}(5) \cup LV_{in}(5)$

$LV_{in}(5) = LV_{out}(5) \setminus{\{t\}} \cup{\{x,y\}}$
$LV_{out}(5) = LV_{in}(6)$

$LV_{in}(6) = LV_{out}(6) \setminus{\{x\}} \cup {\{y\}}$
$LV_{out}(6) = LV_{in}(7)$

$LV_{in}(7) = LV_{out}(7) \setminus{\{y\}} \cup {\{t\}}$
$LV_{out}(7) = LV_{in}(8)$

$LV_{in}(8) = LV_{out}(8) \setminus{\{i\}} \cup {\{i\}}$
$LV_{out}(8) = LV_{in}(4) = LV_{out}(4) \cup \{i,z\} = (LV_{in}(5) \cup LV_{in}(9)) \cup \{i,z\} = (LV_{out}(5) \setminus\{t\} \cup \{x,y\}) \cup \{x\} \cup \{i,z\} = \ ... \setminus \{t\} \cup \{x,y,z,i\} = \{x,y,z,i\}$

$LV_{in}(9) = LV_{out}(9) \setminus{\{y\} \cup {\{x\}}}$
$LV_{out}(9) = \emptyset$

$LV_{in}(9) = \{x\}$