Warum kann die Erkennung von totem Code von einem Compiler nicht vollständig gelöst werden?

192

Die Compiler, die ich in C oder Java verwendet habe, verhindern toten Code (Warnung, wenn eine Zeile niemals ausgeführt wird). Mein Professor sagt, dass dieses Problem von Compilern niemals vollständig gelöst werden kann. Ich habe mich gefragt, warum das so ist. Ich bin mit der tatsächlichen Codierung von Compilern nicht allzu vertraut, da dies eine theoretische Klasse ist. Aber ich habe mich gefragt, was sie überprüfen (wie mögliche Eingabezeichenfolgen gegenüber akzeptablen Eingaben usw.) und warum dies nicht ausreicht.

Lerner
quelle
91
Machen Sie eine Schleife, setzen Sie Code danach und wenden Sie dann en.wikipedia.org/wiki/Halting_problem
zapl
48
if (isPrime(1234234234332232323423)){callSomething();}Wird dieser Code jemals etwas aufrufen oder nicht? Es gibt viele andere Beispiele, bei denen die Entscheidung, ob eine Funktion jemals aufgerufen wird, weitaus teurer ist, als sie nur in das Programm aufzunehmen.
idclev 463035818
33
public static void main(String[] args) {int counterexample = findCollatzConjectureCounterexample(); System.out.println(counterexample);}<- Ist der Println Call Dead Code? Nicht einmal Menschen können dieses Problem lösen!
user253751
15
@ tobi303 kein gutes Beispiel, es ist wirklich einfach, Primzahlen zu faktorisieren ... nur um sie nicht relativ effizient zu faktorisieren. Das Halteproblem liegt nicht in NP, es ist unlösbar.
en_Knight
57
@alephzero und en_Knight - Sie liegen beide falsch. isPrime ist ein gutes Beispiel. Sie haben angenommen, dass die Funktion nach einer Primzahl sucht. Vielleicht war diese Nummer eine Seriennummer und führt eine Datenbanksuche durch, um festzustellen, ob der Benutzer ein Amazon Prime-Mitglied ist? Der Grund dafür ist, dass die einzige Möglichkeit, festzustellen, ob die Bedingung konstant ist oder nicht, darin besteht, die Funktion isPrime tatsächlich auszuführen. Dafür müsste der Compiler nun auch ein Interpreter sein. Aber das würde die Fälle, in denen die Daten volatil sind, immer noch nicht lösen.
Dunk

Antworten:

275

Das Problem mit dem toten Code hängt mit dem Problem des Anhaltens zusammen .

Alan Turing hat bewiesen, dass es unmöglich ist, einen allgemeinen Algorithmus zu schreiben, der ein Programm erhält, und zu entscheiden, ob dieses Programm für alle Eingaben angehalten wird. Möglicherweise können Sie einen solchen Algorithmus für bestimmte Programmtypen schreiben, jedoch nicht für alle Programme.

Wie hängt das mit totem Code zusammen?

Das Problem des Anhaltens lässt sich auf das Problem reduzieren , toten Code zu finden. Wenn Sie also einen Algorithmus finden, der toten Code in einem Programm erkennen kann, können Sie diesen Algorithmus verwenden, um zu testen, ob ein Programm angehalten wird. Da sich dies als unmöglich erwiesen hat, ist das Schreiben eines Algorithmus für toten Code ebenfalls unmöglich.

Wie überträgt man einen Algorithmus für toten Code in einen Algorithmus für das Halting-Problem?

Einfach: Sie fügen nach dem Ende des Programms, das Sie auf Halt prüfen möchten, eine Codezeile hinzu. Wenn Ihr Dead-Code-Detektor feststellt, dass diese Zeile tot ist, wissen Sie, dass das Programm nicht angehalten wird. Wenn dies nicht der Fall ist, wissen Sie, dass Ihr Programm angehalten wird (bis zur letzten Zeile und dann bis zur hinzugefügten Codezeile).


Compiler prüfen normalerweise, ob Dinge, die zum Zeitpunkt der Kompilierung nachgewiesen werden können, tot sind. Zum Beispiel Blöcke, die von Bedingungen abhängig sind, die zum Zeitpunkt der Kompilierung als falsch bestimmt werden können. Oder eine Aussage nach a return(im gleichen Rahmen).

