А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 224
Текст из файла (страница 224)
Формальное требование имеет следующий вид. Мы должны иметь возможность разделить ЮВ-предикаты на страты, так что, если имеется правило с заголовком р и подцелью вида иОТ д (...), д — либо ЕПВ-, либо ЮВ-предикат в более низкой по сравнению с р страте. Если этот принцип выполняется, то страты могут быть вычислены в восходящем порядке при помощи алгоритма 12.15 или !2.!8, после чего можно рассматривать отношения ЮВ-предикатов данной страты, как будто это ЕРВ-предикаты для вычисления более высоких страт. Однако при нарушении указанного принципа итеративный алгоритм может не достичь сходимости, что проиллюстрировано следующим примером. Пример 12.20. Рассмотрим программу Ра!а!ой, состоящую из одного правила: р(Х): — е(Х) й иОТ р(Х) Предположим, что е — ЕРВ-предикат, причем истинно только е (1). Истинно ли р (1)2 Данная программа не стратифицирована.
В какую бы страту мы не поместили предикат р, его правило будет содержать подцель, которая представляет собой отрицание и включает ЮВ-предикат (сам предикат р), располагающийся, само собой разумеется, не в более низкой страте, чем р. Если применить итеративный алгоритм, начиная с В„= О, то первым ответом будет "Нет; р(1) не истинно". Но первая итерация позволит нам вывести р(1), поскольку и е(1), и иОТ р(1) истинны.
Вторая итерация вновь приведет нас к выводу, что р (1) ложно (на этот раз подцель 1чОТ р(1) будет ложна). Третья итерация вновь делает р (1) истинным, четвертая — ложным, и т.д. Мы вынуждены сделать вывод, что данная нестратифицированная программа не имеет смысла, и не рассматривать ее как корректную. и 12.3.7 Упражнения к разделу 12.3 ! Упражнение 12.3.1. Здесь мы рассмотрим более простой по сравнению с примером 12.13 анализ достигающих определений.
Предположим, что каждая инструкция сама по себе является блоком и изначально определяет ровно одну переменную. ЕРВ-предикат ргед(1, 1) означает, что инструкция 1 является предшественницей инструкции 1. ЕРВ-предикат Ие3лея (1, Х) означает, что переменная, определяемая инструкцией 1, — Х. Мы будем использовать ЮВ-предикаты т (1, Р) и ош(1, Р), означающие, что определение Р достигает соответственно начала или конца инструкции 1. Заметим, что определение фактически является номером инструкции.
На рис. 12.19 приведена Ра1а!ой-программа, которая выражает обычный алгоритм вычисления достигающих определений. 1094 Глава 12. Межпропедурный анализ 1) ?пП(1, Р): — с(елпея(1, Х) й г?ебпез(Р, Х) 2) оиг(1, 1): — Иейпез(1, Х) 3) оиг(1,Р): — 1п(1,Р) й 1зОз Ы11(1,Р) 4) !п(1, Р): — оиг(1, Р) й ргеИ(,1, 1) Рнс. 12.19. Рага!оячзрограмма для простого анализа достигающих определений Правило 1 гласит, что инструкция уничтожает саму себя, правило 2 — что инструкция входит в собственное "выходное множество". Правило 3 является обычной передаточной функцией, а правило 4 позволяет слияние, так как 1 может иметь несколько предшественников.
Ваша задача — модифицировать правила для обработки распространенной ситуации неоднозначных определений, например присваиваний посредством указателя. В этой ситуации с(ейпез (1,Х) может быть истинно для нескольких различных Х и одного 1. Определение лучше всего представить парой (Р, Х), где Р— инструкция, а Х вЂ” одна из переменных, которая может быть определена в Р. В результате !и и оиг станут трехаргументными предикатами; например, !и (1, Р, Х) означает, что (возможное) определение Х в инструкции Р достигает начала инструкции 1. Упражнение 12.3.2.
Напишите Раза!оя-программу, аналогичную приведенной на рис. 12.19, для вычисления доступных выражений. В дополнение к предикату г?е1!лез используйте предикат ега! (1, Х, О, т'), который гласит, что инструкция 1 вычисляет выражение ХОК Здесь Π— оператор в выражении, например +. Упражнение 12.3.3. Напишите Ра!а!оя-программу, аналогичную приведенной на рис.
12.19, для вычисления активных переменных. В дополнение к предикату ае1?пе5 воспользуйтесь предикатом ияе(1, Х), который гласит, что инструкция 1 использует переменную Х. Упражнение 12.3.4. В разделе 9.5 мы определили вычисления потока данных, включающие шесть концепций: ожидаемого, доступного, самого раннего, откладываемого, самого позднего и используемого выражений. Предположим, что мы написали Ра!а!оя-программу для определения каждой из них в терминах ЕРВ-концепций, выводимых из программы (например, из информации йеп и к!1!), и остальных из данных шести концепций. Какие из концепций зависимы от других? Какие из зависимостей используют отрицания? Является ли полученная Ра!а!ояпрограмма стратифицированной? 1095 12.4. Простой алгоритм анализа указателей Упражнение 12.3.5. Предположим, что ЕПВ-предикат ес!де (Х, У') состоит из следующих фактов: еНйе (1, 2) еда (2, 3) ефе (3, 4) езде (4, 1) ес)де (4, 5) ес!де (5, 6) а) Смоделируйте Вага!ой-программу из примера 12.12 для этих данных с использованием простой стратегии вычисления из алгоритма 12.15.
Укажите, какие факты рагл выявляются на каждом цикле вычислений. б) Смоделируйте Па!а!ой-программу из примера 12.12 для этих данных с использованием инкрементной стратегии вычисления из алгоритма 12.18. Укажите, какие факты рай выявляются на каждом цикле вычислений. Упражнение 12.3.6. Правило р(Х, 1'): — д(Х, Е) ь г(Е, Иг) й 1чОТ р(Иг, 1') является частью большей Па!а!ой-программы Р. а) Укажите заголовок, тело и подцели данного правила. б) Какие предикаты определенно являются 10В-предикатами программы Р? ! в) Какие предикаты определенно являются ЕПВ-предикатами программы Р? г) Является ли это правило безопасным? д) Стратифицирована ли программа Р? Упражнение 12.3.7.
Преобразуйте правила на рис. 12.14 в инкрементную форму. 12.4 Простой алгоритм анализа указателей В этом разделе мы начнем рассмотрение очень простого, нечувствительного к потоку, анализа псевдонимов указателей в предположении отсутствия вызовов процедур. В последующих разделах мы покажем, как работать с процедурами — сначала контекстно-нечувствительно, а затем контекстно-чувствительно.
Чувствительность к потоку добавляет массу сложностей; и она не слишком важна для языков программирования наподобие 1ата, в которых наблюдается тенденция к наличию методов небольшого размера. Фундаментальным вопросом в анализе псевдонимов указателей является вопрос о том, может ли пара данных указателей быть псевдонимом. Один из способов ответить на этот вопрос состоит в вычислении каждого указателя для получения ответа на вопрос "На какой объект может указывать данный указатель?" Если два указателя могут указывать на один и тот же объект, указатели могут быть псевдонимами.
1096 Глава 12. Межпропедурный анализ 12.4.1 Сложность анализа указателей Особенно сложен анализ указателей для С-программ, поскольку в них над указателями могут выполняться произвольные вычисления. Фактически в С-программе указателю может быть присвоено считанное целочисленное значение, что делает указатель потенциальным псевдонимом для всех указателей в программе.
Указатели в 1ача, известные как ссылки, существенно проще. Над ними не могут выполняться никакие арифметические операции, и указатели могут указывать только на начало объекта. Анализ псевдонимов указателей должен быть межпроцедурным. Без этого следует полагать, что любой вызванный метод может изменить содержимое всех доступных переменных-указателей, делая тем самым внутрипроцедурный анализ неэффективным.
Языки, в которых разрешены косвенные вызовы процедур, вносят дополнительный вклад в сложность анализа указателей. В языке программирования С можно вызвать функцию косвенно, путем вызова разыменованного указателя на функцию. Перед тем как приступить к анализу вызываемой функции, мы должны знать, на что именно может указывать данный указатель на функцию. Понятно, что после анализа вызываемой функции могут обнаружиться новые функции, на которые может указывать рассматриваемый указатель, так что процесс анализа должен быть итеративным. В то время как в С большинство функций все же вызываются непосредственно, виртуальные методы 1ача приводят к тому, что многие вызовы оказываются косвенными.
В случае некоторого вызова х.вз( ) в 1ача-программе может иметься множество классов, в которых есть метод т и которым может принадлежать объект х. Чем более точны наши знания о типе х, тем точнее оказывается граф вызовов. В идеальном случае во время компиляции можно определить точный тип х, а значит, точно указать, какой метод т будет вызван. Пример 12.21.
Рассмотрим последовательность инструкций 1ача: ОЬЗесс о; о = пеы Ясгтпд()г и = о.)тав)тСог)е(); Здесь о объявлено как ОЬз есс. Без анализа, на что именно ссылается о, в качестве возможных целевых методов должны рассматриваться все методы с именем )тав)тсос(е для всех классов.
Знание же о том, что о указывает на объект типа Яск1пд, сузит результаты межпроцедурного анализа до единственного метода 1епдСЬ, объявленного в классе ЗСхтпд. а Для сокращения количества целевых методов можно применить аппроксимацию. Например, можно статически определить, какие типы объектов создаются, 1097 12.4. Простой алгоритм анализа указателей и ограничиться только их анализом. Можно быть и более точным, если получится строить граф вызовов "на лету" на основе выполняемого одновременно анализа, на что именно указывают указатели. Более точные графы вызовов приводят не только к более точным результатам, но и существенно сокращают время, затрачиваемое на выполнение анализа.
Такой анализ целей указателей достаточно сложен. Это не одна из тех "простых" задач потока данных, когда достаточно смоделировать проход по циклу инструкций. При обнаружении новой цели указателя все инструкции, присваивающие значение этого указателя другому, должны быть проанализированы заново. Для простоты мы сосредоточимся, в основном, на языке программирования зача.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
