# Ćwiczenia 13, grupa śr. 17-19, 24 maja 2023

###### tags: `ASK23` `ć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 | 10 |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Kamila Goszcz | X | X | X | X | X | | | | | |
| Mateusz Materek | | | | | | | | | | |
:::

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

## Zadanie 1
:::success
Autor: Kamila Goszcz
:::


__aliasing pamięci__ - opisuje sytuację w której do obszaru pamięci możemy dostać się poprzez różne zmienne, a co za tym idzie modyfikacja pamięci pod jednym ze wskaźników może wpływać na wartości innych zmiennych

__restrict__ - słowo kluczowe informujące o tym, że aktualny program będzie jedynym użytkownikiem danej zmiennej

Nie możemy zoptymalizować `swapa` ze względu na to, że `xs` oraz `ys` mogą na siebie nachodzić, wtedy zmieniając jedną z wartości może zmienić się też druga z nich. Takiego przypadku nie uwzględniamy w `swap2`, a co za tym idzie programy nie są równoważne

## Zadanie 2
:::success
Autor: Kamila Goszcz
:::


#### Ile razy zostanie zawołana funkcja `my_strlen` w funkcji `my_index` i dlaczego?

Zostanie wywołana dokładnie tyle razy ile wynosi długość `s`, kompilator nie może zoptymalizować tej pętli, ponieważ nie wie, jak wygląda jej ciało oraz nie wie czy sama zmienna `s` nie ulegnie zmianie w trakcie trwania programu, nie może zate założyć, że `my_strlen(s)` jest stałą

#### Dodaj atrybut `pure` do funkcji `my_strlen`. Czemu tym razem kompilator był w stanie lepiej zoptymalizować funkcję `my_index`? Czym charakteryzują się czyste funkcje?

Calls to functions that have no observable effects on the state of the program other than to return a value may lend themselves to optimizations such as common subexpression elimination. Declaring such functions with the pure attribute allows GCC to avoid emitting some calls in repeated invocations of the function with the same argument values.

The pure attribute prohibits a function from modifying the state of the program that is observable by means other than inspecting the function’s return value. However, functions declared with the pure attribute can safely read any non-volatile objects, and modify the value of objects in a way that does not affect their return value or the observable state of the program.

#### Następnie uzupełnij ciało funkcji `my_strlen` tak, by wykonywała to samo co `strlen`

__attribute__((pure))
size_t my_strlen(const char *s) {
    size_t i = 0;
    while (*s++)
        i++;
    return i;
}

#### Następnie usuń atrybut `pure` i dodając słowo kluczowe `static` zawęź zakres widoczności funkcji do bieżącej jednostki translacji

(* godbolt *)

#### Co się stało w wyniku przeprowadzenia inliningu? Czy kompilatorowi udało się samemu wywnioskować, że funkcja jest czysta?

Kompilator wstrzyknął w miejsce występowania wywołania funkcji jej zawartość, zauważył wtedy, że wartość `my_strlen(s)` nie zmienia się co pozwoliło mu założyć, że funkcja jest czysta

## Zadanie 3
:::success
Autor: Kamila Goszcz
:::


### Kod z godbolta

foobar(long*, unsigned long, long, long):
        test    rsi, rsi
        je      .L1						// if (rsi == 0) ret
        sub     rdx, rcx				// rdx = rdx - rcx
        lea     rax, [rdi+rsi*8]		// rax = [rdi+rsi*8]
        imul    rdx, rdx				// rdx = rdx * rdx
.L3:
        mov     QWORD PTR [rdi], rdx	// [rdi] = rdx
        add     rdi, 8					// rdi = rdi + 8
        add     rdx, 7					// rdx = rdx + 7
        cmp     rdi, rax				
        jne     .L3						// rdx == rax ? ret : goto .L3
.L1:
        ret
			
foobar:
        testq   %rsi, %rsi
        je      .L1
        subq    %rcx, %rdx
        leaq    (%rdi,%rsi,8), %rax
        imulq   %rdx, %rdx
.L3:
        movq    %rdx, (%rdi)
        addq    $8, %rdi
        addq    $7, %rdx
        cmpq    %rax, %rdi
        jne     .L3
.L1:
        ret

void foobarOpt(long a[], size_t n, long y, long z) {
    if (n == 0)
        return;
    
    y = (y - z);
    y = y * y;
    long* x = a;
    long* last = &a[n];
    do{
        *x = y;
        y = y + 7;
        x++;
    }
    while (x != last);
}

### Niezmiennik pętli
własność prawdziwa przed i po zakończeniu każdej iteracji pętli - w naszym przypadku będzie to wartość `x, x^2, y-z`

### Które wyrażenia zostały wyniesione przed pętlę i dlaczego?
Zauważmy, że `x = y - z` w każdej iteracji pętli przyjmie taką samą wartość, a co za ty idzie możemy wyciągnąć całe wyrażenie przed ciało pętli.

### Które wyrażenia uległy osłabieniu?

long j = 7 * i;
a[i] = j + x * x;

kosztowna instrukcja mnożenia `7 * i` została zamieniona na znacznie tańszą instrukcję dodawania `7`

a[i] = y;
y = y + 7;

## Zadanie 4
:::success
Autor: Kamila Goszcz
:::

__zamiana pętli__ - optymalizacja polegająca na zamianie kolejnością pętli zewnętrznej i wewnętrznej

__łączenie pętli__ - optymalizacja polegająca na zredukowaniu liczby pętli w programie przez łączenie ze sobą ciał pętli o tych samych warunkach

__usuwanie zmiennych indukcyjnych__ - optymalizacja polegająca na zmniejszeniu liczby wyrażeń obliczanych w każdej iteracji pętli