Dies sind spezielle Fälle, und daher ist es möglich, einen Algorithmus für sie zu schreiben. Es ist möglicherweise möglich, Algorithmen für kompliziertere Fälle zu schreiben (z. B. einen Algorithmus, der prüft, ob eine Bedingung syntaktisch ein Widerspruch ist und daher immer false zurückgibt), der jedoch nicht alle möglichen Fälle abdeckt.

RealSkeptic
quelle
8
Ich würde argumentieren, dass das Problem des Anhaltens hier nicht anwendbar ist, da jede Plattform, die ein Kompilierungsziel jedes Compilers in der realen Welt ist, eine maximale Menge an Daten hat, auf die er zugreifen kann, und daher eine maximale Anzahl von Zuständen hat, was bedeutet, dass dies der Fall ist in der Tat eine endliche Zustandsmaschine, keine Turingmaschine. Das Problem des Anhaltens ist für FSMs nicht unlösbar, sodass jeder Compiler in der realen Welt die Erkennung von totem Code durchführen kann.
Vality
50
@Vality 64-Bit-Prozessoren können 2 ^ 64 Bytes adressieren. Viel Spaß beim Durchsuchen aller 256 ^ (2 ^ 64) Staaten!
Daniel Wagner
82
@ DanielWagner Das sollte kein Problem sein. Das Suchen von 256^(2^64)Zuständen ist O(1)so, dass die Erkennung von totem Code in Polynomzeit erfolgen kann.
Aebabis
13
@Leliel, das war Sarkasmus.
Paul Draper
44
@Vality: Die meisten modernen Computer verfügen über Festplatten, Eingabegeräte, Netzwerkkommunikation usw. Bei jeder vollständigen Analyse müssten alle diese Geräte berücksichtigt werden - buchstäblich das Internet und alles, was daran angeschlossen ist. Dies ist kein nachvollziehbares Problem.
Nat
77

Nehmen wir den klassischen Beweis für die Unentscheidbarkeit des Stoppproblems und ändern den Stoppdetektor in einen Totcodedetektor!

C # -Programm

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!");
        }
    }
}

Wenn YourVendor.Compiler.HasDeadCode(quine_text)Rückkehr false, dann ist die Linie System.Console.WriteLn("Dead code!");nicht immer ausgeführt werden, so dass dieses Programm tatsächlich nicht tot - Code, und der Detektor war falsch.

Wenn es jedoch zurückkehrt true, wird die Zeile System.Console.WriteLn("Dead code!");ausgeführt, und da das Programm keinen Code mehr enthält, gibt es überhaupt keinen toten Code. Auch hier war der Detektor falsch.

Da haben Sie es also, ein Totcodedetektor, der nur "Es gibt toten Code" oder "Es gibt keinen toten Code" zurückgibt, muss manchmal falsche Antworten liefern.

Joker_vD
quelle
1
Wenn ich Ihr Argument richtig verstanden habe, wäre eine andere technische Option, dass es nicht möglich ist, einen Totcodedetektor zu schreiben, aber im allgemeinen Fall einen Totcodedetektor. :-)
abligh
1
Inkrement für die Antwort von Godel.
Jared Smith
@abligh Ugh, das war eine schlechte Wortwahl. Ich füttere nicht den Quellcode des Dead-Code-Detektors an sich selbst, sondern den Quellcode des Programms, das ihn verwendet. Sicher, irgendwann müsste es sich wahrscheinlich seinen eigenen Code ansehen, aber es geht ihn etwas an.
Joker_vD
65

Wenn das Problem des Anhaltens zu dunkel ist, stellen Sie es sich so vor.

Nehmen Sie ein mathematisches Problem, von dem angenommen wird, dass es für alle positiven Ganzzahlen n gilt , das jedoch nicht für jedes n gilt . Ein gutes Beispiel wäre Goldbachs Vermutung , dass jede positive gerade ganze Zahl größer als zwei durch die Summe zweier Primzahlen dargestellt werden kann. Führen Sie dann (mit einer geeigneten Bigint-Bibliothek) dieses Programm aus (Pseudocode folgt):

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

