Analiza określony przydział - Definite assignment analysis

W informatyce , określony analiza zadanie to analiza przepływu danych wykorzystywane przez kompilatory do konserwatywnie upewnić się, że zmienna lub lokalizacja jest zawsze przypisany przed użyciem.

Motywacja

W C i C ++ programów źródłem szczególnie trudne do zdiagnozowania błędów jest niedeterministyczny zachowanie, które wynika z lektury Niezainicjowane zmienne ; Takie zachowanie może się wahać pomiędzy platformami buduje, a nawet z przebiegami.

Istnieją dwa sposoby, aby rozwiązać ten problem. Jednym z nich jest, aby zapewnić, że wszystkie lokalizacje są napisane przed ich przeczytać. Twierdzenie Rice'a stwierdzi, że ten problem nie może być rozwiązany w ogóle dla wszystkich programów; Jednak możliwe jest stworzenie konserwatywne (nieprecyzyjne) Analiza, która będzie akceptować tylko programy, które spełniają to ograniczenie, odrzucając kilka poprawnych programów i definitywna analiza przypisanie jest taka analiza. W Java i C # programowanie specyfikacje językowe wymagają raport kompilator błąd kompilacji, jeśli analiza nie powiedzie się. Oba języki wymagają szczególnej formy analizy, która jest opisana w drobiazgowe szczegóły. W Javie, analiza ta została sformalizowana przez Stärk et al., A niektóre programy są poprawne odrzucone i muszą zostać zmienione, aby wprowadzić wyraźne niepotrzebnych zadań. W języku C #, analiza ta została sformalizowana przez Fruja i jest precyzyjny jak dźwięk, w tym sensie, że wszystkie zmienne przypisane wzdłuż wszystkich dróg przepływu sterowania będą rozpatrywane zdecydowanie przypisane. Cyclone język wymaga również programy przekazać ostateczną analizę przypisania, ale tylko na zmiennych o typach wskaźnik, aby ułatwić przenoszenie programów C.

Drugim sposobem na rozwiązanie problemu jest automatycznie zainicjować wszystkie lokalizacje do jakiejś stałej i przewidywalnej wartości w momencie, w którym są zdefiniowane, ale wprowadza nowe zadania, które mogą utrudniać działanie. W tym przypadku analiza określony przydział Umożliwia on optymalizacji kompilator gdzie nadmiarowe zadania - zadania następuje tylko przez inne zadania bez możliwości interweniujących czyta - mogą być wyeliminowane. W tym przypadku, żadne programy są odrzucane, ale programy dla których analiza nie rozpozna określony przydział może zawierać nadmiarową inicjalizacji. Common Language Infrastructure polega na tym podejściu.

Terminologia

Zmienna lub położenie można powiedzieć, aby być w jednym z trzech stanów w danym momencie w programie:

• Zdecydowanie przypisane : Zmienna jest znana z całą pewnością być przypisany.
• Zdecydowanie nieprzypisane : Zmienna jest znana z całą pewnością będzie nieprzypisane.
• Nieznane : Zmienna może być przypisane lub nieprzypisane; analiza nie jest wystarczająco precyzyjny, aby ustalić, które.

Analiza

Dodaje się w oparciu o formalizacji Fruja dnia C # intraprocedural (pojedynczy), określonym metodą analizy przypisania, która jest odpowiedzialna za zapewnienie, że wszystkie zmienne lokalne są przypisane przed ich zastosowaniem. To jednocześnie ma zdecydowany analizy przypisania i stałą propagacji wartości logicznych. Możemy zdefiniować pięć funkcji statycznych:

Dostarczamy równań przepływu danych, które definiują wartości tych funkcji na różnych wyrażeń i oświadczeń, pod względem wartości funkcji na ich składniowych podwyrażeń. Zakładamy, że w tej chwili nie ma żadnych goto , przerwa , nadal , zwrotu lub obsługi wyjątków oświadczenia. Poniżej przedstawiono kilka przykładów tych równań:

