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

Метод анализа переменных в программном обеспечении

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

Простой способ выполнить анализ потока данных программ — это составить уравнения потока данных для каждого узла графа потока управления и решить их, многократно вычисляя выход из входа локально в каждом узле, пока вся система не стабилизируется, т. е. не достигнет фиксированной точки .Этот общий подход, также известный как метод Килдалла , был разработан Гэри Килдаллом во время преподавания в Военно-морской аспирантуре . ^{[1] [2] [3] [4]}

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

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

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

${\displaystyle out_{b}=trans_{b}(in_{b})}$

${\displaystyle in_{b}=join_{p\in pred_{b}}(out_{p})}$

В этом, есть передаточная функция блока . Она работает над входным состоянием , давая выходное состояние . Операция соединения объединяет выходные состояния предшественников , давая входное состояние . ${\displaystyle trans_{b}}$ ${\displaystyle b}$ ${\displaystyle in_{b}}$ ${\displaystyle out_{b}}$ ${\displaystyle join}$ ${\displaystyle p\in pred_{b}}$ ${\displaystyle b}$ ${\displaystyle b}$

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

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

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

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

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

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

для i ← 1 до N

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

пока ( наборы все еще меняются )

для i ← 1 до N

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

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

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

Область значений должна быть частичным порядком с конечной высотой (т. е. не должно быть бесконечных восходящих цепей < < ...). Комбинация функции переноса и операции соединения должна быть монотонной относительно этого частичного порядка. Монотонность гарантирует, что на каждой итерации значение либо останется прежним, либо будет расти, в то время как конечная высота гарантирует, что оно не может расти бесконечно. Таким образом, в конечном итоге мы достигнем ситуации, когда T(x) = x для всех x, что является фиксированной точкой. ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$

Подход к списку работ

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

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

Заказ

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

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

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

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

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

Примеры

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

Прямой анализ

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

 если б == 4 тогда а = 5; еще  а = 3; эндиф  если а < 4 то ...

Достижение определения переменной aв строке 7 представляет собой набор назначений a = 5в строке 2 и a = 3в строке 4.

Анализ в обратном порядке

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

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

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

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

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

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

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

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

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

Некоторые современные компиляторы используют статическую форму с одним присваиванием в качестве метода анализа зависимостей переменных. ^[6]

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

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

Специальные классы задач

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

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

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

Например, в анализе живых переменных операция join — это union. Kill set — это набор переменных, которые записываются в блок, тогда как gen set — это набор переменных, которые считываются без предварительной записи. Уравнения потока данных становятся

${\displaystyle out_{b}=\bigcup _{s\in succ_{b}}in_{s}}$

${\displaystyle in_{b}=(out_{b}-kill_{b})\cup gen_{b}}$

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

out( b ) = 0 для  s  in succ( b ) вых( б ) = вых( б ) или вх( с )in( b ) = (out( b ) и не kill( b )) или gen( b )

Задачи потока данных, которые имеют наборы значений потока данных, которые могут быть представлены в виде битовых векторов, называются задачами битовых векторов , задачами уничтожения генов или локально разделимыми задачами . ^[9] Такие задачи имеют общие решения за полиномиальное время. ^[10]

В дополнение к проблемам достижения определений и живых переменных, упомянутым выше, следующие проблемы являются примерами проблем битовых векторов: ^[10]

• Доступные выражения
• Очень занятые выражения
• Цепочки определения использования

Проблемы IFDS

Межпроцедурные, конечные, распределительные, подмножественные проблемы или проблемы IFDS представляют собой еще один класс проблем с универсальным решением за полиномиальное время. ^{[9] [11]} Решения этих проблем обеспечивают контекстно-зависимый и чувствительный к потоку анализ потоков данных.

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

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

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

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

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

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

• Достижение определений
• Анализ жизнеспособности
• Анализ определенного назначения
• Доступное выражение
• Постоянное распространение

Смотрите также

• Абстрактная интерпретация
• Анализ потока управления
• XLT86

Ссылки

