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

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

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

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

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

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

out_{b}=trans_{b}(in_{b})

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

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

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

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

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

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

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

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

для i ← 1 до N

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

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

для i ← 1 до N

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

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

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

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

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

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

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

Заказ

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

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

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

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

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

Примеры

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

Форвардный анализ

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

  if b == 4 then
     a = 5;
  else 
     a = 3;
  endif
 
  if a < 4 then
     ...

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

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

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

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

Начальный код:

b1: a = 3; 
    b = 5;
    d = 4;
    x = 100;
    if a > b then
b2:    c = a + b;
       d = 2;
b3: endif
    c = 4;
    return b * d + c;

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

// in: {}
b1: a = 3; 
    b = 5;
    d = 4;
    x = 100; //x is never being used later thus not in the out set {a,b,d}
    if a > b then
// out: {a,b,d}    //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d}  

// in: {a,b}
b2: c = a + b;
    d = 2;
// out: {b,d}

// in: {b,d}
b3: endif
    c = 4;
    return b * d + c;
// out:{}

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

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

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

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

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

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

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

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

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

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

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

Бит-векторные проблемы

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

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

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

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

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

out(b) = 0
for s in succ(b)
    out(b) = out(b) or in(s)
in(b) = (out(b) and not kill(b)) or gen(b)

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

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

Проблемы ИФДС

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

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

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

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

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

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

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

См. также

Ссылки

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

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

Купер, Кейт Д .; Торчон, Линда (2003) [2002-01-01]. Разработка компилятора . Морган Кауфманн . ISBN 978-1-55860-698-2 .
Мучник, Стивен Стэнли (1997). Расширенное проектирование и реализация компилятора . Издательство Морган Кауфманн . ISBN 978-1-55860-320-2 .
Хехт, Мэтью С. (3 мая 1977 г.). Анализ потока компьютерных программ . Серия «Языки программирования». Том. 5. Elsevier North-Holland Inc. ISBN компании 978-0-44400210-5 .
Хедкер, Удай П.; Саньял, Амитабха; Каркаре, Багешри (2009). Анализ потоков данных: теория и практика . CRC Press ( Группа Тейлора и Фрэнсиса ).
Нильсон, Флемминг; Нильсон, Ханне Риис ; Хэнкин, Крис (2005). Принципы анализа программ . Springer Science+Business Media .

[Kildall_1972_Optimization-1] Килдалл, Гэри Арлен (май 1972 г.). Глобальная оптимизация выражений во время компиляции (кандидатская диссертация). Сиэтл, Вашингтон, США: Вашингтонский университет , Группа компьютерных наук. Диссертация №20506, Технический отчет №72-06-02.

[Kildall_1973_Optimization-2] Килдалл, Гэри Арлен (1 октября 1973 г.). «Единый подход к глобальной оптимизации программ» (PDF) . Материалы 1-го ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования (POPL) . ПОПЛ '73. Бостон, Массачусетс, США: 194–206. дои : 10.1145/512927.512945 . hdl : 10945/42162 . S2CID 10219496 . Архивировано (PDF) из оригинала 29 июня 2017 г. Проверено 20 ноября 2006 г. ( [1] )

[Cortesi_1999-3] Рютинг, Оливер; Кноп, Йенс; Штеффен, Бернхард (31 июля 2003 г.) [1999]. «Оптимизация: обнаружение равенства переменных, сочетание эффективности и точности» . В Кортези, Агостино; Файле, Жилберто (ред.). Статический анализ: 6-й Международный симпозиум, SAS'99, Венеция, Италия, 22–24 сентября 1999 г., Труды . Конспекты лекций по информатике. Том. 1694 г. (иллюстрированное изд.). Спрингер. С. 232–247 [233]. ISBN 9783540664598 . ISSN 0302-9743 .

[Laws_2014_IEEE-4] Хюитт, Роберт; Юбэнкс, Гордон ; Роландер, Томас «Том» Алан ; Лоус, Дэвид; Мишель, Ховард Э.; Халла, Брайан; Уортон, Джон Харрисон ; Берг, Брайан; Су, Вейлянь; Килдалл, Скотт ; Кампе, Билл (25 апреля 2014 г.). Лоус, Дэвид (ред.). «Наследие Гэри Килдалла: посвящение вехе CP / M IEEE» (PDF) (видеотранскрипция). Пасифик-Гроув, Калифорния, США: Музей истории компьютеров . Справочный номер CHM: X7170.2014 . Проверено 19 января 2020 г. […] Юбэнкс : […] Гэри […] был изобретателем, он был изобретательным, он что-то делал. Его доктор философии. диссертация доказала, что анализ глобальных потоков сходится. […] Это фундаментальная идея в информатике. […] Однажды я прошёл […] летний курс у парня по имени Дхамдере […] они примерно неделю говорили об оптимизации, а затем выставили слайд и сказали: «Метод Килдалла», это реальная история. […] об этом никто никогда не думает. […] [2] [3] (33 страницы)

