Por que a detecção de código morto não pode ser totalmente resolvida por um compilador?

Os compiladores que tenho usado em C ou Java têm prevenção de código morto (aviso quando uma linha nunca será executada). Meu professor diz que esse problema nunca pode ser totalmente resolvido pelos compiladores. Fiquei me perguntando por que isso é. Eu não estou muito familiarizado com a codificação real dos compiladores, pois esta é uma classe baseada em teoria. Mas eu queria saber o que eles verificam (como possíveis seqüências de caracteres de entrada versus entradas aceitáveis ​​etc.) e por que isso é insuficiente.

O problema do código morto está relacionado ao problema da parada .

Alan Turing provou que é impossível escrever um algoritmo geral que receberá um programa e seja capaz de decidir se esse programa é interrompido para todas as entradas. Você pode escrever esse algoritmo para tipos específicos de programas, mas não para todos os programas.

Como isso se relaciona com o código morto?

O problema de parada é redutível ao problema de encontrar código morto. Ou seja, se você encontrar um algoritmo capaz de detectar código morto em qualquer programa, poderá usá-lo para testar se algum programa será interrompido. Desde que isso provou ser impossível, segue-se que escrever um algoritmo para código morto também é impossível.

Como você transfere um algoritmo para código morto para um algoritmo para o problema de parada?

Simples: você adiciona uma linha de código após o final do programa que deseja verificar se há interrupção. Se o seu detector de código morto detectar que esta linha está morta, você saberá que o programa não é interrompido. Caso contrário, você sabe que o seu programa é interrompido (chega à última linha e depois à sua linha de código adicionada).

Os compiladores geralmente verificam se há coisas que podem ser comprovadas em tempo de compilação como mortas. Por exemplo, blocos que dependem de condições que podem ser determinadas como falsas no tempo de compilação. Ou qualquer declaração após a return(dentro do mesmo escopo).

Esses são casos específicos e, portanto, é possível escrever um algoritmo para eles. Pode ser possível escrever algoritmos para casos mais complicados (como um algoritmo que verifica se uma condição é sintaticamente uma contradição e, portanto, sempre retornará falsa), mas ainda assim, isso não cobriria todos os casos possíveis.

Bem, vamos pegar a prova clássica da indecidibilidade do problema de parada e alterar o detector de parada para um detector de código morto!

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

Se YourVendor.Compiler.HasDeadCode(quine_text)retornos false, em seguida, a linha System.Console.WriteLn("Dead code!");não será sempre executada, de modo que este programa realmente não têm código morto, e o detector estava errado.

Porém, se retornar true, a linha System.Console.WriteLn("Dead code!");será executada e, como não há mais código no programa, não há código morto; então, novamente, o detector estava errado.

Portanto, um detector de código morto que retorna apenas "Existe código morto" ou "Não há código morto" às vezes deve gerar respostas erradas.

Se o problema da parada for muito obscuro, pense dessa maneira.

Pegue um problema matemático que se acredita verdadeiro para todo número inteiro positivo n , mas que não foi provado verdadeiro para todo n . Um bom exemplo seria a conjectura de Goldbach , de que qualquer número inteiro positivo maior que dois pode ser representado pela soma de dois números primos. Em seguida (com uma biblioteca bigint apropriada), execute este programa (segue o pseudocódigo):

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

A implementação de isGoldbachsConjectureTrueFor()é deixada como um exercício para o leitor, mas para esse propósito pode ser uma iteração simples sobre todos os números primos menores quen

Agora, logicamente, o acima deve ser o equivalente a:

 for (; ;) {
 }

(ou seja, um loop infinito) ou

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

como a conjectura de Goldbach deve ser verdadeira ou não verdadeira. Se um compilador sempre pudesse eliminar o código morto, definitivamente haveria código morto a ser eliminado aqui em ambos os casos. No entanto, ao fazer isso, pelo menos, seu compilador precisaria resolver problemas arbitrariamente difíceis. Poderíamos fornecer problemas comprovadamente difíceis que precisariam ser resolvidos (por exemplo, problemas de NP-completos) para determinar qual parte do código eliminar. Por exemplo, se usarmos este programa:

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

sabemos que o programa imprimirá "Valor SHA encontrado" ou "Valor SHA não encontrado" (pontos de bônus se você puder me dizer qual é o verdadeiro). No entanto, para um compilador ser capaz de otimizar razoavelmente isso levaria da ordem de 2 ^ 2048 iterações. Seria, de fato, uma ótima otimização, pois eu prevejo que o programa acima funcionaria (ou poderia) até a morte pelo calor do universo, em vez de imprimir qualquer coisa sem otimização.

Não sei se C ++ ou Java têm uma Evalfunção de tipo, mas muitas linguagens permitem que você chame métodos por nome . Considere o seguinte exemplo de VBA (artificial).

Dim methodName As String

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

Application.Run(methodName)

O nome do método a ser chamado é impossível saber até o tempo de execução. Portanto, por definição, o compilador não pode saber com certeza absoluta que um método específico nunca é chamado.

