Методы статического анализа
Статический анализ алиасов (alias analysis) [11] необходим в языках, в которых несколько имён могут быть использованы для доступа к одной и той же области памяти. Например, некоторый элемент массива a может быть адресован в программе как a[0] (каноническое имя элемента массива), как a[j] или вообще как b[-4]. В результате анализа алиасов каждому оператору, выполняющему косвенную запись в память или косвенное чтение из памяти, ставится в соответствие множество имён переменных, которые могут затрагиваться данной операцией.
Если язык допускает алиасы, проведение в той или иной мере анализа указателей необходимо для корректного анализа потоков данных и для преобразования программ. В случае доступа к элементам массивов и полям структур мы можем в простейшем случае предполагать, что считывается или модифицируется сразу весь массив или вся структура. Для указателей или ссылок в простейшем случае ("консервативный" анализ) мы можем исходить из предположения о том, что косвенное чтение из памяти затрагивает все локальные и глобальные переменные, а косвенная запись в память может все их модифицировать. Такая схема слишком груба и в действительности блокирует глубокую трансформацию практически любой программы.
Известно, что общая задача точного анализа указателей как минимум NP-трудна. В настоящее время существуют методы, работающие за полиномиальное время, для указателей на локальные переменные в случае нерекурсивных функций.
Анализ указателей не может быть непосредственно использован для запутывания или распутывания программы, но он является ключевым для точного анализа свойств программы.
Статическое устранение мёртвого кода (dead-code elimination) [19], разд. 18.10. имеет целью выявить в программе код, который выполняется, но не оказывает влияние на результат работы программы.
Статическая минимизация количества переменных (variable minimization) [19], разд. 16.3. имеет целью уменьшить количество используемых в функции локальных переменных за счёт объединения переменных, времена жизни значений в которых не пересекаются, в одну переменную.
Стандартная техника, которая используется для минимизации количества переменных, состоит в построении графа перекрытия переменных с помощью итерационного решения уравнения потока данных и последующей раскраске вершин этого графа в минимальное или близкое к минимальному количество цветов.
Статическое продвижение констант и копий (constant and copy propagation) [19], разд. 12.5, 12.6. заключается в продвижении константных выражений как можно дальше по тексту функции. Если выражение использует только значения переменных, которые в данной точке программы заведомо содержат одно известное при анализе программы значение, такое выражение может быть вычислено на этапе анализа программы. Если в выражении используется переменная, которая в данной точке программы заведомо является копией какой-то другой переменной, в выражение может быть подставлена исходная переменная.
Статический анализ доменов (domain analysis) является расширением алгоритма продвижения констант. Он позволяет определить множество значений, которые может принимать данная переменная в данной точке программы, если это множество не велико.
Статический слайсинг (slicing) [21] - это построение "сокращённой" программы, из которой удалён весь код, не влияющий на вычисление заданной переменной в заданной точке (обратный слайс), но при этом программа остаётся синтаксически и семантически корректной и может быть выполнена. Кроме описанного выше обратного слайсинга разработаны алгоритмы прямого слайсинга. Прямой слайсинг оставляет в программе только те операторы, которые зависят от значения переменной, вычисленного в данной точке программы. Методы слайсинга могут быть полезны при разделении "переплетённых" вычислений, когда одновременно вычисляются две независимые друг от друга величины. Например, в одном цикле может вычисляться скалярное произведение двух векторов, а также минимальный и максимальный элемент каждого вектора, и такие циклы могут быть расщеплены с помощью построения слайсов.
