А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 229

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

Текст из файла (страница 229)

12.29. Программа Оага1ок для контекстно-чувствительного анализа целей указателей правила 5. Это правило гласит, что если точка вызова Я в контексте С вызывает метод ЛХ контекста Р, то формальные параметры в методе ЛХ контекста Р могут указывать на объекты, на которые указывают соответствующие фактические параметры в контексте С.

12.6.3 Доиолнительные наблюдения о чувствительности Описанное нами — одна из формулировок контекстной чувствительности, которая достаточно практична для обработки больших реальных программ на языке программирования 1ауа, с применением приемов, которые вкратце будут описаны в следующем разделе. Тем не менее данный алгоритм не в состоянии обрабатывать приложения Хака очень большого размера. Объекты кучи в данной формулировке именуются их точками вызовов, но без учета контекста. Такое упрощение может привести к проблемам. Рассмотрим идиому фабрики объектов, в которой все объекты одного и того же типа создаются одной и той же подпрограммой. Рассматриваемая схема приведет к тому, что все 1115 12.7. Реализация Оаза!оя с применением ВОО эти объекты будут носить одно и то же имя.

Эту ситуацию относительно просто обработать путем встраивания кода создания нового объекта. В общем случае желательно повысить чувствительность к контексту при именовании объектов. Но хотя добавить чувствительность объектов к контексту в Оага1оя-формулировку несложно, обеспечить масштабируемость данного анализа для работы с большими программами — совершенно другое дело. Еще одним важным видом чувствительности является чувствительность к объектам. Объектно-чувствительный метод может различать методы разных вызываемых объектов. Рассмотрим сценарий точки вызова в контексте, где переменная, как выясняется, может указывать на два разных вызываемых объекта одного и того же класса. Их поля могут указывать на разные объекты.

Если нет возможности различить этн объекты, копирование среди полей объекта, на который ссылается г!з1в, будет создавать ложные отношения — если только мы не сможем разделить анализ в соответствии с вызываемыми объектами. В некоторых случаях объектная чувствительность оказывается более полезной, чем контекстная. 12.6.4 Упражнения к разделу 12.6 Упражнение 12.6.1. Какие контексты будут найдены при применении методов из данного раздела к коду на рис.

12.30? ! Упражнение 12.6.2. Выполните контекстно-чувствительный анализ кода на рис. 12.30. ! Упражнение 12.6.3. Следуя подходу из раздела 12.5, измените Оа!а!оп-правила нз данного раздела так, чтобы они включали информацию о типах и подтипах. 12.7 Реализация Ра1а1оя с применением ВРО Диаграммы бинарного выбора (Ь!вагу дес1яоп йадгащя — ВОО) представляют собой метод представления булевых функций графами.

Г1оскольку всего существует 2з булевых функций от п переменных, нет метода представления всех булевых функций, который был бы достаточно лаконичным. Однако булевы функции, встречающиеся на практике, обычно достаточно регулярны. Таким образом, обычно для них удается найти достаточно краткие ВОО. Оказывается, что булевы функции, описываемые Оа!а!оя-программами, разработанными для анализа исходных текстов программ, не являются исключением.

