Как распознать переменные, которые не влияют на вывод программы?

Question

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

global var_1
global var_2

start program hello(var_3, var_4)
    if (var_2 < 0) then
        save-log-to-disk (var_1, var_3, var_4)
    end-if
    return ("Hello " + var_3 + ", my name is " + var_1)
end program

Здесь только var_1 и var_3 имеют какое-либо влияние на вывод, тогда как var_2 и var_4 используются только для побочных эффектов. Имеют ли переменные типа var_1 и var_3 имя в теории потока данных / теории компилятора? Какие методы статического анализа потоков данных можно использовать для их обнаружения?

Ссылки на академическую литературу по этому вопросу будут особенно оценены.

Answer 1

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

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

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

Если вы сосредоточите свое внимание только на вычислениях, включенных в потоки данных, и отобразите их, вы получите то, что обычно называется "программным фрагментом" . Есть (очень мало) коммерческих инструментов, которые могут показать это вам. Grammatech имеет хорошую репутацию здесь для C и C++.

Существуют стандартные алгоритмы компилятора для построения таких графов потоков данных; посмотрите любую грамотную книгу компиляторов.

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

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

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

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

Вот начальная ссылка: http://en.wikipedia.org/wiki/Data-flow_analysis Любая из книг на этой странице будет довольно хорошей. У меня есть книга Мучника, и она мне очень нравится. Смотрите также эту страницу: ( http://en.wikipedia.org/wiki/Program_slicing)

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

Answer 2

Задача, которую вы указали, в общем, неразрешима, даже для следующего очень узкого особого случая: для единственной подпрограммы P(x), где x - это параметр типа integer. Является ли выход P (x) независимым от значения x, т. Е. P(0) = P(1) = P(2) = ...?

Мы можем свести следующую все еще неразрешимую версию проблемы остановки к приведенному выше вопросу: Учитывая машину Тьюринга M(), программа никогда не останавливается на пустом входе?

Я предполагаю, что мы используем (полный по Тьюрингу) язык, на котором мы можем построить "симулятор машины Тьюринга":

Учитывая программу M(), создайте эту подпрограмму:

P(x):
    if x == 0:
       return 0
    Run M() for x steps
    if M() has terminated then:
        return 1
    else:
        return 0

Сейчас:

P(0) = P(1) = P(2) = ... 
=> 
M() does not terminate.

M() does terminate 
=> P(x) = 1 for a sufficiently large x   
=> P(x) != P(0) = 0

Таким образом, компилятору очень трудно решить, действительно ли переменная не влияет на возвращаемое значение подпрограммы; в вашем примере, "подпрограмма побочного эффекта" может манипулировать одним из его значений (или даже бесконечно зацикливаться, что определенно изменит возвращаемое значение подпрограммы;-) Конечно, перерасходы все еще возможны. Например, можно сделать вывод, что переменная не влияет на возвращаемое значение, если оно вообще не отображается в теле процедуры. Вы также можете увидеть некоторые классические анализы компилятора (такие как упрощение выражений, распространение констант) с побочным эффектом устранения появления таких избыточных переменных.

Answer 3

Я использую следующий алгоритм: переменная используется, если она является параметром или встречается где-либо в выражении, за исключением LHS присваивания. Сначала посчитайте количество использований всех переменных. Удалите неиспользуемые переменные и присваивания неиспользованным переменным. Повторяйте, пока никакие переменные не будут удалены.

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

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

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

Оптимизация компилятора IMHO - это почти всегда эвристика, производительность которой важнее, чем эффективность достижения теоретической цели (например, удаление неиспользуемых переменных). Простые сокращения полезны не только потому, что они быстрые и простые в написании, но и потому, что программист, использующий язык, который понимает основы работы компилятора, может использовать эти знания, чтобы помочь компилятору. Наиболее известным примером этого является, вероятно, рефакторинг рекурсивных функций для помещения рекурсии в хвостовую позицию: бессмысленное упражнение, если программист не знает, что компилятор может выполнить оптимизацию хвостовой рекурсии.