---
# System prepended metadata

title: 'Ćwiczenia 5, grupa cz. 16-18, 28 marca 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ć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

![image](https://hackmd.io/_uploads/B1ndiZQ1R.png)

![image](https://hackmd.io/_uploads/SyUaib71C.png)

![image](https://hackmd.io/_uploads/r1Vqi-Qy0.png)


#### 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	
:::

![5.1](https://hackmd.io/_uploads/SJXbiWmk0.png)


#### 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

![image](https://hackmd.io/_uploads/r1i6NGQk0.png)

#### $$ 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	
:::
![z8](https://hackmd.io/_uploads/Byz2o-7y0.png)

<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
![obrazek na syk](https://hackmd.io/_uploads/B10Hh-XyR.png)

- **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).


