# Ćwiczenia 5, grupa cz. 16-18, 28 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 | 6 | 7 | 8 | 9 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Marcin Banak | X | | | | | X | X | X | X |
Bartosz Borecki | X | | | | | X | X | X |==X==|
Karol Burczyk | X | ==X== | | | | X | X | X | X |
Yelyzaveta Ilman | X | X | | | | X | ==X== | X | X |
Antoni Kamiński | X | X | | | | X | X | X | |
Jan Kamyk | X | X | | | | X | X |==X==| |
Bartosz Kruszewski | X | X | X | X | X | X | X | X | X |
Hanna Laszkiewicz | X | X | | | | X | X | X | X |
Kaja Matuszewska | | | | | | | | | |
Dominik Muc | | | | | | | | | |
Krzysztof Ostrowski | | | | | | X | X | X | |
Franciszek Przeliorz | ==X== | | | | | X | X | X | |
Yaryna Rachkevych | X | | | | | X | X | X | |
Mikołaj Kalitka | | | | | | | | | |
Piotr Thamm | X | X | | | | ==X== | X | X | |
Taras Tsehenko | | | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Franciszek Przeliorz

#### Definicja

Use-definition chains to zbiór etykiet bloków w programie, które zdefiniowały wartość zmiennej x i mogą być osiągnięte przed punktem, w którym chcemy użyć zmiennej x.

