А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 226
Текст из файла (страница 226)
12.21. Правило 1 гласит, что переменная Ъ' может указывать ПОЗ 12.4. Простой алгоритм анализа указателей на объект кучи Н, если инструкция Н представляет собой присваивание нового объекта переменной и. Правило 2 гласит, что если существует инструкция копирования тг = «! и И' может указывать на Н, то и может указывать на Н, 1) рь($;Н): — "Н: Т И = пен Т" 2) ргз(1;Н): — "Г' = И"' й ргх!И; Н) 3) лргз(Н,Г,С): — "КГ = И"' й р!кГИ',С) й рм1~; Н) 4) ргз($; Н): — "!' = И'.Р'" й р!зГИ',С) й йргзГС, Р; Н) Рнс.
12.21. Г!а!а!оя-программа для анализа указателей, нечувствительного к потоку Г!ранило 3 гласит, что если существует инструкция вида !Г. Р = !4 и И' может указывать на С, а и может указывать на Н, то поле г объекта Н может указывать на С. Наконец, правило 4 гласит, что если существует инструкция вида тГ = !4. Р и Иг может указывать на С, а поле Г объекта С может указывать на Н, то и может указывать на Н. Обратите внимание на взаимную рекурсию рж и Ьрм; при этом данная Гэа!а!оя-программа может быть вычислена любым из итеративных алгоритмов, рассматривавшихся в разделе 12.3.4. 12.4.5 Использование информации о типе Поскольку !ака — язык программирования, безопасный с точки зрения типов, переменные могут указывать только на типы, совместимые с объявленными. Например, присваивание объекта, принадлежащего к надклассу объявленного типа переменной, приведет к исключению времени выполнения.
Рассмотрим простой пример, показанный на рис. !2.22, где Я является подклассом Т. Если в данной программе значение р истинно, то будет сгенерировано исключение времени выполнения, поскольку а нельзя присваивать объект класса Т. Таким образом, статически можно заключить, что в силу ограничений, связанных с типами, а может указывать только на 6, но не на д. ПО2 Глава 12. Межпроцелуриый анализ Я а; Т Ь; з.й (р) ( д: Ъ = пещ Т(); е1зе Ь: Ь = пеы Я(); а=Ь; Рис. 12.22. 5ака-программа с ошибкой, связанной с типами Таким образом, мы вводим в наш анализ три Е(3В-предиката, которые отражают важную информацию о типах в анализируемом коде.
!. иТуре ($', Т) гласит, что переменная Ъ" объявлена как имеющая тип Т. 2. лТуре (Н, Т) говорит о том, что тип созданного объекта кучи Н вЂ” Т. Тип создаваемого объекта может не быть точно известен, если, например, объект возвращается методом. В таком случае консервативно предполагается, что тип объекта может быть любым. 3. азз(длаЫе (Т, 5) означает, что объект типа Я может быть присвоен переменной с типом Т. Эта информация в общем случае собирается из объявлений подтипов в программе, но сюда входит и информация о предопределенных классах языка. азя(дпаЫе (Т, Т) всегда истинно. Правила на рис. 12.21 могут быть изменены таким образом, чтобы можно было делать выводы, только если переменной присваивается объект кучи совместимого типа.
Модифицированные правила показаны на рис. 12.23. Первое изменение внесено в правило 2. Последние три подцели говорят нам, что заключение о том, что $" может указывать на Н, можно сделать, только если типы Т и Я, которые могут иметь переменная (~ и объект кучи Н, таковы, что объект типа 5 может быть присвоен переменной, которая является ссылкой на Т. Подобное дополнительное ограничение добавлено и к правилу 4. Заметим, что в правиле 3 дополнительных ограничений нет, поскольку все присваивания должны выполняться через переменные, типы которых уже проверены. Любое ограничение, связанное с типами, перехватывает один дополнительный случай, когда базовый объект представляет собой нулевую константу.
12.4.6 Упражнения к разделу 12.4 Упражнение 12.4.1. На рис. 12.24 л и д представляют собой метки, использующиеся для представления вновь создаваемых объектов, и не являются частью поз 12.4. Простой алгоритм анализа указателей 1) рм(Ъг, Н): — "Н: Т И = пеы Т" 2) ргв($; Н): — "1' = И'" й рм(Иг.,Н) й гТуреЯ,Т) й йТуре(Н, Я) й аЫилаб!е(Т, Я) 3) йрм(Н, Е, С): — "(г.Е = И'" й ргз(И;С) й ргз(Ъ', Н) 4) р(х(Ъ', Н): — "у' = Игр" й ргз(И', С) й йрйт(С,Г,Н) й иТуреЯ,Т) й 'лТуре(Н, Я) й аЫдлаЫе(Т, Я) Рис. 12.23.
Добавление к нечувствительному к потоку анализу указателей ограиичений, связанных с типами кода. Вы можете считать, что объект типа Т имеет поле у". Воспользуйтесь 13а(а1оя-правилами из данного раздела для вывода всех возможных фактов рм и лр1ж с; с.тя Рис. 12.24. Код к упражнению 12.4.1 ! Упражнение 12.4.2. Применение алгоритма из данного раздела к коду д: Т а = пем Т(); а = пеы Т(); Тс=а; Ь: Т а д:ть Т с а.й Ь.Т Т б пем Т(); пем Т(); а; Ь; 1104 Глава 12.
Межпроцедурный анализ приводит к выводу, что и а, и с могут указывать и на Ь, и на д. Если код будет иметь вид Та=пеиТ(); Ь: Т Ь = пеи Т()' Тс=Ь; то внимательное рассмотрение позволяет сделать вывод о том, что а не может указывать на Ь. Предложите внутрипроцедурный анализ потока данных, который может избежать неточности такого вида. ! Упражнение 12.4.3. Анализ из данного раздела можно сделать межпроцедурным, если моделировать вызов и возврат из процедуры так, как если бы это были операции копирования, как в правиле 2 на рис. 12.21. Иными словами, вызов копирует фактические параметры в соответствующие формальные, а возврат копирует переменную, в которой хранится возвращаемое значение, в переменную, которой присваивается результат вызова. Рассмотрите программу на рис.
12.25. а) Выполните нечувствительный анализ этого кода. б) Некоторые из сделанных в части а выводов оказываются "фальшивыми" в том смысле, что не представляют ни одного события, происходящего во время выполнения. Проблема связана с множественными присваиваниями переменной 6. Перепишите код, показанный на рис. 12.25, так, чтобы ни одна переменная не присваивалась более одного раза. Выполните анализ заново и покажите, что каждый выведенный факт рм и лрн осуществляется во время выполнения программы. с р(к х) ( Ь: Т а = пеи Т; а.Т = х; кекцхп а; чоЫ вахи() ( д: Т Ь = пеи Т1 Ь = р(Ь); Ь=Ь.Й; Рис.
12.25. Пример кода для анализа указателей 1105 ! 2.5. Контекстно-нечувствительный межпроцсдурный анализ 12.5 Контекстно-нечувствительный межпроцедурный анализ Теперь рассмотрим вызовы методов. Сначала поясним, как анализ целей указателей может использоваться для вычисления точного графа вызовов, который применяется при вычислении точных результатов целей указателей. Затем мы формализуем построение графа вызовов "на лету" и покажем, как для краткого описания анализа может использоваться Рага!ои 12.5.1 Влияние вызовов методов Влияние вызовов методов в 1ача, таких как х = у. п ( я ), на отношения указания может быть вычислено следующим образом.
1. Определяется тип вызываемого обьекта, который является объектом, на который указывает у. Предположим, что его тип — г. Пусть пз — метод с именем п в последнем надклассе г, в котором имеется метод с именем и. Заметим, что в общем случае выяснить, какой метод будет вызван, можно только динамически. 2. Формальным параметрам т присваиваются объекты, на которые указывают фактические параметры. Фактические параметры включают не только параметры, передаваемые непосредственно,но и сам вызываемый объект.
Каждый вызов метода присваивает вызываемый объект переменной с)тза.з Эти переменные с)ззв будут рассматриваться нами как нулевые формальные параметры методов. В вызове х = у. п(к) два формальных параметра: обьект, на который указывает переменная д и который присвоен переменной с)ттв, и объект, на который указывает и который присваивается первому объявленному формальному параметру пь 3. Объект, возвращаемый т, присваивается переменной, находящейся слева в инструкции присваивания.
В контекстно-нечувствительном анализе параметры и возвращаемые значения моделируются инструкциями копирования. Остается вопрос„как определить тип вызываемого объекта. Можно консервативно определить тип в соответствии с объявлением переменной; например, если объявленная переменная имеет тип г, то могут быть вызваны методы с именем п в подтипах г. К сожалению, если объявленная переменная имеет тип ОЬЗ ест, то потенциальными целевыми методами являются все методы с именем и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