void compute2(long *a, long *b, long k) {
    long n = 1 << k;
    for (long i = 0; i < n; i++)
        a[i * n] = a[i] = 0;
    for (long i = 1; i < n; i++)
        for (long j = 1; j < n; j++)
            a[j * n + i] = i * j;
    for (long i = 1; i < n; i++)
        for (long j = 1; j < n; j++)
            b[i * n + j] = a[i * n + j] 
                         + a[(i - 1) * n + (j - 1)];
}

1)
| j\i | 0 | 1 | 2 | 3 |
| --- | - | - | - | - |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |

2)
| j\i | 0 | 1 | 2 | 3 |
| --- | - | - | - | - |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 |
| 2 | 0 | 2 | 4 | 6 |
| 3 | 0 | 3 | 6 | 9 |

3)
| j\i | 0 | 1 | 2 | 3 |
| --- | - | - | - | -- |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 |
| 2 | 0 | 2 | 5 | 8 |
| 3 | 0 | 3 | 8 | 13 |

void compute2opt(long *a, long *b, long k) {
    long n = 1 << k;
    a[0] = 0;
    for (long i = 1; i < n; i++){
		a[i * n] = a[i] = 0;
        for (long j = i; j < n; j++){
			long idx = i * n + j;
            a[idx] = i * j;
			a[j * n + i] = a[idx];
            b[idx] = a[idx] 
                     + a[idx - n - 1];
			b[j * n + i] = b[idx];
		}
	}
}

## Zadanie 5
:::success
Autor: Kamila Goszcz
:::


neigh: // rdi a, rsi n, rdx i, rcx j
        subq    $1, %rdx              // rdx = i-1
        leaq    -1(%rcx), %r8         // r8 = j-1
        addq    $1, %rcx              // rcx = j+1
        imulq   %rsi, %rdx            // rdx = n * (i-1)
        leaq    (%rdx,%rsi,2), %rsi   // rsi = n*2 + n*(i-1) = n*(i+1)
        leaq    (%rdx,%r8), %r9       // r9 = j-1 + n*(i-1)
        addq    %rcx, %rdx            // rdx = n*(i-1) + j+1
        movq    (%rdi,%rdx,8), %rax   // rax = a[n*(i-1) + j+1]
        movq    %rsi, %rdx            // rdx = n*(i+1)
        subq    %rcx, %rsi            // rsi = n*(i+1) - j+1
        addq    (%rdi,%r9,8), %rax    // rax += a[j-1 + n*(i-1)]
        subq    %r8, %rdx             // rdx = n*(i+1) - j-1
        addq    (%rdi,%rdx,8), %rax   // rax += a[n*(i+1) - j-1] 
        addq    (%rdi,%rsi,8), %rax   // rax += a[n*(i+1) - j+1]
        ret

### Wskaż w poniższym kodzie, które podwyrażenia policzył tylko raz

- (i-1)
- (j-1)
- (j+1)
- (i-1) * n
- (i+1) * n

### Optymalizacja kompilatora

long neigh(long a[], long n, long i, long j) {
    i--;
    size_t j_1 = j-1;
    j++;
    i *= n;
    n *= (i + 2);
    size_t j_2 = j_1 + i;
    i += j;
    long res = a[i];
    i = n;
    n -= j;
    res += a[j_2];
    i -= j_1;
    res += a[i];
    res += a[n];
    return res;
}

long neigh_best(long a[], long n, long i, long j) {
    long idx = n * (i - 1) + (j - 1);
    long res = a[idx];
    idx += 2;
    res += a[idx];
    idx += 2 * n;
    res += a[idx];
    idx -= 2;
    res += a[idx];
    return res;
}

## Zadanie 6
:::danger
Autor:
:::

## Zadanie 7
:::danger
Autor:
:::

nonsense:
        subq    $1, %rsi
        imulq   24(%rdi), %rsi
        movq    16(%rdi), %r8
        movq    (%rdi,%rsi,8), %rax
        movq    32(%rdi), %rsi
        addq    $4, %rax
        leaq    (%rsi,%r8,8), %rsi
        movq    %rsi, (%rdx)
        movq    %rax, (%rcx)
        ret

digraph G {
node [shape = rectangle, style = filled, fillcolor = darkslategray1]
load [fillcolor = darkturquoise]
store [fillcolor = white]
mul
add
sub
lea
load2 [label = "load", fillcolor = darkturquoise]
load3 [label = "load", fillcolor = darkturquoise]
load4 [label = "load", fillcolor = darkturquoise]
store2 [label = "store", fillcolor = white]
{rank = same; store;store2;lea;add}
node [shape = box, style = filled, fillcolor = gray]
rsi [label = "%rsi"]
rdi [label = "%rdi"]
rdx [label = "%rdx"]
rcx [label = "%rcx"]
rsi2 [label = "%rsi"]
rax2 [label = "%rax"]
r82 [label = "%r8"]
{rank = same; rsi, rdi, rdx, rcx}
{rank = same; rsi2, rax2, r82}
rsi -> sub
sub -> mul
rdi -> load [color = red]
rdi -> load2
load -> mul [color = red]
load2 -> r82
mul -> load3 [color = red]
rdi -> load3
rdi -> load4
load3 -> add [color = red]
load2 -> lea
load4 -> lea
lea -> rsi2
lea -> store
rdx -> store
add -> store2 [color = red]
rcx -> store2
add -> rax2 
}

Na czerwono zaznaczona jest ścieżka krytyczna.

Load latency = 4
Store latency = 4

## Zadanie 8
:::danger
Autor:
:::

## Zadanie 9
:::danger
Autor:
:::

## Zadanie 10
:::danger
Autor:
:::