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

192

Компиляторы, которые я использовал в C или Java, имеют предотвращение мертвого кода (предупреждение, когда строка никогда не будет выполнена). Мой профессор говорит, что эта проблема никогда не может быть полностью решена компиляторами. Мне было интересно, почему это так. Я не слишком знаком с фактическим кодированием компиляторов, так как это теоретический класс. Но мне было интересно, что они проверяют (например, возможные строки ввода против допустимых входных данных и т. Д.), И почему этого недостаточно.

ученик
источник
91
сделайте цикл, поместите код после него, затем примените en.wikipedia.org/wiki/Halting_problem
zapl
48
if (isPrime(1234234234332232323423)){callSomething();}этот код когда-нибудь будет вызывать или нет? Есть много других примеров, когда решение о том, вызывать ли функцию когда-либо, намного дороже, чем просто включить ее в программу.
idclev 463035818
33
public static void main(String[] args) {int counterexample = findCollatzConjectureCounterexample(); System.out.println(counterexample);}<- является ли println вызов мертвым кодом? Даже люди не могут решить это!
user253751
15
@ tobi303 не очень хороший пример, на самом деле легко вычислять простые числа ... просто не относить их относительно эффективно. Проблема остановки не в NP, она неразрешима.
en_Knight
57
@alephzero и en_Knight - Вы оба не правы. isPrime - отличный пример. Вы сделали предположение, что функция проверяет простое число. Может быть, это был серийный номер, и он выполняет поиск в базе данных, чтобы определить, является ли пользователь участником Amazon Prime? Причина того, что это отличный пример, заключается в том, что единственный способ узнать, является ли условие постоянным или нет, состоит в том, чтобы фактически выполнить функцию isPrime. Так что теперь это потребует, чтобы компилятор также был интерпретатором. Но это все еще не решило бы те случаи, когда данные изменчивы.
Данк

Ответы:

275

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

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

Как это связано с мертвым кодом?

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

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

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


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

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

RealSkeptic
источник
8
Я бы сказал, что проблема остановки здесь не применима, так как каждая платформа, являющаяся целью компиляции каждого компилятора в реальном мире, имеет максимальный объем данных, к которым она может получить доступ, поэтому она будет иметь максимальное количество состояний, означающих, что это на самом деле это конечный автомат, а не машина Тьюринга. Проблема остановки не является неразрешимой для FSM, поэтому любой компилятор в реальном мире может выполнять обнаружение мертвого кода.
Vality
50
64-битные процессоры @Vality могут адресовать 2 ^ 64 байта. Удачи в поиске всех 256 ^ (2 ^ 64) состояний!
Даниэль Вагнер
82
@DanielWagner Это не должно быть проблемой. Поиск 256^(2^64)состояний таков O(1), что обнаружение мертвого кода может быть сделано за полиномиальное время.
Aebabis
13
@Leliel, это был сарказм.
Пол Дрэйпер
44
@Vality: большинство современных компьютеров имеют диски, устройства ввода, сетевые коммуникации и т. Д. При любом полном анализе необходимо учитывать все такие устройства, в том числе буквально Интернет и все, что к нему подключено. Это не поддающаяся решению проблема.
Nat
77

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

Программа на 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!");
        }
    }
}

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

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

Таким образом, у вас есть это, детектор мертвого кода, который возвращает только «Есть мертвый код» или «Нет мертвого кода», может иногда давать неправильные ответы.

Joker_vD
источник
1
Если я правильно понял ваш аргумент, то технически другой вариант мог бы заключаться в том, что невозможно написать вполне, что является детектором мертвого кода, но в общем случае можно написать детектор мертвого кода. :-)
позднее
1
инкремент для ответа Годеляна.
Джаред Смит
@ Возможно, это был плохой выбор слов. На самом деле я не передаю исходный код детектора мертвых кодов самому себе, а исходный код программы, которая его использует. Конечно, в какой-то момент ему, вероятно, придется взглянуть на собственный код, но это его дело.
Joker_vD
65

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

Возьмите математическую задачу, которая, как полагают, верна для всех 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 итераций. На самом деле это была бы отличная оптимизация, так как я предсказываю, что вышеуказанная программа будет (или может) работать до тепловой смерти вселенной, а не печатать что-либо без оптимизации.

