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


192

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.


91
zrób pętlę, umieść kod po niej, a następnie zastosuj en.wikipedia.org/wiki/Halting_problem
zapl

48
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.
idclev 463035818,

33
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ć!
user253751,

15
@ tobi303 nie jest świetnym przykładem, naprawdę łatwo jest wyliczyć liczby pierwsze ... po prostu nie brać ich względnie efektywnie. Problem zatrzymania nie jest w NP, jest nierozwiązywalny.
en_Knight

57
@alephzero i en_Knight - Oboje się mylicie. isPrime jest świetnym przykładem. Przyjęto założenie, że funkcja sprawdza liczbę pierwszą. Może ten numer był numerem seryjnym i przegląda bazę danych, aby sprawdzić, czy użytkownik jest członkiem Amazon Prime? Jest to świetny przykład, ponieważ jedynym sposobem na sprawdzenie, czy warunek jest stały, czy nie, jest wykonanie funkcji isPrime. Teraz wymagałoby to od Kompilatora również interpretacji. Ale to nadal nie rozwiązałoby przypadków, w których dane są niestabilne.
Dunk

Odpowiedzi:


275

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.


8
Argumentowałbym, że problem zatrzymania nie ma tutaj zastosowania, ponieważ każda platforma, która jest celem kompilacji każdego kompilatora w świecie rzeczywistym, ma maksymalną liczbę danych, do których może uzyskać dostęp, dlatego będzie miała maksymalną liczbę stanów, co oznacza, że ​​jest w rzeczywistości maszyna skończona, a nie maszyna Turinga. Problem zatrzymania nie jest nierozwiązywalny dla FSM, więc każdy kompilator w świecie rzeczywistym może wykryć martwy kod.
Vality

50
@Vality 64-bitowe procesory mogą adresować 2 ^ 64 bajty. Baw się dobrze, przeszukując wszystkie stany 256 ^ (2 ^ 64)!
Daniel Wagner

82
@DanielWagner To nie powinien być problem. Wyszukiwanie 256^(2^64)stanów jest O(1), więc wykrywanie martwego kodu można wykonać w czasie wielomianowym.
aebabis

13
@Lieliel, to był sarkazm.
Paul Draper,

44
@Vality: Większość współczesnych komputerów ma dyski, urządzenia wejściowe, komunikację sieciową itp. Każda kompletna analiza musiałaby uwzględniać wszystkie takie urządzenia - w tym dosłownie Internet i wszystko, co do niego podłączone. To nie jest możliwy do rozwiązania problem.
Nat.

77

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.


1
Jeśli dobrze zrozumiałem twój argument, technicznie inna opcja byłaby taka, że ​​nie można napisać detektora, który jest wykrywaczem martwego kodu, ale w ogóle można napisać wykrywacz martwego kodu. :-)
dniu

1
przyrost odpowiedzi Godelian.
Jared Smith

@abligh Ugh, to był zły wybór słów. W rzeczywistości nie podaję sobie kodu źródłowego wykrywacza martwych kodów, ale kod źródłowy programu, który go używa. Z pewnością w pewnym momencie prawdopodobnie musiałby przyjrzeć się własnemu kodowi, ale to jest jego sprawa.
Joker_vD

65

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.


4
To najlepsza jak dotąd odpowiedź +1
jean

2
Szczególnie interesująca jest dwuznaczność dotycząca tego, na co Standard C zezwala lub nie zezwala, jeśli chodzi o założenie, że pętle się zakończą. Wartość kompilacji polega na tym, że pozwala się kompilatorowi na odroczenie powolnych obliczeń, których wyniki mogą, ale nie muszą być wykorzystane, aż do momentu, w którym ich wyniki byłyby rzeczywiście potrzebne; ta optymalizacja może w niektórych przypadkach być użyteczna, nawet jeśli kompilator nie może udowodnić zakończenia obliczeń.
supercat

2
2 ^ 2048 iteracji? Nawet Głęboka Myśl poddałaby się.
Peter Mortensen

Wypisze „Znalezioną wartość SHA” z bardzo dużym prawdopodobieństwem, nawet jeśli celem był losowy ciąg 64 cyfr szesnastkowych. Chyba że sha256zwraca tablicę bajtów i tablice bajtów nie porównują równe ciągom znaków w twoim języku.
user253751,

