Pourquoi la détection de code mort ne peut-elle pas être entièrement résolue par un compilateur?

Les compilateurs que j'utilisais en C ou Java ont une prévention de code mort (avertissement lorsqu'une ligne ne sera jamais exécutée). Mon professeur dit cependant que ce problème ne peut jamais être entièrement résolu par les compilateurs. Je me demandais pourquoi. Je ne suis pas trop familier avec le codage réel des compilateurs car il s'agit d'une classe basée sur la théorie. Mais je me demandais ce qu'ils vérifient (comme les chaînes d'entrée possibles par rapport aux entrées acceptables, etc.), et pourquoi cela est insuffisant.

Le problème de code mort est lié au problème d'arrêt .

Alan Turing a prouvé qu'il est impossible d'écrire un algorithme général auquel sera attribué un programme et de pouvoir décider si ce programme s'arrête pour toutes les entrées. Vous pourrez peut-être écrire un tel algorithme pour des types de programmes spécifiques, mais pas pour tous les programmes.

Quel est le lien avec le code mort?

Le problème Halting est réductible au problème de la recherche de code mort. Autrement dit, si vous trouvez un algorithme qui peut détecter le code mort dans n'importe quel programme, vous pouvez utiliser cet algorithme pour tester si un programme va s'arrêter. Comme cela s'est avéré impossible, il s'ensuit que l'écriture d'un algorithme pour le code mort est également impossible.

Comment transférez-vous un algorithme pour le code mort dans un algorithme pour le problème d'arrêt?

Simple: vous ajoutez une ligne de code après la fin du programme dont vous souhaitez vérifier l'arrêt. Si votre détecteur de code mort détecte que cette ligne est morte, alors vous savez que le programme ne s'arrête pas. Si ce n'est pas le cas, vous savez que votre programme s'arrête (arrive à la dernière ligne, puis à votre ligne de code ajoutée).

Les compilateurs vérifient généralement les éléments qui peuvent être prouvés au moment de la compilation comme morts. Par exemple, des blocs qui dépendent de conditions qui peuvent être déterminées comme fausses au moment de la compilation. Ou toute instruction après un return(dans la même portée).

Ce sont des cas spécifiques, et il est donc possible d'écrire un algorithme pour eux. Il peut être possible d'écrire des algorithmes pour des cas plus compliqués (comme un algorithme qui vérifie si une condition est syntaxiquement une contradiction et par conséquent retournera toujours faux), mais cela ne couvrirait pas tous les cas possibles.

Eh bien, prenons la preuve classique de l'indécidabilité du problème d'arrêt et changeons le détecteur d'arrêt en détecteur de code mort!

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

S'il YourVendor.Compiler.HasDeadCode(quine_text)revient false, alors la ligne System.Console.WriteLn("Dead code!");ne sera jamais exécutée, donc ce programme a en fait un code mort et le détecteur était erroné.

Mais s'il revient true, alors la ligne System.Console.WriteLn("Dead code!");sera exécutée, et comme il n'y a plus de code dans le programme, il n'y a plus de code mort, donc encore une fois, le détecteur s'est trompé.

Donc voilà, un détecteur de code mort qui ne renvoie que "Il y a du code mort" ou "Il n'y a pas de code mort" doit parfois donner de mauvaises réponses.

Si le problème d'arrêt est trop obscur, pensez-y de cette façon.

Prenons un problème mathématique qui est censé être vrai pour tous les n entiers positifs , mais qui n'a pas été prouvé pour tous les n . Un bon exemple serait la conjecture de Goldbach, selon laquelle tout entier pair positif supérieur à deux peut être représenté par la somme de deux nombres premiers. Ensuite (avec une bibliothèque bigint appropriée) exécutez ce programme (le pseudocode suit):

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

L'implémentation de isGoldbachsConjectureTrueFor()est laissée comme un exercice pour le lecteur mais à cette fin pourrait être une simple itération sur tous les nombres premiers inférieurs àn