Die Implementierung von isGoldbachsConjectureTrueFor()bleibt als Übung für den Leser, könnte aber zu diesem Zweck eine einfache Iteration über alle Primzahlen sein, die kleiner als sindn

Logischerweise muss das Obige entweder das Äquivalent von sein:

 for (; ;) {
 }

(dh eine Endlosschleife) oder

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

wie Goldbachs Vermutung muss entweder wahr oder nicht wahr sein. Wenn ein Compiler immer toten Code eliminieren könnte, gäbe es in beiden Fällen definitiv toten Code, der hier eliminiert werden könnte. Dabei müsste Ihr Compiler jedoch zumindest beliebig schwierige Probleme lösen. Wir könnten Probleme bereitstellen, die nachweislich schwer zu lösen wären (z. B. NP-vollständige Probleme), um zu bestimmen, welches Codebit beseitigt werden soll. Zum Beispiel, wenn wir dieses Programm nehmen:

 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");

Wir wissen, dass das Programm entweder "Gefundener SHA-Wert" oder "Nicht gefundener SHA-Wert" ausgibt (Bonuspunkte, wenn Sie mir sagen können, welcher wahr ist). Damit ein Compiler dies jedoch vernünftigerweise optimieren kann, würde dies in der Größenordnung von 2 ^ 2048 Iterationen liegen. Es wäre in der Tat eine großartige Optimierung, da ich voraussage, dass das obige Programm bis zum Hitzetod des Universums laufen würde (oder könnte), anstatt etwas ohne Optimierung zu drucken.

abligh
quelle
4
Es ist die mit Abstand beste Antwort +1
Jean
2
Was die Dinge besonders interessant macht, ist die Unklarheit darüber, was der C-Standard zulässt oder nicht zulässt, wenn davon ausgegangen wird, dass Schleifen enden. Es ist sinnvoll, einem Compiler zu erlauben, langsame Berechnungen aufzuschieben, deren Ergebnisse möglicherweise bis zu dem Punkt verwendet werden, an dem ihre Ergebnisse tatsächlich benötigt würden. Diese Optimierung kann in einigen Fällen nützlich sein, auch wenn der Compiler nicht nachweisen kann, dass die Berechnungen beendet sind.
Supercat
2
2 ^ 2048 Iterationen? Sogar Deep Thought würde aufgeben.
Peter Mortensen
Es wird mit sehr hoher Wahrscheinlichkeit "Gefundener SHA-Wert" gedruckt, selbst wenn dieses Ziel eine zufällige Zeichenfolge mit 64 Hexadezimalstellen war. Es sei denn, es wird sha256ein Byte-Array zurückgegeben, und Byte-Arrays werden nicht mit Zeichenfolgen in Ihrer Sprache verglichen.
user253751
4
Implementation of isGoldbachsConjectureTrueFor() is left as an exercise for the readerDas brachte mich zum Lachen.
Biziclop
34

Ich weiß nicht, ob C ++ oder Java eine Typfunktion haben Eval, aber in vielen Sprachen können Sie Methoden nach Namen aufrufen . Betrachten Sie das folgende (erfundene) VBA-Beispiel.

Dim methodName As String

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

Application.Run(methodName)

Der Name der aufzurufenden Methode ist bis zur Laufzeit nicht bekannt. Daher kann der Compiler per Definition nicht mit absoluter Sicherheit wissen, dass eine bestimmte Methode niemals aufgerufen wird.

In Anbetracht des Beispiels, eine Methode beim Namen aufzurufen, ist die Verzweigungslogik nicht einmal erforderlich. Einfach sagen

Application.Run("Bar")

Ist mehr als der Compiler bestimmen kann. Wenn der Code kompiliert wird, weiß der Compiler nur, dass ein bestimmter Zeichenfolgenwert an diese Methode übergeben wird. Es wird erst zur Laufzeit überprüft, ob diese Methode vorhanden ist. Wenn die Methode nicht durch normalere Methoden an anderer Stelle aufgerufen wird, kann ein Versuch, tote Methoden zu finden, falsch positive Ergebnisse zurückgeben. Das gleiche Problem tritt in jeder Sprache auf, in der Code über Reflection aufgerufen werden kann.

