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

Wprowadzenie

Jeszcze nie ma...

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 $XopY$ 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

Wstępniak!

Przemieszczenie 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=YopZ$, 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=YopZ$ 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

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=T_i$ ± $T_j$, gdzie jeden z argumentów jest kandydatem, a drugi jest niezmienniczy dla $L$.
• $T=T_k$, gdzie $T_k$ jest kandydatem lub niezmienniczy dla $L$.
• $T=$ ± $T_k$, gdzie $T_k$ jest kandydatem dla $L$.
• $T=\varphi (T_1,...,T_m)$, 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.