Анализ потока данных - Data-flow analysis

Разработка программного обеспечения
Активность ядер
Парадигмы и модели
Методологии и рамки
Вспомогательные дисциплины
Практики
Инструменты
Стандарты и свод знаний
Глоссарии
Контуры

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

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

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

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

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

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

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

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

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

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

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

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

за я ← 1 к N
инициализировать узел i
пока (наборы все еще меняются)
за я ← 1 к N
пересчитать наборы в узле i

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

Перспективный анализ

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

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

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

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

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

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

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

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

обработказа пределами штатастарый в штатеновый в штатесписок работ
b3{}{}{б, г}(b1, b2)
b1{б, г}{}{}(Би 2)
Би 2{б, г}{}{а, б}(b1)
b1{а, б, г}{}{}()

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

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

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

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

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

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

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

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

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

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

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

из(б) = 0за s в succ (б)    из(б) = out (б) или же в(s)в(б) = (из (б) и нет убийство(б)) или же gen (б)

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

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

Проблемы IFDS

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

Существует несколько реализаций анализа потоков данных на основе IDFS для популярных языков программирования, например в саже[11] и ВАЛА[12] фреймворки для анализа Java.

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

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

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

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

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

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

Рекомендации

  1. ^ Килдалл, Гэри Арлен (Май 1972 г.). Оптимизация глобального выражения во время компиляции (Кандидатская диссертация). Сиэтл, Вашингтон, США: Вашингтонский университет, Группа компьютерных наук. Диссертация № 20506, Технический отчет № 72-06-02.
  2. ^ Килдалл, Гэри Арлен (1973-10-01). «Единый подход к глобальной оптимизации программ» (PDF). Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования (POPL). POPL '73. Бостон, Массачусетс, США: 194–206. Дои:10.1145/512927.512945. HDL:10945/42162. S2CID  10219496. В архиве (PDF) из оригинала от 29.06.2017. Получено 2006-11-20. ([1] )
  3. ^ Рютинг, Оливер; Knoop, Jens; Штеффен, Бернхард (2003-07-31) [1999]. «Оптимизация: обнаружение равенства переменных, сочетание эффективности с точностью». В Кортеси, Агостино; Filé, Gilberto (ред.). Статический анализ: 6-й Международный симпозиум, SAS'99, Венеция, Италия, 22–24 сентября 1999 г., Труды. Конспект лекций по информатике. 1694 (иллюстрированный ред.). Springer. С. 232–247 [233]. ISBN  9783540664598. ISSN  0302-9743.
  4. ^ Хайтт, Роберт; Юбэнкс, Гордон; Роландер, Томас «Том» Алан; Законы, Дэвид; Michel, Howard E .; Халла, Брайан; Уортон, Джон Харрисон; Берг, Брайан; Су, Вейлиан; Килдалл, Скотт; Кампе, Билл (25 апреля 2014 г.). Законы, Дэвид (ред.). «Наследие Гэри Килдалла: посвящение CP / M IEEE» (PDF) (транскрипция видео). Пасифик Гроув, Калифорния, США: Музей истории компьютеров. Номер ссылки CHM: X7170.2014. Получено 2020-01-19. […] Юбэнкс: […] Гэри […] Был изобретателем, он был изобретателем, он делал разные вещи. Его доктор философии. Тезис доказал, что анализ глобального потока сходится. […] Это фундаментальная идея в информатике. […] Однажды я проходил […] летний курс у парня по имени Дхамдхере […] Они говорили об оптимизации около недели, а затем подняли слайд и сказали: «Метод Килдалла», это настоящая история. […] Это то, о чем никто никогда не думает. […] [2][3] (33 страницы)
  5. ^ Купер, Кейт Д.; Харви, Тимоти Дж .; Кеннеди, Кен (2004-03-26) [ноябрь 2002]. «Повторение итеративного анализа потока данных» (PDF). PLDI 2003. ACM. TR04-432. Получено 2017-07-01.[постоянная мертвая ссылка ]
  6. ^ Монен, Маркус (2002). Подход к анализу потока данных без графов. Конспект лекций по информатике. 2304. С. 185–213. Дои:10.1007/3-540-45937-5_6. ISBN  978-3-540-43369-9.
  7. ^ Куанг, Хунъюй; Мэдер, Патрик; Ху, Хао; Габи, Ахраф; Хуанг, LiGuo; Люй, Цзянь; Египед, Александр (01.11.2015). «Могут ли зависимости данных метода поддерживать оценку прослеживаемости между требованиями и исходным кодом?». Журнал программного обеспечения: эволюция и процесс. 27 (11): 838–866. Дои:10.1002 / smr.1736. ISSN  2047-7481. S2CID  39846438.
  8. ^ а б Представители, Томас; Хорвиц, Сьюзен; Сагив, Мули (1995). «Точный межпроцедурный анализ потока данных через доступность графа». Материалы 22-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '95. Нью-Йорк, Нью-Йорк, США: ACM Press: 1, 49–61. Дои:10.1145/199448.199462. ISBN  0-89791692-1. S2CID  5955667.
  9. ^ а б Knoop, Йенс; Штеффен, Бернхард; Фоллмер, Юрген (1996-05-01). «Параллелизм бесплатно: эффективный и оптимальный анализ битового вектора для параллельных программ». Транзакции ACM по языкам и системам программирования. 18 (3): 268–299. Дои:10.1145/229542.229545. ISSN  0164-0925. S2CID  14123780.
  10. ^ Naeem, Nomair A .; Лхотак, Ондржей; Родригес, Джонатан (2010), Практические расширения алгоритма IFDS, Конспект лекций по информатике, 6011, Берлин / Гейдельберг, Германия: Springer Verlag, стр. 124–144, Дои:10.1007/978-3-642-11970-5_8, ISBN  978-3-64211969-9
  11. ^ Бодден, Эрик (2012). «Межпроцедурный анализ потока данных с использованием IFDS / IDE и сажи». Материалы международного семинара ACM SIGPLAN по современному уровню анализа программ на Java - SOAP '12. Нью-Йорк, Нью-Йорк, США: ACM Press: 3–8. Дои:10.1145/2259051.2259052. ISBN  978-1-45031490-9. S2CID  3020481.
  12. ^ Рапопорт, Марианна; Лхотак, Ондржей; Совет, Фрэнк (2015). «Точный анализ потока данных при наличии коррелированных вызовов методов». Статический анализ. Конспект лекций по информатике. 9291. Берлин / Гейдельберг, Германия: Springer Verlag. С. 54–71. Дои:10.1007/978-3-662-48288-9_4. ISBN  978-3-66248287-2. Отсутствует или пусто | название = (помощь)

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