А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 231
Текст из файла (страница 231)
Но тогда оба дочерних узла корня оказываются листом 1, так что можно удалить и корень. Таким образом, простейшей В!313 объединения является лист 1 сам по себе. и 12.7.5 Использование диаграмм бинарного выбора для анализа целей указателей Выполнение контекстно-нечувствительного анализа целей указателей — задача нетривиальная. Упорядочение переменных ВЕ113 может существенно влиять на размер представления.
Чтобы получить упорядочение, позволяющее быстро выполнить анализ, требуется учесть множество факторов, а также воспользоваться методом проб и ошибок. Еще труднее выполнить контекстно-чувствительный анализ целей указателей, что связано с экспоненциальным количеством контекстов в программе. В частности, при произвольном назначении номеров для представления контекстов в графе вызовов мы не сможем справиться даже с небольшой программой на языке программирования 3ача.
Очень важно пронумеровать контексты таким образом, чтобы бинарное кодирование анализа целей указателей могло быть очень компактным. Два контекста одного и того же метода с похожими путями вызова имеют очень много общего, так что желательно пронумеровать п контекстов метода последовательно. Аналогично, поскольку пары вызываемых и вызывающих методов в одной точке вызова также имеют очень много общего, желательна такая нумерация контекстов, чтобы числовая разность между каждой парой вызываемых и вызывающих методов в точке вызова была константой. Даже при удовлетворяющей всем условиям схеме контекстов вызовов эффективно проанализировать программу на языке программирования 1ача все равно сложно.
Для получения упорядочения переменных, достаточно эффективного для обработки больших приложений, можно попробовать применить активное машинное обучение. 1124 Глава 12. Межпроцедурный анализ 12.7.6 Упражнения к разделу 12.7 Упражнение 12.7Л. Используя кодирование символов из примера 12.28, разработайте В!7!1, которая представляет отношение, состоящее из кортежей (Ь, Ь), (с, и) и (Ь, а). Булевы переменные упорядочьте любым способом, который даст вам наиболее краткую ВОР.
! Упражнение 12.7.2. Выразите количество узлов в наиболее краткой ВОР, представляющей функцию ИСКЛЮЧАЮЩЕГО ИЛИ от и переменных в виде функции от и. Такая функция ИСКЛЮЧАЮЩЕГО ИЛИ от п переменных возвращает значение "истинно", если среди п переменных нечетное количество истинных, и "ложно", если таких переменных четное число.
Упражнение 12.7.3. Модифицируйте алгоритм )2.29 так, чтобы он давал нам пересечение (логическое И) двух ВГИ). )! Упражнение 12.7.4. Разработайте алгоритмы для выполнения следующих операций над отношениями, представленными упорядоченными диаграммами бинарного выбора. а) Удаление некоторых из булевых переменных.
Представляющая функция должна быть истинна для данного набора значений переменных о, если исходная функция истинна для набора значений переменных о и любого значения удаленной переменной. б) Соединения двух отношений г н а путем объединения кортежа из г с кортежем из а, когда зги кортежи согласуются по общим атрибутам из г и в. Достаточно рассмотреть случай, когда отношения состоят только из двух компонентов, один из которых присутствует в обоих отношениях, т.е. отношения представляют собой т (А, В) и в (В, С). 12.8 Резюме к главе 12 + Межпроцедурный анализ. Анализ потока данных, который отслеживает информацию через границы процедур, называется межпроцедурным анализом.
Многие анализы, такие как анализ целей указателей, могут дать полезные результаты, только если являются межпроцедурными. + Точки вызова. Программа вызывает процедуры в определенных точках, известных как точки вызова. Вызываемая процедура может быть очевидна, но может быть и неоднозначна, если вызывается косвенно через указатель или представляет собой вызов виртуального метода, имеющего несколько реализаций.
1125 12.8. Резюме к главе 12 + Графы вызовов. Граф вызова программы представляет собой двудольный граф, узлами которого являются точки вызовов и процедуры. Ребра графа идут от узла точки вызова к узлу процедуры, если данная процедура может быть вызвана в данной точке. + Встраивание. При отсутствии в программе рекурсии, в принципе, можно заменить все вызовы процедур копиями их кода и применить к получившейся программе внутрипроцедурный анализ. Такой анализ по сути является межпроцедурным.
+ Чувствительность к потоку и контекстная чувствительность. Анализ потока данных называется чувствительным к потоку, если он генерирует факты, зависящие от местоположения в программе. Если эти факты зависят от истории вызовов процедур, то такой анализ называется контекстно-чувствительным. Анализ потока данных может быть чувствителен к потоку, контекстно-чувствителен, может обладать обоими этими свойствами или ни одним из них.
+ Контекстно-чувствительный анализ, основанный на клонировании. В принципе, установив различные контексты, в которых может быть вызвана процедура, можно представить, что имеется клон каждой процедуры для каждого контекста. Таким образом контекстно-нечувствительный анализ работаег в качестве контекстно-чувствительного. + Контекстно-чувствительный анализ, основанный на резюме. Еще один подход к межпроцедурному анализу заключается в распространении ранее описанной методики анализа на основе областей для межпроцедурного анализа.
Кюкдая процедура имеет свою передаточную функцию и в каждом месте вызова процедуры рассматривается как область. + Применение меяслроледурного анализа. Важным приложением, требующим межпроцедурного анализа, является обнаружение уязвимых мест программного обеспечения.
Они зачастую характеризуются чтением данных из ненадежного источника одной процедурой с последующим использованием их другой. + 22ага1од. Язык Вага!оя предоставляет возможность простой записи правил "если-то", которые могут использоваться для описания анализа потока данных на высоком уровне. Наборы Вага!оя-правил, или Вага!оя-программы, могут вычисляться при помощи одного из нескольких стандартных алгоритмов. 1126 Глава 12.
Межпроцедуриый анализ + Оага1од-правила. Правило Ра!а!оя состоит из тела !посылки) и заголовка !следствия). Тело представляет собой один или несколько атомов, а заголовок — ровно один атом. Атомы — это предикаты, применяемые к аргументам, которые могут быть переменными или константами. Атомы тела соединяются при помощи логического И; кроме того, в теле может использоваться отрицание атома. + ЮВ- и Е1хВ-предикаты. Истинные факты ЕПВ-предикатов в Па!а!ой-программе известны априори. В анализе потоков данных эти предикаты соответствуют фактам, которые могут быть получены из анализируемого кода. !ПВ-предикаты определяются самими правилами и в анализе потоков данных соответствуют информации, которую мы пытаемся получить из анализируемого кода. + Вычисление 0ага1ой-програлои.
Мы применяем правила путем подстановки вместо переменных констант, которые делают тело истинным. При этом мы выводим заголовок, который также истииеи при данной подстановке. Эта операция повторяется до тех пор, пока ие останется иевыведеииых фактов. + Инкрементное вычисление Вага1оВ-программ. Повышение эффективности достигается за счет инкрементных вычислений. Мы выполняем ряд итераций.
В одной итерации мы рассматриваем только те подстановки констант вместо переменных, которые делают как минимум один атом тела фактом, открытым иа предыдущей итерации. + Анализ указателей .Уауа. Анализ указателей в !ача можно моделировать схемой, в которой существуют ссылочиые переменные, указывающие иа объекты кучи, которые, в свою очередь, могут иметь поля, указывающие иа другие обьекты кучи. Нечувствительный анализ указателей можно записать в виде Ра!а!ой-программы, которая выводит два вида фактов: что переменная может указывать иа объект кучи или что поле объекта кучи может указывать иа другой объект кучи.
+ Использование информации о типах. Более точною анализа указателей можно добиться, если воспользоваться тем фактом, что ссылочиые переменные могут указывать только иа те объекты кучи, которые принадлежат тому же типу, что и переменная, или его подтипу. + Межпроцедурный анализ указателей. Чтобы сделать анализ межпроцедуриым, требуется добавить правила, которые отражают то, как передаются параметры и как возвращаемые значения присваиваются переменным. Эти правила по сути те же, что и правила для копирования одной ссылочиой переменной в другую. П27 12.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
