А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 219
Текст из файла (страница 219)
В примере 12.5 вызовы из точки с2 можно аппроксимировать строкой вызовов (с2. с4*, сб). Заметим, что при такой схеме даже для программ без рекурсии количество разных контекстов вызова может экспоненциально зависеть от количества процедур в программе. 12.1.4 Контекстно-чувствительный анализ на основе клонирования Еще один подход к контекстно-чувствительному анализу заключается в мысленном клонировании процедур, по одной для каждого уникального контекста, интересуюшего нас. Затем к клонированному графу вызовов можно применить контекстно-нечувствительный анализ. В примерах 12.6 и 12.7 показаны клонированные версии кода из примеров 12.4 и 12.5 соответственно.
В реальности клони- ровать код не требуется — можно просто использовать эффективное внутреннее представление для отслеживания результатов анализа каждого клона. Пример 12.6. Клонированная версия кода, представленного на рис. 12.5, показана на рис. !2.7.
Поскольку каждый контекст вызова работает со своим клоном, никакой путаницы не возникает. Например, 91 получает в качестве аргумента О и возвращает 1; д2 и 93 получают в качестве аргументов 243 и возвращают 244.с Пример 12.7.
Клонированная версия кода из примера 12.5 показана на рис. 12.7. Для процедуры а мы создаем клон для представления всех экземпляров д, впервые вызываемых из точек вызова с1, с2 и сз. В этом случае анализ может определить, что вызов в точке с1 возвращает 1 1в предположении, что он в состоянии вывести, что при и = 0 результат проверки н > 1 отрицательный). Однако этот анализ недостаточно хорош, чтобы получить константы для точек вызовов с2 и сз.
и 1070 Глава 12. Межпроцедурный анализ бог (1 = 0; 1 < п1 1++) ( Г1 = 01(0); 'с2 = д2(243)1 ГЗ = 03(243)1 Х(1) = Г1+Г2+Г31 с1: с2: сЗ: тпг д1 (1пг ч) гесцгп б1(ч)1 1пг д2 (1пг ч) ( гесцгп 12(ч); 1пс дЗ (1пс ч) ( гесцгп бЗ(ч)1 ) с4.1: с4.2: с4.3: тпс Й1 (1пг ч) ( гесцгп (ч+1); ) 1пГ й2 (тпрр ч) геГцгп (ч+1); ) 1пГ 13 (тпГ ч) ( гесцгп (ч+1)г' ) Рис. 12.7. Клонированная версия кода, представленного на рис. 12.5 12.1.5 Контекстно-чувствительный анализ на основе резюме Межпроцедурный анализ на основе резюме представляет собой расширение анализа на основе областей.
По сути, в анализе на основе областей каждая процедура представлена кратким описанием ("резюме"), которое инкапсулирует некоторое наблюдаемое поведение процедуры. Основная цель резюме — избежать повторного анализа тела процедуры в каждой точке, где эта процедура может быть вызвана. Рассмотрим сначала случай с отсутствием рекурсии. Каждая процедура моделируется как область с единой точкой входа, при этом все пары "вызывающая— вызываемая процедуры" описываются отношением "внешняя-внутренняя области".
Единственное отличие от внутрипроцедурной версии заключается в том, 1071 12.1. Базовые концепции айаг (1 = О; 1 < п; 1++) ( Т1 = д1(0)з Г2 = д2(243); сЗ = дЗ(243)з Х(1) = г1+г2+гЗз с1: с2: сЗ: 1пг д1 (1пг ч) ( Н (г>1) гегцгп д1(ч-1)1 ) е1ее ( гегцгп 11(ч)з с4. 1: с5.1: 1пг д2 (1пг ч) 1й (ч > 1) гегигп д2(ч-1)з ) е1ве ( гегпгп й2(ч)з с4.2: с5.2: 1пг дЗ (1пг ч) 1й (ч > 1) ( гегцгп дЗ(ч-1)з ) е1ее ( гегигп ЙЗ(ч)з с4.3: с5.3: 1пг й1 (1пг ч) ( гегигп (ч+1)' 1пг 12 (1пг ч) ( гесигп (ч+1); ) 1пГ йЗ (1пс ч) ( гегпгп (ч+1); Рис.
12.8. Клонированная версия кода, представленного на рис. 12.6 1072 Глава ! 2. Межпроцедурный анализ что в межпроцедурном случае область процедуры может быть вложена внутрь нескольких различных внешних областей. Анализ состоит из двух частей: 1. восходящая фаза, вычисляющая передаточную функцию для резюмирования действий процедуры; 2. нисходящая фаза, которая передает информацию вызывающей функции для вычисления результатов выполнения вызываемых процедур. Для получения полностью контекстно-чувствительных результатов информация от разных контекстов вызова должна распространяться вниз к отдельным вызываемым функциям. Для повышения эффективности (с понижением точности) информация от всех вызывающих функций может обьединяться с использованием оператора сбора, а затем передаваться вниз вызываемым функциям.
Пример 12.8. Для распространения констант каждая процедура резюмируется передаточной функцией, определяющей, как константы распространяются через тело этой процедуры. В примере 12.2 можно резюмировать г" как функцию, которая для данной константы с в качестве фактического параметра о возвращает константу с+ 1. На основе этой информации анализ может определить, что переменные ~1, С2 и ТЗ получают значения 1, 244 и 244 соответственно. Заметим, по этот анализ свободен от неточности из-за нереализуемых строк вызовов. Вспомним, что пример 12.4 расширяет пример 12.2 путем добавления функции д, которая вызывает функцию г".
Таким образом, можно заключить„что передаточная функция для д такая же, как и передаточная функция для г'. Так что мы вновь делаем вывод о том, что переменные ~1, ~2 и Г.З получают значения 1, 244 и 244 соответственно. Теперь рассмотрим значение параметра и функции Г в примере 12.2.
В качестве первого действия можно объединить результаты всех контекстов вызова. Поскольку о может иметь значение О или 243, можно просто заключить, что н не является константой. Это верный вывод, поскольку нет константы, которой можно бы было заменить и в коде. Если мы хотим достичь более точных результатов, то можем вычислить их для интересуюших нас контекстов. Для получения контекстно-чувствительного ответа информация должна передаваться вниз от рассматриваемого контекста. Этот шаг аналогичен нисходящему проходу в анализе на основе областей. Например, значение п равно О в точке вызова с1 и 243 — в точках вызова с2 и сЗ. Для получения преимуществ распространения констант внутри Г" следует зафиксировать это различие путем создания двух специализированных клонов: одного — для входного значения О, а второго — для значения 243, как показано на рис.
12.9. В конце примера 12.8 мы видим, что если мы хотим скомпилировать код в разных контекстах по-разному, то мы должны клонировать его. Отличие заключается 1073 12.1. Базовые концепции аког (1 = 0; 1 < и; 1++) г1 = ЙО(0); Г2 = 1243(243); сЗ = 1243(243); Х(1) = с1+с2+сЗ; с1: с2: сЗ: 1пг 10 (1пГ зг) ( гегигп (1); ) 1пГ 2243 (1пГ ч) ( гесигп (244); Рис. 12.9. Результат распространения всех возмож- ных константных аргументов в функции ) 12.1.6 Упражнения к разделу 12.1 Упражнение 12.1.1. На рис.
12.10 приведена программа на языке программирования С с двумя указателями на функции — р и 9. )т' — константа, которая может быть меньше или больше 1О. Заметим, что в результате в программе получится бесконечная последовательность вызовов, но в данном случае нас это волновать не должно. в том, что при подходе на основе клонирования оно выполняется до анализа, на основе строк вызовов. При использовании подхода на основе резюме клонирование выполняется после анализа, на основе его результатов.
Даже если клонирование не применяется, выводы подхода на основе резюме о результатах выполнения вызываемой процедуры делаются точно, без проблемы нереализуемых путей. Вместо клонирования функций можно прибегнуть к встраиванию кода. Встраивание обладает дополнительным эффектом устранения накладных расходов, связанных с вызовами процедур. Справиться с рекурсией можно путем вычисления решения с фиксированной точкой. При наличии рекурсии мы сперва находим сильно связанные компоненты графа вызовов. В восходящей фазе мы не посещаем сильно связанные компоненты ло тех пор, пока не будут посещены все их преемники. В случае нетривиального сильно связанного компонента мы итеративно вычисляем передаточную функцию для каждой процедуры компонента до достижения сходимости, т.е.
итеративно обновляем передаточные функции до тех пор, пока не достигнем итерации с отсутствием изменений. 1074 Глава 12. Межпроцедурный анализ а) Укажите все точки вызова программы. б) Укажите для каждой точки вызова, на что указывает р? На что указывает !)? в) Изобразите граф вызовов для данной программы.
! г) Опишите все строки вызовов для функций 1 и д. 1пс (*р)(1пс)1 з.пг (*Ч)(з.пг); 1пГ й(1пс 1) ( 1Й (1 < 10) (р = йЧ1 геГцгп (*Ч)(з.);) е1ве (р = йй; гегигп (*р)(з.);) 1пг д(з.пг 5) 1й (] < 10) (с( = йгз гегигп (*р)(5)1) е1ае (с! = йд; гесцгп (*Ч)(2)') нойс).звайп() ( ййз Ч = йяз (*Р)((*Ч)(!ч)) ) Рис. ! 2.10. Программа к упражнению 12.1.1 Упражнение 12.1.2. На рис. 12.11 приведена "тождественная функция" 1с(, возвращающая переданный ей аргумент.
Приведен также фрагмент кода, включающий ветвление с последующим суммированием х + у. а) Изучите код. Что вы можете сказать о значении г после выполнения данного кода? б) Постройте граф потока для данного фрагмента кода, рассматривая вызовы функции фс1 как поток управления. 1075 12.2.
Необходимость межпроцедуриого анализа в) Если применить к графу, построенному в предыдущем задании, анализ распространения констант, как в разделе 9.4, то какие константные значения будут найдены? г) Перечислите все точки вызова на рис. 12.11. д) Перечислите все контексты вызовов функции 1с1. е) Перепишите код на рис.
12.11 путем клонирования новой версии 1с1 для каждого контекста ее вызова. ж) Постройте граф потока вашего кода из предыдущего пункта, рассматривая вызовы функции 1с( как поток управления. з) Примените анализ распространения констант к полученному в предыдущем пункте графу потока. Какие константные значения найдены в этот раз? 1пс Ы(1пс х) ( хесцхп х') з.т (а == 1) ( х = Ы(2)р у = Ы(3); ) е1ве х = 1с1(3); у = Ы(2); ) г =х+у; Рис. 12.11. Фрагмент кода к упражнению 12.1.2 12.2 Необходимость межпроцедурного анализа Получив представление о том, насколько сложен межпроцедурный анализ, рассмотрим важную проблему — когда и зачем он может потребоваться.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
