Analiza przepływu danych - Data-flow analysis

Analiza przepływu danych to technika gromadzenia informacji o możliwym zestawie wartości obliczonych w różnych punktach programu komputerowego . A programu wykres kontroli przepływu (cfg) jest stosowany do określenia tych części programu, do którego przypisana do konkretnej wartości zmiennej może rozprzestrzeniać. Zebrane informacje są często wykorzystywane przez kompilatory podczas optymalizacji programu. Kanonicznym przykładem analizy przepływu danych jest docieranie do definicji .

Prostym sposobem przeprowadzenia analizy przepływu danych programów jest ustawienie równań przepływu danych dla każdego węzła grafu przepływu sterowania i rozwiązanie ich poprzez wielokrotne obliczanie wyjścia z wejścia lokalnie w każdym węźle, aż cały system ustabilizuje się, tj. , osiąga punkt stały .To ogólne podejście, znane również jako metoda Kildalla , zostało opracowane przez Gary'ego Kildalla podczas nauczania w Naval Postgraduate School .

Podstawowe zasady

Analiza przepływu danych to proces zbierania informacji o sposobie wykorzystania zmiennych, zdefiniowanych w programie. Próbuje uzyskać określone informacje w każdym punkcie procedury. Zwykle wystarczy uzyskać tę informację na granicach bloków podstawowych , ponieważ z tego łatwo można obliczyć informacje w punktach bloku podstawowego. W analizie przepływu do przodu stan wyjścia bloku jest funkcją stanu wejścia bloku. Ta funkcja jest złożeniem efektów instrukcji w bloku. Stan wejścia bloku jest funkcją stanów wyjścia jego poprzedników. Daje to zestaw równań przepływu danych:

Dla każdego bloku b:

{\ Displaystyle out_ {b} = trans_ {b} (in_ {b})}

{\ Displaystyle in_ {b} = join_ {p \ w pred_ {b}} (out_ {p})}

W tym jest funkcja przenoszenia bloku . Działa w stanie wejścia , dając stan wyjścia . Dołączyć eksploatacji kombajnów stanach wylotowe poprzedników o , uzyskując stan wejścia . $trans_{b}$ $b$ $w_{b}$ $out_{b}$ $dołączyć$ $p\w pred_{b}$ $b$ $b$

Po rozwiązaniu tego zestawu równań, stany wejścia i/lub wyjścia bloków można wykorzystać do wyprowadzenia właściwości programu na granicach bloku. Funkcję przenoszenia każdej instrukcji można zastosować osobno, aby uzyskać informacje w punkcie wewnątrz bloku podstawowego.

Każdy konkretny typ analizy przepływu danych ma swoją własną funkcję transferu i operacji łączenia. Niektóre problemy z przepływem danych wymagają analizy przepływu wstecznego. Jest to zgodne z tym samym planem, z wyjątkiem tego, że funkcja przenoszenia jest stosowana do stanu wyjściowego dającego stan wejściowy, a operacja łączenia działa na stanach wejściowych następców, aby uzyskać stan wyjściowy.

Punkt wejścia (w przepływie do przodu) odgrywa ważną rolę: ponieważ nie ma poprzedników, jego stan wejścia jest dobrze zdefiniowany na początku analizy. Na przykład zestaw zmiennych lokalnych ze znanymi wartościami jest pusty. Jeśli wykres przepływu sterowania nie zawiera cykli (w procedurze nie było wyraźnych ani niejawnych pętli ), rozwiązanie równań jest proste. Wykres przepływu sterowania można następnie posortować topologicznie ; Działając w takiej kolejności, stany wejściowe mogą być obliczone na początku każdego bloku, ponieważ wszyscy poprzednicy tego bloku zostały już przetworzone, więc ich stany wyjściowe są dostępne. Jeśli wykres przepływu sterowania zawiera cykle, wymagany jest bardziej zaawansowany algorytm.

Algorytm iteracyjny

