А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 218
Текст из файла (страница 218)
При более аккуратном анализе программы обнаруживается, что указатель рй в функции шафп становится равным гип2, а затем в функции йип2 ему присваивается значение йип1. Никаких иных присваиваний указателю рй в программе нет, так что, в частности, указатель рй не может указывать на функцию азайп. В результате получается тот же граф вызовов, приведенный на рис. 12.2, ц.
После еще более точного анализа можно сказать, что точка сЗ вЂ” единственное место, где рй указывает на йип2, поскольку этому вызову непосредственно предшествует присваивание соответствующего значения указателю рй. Аналогично в точке с2 единственное значение, которое может принимать указатель рй,— это йип1. Поскольку единственный способ попасть в функцию йип1 — вызов 1064 Глава 12. Межпроцедурный анализ б) а) Рис.
! 2.2. Графы вызовов для кода на рис. 12.1 из функции йцп2, а в самой функции йцп1 значение рй не изменяется, в этой функции глобальный указатель рй всегда указывает на йцп1. В частности, в точке с1 мы можем быть уверены в том, что рй указывает на йцп1. Таким образом, на рис. 12.2, б приведен более точный, корректный граф вызовов. Б В общем случае наличие ссылок или указателей на функции или методы требует от нас статической аппроксимации потенциальных значений всех параметров процедур, указателей на функции и типов объектов, получающих сообщения. Для выполнения точной аппроксимации требуется применение межпроцедурного анализа. Этот анализ итеративен и начинается со статически определяемого целевого кода. При обнаружении нового целевого кода анализ добавляет в граф вызовов новые ребра и повторяет выявление нового целевого кода, пока данный процесс не сойдется.
12.12 Чувствительность к контексту Межпроцедурный анализ очень сложен еще и потому, что поведение каждой процедуры зависит от контекста, в котором она вызвана. В примере 12.2 для иллюстрации важности чувствительности к контексту рассматривается задача межпроцедурного распространения констант в небольшой программе. Пример 12.2. Рассмотрим фрагмент программы на рис. 12.3. Функция ) вызывается в трех точках: с1, с2 и сЗ. На каждой итерации в точке с1 как фактический параметр передается константа О, а в точках с2 и сЗ вЂ” константа 243; возвращаются соответственно константы 1 и 244.
Таким образом, функциями в каждом 1065 12.1. Базовые концепции контексте вызывается с передачей ей константного значения, но это значение за- висит от контекста. аког (1 = 0; 1 < и; 1++) ( с1 = й(0)1 ~2 = й(243); сЗ = й(243)1 Х[1) = Г1+Г2+Гзз с1: с2: сЗ: 1пс Г (Бпс зг) ( гесцгп (зг+1); ) Рис. 12.3, Фрагмент программы, иллюстрирующий необходимость контекстно-чувстви- тельного анализа Как мы увидим, сказать, что переменным с1, с2 и сЗ (а значит, и Х (з)) присваиваются константные значения, невозможно до тех пор, пока не будет выяснено, что прн вызове в контексте с1 функция у возвращает значение 1, а в двух остальных контекстах — значение 244.
После простейшего наивного анализа можно заключить, что (' может возвращать в любом вызове либо 1, либо 244. е Один простейший, но очень неточный подход к межпроцедурному анализу, известный как контекстно-нечувствитезьный анализ (соп(ех1-(наела(1(уе апа1уяа), заключается в рассмотрении каждой инструкции вызова и возврата как операции безусловного перехода.
Мы создаем надграф потока управления, в котором, помимо обычных ребер внутрипроцедурных потоков управления, имеются дополнительные ребра, соединяющие 1. каждую точку вызова с началом вызываемой в ней процедуры; 2. инструкции возврата с точками вызова.' 'Строго говоря, возврат выполняется в точку, непосредственно следующую за точкой вызова. Добавляются инструкции присваивания каждого фактического параметра соответствующему формальному параметру, а также присваивания возвращаемого значения переменной, получающей результат. Затем можно применить стандартный анализ, предназначающийся для использования в процедуре, к надграфу потока управления для поиска контекстно-нечувствительных межпроцедурных результатов.
При своей простоте такая модель абстрагируется от важных взаимоотношений между входными и выходными значениями в вызовах процедур, что приводит к неточности такого анализа. ~йбб Глава 12. Межпроцедурный анализ Пример 12.3. На рис. 12.4 показан надграф потока управления для программы на рис. 12.3.
Блок Ва представляет собой функцию 1. Блок Вз содержит точку вызова с1; в нем формальному параметру е присваивается значение 0 и выполняется переход в начало функции г", в блок Ва. Аналогично блоки В» и Вз представляют точки вызовов с2 и сЗ соответственно. В блоке В», который достигается из конца функции ~ (блок Ва), возвращаемое функцией значение присваивается переменной с1. Затем формальный параметр и устанавливается равным 243, и путем перехода к блоку Ва выполняется новый вызов функции ~. Обратите внимание на отсутствие ребер от блока Вз к блоку В».
Управление переходит от блока Вз к блоку В» через функцию 1. в, Рис. 12.4. Граф потока управления для кода на рис. 12.3, получающийся прн рассмотрении вызовов функций в качестве потока управления Блок Вз подобен блоку В». Он получает возвращаемое значение от функции г", присваивает его переменной с2 и выполняет третий вызов функции г". Блок Вт представляет возврат из третьего вызова функции ~ и присваивание значения элементу массива Х 11~.
1067 12.1, Базовые концепции 12.1.3 Строки вызовов В примере 12.2 контексты отличались точками вызова процедуры ('. В общем же случае контекст вызова определяется содержимым всего стека вызовов. Будем говорить о строке точек вызова в стеке как о строке вызовов (сай з1пп8). Пример 12.4. На рис. 12.5 приведен немного измененный код, показанный на рис. 12.3. Здесь вызовы функции ( заменены вызовами функции д, которая вызывает 1' с тем же аргументом. Так у нас появляется еще одна точка вызова с4, в которой функция д вызывает функцию (. Имеется три строки вызовов функции )': (с1, с4), (с2, с4) и (сЗ, с4).
Как видите, в данном примере значение с в функции ( зависит не от последней точки вызова с4 в строке вызовов; оно определяется первым элементом этой строки. е аког (1 = 0; 1 < п; 1++) ( с1 = 9(О); гг = 9(243); ГЗ = 9(243); Х[11 = с1+сг+сЗ; с1: с2: сЗ: 1пс 9 (тпс ч) ( гегцгп й(ч)р с4: 1пг й (1пс ч) ( гесцгп (~г+1); ) Рис. 12.5. Фрагмент программы, иллюстрирующий строки вызовов В примере 12.4 демонстрируется, что важная для анализа информация может быть внесена ранними элементами цепочки вызовов.
Фактически иногда для Если рассматривать рис. 12.4 как если бы это был граф потока единой процедуры, то можно заключить, что при переходе к блоку Ва переменная н может иметь значение 0 или 243. Таким образом, наибольшее, что можно сказать о значении гесча1, — что оно может быть равным либо 1„либо 244. Значит, Х [() должно принимать одно из следующих значений: 3, 246, 489 или 732. В отличие от контекстно-нечувствительного анализа, контекстно-чувствительный анализ разделяет результаты вызова в каждом контексте и дает интуитивный ответ, описанный в примере 12.2: переменная г1 всегда равна 1, переменные сг и тЗ всегда равны 244, а Х ((] — 489.
а 1068 Глава 12. Межпроцедурный анализ получения максимально точного ответа необходимо рассматривать всю строку вызовов, как показано в примере 12.5. Пример 12.5. В этом примере иллюстрируется, как возможность неограниченного рассмотрения строк вызовов позволяет получать более точные результаты. На рис. 12.6 мы видим, что если д вызывается с положительным значением с, то д рекурсивно вызывается с раз. Каждый раз при вызове функции д значение ее параметра о уменьшается на 1. Таким образом, значение параметра о функции д в контексте строки вызова с2 (с4)" равно 243 — п.
Результатом работы функции д, таким образом, является увеличение нуля или любого отрицательного аргумента на 1 и возврат 2 для любого аргумента, равного 1 или больше. с1: с2: сЗ: з.пт. ц (з.пс ч) 1й (ч>1) ( гегцгп п(ч-1)г ) е1ве ( геСигп й(ч); с5: 1пт. й (1пт. ч) ( гекцгп (ч+1); ) Рнс. 12.6. Рекурсивная программа, требуюшая анализа всей строки вызовов Для функции г" имеются три возможные строки вызовов. Если работа начинается с вызова в точке с1, то функция д немедленно вызывает функцию г', так что одной из таких строк является строка (с1, с5).
Если начать с точки с2 или сЗ, то функция д вызывается 243 раза, после чего вызывается функция )'. Соответствующие строки вызова — (с2,г4,с4,..., с5) и (сЗ,с4,с4,...,с5), в каждой из которых имеется по 242 точки с4. В первом из этих контекстов значение параметра о функции г' равно О, в то время как в остальных двух контекстах это значение — 1. Б При проектировании контекстно-чувствительного анализа главным фактором должна являться его точность. Например, вместо рассмотрения полных строк вы- аког (з. = 11 г2 ТЗ Х [ 3.
) ) 0; 1 < п; з.++) ( п(О); д(243); д(243); с1+с2+сЗ; 1069 12.1. Базовые концепции зовов для определения контекста мы можем ограничиться только Й последними точками вызовов. Такой метод известен как й-ограниченный контекстный анализ. Контекстно-нечувствительный анализ представляет собой частный случай йограниченного контекстно-чувствительного анализа при к = О.
Все константы в примере 12.2 могут быть найдены с использованием 1-ограниченного анализа, а в примере 12.4 — при помощи 2-ограниченного анализа. Однако в примере 12.5 никакой Й-ограниченный анализ не в состоянии найти все константы, если константы 243 будут заменены двумя разными произвольно большими константами. Вместо выбора фиксированного значения )г для всех ациклических строк вызовов (т.е. строк, в которых отсутствуют рекурсивные циклы) следует добиваться полной контекстной чувствительности. Чтобы ограничить количество различных анализируемых контекстов, в случае строк вызовов с рекурсией можно свернуть все рекурсивные циклы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
