# Ćwiczenia 3, grupa śr. 17-19, 23. 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Grzegorz Bielecki | | | | | | | | |
Kamila Brzozowska | X | X | X | X | X | X | | |
Adam Ciężkowski | ==X== | X | X | X | X | X | X | X |
Natalia Czerep | X | X | X | X | X | X | | |
Jan Dalecki | X | X | X | X | X | ==X== | X | X |
Marko Golovko | X | X | X | X | | | | |
Adam Górkiewicz | X | X | X |==X==| X | X | X | X |
Piotr Gunia | ==X== | X | X | X | X | | | |
Krzysztof Jadłowski | | | | | | | | |
Magdalena Jarecka | X | X | | X | | X | X | |
Mikołaj Jaszcza | x | x | x | x | x | x |==x==| |
Monika Jędrzejkowska | | | | | | | | |
Michał Kierul | | | | | | | | |
Damian Lukas | X | X | | | | X | | |
Karol Ochman-Milarski | | | | | | | | |
Piotr Piesiak | | | | | | | | |
Damian Ratajski | | | | | | | | |
Aleksandra Rozkrut | X | X | X | X |==X==| | | |
Marcin Sarnecki | X |==X==| X | X | X | X | X | |
Maria Szlasa | X | X | X | | X | | | |
Mateusz Burdyna | X | X |==X==| X | X | | | |
Nikola Wrona | X | X | X | X | X | X | X | |
Marcin Wróbel | X | X | X | X |==X==| X | X | |
:::

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

## Zadanie 1

:::success
Autor: Piotr Gunia
:::




## Zadanie 2

:::success
Autor: Marcin Sarnecki
:::
$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) = \{(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,?) (t,5)\}$
$RD_{\bullet}(4) = RD_{\circ}(4)$

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

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

$RD_{\circ}(7) = RD_{\bullet}(6)$
$RD_{\bullet}(7) = RD_{\circ}(7) \setminus \{(y,7),(y,2)\} \bigcup \{(y,7)\} = \{(x,6), (y,7), (z,?), (i,3), (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), (x,6), (y,9), (z,?), (i,3), (i,8), (t,?) (t,5)\}$

## Zadanie 3

:::success
Autor: Mateusz Burdyna
:::


$*$ - ostatnie przypisanie do danego $RD_i$
$$
\begin{align}
*RD_∘(1) &= \{(x,?),(y,?),(z,?),(t,?),(i,?)\} \\
*RD_⦁(1) &= \{(x,1),(y,?),(z,?),(t,?),(i,?)\} \\
*RD_∘(2) &= \{(x,1),(y,?),(z,?),(t,?),(i,?)\} \\
*RD_⦁(2) &= \{(x,1),(y,2),(z,?),(t,?),(i,?)\} \\
*RD_∘(3) &= \{(x,1),(y,2),(z,?),(t,?),(i,?)\} \\
*RD_⦁(3) &= \{(x,1),(y,2),(z,?),(t,?),(i,3)\} \\
RD_∘(4) &= \{(x,1),(y,2),(z,?),(t,?),(i,3)\} \\
RD_⦁(4) &= \{(x,1),(y,2),(z,?),(t,?),(i,3)\} \\
RD_∘(5) &= \{(x,1),(y,2),(z,?),(t,?),(i,3)\} \\
RD_⦁(5) &= \{(x,1),(y,2),(z,?),(t,5),(i,3)\} \\
RD_∘(6) &= \{(x,1),(y,2),(z,?),(t,5),(i,3)\} \\
RD_⦁(6) &= \{(x,6),(y,2),(z,?),(t,5),(i,3)\} \\
RD_∘(7) &= \{(x,6),(y,2),(z,?),(t,5),(i,3)\} \\
RD_⦁(7) &= \{(x,6),(y,7),(z,?),(t,5),(i,3)\} \\
RD_∘(8) &= \{(x,6),(y,7),(z,?),(t,5),(i,3)\} \\
*RD_⦁(8) &= \{(x,6),(y,7),(z,?),(t,5),(i,8)\} \\
*RD_∘(4) &= \{(x,1), (x, 6),(y,2), (y, 7),(z,?),(t,?),(t, 5), (i,3), (i, 8)\} \\
*RD_⦁(4) &= \{(x,1), (x, 6),(y,2), (y, 7),(z,?),(t,?),(t, 5), (i,3), (i, 8)\} \\
*RD_∘(5) &= \{(x,1), (x, 6),(y,2), (y, 7),(z,?),(t,?),(t, 5), (i,3), (i, 8)\} \\
*RD_⦁(5) &= \{(x,1), (x, 6),(y,2), (y, 7),(z,?),(t, 5), (i,3), (i, 8)\} \\
*RD_∘(6) &= \{(x,1), (x, 6),(y,2), (y, 7),(z,?),(t, 5), (i,3), (i, 8)\} \\
*RD_⦁(6) &= \{(x, 6),(y,2), (y, 7),(z,?),(t, 5), (i,3), (i, 8)\} \\
*RD_∘(7) &= \{(x, 6),(y,2), (y, 7),(z,?),(t, 5), (i,3), (i, 8)\} \\
*RD_⦁(7) &= \{(x, 6),(y, 7),(z,?),(t, 5), (i,3), (i, 8)\} \\
*RD_∘(8) &= \{(x, 6),(y, 7),(z,?),(t, 5), (i,3), (i, 8)\} \\
*RD_∘(9) &= \{(x,1), (x, 6),(y,2), (y, 7),(z,?),(t,?),(t, 5), (i,3), (i, 8)\} \\
*RD_⦁(9) &= \{(x,1), (x, 6),(y, 9),(z,?),(t,?),(t, 5), (i,3), (i, 8)\} \\
\end{align}
$$