Na verdade, dado o exemplo de chamar um método pelo nome, a lógica de ramificação nem é necessária. Simplesmente dizendo

Application.Run("Bar")

É mais do que o compilador pode determinar. Quando o código é compilado, tudo o que o compilador sabe é que um determinado valor de string está sendo passado para esse método. Ele não verifica se esse método existe até o tempo de execução. Se o método não for chamado em outro lugar, por métodos mais normais, uma tentativa de encontrar métodos mortos pode retornar falsos positivos. O mesmo problema existe em qualquer idioma que permita que o código seja chamado via reflexão.

Código morto incondicional pode ser detectado e removido por compiladores avançados.

Mas também há código morto condicional. Esse é um código que não pode ser conhecido no momento da compilação e só pode ser detectado durante o tempo de execução. Por exemplo, um software pode ser configurável para incluir ou excluir determinados recursos, dependendo da preferência do usuário, tornando determinadas seções de código aparentemente inoperantes em cenários específicos. Isso não é um código morto real.

Existem ferramentas específicas que podem fazer testes, resolver dependências, remover código morto condicional e recombinar o código útil em tempo de execução para obter eficiência. Isso é chamado eliminação dinâmica de código morto. Mas como você pode ver, está além do escopo dos compiladores.

Um exemplo simples:

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

Agora suponha que a porta 0x100 seja projetada para retornar apenas 0 ou 1. Nesse caso, o compilador não pode descobrir que o elsebloco nunca será executado.

No entanto, neste exemplo básico:

bool boolVal = /*anything boolean*/;

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

Aqui o compilador pode calcular que o elsebloco é um código morto. Portanto, o compilador pode avisar sobre o código morto apenas se tiver dados suficientes para descobrir o código morto e também deve saber como aplicar esses dados para descobrir se o bloco fornecido é um código morto.

EDITAR

Às vezes, os dados simplesmente não estão disponíveis no momento da compilação:

// File a.cpp
bool boolMethod();

bool boolVal = boolMethod();

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

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

Ao compilar a.cpp, o compilador não pode saber que boolMethodsempre retorna true.

Sempre falta ao compilador algumas informações de contexto. Por exemplo, você deve saber que um valor duplo nunca excede 2, porque esse é um recurso da função matemática que você usa em uma biblioteca. O compilador nem vê o código na biblioteca e nunca pode conhecer todos os recursos de todas as funções matemáticas e detectar todas as maneiras complicadas e complicadas de implementá-las.

O compilador não vê necessariamente o programa inteiro. Eu poderia ter um programa que chama uma biblioteca compartilhada, que chama de volta para uma função no meu programa que não é chamada diretamente.

Portanto, uma função que está morta em relação à biblioteca em que é compilada pode se tornar viva se essa biblioteca for alterada em tempo de execução.

Se um compilador pudesse eliminar todo o código morto com precisão, ele seria chamado de intérprete .

Considere este cenário simples:

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

my_func() pode conter código arbitrário e, para que o compilador determine se ele retorna verdadeiro ou falso, ele precisará executar o código ou fazer algo que seja funcionalmente equivalente à execução do código.

A idéia de um compilador é que ele execute apenas uma análise parcial do código, simplificando assim o trabalho de um ambiente de execução separado. Se você realizar uma análise completa, não será mais um compilador.

Se você considerar o compilador como uma função c(), onde c(source)=compiled codee o ambiente em execução como r(), onde r(compiled code)=program output, para determinar a saída de qualquer código-fonte do qual você deve calcular o valor r(c(source code)). Se cálculo c()requer o conhecimento do valor r(c())para qualquer entrada, não há necessidade de um separado r()e c(): você só pode derivar uma função i()de c()tal que i(source)=program output.

Outros comentaram sobre o problema da parada e assim por diante. Eles geralmente se aplicam a partes de funções. No entanto, pode ser difícil / impossível saber se um tipo inteiro (classe / etc) é usado ou não.

No .NET / Java / JavaScript e em outros ambientes orientados a tempo de execução, não há nada que impeça os tipos de serem carregados via reflexão. Isso é popular nas estruturas de injeção de dependência e é ainda mais difícil de ser considerado diante da desserialização ou do carregamento dinâmico do módulo.

O compilador não pode saber se esses tipos seriam carregados. Seus nomes podem vir de arquivos de configuração externos em tempo de execução.

Você pode procurar por trepidação de árvores, um termo comum para ferramentas que tentam remover com segurança subgráficos de código não utilizados.

Tome uma função

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

Você pode provar que actnumbernunca será 2assim Action2()e nunca será chamado ...?

Discordo do problema da parada. Eu não chamaria esse código de morto, embora, na realidade, nunca seja alcançado.

Em vez disso, vamos considerar:

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

(Ignore os erros de tipo e de estouro) Código morto?

Veja este exemplo:

public boolean isEven(int i){

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

O compilador não pode saber que um int só pode ser par ou ímpar. Portanto, o compilador deve ser capaz de entender a semântica do seu código. Como isso deve ser implementado? O compilador não pode garantir que o menor retorno nunca seja executado. Portanto, o compilador não pode detectar o código morto.