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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 = ϕ(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 = ϕ(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 ϕ-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=Ti ± Tj, gdzie jeden z argumentów jest kandydatem, a drugi jest niezmienniczy dla L.
  • T=Tk, gdzie Tk jest kandydatem lub niezmienniczy dla L.
  • T= ± Tk, gdzie Tk jest kandydatem dla L.
  • T=ϕ(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.

Redukcja mocy

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Metody_realizacji_języków_programowania/MRJP_Wykład_8&oldid=3697”