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

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


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

:::

## Zadanie 7
:::success
Autor: Małgorzata Galińska
:::

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

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

:::

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


### Znaczenie instrukcji $x = *(y+imm)$

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

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.

3. Wykonanie operacji dodawania $y+imm$ i przekazanie wyniku do **Data Memory**,

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.