А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 222
Текст из файла (страница 222)
Пример 12.12. Простым примером Ра!а!ой-программы является вычисление путей в графе, заданном его (ориентированными) ребрами, т.е. существует предикат езде (Х, У), который означает "существует ребро от узла Х к узлу У". Еще один предикат — рай (Х, У) — означает, что существует путь от узла Х к узлу У. Правила, определяющие пути, имеют следующий вид: езде (Х, У) рай (Х, У) в рай (Я, У) 1) рай (Х, У) 2) рай (Х, У) Первое правило гласит, что отдельное ребро является путем. Иначе говоря, если мы заменим переменную Х константой а, а переменную У вЂ” константой 6 и предикат е~48е (а, 6) истинен (т.е.
имеется ребро из узла п, в узел 6), то истинен и предикат рай (а, 6) (т.е. существует путь из узла а в узел 6). Второе правило гласит, что если существует путь из некоторого узла Х в некоторый узел 7, а также путь из узла Я в узел У, то существует путь из узла Х в узел У. Это правило выражает "транзитивное замыкание".
Заметим, что любой путь можно сформировать, беря ребра вдоль пути и многократно применяя правило транзитивного замыкания. Предположим, например, что истинны следующие факты (основные атомы): е фе (1, 2), еда (2, 3) и ефе (3, 4). Тогда можно воспользоваться первым правилом с тремя разными подстановками для вывода рай(1,2), рай(2,3) и рай(3,4).
Так, подстановка Х =- 1 и У = 2 приводит первое правило к виду рай (1, 2):— езде (1, 2). Поскольку езде (1, 2) истинно, мы получаем истинность рай (1, 2). Имея указанные три факта о предикате рай, можно несколько раз применить к ним второе правило. Если подставить Х = 1, У = 2 и У = 3, второе правило дает нам рай (1, 3): — рай (1, 2) а рай (2, 3).
Так как обе подцепи тела уже были выведены, нам известно, что обе они истинны, так что мы выводим и заголовок 1085 ! 2.3. Логическое представление потока данных рай (1, 3). Подстановка Х = 1, Я = 3 и У = 4 позволяет нам вывести заголовок рай (1, 4), т.е. мы выясняем, что существует путь из узла 1 в узел 4. и 12.3.3 Интенсиональные и экстенсиональные редикаты В программах Оа!а!о8 удобно различать два типа предикатов. !.
Предикаты экпненсиональной базы Донных (ехгепяопа! да1аЬазе — ЕОВ)— это предикаты, которые определяются априори, т.е. их истинные факты либо заданы отношением или таблицей, либо вытекают из смысла предиката (например, в случае предикатов сравнения). 2. Предикаты интенсиональной базы даллас (!п1епяопа! да!аЬазе — !ОВ) определяются только правилами.
Предикат должен быть либо ЕОВ-, либо 1ОВ-предикатом, причем может принадлежать только к одному из этих типов. Таким образом, любой предикат, находящийся в заголовке одного или нескольких правил, обязан быть !ОВ-преднкатом. Предикаты, находящиеся в теле правил, могут быть как ЕОВ-, так и !ОВ-предикатами. Так, в примере 12. 12 еда является ЕОВ-предикатом, а рай — 1ОВ-предикатом. Вспомним, что у нас имелось несколько фактов езде, таких как ег(де (1, 2), но факты рай выводились при помоши правил. При использовании Оа!а!о8-программ для выражения алгоритмов потоков данных ЕОВ-предикаты вычисляются из самого графа потока. !ОВ-предикаты выражаются при помощи правил, и задача потока данных решается путем вывода всех возможных !ОВ-фактов на основании правил и имеющихся ЕОВ-фактов. Пример 12.13.
Рассмотрим, каким образом в Оа!а!о8 можно выразить достигающие определения. Во-первых, имеет смысл работать на уровне инструкций, а не на уровне блоков, т.е. построение множеств дел и йП из базовых блоков будет интегрировано с вычислением самих достигающих определений. На рнс.
12.13 представлен типичный блок. Обратите внимание, что мы идентифицируем точки внутри блока, нумеруя их 0,1,...,п, где п — количество инструкций в блоке. 1-е определение находится "в точке" г; в точке 0 никаких определений нет. х = у+2 Ь1 ' *р=ц х=ч Рис.
12. 13. Базовый блок с точками между инструкциями 1086 Глава 12. Межпроцелурный анализ Точка в программе должна быть представлена парой (Ь, п), где Ь вЂ” имя блока, а п — целое число от 0 до количества инструкций в базовом блоке Ь. Наша формулировка требует двух ЕРВ-предикатов. 1. Предикат с~е1 (В, Х, Х) истинен тогда и только тогда, когда М-я инструкция в базовом блоке В может определять переменную Х. Например, на рис.
12.13 Ые1 (Ьы 1, х) истинно, Ые1'(Ьы 3, х) истинно и с1е1 (Ьы 2, У) истинно для каждой возможной переменной У, на которую в зтой точке может указывать указатель р. 2. Предикат зисс (В, Ю, С) истинен тогда и только тогда, когда базовый блок С является преемником базового блока В в графе потока и В содержит М инструкций, т.е. управление может быть передано из точки М базового блока В в точку 0 блока С. Предположим, например, что предшественником блока 61 на рис. 12.13 является блок Ьз, состоящий из пяти инструкций.
Тогда предикат зисс (Ьз, 5, 61) истинен. Имеется также один 1РВ-предикат и! (В, М, С, М, Х). Он истинен тогда и только тогда, когда определение переменной Х в М-й инструкции базового блока С достигает точки Х базового блока В. Правила, определяющие предикат Ы, показаны на рис. 12.14. 1) п1(В, Ж, В, Х, Х): — г1еЯВ, Ю, Х) 2) п$(В,г1,С,М,Х): — п1(В,Х вЂ” 1,С,М,Х) й с!е1(В,Х,У) й Х~ У 3) п1(В,О,С,М,Х): — п1(Р,М,С,М,Х) й зисе(Р, Х, В) Рис. 12.14. Правила лля преликата п! Правило 1 гласит, что если !У-я инструкция базового блока В определяет Х, то это определение Х достигает )1Г-й точки В (т.е.
точки, следующей непосредственно за инструкцией). Это правило соответствует концепции "йеп" в нашей ранней формулировке достигающих определений, основанной на теории множеств. Правило 2 представляет идею о том, что определение проходит через инструкцию, если оно не уничтожается ею, и что единственный способ уничтожения определения заключается в переопределении переменной со 100'Ь гарантией.
Де- !2.3. Логическое представление потока данных 1087 тальнее правило 2 гласит, что определение переменной Х из М-й инструкции блока С достигает точки )!! базового блока В, если а) оно достигает предыдущей точки )т' — 1 базового блока В и б) существует как минимум одна переменная У, отличная от Х, которая может быть определена в Ю-й инструкции В. Наконец, правило 3 выражает поток управления в графе. Оно гласит, что определение Х в М-й инструкции базового блока С достигает точки О базового блока В, если существует некоторый базовый блок Р с )т' инструкциями, такой, что определение Х достигает конца базового блока Р, а В является преемником базового блока Р.
и ЕРВ-предикат зисс из примера !2.13 может быть выведен из графа потока. Можно также получить из графа потока и предикат ЫеГ", если консервативно считать, что указатель может указывать на что угодно. Если мы хотим ограничить область указателя переменными соответствующего типа, то можно получить информацию о типах из таблицы символов и использовать меньшее отношение Нег". Один из вариантов состоит в том, чтобы сделать Ие2 ЕОВ-предикатом и определить его при помощи правил.
Эти правила будут использовать более примитивные ЕРВ-предикаты, которые могут быть определены из графа потока и таблицы символов. Пример 12.14. Предположим, что мы вводим два новых ЕРВ-предиката. 1. Предикат азз!дп (В, Д1,Х) истинен, если Ж-я инструкция базового блока В имеет Х в левой части. Заметим, что Х может быть переменной или простым выражением с 1-значением наподобие *р. 2. Предикат ггре(Х, Т) истинен, если типом Х является Т. Здесь Х, опять же, может быть переменной или простым выражением с 1-значением, а Т может быть любым выражением корректного типа.
Тогда мы можем записать правила для Ие1, делая его 1РВ-предикатом. На рис. 12.15 приведено расширение рис. 12.14 с двумя из возможных правил для Не!; Правило 4 гласит, что Ж-я инструкция базового блока В определяет Х, если Х присваивается Х-й инструкцией. Правило 5 говорит о том, что переменная Х может также быть определена л1-й инструкцией базового блока В, если эта инструкция выполняет присваивание *Р, а Х является любой переменной типа, на который указывает указатель Р.
Другие виды присваиваний требуют иных правил для Ые1: В качестве примера использования правил на рис. 12.15 для выводов еще раз рассмотрим базовый блок 6! на рис. 12.!3. Первая инструкция присваивает значение переменной х, так что ахилл (6!, 1, х) является ЕРВ-факгом. Третья инструкция также присваивает значение переменной х, так что аЫдл (6ы 3, х) является 1088 Глава 12.
Межпроцедурный анализ ! ) пИВ, Аг, В, Ю, Х): — йе)( В, )Х, Х) 2) пУВ, )'т'. С, ЛХ, Х): — ггИ,В, Х вЂ” 1. С, М, Х) й Нег'(В, Ю, У) й ХфУ 3) Ы(В,О,С,Л1, Х) : — и1(Р,Х,С,ЛХ,Х) й йвсс(Р. Ж, В) 4) г2еЯВ, Ж, Х): — аьаап(В, АГ, Х) 5) ЫеДВ,Ж,Х): — ахпдп(В,Л1,*Р) й гире(Х,Т) й ~уре(Р, *Т) Рис. 12.15. Правила для предикатов п1 и Ие! еще одним ЕРВ-фактом. Вторая инструкция выполняет косвенное присваивание через указатель р, так что третьим ЕРВ-факгом является азз18п (бы 2, *р), Правило 4 позволяет нам вывести с!лбы 1, х) и с!еДбп 3, х). Предположим, что р имеет тип указателя на целое число (*1пс), а х и у являются целочисленными переменными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