abligh
источник
4
Это лучший ответ на сегодняшний день +1
Жан
2
Что делает вещи особенно интересными, так это неоднозначность того, что стандарт С допускает или не разрешает, когда речь заходит о том, что циклы завершатся. Есть смысл в том, чтобы компилятор мог отложить медленные вычисления, результаты которых могут или не могут быть использованы до момента, когда их результаты будут фактически необходимы; в некоторых случаях эта оптимизация может быть полезной, даже если компилятор не может доказать, что вычисления завершены.
суперкат
2
2 ^ 2048 итераций? Даже Глубокая Мысль сдастся.
Питер Мортенсен
С большой вероятностью будет напечатано «Найдено значение SHA», даже если эта цель была случайной строкой из 64 шестнадцатеричных цифр. Если только не sha256возвращает байтовый массив, а байтовые массивы не сравниваются равными строкам на вашем языке.
user253751 23.10.15
4
Implementation of isGoldbachsConjectureTrueFor() is left as an exercise for the readerЭто заставило меня посмеяться.
Бизиклоп
34

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

Dim methodName As String

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

Application.Run(methodName)

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

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

Application.Run("Bar")

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

Резиновая утка
источник
2
В Java (или C #) это можно сделать с помощью отражения. C ++ вы, вероятно, могли бы выполнить некоторые неприятности, используя для этого макросы. Не было бы красиво, но C ++ редко бывает.
Даррел Хоффман
6
@DarrelHoffman - Макросы раскрываются до того, как код передается компилятору, поэтому макросы определенно не такие, как вы бы это делали. Указатели на функции - это то, как вы это сделаете. Я годами не использовал C ++, поэтому извините, если мои точные имена типов неверны, но вы можете просто сохранить карту строк для указателей на функции. Затем есть что-то, что принимает строку из пользовательского ввода, ищет эту строку на карте, а затем выполняет указанную функцию.
ArtOfWarfare
1
@ArtOfWarfare мы не говорим о том, как это можно сделать. Очевидно, что семантический анализ кода может быть сделан, чтобы найти эту ситуацию, суть в том, что компилятор этого не делает . Возможно, возможно, возможно, но это не так.
RubberDuck
3
@ArtOfWarfare: Если хочешь придираться, конечно. Я считаю, что препроцессор является частью компилятора, хотя я знаю, что технически это не так. В любом случае указатели на функции могут нарушать правило, согласно которому функции нигде не ссылаются напрямую - они, как указатель, а не прямой вызов, очень похожи на делегат в C #. C ++ в целом гораздо сложнее предсказать компилятору, так как он имеет так много способов сделать что-то косвенно. Даже такие простые задачи, как «найти все ссылки», не являются тривиальными, так как они могут скрываться в typedef, макросах и т. Д. Не удивительно, что не удается легко найти мертвый код.
Даррел Хоффман
1
Вам даже не нужны динамические вызовы методов для решения этой проблемы. Любой открытый метод может быть вызван еще не написанной функцией, которая будет зависеть от уже скомпилированного класса в Java или C # или любом другом скомпилированном языке с некоторым механизмом динамического связывания. Если компиляторы исключат их как «мертвый код», то мы не сможем упаковать предварительно скомпилированные библиотеки для распространения (NuGet, jars, колеса Python с двоичным компонентом).
jpmc26
12

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

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

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

dspfnder
источник
5
«Безусловный мертвый код может быть обнаружен и удален передовыми компиляторами». Это не похоже на вероятность. Потеря кода может зависеть от результата данной функции, и эта функция может решить произвольные проблемы. Таким образом, ваше утверждение утверждает, что продвинутые компиляторы могут решать произвольные задачи.
Темыр
6
@Taemyr Тогда не было бы известно, чтобы быть безусловно мертвым, не так ли?
JAB
1
@Taemyr Вы, кажется, неправильно поняли слово «безусловный». Если мертвость кода зависит от результата функции, то это условный мертвый код. «Условие» является результатом функции. Для того, чтобы быть «безусловным» она должна была бы не зависеть от какой - либо результата.
Kyeotic
12

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

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.

Алекс Лоп.
источник
1
Несмотря на то, что компилятор не знает точно, я думаю, что в духе вопроса также спросить, может ли компоновщик знать.
Кейси Кубалл
1
@Darthfett Это не ответственность компоновщика . Линкер не анализирует содержание скомпилированного кода. Линкер (вообще говоря) просто связывает методы и глобальные данные, его не волнует контент. Однако некоторые компиляторы имеют возможность объединить исходные файлы (например, ICC), а затем выполнить оптимизацию. В этом случае рассматривается случай в EDIT, но этот параметр будет влиять на время компиляции, особенно когда проект большой.
Алекс Лоп.
Этот ответ кажется мне вводящим в заблуждение; Вы приводите два примера, где это невозможно, потому что не вся информация доступна, но разве вы не должны сказать, что это невозможно, даже если информация есть?
Антон Голов
@AntonGolovIt не всегда так. Во многих случаях, когда информация есть, компиляторы могут обнаружить мертвый код и оптимизировать его.
Алекс Лоп.
@abforce просто блок кода. Это могло быть что-то еще. :)
Алекс Лоп.
4

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

