Metody realizacji języków programowania/MRJP Ćwiczenia 8: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 14: Linia 14:
 
  x:=a[i]
 
  x:=a[i]
 
powinna być zastąpiona przez  
 
powinna być zastąpiona przez  
  t=4*i
+
  t:=4*i
  x=a[t]
+
  x:=a[t]
 
gdzie t jest nową zmienną.
 
gdzie t jest nową zmienną.
 
Zastosuj przemieszczanie kodu
 
Zastosuj przemieszczanie kodu

Aktualna wersja na dzień 21:23, 1 paź 2006

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.

W8bloki.jpg