Zadanie 1

Jednym z klasycznych usprawnień programów jest wynoszenie stałych podwyrażeń poza pętle. Jednakże wymaga to ustalenia które podwyrażenia są stałe. Podwyrażania stałe definiujemy jako takie podwyrażenia których wartości po obliczeniu w pierwszej iteracji nie zmieniają się w kolejnych iteracjach pętli. Może się zdażyć że ponowne wykonanie pętli da nam inną wartość tekiego podwyrażenia, istotne jest tylko by wartość nie zmieniała w takcie każdego pojedyńczego wykonania pętli. Rozważmy poniższą pętlę:

int z = 0;
void foo() { z++;}
....
{
s1 = 0;
s2 = 0;
b = random();
for(i = 0; i < 100; i++) {
    foo();
    k = 5;
    c = b;
    d = c + k;
    f = random();
    g = d + z;
    s1 += f;
    s1 += g;
    s2 += d;
}
}

Które podwyrażenia w tej pętli są stałe. Jakie podwyrażenia zostaną uznane za stałe przez następujące metody:

jawne stałe i zmienne do których nie ma przypisania wewnątrz pętli
co wyżej plus wartości funkcji ze stałymi argumentami
jawne stałe i zmienne lokalne (niewidoczne dla innych funkcji) do których nie ma przypisania wewnątrz pętli
jak wyżej plus uznajemy za stałe wyrażenia arytmetyczne ze stałymi argumentami

Które z powyższych metod są poprawne (tzn. znalezione podwyrażenia faktycznie są stałe)? Podać przykłady pętli z podwyrażniami stałymi których nie znajdą te z powyższych metod które są poprawne.

Zadanie 2

Zakładamy że program napisamy w klasycznym języku algorytmicznym w 80% wykonuje operacje na zmiennych prostych zaś w 20% wywołania funkcji. Dodatkowo zakładamy że operacja na zmiennej prostej wymaga przeciętnie dwu instrukcji maszynowych, zaś wywołanie funkcji pięciu. Jak się zmieni ilość wykonywanych instukcji jeśli do języka dodamy wsparcie obiektowe, tak że wywołamie metody będzie wymagało trzech dodatkowych instrukcji w porównaniu z wywołaniem funkcji i zamienimy wszystkie wywołania funkcji na wywołania metod. Jak się zmieni ilość wykonywanych instrukcji jeśli chcemy przejść do "czysto obiektowego" języka tak że każda operacja oryginalnego programu stanie się wywołaniem metody, przy tym jeśli operacja dotyczyła zmiennej prostej to zakładamy że treść metody wykona tę operację, tak że narzut składa się z kosztu wywołania metody, zaś jeśli operacja była wywołaniem funkcji to zamieniamy ją na wywołanie metody.

Uwaga: powyżej piszę o wykonywanych operacjach ponieważ proporcje instukcji w treści programu często znacznie się różnia od proporcji w trakcie wykonania. Po prostu niektóre (zwykle małe) fragmenty programu są znacznie częściej wykonywane niż inne części programu.

Zadanie 3

Zakładamy że przeciętnie interpreter na wykonanie prostej operacji potrzebuje 200 instrukcji maszynowych. Ze względu na duży czas wykonania prostych operacji do języków interpretowanych zwykle dodaje się funkcje wbudowane które w miarę wydajnie wykonują bardziej złożone operacje. Zakładamy że 80% wykonywanych operacji to operacje proste, zaś 20% wywołania funkcji wbudowanych. Aby przyspieszyć wykonanie programu chcemy go skompilować. Przy tym zakładamy że proste operacje da się przetłumaczyć przeciętnie do 3 instrukcji maszynowych, zaś funkcje wbudowane musimy dalej wywoływać. Przy tym przecietne wywołanie funkcji wbudowanej przez interpreter wymaga 1000 instrukcji, zaś kompilator może oszczędzić 200 instrukcji z kosztu wywołania. Jak kompilacja zmieni liczbę wykonywanych instrukcji?