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

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

Optymalizacja II

Na tym wykładzie zajmiemy się globalną analizą przepływu danych, którą można wykorzystać do optymalizowania i generowania kodu. Globalna analiza przepływu danych polega na zebraniu informacji związanych z każdym blokiem (bądź fragmentem bloku) grafu przepływu (stąd "globalność"), a następnie wykorzystaniu jej w poprawianiu kodu i generowaniu kodu docelowego. Podstawowym narzędziem są "równania przepływu", które będziemy rozwiązywać w celu obliczenia potrzebnych informacji. Interesujące jest to, że wiele problemów globalnej analizy przepływu danych podlega podobnym regułom rozwiązywania, co wykorzystamy do przedstawienia efektywnych algorytmów.

Ilustracją będą dwa problemy:

• definicji osiągających - stosowanych w rozwiązywaniu globalnej propagacji kopii i eliminacji zmiennych indukcyjnych,
• zmiennych żywych - stosowanych w generowaniu kodu (tzw. przydział rejestrów procesora).

Podstawy

Równania przepływu danych

Informacje dotyczące przepływu danych zwykle wylicza się za pomocą układów równań, które przedstawiają zależności między występowaniem tych informacji pomiędzy różnymi punktami programu. Zwykle równanie ma postać:

$out[S]=gen[S]\cup (in[S]-kill[S])$.

Należy je rozumieć w następujący sposób: informacja dostępna na końcu instrukcji jest sumą zbiorów informacji

• przez nią generowanych (oznaczonych jako $gen[S]$)
• dostępnych na wejściu do niej ($in[S]$) ale bez informacji, które są niszczone przez tą instrukcję ($kill[S]$).

W zależności od rozwiązywanego zadania, będziemy rozważać równania, w których $in[S]$ definiuje się za pomocą $out[S]$ (w analizie od końcowego bloku). W globalnej analizie przepływu danych zamiast pojedyńczej instrukcji stosuje się bloki bazowe z grafu przepływu.

Definicje osiągające

Definicją zmiennej nazywamy instrukcję, która wiąże lub może wiązać tą zmienną z wartością. Przypisania lub czytanie z pliku to instrukcje zawsze definiującą zmienną. Nazywamy je definicjami pewnymi. Instrukcje niepewne to takie, którę mogą definiować zmienną np.:

• wywołanie procedury ze zmienną jako argumentem przekazywanym nie przez wartość,
• przypisania przez wskaźnik do zmiennej (w praktyce oznacza to defnicję każdej zmiennej).

Rozważmy ścieżkę w grafie przepływu łączącą dwa punkty. Wystąpienie pewnej definicji zmiennej a na tej ścieżce zabija wcześniejszą definicję tej zmiennej. Piszemy, że definicja D osiąga punkt P w grafie przepływu, jeśli istnieje ścieżka z miejsca występującego bezpośrednio po D do P taka, że D nie jest zabijane na tej ścieżce. Zauważmy, że w danym punkcie mogą być osiągalne pewne i niepewne definicje.

W poniższym przykładzie definicje X=1 i X=3 są pewne, a *Z=1 jest niepewna. Definicja X=1 nie jest zabijana przez definicje z bloku C, zatem w bloku D jest osiągalna. Jednocześnie w bloku D jest osiągalna definicja niepewna *Z=1, która potencjalnie też jest definiującą dla zmiennej X. Instrukcja X=3 w bloku E zabija wcześniejsze definicje X.

Zakładamy, że docelowy program będzie wykorzystywał wszystkie krawędzie (sprawdzenie tego jest problemem nierozstrzygalnym). Wszelkie wątpliwości rozważamy konserwatywnie tak, by uwzględnić każdy potencjalny scenariusz wykonania. Dlatego musimy rozważać definicje pewne zasłonięte przez definicje niepewne i ścieżki, które być może nigdy nie zostaną wykorzystane.

Programy strukturalne i obliczanie definicji osiągających

Załóżmy standardową gramatykę pewnego języka strukturalnego:

S ::= S1 ;  S2                  // Złożenie
    | if E then S1 else S2      // Instrukcja warunkowa
    | do S1 while E             // Pętla 
    | id := E                   // Przypisanie (definicja pewna)
E ::= id + id
    | id 

Zakładamy, że wszystkie definicje są pewne. Równania przepływu danych dla definicji osiągających można łatwo zapisać:

