Metody realizacji języków programowania/MRJP Wykład 7

From Studia Informatyczne

autor: Łukasz Sznuk (luke@mimuw.edu.pl)

Spis treści

Przekształcanie kodu do postaci SSA

Podział kodu na bloki bazowe

Standardowa definicja bloku bazowego głosi, że jest to fragment kodu, do którego sterowanie wchodzi wyłącznie na początku, a wychodzi przez ostatnią instrukcję. Gdy mówimy o kodzie czwórkowym z poprzedniego wykładu, to jest to kawałek kodu, w którym instrukcja skoku (warunkowego lub nie) może być tylko ostatnim rozkazem oraz taki, że żadna instrukcja z wyjątkiem pierwszego rozkazu w bloku nie jest celem żadnego skoku.

Podział programu na bloki bazowe nie jest więc szczególnie skomplikowany. Pierwsza instrukcja programu jest początkiem pierwszego bloku bazowego. Blok obejmuje kolejne instrukcje i kończy się w pierwszej napotkanej sytuacji z poniżej wymienionych:

  • za instrukcją skoku,
  • przed instrukcją, która jest celem jakiegoś skoku,
  • na końcu programu.

Kolejna instrukcja (jeśli istnieje) jest początkiem następnego bloku.

Z pojęciem bloków bazowych wiąże się [[Metody realizacji języków programowania/MRJP Wykład 6#grafprzeplywu|wspominany już wcześniej]] graf przepływu sterowania. Wierzchołkami tego grafu są bloki bazowe, a krawędź między wierzchołkami istnieje, jeśli sterowanie może przejść z jednego z tych bloków do drugiego. Krawędź jest skierowana od bloku, z którego sterowanie wychodzi, do bloku, który sterowanie przejmuje. Oczywiście z każdego bloku może wychodzić więcej niż jedna krawędź (gdy jest kończony instrukcją skoku warunkowego). W przypadku opisanego poprzednio kodu czwórkowego z bloku mogą wychodzić co najwyżej dwie krawędzie, ale gdy dopuszczamy bardziej skomplikowane instrukcje sterujące, krawędzi tych może być więcej.

Po podzieleniu kodu na bloki bazowe stworzenie grafu przepływu sterowania jest trywialne.

Przykładowo, następujący kod:

 (1) i := 0
 (2) if i = 10 goto (12)
 (3) j := 0
 (4) if j = 10 goto (10)
 (5) t1 := i * 10
 (6) t2 := t1 + j
 (7) a[t2] := 0
 (8) j := j + 1
 (9) goto (4)
(10) i := i + 1
(11) goto (2)
(12) k := 0


(zamiast stosować używane w poprzednim wykładzie etykiety, tu używamy numerów linii) po podziale na bloki bazowe i z dorysowanymi krawędziami grafu przepływu sterowania wygląda tak:

Historycznie istniały inne definicje bloków bazowych - dowodzono np., że lepsza może być definicja, w której blok jest kończony tylko poprzez skok bezwarunkowy. Wprawdzie komplikuje to znacząco algorytmy optymalizacji, ale ponieważ czas działania tych algorytmów jest najczęściej funkcją liczby bloków w kodzie, zmniejszenie liczby bloków może je przyspieszyć. Wydaje się jednak, że przy obecnych prędkościach procesorów, a także z uwagi na postępy w algorytmach optymalizacji, dodatkowa ich komplikacja nie jest warta niepewnego przyspieszenia optymalizatora.

Postać SSA

Jak się okaże w trakcie wykładów o optymalizacji, aby te optymalizacje zaimplementować, konieczna będzie znajomość miejsc, w których dana zmienna jest definiowana i używana. W "normalnym" programie każda zmienna może być definiowana wielokrotnie. To w oczywisty sposób utrudnia wyliczanie tych potrzebnych wartości.

Można przekształcić kod do postaci, w której każda zmienna będzie definiowana tylko jeden raz. Przykładowo, kod:

a := x + y
b := 2 * a
a := a + 2
b := b + a
a := b - 4

można zmienić na:

a{}_1 := x + y
b{}_1 := 2 * a{}_1
a{}_2 := a{}_1 + 1
b{}_2 := b{}_1 + a{}_2
a{}_3 := b{}_2 - 4

Jak widać, wymaga to wprowadzenia wielu dodatkowych zmiennych pomocniczych, ale nie jest to problemem - na etapach optymalizacji i generowania kodu można ponownie zmniejszyć ich liczbę. Ponieważ zmienne oznaczone tą samą nazwą z różnymi indeksami są z naszego punktu widzenia różnymi wersjami tej samej zmiennej, dalej będziemy się posługiwali pojęciami takimi jak definicja zmiennej, mając na uwadze, że dla kodu w postaci SSA oznacza to definicję którejś wersji zmiennej.

Oprócz wspomnianego uproszczenia wyliczania miejsc definicji zmiennej (wyliczania łańcuchów definicja-użycie) sprowadzenie kodu do tej postaci ma też inną zaletę - zmienne, które używają tej samej nazwy w kilku różnych miejscach kodu, ale ich użycie w tych (np. popularne jest używanie i jako indeksu w kilku kolejnych pętlach) miejscach jest zupełnie niezwiązane ze sobą, w nowej postaci będą miały inne nazwy, co także może ułatwić optymalizację.

Postać, w której każda zmienna ma tylko jedną statyczną definicję, nazywana jest angielskim skrótem SSA (ang. Static Single Assignment). Statyczna definicja to definicja występująca w kodzie źródłowym. Gdy taka definicja jest umieszczona w pętli, to mimo, że zmienna będzie miała tylko jedną definicję statyczną, jej wartość w trakcie działania programu będzie mogła być zmieniana wielokrotnie. Ta zmienna będzie miała wówczas wiele definicji dynamicznych.

Dla bloków bazowych przekształcenie kodu do postaci SSA jest, jak można zaobserwować na powyższym przykładzie, proste. Każdą definicję zmiennej zastępuje się definicją nowo utworzonej zmiennej, a każde użycie zmiennej - tak, by korzystało z najbliższej wcześniejszej definicji.

Problem pojawia się dla bardziej skomplikowanych programów, których graf przepływu zawiera sytuację taką, jak na poniższym rysunku:

Przy próbie przekształcenia kodu do postaci SSA okazuje się, że nie wiemy, której zmiennej użyć w bloku 3 w miejsce b - czy tej z bloku 1, czy z bloku 2.

Z pomocą przyjdzie nam funkcja \phi, której argumentami będą zmienne, które musimy rozważyć. Funkcja ta będzie wybierała właściwą zmienną w zależności od tego, którą krawędzią sterowanie weszło do bloku. Nie przejmujmy się chwilowo metodami implementacji takiej funkcji, bo do sprowadzania kodu do postaci SSA ani do rozważania optymalizacji jej implementacja jest niepotrzebna.

Po skorzystaniu z funkcji \phi graf przepływu sterowania wygląda następująco:

Sprowadzanie kodu do postaci SSA

Oprócz przemianowania kolejnych definicji jednej zmiennej na definicje kolejnych wersji zmiennej trzeba tylko wyznaczyć miejsca, w których skorzystamy z funkcji \phi.

Najprostszym rozwiązaniem jest używanie jej dla wszystkich zmiennych, które są w tym bloku używane, a nie są definiowane na początku każdego bloku bazowego, do którego wchodzi więcej niż jedna krawędź. Takie podejście może jednak powodować wstawianie wielu niepotrzebnych przypisań, skorzystamy więc z nieco bardziej wyszukanej metody.

Kiedy potrzebujemy użyć funkcji \phi dla jakiejś zmiennej, powiedzmy x, na początku jakiegoś bloku? Nieformalnie - tylko wtedy, gdy do tego bloku może dotrzeć kilka wersji zmiennej x. Formalnie: weźmy bloki a i b zawierające definicję zmiennej x oraz pewien blok c. Jeśli w grafie przepływu istnieje ścieżka z a do c oraz z b do c i ścieżki te są wierzchołkowo rozłączne, to w bloku c potrzebujemy użyć funkcji \phi dla zmiennej x. Przy takiej definicji trzeba jeszcze założyć, że na początku działania programu (w pierwszym bloku bazowym) wszystkie zmienne są inicjowane.

Wprost z tej definicji możemy wyprowadzić algorytm wstawiający wystąpienia funkcji \phi dokładnie tam, gdzie jest to potrzebne. Niestety, naiwny algorytm będzie miał absolutnie niesatysfakcjonujący czas działania.

Spróbujmy użyć innego podejścia.

Wprowadźmy pojęcie dominacji w grafie skierowanym z wierzchołkiem początkowym s: wierzchołek d dominuje nad wierzchołkiem w wtedy i tylko wtedy, gdy każda ścieżka od s do w przechodzi przez d. Wierzchołek w dominuje ściśle v jeśli w dominuje v i w jest różne od v.

Granicą dominacji wierzchołka w nazwiemy zbiór wszystkich wierzchołków v takich, że w dominuje poprzednika v na ścieżce od w do v, ale nie dominuje ściśle wierzchołka v.

Jeśli wierzchołek w zawiera definicję jakiejś zmiennej a, to we wszystkich wierzchołkach z granicy dominacji w musimy użyć funkcji \phi. Wynika to z tego, że do tych wierzchołków może dotrzeć więcej niż jedna definicja a - pierwsza z w, a druga - z wierzchołka początkowego. Ponieważ wstawienie funkcji \phi jest definicją zmiennej, to proces wyznaczania granic dominacji i dodawania funkcji \phi trzeba powtarzać dla kolejnych wierzchołków.

Twierdzenie, którego dowód pominiemy, głosi, że zbiór funkcji \phi wstawionych zgodnie z podaną wcześniej regułą ścieżek i zbiór funkcji wstawionych zgodnie z metodą granicy dominacji są identyczne. W związku z tym wystarczy znaleźć efektywny algorytm wyznaczania granic dominacji, by otrzymać szybką metodę wstawiania funkcji \phi.

Poprzestańmy na stwierdzeniu, że algorytmy takie istnieją. Jednym z nich jest algorytm Lengauera-Tarjana działający w czasie prawie liniowym. Zainteresowanych odsyłamy np. do książki Appela, gdzie jest on przedstawiony w kontekście wyznaczania miejsc wstawienia funkcji \phi.

Konwersja kodu do postaci bez funkcji \phi

Do tej pory zakładaliśmy, że funkcja \phi jest w "jakiś" sposób dostępna, bez wchodzenia w szczegóły implementacji. Niestety, magiczne właściwości tej funkcji - znajomość krawędzi, po której sterowanie weszło do danego bloku - uniemożliwiają jej stworzenie. Generując kod docelowy lub kolejną reprezentację pośrednią musimy jednak w jakiś sposób pozbyć się \phi.

Rozwiązaniem jest umieszczenie instrukcji kopiujących odpowiednią zmienną przed blokiem, w którym znajduje się funkcja \phi, co przedstawiono na poniższym rysunku:

Takie rozwiązanie może jednak spowodować nadmiarowe wykonywanie rozkazów. Gdy sterowanie przechodzi z bloku 1 do 3, wykonanie zaznaczonej instrukcji jest konieczne. Jednak sterowanie może przechodzić do bloku 2, wówczas zaznaczony rozkaz jest wykonywany nadmiarowo. Można temu zaradzić dodając do grafu przepływu sterowania puste bloki, w których następnie umieścimy instrukcje kopiujące:

Wyznaczenie formalnej metody dodawania bloków pozostawiamy jako ćwiczenie.

Podsumowanie

Przedstawiona tu postać SSA jest pewną szczególną formą kodu pośredniego. Można ją zastosować do czwórek z poprzedniego wykładu. Zapis kodu w tej postaci ułatwia implementację algorytmów optymalizacyjnych. Wiele współczesnych kompilatorów - np. GCC - korzysta z postaci SSA w trakcie optymalizacji.