Najczęstszym sposobem rozwiązywania równań przepływu danych jest użycie algorytmu iteracyjnego. Rozpoczyna się przybliżeniem stanu w każdym bloku. Stany wyjściowe są następnie obliczane przez zastosowanie funkcji transferu do stanów wewnętrznych. Z tych stanów w stanach są aktualizowane przez zastosowanie operacji łączenia. Te dwa ostatnie kroki są powtarzane, aż dojdziemy do tzw. punktu stałego : sytuacji, w której stany wewnętrzne (a w konsekwencji stany zewnętrzne) nie ulegają zmianie.

Podstawowym algorytmem rozwiązywania równań przepływu danych jest iteracyjny algorytm round-robin :

dla i ← 1 do N

zainicjować węzeł i

podczas ( zestawy wciąż się zmieniają )

dla i ← 1 do N

przeliczyć zbiory w węźle i

Konwergencja

Aby było użyteczne, podejście iteracyjne powinno rzeczywiście osiągnąć punkt stały. Można to zagwarantować przez nałożenie ograniczeń na kombinację domeny wartości stanów, funkcji transferu i operacji łączenia.

Dziedzina wartości powinna być porządkiem częściowym o skończonej wysokości (tj. nie ma nieskończonych łańcuchów rosnących < < ...). Kombinacja transmitancji i operacji sprzężenia powinna być monotoniczna względem tego porządku częściowego. Monotoniczność zapewnia, że w każdej iteracji wartość albo pozostanie taka sama, albo wzrośnie, podczas gdy skończona wysokość zapewnia, że nie będzie mogła rosnąć w nieskończoność. W ten sposób ostatecznie dojdziemy do sytuacji, w której T(x) = x dla wszystkich x, co jest punktem stałym. $x_{1}$ $x_{2}$

Podejście do listy prac

Łatwo jest ulepszyć powyższy algorytm, zauważając, że stan wewnętrzny bloku nie zmieni się, jeśli nie zmienią się stany wyjściowe jego poprzedników. Dlatego wprowadzamy listę prac : listę bloków, które wciąż wymagają przetworzenia. Za każdym razem, gdy zmienia się stan out bloku, dodajemy jego następców do listy prac. W każdej iteracji blok jest usuwany z listy prac. Obliczany jest jego stan zewnętrzny. Jeśli stan zewnętrzny uległ zmianie, następcy bloku zostaną dodani do listy prac. Aby zapewnić wydajność, blok nie powinien znajdować się na liście zadań więcej niż raz.

Algorytm rozpoczyna się od umieszczenia na liście prac bloków generujących informacje. Kończy się, gdy lista prac jest pusta.

Zamawianie

Na efektywność iteracyjnego rozwiązywania równań przepływu danych wpływa kolejność odwiedzania węzłów lokalnych. Co więcej, zależy to od tego, czy równania przepływu danych są używane do analizy przepływu danych w przód czy wstecz w CFG. Intuicyjnie, w przypadku problemu z przepływem w przód, najszybsze byłoby, gdyby wszystkie poprzedniki bloku zostały przetworzone przed samym blokiem, ponieważ od tego czasu iteracja będzie wykorzystywać najnowsze informacje. W przypadku braku pętli możliwe jest uporządkowanie bloków w taki sposób, że prawidłowe stany wyjściowe są obliczane przez przetwarzanie każdego bloku tylko raz.

Poniżej omówiono kilka porządków iteracji rozwiązywania równań przepływu danych (pojęciem powiązanym z porządkiem iteracji CFG jest przechodzenie po drzewie ).

Kolejność losowa — ta kolejność iteracji nie wie, czy równania przepływu danych rozwiązują problem z przepływem danych do przodu, czy do tyłu. W związku z tym wydajność jest stosunkowo niska w porównaniu ze specjalistycznymi zleceniami iteracji.
Postorder — jest to typowa kolejność iteracji w przypadku problemów z wstecznym przepływem danych. W iteracji postorder węzeł jest odwiedzany po odwiedzeniu wszystkich jego kolejnych węzłów. Zazwyczaj iteracja postorder jest realizowana zestrategią na pierwszym miejscu .
Reverse postorder — jest to typowa kolejność iteracji w przypadku problemów z przepływem danych do przodu. W iteracji odwróconej kolejności , węzeł jest odwiedzany przed odwiedzeniem któregokolwiek z jego węzłów następczych, z wyjątkiem sytuacji, gdy do następcy dociera tylna krawędź. (Zauważ, że odwrotne zamówienie pocztowe to nie to samo, co przedsprzedaż .)