Хотя краткие ВОО-представления информации о программах зачастую требуют применения эвристик и/или методов, используемых в коммерческих ВОО-пакетах, на практике ВОО-подход зарекомендовал себя как вполне успешный. В частности, он превосходит методы, основанные на обычных системах баз данных, поскольку 1116 Глава 12. Межпроцедурный анализ с1азз т ( згоз.с) р() ( Ь: Т а = пеи Т(); т Ь = пеи Т(); с1: Т с = а.с1(Ь): т ((т у) Т с( = пеи Т(); с2: с) = ГЬз.з.с((с(); сЗ: с1 = с1.Ч(у); с4: с) = с1.г(); гегцгп Ф Т г() ( гегцгп гЬзз; ) ) Рис.

!2.30. Код к упражнениям !2.6.! и !2.6.2 последние разработаны для более нерегулярных данных, обычно встречающихся в коммерческих приложениях. Рассмотрение всей разрабатываемой годами ВРР-технологии выходит за пределы нашей книги. Здесь мы только вкратце рассмотрим концепцию ВРР: каким образом представить связанные данные в виде ВРР и как работать с ВРР для отражения операций, выполняющих Ра!а1ол-программы при помощи алгоритмов, таких как алгоритм 12.18.

Наконец, мы опишем, как представить в ВРР экспоненциальное количество контекстов, что является ключом к успешному использованию ВРР в контекстно-чувствительном анализе. 12.7.1 Диаграммы бинарного выбора Диаграммы бинарного выбора представляют булевы функции при помощи ориентированного ациклического графа с корнем. Каждый внутренний узел ориентированного ациклического графа помечен одной из переменных представляемой функции. В нижней части ориентированного ациклического графа находятся два листа, помеченные О и 1. Каждый внутренний узел имеет два ребра к дочерним узлам; эти ребра называются верхним ()з(я)з) и нижним (1ои). Нижнее ребро связано со случаем, когда переменная в узле имеет значение О, а верхнее — когда ее значение равно 1.

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

Пример 12.27. На рис. 12.31 приведен пример ВПП. Ниже мы познакомимся с функцией, которую представляет это В!30. Все нижние ребра на рисунке имеют метку О, а верхние — метку 1. Рассмотрим вычисление функции для набора переменных ю = х = у = 0 и а = 1. Начнем с корня. Поскольку ю = О, мы выбираем левое ребро, которое приводит нас к левому узлу х. Поскольку х = О, мы вновь выбираем левое ребро, которое приводит нас в левый узел у, где мы также выбираем левое ребро в силу у = О.

Это ребро приводит нас в левый узел г, в котором, поскольку г = 1, мы выбираем правое ребро, ведущее нас в лист 1. Таким образом, мы делаем заключение, что для данного набора значений переменных функция возвращает значение "истина". Рис. !2.3!. Диаграмма бинарного выбора Рассмотрим теперь набор значений тасуя = 0101, т.е. ю = у = 0 и т = г = 1.

Мы снова начинаем с корня ВПП. Поскольку зл = О, мы опять идем по левому ребру в левый узел з. Но теперь, поскольку х = 1, мы выходим из этого узла 1118 Глава 12. Межпроцедурный анализ по верхнему ребру, которое ведет нас непосредственно в лист О. Значит, для набора значений 0101 функция возвращает значение "ложь".

Но поскольку мы не использовали прн этом значений у и г, можно заключить, что функция ложна для всех наборов значений 01уг. Такое "сокращенное вычисление" — одна из причин, по которой ВОР обычно является лаконичным представлением булевых функций. а На рис. !2.3! узлы распределены по рангам — каждый ранг содержит узлы с меткой определенной переменной.

Хотя это не обязательное требование, удобно самоограничиться упорядоченными диаграммами бинарного выбора. В упорядоченной ВРР существует порядок тз, хз,..., х„переменных, и, если существует ребро от родительского узла с меткой х, к дочернему узлу с меткой х, то 1 < ~. Мы увидим, что работать с упорядоченной ВРР проще, поэтому далее все рассматриваемые ВОР предполагаются упорядоченными. Заметим также, что диаграммы бинарного выбора являются ориентированными ациклическими графами, но не деревьями. В них не только листья 0 и 1 обычно имеют по нескольку родительских узлов, но и внутренние узлы также могут иметь по нескольку родительских. Например, крайний справа узел г на рис.

12.31 имеет два родительских узла. Это объединение узлов — вторая причина, по которой ВОР обычно достаточно кратки. 12.7.2 Преобразования диаграмм бинарного выбора Выше мы упоминали, что два упрощения ВРР могут ее сократить. !. Сокращенные вычисления. Если у узла Х н верхнее, и нижнее ребра идут в один и тот же узел М, то узел Ю можно удалить. Ребра, входящие в !т', перенаправляются в узел ЛХ. 2.

Слияние узлов. Если у двух узлов, Л! и ЛХ, нижние ребра идут в один и тот же узел и верхние ребра также идут в один и тот же узел, то узлы Ю и М можно объединить в один. Ребра, входящие в узлы Л! и ЛХ, теперь идут в объединенный узел. Эти преобразования могут быть выполнены и в обратном направлении. В частности, в ребро от Х к М можно добавить новый узел. Оба ребра из этого нового узла ведут в ЛХ, а ребро из Х, которое ранее шло в узел М, теперь идет в новый узел. Заметим, однако, что переменная, назначаемая новому узлу, должна быть одной из переменных, лежащих между Л! н М в порядке, используемом ВРР.

Характеристики

Список файлов книги