Анализ потока данных

редактировать

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

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

Содержание

1 Основные принципы
2 Итерационный алгоритм
- 2.1 Конвергенция
- 2.2 Подход к списку работ
- 2.3 Порядок имеет значение
- 2.4 Инициализация
3 Примеры
- 3.1 Прогрессивный анализ
- 3.2 Обратный анализ
4 Другие подходы
5 Специальные классы проблем
- 5.1 Проблемы с битовыми векторами
- 5.2 Проблемы IFDS
6 Чувствительность
7 Список анализов потока данных
8 См. Также
9 Ссылки
10 Дополнительная литература

Основные принципы

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

Для каждого блока b:

outb = transb (inb) {\ displaystyle out_ {b} = trans_ {b} (in_ {b})}

out_b = trans_b (in_b)

inb = joinp ∈ predb (outp) {\ displaystyle in_ {b} = join_ {p \ in pred_ {b}} (out_ {p})}

in_b = join_ {p \ in pred_b} (out_p)

Здесь $transb {\ displaystyle trans_ { b}}$ $trans_b$ - передаточная функция блока $b {\ displaystyle b}$ $b$ . Он работает с состоянием входа $i n b {\ displaystyle in_ {b}}$ $in_b$ , давая состояние выхода $o u t b {\ displaystyle out_ {b}}$ $out_b$ . операция соединения $join {\ displaystyle join}$ $join$ объединяет состояния выхода предшественников $p ∈ predb {\ displaystyle p \ in pred_ {b}}$ $p \ in pred_b$ из $b {\ displaystyle b}$ $b$ , что дает состояние входа $b {\ displaystyle b}$ $b$ .

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

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

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

Итерационный алгоритм

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

Базовым алгоритмом для решения уравнений потока данных является итерационный алгоритм циклического перебора :

для i ← от 1 до N

инициализировать узел i

while (наборы все еще меняется)

для i ← от 1 до N

повторно вычислить наборы в узле i

Конвергенция

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

Область значений должна быть частичным порядком с конечной высотой (т. Е. Не существует бесконечных восходящих цепочек $x 1 {\ displaystyle x_ {1} }$ $x_{1}$ < $x 2 {\ displaystyle x_ {2}}$ $x_{2}$ <...). The combination of the transfer function and the join operation should be монотонный по отношению к этому частичному порядку. Монотонность гарантирует, что на каждой итерации значение либо останется прежним, либо будет увеличиваться, а конечная высота гарантирует что он не может расти бесконечно. Таким образом, мы в конечном итоге достигнем ситуации, когда T (x) = x для всех x, что является фиксированной точкой.

Подход с использованием рабочего списка

Легко улучшить в приведенном выше алгоритме, заметив, что внутреннее состояние блока не изменится, если исходное состояние его предшественников не изменится. Поэтому мы вводим рабочий список : список блоков, которые все еще необходимо обработать. Каждый раз, когда состояние выхода блока изменяется, мы добавляем его преемников в рабочий список. На каждой итерации блок удаляется из рабочего списка. Его исходное состояние вычисляется. Если исходное состояние изменилось, успех блока Цессоры добавлены в список работ. Для эффективности блок не должен быть в рабочем списке более одного раза.

Алгоритм запускается с помещения блоков генерации информации в рабочий список. Он завершается, когда рабочий список пуст.

Порядок имеет значение

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

Далее обсуждаются несколько итерационных порядков для решения уравнений потока данных (связанное с порядком итерации CFG понятие - это обход дерева дерево ).

Случайный порядок - Этот порядок итераций не знает, решают ли уравнения потока данных прямую или обратную задачу потока данных. Следовательно, производительность относительно низка по сравнению со специализированными порядками итераций.
Postorder - это типичный порядок итераций для проблем с обратным потоком данных. В итерации постпорядка узел посещается после посещения всех его последующих узлов. Как правило, итерация после упорядочения реализуется с помощью стратегии в глубину .
Обратный постордер - это типичный порядок итераций для задач прямого потока данных. В итерации с обратным порядком узел посещается до того, как был посещен какой-либо из его последующих узлов, за исключением случаев, когда последователь достигается задним краем. (Обратите внимание, что обратный поступорядочение - это не то же самое, что предзаказ.)

Инициализация

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

Примеры

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

Прогрессивный анализ

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

1, если b == 4, то 2 a = 5; 3 иначе 4 a = 3; 5 endif 6 7 if a < 4 then 8...

Достигающее определение переменной aв строке 7 - это набор присваиваний a = 5в строке 2 и a = 3в строке 4.

Обратный анализ

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

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

Исходный код:

b1: a = 3; b = 5; d = 4; х = 100; если a>b, то b2: c = a + b; d = 2; b3: endif c = 4; вернуть b * d + c;

Обратный анализ:

// in: {} b1: a = 3; b = 5; d = 4; х = 100; // x никогда не используется позже, поэтому не в исходном наборе {a, b, d} if a>b then // out: {a, b, d} // объединение всех (входящих) наследников b1 =>b2: {a, b} и b3: {b, d} // in: {a, b} b2: c = a + b; d = 2; // выход: {b, d} // вход: {b, d} b3: endif c = 4; вернуть b * d + c; // out: {}