Inicjalizacja

Początkowa wartość stanów w stanie jest ważna dla uzyskania prawidłowych i dokładnych wyników. Jeżeli wyniki są wykorzystywane do optymalizacji kompilatora, powinny one dostarczać informacji konserwatywnych , tzn. podczas ich stosowania program nie powinien zmieniać semantyki. Iteracja algorytmu punktu stałego przyjmie wartości w kierunku elementu maksymalnego. Dlatego inicjowanie wszystkich bloków z maksymalnym elementem nie jest przydatne. Co najmniej jeden blok zaczyna się w stanie o wartości mniejszej niż maksymalna. Szczegóły zależą od problemu z przepływem danych. Jeśli element minimum reprezentuje całkowicie konserwatywne informacje, wyniki mogą być bezpiecznie używane nawet podczas iteracji przepływu danych. Jeśli przedstawia najdokładniejsze informacje, przed zastosowaniem wyników należy osiągnąć punkt stały.

Przykłady

Poniżej przedstawiono przykłady właściwości programów komputerowych, które można obliczyć za pomocą analizy przepływu danych. Należy zauważyć, że właściwości obliczone za pomocą analizy przepływu danych są zazwyczaj tylko przybliżeniami właściwości rzeczywistych. Dzieje się tak, ponieważ analiza przepływu danych działa na strukturze syntaktycznej CFG bez symulowania dokładnego przepływu sterowania w programie. Jednak, aby być nadal użytecznym w praktyce, algorytm analizy przepływu danych jest zwykle zaprojektowany do obliczania górnej lub dolnej aproksymacji rzeczywistych właściwości programu.

Analiza w przód

W idące definicja oblicza analizy dla każdego programu wskazać zestaw definicji, które mogą potencjalnie osiągnąć ten punkt programu.

  if b==4 then
     a = 5;
  else 
     a = 3;
  endif
 
  if  a < 4 then
     ...

Osiągająca definicja zmiennej aw wierszu 7 to zbiór przypisań a = 5w wierszu 2 i a = 3w wierszu 4.

Analiza wsteczna

Na żywo analizy zmiennych oblicza dla każdego punktu programu zmienne, które mogą być potencjalnie czytaj potem przed ich kolejnej aktualizacji zapisu. Wynik jest zwykle używany przez eliminację martwego kodu w celu usunięcia instrukcji, które przypisują do zmiennej, której wartość nie jest później używana.

Stan w bloku to zestaw zmiennych, które są aktywne na początku tego bloku. Początkowo zawiera wszystkie zmienne na żywo (zawarte) w bloku, przed zastosowaniem funkcji transferu i obliczeniem rzeczywistych wartości zawartych. Funkcja przenoszenia instrukcji jest stosowana przez zabicie zmiennych zapisanych w tym bloku (usunięcie ich z zestawu aktywnych zmiennych). Stan wyjściowy bloku to zestaw zmiennych, które są aktywne na końcu bloku i jest obliczany przez sumę stanów wewnętrznych następców bloku.

Kod początkowy:

b1: a = 3; 
    b = 5;
    d = 4;
    x = 100;
    if a > b then
b2:    c = a + b;
       d = 2;
b3: endif
    c = 4;
    return b * d + c;

Analiza wsteczna:

// in: {}
b1: a = 3; 
    b = 5;
    d = 4;
    x = 100; //x is never being used later thus not in the out set {a,b,d}
    if a > b then
// out: {a,b,d}    //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d}  

// in: {a,b}
b2: c = a + b;
    d = 2;
// out: {b,d}

// in: {b,d}
b3: endif
    c = 4;
    return b * d + c;
// out:{}