[Cooper_2004-5] Купер, Кейт Д .; Харви, Тимоти Дж.; Кеннеди, Кен (26 марта 2004 г.) [ноябрь 2002 г.]. «Итеративный анализ потоков данных, новый взгляд» (PDF) . ПЛДИ 2003 . АКМ . ТР04-432 . Проверено 1 июля 2017 г. ^{[ постоянная мертвая ссылка ]}

[6] «Статическое одиночное присвоение (с соответствующими примерами)» . Гики для Гиков . 02.10.2021 . Проверено 16 августа 2023 г.

[Mohnen_2002-7] Монен, Маркус (2002). «Графиковый подход к данным — анализ потоков». Конструкция компилятора . Конспекты лекций по информатике. Том. 2304. стр. 185–213. дои : 10.1007/3-540-45937-5_6 . ISBN 978-3-540-43369-9 .

[Kuang_2015-8] Куанг, Хунъюй; Мэдер, Патрик; Ху, Хао; Габи, Ахраф; Хуан, ЛиГо; Лю, Цзянь; Эгед, Александр (1 ноября 2015 г.). «Могут ли зависимости данных метода поддерживать оценку прослеживаемости между требованиями и исходным кодом?». Журнал программного обеспечения: эволюция и процесс . 27 (11): 838–866. дои : 10.1002/смр.1736 . ISSN 2047-7481 . S2CID 39846438 .

[Reps_1995-9] Перейти обратно: ^а ^б Репс, Томас; Хорвиц, Сьюзен; Сагив, Мули (1995). «Точный межпроцедурный анализ потоков данных через достижимость графа». Материалы 22-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '95 . Нью-Йорк, Нью-Йорк, США: ACM Press . стр. 1, 49–61. дои : 10.1145/199448.199462 . ISBN 0-89791692-1 . S2CID 5955667 .

[Knoop_1996-10] Перейти обратно: ^а ^б Кноп, Йенс; Штеффен, Бернхард ; Фоллмер, Юрген (1 мая 1996 г.). «Бесплатный параллелизм: эффективный и оптимальный битвекторный анализ для параллельных программ» . Транзакции ACM в языках и системах программирования . 18 (3): 268–299. дои : 10.1145/229542.229545 . ISSN 0164-0925 . S2CID 14123780 .

[Naeem_2010-11] Наим, Номаир А.; Лхотак, Ондржей; Родригес, Джонатан (2010), «Практические расширения алгоритма IFDS», Конструкция компилятора , Конспекты лекций по информатике, том. 6011, Берлин/Гейдельберг, Германия: Springer Verlag , стр. 124–144, doi : 10.1007/978-3-642-11970-5_8 , ISBN 978-3-64211969-9

[Bodden_2012-12] Бодден, Эрик (2012). «Межпроцедурный анализ потоков данных с помощью IFDS/IDE и Soot». Материалы международного семинара ACM SIGPLAN по современному анализу Java-программ . Нью-Йорк, Нью-Йорк, США: ACM Press . стр. 3–8. дои : 10.1145/2259051.2259052 . ISBN 978-1-45031490-9 . S2CID 3020481 .

[Rapoport_2015-13] Рапопорт, Марианна; Лхотак, Ондржей; Совет, Фрэнк (2015). Точный анализ потока данных при наличии коррелированных вызовов методов . Международный симпозиум по статическому анализу. Конспекты лекций по информатике. Том. 9291. Берлин/Гейдельберг, Германия: Springer Verlag . стр. 54–71. дои : 10.1007/978-3-662-48288-9_4 . ISBN 978-3-66248287-2 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

v т и Оптимизация компилятора
Basic block	Peephole optimization Local value numbering
Loop	Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction
Data-flow analysis	Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Use-define chain
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Instruction scheduling Instruction selection Register allocation Rematerialization
Functional	Deforestation Tail-call elimination
Global	Interprocedural optimization
Other	Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization
Static analysis	Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis