# Ćwiczenia 5, grupa cz. 10-12, 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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Borys Adamiak | X | X | | | | ==X== | X | X | X |
Michał Chawar | | | | | | | | | |
Julia Cygan | X | X | | | | X |==X==| X | X |
Maciej Dengusiak | X | X | | | | X | X | X | X |
Patryk Flama | X | X | | | | X | X | X | X |
Szymon Fluder | X | X | | | X | X | X | X | ==X==|
Aleksandra Jędrzejak | X | ==X== | | | | X | X | X | X |
Mikołaj Karapka | X | X | | | | X | X | X | ==X== |
Viktoriia Kashpruk | X | X | | | X | X | X | ==X== | X |
Wiktor Małek | ==X== | X | | | X | X | X | X | X |
Błażej Molik | X | | | | | X | X | X | X |
Andrzej Morawski | | | | | | | | | |
Konrad Oleksy | | | | | | | | | |
Lucjan Pucelak | X | | | | | X | X | X | X |
Aleksandra Sęk | | | | | | X | X | X | X |
Radosław Śliwiński | | | | | | | | | |
Piotr Traczyński | X | | | | | X | X | X | |
Katarzyna Trzos | X | X | | | | X | X | X | X |
Piotr Warząchowski | X | | | | | X | X | X | X |
Olga Zaborska | X | | | | | X | X | X | X |
:::

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

## Zadanie 1
:::success
Autor: Wiktor Małek
:::

zbiory $RD_{in}$ z zadania 6. z listy 3.:

$$RD_{in}(1)=\{(x, ?), (y, ?), (i, ?), (t, ?)\}$$

$$RD_{in}(2)=\{(x, 1), (y, ?), (i, ?), (t, ?)\}$$

$$RD_{in}(3)=\{(x, 1), (y, 2), (i, ?), (t, ?)\}$$