Badeente
quelle
2
In Java (oder C #) kann dies mit Reflexion erfolgen. In C ++ könnten Sie wahrscheinlich mit Makros etwas Unangenehmes bewirken. Wäre nicht schön, aber C ++ ist es selten.
Darrel Hoffman
6
@DarrelHoffman - Makros werden erweitert, bevor der Code an den Compiler übergeben wird. Makros sind also definitiv nicht so, wie Sie dies tun würden. Zeiger auf Funktionen ist, wie Sie dies tun würden. Ich habe C ++ seit Jahren nicht mehr verwendet. Entschuldigen Sie, wenn meine genauen Typnamen falsch sind, aber Sie können einfach eine Zuordnung von Zeichenfolgen zu Funktionszeigern speichern. Haben Sie dann etwas, das eine Zeichenfolge aus Benutzereingaben akzeptiert, diese Zeichenfolge in der Karte nachschlägt und dann die Funktion ausführt, auf die verwiesen wird.
ArtOfWarfare
1
@ArtOfWarfare wir reden nicht darüber, wie es gemacht werden könnte. Offensichtlich kann eine semantische Analyse des Codes durchgeführt werden, um diese Situation zu finden. Der Punkt war, dass der Compiler dies nicht tut . Es könnte vielleicht, vielleicht, aber es tut es nicht.
RubberDuck
3
@ArtOfWarfare: Wenn du nicht picken willst, sicher. Ich betrachte den Präprozessor als Teil des Compilers, obwohl ich weiß, dass dies technisch nicht der Fall ist. Auf jeden Fall können Funktionszeiger gegen die Regel verstoßen, dass die Funktionen nirgendwo direkt referenziert werden - sie sind wie ein Zeiger anstelle eines direkten Aufrufs ähnlich wie ein Delegat in C #. C ++ ist für einen Compiler im Allgemeinen viel schwieriger vorherzusagen, da es so viele Möglichkeiten gibt, Dinge indirekt zu erledigen. Selbst Aufgaben wie "Alle Referenzen finden" sind nicht trivial, da sie sich in Typedefs, Makros usw. verstecken können. Kein Wunder, dass toter Code nicht leicht gefunden werden kann.
Darrel Hoffman
1
Sie benötigen nicht einmal dynamische Methodenaufrufe, um dieses Problem zu lösen. Jede öffentliche Methode kann von einer noch nicht geschriebenen Funktion aufgerufen werden, die von der bereits kompilierten Klasse in Java oder C # oder einer anderen kompilierten Sprache mit einem Mechanismus für die dynamische Verknüpfung abhängt. Wenn Compiler diese als "toten Code" eliminieren würden, könnten wir vorkompilierte Bibliotheken nicht für die Verteilung verpacken (NuGet, Jars, Python-Räder mit Binärkomponente).
jpmc26
12

Unbedingter toter Code kann von fortgeschrittenen Compilern erkannt und entfernt werden.

Es gibt aber auch bedingten toten Code. Dies ist Code, der zum Zeitpunkt der Kompilierung nicht bekannt ist und nur zur Laufzeit erkannt werden kann. Beispielsweise kann eine Software so konfiguriert werden, dass bestimmte Funktionen je nach Benutzerpräferenz ein- oder ausgeschlossen werden, wodurch bestimmte Codeabschnitte in bestimmten Szenarien scheinbar tot erscheinen. Das ist kein wirklich toter Code.

Es gibt spezielle Tools, mit denen Sie Tests durchführen, Abhängigkeiten auflösen, bedingten toten Code entfernen und den nützlichen Code zur Laufzeit aus Effizienzgründen neu kombinieren können. Dies wird als dynamische Eliminierung von totem Code bezeichnet. Aber wie Sie sehen, geht es über den Rahmen von Compilern hinaus.

dspfnder
quelle
5
"Unbedingter toter Code kann von fortgeschrittenen Compilern erkannt und entfernt werden." Dies scheint nicht wahrscheinlich. Code-Deadness kann vom Ergebnis einer bestimmten Funktion abhängen, und diese bestimmte Funktion kann beliebige Probleme lösen. Ihre Aussage besagt also, dass fortgeschrittene Compiler beliebige Probleme lösen können.
Taemyr
6
@Taemyr Dann wäre es nicht bekannt, bedingungslos tot zu sein, oder?
JAB
1
@Taemyr Du scheinst das Wort "bedingungslos" falsch zu verstehen. Wenn der Code-Deadness vom Ergebnis einer Funktion abhängt, handelt es sich um einen bedingten Deadcode. Die "Bedingung" ist das Ergebnis der Funktion. Um "bedingungslos" zu sein, müsste es nicht von einem Ergebnis abhängen.
Kyeotic
12

Ein einfaches Beispiel:

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;
}

