А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 228
Текст из файла (страница 228)
Какой из них мы должны использовать? При вычислении резюме информации о целях указателей имеется ряд трудностей. Резюме имеют большой размер. Резюме каждого метода должно включать результат действий функции и всех функций, вызываемых ею„на входные параметры. Иначе говоря, метод может изменить множество целей всех данных, достижимых через статические переменные, входные параметры и все объекты, создаваемые методом и вызываемыми им функциями. До сих пор не имеется решения, которое можно было бы масштабировать для больших программ.
Даже если резюме сможет быть вычислено при восходяшем проходе, то вычисление множеств целей для всего экспоненциального количества контекстов при нисходящем проходе представляет собой еше большую проблему. Такая информация 1110 Глава 12. Межпроцедурный анализ необходима для глобальных запросов наподобие поиска всех точек в коде, которые обращаются к некоторому объекту. В этом разделе мы рассмотрим контекстно-чувствительный анализ, основанный на клонировании. Такой анализ просто клонирует методы, по одному для каждого интересуюшего нас контекста.
Затем мы применяем к клонированному графу вызовов контекстно-нечувствительный анализ. Хотя этот подход и кажется простым, но проблема заключается в деталях обработки больших количеств клонов. Сколько всего существует контекстов? Даже если воспользоваться идеей свертки всех рекурсивных циклов, рассматривавшейся в разделе 12.1.3, вряд ли удастся найти все 10'4 контекстов приложений Гала. Представление результатов такого количества контекстов — задача не для слабонервных.
Разделим рассмотрение контекстно-чувствительного анализа на две части. 1. Как логически работать с контекстной чувствительностью? Эта часть проста, так как мы просто применяем контекстно-нечувствительный алгоритм к клонированному графу потока. 2. Как представить экспоненциальное количество контекстов? Один из способов состоит в представлении информации в виде диаграмм бинарного выбора (Ь1пагу бес1а1оп дщгашз — ВРР) — высокооптимизированной структуры данных, используемой во многих других приложениях. Этот подход к контекстной чувствительности представляет собой прекрасный пример важности абстракции. Как мы покажем, устранение алгоритмической сложности возможно благодаря многим годам работы, вылившимся в ВРР- абстракпию.
Можно определить контекстно-чувствительный анализ целей указателей всего лишь несколькими строками Ра1а1оя, которые, в свою очередь, используют тысячи строк существующего кода для работы с ВРР. Этот подход имеет несколько важных преимушеств. Во-первых, он позволяет легко выразить различные дальнейшие анализы, которые используют результаты анализа целей указателей. В конце концов, сам по себе анализ целей указателей мало интересен. Во-вторых, он облегчает написание корректного анализа, позволяя воспользоваться большим количеством готового хорошо отлаженного кода. 12.6.1 Контексты и строки вызовов В контекстно-чувствительном анализе целей указателей, описанном ниже, предполагается, что граф вызовов уже вычислен. Этот шаг помогает получить компактное представление многих контекстов вызовов. Для получения графа вызовов сначала выполняется рассматривавшийся в разделе 12.5 контекстно-нечувствительный анализ целей указателей, который строит граф вызовов "на лету".
Сейчас мы опишем, как создать клонированный граф вызовов. 1111 ) 2.6. Контекстно-чувствительный анализ указателей Контекст является представлением строки вызовов, которая формирует историю активных вызовов функций. Другой взгляд на контекст рассматривает его как резюме последовательности вызовов, записи активации которых находятся в настояшее время в стеке времени выполнения. Если в стеке нет рекурсивных функций, то строка вызовов — последовательность точек, из которых выполнялись вызовы в стеке — является полным представлением.
Это приемлемое представление в том смысле, что в нем содержится конечное количество различных контекстов, хотя это количество может экспоненциально зависеть от количества функций в программе. Однако если в программе имеются рекурсивные функции, то количество возможных строк вызовов становится бесконечным, н мы не можем позволить всем возможным строкам вызовов представлять различные контексты. Существуют разные способы ограничения количества различных контекстов.
Например, можно записать регулярное выражение, которое описывает все возможные строки вызовов, и преобразовать это регулярное выражение в детерминированный конечный автомат с применением методов из раздела 3.7. После этого контекст может идентифицироваться состояниями этого автомата. Здесь мы применим более простую схему, которая собирает историю нерекурсивных вызовов, а рекурсивные вызовы рассматривает как "слишком сложные". Мы начнем с поиска всех множеств взаимно рекурсивных функций в программе.
Этот процесс прост и детально рассматриваться здесь не будет. Представим граф, узлами которого являются функции, а наличие ребра от р к д означает, что функция р вызывает функцию д. Сильно связанные компоненты такого графа представляют собой множества взаимно рекурсивных функций. Распространенный частный случай — функция, вызывающая саму себя и не входящая в сильно связанный компонент с другими функциями. Такая функция образует сильно связанный компонент сама по себе. Нерекурсивные функции также образуют сильно связанные компоненты сами по себе. Назовем сильно связанный компонент нетривиальным, если он либо состоит более чем нз одного члена (случай взаимной рекурсии), либо имеет единственный рекурсивный член.
Сильно связанный компонент, состоящий нз единственной нерекурсивной функции, будем называть тривиальным сильно связанным компонентом. Модифицируем правило, что любая строка вызовов представляет собой контекст, следующим образом. Для данной строки вызовов удаляем точку вызова з, если выполняется следующее. 1. з находится в функции р. 2. В точке з вызывается функция д (возможно, что д == р). 3. р и д находятся в одном и том же сильно связанном компоненте (т.е, р и д взаимно рекурсивны, или д = р и р — рекурсивная функция).
1112 Глава 12. Межпроцедурный анализ В результате, когда вызывается член нетривиального сильно связанного компонента Я, соответствующая точка вызова становится частью контекста, но вызовы внутри Я других функций из того же сильно связанного компонента не являются частью контекста. Наконец, когда из Я делается вызов "вовне", эта точка вызова записывается как часть контекста. Пример 12.26. На рис. 12.28 приведен набросок из пяти функций с некоторыми точками вызова и вызовами друг друга. Изучение вызовов показывает, что д и г являются взаимно рекурсивными, а р, в и ( — не рекурсивными. Таким образом, наши контексты представляют собой списки всех точек вызова за исключением яЗ и з5, в которых имеют место рекурсивные вызовы между д и г.
чойс( р() ( Ь: а = пеы Т; з1: Т Ь = с((а)з з2: я ()з); с((Т и) ( зЗ: с = г(и); Т с) = пеы Т; я4: с (с(); гесцгп с); Т г(Т х) ( я5: Т е = с1(х); яб: я(е); гесцгп е; чофс( з(Т у) ( я7: Т ~ = Г(У)' я8: Й = г(Й); Т с(Т е) Т ~2 = пеы Т; гегигп д; ) Рис. 12.28. Функции и точки вызова к примеру 12.26 Шз 12.6. Контекстно-чувствительный анализ указателей Рассмотрим все сгюсобы достижения р из 1, т.е. все контексты, в которых осуществляется вызов 1.
!. р может вызвать а в точке в2, а затем а может вызвать 1 в точке в7 или в8. Таким образом, две возможные строки вызовов — (а2, а7) и (а2, з8). 2. р может вызвать д в точке в1. Затем 9 и г могут несколько раз рекурсивно вызывать друг друга. Этот цикл вызовов может быть остановлен следующими способами. а) В точке в4, где 1 вызывается непосредственно из д. Это дает нам только один контекст (а1,з4). б) В точке вб, где т вызывает я. Здесь мы можем достичь 1 вызовом либо в точке в7, либо в точке в8. Это дает нам еще два контекста— (з1, аб, а7) и (з1, зб, а8).
Таким образом, всего имеется пять контекстов вызова 1. Обратите внимание, что все эти контексты не включают точки рекурсивных вызовов вЗ и в5. Например, контекст (в1, а4) на самом деле представляет бесконечное множество строк вызовов (а1,зЗ,(аб,зЗ)",з4) для всех п > О. а Опишем теперь, как строится клонированный граф.
Каждый клонированный метод идентифицируется методом М программы и контекстом С. Ребра можно получить путем добавления соответствующих контекстов к каждому из ребер исходного графа вызовов. Вспомним, что если предикат 1люкез (Я, М) истинен, то в исходном графе вызовов имеется ребро от точки вызова Я к методу М.
Чтобы добавить контекст для идентификации методов в клонированном графе вызовов, можно определить соответствующий предикат СЯлгокез, такой, что С%иго/сея (Я, С, М, Р) истинно, если точка вызова о в контексте С вызывает контекст Р метода М. 12.6.2 Добавление контекста в правила Вша!од Чтобы найти контекстно-чувствительные отношения указывания, можно просто применить контекстно-нечувствительный анализ целей указателей к клонированному графу вызовов.
Поскольку метод в клонированном графе вызовов представлен исходным методом и контекстом, мы должны соответствующим образом изменить правила Ра1а!о8. Для простоты приведенные на рис. 12.29 правила не включают ограничений, связанных с типами; символы являются любыми новыми переменными. Дополнительный аргумент, представляющий контекст, должен быть передан 1РВ-предикату рв. ргз (К С, Н) гласит, что переменная Ъ" в контексте С может указывать на обьект Н. Все правила самоочевидны, за исключением, возможно, 1114 Глава! 2. Межпроцедурный анализ 1) рь(1г,С,Н): — "Н: Т и = пезгТ()" й СЯ1нкокея(Н, С,, ) 2) ргк(1г,С,Н): — "и = И'" й рь(Иг, С, Н) 3) Ьрь(Н,Г,С): — "Кр = И"' й рь(И;С,С) й рь(К С, Н) 4) рь(Ъ; С, Н): — "1' = И'Х" й рь(И~,С,С) й йрь(С, Р, Н) 5) рь(1', Р, Н): — СЯтуо)гек(Б, С, ЛХ, Р) й Х 1(М,Х,Р') й асгиа1(Н,Х, И') й рь(И;С, Н) Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