1. Килдалл, Гэри Арлен (май 1972). Глобальная оптимизация выражений во время компиляции (диссертация на степень доктора философии). Сиэтл, Вашингтон, США: Вашингтонский университет , Computer Science Group. Диссертация № 20506, Технический отчет № 72-06-02.
2. Kildall, Gary Arlen (1973-10-01). "Унифицированный подход к глобальной оптимизации программ" (PDF) . Труды 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования (POPL) . POPL '73. Бостон, Массачусетс, США: 194–206. doi :10.1145/512927.512945. hdl :10945/42162. S2CID  10219496. Архивировано (PDF) из оригинала 29-06-2017 . Получено 20-11-2006 .([1])
3. Рютинг, Оливер; Кноп, Йенс; Штеффен, Бернхард (2003-07-31) [1999]. "Оптимизация: обнаружение равенств переменных, сочетание эффективности с точностью". В Cortesi, Агостино; Филе, Жилберто (ред.). Статический анализ: 6-й международный симпозиум, SAS'99, Венеция, Италия, 22–24 сентября 1999 г., Труды . Заметки лекций по информатике. Том 1694 (иллюстрированное издание). Springer. стр. 232–247 [233]. ISBN 9783540664598. ISSN  0302-9743.
4. Хьюитт, Роберт; Юбэнкс, Гордон ; Роландер, Томас «Том» Алан ; Лоус, Дэвид; Мишель, Говард Э.; Халла, Брайан; Уортон, Джон Харрисон ; Берг, Брайан; Су, Вейлиан; Килдалл, Скотт ; Кампе, Билл (25.04.2014). Лоус, Дэвид (ред.). «Наследие Гэри Килдалла: посвящение CP/M IEEE Milestone» (PDF) (видеотранскрипция). Пасифик-Гроув, Калифорния, США: Музей компьютерной истории . Номер ссылки CHM: X7170.2014 . Получено 19.01.2020 . […] Юбэнкс : […] Гэри […] был изобретателем, он был изобретательным, он делал вещи. Его докторская диссертация доказала, что глобальный анализ потока сходится. […] Это фундаментальная идея в компьютерной науке. […] Однажды я прошел […] летний курс у парня по имени Дхамдхере […] они говорили об оптимизации где-то неделю, а потом вывесили слайд и сказали: «Метод Килдалла», вот настоящая история. […] это то, о чем никто никогда не думает. […][2][3] (33 страницы)
5. Купер, Кит Д .; Харви, Тимоти Дж.; Кеннеди, Кен (2004-03-26) [Ноябрь 2002]. "Итеративный анализ потока данных, пересмотр" (PDF) . PLDI 2003 . ACM . TR04-432 . Получено 2017-07-01 .^{[ постоянная мертвая ссылка ]}
6. "Статическое одиночное присваивание (с соответствующими примерами)". GeeksforGeeks . 2021-10-02 . Получено 2023-08-16 .
7. Монен, Маркус (2002). «Подход без графов к анализу потоков данных». Построение компилятора . Конспект лекций по информатике. Том 2304. С. 185–213. doi :10.1007/3-540-45937-5_6. ISBN 978-3-540-43369-9.
8. Куанг, Хонгюй; Мэдер, Патрик; Ху, Хао; Габи, Ашраф; Хуан, Лигуо; Лю, Цзянь; Эгиед, Александр (01.11.2015). «Могут ли зависимости данных методов поддерживать оценку прослеживаемости между требованиями и исходным кодом?». Журнал программного обеспечения: эволюция и процесс . 27 (11): 838–866. doi :10.1002/smr.1736. ISSN  2047-7481. S2CID  39846438.
9. Reps, Thomas; Horwitz, Susan; Sagiv, Mooly (1995). "Точный межпроцедурный анализ потока данных с помощью графовой достижимости". Труды 22-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '95 . Нью-Йорк, Нью-Йорк, США: ACM Press . С. 1, 49–61. doi :10.1145/199448.199462. ISBN 0-89791692-1. S2CID  5955667.
10. Knoop, Jens; Steffen, Bernhard ; Vollmer, Jürgen (1996-05-01). "Свободный параллелизм: эффективный и оптимальный анализ битовых векторов для параллельных программ". ACM Transactions on Programming Languages ​​and Systems . 18 (3): 268–299. doi : 10.1145/229542.229545 . ISSN  0164-0925. S2CID  14123780.
11. Naeem, Nomair A.; Lhoták, Ondřej; Rodriguez, Jonathan (2010), «Практические расширения алгоритма IFDS», Compiler Construction , Lecture Notes in Computer Science, т. 6011, Берлин / Гейдельберг, Германия: Springer Verlag , стр. 124–144, doi : 10.1007/978-3-642-11970-5_8 , ISBN 978-3-64211969-9
12. Бодден, Эрик (2012). «Анализ межпроцедурных потоков данных с IFDS/IDE и Soot». Труды Международного семинара ACM SIGPLAN по современному уровню анализа программ Java . Нью-Йорк, Нью-Йорк, США: ACM Press . С. 3–8. doi :10.1145/2259051.2259052. ISBN 978-1-45031490-9. S2CID  3020481.
13. Рапопорт, Марианна; Лхотак, Ондржей; Тип, Франк (2015). Точный анализ потока данных при наличии коррелированных вызовов методов . Международный симпозиум по статическому анализу. Конспект лекций по информатике. Том 9291. Берлин / Гейдельберг, Германия: Springer Verlag . С. 54–71. doi :10.1007/978-3-662-48288-9_4. ISBN 978-3-66248287-2.

Дальнейшее чтение

• Купер, Кит Д. ; Торцон, Линда (2003) [2002-01-01]. Разработка компилятора . Морган Кауфманн . ISBN 978-1-55860-698-2.
• Muchnick, Steven Stanley (1997). Advanced Compiler Design and Implementation . Издательство Morgan Kaufmann . ISBN 978-1-55860-320-2.
• Хехт, Мэтью С. (1977-05-03). Анализ потока компьютерных программ . Серия «Языки программирования». Том 5. Elsevier North-Holland Inc. ISBN 978-0-44400210-5.
• Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri (2009). Анализ потока данных: теория и практика. CRC Press ( Taylor and Francis Group ).
• Нильсон, Флемминг; Нильсон, Ханне Риис ; Ханкин, Крис (2005). Принципы анализа программ . Springer Science+Business Media .