$$RD_{in}(4)=\{(x, 1), (y, 2), (i, 3), (t, ?), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(5)=\{(x, 1), (y, 2), (i, 3), (t, ?), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(6)=\{(x, 1), (y, 2), (i, 3), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(7)=\{(y, 2), (i, 1), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(8)=\{(i, 3), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$$RD_{in}(9)=\{(x, 1), (y, 2), (i, 3), (t, ?), (x, 6), (y, 7), (i, 8), (t, 5)\}$$

$gen_{LV}(l)$ zbiór zmiennych, które są potrzebne do nadpisania zmiennej w etykiecie $l$




Brak zbiorów UD dla linii 1,2,3 bo żadna zmienna nie jest w nich użyta - są to przypisania, UD tych linii są wiec zbiorami pustymi.

$UD(i, 4) = \{3,8\}$

$UD(x, 5) = \{1,6\}$
$UD(y, 5) = \{2,7\}$

$UD(y, 6) = \{2,7\}$

$UD(t, 7) = \{5\}$

$UD(i, 8) = \{3,8\}$

$UD(x, 9) = \{1,6\}$

## Zadanie 2
:::success
Autor: Aleksandra Jędrzejak
:::


1: [𝑥 : = 0]
2: [𝑦 : = 1]
3: [𝑖 : = 1]
4: 𝑤ℎ𝑖𝑙𝑒 [𝑖 < 𝑧] 𝑑𝑜
5: [𝑡 : = 𝑥 + 𝑦]
6: [𝑥 : = 𝑦]
7: [𝑦 : = 𝑡]
8: [𝑖 : = 𝑖 + 1]
𝑜𝑑
9: [𝑦 : = 𝑥]

killAE(l) | genAE(l)
1| {} | {}
2| {} | {}
3| {} | {}
4| {} | {}
5| {} | {x+y}
6| {x+y} | {}
7| {} | {}
8| {} | {} (i+1 zawiera i, generowane są jedynie wyrażenia bez i)
9| {} | {}

AE.entry(1) = { }
AE.exit(1) = AE.entry(1) ∪ { }
AE.entry(2) = AE.exit(1)
AE.exit(2) = AE.entry(2) ∪ { }
AE.entry(3) = AE.exit(2)
AE.exit(3) = AE.entry(3) ∪ { }
AE.entry(4) = AE.exit(3) ∩ AE.exit(8)
AE.exit(4) = AE.entry(4)
AE.entry(5) = AE.exit(4)
AE.exit(5) = AE.entry(5) ∪ { x+y }
AE.entry(6) = AE.exit(5)
AE.exit(6) = AE.entry(6) \ { x+y }
AE.entry(7) = AE.exit(6)
AE.exit(7) = AE.entry(7) \ { }
AE.entry(8) = AE.exit(7)
AE.exit(8) = AE.entry(8)
AE.entry(9) = AE.exit(4)

Wyliczanie algorytmem stałopunktowym:

Dla 1<=i<=9 AE.entry(i) = AE.exit(i) = { }

AE.entry(1) = { }
AE.exit(1) = AE.entry(1) ∪ { } = { }
AE.entry(2) = AE.exit(1) = { }
AE.exit(2) = AE.entry(2) ∪ { } = { }
AE.entry(3) = AE.exit(2) = { }
AE.exit(3) = AE.entry(3) ∪ { } = { }
AE.entry(4) = AE.exit(3) ∩ AE.exit(8) = { }
AE.exit(4) = AE.entry(4) = { }
AE.entry(5) = AE.exit(4) = { }
AE.exit(5) = AE.entry(5) ∪ { x+y } = { x+y }
AE.entry(6) = AE.exit(5) = { x+y }
AE.exit(6) = AE.entry(6) \ { x+y } = { }
AE.entry(7) = AE.exit(6)= { }
AE.exit(7) = AE.entry(7) \ { } = { }
AE.entry(8) = AE.exit(7) = { }
AE.exit(8) = AE.entry(8) = { }
AE.entry(9) = AE.exit(4)= { }

## Zadanie 3
:::success
Autor: Viktoriia Kashpruk
### Zadanie 3

ANALIZA TYPU **MUST, FORWARD**
MUST - jeśli mamy wyrażenie a dostępne w zmiennej x, w jakimś punkcie programu, to ono ma być dostępne w tym punkcie niezależnie od tego którą ścieżką przyszliśmy do tego punktu.
FORWARD - instrukcja bierze zbiór faktów z wejścia przetwatrza je za pomocą zbiorów kill i gen, produkuje fakty na wyściu.
BACKWARD- odwrotnie, bierze fakty prawdziwe na wyjściu programu i przetwarza je za pomocą zbiorów kill i ger na zbiór faktów prawdziwych na wejśćiu.
Dziedzina: VAR X EXP
$kill_{AE}([ x:= a]^{l}) = \{<y, a'> | x \in FV(a')\ \cup y=x\}$ gdzie y jest zmienna w programie
$kill_{AE}([skip]^{l}) = \emptyset$
$kill_{AE}([b]^{l}) = \emptyset$

$gen_{AE}([ x:= a]^{l}) = \{<x, a>\} \quad jeżeli \quad x \notin a \quad wpp. \{\}$
$gen_{AE}([skip]^{l}) = \emptyset$
$gen_{AE}([b]^{l}) = \emptyset$
Postać ogólna równań występująca w tej analize pozostaje bez zmian.




:::

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

:::

## Zadanie 5
:::success
Autor: Szymon Fluder


Dziedzina i postać równań jest taka sama jak poprzednio. Jedyne, co się zmienia to $gen_{LV}$ - nie generujemy zmiennej, jeśli była ona użyta to nadpisania zmiennej zemdlonej.
Analiza jest typu wstecznego - idziemy od końca.
$$
gen_{LV}([x := a]^l) = FV(a) \space \textrm{if} x \in LV_{out}(l) \space \textrm{else} \space \emptyset
$$
:::

## Zadanie 6
:::success
Autor: Borys Adamiak
:::

1) while(b) { ... }

JUMP : if(b == false) goto END
     : { ... }
     : goto JUMP
END  :

2) for(i = 0; i < n; i++) { ... }

     : i := 0
JUMP : if(i >= n) goto END
     : { ... }
     : i := i+1
     : goto JUMP
END  :

3) do { ... } while(b)

JUMP : { ... }
     : if(b == true) goto JUMP
END  :

## Zadanie 7
:::success
Autor: Julia Cygan
$a^3$ + $4a^2b$ + $4b^2a$ + $b^3$ = $(a+b)^3$ + $ab(a + b)$

$t_1$ = a + b
$t_2$ = a + b
$t_1$ = $t_1$ * $t_1$
$t_1$ = $t_1$ * $t_2$
$t_2$ = $t_2$ * a
$t_2$ = $t_2$ * b
$t_1$ = $t_1$ + $t_2$

z dodatkowym rejestrem mem:

$t_1$ = a * a
$t_1$ = a * $t_1$
mem[0] = $t_1$
$t_1$ = a * b
$t_1$ = 4 * $t_1$
$t_1$ = a * $t_1$
mem[4] = $t_1$
$t_1$ = a * b
$t_1$ = 4 * $t_1$
$t_1$ = b * $t_1$
mem[8] = $t_1$
$t_1$ = b * b
$t_1$ = b * $t_1$

odczytanie wartosci:
x = mem[0]
t = x
x = mem[4]
t = t + x
x = mem[8]
t = t + x
t = t + $t_1$
:::

## Zadanie 8
:::success
Autor: Aleksandra Sęk
:::

## Zadanie 9
:::success
Autor: Lucjan Pucelak
:::