Состояние входа b3 содержит только b и d, поскольку c было записано. Выходное состояние b1 - это объединение внутренних состояний b2 и b3. Определение c в b2 может быть удалено, поскольку c не является живым сразу после оператора.

Решение уравнений потока данных начинается с инициализации всех входящих и исходящих состояний пустым набором. Список работ инициализируется путем вставки точки выхода (b3) в список работ (типично для обратного потока). Его вычисленное состояние in-state отличается от предыдущего, поэтому вставляются его предшественники b1 и b2, и процесс продолжается. Прогресс суммирован в таблице ниже.

обработка	выходное состояние	старое текущее состояние	новое внутреннее состояние	рабочий список
b3	{}	{}	{b, d}	(b1, b2)
b1	{b, d}	{}	{}	(b2)
b2	{b, d}	{}	{a, b}	(b1)
b1	{a, b, d}	{}	{}	()

Обратите внимание, что b1 был введен в список перед b2, что привело к принудительной обработке b1 дважды (b1 был повторно введен как предшественник b2). Вставка b2 перед b1 позволила бы завершить выполнение раньше.

Инициализация с пустым набором - оптимистичная инициализация: все переменные начинаются как мертвые. Обратите внимание, что исходящие состояния не могут сокращаться от одной итерации к следующей, хотя исходное состояние может быть меньше, чем внутреннее состояние. Это видно из того факта, что после первой итерации выходное состояние может измениться только путем изменения входящего состояния. Поскольку in-state начинается как пустой набор, он может только увеличиваться в следующих итерациях.

Другие подходы

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

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

Особые классы проблем

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

Проблемы с битовым вектором

Приведенные выше примеры представляют собой проблемы, в которых значение потока данных является набором, например набором достижения определений (использование бита для позиции определения в программе), или набор текущих переменных. Эти наборы могут быть эффективно представлены как битовые векторы, в которых каждый бит представляет принадлежность набора к одному конкретному элементу. Используя это представление, функции соединения и передачи могут быть реализованы как поразрядные логические операции. Операция соединения обычно представляет собой объединение или пересечение, реализуемое поразрядными логическими операциями или и l ogical и. Передаточная функция для каждого блока может быть разложена на так называемые наборы генерации и уничтожения.

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

outb = ⋃ s ∈ succbins {\ displaystyle out_ {b} = \ bigcup _ {s \ in succ_ {b}} in_ {s}}

out_b = \ bigcup_ {s \ in succ_b} in_s

inb = (outb - killb) ∪ genb {\ displaystyle in_ {b} = (out_ {b} -kill_ {b}) \ cup gen_ {b}}

in_b = (out_b - kill_b) \ чашка gen_b

В логических операциях это читается как

out (b) = 0 для s insucc (b) out (b) = out (b) или in (s) in (b) = (out (b) and not kill (b)) или gen (b)

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

В дополнение к упомянутым выше проблемам с определениями и текущими переменными, следующие проблемы являются примерами проблем с битовым вектором:

Задачи IFDS

Межпроцедурные, конечные, распределительные задачи, задачи подмножества или Задачи IFDS - это еще один класс проблем с общим решением за полиномиальное время. Решения этих проблем обеспечивают анализ потоков данных с учетом контекста и потока.

Существует несколько реализаций анализа потоков данных на основе IDFS для популярных языков программирования, например в фреймворках Soot и WALA для анализа Java.

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

Чувствительность

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

A чувствительный к потоку анализ учитывает порядок операторов в программе. Например, анализ псевдонимов указателя, нечувствительный к потоку, может определять «переменные x и y могут относиться к одному и тому же местоположению», в то время как анализ с учетом потока может определять «после утверждения 20 переменные x и y могут относиться к одному и тому же местоположению».
A чувствительный к пути анализ вычисляет различные фрагменты аналитической информации в зависимости от предикатов в инструкциях условного перехода. Например, если ветвь содержит условие x>0, то на пути падения анализ будет предполагать, что x<=0, а в целевой ветви - что действительно x>0.
A контекстно-зависимый анализ - это межпроцедурный анализ, который учитывает контекст вызова при анализе цели вызова функции. В частности, используя контекстную информацию, можно вернуться к исходному сайту вызова, тогда как без этой информации информация анализа должна распространяться обратно на все возможные сайты вызова, потенциально теряя точность.

Список анализов потока данных

См. Также

Ссылки

Дополнительная литература

Купер, Кейт Д. ; Торчон, Линда (2003) [2002-01-01]. Разработка компилятора. Морган Кауфманн. ISBN 978-1-55860-698-2.
Мучник, Стивен Стэнли (1997). Расширенный дизайн и реализация компилятора. Издательство Морган Кауфманн. ISBN 978-1-55860-320-2.
Хехт, Мэтью С. (1977-05-03). Анализ потока компьютерных программ. Серия языков программирования. 5. Elsevier North-Holland Inc. ISBN 978-0-44400210-5.
Khedker, Uday P.; Саньял, Амитабха; Каркаре, Багешри (2009). Анализ потока данных: теория и практика. CRC Press (Taylor and Francis Group ).
Nielson, Flemming; Nielson, Hanne Riis; Hankin, Chris (2005). Принципы анализа программ. Springer Science + Business Media.