Faza syntezy Synteza kodu i środowisko czasu wykonywania Języki formalne i techniki translacji - Wykład 12 Generowanie kodu pośredniego. Optymalizacja kodu. Maciek Gębala Generowanie kodu wynikowego. 15 maja 2013 Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Po co język pośredni? Języki pośrednie Języki pośrednie mogą być: Załóżmy że mamy n języków wysokiego poziomu i k rodzajów zorientowane na maszynę docelową (uwzględniające fizyczne maszyn docelowych. właściwości maszyn: liczba rejestrów, organizacja pamięci, Pisząc kompilatory bezpośrednie musimy stworzyć nk różnych współbieżność); implementacji. zorientowane na język programowania (np. bytecode Java-y); Korzystając z kodu pośredniego piszemy n przodów kompilatora uniwersalne (np. kod trójadresowy liniowa reprezentacja i osobno k tyłów kompilatora. drzewa wyprowadzenia, prosty język podobny do języka Aatwiej też wprowadzać nowe języki i nowe rodzaje maszyn. maszynowego). Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Kod trójadresowy - instrukcje Kod trójadresowy - instrukcje Instrukcje przypisania z wykorzystaniem binarnego operatora x ! y ć% z; Instrukcje związane z podprogramami: Instrukcje przypisania z wykorzystaniem unarnego operatora Przekazanie parametru param x; x ! ć%y; Wywołanie podprogramu call P, n; Instrukcje kopiowania x ! y; Powrót z procedury return; Skoki bezwarunkowe goto L; Powrót z funkcji ze zwróceniem wartości return y. Skoki warunkowe if x <" y goto L; Podprogramy wymagają implementacji stosu na gromadzenie Przypisania indeksowane x ! y[i] lub x[i] ! y; argumentów i wywołań. Przypisania z użyciem adresów i wskazników x ! &y, x ! "y lub "x ! y; Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Przykład przekładu Generowanie kodu wynikowego Język zródłowy Ostatnią fazą kompilatora jest generator kodu wynikowego. Z kodu pośredniego wytwarzany jest równoważny kod wynikowy. Trójadresowy kod pośredni Kod wynikowy musi być poprawny i efektywny. i ! n W analizie algorytmów generowania i optymalizacji kodu loop: wynikowego pomocne są grafy przepływu. if i < 1 goto end t2 ! 2 " i Najważniejsze problemy przy generowaniu kodu wynikowego to a[t2] ! i wybór rozkazów i przydział rejestrów. i ! i - 1 goto loop end: Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Graf przepływu Przydział rejestrów Blok podstawowy fragment kodu wykonywany zawsze od pierwszej do ostatniej instrukcji. Graf przepływu wierzchołkami są bloki podstawowe, krawędzie skierowane odzwierciedlają przepływ sterowania. Właściwy przydział rejestrów ma ogromne znaczenie dla efektywności działania programu wynikowego. Przykład Operacje na rejestrach są zawsze szybsze ale rejestrów jest x ! a niewiele. y ! b Rejestry mogą być różnego rodzaju dedykowane do W: if x = y goto F określonych operacji. if x < y goto E x ! x - y goto W E: y ! y - x goto W F: stop Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Optymalizacja kodu Optymalizacja kodu Ulepszenia mogą być wykonane na poziomie: Optymalizacja kodu to przekształcenie mające na celu poprawę efektywności kodu wynikowego. kodu zródłowego profilowanie programu, przekształcenia pętli; Celem optymalizacji jest uzyskanie szybszego lub mniejszego reprezentacji pośredniej ulepszanie pętli i wywoływania kodu. procedur, obliczanie adresów; Optymalizacja opiera się na analizie przepływu sterowania i kodu wynikowego przydział rejestrów, idiomy maszynowe, przepływu danych. szeregowanie instrukcji. Optymalizacja musi zachować semantykę programu. Optymalizacja powinna być opłacalna zauważalny efekt Optymalizacja może być lokalna (na poziomie bloków podstawowych) powinien odpowiadać nakładowi pracy. lub globalna (ponad blokami podstawowymi). Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Optymalizacja kodu Optymalizacja kodu Idiomy maszynowe: Jeżeli jakieś wyrażenie w pętli nie zmienia wartości w trakcie zastępujemy ; przebiegu pętli to kod obliczający wartość tego wyrażenia można Tożsamości algebraiczne: 0 x !! 0, 1 x !! x; wyciągnąć przed pętlę. Redukcja siły operatora: 2 x !! x + x, 8 x !! x >> 3; Pętlę można rozwinąć jeżeli wykonanie jej bez skoków zajmuję mniej miejsca (pętle o stałym niewielkim przebiegu). Zwijanie stałych: zastępujemy przez ; Funkcje wykonujące niewielkie obliczenia można zamiast Eliminacja wspólnych podwyrażeń; wywoływać wkleić bezpośrednio do kodu (rozwijanie funkcji). Usuwanie martwego kodu. Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Środowisko czasu wykonania Zmienne nielokalne Problem dostępu do zmiennych nielokalnych występuje w Dostęp do nazw nielokalnych. językach dopuszczających wielokrotne zagnieżdżanie Przekazywanie parametrów. podprogramów i deklarowanie zmiennych lokalnych. Dynamiczny przydział pamięci. Problemem jest określenie która zmienna o tej samej nazwie jest właściwa: trzeba określić zakresy widzialności. Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Parametry podprogramów Przekazywanie parametru przez wartość Tryby przekazywania parametrów wejściowy (IN) parametr zawiera wartość stałej, zmiennej lub Najprostsza metoda przekazywania parametrów. wyrażenia; Wykorzystywana do przekazywania parametrów tylko w trybie wyjściowy (OUT) program zwraca za pośrednictwem wejściowym. wyrażenia wartość; Domyślna w większości języków. wejściowo-wyjściowy (IN-OUT) program zarówno otrzymuje jak Podprogram ma dostęp tylko do kopii zmiennych (brak efektów i zwraca wartość za pośrednictwem parametru. ubocznych). W przypadku dużych obiektów metoda bardzo kosztowna. Metody przekazywania parametrów: przez wartość, przez referencję, przez rezultat, przez kopiowanie i odtwarzanie, przez nazwę. Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Przekazywanie parametru przez referencję Przekazywanie parametru przez rezultat Wykorzystywana do przekazywania parametrów tylko w trybie Wykorzystywana do przekazywania parametrów tylko w trybie wyjściowym. wejściowo-wyjściowym. Dostępna w niewielu współczesnych językach (Ada), w innych Parametr jest przekazywany jako wskaznik (referencja) do zastępowana funkcjami lub referencjami. miejsca przechowywania aktualnego parametru. W wywołaniu parametr nie ma określonej wartości. Nie ma problemu z dużymi obiektami ale dostęp do parametrów jest wolniejszy (adresowanie pośrednie). Parametr musi być zmienną. Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Przekazywanie parametru przez kopiowanie Przekazywanie parametru przez nazwę i odtwarzanie Podprogram jest traktowany jako makro. Podprogram jest rozwijany tak jakby był w miejscu wywołania. Hybryda metod przekazywania przez wartość i referencję. Parametry są tekstowo wstawiane w miejsce parametrów Po powrocie z podprogramu wartości są przepisywane. formalnych. Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania Organizacja pamięci Zarządzanie pamięcią sterta Pamięć jest w czasie wykonywania programu dzielona na cztery obszary: Dynamiczne przydzielanie pamięci. 1 Zwalnianie pamięci obszar kodu jawne uruchamiane przez programistę (problemy z wiszącymi 2 obszar danych statycznych referencjami i niezwolnioną pamięcią (Memory Leak)). 3 stos niejawne uruchamiane automatycznie (Garbage Collector). 4 sterta Fragmentacja i scalanie pamięci. Metody przydziału pamięci. Obszary stosu i sterty zmieniają swój rozmiar w trakcie działania programu. Maciek Gębala Synteza kodu i środowisko czasu wykonywania Maciek Gębala Synteza kodu i środowisko czasu wykonywania