Почему невозможно полностью разрешить обнаружение кодового кода компилятором?

Ответ 1

Проблема с мертвым кодом связана с проблемой Halting.

Алан Тьюринг доказал, что невозможно написать общий алгоритм, которому будет дана программа, и иметь возможность решить, останавливается ли эта программа для всех входов. Вы можете написать такой алгоритм для определенных типов программ, но не для всех программ.

Как это относится к мертвому коду?

Проблема с остановкой сводится к проблеме поиска мертвого кода. То есть, если вы найдете алгоритм, который может обнаружить мертвый код в любой программе, вы можете использовать этот алгоритм для проверки того, остановится ли какая-либо программа. Поскольку это оказалось невозможным, из этого следует, что писать алгоритм для мертвого кода также невозможно.

Как вы передаете алгоритм для мертвого кода в алгоритм проблемы с остановкой?

Простой: вы добавляете строку кода после окончания программы, которую хотите проверить на остановке. Если ваш детектор мертвого кода обнаруживает, что эта линия мертва, вы знаете, что программа не останавливается. Если это не так, то вы знаете, что ваша программа останавливается (попадает в последнюю строку, а затем в вашу добавленную строку кода).

Компиляторы обычно проверяют вещи, которые могут быть доказаны во время компиляции, чтобы быть мертвым. Например, блоки, которые зависят от условий, которые могут быть определены как ложные во время компиляции. Или любой оператор после return (в пределах той же области).

Это конкретные случаи, и поэтому можно написать для них алгоритм. Возможно, можно написать алгоритмы для более сложных случаев (например, алгоритм, который проверяет синтаксически условие противоречия и поэтому всегда возвращает false), но тем не менее это не распространяется на все возможные случаи.

Ответ 2

Хорошо, возьмем классическое доказательство неразрешимости проблемы остановки и изменим детектор остановки на детектор мертвого кода!

Программа С#

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

Если YourVendor.Compiler.HasDeadCode(quine_text) возвращает false, тогда строка System.Console.WriteLn("Dead code!"); не будет выполняться, поэтому у этой программы действительно есть мертвый код, а детектор ошибочен.

Но если он вернет true, тогда будет выполнена строка System.Console.WriteLn("Dead code!");, и, поскольку в программе больше нет кода, нет никакого мертвого кода вообще, так что снова детектор был не прав.

Итак, у вас это есть, детектор мертвого кода, который возвращается только "Есть мертвый код" или "Нет мертвого кода", иногда должен давать неправильные ответы.

Ответ 3

Если проблема с остановкой слишком неясна, подумайте об этом таким образом.

Возьмите математическую задачу, которая считается верной для всего положительного целого числа n, но не доказана, что она верна для каждого n. Хорошим примером может быть гипотеза Голдбаха, что любое положительное четное целое число больше двух может быть представлено суммой двух простых чисел. Затем (с соответствующей библиотекой bigint) запустите эту программу (псевдокод следует):

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

Реализация isGoldbachsConjectureTrueFor() оставлена ​​как упражнение для читателя, но для этой цели может быть простая итерация по всем простым числам меньше n

Теперь логически указанное выше должно быть эквивалентно:

 for (; ;) {
 }

(т.е. бесконечный цикл) или

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

поскольку гипотеза Гольдбаха должна быть верной или неверной. Если компилятор всегда может исключить мертвый код, в этом случае определенно будет мертвый код, чтобы исключить его. Однако при этом, по крайней мере, ваш компилятор должен будет решить произвольно трудные проблемы. Мы могли бы обеспечить проблемы достаточно трудно, чтобы решить (например, проблемы с NP-полным), чтобы определить, какой бит кода нужно устранить. Например, если мы возьмем эту программу:

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

мы знаем, что программа либо выведет "Найденное значение SHA", либо "Не найденное значение SHA" (бонусные баллы, если вы можете сказать мне, какая из них истинна). Однако, чтобы компилятор мог разумно оптимизировать, что потребовало бы порядка 2 ^ 2048 итераций. На самом деле это была бы большая оптимизация, поскольку я предсказывал, что вышеуказанная программа будет (или может) работать до жары смерти Вселенной, а не печатать что-либо без оптимизации.

Ответ 4

Я не знаю, имеет ли С++ или Java функцию типа Eval, но многие языки позволяют вам вызывать методы по имени. Рассмотрим следующий (надуманный) пример VBA.

Dim methodName As String

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

Application.Run(methodName)

Имя метода, который будет вызываться, невозможно узнать до выполнения. Поэтому, по определению, компилятор не может с абсолютной уверенностью знать, что конкретный метод никогда не вызывается.

Собственно, на примере вызова метода по имени логика разветвления даже не нужна. Просто говоря

Application.Run("Bar")