S ::= S1 ;  S2                  $gen[S]=gen[S2]\cup (gen[S1]-kill[S2])$
                                $kill[S]=kill[S2]\cup (kill[S1]-gen[S2])$    
                                $in[S1]=in[S]$
                                $in[S2]=in[S1]$
                                $out[S]=out[S2]$
            
    | if E then S1 else S2      $gen[S]=gen[S1]\cup gen[S2]$
                                $kill[S]=kill[S1]\cap kill[S2]$
                                $in[S1]=in[S]$
                                $in[S2]=in[S]$
                                $out[S]=out[S1]\cup out[S2]$

    | do S1 while E             $gen[S]=gen[S1]$
                                $kill[S]=kill[S1]$
                                $in[S]=in[S]\cup gen[S1]$
                                $out[S]=out[S1]$

    | id := E                   $gen[S]=\{id:=E\}$
                                $kill[S]=D_{id}-\{id:=E\}$
                                $out[S]=gen[S]\cup (in[S]-kill[S])$  

Tu $D_{id}$ to zbiór wszystkich definicji zmiennej id w programie.

Cechy oblicznych zbiorów:

• "prawdziwy" kill (tzn. taki, który zostałby wygenerowany podczas pewnego uruchomienia programu) jest zawsze nadzbiorem obliczanego (wg powyższych reguł),
• "prawdziwy" gen jest zawsze podzbiorem obliczanego.

Takie różnice są akceptowalne (bezpieczne), pod warunkiem, że wykonane optymalizacje w oparciu o takie zbiory wygenerowanych definicji osiągających nie zmieniają obliczanej funkcji programu.

Definicje osiągające można wykorzystać w algorytmach globalnej optymalizacji np.:

• globalnej propagacji kopii
• eliminacji zmiennych indukcyjnych

Tutaj pominiemy szczegóły tych algorytmów. Zainteresowanych odsyłamy do książki "Kompilatory", Aho, Sethi i Ullmana.

Podejście iteracyjne

W ogólnej sytuacji stosuje się podejście iteracyjne. Ponieważ wiele problemów związanych z analizą przepływu danych ma charakter "generowania-zabijania", pokażemy na przykładzie problemu definicji osiągających, jak rozwiązywać równania przepływu danych dla dowolnych grafów przepływu.

Schemat:

• zbuduj graf przepływu,
• oblicz zbiory gen i kill dla bloków bazowych,
• oblicz jednocześnie, stosując podejście iteracyjne, zbiory in i out.

Bedziemy wyróżniać dwa rodzaje obliczeń:

• do przodu, gdy zbiory out oblicza się na podstawie zbiorów in,
• do tyłu, gdy zbiory in oblicza się na podstawie zbiorów out.

Operatorem łączącym nazywamy operator użyty do zdefiniowania zbiorów przychodzących do danego bloku. Np. dla problemu definicji osiągających jest to operator sumy.

Problem osiągających definicji

Równania dla tego problemu są następujące:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle in[B] = \bigcup_{P\ \mbox{\small poprzednik}\ B}\ out[B]}

$out[B]=gen[B]\cup (in[B]-kill[B])$

Algorytm iteracyjny obliczający in i out jest dość naturalny:

1. Oblicz gen i kill dla bloków bazowych
2. for każdy blok bazowy B do 
      $out[B]:=gen[B]$ 
      $in[B]:=\mathrm{\varnothing }$
3. end for
4. while zbiory in lub out zmieniają się do
5.    for każdy blok bazowy B do     
           Parser nie mógł rozpoznać (błąd składni): {\displaystyle in[B]:= \bigcup_{P\ \mbox{\small poprzednik}\ B}\ out[B]}
       
           $out[B]=gen[B]\cup (in[B]-kill[B])$
6.    end for
5. done

Zmienne żywe

Przypomnijmy definicję zmiennej żywej: zmienna jest żywa w danym miejscu, jeśli może być użyta na pewnej ścieżce rozpoczynającej się od tego miejsca. W przeciwnym przypadku mówimy, że zmienna jest martwa. Ta informacja jest ważna w generowaniu kodu wynikowego, np. w sytuacji gdy potrzebujemy wolnego rejestru można użyć tych, które aktualnie przechowują zmienne martwe.

Równania dla tego problemu są następujące:

$in[B]=use[B]\cup (out[B]-def[B])$
Parser nie mógł rozpoznać (błąd składni): {\displaystyle in[B] = \bigcup_{S\ \mbox{\small następnik}\ B}\ in[S]}

gdzie

• in[B] - zbiór zmiennych żywych bezpośrednio przed blokiem B
• out[B] - zbiór zmiennych żywych bezpośrednio za blokiem B
• def[B] - do tego zbioru należy każda zmienna, której definicja i póżniejsze użycie jest w B (odpowiednik zbioru gen)
• use[B] - do tego zbioru należy każda zmienna, która może być użyta w B przed dowolną definicją tej zmiennej (odpowiednik zbioru kill)

Algorytm iteracyjny jest analogiczny do poprzedniego.