4
Implementation of isGoldbachsConjectureTrueFor() is left as an exercise for the readerTo mnie zachichotało.
biziclop,

34

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.


2
W Javie (lub C #) można to zrobić za pomocą refleksji. C ++ prawdopodobnie mógłbyś zrobić trochę nieprzyjemności za pomocą makr, aby to zrobić. Nie byłoby ładnie, ale C ++ rzadko tak jest.
Darrel Hoffman

6
@DarrelHoffman - Makra są rozwijane przed przekazaniem kodu kompilatorowi, więc makra zdecydowanie nie są takie, jak byś to zrobił. Wskaźniki do funkcji to jak to zrobiłbyś. Nie używałem C ++ od lat, więc przepraszam, jeśli moje dokładne nazwy typów są nieprawidłowe, ale możesz po prostu przechowywać mapę ciągów do wskaźników funkcji. Następnie mieć coś, co akceptuje ciąg znaków na podstawie danych wprowadzonych przez użytkownika, wyszukuje ten ciąg znaków na mapie, a następnie wykonuje wskazaną funkcję.
ArtOfWarfare

1
@ArtOfWarfare nie mówimy o tym, jak można to zrobić. Oczywiście semantyczna analiza kodu może być wykonana w celu znalezienia takiej sytuacji, chodziło o to, że kompilator nie . Być może może, ale tak nie jest.
RubberDuck,

3
@ArtOfWarfare: Jeśli chcesz nitpick, na pewno. Uważam, że preprocesor jest częścią kompilatora, choć wiem, że technicznie nie jest. W każdym razie wskaźniki funkcji mogą złamać zasadę, że do funkcji nie ma bezpośredniego odniesienia nigdzie - są one, jak wskaźnik zamiast bezpośredniego wywołania, podobnie jak delegat w C #. C ++ jest ogólnie znacznie trudniejszy do przewidzenia dla kompilatora, ponieważ ma tak wiele sposobów robienia rzeczy pośrednio. Nawet zadania tak proste jak „znajdź wszystkie referencje” nie są trywialne, ponieważ mogą ukrywać się w typedefach, makrach itp. Nic dziwnego, że nie może łatwo znaleźć martwego kodu.
Darrel Hoffman

1
Nie potrzebujesz nawet dynamicznych wywołań metod, aby poradzić sobie z tym problemem. Dowolną metodę publiczną można wywołać przez jeszcze nie napisaną funkcję, która będzie zależeć od już skompilowanej klasy w Javie, C # lub innym skompilowanym języku z pewnym mechanizmem dynamicznego łączenia. Jeśli kompilatory wyeliminują je jako „martwy kod”, nie bylibyśmy w stanie spakować wstępnie skompilowanych bibliotek do dystrybucji (NuGet, słoiki, koła Pythona z komponentem binarnym).
jpmc26

12

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.


5
„Bezwarunkowy martwy kod może zostać wykryty i usunięty przez zaawansowane kompilatory.” To nie wydaje się prawdopodobne. Martwość kodu może zależeć od wyniku danej funkcji, a ta funkcja może rozwiązać dowolne problemy. Tak więc twoje stwierdzenie potwierdza, że ​​zaawansowane kompilatory mogą rozwiązać dowolne problemy.
Taemyr

6
@Taemyr W takim razie nie wiadomo, że jest bezwarunkowo martwy, prawda?
JAB

1
@Taemyr Wydaje się, że źle rozumiesz słowo „bezwarunkowy”. Jeśli martwość kodu zależy od wyniku funkcji, jest to warunkowy martwy kod. „Warunek” jest wynikiem funkcji. Być „bezwarunkowe” musiałby to nie zależy od żadnych wyników.
Kyeotic,

12

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.


1
Chociaż ściśle prawda, że kompilator nie wie, myślę, że w duchu pytania leży również pytanie, czy linker może wiedzieć.
Casey Kuball

1
@Darthfett to nie jest Linker s odpowiedzialność. Linker nie analizuje zawartości skompilowanego kodu. Linker (ogólnie mówiąc) po prostu łączy metody i dane globalne, nie dba o treść. Jednak niektóre kompilatory mają opcję konkatenacji plików źródłowych (np. ICC), a następnie przeprowadzenia optymalizacji. W takim przypadku sprawa objęta EDIT jest objęta, ale ta opcja wpłynie na czas kompilacji, szczególnie gdy projekt jest duży.
Alex Lop.

Ta odpowiedź wydaje mi się myląca; podajesz dwa przykłady, w których nie jest to możliwe, ponieważ nie wszystkie informacje są dostępne, ale czy nie powinieneś powiedzieć, że jest to niemożliwe, nawet jeśli informacje tam są?
Anton Golov

@AntonGolov Nie zawsze jest to prawda. W wielu przypadkach, gdy informacje są dostępne, kompilatory mogą wykryć martwy kod i zoptymalizować go.
Alex Lop.

@abforce tylko blok kodu. To mogło być cokolwiek innego. :)
Alex Lop.

