# Ćwiczenia 4, grupa śr. 17-19, 30. 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 | | |
Adam Ciężkowski | X | X | | | X | X | X | |
Natalia Czerep | | X | | X | X | X | X | |
Jan Dalecki | X | X | X | X | X | X | X | X |
Marko Golovko | X | X | X | X | X | X | X | |
Adam Górkiewicz | X | X | X | X | X | X | X | X |
Piotr Gunia | | X | | | X | X | X | |
Krzysztof Jadłowski | | | | X | X | X | X | |
Magdalena Jarecka | X | | | | X | X | X | |
Mikołaj Jaszcza | X | X | X | X | X | X | X | |
Monika Jędrzejkowska | | | | | | | | |
Michał Kierul | | X | | X | X| X | X | |
Damian Lukas | | | | | | | | |
Karol Ochman-Milarski | | | | | | | | |
Piotr Piesiak | | | | | | | | |
Damian Ratajski | | | | | | | | |
Aleksandra Rozkrut | 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 | |
Nikola Wrona | 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 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 1
:::success
Autor: Mikołaj Jaszcza
:::

Bazujemy na rozwiązaniu uprzednio wklejonym:


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)$

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

### Etap 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\}$

### Etap 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\}$

### Etap 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\}$

### Etap 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\}$

### Etap 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\}$

### Etap 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\}$ // zawsze zostanie
$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\}$ // zawsze zostanie
$AE_{exit}(6) = \{i+1\}$
$AE_{exit}(7) = \{i+1\}$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Etap 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\}$ // zawsze zostanie
$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\}$ // zawsze zostanie
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \{i+1\}$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Etap 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\}$ // zawsze zostanie
$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\}$ // zawsze zostanie
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Etap 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\}$ // zawsze zostanie
$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\}$ // zawsze zostanie
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

### Etap 10 (bez zmian - koniec)
$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\}$ // zawsze zostanie
$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\}$ // zawsze zostanie
$AE_{exit}(6) = \emptyset$
$AE_{exit}(7) = \emptyset$
$AE_{exit}(8) = \emptyset$
$AE_{exit}(9) = \emptyset$

## Zadanie 2
:::success
Autor: Adam Górkiewicz
:::


Analiza będzie podobna do standardowej analizy $AE$, czyli (podobnie jak powyżej)
$$ F_\circ(l) = \cap\{F_\bullet(l') \ | \ (l', l) \in flow(S_*) \} $$
$$ F_\bullet(l) = (F_\circ(l) \setminus kill(l)) \cup gen(l) \ $$
Dziedziną zbiorów występujących w tej analizie będą zbiory zawierające pewne trójki $(x, l, a)$ oznaczające, że w danym punkcie wyrażenie $a$ jest dostępne w zmiennej $x$ przypisanej w operacji o identyfikatorze $l$. Funkcje $gen$ oraz $kill$ będą więc zdefiniowane następująco:
$$ gen([x := a]^l) = \{ (x, l, a) \}$$
$$ kill([x := a]^l) = \{ (x, l', a') \text{ po wszystkich $l', a'$} \} \\ \cup \{ (x', l', a') \text{ po wszystkich $x', l'$; po $a'$ zawierającym $x$} \}.$$
Natomiast dla operacji niemodyfikujących wartości zmiennych
$$ kill(l) = gen(l) = \emptyset $$
Analiza jest typu forward, must.

## Zadanie 3
:::success
Autor: Marko Golovko
:::



:::spoiler Pierwsza i druga wersja rozwiązania zadania (nieprawidłowa)


:::

## Zadanie 4
:::success
Autor: Marcin Sarnecki
:::
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:
- backward, ponieważ to, czy zmienna jest silnie żywa, zależy od przyszłych punktó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
:::success
Autor: Marcin Wróbel
:::
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
:::success
Autor: Krzysztof Jadłowski
:::

Możemy zauważyć że jako, że potrzebne nam są tylko 4 zmienne tymczasowe(nasz ostateczny wynik jest sumą, czyli możemy dodawać do niego kolejne elementy), dwie zmienne są nam potrzebne do przypisywania kolejnych wyników składników sumy, oraz kolejne dwie zamiennie jako "sumy prefiksowe".

t_1 := a * a
t_2 := t_1 * a
t_3 := t_2

t_1 := b * b
t_2 := t_1 * b
t_4:= t_3 + t_2

t_1 := a * b
t_2 := t_1 * 4
t_1 := t_2 * a
t_3:= t_4 + t_1

t_1 := a * b
t_2 = t_1 * 4
t_1 = t_2 * b
t_4 = t_3 + t_1

x:= t_4

t_1 := a * a
t_2 := t_1 * a
mem := t_2

t_1 := b * b
t_2 := t_1 * b
t_1 := mem
t_3 := t_1 + t_2
mem := t_3

t_1:= a * b
t_2 := t_1 * 4
t_1 := t_2 * a
t_2 = mem
t_3 = t_1 + t_2
mem:= t_3

t_1 := a * b
t_2 := t_1 * 4
t_1 := t_2 * b
t_2 = mem
t_3 = t_1 + t_2
mem := t_3

x:= mem

*****************************


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

## Zadanie 7
:::success
Autor: Magdalena Jarecka
:::

### Bubble Sort

## Zadanie 8
:::success
Autor: Jan Dalecki
:::


### 1. Układ sekwencyjny z jednym CSA

Posiadamy jeden moduł carry-save adder, który w pierwszym cyklu przeprowadzi obliczenia na b0A, b1A, b2A. Wynik takiego pośredniego obliczenia będziemy zapisywać w dwóch rejestrach Reg0 i Reg1, które na początku przechowują wartości b0A, b1A. Do 3 wejścia CSA podajemy w każdym cyklu kolejne wartości b2A, b3A i b4A.

Układ ten symuluje układ kombinacyjny z 3 sumatorami CSA. Każdy cykl to przejście do kolejnego poziomu. Po 3 cyklu na wyjściu RCA otrzymamy wynik mnożenia.

Reg2:0 przechowuje wyniki p0, p1, p2 które są uzyskiwane na każdym poziomie w układzie kombinacyjnym.

### 2. Układ sekwencyjny z 3 CSA

W tym układzie pamiętamy każde obliczenia wykonane przez sumatory CSA. Dzięki temu możemy skrócić czas na obliczenie dużej liczby kolejnych par liczb. Bez pamięci czas zegara byłby ograniczony przez czas obliczenia całego układu. Wprowadzając rejestry możemy zwiększyć częstotliwość zegara, który ograniczamy jedynie czasem RCA.

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