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

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

Optymalizacja kodu pośredniego w postaci SSA

Optymalizacja kodu (tu pośredniego) jest procesem, którego celem jest zmiana kodu przy zachowaniu obliczanej funkcji tak, by przyspieszyć działanie docelowego programu i ewentualnie zmniejszyć jego rozmiar. To drugie wymaganie w obecnych czasach ma mniejsze znaczenie. Zwróćmy uwagę, że optymalizacja jest raczej "poprawianiem" programu, bo rzadko otrzymany kod jest "optymalny". Należy pamiętać, że w optymalizacji powinno uwzględniać się wiele ogólnych warunków:

• czas działania docelowego programu jest najbardziej istotny; złożony program może pewne fragmenty wykonywać częściej - te powinny być lepiej zoptymalizowane i odwrotnie nie warto optymalizować rzadko wykonywanych fragmentów programu,
• dane wejściowe mogą wpływać na to jak często wykonuje się określone fragmenty programu - dobry optymalizator powinien próbować zgadnąć istotne (czyli często wykonywane) dla optymalizacji fragmenty,
• rozmiar docelowego programu obecnie ma mniejsze znaczenie,
• rozsądny czas wykonywania optymalizacji.

Wykład przedstawia podstawowe techniki optymalizacji kodu pośredniego w postaci SSA, choć niektóre z nich mogą być stosowane do innych postaci np. kodu czwórkowego (ang. three-address code). Jak już wiemy z wykładu o generowaniu kodu pośredniego postać SSA jest szczególnie użyteczna w optymalizacji - istotnie upraszcza zapis i implementację algorytmów poprawiających kod. Jest stosowana w optymalizatorach ważnych kompilatorów np. GCC.

Podstawowe przekształcenia poprawiające kod

Poniższe przykłady nie są przedstawione w postaci SSA, ale mogą być łatwo do niego przekształcone (w celu lepszej czytelności piszemy a zamiast a1, x zamiast x1, itd.).

Propagacja kopii

Instrukcja postaci X = Y jest instrukcją kopiowania. Naturalne jest zastąpienie wystąpień zmiennej X przez Y.

Przykład:

x = y
a = x + y
b = a + x

Zastępujemy przez:

x = y
a = y + y
b = a + y

Po wykonaniu propagacji kopii, instrukcja kopiująca jest martwym kodem. Ostatecznie otrzymamy:

a = y + y
b = a + y

Eliminacja wspólnych podwyrażeń

Wyrażenie E postaci X op Y jest nazywane wspólnym podwyrażeniem, jeśli występuje ono w kilku miejscach, oraz jeśli wartości zmiennych X i Y użytych w kolejnych wystąpieniach E nie zmieniły się po poprzednim obliczeniu E. W takiej sytuacji można zastąpić kolejne wystąpienia E przez wartość wyliczoną za pierwszym razem.

Przykład:

a = 4 * i
b = 4 * i
c = a + b

Drugie wyliczenie 4 * i można zastąpić przez b. Przekształcony blok:

a = 4 * i
b = a
c = a + b

Eliminację wspólnych podwyrażeń można stosować

• lokalnie - gdy przeszukujemy jeden blok bazowy,
• globalnie - dla całego grafu przepływu (trudniejsze z powodu pętli).

Usuwanie martwego kodu

Zmienną nazywamy żywą w danym miejscu programu, jeżeli jej wartość może zostać użyta. W pozostałych przypadkach nazywamy zmienną martwą w tym miejscu. Analogicznie definiujemy kod martwy, tzn. taki, który oblicza wartości bezużyteczne. Na przykład wyliczenie wartości dla zmiennej martwej lub instrukcja postaci

if (false) ...

to kod martwy.

Oczywiści kod martwy usuwamy.

Często kod martwy powstaje po propagacji kopii lub po zwijaniu stałych .

Zwijanie stałych

Jest to proces upraszczania wyrażeń stałych. Przykład:

x = 30 * 2

można zastąpić przez

x = 60

Zwijanie stałych czasem wykonuje się na wcześniejszych etapach kompilacji.

Propagacja stałych

Jest to proces zastępowania wystąpień stałych przez ich wartości. Przykład

x = 60
y = 3 * x

można zastąpić przez

x = 60
y = 3 * 60

i dalej po zwinięciu wartości w drugim przypisaniu otrzymamy

x = 60
y = 180

W wyniku propagacji stałych instrukcja definiująca stałą staje się martwym kodem, który można usunąć w trakcie eliminacji martwego kodu.

Optymalizacja pętli

Przemieszczanie kodu

Polega na zmiejszeniu ilości kodu w pętli, przez przemieszczenie obliczeń niezmienniczych przed pętle.

Prosty przykład:

i = 0
do {
   a = 13
   i = i + 1
} while (i < 15) 

przedstawiamy w postaci SSA:

(0) i1 = 0
(1) i2 = $\varphi$(i1,i3)
(2) a = 13
(3) i3 = i2 + 1
(4) if (i3 < 15) goto (1)

Wyrażeniem niezmienniczym jest instrukcja przypisania w linii (2). Możemy ją przemieścić przed pętlę:

(0) i1 = 0
(1) a = 13
(2) i2 = $\varphi$(i1,i3)
(3) i3 = i2 + 1
(4) if (i3 < 15) goto (2)

W ogólnej sytuacji stosujemy schemat: jeśli I jest instrukcją X = Y op Z, oraz Y, Z nie odwołują się do $\varphi$-węzła lub definicji wewnątrz pętli, wtedy

• usuń instrukcję I (to jest instrukcja niezmiennicza dla tej pętli),
• utwórz nową tymczasową zmienną T,
• wstaw nową instrukcję T = Y op Z oraz X = T do (ewentualnie) nowego bloku przed tą pętlą.

