 | Этот раздел требует дополнительных ссылок для проверки . ( Февраль 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
| Разработка программного обеспечения |
|---|
Анализ потока данных - это метод сбора информации о возможном наборе значений, вычисленных в различных точках компьютерной программы . Граф потока управления программы (CFG) используется для определения тех частей программы, в которые может распространяться конкретное значение, присвоенное переменной. Собранная информация часто используется компиляторами при оптимизации программы. Канонический пример анализа потока данных - определение определений .
Простой способ выполнить анализ потока данных программ состоит в том, чтобы установить уравнения потока данных для каждого узла графа потока управления и решить их, многократно вычисляя выходные данные от входа локально в каждом узле до тех пор, пока вся система не стабилизируется, т. Е. он достигает фиксированной точки .Этот общий подход, также известный как метод Килдалла , был разработан Гэри Килдаллом во время обучения в Военно-морской аспирантуре . [1] [2] [3] [4]
Основные принципы [ править ]
Анализ потока данных - это процесс сбора информации о том, как используются переменные, определенные в программе. Он пытается получить конкретную информацию на каждом этапе процедуры. Обычно достаточно получить эту информацию на границах базовых блоков , поскольку отсюда легко вычислить информацию в точках базового блока. В анализе прямого потока состояние выхода блока является функцией входного состояния блока. Эта функция представляет собой композицию эффектов операторов в блоке. Состояние входа блока является функцией состояний выхода его предшественников. Это дает набор уравнений потока данных:
Для каждого блока b:
В этом, является передаточной функцией блока . Он работает с входным состоянием , давая выходное состояние . Присоединиться к операции комбинаты экзит Штаты предшественников из , дающих состояния входа в .
После решения этого набора уравнений состояния входа и / или выхода блоков можно использовать для получения свойств программы на границах блоков. Передаточная функция каждого оператора в отдельности может применяться для получения информации в точке внутри базового блока.
Каждый конкретный тип анализа потока данных имеет свою особую передаточную функцию и операцию соединения. Некоторые проблемы с потоком данных требуют анализа обратного потока. Это следует тому же плану, за исключением того, что передаточная функция применяется к состоянию выхода, дающему состояние входа, а операция соединения работает с состояниями входа преемников, чтобы получить состояние выхода.
Точка входа (в прямом потоке) играет важную роль: поскольку у нее нет предшественников, ее состояние входа четко определяется в начале анализа. Например, набор локальных переменных с известными значениями пуст. Если граф потока управления не содержит циклов (в процедуре не было явных или неявных циклов ), решение уравнений несложно. Затем можно топологически отсортировать граф потока управления ; выполняются в таком порядке, состояния входа могут быть вычислены в начале каждого блока, поскольку все предшественники этого блока уже были обработаны, поэтому их состояния выхода доступны. Если граф потока управления действительно содержит циклы, требуется более продвинутый алгоритм.
Итерационный алгоритм [ править ]
Наиболее распространенный способ решения уравнений потока данных - использование итеративного алгоритма. Он начинается с приблизительного определения состояния каждого блока. Затем вычисляются исходящие состояния, применяя передаточные функции к входящим состояниям. Из них внутренние состояния обновляются путем применения операций соединения. Последние два шага повторяются до тех пор, пока мы не достигнем так называемой фиксированной точки : ситуации, в которой внутренние состояния (и, как следствие, исходящие состояния) не меняются.
Базовым алгоритмом решения уравнений потока данных является циклический итерационный алгоритм :
- для i ← от 1 до N
- инициализировать узел i
- в то время как ( наборы все еще меняются )
- для i ← от 1 до N
- пересчитать наборы в узле i
- для i ← от 1 до N
Конвергенция [ править ]
Чтобы можно было использовать итеративный подход, он должен фактически достичь фиксированной точки. Это может быть гарантировано путем наложения ограничений на комбинацию области значений состояний, передаточных функций и операции соединения.
Домен значения должен быть частичным порядком с конечной высотой (т.е. нет бесконечных возрастающих цепочек < <...). Комбинация передаточной функции и операции соединения должна быть монотонной по отношению к этому частичному порядку. Монотонность гарантирует, что на каждой итерации значение либо останется прежним, либо будет расти, а конечная высота гарантирует, что оно не может расти бесконечно. Таким образом, мы в конечном итоге придем к ситуации, когда T (x) = x для всех x, которые являются фиксированной точкой.
Подход со списком работ [ править ]
Вышеописанный алгоритм легко улучшить, заметив, что внутреннее состояние блока не изменится, если исходное состояние его предшественников не изменится. Поэтому мы вводим рабочий список : список блоков, которые еще нужно обработать. Каждый раз, когда состояние выхода блока изменяется, мы добавляем его преемников в рабочий список. На каждой итерации из рабочего списка удаляется блок. Вычисляется его исходное состояние. Если состояние out изменилось, преемники блока добавляются в рабочий список. Для эффективности блок не должен быть в рабочем списке более одного раза.
Алгоритм запускается с помещения в рабочий список блоков, генерирующих информацию. Он завершается, когда рабочий список пуст.
Порядок имеет значение [ править ]
На эффективность итеративного решения уравнений потока данных влияет порядок посещения локальных узлов. [5] Кроме того, это зависит от того, используются ли уравнения потока данных для прямого или обратного анализа потока данных через CFG. Интуитивно понятно, что в задаче прямого потока было бы быстрее всего, если бы все предшественники блока были обработаны до самого блока, поскольку тогда итерация будет использовать самую последнюю информацию. При отсутствии циклов можно упорядочить блоки таким образом, чтобы правильные исходные состояния вычислялись путем обработки каждого блока только один раз.
Далее обсуждаются несколько порядков итераций для решения уравнений потока данных (связанное с порядком итераций CFG понятие - это обход дерева по дереву ).
- Случайный порядок - этот порядок итераций не знает, решают ли уравнения потока данных прямую или обратную задачу потока данных. Следовательно, производительность относительно низкая по сравнению со специализированными итерационными заказами.
- Поступорядочение - это типичный порядок итераций для проблем с обратным потоком данных. В итерации после порядка посещение узла происходит после того, как были посещены все его последующие узлы. Как правило, итерация после порядка реализуется состратегией «в глубину» .
- Обратный поступорядочение - это типичный порядок итераций для задач прямого потока данных. В итерации с обратным порядком , узел посещается до того, как был посещен какой-либо из его последующих узлов, за исключением случаев, когда последующий достигается задним краем. (Обратите внимание, что обратный постзаказ - это не то же самое, что предварительный заказ .)
Инициализация [ править ]
Начальное значение внутренних состояний важно для получения правильных и точных результатов. Если результаты используются для оптимизации компилятора, они должны предоставлять консервативную информацию, т. Е. При применении информации программа не должна изменять семантику. Итерация алгоритма фиксированной точки принимает значения в направлении максимального элемента. Поэтому инициализация всех блоков максимальным элементом бесполезна. По крайней мере, один блок запускается в состоянии со значением меньше максимального. Детали зависят от проблемы с потоком данных. Если минимальный элемент представляет собой полностью консервативную информацию, результаты можно безопасно использовать даже во время итерации потока данных. Если он представляет собой наиболее точную информацию, должна быть достигнута фиксированная точка, прежде чем можно будет применить результаты.
Примеры [ править ]
Ниже приведены примеры свойств компьютерных программ, которые можно вычислить с помощью анализа потока данных. Обратите внимание, что свойства, вычисленные с помощью анализа потока данных, обычно являются только приближением к реальным свойствам. Это связано с тем, что анализ потока данных работает с синтаксической структурой CFG, не моделируя точный поток управления программой. Однако, чтобы по-прежнему быть полезным на практике, алгоритм анализа потока данных обычно предназначен для вычисления верхнего или нижнего приближения реальных свойств программы.
Перспективный анализ [ править ]
Анализ определения достижения вычисляет для каждой точки программы набор определений, которые потенциально могут достичь этой точки программы.
если b == 4, то а = 5; еще а = 3; endif если a <4, то ...
| Достигающее определение переменной |
Обратный анализ [ править ]
Анализ динамических переменных вычисляет для каждой точки программы переменные, которые потенциально могут быть прочитаны впоследствии перед их следующим обновлением записи. Результат обычно используется при удалении мертвого кода для удаления операторов, которые присваиваются переменной, значение которой впоследствии не используется.
Состояние блока - это набор переменных, которые действуют в его начале. Первоначально он содержит все переменные, существующие (содержащиеся) в блоке, до применения передаточной функции и вычисления фактических содержащихся значений. Передаточная функция оператора применяется путем уничтожения переменных, записанных в этом блоке (удаление их из набора действующих переменных). Выходное состояние блока - это набор переменных, которые активны в конце блока и вычисляются путем объединения внутренних состояний преемников блока.
Исходный код:
b1: а = 3; b = 5; d = 4; х = 100; если a> b, тоb2: c = a + b; d = 2;b3: endif c = 4; вернуть b * d + c;
|
Обратный анализ:
// в: {}b1: а = 3; b = 5; d = 4; х = 100; // x никогда не используется позже, поэтому не в исходном наборе {a, b, d} если a> b, то// out: {a, b, d} // объединение всех (входящих) наследников b1 => b2: {a, b} и b3: {b, d} // в: {a, b}b2: c = a + b; d = 2;// выход: {b, d}// в: {b, d}b3: endif c = 4; вернуть b * d + c;// из:{}
|
Состояние in b3 содержит только b и 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]
Специальные классы задач [ править ]
Существует множество специальных классов проблем с потоками данных, которые имеют эффективные или общие решения.
Проблемы с битовыми векторами [ править ]
Приведенные выше примеры представляют собой проблемы, в которых значение потока данных является набором, например набором достижений определений (использование бита для позиции определения в программе) или набором текущих переменных. Эти наборы могут быть эффективно представлены как битовые векторы , в которых каждый бит представляет принадлежность набора к одному конкретному элементу. Используя это представление, функции соединения и передачи могут быть реализованы как побитовые логические операции. Операция соединения обычно представляет собой объединение или пересечение, реализуемое поразрядным логическим или и логическим и . Передаточная функция для каждого блока может быть разложена на так называемые наборы генерации и уничтожения .
Например, в анализе живых переменных операция соединения - это объединение. Набор уничтожения - это набор переменных, которые записываются в блок, тогда как набор генерации - это набор переменных, которые считываются без предварительной записи. Уравнения потока данных становятся
В логических операциях это читается как
out ( b ) = 0 для s in succ ( b ) out ( b ) = out ( b ) или in ( s )in ( b ) = (out ( b ), а не kill ( b )) или gen ( b )
DataFlow проблемы , которые имеют наборы значений данных потока , которые могут быть представлены в виде битовых векторов называются разрядные векторные проблемы , проблемы генераторной Убей , или локально отделимые проблемы . [8] Такие задачи имеют типичные решения за полиномиальное время. [9]
В дополнение к упомянутым выше проблемам с определениями и текущими переменными, следующие проблемы являются примерами проблем с битовым вектором: [9]
- Доступные выражения
- Очень занятые выражения
- Цепочки использования-определения
Проблемы IFDS [ править ]
Межпроцедурные, конечные, распределительные задачи подмножества или задачи IFDS - это еще один класс проблем с общим решением за полиномиальное время. [8] [10] Решения этих проблем обеспечивают контекстно-зависимый и чувствительный к потоку анализ потоков данных.
Существует несколько реализаций анализа потоков данных на основе IDFS для популярных языков программирования, например, в структурах Soot [11] и WALA [12] для анализа Java.
Каждая проблема битового вектора также является проблемой IDFS, но есть несколько значительных проблем IDFS, которые не являются проблемами битового вектора, включая действительно живые переменные и, возможно, неинициализированные переменные.
Чувствительность [ править ]
Анализ потока данных по своей природе чувствителен к потокам. Анализ потока данных обычно не зависит от пути, хотя можно определить уравнения потока данных, которые дают анализ с учетом пути.
- Анализ, чувствительный к потоку, учитывает порядок операторов в программе. Например, анализ псевдонимов указателя, нечувствительный к потоку, может определять «переменные x и y могут относиться к одному и тому же местоположению», в то время как анализ с учетом потока может определять «после оператора 20 переменные x и y могут относиться к одному и тому же местоположению».
- Анализ с учетом пути вычисляет различные фрагменты аналитической информации в зависимости от предикатов в инструкциях условного перехода. Например, если ветвь содержит условие
x>0, то на осень-через путь, анализ был бы предположить , чтоx<=0и на цели отрасли было бы предположить , что на самом делеx>0имеет место. - Контекстная анализ является межпроцедурным анализом , который учитывает контекст вызова при анализе цели вызова функции. В частности, используя контекстную информацию, можно вернуться к исходному сайту вызова, тогда как без этой информации информация анализа должна распространяться обратно на все возможные сайты вызова, потенциально теряя точность.
Список анализов потока данных [ править ]
- Достижение определений
- Анализ живучести
- Определенный анализ назначения
- Доступное выражение
- Постоянное распространение
См. Также [ править ]
- Абстрактная интерпретация
- Анализ потока управления
- XLT86
Ссылки [ править ]
- ^ Kildall, Гэри Арлен (май 1972). Оптимизация глобального выражения при компиляции (кандидатская диссертация). Сиэтл, Вашингтон, США: Вашингтонский университет , группа компьютерных наук. Тезис № 20506, Технический отчет № 72-06-02.
- ^ Килдалл, Гэри Арлен (1973-10-01). «Единый подход к глобальной оптимизации программ» (PDF) . Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования (POPL) . POPL '73. Бостон, Массачусетс, США: 194–206. DOI : 10.1145 / 512927.512945 . ЛВП : 10945/42162 . S2CID 10219496 . Архивировано (PDF) из оригинала 29.06.2017 . Проверено 20 ноября 2006 . ( [1] )
- ^ Рютинг, Оливер; Кноп, Йенс; Штеффен, Бернхард (31 июля 2003 г.) [1999]. «Оптимизация: обнаружение равенства переменных, сочетание эффективности с точностью» . В Кортеси, Агостино; Filé, Gilberto (ред.). Статический анализ: 6-й Международный симпозиум, SAS'99, Венеция, Италия, 22–24 сентября 1999 г., Материалы . Конспект лекций по информатике. 1694 (иллюстрированный ред.). Springer. С. 232–247 [233]. ISBN 9783540664598. ISSN 0302-9743 .
- ^ Хайтт, Роберт; Юбэнкс, Гордон ; Роландер, Томас «Том» Алан ; Законы, Дэвид; Michel, Howard E .; Халла, Брайан; Уортон, Джон Харрисон ; Берг, Брайан; Су, Вейлиан; Килдалл, Скотт ; Кампе, Билл (25 апреля 2014 г.). Законы, Дэвид (ред.). «Наследие Гэри Килдалла: посвящение CP / M IEEE» (PDF) (транскрипция видео). Пасифик Гроув, Калифорния, США: Музей истории компьютеров . Номер ссылки CHM: X7170.2014 . Проверено 19 января 2020 .
[…]
Юбэнкс
: […]
Гэри
[…] Был изобретателем, он был изобретателем, он делал разные вещи. Его доктор философии. Диссертация доказала, что анализ глобального потока сходится. […] Это фундаментальная идея в информатике. […] Однажды я прошел […] летний курс у парня по имени Дхамдхере […] они говорили об оптимизации около недели, а затем они подняли слайд и сказали: «Метод Килдалла», это настоящая история. […] Об этом никто никогда не думает. […]
[2] [3] (33 страницы) - ^ Купер, Кейт Д .; Харви, Тимоти Дж .; Кеннеди, Кен (2004-03-26) [ноябрь 2002]. «Повторение итеративного анализа потока данных» (PDF) . PLDI 2003 . ACM . TR04-432 . Проверено 1 июля 2017 . [ постоянная мертвая ссылка ]
- ^ Mohnen, Markus (2002). Подход к анализу потоков данных без графов . Конспект лекций по информатике. 2304 . С. 185–213. DOI : 10.1007 / 3-540-45937-5_6 . ISBN 978-3-540-43369-9.
- ^ Куанг, Хунъюй; Мэдер, Патрик; Ху, Хао; Габи, Ахраф; Хуанг, LiGuo; Люй, Цзянь; Египтян, Александр (01.11.2015). «Могут ли зависимости данных методов поддерживать оценку прослеживаемости между требованиями и исходным кодом?». Журнал программного обеспечения: эволюция и процесс . 27 (11): 838–866. DOI : 10.1002 / smr.1736 . ISSN 2047-7481 . S2CID 39846438 .
- ^ a b Представители, Томас; Хорвиц, Сьюзен; Сагив, Мули (1995). «Точный межпроцедурный анализ потока данных через доступность графа». Материалы 22-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '95 . Нью-Йорк, Нью-Йорк, США: ACM Press : 1, 49–61. DOI : 10.1145 / 199448.199462 . ISBN 0-89791692-1. S2CID 5955667 .
- ^ а б Кнуп, Йенс; Штеффен, Бернхард ; Фоллмер, Юрген (1996-05-01). «Параллелизм бесплатно: эффективный и оптимальный анализ битового вектора для параллельных программ» . Транзакции ACM по языкам и системам программирования . 18 (3): 268–299. DOI : 10.1145 / 229542.229545 . ISSN 0164-0925 . S2CID 14123780 .
- ^ Naeem, Nomair A .; Лхотак, Ондржей; Родригес, Джонатан (2010), практические Расширения IFDS алгоритма , Lecture Notes в области компьютерных наук, 6011 , Берлин / Гейдельберг, Германия: Springer Verlag , стр 124-144,. DOI : 10.1007 / 978-3-642-11970-5_8 , ISBN 978-3-64211969-9
- ^ Бодден, Эрик (2012). «Межпроцедурный анализ потока данных с использованием IFDS / IDE и сажи». Материалы международного семинара ACM SIGPLAN по современному состоянию анализа программ на Java - SOAP '12 . Нью-Йорк, Нью-Йорк, США: ACM Press : 3–8. DOI : 10.1145 / 2259051.2259052 . ISBN 978-1-45031490-9. S2CID 3020481 .
- ^ Рапопорт, Марианна; Лхотак, Ондржей; Совет, Фрэнк (2015). Точный анализ потока данных при наличии коррелированных вызовов методов . Международный симпозиум по статическому анализу. Конспект лекций по информатике. 9291 . Берлин / Гейдельберг, Германия: Springer Verlag . С. 54–71. DOI : 10.1007 / 978-3-662-48288-9_4 . ISBN 978-3-66248287-2.
Дальнейшее чтение [ править ]
- Купер, Кейт Д .; Торчон, Линда (2003) [01.01.2002]. Разработка компилятора . Морган Кауфманн . ISBN 978-1-55860-698-2.
- Мучник, Стивен Стэнли (1997). Расширенный дизайн и реализация компилятора . Издательство Морган Кауфманн . ISBN 978-1-55860-320-2.
- Хехт, Мэтью С. (1977-05-03). Анализ потока компьютерных программ . Серия языков программирования. 5 . ISBN компании Elsevier North-Holland Inc. 978-0-44400210-5.
- Хедкер, Удай П .; Саньял, Амитабха; Каркаре, Багешри (2009). Анализ потока данных: теория и практика . CRC Press ( Тейлор и Фрэнсис Групп ).
- Нильсон, Флемминг; Нильсон, Ханне Риис; Ханкин, Крис (2005). Принципы анализа программ . Springer Science + Business Media .
