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