Przetłumacz poniższy fragment programu na kod czwórkowy i sprowadź ten kod do postaci SSA. Wstaw funkcje \(\phi\) tylko tam, gdzie jest to konieczne. Pamiętaj o zmianie nazw (dodaniu indeksów) zmiennych.
while (a != 0) { if (a < 0) { b = 1; } else { b = -1; } a = a + b; }
Dana funkcja
int g(int a,b,c,d,e,f) { while(e) { a = b+c; d = d-c; e=a-f; if(e) f = a-d; else { b = d+f; e = a-c; } b = d+c; } return b; }
Maszyna docelowa: 3 rejestry ogólnego przeznaczenia, wskaźnik stosu i ramki, operacje
LOAD Ri, m -przesłanie z pamieci do rejestru
STORE Rj, m - przeslanie z rejestru do pamieci
SUB Ri, RJ - Ri := Ri - Rj
ADD analogicznie
a. Wygenerować kod czwórkowy, zidentyfikować bloki proste narysować graf przepływu i określić zmienne zywe na początku i końcu każdego bloku prostego.
b. Wygenerować kod maszynowy dla pierwszego bloku {a=b+c itd} metodą opisów rejestrów i wartości
Dana funkcja
unsigned f(unsigned a) { int b = a+1; { unsigned a = b+1; unsigned c = a/2; if(c>0) return f(c); else return 0; } }
Maszyna docelowa: 1 rejestr ogólnego przeznaczenia A, wskaźnik stosu i ramki, operacje
LOAD A, m ;przesłanie z pamieci do rejestru
STORE A, m ; przeslanie z rejestru do pamieci
SUB A, m ; A := A - M[m]
INC A ; A := A+1
SHL A ; A := 2*A
SHR A ; A := A/2
inne operacje analogicznie
a. Wygenerować kod czwórkowy, zidentyfikować bloki proste narysować graf przepływu i określić zmienne zywe na początku i końcu każdego bloku prostego.
b. Wygenerować kod dla opisanej maszyny
Podaj przykład programu w kodzie czwórkowym, który po wykonaniu podanego poniżej
ciągu optymalizacji uprości się do
return 42;
Optymalizacje powinny zostać wykonane w następującej kolejności:
1. Propagacja kopii
2. Eliminacja martwego kodu
3. Eliminacja wspólnych podwyrażeń
4. Propagacja stałej
5. Zwijanie stałej
6. Propagacja stałej
7. Zwijanie stałej
8. Propagacja stałej
9. Eliminacja martwego kodu
10. Zwijanie stałej
11. Propagacja stałej
12. Eliminacja martwego kodu
Uwaga: w każdym kroku daną optymalizację można w razie potrzeby zastosować więcej niż
raz. Tym niemniej obowiązuje kryterium długości kodu wyjściowego.
Dana jest maszyna z dwoma rejestrami R0, R1 i instrukcjami:
Ri:=Ri-Rj odejmowanie zawartości Rj od zawartości Ri
Ri:=Ri/Rj dzielenie zawartości Ri przez zawartosc Rj
Ri:=id
zaladowanie do Ri wartości zmiennej
id:=Ri
zapisanie na zmiennej zawartości rejestru Ri
Ri:=Rj
przepisanie do Ri zawartości Rj
gdzie "i", "j" to 0 lub 1 a "id" to identyfikator zmiennej.
Korzystając z metody tablicy opisów wartości i rejestrów wygeneruj możliwie dobry kod dla
ciągu instrukcji, po którym żywe są zmienne "a" i "b":
x:=a; a:=b/a; b:=a-x; a:=b/x
Dane są deklaracje:
var i,r:integer;
a,b:array [0..n] of integer;
Zakładając, że liczba całkowita zajmuje cztery adresowalne komórki pamięci, wygeneruj kod czwórkowy i narysuj graf przepływu sterowania dla fragmentu programu:
i:=1; while a[i]=b[i] do i:=i+1; r:=a[i]-b[i]
Przyjmując, ze na zakończenie tego fragmentu żyje tylko zmienna "r", zoptymalizuj wygenerowany wcześniej kod czworkowy, nazywając każdą z wykonanych optymalizacji.
Uwaga: Składnia Pascalowa, czyli "=" oznacza porównanie, a ":=" - przypisanie.
Dana funkcja:
int f(int n) { int u=0, v=1, i=2, t; while(i<n) { t=u+v; u=v; v=t; i=i+1; } return v; }
a. Wygeneruj kod czwórkowy w postaci SSA, podziel go na bloki proste;
narysuj graf przeplywu sterowania.
b. Zastosuj (i nazwij) znane optymalizacje w celu ulepszenia kodu
Rozważmy funkcję
void sort(int n) { int i,j,t; for (i = 0; i < n; i++) for (j = n-1; j > i; j--) if (A[j-1] > A[j]) { t = A[j-1]; A[j-1] = A[j]; A[j] = t; } }
a. Wygeneruj kod czwórkowy dla powyższej procedury (bez protokołu wejścia i powrotu). Zidentyfikuj bloki proste i narysuj graf przepływu sterowania. Uwaga: odwołanie do elementu tablicy wymaga podania offsetu tego elementu w bajtach, int zajmuje 4 bajty, tablice indeksowane od 0.
b. Wykonaj kilka kroków optymalizacji uzyskanego kodu czwórkowego (wystarczy zastosować dokładnie 5 różnych rodzajów optymalizacji i je odpowiednio opisać.)
Maszyna docelowa ma dwa rejestry ogólnego przeznaczenia R0,R1
oraz instrukcje (dla i,j=0,1, m oznacza komórkę pamięci):
Ri = Rj
Ri = m
m = Rj
Ri = Ri op Rj
"op" jest pewna operacją arytmetyczną; instrukcje operujące wyłącznie na rejestrach mają koszt 2, instrukcje z dostępem do pamięci mają koszt 7.
Rozważmy blok prosty, na końcu którego żywa jest (tylko) zmienna e:
c = b; a = a op c; d = b op a; e = d op e; e = a op e; a = c op b; e = a op e;
A. Wskaż zmienne żywe przed każdą z instrukcji.
B. Korzystając z metody opisu rejestrów i wartości, wygeneruj możliwie najlepszy (w sensie kosztu) kod dla tego bloku. Do komórek pamięci przechowujących zmienne można się odwoływać przez nazwę zmiennej (np. R0 = a).
Uwaga: na tym etapie należy generować kod maszynowy dokładnie dla podanego kodu czwórkowego, bez żadnych optymalizacji.
C. Jakie optymalizacje można zastosować do tego kodu czwórkowego? W jaki sposób wpłyną one na wynikowy kod maszynowy?