Nehmen wir nun an, dass der Port 0x100 nur 0 oder 1 zurückgibt. In diesem Fall kann der Compiler nicht herausfinden, dass der elseBlock niemals ausgeführt wird.

In diesem grundlegenden Beispiel jedoch:

bool boolVal = /*anything boolean*/;

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

Hier kann der Compiler die berechnen else Block ein toter Code ist. Der Compiler kann also nur dann vor dem toten Code warnen, wenn er über genügend Daten verfügt, um den toten Code herauszufinden, und er sollte auch wissen, wie diese Daten angewendet werden, um herauszufinden, ob der angegebene Block ein toter Code ist.

BEARBEITEN

Manchmal sind die Daten zum Zeitpunkt der Kompilierung einfach nicht verfügbar:

// File a.cpp
bool boolMethod();

bool boolVal = boolMethod();

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

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

Beim Kompilieren von a.cpp kann der Compiler nicht wissen, dass boolMethodimmer zurückgegeben wird true.

Alex Lop.
quelle
1
Obwohl dies absolut richtig ist, dass der Compiler es nicht weiß, denke ich, dass es im Geiste der Frage liegt, auch zu fragen, ob der Linker es wissen kann.
Casey Kuball
1
@Darthfett Es liegt nicht in der Verantwortung des Linkers . Linker analysiert den Inhalt des kompilierten Codes nicht. Der Linker (im Allgemeinen) verknüpft nur die Methoden und die globalen Daten, der Inhalt ist ihm egal. Einige Compiler haben jedoch die Möglichkeit, die Quelldateien (wie ICC) zu verketten und anschließend die Optimierung durchzuführen. In diesem Fall wird der Fall unter BEARBEITEN behandelt, aber diese Option wirkt sich auf die Kompilierungszeit aus, insbesondere wenn das Projekt groß ist.
Alex Lop.
Diese Antwort scheint mir irreführend; Sie geben zwei Beispiele an, bei denen dies nicht möglich ist, weil nicht alle Informationen verfügbar sind. Sollten Sie jedoch nicht sagen, dass dies unmöglich ist, selbst wenn die Informationen vorhanden sind?
Anton Golov
@AntonGolovEs ist nicht immer wahr. In vielen Fällen, wenn die Informationen vorhanden sind, können die Compiler den toten Code erkennen und optimieren.
Alex Lop.
@abforce nur ein Codeblock. Es hätte alles andere sein können. :)
Alex Lop.
4

Dem Compiler fehlen immer einige Kontextinformationen. Sie wissen vielleicht, dass ein Doppelwert niemals 2 überschreitet, da dies ein Merkmal der mathematischen Funktion ist, die Sie aus einer Bibliothek verwenden. Der Compiler sieht nicht einmal den Code in der Bibliothek, und er kann niemals alle Merkmale aller mathematischen Funktionen kennen und alle unerwünschten und komplizierten Möglichkeiten erkennen, sie zu implementieren.

cdonat
quelle
4

Der Compiler sieht nicht unbedingt das gesamte Programm. Ich könnte ein Programm haben, das eine gemeinsam genutzte Bibliothek aufruft, die eine Funktion in meinem Programm aufruft, die nicht direkt aufgerufen wird.

Eine Funktion, die in Bezug auf die Bibliothek, für die sie kompiliert wurde, tot ist, könnte also lebendig werden, wenn diese Bibliothek zur Laufzeit geändert wird.

Steve Sanbeg
quelle
3