cdonat
источник
4

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

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

Стив Санбег
источник
3

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

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

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.

biziclop
источник
2

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

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

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

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

Дрю Ноакс
источник
Я не знаю о Java и javascript, но .NET на самом деле имеет плагин для повышения резкости для такого типа обнаружения DI (называемый Agent Mulder). Конечно, он не сможет обнаружить файлы конфигурации, но он сможет обнаружить конфит в коде (что гораздо популярнее).
Галстуки
2

Взять на себя функцию

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

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

CiaPan
источник
7
Если вы можете анализировать вызывающие функции, то вы можете, да.
раньше
2
@abligh Но компилятор обычно не может анализировать весь вызывающий код. В любом случае, даже если бы это было возможно, для полного анализа может потребоваться просто симуляция всех возможных потоков управления, что почти всегда просто невозможно из-за необходимых ресурсов и времени. Таким образом, даже если теоретически существует доказательство того, что « Action2()никогда не будет вызвано», невозможно доказать это утверждение на практике - не может быть полностью решено компилятором . Разница в том, что «существует число X» против «мы можем записать число X в десятичном виде». Для некоторых X последнее никогда не произойдет, хотя первое верно.
CiaPan
Это плохой ответ. другие ответы доказывают, что это невозможно узнать actnumber==2. Этот ответ просто утверждает, что это трудно, даже не заявив о сложности.
MSalters
1

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

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

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

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

Лорен Печтель
источник
2
Последняя теорема Ферма была доказана в 1994 году. Поэтому правильная реализация вашего метода никогда не запустит FermatWasWrong. Я подозреваю, что ваша реализация запустит FermatWasWrong, потому что вы можете достичь предела точности с плавающей точкой.
Taemyr
@Темыр ага! Эта программа неправильно проверяет последнюю теорему Ферма; контрпример для того, что он проверяет, это N = 3, A = 65536, B = 65536 (что дает Test = 0)
user253751
@immibis Да, я пропустил, что он переполнится до того, как точность на поплавках станет проблемой.
Темыр
@immibis Обратите внимание на нижнюю часть моего поста: игнорируйте ошибки типа и переполнения. Я просто взял за основу то, что считал нерешенной проблемой - я знаю, что код не идеален. Это проблема, которая в любом случае не может быть грубой.
Лорен Печтел
-1

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

public boolean isEven(int i){

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

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

пользователь
источник
1
Хм, правда? Если я напишу это в C # + ReSharper, я получу пару советов. Следуя им, наконец, дает мне код return i%2==0;.
Томас Веллер
10
Ваш пример слишком прост, чтобы быть убедительным. Конкретный случай i % 2 == 0и i % 2 != 0даже не требует рассуждения о значении целого по модулю константы (что все еще легко сделать), он требует только общего исключения подвыражения и общего принципа (даже канонизации), который if (cond) foo; if (!cond) bar;можно упростить до if (cond) foo; else bar;. Конечно, «понимание семантики» является очень сложной проблемой, но этот пост не показывает, что это так, и не показывает, что решение этой сложной проблемы необходимо для обнаружения мертвого кода.
5
В вашем примере оптимизирующий компилятор определит общее подвыражение i % 2и выведет его во временную переменную. Затем он распознает, что эти два ifоператора являются взаимоисключающими и могут быть записаны как if(a==0)...else..., а затем обнаружит, что все возможные пути выполнения проходят через первые два returnоператора, и поэтому третий returnоператор является мертвым кодом. ( Хороший оптимизирующий компилятор еще более агрессивен: GCC превратил мой тестовый код в пару операций с битами).
Марк
1
Этот пример хорош для меня. Это представляет случай, когда компилятор не знает о некоторых фактических обстоятельствах. То же самое касается if (availableMemory()<0) then {dead code}.
Маленькая Санти
1
@LittleSanti: На самом деле, GCC обнаружит, что все , что вы там написали, является мертвым кодом! Это не просто {dead code}часть. GCC обнаруживает это, доказывая неизбежное переполнение целых чисел со знаком. Поэтому весь код этой дуги в графе выполнения является мертвым кодом. GCC может даже удалить условную ветвь, которая ведет к этой дуге.
MSalters