• Dowolne wyrażenie lub oświadczenie e , że nie wpływa to na pewno zestaw zmiennych przypisanych: po ( e ) = przed ( e )
• Niech e być wyrazem przypisanie loc = v . Następnie przed ( V ) = przed ( e ) i po ( E ) = od ( v ) U} {loc.
• Niech e być wyrazem prawda . Wtedy prawdziwy ( e ) = przed ( e ) i false ( e ) = Vars ( e ). Innymi słowy, jeżeli e ma wartość false , wszystkie zmienne ( próżniowo ) zdecydowanie przypisany, ponieważ e nie ocenia się fałszywe.
• Ponieważ metoda argumenty są oceniane od lewej do prawej, przed ( arg _{i  + 1} ) = after ( arg _I ). Po zakończeniu metoda, poza parametry są zdecydowanie przypisane.
• Niech s będzie instrukcja warunkowa jeśli ( e ) s ₁ inny s ₂ . Następnie przed ( e ) = przed ( a ), przed (a ₁ ) = prawdziwy ( e ) przed ( a ₂ ) = fałszywe ( e ), i po ( a ) = od ( a ₁ ) przecinają się po ( a ₂ ) ,
• Niech s będzie oświadczenie pętli podczas gdy ( e ) s ₁ . Potem wcześniej ( e ) = przed ( a ), przed ( a ₁ ) = prawdziwe ( e ), i po ( a ) = False ( e ).
• I tak dalej.

Na początku tego sposobu, nie ma zmienne lokalne są zdecydowanie przypisane. Weryfikator wielokrotnie iteracje nad drzewo składniowe oraz zastosowania równań przepływu danych do migracji informacji pomiędzy zestawami aż stały punkt może być osiągnięta. Następnie, weryfikator analizuje przed ustawić każdej wypowiedzi, która używa zmiennej lokalnej w celu zapewnienia, że zawiera tę zmienną.

Algorytm jest skomplikowane przez wprowadzenie kontroli przepływu skoki jak goto , przerwy , w dalszym ciągu , powrotu i obsługę wyjątków. Każde oświadczenie, które mogą stać się celem jednego z tych skoków musi przecinać jej przed set z zestawem zdecydowanie przypisanych zmiennych u źródła skoku. Gdy zostaną one wprowadzone, otrzymany strumień danych może mieć wiele punktów stałych, w tym przykładzie:

1  int i = 1;
2  L:
3  goto L;

Ponieważ etykieta L może być osiągnięte z dwoma miejscami równanie kontroli przepływu do goto nakazuje wcześniej (2) = od (1) przecinają się przed (3). Ale zanim (3) = przed (2), więc przed (2) = po (1) przecinają się przed (2). Ma to dwie stałe punktów zaczepienia dla wcześniej (2), {i} i zbiór pusty. Jednakże, jeżeli można wykazać, że ze względu na monotoniczny postaci równań przepływu danych, jest wyjątkowy maksymalny punkt stały (stały punkt największego rozmiaru), która zapewnia największą możliwą informację o zdecydowanie przypisanych zmiennych. Taka ilość (lub maksymalny) punkt stały może być obliczany za pomocą standardowych technik; patrz analizy przepływu danych .

Dodatkowym problemem jest to, że skok kontroli przepływu może spowodować, że pewne kontroli przepływu niemożliwe; Na przykład, w tym fragment kodu zmienna i jest zdecydowanie przypisany przed użyciem:

1  int i;
2  if (j < 0) return; else i = j;
3  print(i);

Równanie dla przepływu danych , jeżeli mówi, że gdy (2) = po ( powrót ) przecinają po ( ı = j ). Aby to działało poprawnie, definiujemy po ( e ) = Vars ( e ) dla wszystkich kontrola przepływu skacze; to bezmyślnie ważne w tym samym sensie, że równanie false ( prawda ) = Vars ( e ) jest ważna, ponieważ nie jest możliwe sterowanie natychmiast dotrzeć do punktu po skoku kontrola przepływu.

Referencje