Wenn ein Compiler den gesamten toten Code genau eliminieren könnte, würde er als Interpreter bezeichnet .

Stellen Sie sich dieses einfache Szenario vor:

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

my_func() kann beliebigen Code enthalten, und damit der Compiler feststellen kann, ob er true oder false zurückgibt, muss er entweder den Code ausführen oder etwas tun, das funktional dem Ausführen des Codes entspricht.

Die Idee eines Compilers ist, dass er nur eine teilweise Analyse des Codes durchführt, wodurch die Arbeit einer separaten laufenden Umgebung vereinfacht wird. Wenn Sie eine vollständige Analyse durchführen, ist dies kein Compiler mehr.


Wenn Sie den Compiler als eine Funktion betrachten c(), wo c(source)=compiled codeund die laufende Umgebung als r(), wo r(compiled code)=program output, müssen Sie den Wert von berechnen, um die Ausgabe für einen beliebigen Quellcode zu bestimmen r(c(source code)). Wenn Rechen c()das Wissen des Wertes erfordert r(c())für jede Eingabe, gibt es keine Notwendigkeit für einen separaten r()und c(): Sie nur eine Funktion ableiten i()aus , c()so dass i(source)=program output.

biziclop
quelle
2

Andere haben das Problem des Anhaltens usw. kommentiert. Diese gelten im Allgemeinen für Teile von Funktionen. Es kann jedoch schwierig / unmöglich sein zu wissen, ob auch nur ein ganzer Typ (Klasse / usw.) verwendet wird oder nicht.

In .NET / Java / JavaScript und anderen zur Laufzeit gesteuerten Umgebungen hindert nichts das Laden von Typen über Reflection. Dies ist bei Abhängigkeitsinjektions-Frameworks beliebt und angesichts der Deserialisierung oder des Ladens dynamischer Module noch schwieriger zu begründen.

Der Compiler kann nicht wissen, ob solche Typen geladen werden würden. Ihre Namen könnten zur Laufzeit aus externen Konfigurationsdateien stammen.

Möglicherweise möchten Sie nach Baumschütteln suchen, was ein häufiger Begriff für Tools ist, die versuchen, nicht verwendete Untergraphen von Code sicher zu entfernen.

Drew Noakes
quelle
Ich weiß nichts über Java und Javascript, aber .NET hat tatsächlich ein Resharper-Plugin für diese Art der DI-Erkennung (Agent Mulder genannt). Natürlich kann es keine Konfigurationsdateien erkennen, aber es kann Confit im Code erkennen (was viel beliebter ist).
Krawatten
2

Nehmen Sie eine Funktion

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

Können Sie beweisen, dass actnumberdas niemals 2so sein wird, dass Action2()es niemals heißt ...?

CiaPan
quelle
7
Wenn Sie die Aufrufer der Funktion analysieren können, können Sie dies möglicherweise, ja.
Abligh
2
@abligh Aber der Compiler kann normalerweise nicht den gesamten aufrufenden Code analysieren. Selbst wenn dies möglich wäre, erfordert die vollständige Analyse möglicherweise nur eine Simulation aller möglichen Kontrollflüsse, was aufgrund der benötigten Ressourcen und der benötigten Zeit fast immer einfach unmöglich ist. Also selbst wenn theoretisch es existiert ein Beweis dafür , dass ‚ Action2()nie genannt werden‘ ist es unmöglich , den Anspruch in der Praxis zu beweisen - nicht vollständig durch einen Compiler gelöst werden . Der Unterschied ist wie 'es gibt eine Zahl X' vs. 'wir können die Zahl X dezimal schreiben'. Für einige X wird das letztere niemals passieren, obwohl das erstere wahr ist.
CiaPan
Dies ist eine schlechte Antwort. Die anderen Antworten beweisen, dass es unmöglich ist zu wissen, ob actnumber==2. Diese Antwort behauptet lediglich, es sei schwierig, ohne auch nur eine Komplexität anzugeben.
MSalters
1

Ich bin nicht einverstanden mit dem Problem des Anhaltens. Ich würde einen solchen Code nicht als tot bezeichnen, obwohl er in Wirklichkeit niemals erreicht werden kann.

