А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 165
Текст из файла (страница 165)
Такая же аргументация применима к любым другим множествам 8еп-к111-функций. 811 9.7. Анализ на основе областей Замыкание Если ! представляет собой передаточную функцию цикла, то !" представляет собой влияние п проходов по циклу. В случае, когда количество итераций неизвестно, мы вынуждены считать, что цикл может выполняться О или больше раз.
Передаточную функцию такого цикла мы представим как !' — замыкание 1, определяемое как У* = Л ~" Заметим, что 1с должно быть тождественной функцией, поскольку она представляет собой влияние нулевого количества проходов по циклу, т.е. при отсутствии перемещения из входного узла. Если 7 представляет тождественную передаточную функцию, то можно записать 1*=ГЛ Л !" Предположим, что передаточная функция ! в структуре достигающих определений имеет множества Пеп и Ы1. Тогда (х) = 1(!(х)) = = — дел 0 ((Пеп 0 (х — 1аП)) — ЙП) = = дел 0 (х — Ы1) (х) = 1(! (х)) = = Пеп 0 (х — 1аП) И так далее: любая функция !" (х) имеет вид 8еп о (х — Ы1).
Таким образом, проход по циклу не влияет на передаточную функцию вида 8еп-'и1!1. Итак, (х) = 1 Л ! (х) Л ! (х) Л ... = = х 0 (деп 0 (х — ЙП)) = =дел 0х Иначе говоря, множества ееп и Ы1 для 1* представляют собой яеп и О соответственно. Интуитивно понятно, что поскольку можно вообще миновать цикл, все достигающие определения из множества х будут достигать входа в цикл. Во всех последующих итерациях достигающие определения включают таковые из множества Пеп.
9.7.5 Алгоритм анализа на основе областей Приведенный далее алгоритм решает задачу анализа потока данных в прямом направлении на приводимом графе потока в соответствии с некоторой структурой, удовлетворяющей предположениям из раздела 9.7.4. Вспомним, что 1па„~п ) 812 Глава 9. Машинно-независимые оптимизации и ~п о„,1д1 обозначают передаточные функции, которые преобразуют значения потока данных на входе в область Л в корректные значения на входе в подобласть Л' и на выходе из блока В соответственно.
Алгоритм 9.49. Анализ на основе областей Вход: структура потока данных со свойствами, изложенными в разделе 9.7.4, и приводимый граф потока С. Выход: значения потока данных пч [В] для каждого блока В в С. Метод: выполняем следующие действия. 1. Используем алгоритм 9.48 для построения восходящей последовательности областей С, скажем, Л|, Лз,..., Л„, где ˄— область верхнего уровня.
2. Выполняем восходящий анализ для вычисления передаточных функций, которые подытоживают влияние выполнения области. Для каждой области Л|, Лз,..., Л в восходящем порядке выполняем следующее. а) Если Л представляет собой область-лист, соответствующую блоку В, то положим ~па„1п1 = 1 и 1л ц,1в1 = 1в — передаточной функции, связанной с блоком В.
б) Если Л вЂ” область тела, то выполняем вычисления, показанные на рис. 9.50, а. в) Если Л вЂ” область цикла, то выполняем вычисления, показанные на рис. 9.50, б. 3. Выполняем нисходящий проход для поиска значений потока данных в начале каждой области. а) пч]Л„] = п|]Вход]. б) Для каждой области Ле ) Лы.... Л | ) в нисходящем порядке вычисляем 1Ж |Л] = 1п т~ч|п1 (111 ]Л']), где Л' — область, непосредственно охватывающая область Л. Сначала подробно рассмотрим, как работает восходяц|ий анализ. В строке 1 на рис. 9.50, а мы посещаем подобласти области тела в некотором топологическом порядке. В строке 2 вычисляется передаточная функция, представляющая все возможные пути от заголовка Л к заголовку Я. Затем в строках 3 и 4 мы вычисляем передаточные функции, представляющие все возможные пути от заголовка Л к выходам из Л, т.е.
к выходам из всех блоков, которые имеют преемников за пределами Я. Заметим, что все предшественники В' в Л должны быть в областях, которые предшествуют Я в топологическом порядке, построенном в строке 1. Таким образом, 1л цт|п1 будет уже вычислено в строке 4 предыдущей итерации внешнего цикла. 813 9,7. Анализ на основе областей 1ог (каждая подобласть Я, непосредственно содержащаяся в Л, в топологическом порядке) ( ,/йзн)В) = Анрелшесгвениики В заголовка В из й / й,она )В) /* Если Я вЂ” заголовок области Л, то /й г )В)— сбор "по ничему", т.е.
тождественная функция */ !ог (каждый выходной блок В в В) ./й,оиг)В) =,/Я,онг)В) и /гйитЯ 2) 3) 4) а) Построение передаточной функции для области тела Л Пусть Я вЂ” область тела, непосредственно вложенная в Л (т.е. В представляет собой Л без обратных ребер из Л в заголовок Л; сии)В) — '1АПрелшесгвенники В заголовка В в й .Г.з,онт)В) / )ог (каждого выходного блока В из Л) з й,онт)В) = Б,онт)В) 1й,ги)В) б) Построение передаточной функции для области цикла Л' 2) 3) 4) Рис. 9.50. Детали вычислений потоков данных на основе областей Вспомним упрощенные правила для передаточных функций вида дел-/п7/ из раз- дела 9.7.4. Для областей циклов мы выполняем шаги в строках 1-4 на рис.
9.50, б. В строке 2 вычисляется влияние обхода по циклу области тела Я нуль нли больше раз. В строках 3 и 4 вычисляется влияние выходов из цикла после одной или более итераций. В нисходящем проходе алгоритма на шаге 3, а сначала устанавливаются граничные условия на входе в верхнюю область. Затем, если Л содержится в Л' непосредственно, для вычисления 1м[Л] можно просто применить передаточную фуНКцИЮ /йга )й) К ЗНаЧЕНИЮ ПОтОКа даННЫХ 1М )Л').
гз Пример 9.50. Применим алгоритм 9,49 для поиска достигающих определений в графе потока на рис. 9.48, а. На шаге ! создается восходящий порядок, в котором посещаются области. Этот порядок определяет нумерацию индексов областей Л! г Л2 г ° ° ° г Лп Значения множеств дел н /гг7/ для пяти базовых блоков приведены ниже. 814 Глава 9. Машинно-независимые оптимизации ° Для получения сбора передаточных функций вычисляются объединение множеств пел и пересечение множеств ИП. ° Для вычисления композиции передаточных функций вычисляются объединения множеств деп и ЬП.
Однако как исключение выражение, которое генерируется первой функцией, при этом не генерируется второй и уничтожается ею, не входит в множество пел результата. ° Для получения замыкания передаточной функции деи оставляется неизменным, а лзП становится пустым множеством. Первыми пятью областями Лы..., Вз являются соответственно базовые блоки Вы..., Вз.
Функция ~п,пи~В 1 для 1 < з < 5 является тождественной функцией, а функция гл от~В ~ — передаточной функцией для блока В,: 1В„ог ~Вй (*) = (л — И11В,) 08елВ, Остальные передаточные функции, построенные на шаге 2 алгоритма 9.49, подытожены на рис.
9.5!. Область Лш состоящая из областей Вз, Вз н В4, представляет тело цикла и, таким образом, не включает обратное ребро В4 — Вз. Порядок обработки этих областей представляет собой единственный топологический порядок: Лз, Лз, Л4. Лз не имеет предшественников в пределах Вл., вспомним, что ребро В4 — Вз выходит за пределы Ве. Таким образом, ~лези~пз1 представляет собой тождественную функцию~~, а тле о„т~пз~ — передаточную функцию для блока Вз.
Заголовок области Вз имеет одного предшественника в Ве, а именно — Вз. Передаточная функция к его входу представляет собой просто передаточную функцию к выходУ из Вз, |Ве оот~пзй котоРаЯ Уже вычислена. Дли полУчениЯ пеРедаточной функции к выходу из Вз мы вычисляем композицию этой функции с передаточной функцией Вз в ее собственной области. Наконец, поскольку и Вз, и Вз являются предшественниками В4, заголовка Л4, для вычисления передаточной функции ко входу в В» мы должны вычислить 1Ве,оит~Вз1 Д 1Яе,оит~В41 Для получения требующейся функции 1".Ве „т~В,~ следует вычислить композицию этой передаточной функции и функции 1В4 пт~пяр Обратите внимание, например, что дз не уничтожается в этой передаточной функции, поскольку путь Вз — В4 не переопределяет переменную а.
Теперь рассмотрим область цикла Лт. Она содержит только одну подобласть Вп, которая представляет тело ее цикла. Поскольку существует только одно обратное ребро В4 — Вз к заголовку Вп, передаточная функция, представляющая и Строго говоря, имеется в виду функция ~п, Млвр ио когда область ивподобие Вз представляет собой единственный блок, в телом контексте более понятным оказывается использование имени блока вместо имени области. 815 9.7. Анализ на основе областей ПЕРЕДАТОЧНАЯ ФУНКЦИЯ ~йб м(йг] ~йа,оп(йг] Ткб, (кз] 2 Кб,оит(вз] С Кбайт(Й4] з йб,Оит В4] (?44) (с[4) (с"415[5) (с[4 ?45) (4441 4[51 ?[6) ( [1) ( [1) (с[1, с[З) ( [1) (с[1, с[2) 4 Йг,оит(вг[ 4 Й5,64[йг] з йб,оит(вг[ 2 йз,оит(вз[ з кбзя[йз] з Кб,оит[вг[ ' ' з йб,оит(вз[ 1К4,0ит В4 4 йт,~н йб[ (с[4~ 445~ с"6) (с[4 ~ 4[51 4[6) (444~ 5[5~ с"6) 1йт ьч(йб] ~йб оит(В4[ Л' т Оит(Вз[ Л?б,оит(вз[ 4 Йт,?6(йб[ 4 йт Ост(В4[ Уйб Оит В4 1КТ ьч[йб (с[1, с[з) (с"11 4"2) 4 Кби?4(йс[ Л?б,оит(В [ з йб 64(йт[ 2 йб,оит(вз[ Л?8.Оит(В4[ .~йб,?Н(йб[ .1йб,оит Вб И (с[1, с[2, с[3) ( [1, [2, [3) (с[2 с[4 ~ с[5 ~ 4[6 ) (?43 с"4 ~ 4[5~ с[6) (5[2~ 5[3~ 4[4~ 5[5~ с[6) (С[2, С"3, С"4, С[5, 4"6) (с[4 ~ ?[51 ?[6) (с[4, с[5, с[6) (с[,, с[з) (с[1 с[2) ( [1) ( [1) з йьоит(вс] з' Йб,оит(в? [ 2 К~в~(В ] йт оит(В4] 4 йб,оит(вз( Л?з,оит Вб о Л?блн(йт] Л?...(.,( ' ' 2йб,оит(В4[ Л?, 'й, Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