Maintenant, logiquement, ce qui précède doit être soit l'équivalent de:

 for (; ;) {
 }

(c'est-à-dire une boucle infinie) ou

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

car la conjecture de Goldbach doit être vraie ou fausse. Si un compilateur pouvait toujours éliminer le code mort, il y aurait certainement du code mort à éliminer ici dans les deux cas. Cependant, ce faisant, votre compilateur devra au moins résoudre des problèmes arbitrairement difficiles. Nous pourrions fournir des problèmes prouvablement dur qu'il faudrait résoudre (par exemple les problèmes NP-complets) pour déterminer quel bit de code à éliminer. Par exemple, si nous prenons ce programme:

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

nous savons que le programme imprimera soit "Valeur SHA trouvée" soit "Valeur SHA non trouvée" (points bonus si vous pouvez me dire laquelle est vraie). Cependant, pour qu'un compilateur puisse raisonnablement optimiser cela prendrait de l'ordre de 2 ^ 2048 itérations. Ce serait en fait une excellente optimisation car je prédis que le programme ci-dessus fonctionnerait (ou pourrait) fonctionner jusqu'à la mort thermique de l'univers plutôt que d'imprimer quoi que ce soit sans optimisation.

Je ne sais pas si C ++ ou Java ont une Evalfonction de type, mais de nombreux langages vous permettent d'appeler des méthodes par leur nom . Considérez l'exemple VBA (artificiel) suivant.

Dim methodName As String

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

Application.Run(methodName)

Le nom de la méthode à appeler est impossible à connaître jusqu'à l'exécution. Par conséquent, par définition, le compilateur ne peut pas savoir avec une certitude absolue qu'une méthode particulière n'est jamais appelée.

En fait, étant donné l'exemple de l'appel d'une méthode par son nom, la logique de branchement n'est même pas nécessaire. Dire simplement

Application.Run("Bar")

C'est plus que ce que le compilateur peut déterminer. Lorsque le code est compilé, tout ce que le compilateur sait, c'est qu'une certaine valeur de chaîne est transmise à cette méthode. Il ne vérifie pas si cette méthode existe jusqu'à l'exécution. Si la méthode n'est pas appelée ailleurs, via des méthodes plus normales, une tentative de recherche de méthodes mortes peut renvoyer des faux positifs. Le même problème existe dans n'importe quel langage qui permet d'appeler du code via la réflexion.

Le code mort inconditionnel peut être détecté et supprimé par des compilateurs avancés.

Mais il existe également un code mort conditionnel. Il s'agit d'un code qui ne peut pas être connu au moment de la compilation et ne peut être détecté que pendant l'exécution. Par exemple, un logiciel peut être configurable pour inclure ou exclure certaines fonctionnalités en fonction des préférences de l'utilisateur, ce qui rend certaines sections de code apparemment mortes dans des scénarios particuliers. Ce n'est pas un vrai code mort.

Il existe des outils spécifiques qui peuvent effectuer des tests, résoudre les dépendances, supprimer le code mort conditionnel et recombiner le code utile lors de l'exécution pour plus d'efficacité. C'est ce qu'on appelle l'élimination dynamique du code mort. Mais comme vous pouvez le voir, cela dépasse le cadre des compilateurs.

Un exemple simple:

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

Supposons maintenant que le port 0x100 est conçu pour renvoyer uniquement 0 ou 1. Dans ce cas, le compilateur ne peut pas comprendre que le elsebloc ne sera jamais exécuté.

Cependant, dans cet exemple de base:

bool boolVal = /*anything boolean*/;

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

Ici, le compilateur peut calculer si le elsebloc est un code mort. Ainsi, le compilateur peut avertir du code mort uniquement s'il dispose de suffisamment de données pour comprendre le code mort et il doit également savoir comment appliquer ces données afin de déterminer si le bloc donné est un code mort.

ÉDITER

Parfois, les données ne sont tout simplement pas disponibles au moment de la compilation:

// File a.cpp
bool boolMethod();

bool boolVal = boolMethod();

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

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

Lors de la compilation de a.cpp, le compilateur ne peut pas savoir que cela boolMethodrevient toujours true.

Le compilateur manquera toujours d'informations sur le contexte. Par exemple, vous savez peut-être qu'une valeur double n'excède jamais 2, car c'est une caractéristique de la fonction mathématique que vous utilisez à partir d'une bibliothèque. Le compilateur ne voit même pas le code dans la bibliothèque, et il ne peut jamais connaître toutes les fonctionnalités de toutes les fonctions mathématiques et détecter toutes les manières compliquées et compliquées de les implémenter.

Le compilateur ne voit pas nécessairement tout le programme. Je pourrais avoir un programme qui appelle une bibliothèque partagée, qui rappelle une fonction de mon programme qui n'est pas appelée directement.

Ainsi, une fonction qui est morte par rapport à la bibliothèque avec laquelle elle est compilée pourrait devenir active si cette bibliothèque était modifiée au moment de l'exécution.

Si un compilateur pouvait éliminer avec précision tout le code mort, il serait appelé interprète .

Considérez ce scénario simple:

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

my_func() peut contenir du code arbitraire et pour que le compilateur détermine s'il renvoie vrai ou faux, il devra soit exécuter le code, soit faire quelque chose qui est fonctionnellement équivalent à l'exécution du code.

L'idée d'un compilateur est qu'il n'effectue qu'une analyse partielle du code, simplifiant ainsi le travail d'un environnement d'exécution distinct. Si vous effectuez une analyse complète, ce n'est plus un compilateur.

Si vous considérez le compilateur comme une fonction c(), où c(source)=compiled code, et l'environnement d'exécution comme r(), où r(compiled code)=program output, alors pour déterminer la sortie de tout code source, vous devez calculer la valeur der(c(source code)) . Si calcul c()nécessite la connaissance de la valeur r(c())pour toute entrée, il n'y a pas besoin d'un séparé r()et c()vous pouvez simplement tirer une fonction i()de c()telle sorte que i(source)=program output.

D'autres ont commenté le problème de l'arrêt, etc. Celles-ci s'appliquent généralement à des portions de fonctions. Cependant, il peut être difficile / impossible de savoir si même un type entier (classe / etc) est utilisé ou non.

Dans .NET / Java / JavaScript et d'autres environnements pilotés par le runtime, il n'y a rien qui empêche le chargement des types via la réflexion. Ceci est populaire avec les frameworks d'injection de dépendance, et est encore plus difficile à raisonner face à la désérialisation ou au chargement de module dynamique.

Le compilateur ne peut pas savoir si de tels types seraient chargés. Leurs noms pourraient provenir de fichiers de configuration externes lors de l'exécution.

Vous voudrez peut-être chercher autour de l' arbre qui est un terme courant pour les outils qui tentent de supprimer en toute sécurité les sous-graphiques de code inutilisés.

Prenez une fonction

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

Pouvez-vous prouver que actnumbercela ne sera jamais 2ainsi que ce Action2()n'est jamais appelé ...?

Je ne suis pas d'accord sur le problème de l'arrêt. Je n'appellerais pas un tel code mort même si en réalité il ne sera jamais atteint.

Considérons plutôt:

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

(Ignorer les erreurs de type et de débordement) Code mort?

Regardez cet exemple:

public boolean isEven(int i){

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

Le compilateur ne peut pas savoir qu'un int ne peut être que pair ou impair. Par conséquent, le compilateur doit être capable de comprendre la sémantique de votre code. Comment cela devrait-il être mis en œuvre? Le compilateur ne peut pas garantir que le retour le plus bas ne sera jamais exécuté. Par conséquent, le compilateur ne peut pas détecter le code mort.