## Zadanie 4

:::success
Autor: Adam Górkiewicz
:::

## Zadanie 5

:::success
Autor: Aleksandra Rozkrut
:::



W instrukcji `2` sprawdzamy, czy $x>0$, a $RD_{entry}(2)=\{(x,1), (y,?), (z, ?)\}$, więc program nigdy nie wejdzie do instrukcji `4`. Z tego wynika, że krotka $(y,4)$ nie musi znajdować się w $RD_{entry}(5)$ i $RD_{exit}(5)$. Zatem to rozwiązanie nie jest najlepsze.

## Zadanie 6

:::success
Autor: Jan Dalecki
:::

## Zadanie 7

:::success
Autor: Mikołaj Jaszcza
:::
"Use-Definition Chain" to struktura danych która dla każdego wystąpienia zmiennej w programie trzyma informację o miejscach, w których mogła być zdefiniowana bez jej późniejszej zmiany aż do rozważanego wystąpienia. Jest używana do statycznej analizy kodu - służyć może między innymi do pewnych optymalizacji w procesie kompilacji.

Opisywane analizy przedstawię w postaci:
$UD\texttt{-}chain(VAR,LABEL) = \{L1, L2, ...\}$

Przypomnijmy kod z zadania 1:

Nie rozpisujemy analiz typu $UD\texttt{-}chain(VAR,LAB)$ gdy wartość zmiennej $VAR$ nie jest istotna dla instrukcji oznaczonej $LAB$ (ich wartość można symbolicznie zapisać przez $\emptyset$)

Analizując więc instrukcje które korzystają z wartości jakichś zmiennych (tj. inne niż ... := b dla b będącą stałą):
$UD\texttt{-}chain(i,4) = ...$
$UD\texttt{-}chain(z,4) = ...$

$UD\texttt{-}chain(x,5) = ...$
$UD\texttt{-}chain(y,5) = ...$

$UD\texttt{-}chain(y,6) = ...$

$UD\texttt{-}chain(t,7) = ...$

$UD\texttt{-}chain(i,8) = ...$

$UD\texttt{-}chain(x,9) = ...$

Przypomnijmy wartości $RD_{\circ}(4)$, $RD_{\circ}(5)$, $RD_{\circ}(6)$, $RD_{\circ}(7)$, $RD_{\circ}(8)$, $RD_{\circ}(9)$ (bo tylko dla instrukcji 4, 5, 6, 7, 8, 9 mamy wyrażenia takiego typu jak opisałem wyżej):

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

Mamy zatem:
$UD\texttt{-}chain(i,4) = \{3, 8\}$
$UD\texttt{-}chain(z,4) = \{?\}$
$UD\texttt{-}chain(x,5) = \{1, 6\}$
$UD\texttt{-}chain(y,5) = \{2, 7\}$
$UD\texttt{-}chain(y,6) = \{2, 7\}$
$UD\texttt{-}chain(t,7) = \{5\}$
$UD\texttt{-}chain(i,8) = \{3, 8\}$
$UD\texttt{-}chain(x,9) = \{1, 6\}$

co kończy zadanie

## Zadanie 8

:::success
Autor: Adam Ciężkowski
:::


Analiza dotępnych wyrażeń pozwala na redukcję obliczeń, które wykonaliśmy już wcześniej. Jeśli zmieniamy jakąś zmienną, wyrzucamy wyrażenia ją zawierającą. Jeśli przypisujemy do zmiennej (ciąg) wyrażeń, dodajemy te, które nie zawierają tej zmiennej.




<!--  - z błędem -->

<!--  -->