Dlaczego wykrywanie martwego kodu nie może być w pełni rozwiązane przez kompilator?

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.

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.

Cóż, weźmy klasyczny dowód na nierozstrzygalność problemu zatrzymania i zmień czujnik zatrzymania na detektor martwego kodu!

Program C #

using System;
using YourVendor.Compiler;

class Program
{
    static void Main(string[] args)
    {
        string quine_text = @"using System;
using YourVendor.Compiler;

class Program
{{
    static void Main(string[] args)
    {{
        string quine_text = @{0}{1}{0};
        quine_text = string.Format(quine_text, (char)34, quine_text);

        if (YourVendor.Compiler.HasDeadCode(quine_text))
        {{
            System.Console.WriteLine({0}Dead code!{0});
        }}
    }}
}}";
        quine_text = string.Format(quine_text, (char)34, quine_text);

        if (YourVendor.Compiler.HasDeadCode(quine_text))
        {
            System.Console.WriteLine("Dead code!");
        }
    }
}

Jeśli YourVendor.Compiler.HasDeadCode(quine_text)wróci false, to linia System.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, linia System.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.

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):

 for (BigInt n = 4; ; n+=2) {
     if (!isGoldbachsConjectureTrueFor(n)) {
         print("Conjecture is false for at least one value of n\n");
         exit(0);
     }
 }

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:

 for (; ;) {
 }

(tj. nieskończona pętla) lub

print("Conjecture is false for at least one value of n\n");

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:

 String target = "f3c5ac5a63d50099f3b5147cabbbd81e89211513a92e3dcd2565d8c7d302ba9c";
 for (BigInt n = 0; n < 2**2048; n++) {
     String s = n.toString();
     if (sha256(s).equals(target)) {
         print("Found SHA value\n");
         exit(0);
     }
 }
 print("Not found SHA value\n");

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.

Nie wiem, czy C ++ lub Java mają funkcję Evaltypu, ale wiele języków pozwala na wywoływanie metod według nazwy . Rozważ następujący (wymyślony) przykład VBA.

Dim methodName As String

If foo Then
    methodName = "Bar"
Else
    methodName = "Qux"
End If

Application.Run(methodName)

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ę

Application.Run("Bar")

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.

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.

Prosty przykład:

int readValueFromPort(const unsigned int portNum);

int x = readValueFromPort(0x100); // just an example, nothing meaningful
if (x < 2)
{
    std::cout << "Hey! X < 2" << std::endl;
}
else
{
    std::cout << "X is too big!" << std::endl;
}

Załóżmy teraz, że port 0x100 ma zwracać tylko 0 lub 1. W takim przypadku kompilator nie może stwierdzić, że elseblok nigdy nie zostanie wykonany.

Jednak w tym podstawowym przykładzie:

bool boolVal = /*anything boolean*/;

if (boolVal)
{
  // Do A
}
else if (!boolVal)
{
  // Do B
}
else
{
  // Do C
}

Tutaj kompilator może obliczyć, że elseblok 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:

// File a.cpp
bool boolMethod();

bool boolVal = boolMethod();

if (boolVal)
{
  // Do A
}
else
{
  // Do B
}

//............
// File b.cpp
bool boolMethod()
{
    return true;
}

Podczas kompilacji a.cpp kompilator nie może wiedzieć, że boolMethodzawsze zwraca true.

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.

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.

Gdyby kompilator mógł dokładnie wyeliminować cały martwy kod, nazywałby to interpreter .

Rozważ ten prosty scenariusz:

if (my_func()) {
  am_i_dead();
}

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(), gdzie c(source)=compiled code, a działające środowisko jako r(), gdzie r(compiled code)=program output, to aby określić wynik dla dowolnego kodu źródłowego, musisz obliczyć wartość r(c(source code)). Jeśli obliczenia c()wymagają znajomości wartości r(c())dowolnego wejścia, nie ma potrzeby oddzielnego r()i c(): można po prostu wyprowadzić funkcję i()z c()takiego i(source)=program output.

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.

Weź funkcję

void DoSomeAction(int actnumber) 
{
    switch(actnumber) 
    {
        case 1: Action1(); break;
        case 2: Action2(); break;
        case 3: Action3(); break;
    }
}

Czy możesz udowodnić, że actnumbernigdy nie będzie 2tak, że Action2()nigdy się nie nazywa ...?

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:

for (int N = 3;;N++)
  for (int A = 2; A < int.MaxValue; A++)
    for (int B = 2; B < int.MaxValue; B++)
    {
      int Square = Math.Pow(A, N) + Math.Pow(B, N);
      float Test = Math.Sqrt(Square);
      if (Test == Math.Trunc(Test))
        FermatWasWrong();
    }

private void FermatWasWrong()
{
  Press.Announce("Fermat was wrong!");
  Nobel.Claim();
}

(Zignoruj ​​błędy typu i przepełnienia) Martwy kod?

Spójrz na ten przykład:

public boolean isEven(int i){

    if(i % 2 == 0)
        return true;
    if(i % 2 == 1)
        return false;
    return false;
}

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.