$def(x, l)$ - blok $l$ przypisuje wartość do zmiennej $x$\
$clear(x, l, l')$ - żaden z bloków na ścieżce z $l$ do $l'$ nie przypisuje wartości do zmiennej $x$, ale $l'$ odwołuje się do $x$ (bez przypisywania $x$ wartości).

$ud(x, l') = \{l | def(x, l) \land \exists l'': (l,l'')\in flow(S)$
$\in clear(x, l'', l')\}\cup \{?|clear(x, init(S),l')\}$

#### Definicja alternatywna

$ud(x, l') = \{l' | (x, l') \in RD_{entry}(l)\} if x \in gen(B^l)$

---

#### Program z zadania 3, lista 6

[𝑥:= 0]1
[𝑦:= 1]2
[𝑖 := 1]3
while [𝑖 < 𝑧]4 do
    [𝑡:= 𝑥 + 𝑦]5 
    [𝑥:= 𝑦]6 
    [𝑦:= 𝑡]7
    [𝑖:= 𝑖+1]8
od
[𝑦:= 𝑥]9

#### Zbiory $RD_\circ$

|i | $Rd_{\circ} (l)$ |
|--- | --------------------------------------------------------- |
|1 | {(x,?), (y,?), (z,?), (i,?), (t,?)} |
|2 | {(x,1), (y,?), (z,?), (i,?), (t,?)} |
|3 | {(x,1), (y,2), (z,?), (i,?), (t,?)} |
|4 | {(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)} |
|5 | {(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)} |
|6 | {(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)} |
|7 | {(x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)} |
|8 | {(x,6), (y,7), (z,?), (i,3), (i,8), (t,5)} |
|9 | {(x,1), (x,6), (y,2), (y,7), (z,?), (i,3), (i,8), (t,5)} |

---

#### Rozwiązanie

Jeśli w bloku o etykiecie 'l' mamy odwołanie do zmiennej 'x' , to $ud(x, l)$ oznacza zbiór etykiet instrukcji, które ostatnio przypisały wartość zmiennej 'x'. Ten zbiór może zawierać więcej niż jedną etykietę, gdy występuje "rozgałęzienie" w przepływie sterowania.

Znak '?' zostało wpisane, gdy zmienna 'x' nie została wcześniej przypisana wartości.

| | x | y | z | t | i |
|----|----------|----------|-----|-----|---------|
| 1. | ∅ | ∅ | ∅ | ∅ | ∅ |
| 2. | ∅ | ∅ | ∅ | ∅ | ∅ |
| 3. | ∅ | ∅ | ∅ | ∅ | ∅ |
| 4. | ∅ | ∅ | {?} | ∅ | {3} |
| 5. | {1, 6} | {2, 7} | ∅ | ∅ | ∅ |
| 6. | ∅ | {2, 7} | ∅ | ∅ | ∅ |
| 7. | ∅ | ∅ | ∅ | {5} | ∅ |
| 8. | ∅ | ∅ | ∅ | ∅ | {3, 8} |
| 9. | {1, 6} | ∅ | ∅ | ∅ | ∅ |

:::

## Zadanie 2
:::success
Autor: Karol Burczyk
:::

Przykład:
a := x + y b := c + x + y -> b := c + a




#### Równania

OUT(1) = IN(1)
OUT(2) = IN(2)
OUT(3) = IN(3)
OUT(4) = IN(4)
OUT(5) = IN(5) U {x + y}
OUT(6) = IN(6) \ {x + y}
OUT(7) = IN(7) \ {x + y}
OUT(8) = IN(8) \ {i + 1}
OUT(9) = IN(9)

IN(1) = {}
IN(2) = OUT(1)
IN(3) = OUT(2)
IN(4) = OUT(3) * OUT(8)
IN(5) = OUT(4)
IN(6) = OUT(5)
IN(7) = OUT(6)
IN(8) = OUT(7)
IN(9) = OUT(4)

#### Wyniki

IN(1) = {}
OUT(1) = IN(1) = {}
IN(2) = OUT(1) = {}
OUT(2) = IN(2) = {}
IN(3) = OUT(2) = {}
OUT(3) = IN(3) = {}
IN(4) = OUT(3) * OUT(8) = {} * OUT(8) = {}
OUT(4) = IN(4) = {}
IN(5) = OUT(4) = {}
OUT(5) = IN(5) U {x + y} = {x + y}
IN(6) = OUT(5) = {x + y}
OUT(6) = IN(6) \ {x + y} = {}
IN(7) = OUT(6) = {}
OUT(7) = IN(7) \ {x + y} = {}
IN(8) = OUT(7) = {}
OUT(8) = IN(8) \ {i + 1} = {}
IN(9) = OUT(4) = {}
OUT(9) = IN(9) = {}

## Zadanie 3
:::success
Autor: Bartosz Kruszewski
:::

#### Definicja

Ta analiza różni się od analizy z poprzedniego zadania tym, że rozpatrujemy w niej zbiór dostępnych wyrażeń dla każdej zmiennej osobno.

#### Definicja $kill$ i $gen$

$kill([x := a]) = \{(x, a') | a' \in AEXP, x \in FV(a')\}$\
$kill([skip]) = \emptyset$ \
$kill([b]) = \emptyset$

$gen([x := a]) = \{(x, a') | a' \in AEXP(a), x \notin FV(a') \}$ \
$gen([skip]) = \emptyset$ \
$gen([b]) = \emptyset$

#### Postać równań

$IN(l) = \cap OUT(l')$\
$OUT(l) = IN(l) \cup gen(l) \setminus kill(l)$

Analiza jest typu $must$ bo używamy przekroju zbiorów do łączneia wyników z różnych ścieżek, oraz typu $forward$, ponieważ "idziemy do przodu" w przepływie sterowania.

## Zadanie 4
:::success
Autor: Bartosz Kruszewski
:::

#### Definicja

Ta analiza różni się od analizy z poprzedniego tym, że rozpatrujemy w niej zbiór dostępnych wyrażeń dla każdej zmiennej osobno.

#### Definicja $kill$ i $gen$

$kill([x := a]) = \{(x, a') | a' \in AEXP, x \in FV(a')\}$\
$kill([skip]) = \emptyset$ \
$kill([b]) = \emptyset$

$gen([x := a]) = \{(x, a') | a' \in AEXP(a), x \notin FV(a') \}$ \
$gen([skip]) = \emptyset$ \
$gen([b]) = \emptyset$

#### Postać równań

$IN(l) = \cap OUT(l')$\
$OUT(l) = IN(l) \cup gen(l) \setminus kill(l)$

Analiza jest typu $must$ bo używamy przekroju zbiorów do łączneia wyników z różnych ścieżek, oraz typu $forward$, ponieważ "idziemy do przodu" w przepływie sterowania.

Analiza jest typu $must$, więc do obliczania równań użyjemy algorytmu stałopunktowego w wersji z szukaniem **największego** punktu stałego, zamiast najmniejszego.

#### Równania

OUT(1) = IN(1)
OUT(2) = IN(2)
OUT(3) = IN(3)
OUT(4) = IN(4)
OUT(5) = IN(5) U {(t, x + y)}
OUT(6) = IN(6) \ {(y, x + y), (t, x + y), (i, x + y)}
OUT(7) = IN(7)
OUT(8) = IN(8)
OUT(9) = IN(9)

IN(1) = {}
IN(2) = OUT(1)
IN(3) = OUT(2)
IN(4) = OUT(3) * OUT(8)
IN(5) = OUT(4)
IN(6) = OUT(5)
IN(7) = OUT(6)
IN(8) = OUT(7)
IN(9) = OUT(4)

#### Wyniki

IN(1) = {}
OUT(1) = IN(1) = {}
IN(2) = OUT(1) = {}
OUT(2) = IN(2) = {}
IN(3) = OUT(2) = {}
OUT(3) = IN(3) = {}
IN(4) = OUT(3) * OUT(8) = {} * OUT(8) = {}
OUT(4) = IN(4) = {}
IN(5) = OUT(4) = {}
OUT(5) = IN(5) U {x + y} = {(t, x + y)}
IN(6) = OUT(5) = {(t, x + y)}
OUT(6) = IN(6) \ {(y, x + y), (t, x + y), (i, x + y)} = {}
IN(7) = OUT(6) = {}
OUT(7) = IN(7) = {}
IN(8) = OUT(7) = {}
OUT(8) = IN(8) = {}
IN(9) = OUT(4) = {}
OUT(9) = IN(9) = {}

## Zadanie 5
:::success
Autor: Bartosz Kruszewski
:::


#### Przykład

W pierwszym przypadku zmienne silne zywe nie róznią się od zwyklych zywych. Natomiast w drugim przykladzie widzimy ze x jest uzywany tylko do zdefioniowania y, wiec jest zywy (bo jest wykorzystywany do przypisania), ale nie jest silnie zywy, poniewaz y jest martwy.

#### Definicje $kill$ oraz $gen$:

Oznaczmy $SL(l)$ jako zbiór zmiennych silnie zywych w dla $OUT(l)$

$kill([x := a]) = \{x\}$ \
$kill([skip]) = \emptyset$ \
$kill([b]) = \emptyset$

$gen([x := a]) = \{a' | a' \in FV(a) \land x \in SL(l)\}$ \
$gen([skip]) = \emptyset$ \
$gen([b]) = FV(b)$

Róznica pomiedzy standardowymi zmiennymi zywymi polega na tym, ze sprawdzamy, w momencie dodawania nowej zmiennej do zbioru, czy przypisywana jest ona zmiennej zywej, czyli takiej którą wybraliśmy wcześniej.

#### Równania przepływu

$OUT(l) = \cup {IN(l')}$\
$IN(l) = OUT(l) \setminus kill(l) \cup gen(l)$

Analiza jest typu $may$ bo używamy sumy zbiorów do łączneia wyników z różnych ścieżek, oraz typu $backward$, ponieważ "cofamy się" w przepływie sterowania.

## Zadanie 6
:::success
Autor: Piotr Thamm


#### $$ while (b)\{...\} $$

L: if b == 0 goto E
   ...
   goto L
E:

#### $$ for (i = 0; i < n; i++) \{...\} $$

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

#### $$ do\{...\}while (b) $$

L: ...
   if b goto L

:::

## Zadanie 7
:::success
Autor: Krzysztof Ostrowski
:::

### Przekształcenie wyrażenia

$x = a*a*a + 4*a*a*b + 4*a*b*b + b*b*b =$
$=(a + b)^3 + a*a*b + a*b*b =$
$=(a + b)^3 + a*b*(a + b)$

#### Program optymalny w kodzie trójkowym

t1 := a + b # t1 = a + b
t2 := t1 # t2 = a + b
t2 := t2 * t1 # t2 = (a + b) ^ 2
t2 := t2 * t1 # t2 = (a + b) ^ 3
t1 := t1 * a # t1 = (a + b) * a
t1 := t1 * b # t1 = (a + b) * a * b
t1 := t1 + t2 # t1 = (a + b) * a * b + (a + b) ^ 3

### Program bez przekształcenia, ale z wykorzystaniem $mem$

#### wyliczenie wartośći i zapisanie ich w tablicy
t := a * a
t := t * a
mem[0] := t
t := 4 * a
t := t * a
t := t * b
mem[4] := t
t := 4 * a
t := t * b
t := t * b
mem[8] := t
t := b * b
t := t * b
mem[12] := t

#### odczytanie wartości i dodanie ich
r := mem[0]
t := r
r := mem[4]
t := t + r
r := mem[8]
t := t + r
r := mem[12]
t := t + r

## Zadanie 8
:::success
Autor: Jan Kamyk
:::

<B>Bubble Sort</B>

i = 0
L1: if i >= n goto L2
j = 0

L3: if j >= n-i-1 goto L4
t1 = j * 1
addr1 = &A + t1
t2 = (j+1) * 1
addr2 = &A + t2
val1 = *addr1
val2 = *addr2
if val1 > val2 goto L5
temp = *addr1
*addr1 = *addr2
*addr2 = temp

L5: j = j + 1
goto L3

L4: i = i + 1
goto L1

L2:
//Posortowana tablica

## Zadanie 9
:::success
Autor: Marcin Banak
:::

#### Zadania poszczególnych elementów procesora

- **licznik rozkazów**: przesyła kolejne numery instrukcji w kazdym cyklu zegara
- **rejestr rozkazów**: przyjmuje numer instrukcji od licznika i zwraca jej treść
- **plik rejestrów**: odczytuje i zapisuje wartości zmiennych do rejestrów,
wejścia A1, A2 i RD1, RD2 słuzą do odczytu, natomiast A3 i WD3 do zapisu.
Wejście jednobitowe WE3 sluzy do okreslenia czy chcemy zapisywac
- **ALU *(jednostka arytmetyczno-logiczna)***: wykonuje podstawowe operacje arytmetyczne i logiczne, jest sterowana przez 3-bitowe wejśćie, za pomocą którego wybieramy jaką operacje chcemy wykonać
- **pamiec danych**: zapisuje i odczytuje dane, głównie z przeznaczeniem "na pózniej".

#### Znaczenie operacji $ x:= *(y + imm)$

Operacja polega na odczytaniu wartości z pamięci pod adresem $y + imm$, a następnie przypisaniu jej do $x$.

#### Wykonanie operacji

1. Przekazanie numeru instrukcji do rejstru rozkazów
2. Oczytanie instrukcji przez rejestr rozkazów i przesłanie inforacji o niej do pliku rejestrów, oraz informacji, ze bedzie wykonywac dodawanie do ALU
3. Odczytanie wartości zmiennych $y$ i $imm$ przez rejestr plików, oraz zdefiniowanie, ze będzie zapisać dane do $x$
4. Rozszerzenie reprezentacji $imm$ do 32-bitów, zeby mozna było ją dodać do $y$
5. Przekazanie $y$ oraz $imm$ do ALU, gdzie zostaną dodane
6. Odczytanie danych z pamięci pod wyliczonym w kroku 5. adresem i przekazanie ich do pliku rejestrów, gdzie zostaną zapisane jako $x$
7. Instrukcja nie zmieniała przebiegu sterowania, więc zwiększamy wartość licznika rozkazów o 32-bity (długość pojedyńczej instrukcji).