---
# System prepended metadata

title: 'Ćwiczenia 5, grupa śr. 12-14, 27 marca 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ćwiczenia 5, grupa śr. 12-14, 27 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   |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- | 
Mikołaj Balwicki         |   X   |  X   |  X   |  X   |     |  X   |  X   |     |     | 
Małgorzata Galińska      |   X   |  X   |     |     |     |  X   |   ==X==  |  X  |     |
Maria Hreniak            |      |     |     |     |     |     |     |     |     |
Jakub Jankowski          |  X    |  X   |     |     |     |   X  |  X   |  ==X==   |   X  |
Mikołaj Kalitka          |   X   |  X   |     |     |     |  X   |  X   |  X   |     |
Julia Konefał            |    X  |     |     |     |     |   X  |  X   |  X   |  X   |
Julia Kulczycka          |       ==X==   |  X   |     |     |   |   X  |   X  |  X   |  X   |
Cecylia Łyjak            |      |     |     |     |     |     |     |     |     |
Adam Majchrowski         |   X   |  X   |     |     |     |  ==X==   |  X   |  X   |  X   |
Piotr Mańkowski          |      |     |     |     |     | X   | X   |==X== |     |
Piotr Salamon            |   X   |  X   |     |   |     | X    |   X  |  X  |     |
Maciej Szałasz           |   X   |   X  |     |     |     |   X  |  X   |  X   |  ==X==   |
:::




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



## Zadanie 1
:::success
Autor: Julia Kulczycka	
:::
### Co to jest analiza use-definition?
*Intuicja:* Każde użycie zmiennej jest połączone z miejscem, w którym została zdefiniowana.
Analiza "use-definition" pozwala na ustalenie, skąd pochodzi wartość zmiennej oraz gdzie jest wykorzystywana. 
Zalety pod kątem optymalizacji: 
- pominięcie zbędnych obliczeń (np. widząc, że na jedynej ścieżce obliczeń zmienna jest redefiniowana przed wykorzystaniem jej, będziemy mogli pominąć poprzednie przypisanie)
- zwolnienie zmiennych, które nie będą już używane (możemy zobaczyć, kiedy zmienna jest używana "ostatni raz" i dalsze redefiniowanie jej nie zmieni działania programu).

### Analiza
Z poprzedniej listy:
![image](https://hackmd.io/_uploads/HkpeUZxJR.png)

|   | x | y | z | i | t |
|---|---|---|---|---|---|
| 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: Piotr Salamon

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

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

RDin(1) = {}
RDin(2) = RDout(1)
RDin(3) = RDout(2)
RDin(4) = RDout(3) ∩ RDout(8)
RDin(5) = RDout(4)
RDin(6) = RDout(5)
RDin(7) = RDout(6)
RDin(8) = RDout(7)
RDin(9) = RDout(4)



RDin(1) = {}
RDin(2) = RDout(1) = {}
RDin(3) = RDout(2) = {}
RDin(4) = RDout(3) ∩ RDout(8) = {} ∩ RDout(8) = {}
RDin(5) = RDout(4) = {}
RDin(6) = RDout(5) = {x + y}
RDin(7) = RDout(6) = {}
RDin(8) = RDout(7) = {}
RDin(9) = RDout(4) = {}

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

## Zadanie 3
:::success
Autor: Mikołaj Balwicki	
:::

Wprowadźmy następujące oznaczenia:
(x, a) – wyrażenie a jest dostępne w zmiennej x
AEV∘, AEV• to funkcje z Lab w $\mathcal{P}(Var \times Exp)$
FV(a) – zbiór zmiennych występujących w wyrażeniu a, podzbiór Var

killAEV([x:=a]l) = { (x’, a’) ∈ AEV∘ \| x’ = x or x ∈ FV(a’) }
genAEV([x:=a]l) = { (x, a) jeżeli x ∉ FV(a) }

AEV∘(l) = ∅ jeżeli l = init(S*)
AEV∘(l) = ⋂{AEV•(l’) \| (l’, l) ∈ flow(S*)}
AEV•(l) = (AEV∘(l) \ killAEV(l)) ∪ genAEV(l)


## Zadanie 4
:::success
Autor: Mikołaj Balwicki	
:::
![image](https://hackmd.io/_uploads/H1FchickA.png)
![image](https://hackmd.io/_uploads/rJfdnjcyA.png)
W powyższej tabelce para postaci (a, ?), gdzie a należy do zbioru zmiennych reprezentuje wszystkie pary postaci (a, exp), gdzie exp należy do zbioru wszystkich wyrażeń.

Jeśli: Z -- zbiór zmiennych, Exp -- zbiór wyrażeń w programie suma z {?}.
$Z\times Exp$ --- zbiór wszystkich faktów, czyli wartość początkowa zmiennych w algorytmie liczącym największy punkt stały.




## Zadanie 5
:::danger
Autor: dodeklarować!
:::

## Zadanie 6
:::success
Autor: Adam Majchrowski	
![image](https://hackmd.io/_uploads/rJQuZK-1R.png)

:::

## Zadanie 7
:::success
Autor: Małgorzata Galińska	
:::
![image](https://hackmd.io/_uploads/HJ1lJh5yA.png)

Kod trójkowy z użyciem 2 rejestrów tymczasowych t1, t2:
```t1 := a * a
t2 := t1 * a

x := t2

t1 := a * b
t2 := t1 * a
t1 := t2 * 4

x := x + t1

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

t1 := b * b
t2 := t1 * b

x := x + t2
```

Kod trójkowy z użyciem dodatkowego rejestru mem:
Zdefiniujmy:
x := a[i] jest tym samym co t := a + i,  x := *t
a[i] := x jest tym samym co t := a + i,  *t := x

wyliczenie wartości i zapisanie ich w tablicy:
```t := a * a
t := t * a
mem[0] := t
t := 4 * a
t := t * a
t := t * b
mem[1] := t
t := 4 * a
t := t * b
t := t * b
mem[2] := t
t := b * b
t := t * b
mem[3] := t
```
odczytanie wartości i dodanie ich do wyniku:
```
t := mem[0]
r := mem[1]
t := t + r
r := mem[2]
t := t + r
r := mem[3]
t := t + r
```


## Zadanie 8
:::success
Autor: Jakub Jankowski
![image](https://hackmd.io/_uploads/S1ixfKW1R.png)


:::

## Zadanie 9
:::success
Autor: Maciej Szałasz	
:::

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

### Znaczenie instrukcji $x = *(y+imm)$
![image](https://hackmd.io/_uploads/HJElNcqyA.png)

### Znaczenie instrukcji $x = *(y+imm)$
Przypisujemy wartość z adresu $y+imm$ do zmiennej $x$.

### Kolejne kroki
1. Pobranie instrukcji z instruction memory i przekazanie informacji dalej
![image](https://hackmd.io/_uploads/S1U9ScqkC.png)

2. Odczytanie wartości $y$, przekazanie rodzaju operacji do **ALU**, oraz rozrzeszenie $imm$ do  32-bitów, i przekazanie go wraz z $y$ do ALU.
![image](https://hackmd.io/_uploads/Symf895yR.png)

3. Wykonanie operacji dodawania $y+imm$ i przekazanie wyniku do **Data Memory**, 
![image](https://hackmd.io/_uploads/SyR1Oq5JR.png)

4. Odczytanie wartości z adresu $y+imm$ y przekazanie jej do **WD3**
5. przekazanie do **A3** adresu $x$, oraz ustawienie **WE3** na 1 w celu zapisania wartości.
![image](https://hackmd.io/_uploads/H1rXu951C.png)