Больше, чем может определить компилятор. Когда код компилируется, все компиляторы знают, что определенное значение строки передается этому методу. Он не проверяет, существует ли этот метод до выполнения. Если метод не вызывается в другом месте, используя более обычные методы, попытка найти мертвые методы может возвращать ложные срабатывания. Такая же проблема существует на любом языке, который позволяет коду вызывать через отражение.

Ответ 5

Простой пример:

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

Теперь предположим, что порт 0x100 предназначен для возврата только 0 или 1. В этом случае компилятор не может понять, что блок else никогда не будет выполнен.

Однако в этом базовом примере:

bool boolVal = /*anything boolean*/;

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

Здесь компилятор может вычислить блок else - это мертвый код. Поэтому компилятор может предупреждать о мертвом коде, только если у него достаточно данных для определения мертвого кода, а также он должен знать, как применять эти данные, чтобы выяснить, является ли данный блок мертвым кодом.

ИЗМЕНИТЬ

Иногда данные во время компиляции недоступны:

// File a.cpp
bool boolMethod();

bool boolVal = boolMethod();

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

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

При компиляции a.cpp компилятор не может знать, что boolMethod всегда возвращает true.

Ответ 6

Безусловный мертвый код может быть обнаружен и удален передовыми компиляторами.

Но есть также условный мертвый код. Это код, который не может быть известен во время компиляции и может быть обнаружен только во время выполнения. Например, программное обеспечение может быть сконфигурировано для включения или исключения определенных функций в зависимости от предпочтений пользователя, что делает определенные разделы кода, казалось бы, мертвыми в определенных сценариях. Это не настоящий мертвый код.

Существуют специальные инструменты, которые могут выполнять тестирование, разрешать зависимости, удалять условный мертвый код и рекомбинировать полезный код во время выполнения для повышения эффективности. Это называется удалением динамического кода. Но, как вы видите, это выходит за рамки компиляторов.

Ответ 7

В компиляторе всегда будет отсутствовать контекстная информация. Например. вы можете знать, что двойное значение никогда не выдает 2, потому что это функция математической функции, которую вы используете из библиотеки. Компилятор даже не видит код в библиотеке, и он никогда не узнает всех функций всех математических функций и не обнаружит все сложные и сложные способы их реализации.

Ответ 8

Компилятор не обязательно видит всю программу. Я мог бы иметь программу, которая вызывает общую библиотеку, которая возвращает функцию в мою программу, которая не вызывается напрямую.

Таким образом, функция, которая мертва относительно библиотеки, скомпилированной против нее, может стать живой, если эта библиотека была изменена во время выполнения.

Ответ 9

Если компилятор может точно удалить весь мертвый код, он будет называться интерпретатором.

Рассмотрим этот простой сценарий:

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

my_func() может содержать произвольный код и для того, чтобы компилятор мог определить, вернет ли он true или false, он либо должен будет запустить код, либо сделать что-то функционально эквивалентное запуску кода.

Идея компилятора заключается в том, что он выполняет только частичный анализ кода, что упрощает работу отдельной рабочей среды. Если вы выполните полный анализ, это уже не компилятор.

Если вы рассматриваете компилятор как функцию c(), где c(source)=compiled code, а работающая среда как r(), где r(compiled code)=program output, то для определения вывода для любого исходного кода вам нужно вычислить значение r(c(source code)). Если для вычисления c() требуется знание значения r(c()) для любого ввода, нет необходимости в отдельном r() и c(): вы можете просто получить функцию i() из c(), чтобы i(source)=program output.

Ответ 10

Возьмем функцию

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

Можете ли вы доказать, что actnumber никогда не будет 2, чтобы Action2() никогда не вызывался...?

Ответ 11

Другие прокомментировали проблему остановки и т.д. Они обычно применяются к частям функций. Однако может быть трудно/невозможно узнать, используется ли даже целый тип (класс/etc) или нет.

В .NET/Java/JavaScript и других средах, управляемых во время выполнения, нет ничего, что останавливало бы типы, загружаемые через отражение. Это популярно в рамках фреймворков с зависимостями, и еще труднее рассуждать перед лицом десериализации или загрузки динамического модуля.

Компилятор не может знать, будут ли загружены такие типы. Их имена могут появляться из внешних файлов конфигурации во время выполнения.

Вам может понравиться искать дрожание дерева, что является общим термином для инструментов, которые пытаются безопасно удалить неиспользуемые подграфы кода.

Ответ 12

Я не согласен с проблемой остановки. Я бы не назвал такой код мертвым, хотя на самом деле он никогда не будет достигнут.

Вместо этого рассмотрим:

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

(Игнорировать ошибки типа и переполнения) Мертвый код?

Ответ 13

Посмотрите на этот пример:

public boolean isEven(int i){

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

Компилятор не может знать, что int может быть только четным или нечетным. Поэтому компилятор должен уметь понимать семантику вашего кода. Как это должно быть реализовано? Компилятор не может гарантировать, что самый низкий доход никогда не будет выполнен. Поэтому компилятор не может обнаружить мертвый код.