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

Globalna analiza przepływu danych

Opracowana na podstawie "Kompilatory" Aho, Sethi, Ullmana.

Podstawy

Równania przepływu danych

(Zakładam, ze pojęcie grafu przepływu jest już znane.)

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ąco: 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ągalnych

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ągalnych 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ągalnych nie zmieniają obliczanej funkcji programu.

Generowanie kodu wynikowego - przydział rejestrów

Może osobny wykład?