Betrachten wir stattdessen:

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();
}

(Typ- und Überlauffehler ignorieren) Toter Code?

Loren Pechtel
quelle
2
Der letzte Satz von Fermat wurde 1994 bewiesen. Eine korrekte Implementierung Ihrer Methode würde FermatWasWrong also niemals ausführen. Ich vermute, dass Ihre Implementierung FermatWasWrong ausführen wird, da Sie die Präzisionsgrenze von Floats erreichen können.
Taemyr
@ Taemyr Aha! Dieses Programm testet Fermats letzten Satz nicht korrekt. Ein Gegenbeispiel für den Test ist N = 3, A = 65536, B = 65536 (was Test = 0 ergibt)
user253751
@immibis Ja, ich habe verpasst, dass es int überläuft, bevor die Präzision der Floats zu einem Problem wird.
Taemyr
@immibis Beachten Sie den unteren Rand meines Beitrags: Ignorieren Sie die Typ- und Überlauffehler. Ich habe nur das, was ich für ein ungelöstes Problem hielt, als Grundlage für eine Entscheidung genommen - ich weiß, dass der Code nicht perfekt ist. Es ist ein Problem, das sowieso nicht brutal erzwungen werden kann.
Loren Pechtel
-1

Schauen Sie sich dieses Beispiel an:

public boolean isEven(int i){

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

Der Compiler kann nicht wissen, dass ein int nur gerade oder ungerade sein kann. Daher muss der Compiler in der Lage sein, die Semantik Ihres Codes zu verstehen. Wie soll dies umgesetzt werden? Der Compiler kann nicht sicherstellen, dass die niedrigste Rückgabe niemals ausgeführt wird. Daher kann der Compiler den toten Code nicht erkennen.

Benutzer
quelle
1
Ähm, wirklich? Wenn ich das in C # + ReSharper schreibe, bekomme ich ein paar Hinweise. Wenn ich ihnen folge, bekomme ich endlich den Code return i%2==0;.
Thomas Weller
10
Ihr Beispiel ist zu einfach, um zu überzeugen. Der spezielle Fall von i % 2 == 0und i % 2 != 0erfordert nicht einmal eine Überlegung über den Wert eines ganzzahligen Modulo einer Konstanten (was immer noch einfach zu tun ist), sondern nur die Eliminierung von Unterausdrücken und das allgemeine Prinzip (sogar Kanonisierung), if (cond) foo; if (!cond) bar;das vereinfacht werden kann if (cond) foo; else bar;. Natürlich ist "Semantik verstehen" ein sehr schwieriges Problem, aber dieser Beitrag zeigt weder, dass dies der Fall ist, noch, dass die Lösung dieses schwierigen Problems für die Erkennung von totem Code erforderlich ist.
5
In Ihrem Beispiel erkennt ein optimierender Compiler den allgemeinen Unterausdruck i % 2und zieht ihn in eine temporäre Variable. Es wird dann erkannt, dass sich die beiden ifAnweisungen gegenseitig ausschließen und als geschrieben werden können if(a==0)...else..., und dann festgestellt, dass alle möglichen Ausführungspfade die ersten beiden returnAnweisungen durchlaufen und daher die dritte returnAnweisung toter Code ist. (Ein guter Optimierungs-Compiler ist noch aggressiver: GCC hat meinen Testcode in zwei Bitmanipulationsoperationen umgewandelt.)
Mark
1
Dieses Beispiel ist gut für mich. Dies ist der Fall, wenn ein Compiler einige sachliche Umstände nicht kennt. Das gilt auch für if (availableMemory()<0) then {dead code}.
Little Santi
1
@LittleSanti: Tatsächlich wird GCC feststellen, dass alles , was Sie dort geschrieben haben, toter Code ist! Es ist nicht nur der {dead code}Teil. GCC entdeckt dies, indem es nachweist, dass ein unvermeidbarer Überlauf mit vorzeichenbehafteten Ganzzahlen vorliegt. Der gesamte Code in diesem Bogen im Ausführungsdiagramm ist daher toter Code. GCC kann sogar den bedingten Zweig entfernen, der zu diesem Bogen führt.
MSalters