Stan in b3 zawiera tylko b i d , ponieważ c zostało napisane. Stan wyjściowy b1 jest sumą stanów wewnętrznych b2 i b3. Definicję c w b2 można usunąć, ponieważ c nie jest aktywne bezpośrednio po stwierdzeniu.

Rozwiązywanie równań przepływu danych rozpoczyna się od zainicjowania wszystkich stanów wejściowych i wyjściowych do pustego zbioru. Lista prac jest inicjowana przez wstawienie punktu wyjścia (b3) na liście prac (typowe dla przepływu wstecznego). Jego obliczone w stanie różni się od poprzedniego, więc jego poprzednicy b1 i b2 są wstawiane i proces jest kontynuowany. Postępy podsumowano w poniższej tabeli.

przetwarzanie	poza stanem	stary w stanie	nowy w stanie	Lista pracy
b3	{}	{}	{b, d}	(b1,b2)
b1	{b, d}	{}	{}	(b2)
b2	{b, d}	{}	{a,b}	(b1)
b1	{a, b, d}	{}	{}	()

Zauważ, że b1 został wprowadzony na listę przed b2, co wymusiło dwukrotne przetwarzanie b1 (b1 zostało ponownie wprowadzone jako poprzednik b2). Wstawienie b2 przed b1 umożliwiłoby wcześniejsze zakończenie.

Inicjowanie pustym zestawem jest optymistyczną inicjacją: wszystkie zmienne zaczynają się jako martwe. Należy zauważyć, że stany zewnętrzne nie mogą się kurczyć z jednej iteracji do następnej, chociaż stan zewnętrzny może być mniejszy niż stan wewnętrzny. Widać to z faktu, że po pierwszej iteracji stan zewnętrzny może się zmienić jedynie poprzez zmianę stanu wewnętrznego. Ponieważ stan w stanie zaczyna się jako zestaw pusty, może rosnąć tylko w kolejnych iteracjach.

Inne podejścia

W 2002 roku Markus Mohnen opisał nową metodę analizy przepływu danych, która nie wymaga jawnej konstrukcji grafu przepływu danych, zamiast tego polega na abstrakcyjnej interpretacji programu i utrzymywaniu działającego zestawu liczników programu. W każdej gałęzi warunkowej oba cele są dodawane do zestawu roboczego. Każda ścieżka jest śledzona dla jak największej liczby instrukcji (do końca programu lub dopóki nie zapętli się bez zmian), a następnie usuwana jest z zestawu i pobierany jest następny licznik programu.

Połączenie analizy przepływu sterowania i analizy przepływu danych okazało się przydatne i komplementarne w identyfikacji spójnych regionów kodu źródłowego implementujących funkcjonalności systemu (np. cechy , wymagania lub przypadki użycia ).

Specjalne klasy problemów

Istnieje wiele specjalnych klas problemów z przepływem danych, które mają wydajne lub ogólne rozwiązania.

Problemy z wektorami bitowymi

Powyższe przykłady to problemy, w których wartością przepływu danych jest zbiór, np. zbiór definicji osiągania (Użycie bitu dla pozycji definicji w programie) lub zbiór zmiennych żywych. Te zestawy mogą być skutecznie reprezentowane jako wektory bitowe , w których każdy bit reprezentuje przynależność do zestawu jednego określonego elementu. Korzystając z tej reprezentacji, funkcje łączenia i przesyłania mogą być zaimplementowane jako bitowe operacje logiczne. Operacja sprzężenia jest zazwyczaj sumą lub przecięciem, zaimplementowaną przez bitowe Logic lub and Logic and . Funkcję transferu dla każdego bloku można rozłożyć na tak zwane zestawy gen i kill .

Na przykład w analizie zmiennych na żywo operacją łączenia jest suma. Zestaw zabijania to zestaw zmiennych, które są zapisywane w bloku, podczas gdy zestaw gen to zestaw zmiennych, które są odczytywane bez wcześniejszego zapisania. Równania przepływu danych stają się

{\ Displaystyle out_ {b} = \ bigcup _ {s \ w succ_ {b}} w_ {s}}

