Metody realizacji języków programowania/MRJP Ćwiczenia 8

Autor: Paweł Górecki (gorecki@mimuw.edu.pl)

Zadanie 1

Zapisz algorytm

• sortowania bąbelkowego
• lub wyszukiwania binarnego

w postaci grafu przepływu. Zastosuj podstawowe metody optymalizacji.

Zadanie 2

Dla grafów przepływu z poprzedniego zadania. Przekształć do postaci SSA przy założeniu, że każdy element tablicy zajmuje 4 bajty, czyli np.: instrukcja

x:=a[i]

powinna być zastąpiona przez

t:=4*i
x:=a[t]

gdzie t jest nową zmienną. Zastosuj przemieszczanie kodu oraz znajdź kandydatów na zmienne indukcyjne i zredukuj moc.

Zadanie 3

Przekształć poniższy program (w postaci grafu przepływu) do postaci SSA i zastosuj znane Ci optymalizacje.