Proces ten rozszerzamy, wykonując iteracyjnie:

• jeśli argumenty operacji pewnej instrukcji są zdefiniowane przez instrukcje niezmiennicze (tzn. ta instrukcja jest również niezmiennicza w pętli), wykonuj analogiczne przenoszenie kodu do bloku przed pęltą.

Zmienne indukcyjne i redukcja mocy

Wyszukanie zmiennych indukcyjnych

Identyfikacja zmiennych, które zmieniają się w regularny sposób w pętli ułatwia optymalizację pętli. Zmienne o takiej własności nazywany indukcyjnymi. W połączeniu z redukcją mocy (czyli zastępowaniem drogich obliczeń przez tańsze, np. zamiast mnożenia dodawanie), można w najlepszym przypadku zostawić tylko jedną zmienną indukcyjną.

Zmienne indukcyjne w poniższym przykładzie to i, j:

i = 0 
do { 
  j = 4 * i
  i = i + 1 
} while (i < 20)

Identyfikowanie zmiennych indukcyjnych jest prostsze, gdy program jest w postaci SSA.

Zaczniemy od obliczenia zbioru kandydatów na zmienne indukcyjne: Dla danej pętli L zmienna T jest kandydatem na zmienną indukcyjną dla L (niżej będziemy pisać jest kandydatem) wtedy i tylko wtedy, gdy T jest obliczana w L i to obliczenie ma jedną następujących postaci:

• T = X ± Y, gdzie jeden z argumentów jest kandydatem, a drugi jest niezmienniczy dla L.
• T = X, gdzie X jest kandydatem lub niezmienniczy dla L.
• T = ± X, gdzie X jest kandydatem dla L.
• T = $\varphi$(T1, . . ., Tm), gdzie każdy z argumentów jest albo kandydatem, albo jest niezmienniczy dla L.

Zdefiniujemy teraz pojęcie zbioru indukcyjnego i zmiennych indukcyjnych. Rozważmy graf skierowany, którego wierzchołkami są kandydaci, a zbiór krawędzi posiada krawędź z T do U, jeśli T jest użyta do obliczenia wartości U. Zmienna indukcyjna jest kandydatem, który jest elementem silnie spójnej składowej tego grafu. Zbiór zmiennych w takiej silnie spójnej składowej nazywamy zbiorem indukcyjnym.

Przykład:

m = 0 
do 
   l = m + 1
   t = l + 2
   m = t - 4
while (true)

Zapisujemy w postaci SSA:

(1) m${}_0$ = 0
(2) m${}_1$=$\varphi$(m${}_0$,m${}_2$)
(3) l${}_1$ = m${}_1$ + 1
(4) t${}_1$ = l${}_1$ + 2
(5) m${}_2$ = t${}_1$ - 4
(6) goto (2)

Graf skierowany dla kandydatów na zmienne indukcyjne jest przedstawiony poniżej:

Zbiorem indukcyjnym jest: {m${}_1$,l${}_1$,t${}_1$,m${}_2$}. Zaczynamy od zmiennej m${}_1$ definiowanej przez $\varphi$ i wartości pozostałych można przedstawić w postaci: m${}_1$ + C, gdzie C jest stałą. Tu:

(1) m${}_0$ = 0
(2) m${}_1$=$\varphi$(m${}_0$,m${}_2$)
(3) l${}_1$ = m${}_1$ + 1
(4) t${}_1$ = m${}_1$ + 3
(5) m${}_2$ = m${}_1$ - 1
(6) goto (2)

Po wykonaniu tej operacji zmienne l${}_1$, t${}_1$ nie są używane do obliczania m${}_2$. Jest mniej zależności i być może część zmiennych będzie usunięta po zastosowaniu innych rodzajów optymalizacji.

Redukcja mocy w pętlach

W przypadku, gdy do wyliczania używamy mnożenia, można zastosować inne podejście. Najpierw klasyfikujemy zmienne na kilka rodzajów:

• Zmienna indukcyjna podstawowa - jej definicja występuje dokładnie raz w pętli i jest postaci i = i + C, gdzie C jest niezmiennicze w pętli.
• Zmienna indukcyjna wspólna - jej definicja występuje dokładnie raz w pętli i jej wartość jest funkcją liniową pewnej zmiennej indukcyjnej; czyli i = A op j + B, gdzie A oraz B są niezmiennicze w pętli, op jest operatorem mnożenia lub dzielenia, a j jest zmienną indukcyjną.

Algorytm redukcji mocy: dla zmiennej indukcyjnej wspólnej i zdefiniowanej przez i = A * j + B, gdzie j jest zmienną indukcyjną podstawową.

1. Stwórz nową zmienną k.
2. Dodaj przed pętlą k = A * j + B (przekształć do SSA).
3. Za instrukcją j = j + C dodaj k = k + B * C (przekształć do SSA).
4. Zastąp definicję i przez i = k.

Odniesione korzyści to mniejsza liczba operacji mnożenia oraz wyniesione przed pętle obliczenia na wartościach niezmienniczych A, B oraz C.

W analogiczny sposób można redukować moc dla sytuacji, w których zmienna indukcyjna jest wykorzystywana do przypisania z mnożeniem, tzn. w pętli jest instrukcja k = j * A, gdzie A jest niezmiennicze, a j jest zmienną indukcyjną podstawową, której inkrementacja w pętli jest postaci j = j + C. W tej sytuacji zastępujemy przypisanie na k instrukcją k = k + C * A oraz dodajemy przed pętlą odpowiednią inicjalizację wartości k.