Kompilatory, których używałem w C lub Javie, mają funkcję zapobiegania martwemu kodowi (ostrzeżenie, że linia nigdy nie zostanie wykonana). Mój profesor mówi, że kompilatory nigdy nie mogą w pełni rozwiązać tego problemu. Zastanawiałem się, dlaczego tak jest. Nie znam się zbyt dobrze na kodowaniu kompilatorów, ponieważ jest to klasa teoretyczna. Zastanawiałem się jednak, co sprawdzają (np. Możliwe ciągi wejściowe vs. dopuszczalne dane wejściowe itp.) I dlaczego to nie wystarcza.
compiler-theory
Uczeń
źródło
źródło
if (isPrime(1234234234332232323423)){callSomething();}
czy ten kod kiedykolwiek coś zadzwoni czy nie? Istnieje wiele innych przykładów, w których decydowanie, czy funkcja jest kiedykolwiek wywoływana, jest znacznie droższe niż tylko włączenie jej do programu.public static void main(String[] args) {int counterexample = findCollatzConjectureCounterexample(); System.out.println(counterexample);}
<- czy println wywołuje martwy kod? Nawet ludzie nie mogą tego rozwiązać!Odpowiedzi:
Problem martwego kodu jest związany z problemem zatrzymania .
Alan Turing udowodnił, że niemożliwe jest napisanie ogólnego algorytmu, który otrzyma program i będzie w stanie zdecydować, czy program ten zatrzyma się dla wszystkich danych wejściowych. Możesz być w stanie napisać taki algorytm dla określonych typów programów, ale nie dla wszystkich programów.
Jak to się ma do martwego kodu?
Problem zatrzymania można zredukować do problemu znalezienia martwego kodu. Oznacza to, że jeśli znajdziesz algorytm wykrywający martwy kod w dowolnym programie, możesz użyć tego algorytmu do sprawdzenia, czy jakiś program się zatrzyma. Ponieważ okazało się to niemożliwe, z tego powodu napisanie algorytmu dla martwego kodu jest również niemożliwe.
Jak przenieść algorytm martwego kodu do algorytmu problemu zatrzymania?
Proste: dodajesz wiersz kodu po zakończeniu programu, który chcesz sprawdzić pod kątem zatrzymania. Jeśli wykrywacz martwego kodu wykryje, że linia nie żyje, oznacza to, że program się nie zatrzymuje. Jeśli nie, to wiesz, że twój program zatrzymuje się (przechodzi do ostatniej linii, a następnie do dodanej linii kodu).
Kompilatory zwykle sprawdzają, czy rzeczy, które można udowodnić w czasie kompilacji, są martwe. Na przykład bloki zależne od warunków, które można określić jako fałszywe w czasie kompilacji. Lub dowolne oświadczenie po
return
(w tym samym zakresie).Są to szczególne przypadki i dlatego można dla nich napisać algorytm. Możliwe jest pisanie algorytmów dla bardziej skomplikowanych przypadków (takich jak algorytm, który sprawdza, czy warunek jest sprzecznością składniową i dlatego zawsze zwróci fałsz), ale nadal nie obejmie wszystkich możliwych przypadków.
źródło
256^(2^64)
stanów jestO(1)
, więc wykrywanie martwego kodu można wykonać w czasie wielomianowym.Cóż, weźmy klasyczny dowód na nierozstrzygalność problemu zatrzymania i zmień czujnik zatrzymania na detektor martwego kodu!
Program C #
Jeśli
YourVendor.Compiler.HasDeadCode(quine_text)
wrócifalse
, to liniaSystem.Console.WriteLn("Dead code!");
nie zostanie nigdy zrealizowany, więc ten program faktycznie nie ma martwego kodu, a detektor myliłem.Ale jeśli zwróci
true
, liniaSystem.Console.WriteLn("Dead code!");
zostanie wykonana, a ponieważ w programie nie ma już kodu, w ogóle nie ma martwego kodu, więc ponownie wykrywacz się pomylił.Tak więc, wykrywacz martwego kodu, który zwraca tylko „Istnieje martwy kod” lub „Nie ma martwego kodu”, musi czasami dawać błędne odpowiedzi.
źródło
Jeśli problem zatrzymania jest zbyt niejasny, pomyśl o tym w ten sposób.
Weźmy matematyczny problem, który uważa się za prawdziwy dla wszystkich liczb całkowitych dodatnich n , ale nie udowodniono, że jest prawdziwy dla każdego n . Dobrym przykładem może być hipoteza Goldbacha , że każda dodatnia nawet liczba całkowita większa niż dwa może być reprezentowana przez sumę dwóch liczb pierwszych. Następnie (z odpowiednią biblioteką bigint) uruchom ten program (następuje pseudokod):
Wdrożenie
isGoldbachsConjectureTrueFor()
jest pozostawione jako ćwiczenie dla czytelnika, ale w tym celu może być prostą iteracją wszystkich liczb pierwszych mniejszych niżn
Teraz logicznie powyższe musi być równoważne z:
(tj. nieskończona pętla) lub
ponieważ hipoteza Goldbacha musi być albo prawdziwa, albo nieprawda. Gdyby kompilator zawsze mógł wyeliminować martwy kod, zdecydowanie byłby martwy kod do wyeliminowania w obu przypadkach. Jednak w ten sposób kompilator musiałby rozwiązać arbitralnie trudne problemy. Możemy dostarczyć problemy provably ciężko, że będzie musiał rozwiązać (np NP-zupełny problemów), aby określić, który fragment kodu do wyeliminowania. Na przykład, jeśli weźmiemy ten program:
wiemy, że program wydrukuje „Znaleziono wartość SHA” lub „Nie znaleziono wartości SHA” (punkty bonusowe, jeśli możesz mi powiedzieć, która z nich jest prawdziwa). Jednak, aby kompilator był w stanie racjonalnie zoptymalizować, przyjmowałby kolejność 2 ^ 2048 iteracji. Byłaby to świetna optymalizacja, ponieważ przewiduję, że powyższy program będzie (lub mógłby) działać aż do śmierci cieplnej wszechświata, zamiast drukować cokolwiek bez optymalizacji.
źródło
sha256
zwraca tablicę bajtów i tablice bajtów nie porównują równe ciągom znaków w twoim języku.Implementation of isGoldbachsConjectureTrueFor() is left as an exercise for the reader
To mnie zachichotało.Nie wiem, czy C ++ lub Java mają funkcję
Eval
typu, ale wiele języków pozwala na wywoływanie metod według nazwy . Rozważ następujący (wymyślony) przykład VBA.Nazwy metody, która ma zostać wywołana, nie można poznać przed uruchomieniem. Dlatego z definicji kompilator nie może z absolutną pewnością stwierdzić, że określona metoda nigdy nie jest wywoływana.
W rzeczywistości, biorąc pod uwagę przykład wywołania metody według nazwy, logika rozgałęziania nie jest nawet konieczna. Po prostu mówię
To więcej niż kompilator może określić. Gdy kod jest kompilowany, kompilator wie tylko, że do tej metody przekazywana jest pewna wartość ciągu. Nie sprawdza, czy ta metoda istnieje do czasu wykonania. Jeśli metoda nie jest wywoływana gdzie indziej, za pomocą bardziej normalnych metod, próba znalezienia martwych metod może zwrócić wyniki fałszywie dodatnie. Ten sam problem występuje w każdym języku, który pozwala na wywołanie kodu poprzez odbicie.
źródło
Zaawansowane kompilatory mogą wykryć i usunąć bezwarunkowy martwy kod.
Ale jest też warunkowy martwy kod. Jest to kod, który nie może być znany w momencie kompilacji i można go wykryć tylko w czasie wykonywania. Na przykład oprogramowanie może być konfigurowalne w celu włączenia lub wyłączenia niektórych funkcji w zależności od preferencji użytkownika, co powoduje, że niektóre sekcje kodu wydają się martwe w określonych scenariuszach. To nie jest prawdziwy martwy kod.
Istnieją specjalne narzędzia, które mogą wykonywać testy, rozwiązywać zależności, usuwać warunkowy martwy kod i ponownie łączyć użyteczny kod w czasie wykonywania w celu zwiększenia wydajności. Nazywa się to dynamiczną eliminacją martwego kodu. Ale jak widać, wykracza to poza zakres kompilatorów.
źródło
Prosty przykład:
Załóżmy teraz, że port 0x100 ma zwracać tylko 0 lub 1. W takim przypadku kompilator nie może stwierdzić, że
else
blok nigdy nie zostanie wykonany.Jednak w tym podstawowym przykładzie:
Tutaj kompilator może obliczyć, że
else
blok jest martwym kodem. Kompilator może więc ostrzegać o martwym kodzie tylko wtedy, gdy ma wystarczającą ilość danych, aby ustalić martwy kod, a także powinien wiedzieć, jak zastosować te dane, aby dowiedzieć się, czy dany blok jest martwym kodem.EDYTOWAĆ
Czasami dane są po prostu niedostępne w czasie kompilacji:
Podczas kompilacji a.cpp kompilator nie może wiedzieć, że
boolMethod
zawsze zwracatrue
.źródło
Kompilatorowi zawsze brakuje niektórych informacji kontekstowych. Na przykład możesz wiedzieć, że podwójna wartość nigdy nie przekracza 2, ponieważ jest to cecha funkcji matematycznej, której używasz z biblioteki. Kompilator nawet nie widzi kodu w bibliotece i nigdy nie może poznać wszystkich funkcji wszystkich funkcji matematycznych oraz wykryć wszystkie zużyte i skomplikowane sposoby ich implementacji.
źródło
Kompilator niekoniecznie widzi cały program. Mógłbym mieć program, który wywołuje bibliotekę współdzieloną, która wywołuje z powrotem funkcję w moim programie, która nie jest wywoływana bezpośrednio.
Tak więc funkcja, która jest martwa w stosunku do biblioteki, z którą została skompilowana, może zostać aktywowana, jeśli biblioteka zostanie zmieniona w czasie wykonywania.
źródło
Gdyby kompilator mógł dokładnie wyeliminować cały martwy kod, nazywałby to interpreter .
Rozważ ten prosty scenariusz:
my_func()
może zawierać dowolny kod, a aby kompilator mógł ustalić, czy zwraca on wartość prawda, czy fałsz, będzie musiał uruchomić kod lub zrobić coś, co jest funkcjonalnie równoważne z uruchomieniem kodu.Kompilator polega na tym, że wykonuje on tylko częściową analizę kodu, co upraszcza pracę osobnego działającego środowiska. Jeśli wykonasz pełną analizę, nie będzie to już kompilatorem.
Jeśli weźmiesz pod uwagę kompilator jako funkcję
c()
, gdziec(source)=compiled code
, a działające środowisko jakor()
, gdzier(compiled code)=program output
, to aby określić wynik dla dowolnego kodu źródłowego, musisz obliczyć wartośćr(c(source code))
. Jeśli obliczeniac()
wymagają znajomości wartościr(c())
dowolnego wejścia, nie ma potrzeby oddzielnegor()
ic()
: można po prostu wyprowadzić funkcjęi()
zc()
takiegoi(source)=program output
.źródło
Inni komentowali problem zatrzymania i tak dalej. Zasadniczo dotyczą one części funkcji. Jednak może być trudno / nie wiedzieć, czy używany jest nawet cały typ (klasa / etc).
W .NET / Java / JavaScript i innych środowiskach opartych na środowisku uruchomieniowym nic nie powstrzymuje ładowania typów poprzez odbicie. Jest to popularne w ramach wstrzykiwania zależności i jest jeszcze trudniejsze do uzasadnienia w obliczu deserializacji lub dynamicznego ładowania modułu.
Kompilator nie może wiedzieć, czy takie typy zostaną załadowane. Ich nazwy mogą pochodzić z zewnętrznych plików konfiguracyjnych w czasie wykonywania.
Możesz poszukać wytrząsania drzew, które jest powszechnym terminem określającym narzędzia, które próbują bezpiecznie usunąć nieużywane podgrupy kodu.
źródło
Weź funkcję
Czy możesz udowodnić, że
actnumber
nigdy nie będzie2
tak, żeAction2()
nigdy się nie nazywa ...?źródło
Action2()
nigdy nie będzie się nazywać”, nie można udowodnić twierdzenia w praktyce - kompilator nie może go w pełni rozwiązać . Różnica jest taka, że „istnieje liczba X” vs. „możemy zapisać liczbę X w systemie dziesiętnym”. Dla niektórych X to drugie nigdy się nie wydarzy, chociaż to pierwsze jest prawdą.actnumber==2
. Ta odpowiedź po prostu twierdzi, że jest trudna, nawet nie mówiąc o złożoności.Nie zgadzam się co do problemu zatrzymania. Nie nazwałbym takiego kodu martwym, chociaż w rzeczywistości nigdy nie zostanie osiągnięty.
Zamiast tego rozważmy:
(Zignoruj błędy typu i przepełnienia) Martwy kod?
źródło
Spójrz na ten przykład:
Kompilator nie może wiedzieć, że int może być parzyste lub nieparzyste. Dlatego kompilator musi być w stanie zrozumieć semantykę kodu. Jak należy to wdrożyć? Kompilator nie może zagwarantować, że najniższy zwrot nigdy nie zostanie wykonany. Dlatego kompilator nie może wykryć martwego kodu.
źródło
return i%2==0;
.i % 2 == 0
ii % 2 != 0
nawet nie wymaga rozumowania o wartości liczby całkowitej modulo stałej (co nadal jest łatwe do zrobienia), wymaga jedynie wspólnej eliminacji podwyrażeń i ogólnej zasady (nawet kanonizacji), którąif (cond) foo; if (!cond) bar;
można uprościćif (cond) foo; else bar;
. Oczywiście „zrozumienie semantyki” jest bardzo trudnym problemem, ale ten post nie pokazuje, że tak jest, ani nie pokazuje, że rozwiązanie tego trudnego problemu jest konieczne do wykrycia martwego kodu.i % 2
i wyciągnie je do zmiennej tymczasowej. Następnie rozpozna, że dwieif
instrukcje wykluczają się wzajemnie i mogą być zapisane jakoif(a==0)...else...
, a następnie zauważy, że wszystkie możliwe ścieżki wykonania przechodzą przez dwie pierwszereturn
instrukcje, a zatem trzeciareturn
instrukcja jest martwym kodem. ( Dobry kompilator optymalizujący jest jeszcze bardziej agresywny: GCC zamienił mój kod testowy w parę operacji manipulacji bitami).if (availableMemory()<0) then {dead code}
.{dead code}
część. GCC odkrywa to, udowadniając, że istnieje nieuniknione przepełnienie liczb całkowitych ze znakiem. Cały kod na tym łuku na wykresie wykonania jest zatem martwy. GCC może nawet usunąć gałąź warunkową, która prowadzi do tego łuku.