А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 227
Текст из файла (страница 227)
В реальных программах, использующих Вспомним, что переменные различаются методами, к которым оии принадлежат, так что имеется много переменных Спъа, но а каждом методе программы — только одна такая переменная. 1(Об Глава 12. Межпроцсдурный анализ иерархии объектов и включающих много больших библиотек, такой подход может привести к множеству ложных целей вызова, замедляя анализ и делая его менее точным. Чтобы вычислить цели вызова, нам надо знать, на что именно может указывать переменная; но пока мы не знаем цели вызова, мы не можем найти все, на что указывают переменные. Такое рекурсивное соотношение требует обнаружения целей вызовов "на лету" прн вычислении множества целей указателя.
Анализ продолжается до тех пор, пока на очередной итерации мы не сможем обнаружить ни новые цели вызовов, ни новые отношения указания. Пример 12.24. В коде на рис. 12.26 г является подтипом а, который, в свою очередь, является подтипом 1. Если использовать только информацию из объявлений типов, а . п ( ) может вызывать любой из трех объявленных методов с именами и, поскольку а и г являются подтипами объявленного типа а — (. Кроме того, после строки 5 а может указывать на объекты д, Ь и (. с1азз с ( 1) сз: с п() ( гегцгп ) с1азв в ехГепс)в Г 2) )з: Г п() ( гегцгп ) с1азз г ехгепс(в в 3) з.: г п() ( гесцгп ) пеи г(); ) ( пеи з(); ) ( пеи г(); ) лзазп () ( 4) 3„ .Г а = пеы с(); 5) а = а„п(); Рис.
12.2б. Вызов виртуального метода Анализируя отношение указывания, мы сначала определяем, что а может указывать на ) — объект типа 1. Таким образом, целью вызова является метод, объявленный в строке 1. Анализируя строку 1, мы определяем, что а может также указывать на д, объект типа г. Таким образом, целью вызова может быть метод, объявленный в строке 3, а и может указывать на ( — другой объект типа г. Поскольку новых целей вызова нет, анализ завершается без рассмотрения метода, объявленного в строке 2, и без заключения о том, что а может указывать на 6.
с 1107 12.5. Контекстно-нечувствительный межпроцедурный анализ 12.5.2 Построение графа вызовов в Ра1а1ор Чтобы сформулировать правила Оага!оя для контекстно-нечувствительного межпроцедурного анализа, мы вводим три ЕОВ-предиката, каждый из которых легко получается из исходного кода. !. асгиа! (Я, 1, (г) гласит, что à — 1-й фактический параметр, использованный в точке вызова Я. 2.
~огта!(М,1, и) гласит, что и — 1-й формальный параметр, объявленный в методе ЛХ. 3. с!за(Т, Л!, М) гласит, что М вЂ” метод, вызываемый, когда вызывается метод Н вызываемого объекта типа Т (сЬа — сокращение от "с1аьа Ыегагс(зу апа!уз)з", "анализ иерархии классов"), Каждое ребро графа вызовов представлено 1ПВ-предикатом зпго!гет При обнаружении новых ребер графа вызовов создаются новые отношения указания в качестве передаваемых параметров и возвращаемых значений. Все это подытожено правилами, приведенными на рис. 12.27.
1) !лго/гез( э', М) "я: )г.!у(...)" й рге(~;Н) й !зТуре(Н,Т) й с!за(Т, Л!, ЛХ ) 2) ргз(1; Н): — тмз!гез(Б, М) й !огта1(М,1, 1') й асгиа!(Я,1, И') й рге(И', Н) Рнс. 12.27. 1Зага!од-программа для построения графа вызовов Первое правило вычисляет цель точки вызова„т.е.
"Я: 1'.1ч' (...)" гласит, что существует точка вызова с меткой Я, которая вызывает метод с именем Х обьекта, на который указывает и. Подцепи говорят нам, что если Г может указывать на обьекг кучи Н типа Т, а М вЂ” метод, использованный при вызове Лг для объекта типа Т, то точка вызова Я может вызывать метод ЛХ. Второе правило гласит, что если точка Я может вызывать метод М, то каждый формальный параметр М может указывать на то, на что указывает соответствующий фактический параметр в данной точке вызова. Правило для обработки возвращаемых значений остается читателю в качестве упражнения. 1108 Глава!2.
Межпроцедурный анализ Объединение этих двух правил с правилами, поясненными в разделе 12.4, создает контекстно-нечувствительный анализ целей указателей, который использует вычисляемый "на лету" граф вызовов. Этот анализ имеет побочный эффект, заключающийся в построении графа вызовов с применением контекстно-нечувствительного и чувствительного к потоку анализов целей указателей.
Этот граф вызовов значительно более точен, чем граф, вычисленный на основе только лишь объявлений типов и синтаксического анализа. 12.5.3 Динамическая загрузка и отражение Языки программирования наподобие 1ача позволяют выполнять динамическую загрузку классов. Проанализировать все возможные выполнения кода невозможно, а следовательно, невозможно статически обеспечить консервативное приближение графов вызовов или псевдонимов указателей.
Статический анализ в состоянии предоставить лишь приближение, основанное на анализе кода. Вспомним, что все описанные здесь анализы могут быть применены на уровне байт-кода 1ача и, таким образом, не требуют изучения исходного кода. Эта возможность особенно важна в связи с использованием 1ача-программами множества библиотек. Даже если считать, что анализируется весь выполнимый код, все равно имеется еще одна сложность, делающая консервативный анализ невозможным: отражение (гейесбоп). Отражение позволяет программе динамически определять типы создаваемых объектов, имена вызываемых методов, а также имена полей, к которым выполняется обращение. Имена типа, метода и поля могут быть вычислены или получены из пользовательского ввода, так что в общем случае единственная возможность приближения — считать возможным все.
Пример 12.25. Приведенный ниже код показывает распространенное примене- ние отражения: 1) Ятгепд с1аззМапзе- 2) С1авз с = С1авз.йогМате(с1аззМате); 3) ОЪЗесГ о = с.пеы1пзКапсе(); 4) Т с = (Т) о; Метод йогМаве в библиотеке С1авз принимает строку, содержащую имя класса, и возвращает класс. Метод пеы1пзбапсе возвращает экземпляр этого класса. Вместо того чтобы оставить объект о типа ОЪз есс, этот объект приводится к надклассу всех ожидаемых классов Т. а Многие большие приложения 1ача применяют отражения, при этом обычно используя распространенные идиомы наподобие показанной в примере ) 2.25. Если приложение не переопределяет загрузчик класса, то сказать, какой класс имеет объект, можно при знании значения с1аззМанзе.
Если значение с1аввМаве 1!09 12.6. Контекстно-чувствительный анализ указателей определяется в программе, то, поскольку строки в 1ача неизменяемы, знание того, на что указывает с1аваыате, дает нам имя класса. Этот метод представляет собой еще одно использование анализа целей указателей.
Если значение с1авв1яапю основано на пользовательском вводе, то анализ целей указателей может помочь выяснить, где именно вводится это значение, так что разработчик может ограничить его область видимости. Аналогично можно воспользоваться инструкцией приведения типа (строка 4 в примере 12.25) для аппроксимации типа динамически создаваемых объектов. В предположении, что обработчик исключений приведения типа не переопределен, объект должен принадлежать подклассу класса '1', 12.5.4 Упражнения к разделу 12.5 Упражнение !2.5.1.
Для кода на рис. 12.26 а) постройте ЕРВ-отношения ас~иа?,?огти! и сйа; б) сделайте все возможные выводы о фактах рм и Ьргж ! Упражнение 12.5.2. Каким образом добавить дополнительные предикаты и правила к ЕРВ-предикатам и правилам из раздела 12.5.2, чтобы учесть тот факт, что если вызов метода возврашает объект, то переменная, которой присваивается результат вызова, может указывать на то, на что указывает переменная, храняшая возврашаемое значение? 12.6 Контекстно-чувствительный анализ указателей Как говорилось в разделе !2.1.2, контекстная чувствительность может существенно повысить точность межпроцедурного анализа. Мы говорили о двух подходах к межпроцедурному анализу, основанных на клонировании (раздел 12.!.4) и на резюме (раздел 12.1.5).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