{\ Displaystyle in_ {b} = (out_ {b}-kill_ {b}) \ filiżanka gen_ {b}}

W operacjach logicznych brzmi to jako

out(b) = 0
for s in succ(b)
    out(b) = out(b) or in(s)
in(b) = (out(b) and not kill(b)) or gen(b)

Problemy przepływu danych, które mają zestawy wartości przepływu danych, który może być przedstawiony jako bitowych wektorów zwany bitowe problemy wektor , problemy gen zabić lub lokalnie rozłączne problemy . Takie problemy mają ogólne rozwiązania wielomianowe.

Oprócz problemów z osiąganiem definicji i zmiennych żywych wspomnianych powyżej, następujące problemy są przykładami problemów z wektorami bitowymi:

Problemy z IFDS

Problemy międzyproceduralne, skończone, dystrybutywne, podzbiorów lub problemy IFDS to kolejna klasa problemów z ogólnym rozwiązaniem wielomianowym. Rozwiązania tych problemów zapewniają kontekstową i wrażliwą na przepływ analizy przepływu danych.

Istnieje kilka implementacji analiz przepływu danych opartych na IDFS dla popularnych języków programowania, np. we frameworkach Soot i WALA do analizy Java.

Każdy problem związany z wektorem bitowym jest również problemem związanym z IDFS, ale istnieje kilka znaczących problemów związanych z IDFS, które nie są problemami związanymi z wektorem bitowym, w tym naprawdę żywe zmienne i prawdopodobnie niezainicjowane zmienne.

Wrażliwości

Analiza przepływu danych jest z natury wrażliwa na przepływ. Analiza przepływu danych jest zazwyczaj niewrażliwa na ścieżki, chociaż możliwe jest zdefiniowanie równań przepływu danych, które dają analizę wrażliwą na ścieżki.

Przepływu wrażliwych analiza uwzględnia kolejność instrukcji w programie. Przykładowo, analiza wskaźnik ps przepływu niewrażliwe może określić „zmiennych x i y mogą odnosić się do tego samego miejsca”, podczas gdy analiza przepływów wrażliwych może określić „po sprawozdaniu 20 zmiennych x i y mogą odnosić się do tej samej lokalizacji.”
Ścieżka wrażliwe analiza oblicza różnych informacji do analizy zależy od orzeczników w instrukcjach warunkowych branży. Na przykład, jeśli gałąź zawiera warunek x>0, to na ścieżce opadania analiza założyłaby, że x<=0i na celu gałęzi założyłaby, że rzeczywiście x>0ma miejsce.
Analiza kontekstowa to analiza międzyproceduralna, która uwzględnia kontekst wywołania podczas analizowania celu wywołania funkcji. W szczególności, korzystając z informacji kontekstowych, można przeskoczyć z powrotem do pierwotnego miejsca połączenia, podczas gdy bez tej informacji informacje z analizy muszą być propagowane z powrotem do wszystkich możliwych miejsc połączenia, potencjalnie tracąc precyzję.

Lista analiz przepływu danych

Zobacz też

Bibliografia

Dalsza lektura

Cooper, Keith D .; Torczon, Linda (2003) [2002-01-01]. Inżynieria kompilatora . Morgana Kaufmanna . Numer ISBN 978-1-55860-698-2.
Muchnick, Steven Stanley (1997). Zaawansowany projekt i implementacja kompilatora . Wydawnictwo Morgana Kaufmanna . Numer ISBN 978-1-55860-320-2.
Hecht, Mateusz S. (1977-05-03). Analiza przepływu programów komputerowych . Seria języków programowania. 5 . Elsevier North-Holland Inc. ISBN 978-0-44400210-5.
Khedker, Uday P.; Sanjal, Amitabha; Karkare, Bageshri (2009). Analiza przepływu danych: teoria i praktyka . CRC Press ( Grupa Taylora i Francisa ).
Nielson, Flemming; Nielson, Hanne Riis; Hankin, Chris (2005). Zasady analizy programu . Springer Nauka+Biznes Media .

Languages

In other projects