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

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

Streszczenie

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.

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).

Podstawowe przekształcenia poprawiające kod

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 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.

W oczywisty sposób 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 optymalizacje 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 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.