А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 225
Текст из файла (страница 225)
Начнем с анализа, нечувствительного к потоку и контексту, полагая для начала, что в программе не вызываются никакие методы. Затем опишем, как можно строить граф вызовов "на лету" при вычислении результатов анализа целей указателей. И наконец мы опишем один из контекстно-чувствительных методов. 12.4.2 Модель указателей и ссылок Предположим, что наш язык программирования имеет следующие способы представления и работы со ссылками. 1. Некоторые переменные в программе имеют тип "указатель на Т" или "ссылка на Т", где Т вЂ” тип языка программирования.
Эти переменные либо статические, либо активные в стеке времени выполнения. Далее мы будем называть их просто переменными. 2. Имеется куча объектов. Все переменные указывают на объекты кучи, но не на иные переменные. Такие объекты мы будем называть объектами кучи (Ьеар оЬ1ес1я). 3. Объект кучи может иметь ноля, а значение поля может быть ссылкой на объект кучи (но не на переменную). Такая структура хорошо моделирует язык программирования 5ача, и в примерах мы будем использовать синтаксис зача. Заметим, что язык программирования С моделируется существенно хуже, поскольку переменные-указатели в С могут указывать на другие переменные-указатели, и, в принципе, любое значение С может быть преобразовано в указатель.
Поскольку мы выполняем нечувствительный анализ, достаточно утверждения, что данная переменная о может указывать на данный объект кучи 6; нас не интересует вопрос, где именно в программе о может указывать на 6 или в каком контексте и может указывать на 6. Заметим, однако, что переменные могут быть именованы при помощи их полных имен. В зача такое полное имя может включать модуль, класс, метод и блок в методе наряду с самим именем переменной. )ОДЕВ Глава 12. Межпропедурный анализ Таким образом, мы можем различать несколько переменных с одним и тем же идентификатором.
Объекты кучи не имеют имен. Динамически может быть создано неограниченное количество объектов. Мы будем ссылаться на объекты с использованием инструкций, в которых они были созданы. Поскольку инструкция может выполняться многократно и каждый раз создавать новый объект кучи, утверждение наподобие ев может указывать на 6" на самом деле означает чв может указывать на один или несколько объектов, созданных в инструкции с меткой 6". Цель анализа состоит в определении того, на что может указывать каждая переменная и каждое поле каждого объекта кучи.
Будем называть такой анализ анализам целей указателей (ро)п(з-(о апа1уяя); два указателя являются псевдонимами, если их целевые множества пересекаются. Здесь мы опишем анализ, основанный на включении ()пс!пз1че-Ьаяеп); т.е. инструкция вида ч = и приводит к тому, что переменная о указывает на все объекты, на которые указывает ю, но не наоборот. Хотя этот подход и кажется очевидным, существуют и иные альтернативы определения анализа целей указателей. Например, можно определить анализ, основанный на эквивалентности (ейп1ча!енсе-Ьаяеп), такой, что инструкция вида ч = и помещает переменные с и и~ в один класс эквивалентности, указывающий на все переменные, на которые может указывать каждый из указателей.
Хотя эта формулировка и не обеспечивает хорошего приближения при вычислении псевдонимов, она предоставляет быстрый, а часто и достаточно хороший ответ на вопрос о том, какие переменные указывают на один и тот же вид объектов. 12.4.3 Нечувствительность к потоку Начнем с очень простого примера для иллюстрации влияния игнорирования потока управления в анализе целей указателей. пеи ОЬ3есс(); пеи ОЬЗесс(); пеи ОЬЗесс(); Ь| с; а; 1) Ь: 2) з.: 3) 3: 4) 5) 6) Рис. 12.20. Кол Зача к примеру 12.22 Пример 12.22.
На рис. ! 2.20 создаются три объекта, 6, ( и 2, которые присваива- ются соответственно переменным а, 6 и с. Таким образом, по окончании строки 3 а указывает на 6, 6 — на г, с — на ~. 1099 12.4. Простой алгоритм анализа указателей Если проследовать по строкам 4-6, то после строки 4 выяснится, что а указывает только на ю'.
После строки 5 6 указывает на з, а после строки б с указывает на 1. и Приведенный выше анализ чувствителен к потоку, поскольку мы следуем за потоком управления и после каждой инструкции выясняем, на что может указывать каждая переменная. Другими словами, наряду с выяснением, какая информация о целях указателей "генерируется'* каждой инструкцией, мы также рассматриваем, какая информация о целях указателей "уничтожается". Например, инструкция Ь = с; уничтожает предыдущий факт "6 указывает на 1" и генерирует новое соотношение "6 указывает на то же, на что и с".
Нечувствительный к потоку анализ игнорирует поток управления, что по сути эквивалентно предположению, что все инструкции программы могут выполняться в произвольном порядке. При этом анализе вычисляется только одно глобальное отображение, указывающее, на что может указывать каждая переменная в любой точке выполнения программы. Если переменная может указывать на два разных объекта после двух разных инструкций программы, мы просто записываем, что она может указывать на два объекта. Другими словами, в анализе, нечувствительном к потоку, присваивание не уничтожает отношения указывания, а только их генерирует.
Для вычисления нечувствительных к потоку результатов мы многократно добавляем цели указателей для каждой инструкции, пока новые цели не перестанут обнаруживаться. Понятно, что отсутствие чувствительности к потоку существенно ослабляет результаты анализа, но при таком подходе снижается размер представления результатов и быстрее достигается сходимость алгоритма. Пример 12.23. Вернемся к примеру 12.22.
Строки 1 — 3 говорят нам, что а может указывать на 6, 6 может указывать на г, а с может указывать на ~'. После строк 4 и 5 и может указывать на 6 и 1, а 6 — на 1 и з', Анализ строки 6 дает нам, что с может указывать на 6, 1 и 2. Эта информация воздействует на строку 5, которая, в свою очередь, воздействует на строку 4. В конце концов мы делаем бесполезный вывод, что любой указатель может указывать на любой объект.
и 12.4.4 Формулировка с применением Ра1а1од Формализуем нечувствительный к потоку анализ целей указателей, основанный на рассмотренном выше материале. Пока что мы проигнорируем вызовы процедур и сконцентрируемся на четырех видах инструкций, которые могут влиять на значения указателей. 1. Созданиеобъекта. Ь~ Т ч = пем Т();.Даннаяинструкциясоздаетновый объект кучи, и переменная о может указывать на него. пой Глава ! 2. Межпроцедурный анализ 2. Инструкция копирования. ч = мг .
Здесь с и и — переменные. Инструкция делает переменную и указывающей на тот же объект кучи, на который указывает переменная ю, т.е. значение ш копируется в с. 3. Сохранение в лоле. ч. й = и!. Тип объекта, на который указывает с, должен иметь поле г" некоторого ссылочного типа. Пусть и указывает на объект кучи 6, а ш указывает на д. Данная инструкция делает поле )' обьекта 6 указывающим на д. Заметим, что переменная с остается при этом неизменной.
4. Загрузка поля. ч = и. г;. Здесь ю — переменная, указывающая на некоторый объект в куче, который имеет поле г", и г" указывает на некоторый объект кучи 6. Инструкция делает переменную с указывающей на 6. Заметим, что обращение к составному полю в исходном коде наподобие ч = и. й. д разбивается на две примитивные инструкции загрузки поля: Выразим наш анализ формально при помощи правил Рага!оя. Имеется только два 1РВ-предиката, которые мы должны вычислять.
1. рм (К Н) означает, что переменная Г может указывать на объект кучи Н. 2. 6ргз(Н, Г, С) означает, что поле г объекта кучи Н может указывать на объект кучи С. ЕРВ-отношения строятся на основе исходного текста программы. Поскольку положение инструкций в программе при нечувствительном к потоку анализе не имеет значения, в ЕРВ достаточно указать существование инструкций, имеющих определенный вид.
Далее мы сделаем удобное упрощение. Вместо определения ЕРВ-отношений для хранения информации, полученной из исходного текста программы, мы будем использовать заключенные в кавычки инструкции, указывающие ЕРВ-отношение или отношения, которые представляет данная инструкция. Например, "Н: Т 'г' = пои ТО" является ЕРВ-фактом, утверждающим, что в инструкции Н имеется присваивание, которое делает переменную И указывающей на новый объект типа Т. Мы полагаем, что на практике будет иметься соответствующее ЕРВ-отношение, которое будет заполнено основными атомами, по одному для каждой инструкции данного вида в программе. При таком соглашении все, что нам надо для написания Рага!оя-программы,— это по одному правилу для каждого из четырех типов инструкций. Такая программа показана на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