4

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.


4

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.


3

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.


2

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.


Nie wiem o Javie i javascript, ale .NET faktycznie ma wtyczkę resharper do tego rodzaju detekcji DI (o nazwie Agent Mulder). Oczywiście nie będzie w stanie wykryć plików konfiguracyjnych, ale jest w stanie wykryć confit w kodzie (co jest znacznie bardziej popularne).
Remisy

2

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 ...?


7
Jeśli potrafisz analizować osoby wywołujące funkcję, być może możesz, tak.
dniu

2
@abligh Ale kompilator zwykle nie może analizować całego kodu wywołującego. W każdym razie, nawet jeśli to możliwe, pełna analiza może wymagać jedynie symulacji wszystkich możliwych przepływów sterowania, co jest prawie zawsze niemożliwe ze względu na zasoby i czas. Więc nawet jeśli teoretycznie istnieje dowód, że „ 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ą.
CiaPan

To kiepska odpowiedź. pozostałe odpowiedzi dowodzą, że nie można wiedzieć, czy actnumber==2. Ta odpowiedź po prostu twierdzi, że jest trudna, nawet nie mówiąc o złożoności.
MSalters

1

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?


2
Ostatnie twierdzenie Fermata zostało udowodnione w 1994 roku. Zatem poprawne wdrożenie twojej metody nigdy nie uruchomiłoby FermatWasWrong. Podejrzewam, że twoja implementacja uruchomi FermatWasWrong, ponieważ możesz przekroczyć granicę precyzji pływaków.
Taemyr

@Taemyr Aha! Ten program nie testuje poprawnie ostatniego twierdzenia Fermata; kontrprzykładem tego, co robi test jest N = 3, A = 65536, B = 65536 (co daje Test = 0)
253751

@immibis Tak, przegapiłem, że przepełni się int, zanim precyzja na pływakach stanie się problemem.
Taemyr

@immibis Uwaga na dole mojego postu: zignoruj ​​błędy typu i przepełnienia. Właśnie brałem to, co uważałem za nierozwiązany problem, jako podstawę decyzji - wiem, że kod nie jest idealny. To problem, którego i tak nie można brutalnie wymusić.
Loren Pechtel

-1

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.


1
Umm, naprawdę? Jeśli napiszę to w C # + ReSharper, otrzymam kilka wskazówek. Podążanie za nimi w końcu daje mi kod return i%2==0;.
Thomas Weller,

10
Twój przykład jest zbyt prosty, aby był przekonujący. Konkretny przypadek i % 2 == 0i i % 2 != 0nawet 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.

5
W twoim przykładzie kompilator optymalizujący wykryje wspólne podwyrażenie i % 2i wyciągnie je do zmiennej tymczasowej. Następnie rozpozna, że ​​dwie ifinstrukcje wykluczają się wzajemnie i mogą być zapisane jako if(a==0)...else..., a następnie zauważy, że wszystkie możliwe ścieżki wykonania przechodzą przez dwie pierwsze returninstrukcje, a zatem trzecia returninstrukcja jest martwym kodem. ( Dobry kompilator optymalizujący jest jeszcze bardziej agresywny: GCC zamienił mój kod testowy w parę operacji manipulacji bitami).
Mark

1
Ten przykład jest dla mnie dobry. Stanowi to przypadek, gdy kompilator nie wie o pewnych faktycznych okolicznościach. To samo dotyczy if (availableMemory()<0) then {dead code}.
Little Santi

1
@LittleSanti: W rzeczywistości GCC wykryje, że wszystko , co tam napisałeś, jest martwym kodem! To nie tylko {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.
MSalters
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.