А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 164
Текст из файла (страница 164)
существует заголовок 6 е АГ, доминирующий над всеми узлами в Ж; 2. если некоторый узел гп может достичь узла и е Ю, минуя 6, то т также входит в АГ; 3. Š— множество всех ребер потока управления между узлами пз и пз из Х, за исключением, возможно, некоторых ребер, входящих в 6. Пример 9.4б. Ясно, что естественный цикл представляет собой область, но область не обязательно содержит обратное ребро и не обязательно включает пикл.
805 9.7. Анализ на основе областей ( Вход) Рнс. 9.47. Примеры областей Например, на рис. 9.47 узлы В1 и Вз вместе с ребром В~ — Вз образуют область; то же самое можно сказать и об узлах Вы Вз и Вз и ребрах В1 — Вз, Вз — Вз нВ~- Вз. Однако подграф с узлами Вз и Вз и ребром Вз — Вз область не образует, поскольку управление может попасть в подграф как через узел Вз, так и через узел Вз. Говоря более точно, ни Вз, ни Вз не доминируют друг над другом, так что условие 1 для области оказывается не выполненным. Даже если мы выберем, скажем, Вз в качестве "заголовка", то будет нарушено условие 2, поскольку можно достичь Вз из Вы не проходя через Вз, а В1 не входит в "область".
Б 9.7.2 Иерархии областей для приводимых графов ПОТОКОВ В приведенном далее материале предполагается, что граф потока приводим. Если вдруг нам придется иметь дело с неприводимыми графами, мы можем воспользоваться методом "расщепления узлов", рассматривающимся в разделе 9.7.6. Для построения иерархии областей мы идентифицируем естественные циклы. Вспомним из раздела 9.6.6, что в приводимом графе потока любые два естественных цикла либо не пересекаются, либо один из них вложен в другой. Процесс "разбора" приводимого графа потока в иерархию циклов начинается с того, что каждый базовый блок рассматривается как область.
Такие области мы будем называть обладании-листьями (1еаГ гея)оп). Затем мы упорядочиваем естественные циклы изнутри наружу, т.е. начиная с наиболее внутренних циклов. При обработке цикла мы заменяем его узлом, выполняя следуюшие шаги. 1. Тело цикла Л (все узлы и ребра, за исключением обратных ребер к заголовку) замещаем узлом, представляющим область Л.
Ребра, ведущие к заголовку Л, входят теперь в узел В. Ребро нз любого выхода из Ь замещается ребром от Л в то же самое место назначения. Однако если ребро является 806 Глава 9. Машинно-независимые оптимизации обратным, то оно становится петлей у Л. Назовем Л областью тела (Ьоду ге81оп). 2. Строим область Л', представляющую естественный цикл В целиком, и называем Л' областью цикла (!оор ге81оп). Единственное отличие Л от Л' заключается в том, что последняя включает обратные ребра к заголовку цикла Т. Другими словами, при замене в графе потока Л областью Л' все, что нам надо сделать, — это удалить ребро-петлю от Л к Л.
Таким образом мы сводим к отдельным узлам все ббльшие и большие циклы, сначала с ребрами-петлями, а затем и без них. Поскольку циклы в приводимых графах потоков либо вложены, либо не пересекаются, узел области цикла может представлять все узлы естественного цикла в ряду графов потоков, строящихся описанным способом. В конечном счете все естественные циклы сводятся к отдельным узлам. В этот момент граф потока может быть либо сведен к единственному узлу, либо состоять из нескольких узлов и не содержать циклов (т.е.
приведенный граф потока представляет собой ациклический граф из нескольких узлов). В первом случае построение иерархии областей завершено, во втором мы строим еще одну область тела для всего графа потока. Пример 9.47. Рассмотрим граф потока на рис. 9.48, а. У этого графа потока имеется одно обратное ребро, ведущее от В4 к Вз.
Иерархия областей показана на рис. 9.48, б. Всего имеется 8 областей. 1. Области Лг,..., Ль являются областями-листьями, представляющими блоки Вы...,Вь соответственно. Каждый блок является выходным блоком в своей области. 2. Область тела Ле представляет тело единственного цикла в графе потока; она состоит из областей Лз, Лз и Л4 и межобластных ребер Вз — Вз, Вз — ~ В4 и Вз — ~ В4. Она содержит два выходных блока, Вз и В4, поскольку оба они имеют выходные ребра, не содержащиеся в области. На рнс.
9.49, а показан граф потока с областью Ле, приведенной к единственному узлу. Заметим, что хотя оба ребра, Лз — Ль и Л4 — Лы заменены ребром Лв — Лы важно помнить, что это последнее ребро представляет два ребра. Это связано с тем, что мы будем распространять перелаточные функции по этому ребру и должны знать, что выходящее из блоков Вз и В4 будет достигать заголовка Лв. 3. Область цикла Лт представляет естественный цикл целиком. Она включает одну подобласть Ла и одно обратное ребро В4 — Вз.
Она также имеет два выходных узла — те же Вз и В4. На рис. 9.49, б показан граф потока после приведения естественного цикла к области Лт. 807 9.7. Анализ иа основе областей б) Рис. 9.48. Пример графа потока для задачи достигаюших определений (а), и его иерархия областей (б) 4. Область тела Ла представляет собой наивысшую область. Она включает три области, Лн Лт, Лб, и три межобластных ребра, В) -4 Вз, Вз — Вб и В4 — Вб. При приведении графа потока к Ла он становится единственным узлом. Поскольку обратных ребер к его заголовку В) нет, заключительный шаг, приводящий эту область тела к области цикла, не требуется.о 808 Глава 9.
Машинно-независимые оптимизации а) Рис. 9.49. Шаги приведения графа потока на рнс. 9.48 к единственной области Подытоживая процесс иерархической декомпозиции приводимого графа потока, мы получаем следующий алгоритм. Алгоритм 9.48. Построение восходяшего порядка областей приводимого графа потока ВХОД: приводимый граф потока С. ВЫХОД: список областей графа потока С, который может использоваться в задачах потоков данных на основе областей. МетОД; выполняем следуюшие действия. Е Начинаем со списка листьев-областей, состоящих из отдельных блоков С в произвольном порядке. 2.
Неоднократно выбираем естественный цикл з,, такой„что если существуют любые естественные циклы, содержашиеся в ь, то тела и области этих циклов уже внесены в список. Сначала добавляем область, состоящую из тела э. (т.е. Ь без обратных ребер к заголовку Ь), а затем — область цикла Ь. 3. Если весь граф не представляет собой естественный цикл, добавляем в конец списка область, состоящую из всего графа потока целиком.
и 9.7.3 Обзор анализа на основании областей Для каждой области Л и для каждой подобласти Л' в Л мы вычисляем передаточную функцию ~н „~н.р которая суммирует влияние выполнения всех возможных путей, ведуших от входа в Л ко входу в Л', в пределах Л. Мы говорим, что базовый блок В в Л является выходным блоком (ехй Ыоск) области Л, если у него имеется выходное ребро к некоторому блоку вне Л. Мы также вычисляем передаточные функции для каждого выходного блока В в Л, которые обозначаются как ~л ц,~н1 и которые суммируют влияние выполнения всех возможных путей в Л, ведуших от входа в Л к выходу из В. 809 9.7. Анализ иа основе областей Происхождение термина "нриводимостьн Сейчас вы узнаете, почему приводимые графы получили такое название. Мы не будем доказывать этот факт, но использованное в данной книге определение "приводимого графа потока", включающее обратные ребра графа, эквивалентно нескольким определениям, в которых граф потока механически приводится к единственному узлу.
Процесс свертки естественных циклов, описанный в разделе 9.7.2, — один из них. Другое интересное определение заключается в том, что приводимыми графами потоков являются те и только те графы, которые могут быть приведены к единственному узлу при помощи следующих двух преобразований; Ть удаление ребра-петли, входящего в узел, из которого оно вышло; Тз. обьединение узлов т и и, если узел и имеет единственного предшественника го и и не является входным для графа потока. Затем мы обрабатываем иерархию областей, вычисляя передаточные функции для все ббльших областей. Мы начинаем с областей, состоящих из отдельных блоков, для которых передаточная функция Лз „д представляет собой тождественнУю фУнкцию, а фУнкциЯ 7п п,~п1 ЯвлЯетсЯ пеРедаточной фУнкцией длЯ блока В. При перемещении вверх по иерархии выполняется следующее.
° Если Л вЂ” область тела, то ребра, принадлежащие Л, образуют ациклический граф на подобластях Л. Для вычисления передаточных функций можно воспользоваться топологическим упорядочением областей. ° Если Л вЂ” область цикла, то учитывается только влияние обратных ребер, ведущих к заголовку Л. В конечном счете мы достигаем вершины иерархии и вычисляем передаточные функции для области Л„, которая представляет собой весь граф целиком. Как именно выполняется каждое вычисление„вы узнаете из алгоритма 9.49.
Следующий щаг состоит в вычислении значений потока данных на входе и выходе каждого базового блока. Мы работаем с областями в обратном порядке, начиная с области В и опускаясь вниз по иерархии. Для каждой области мы вычисляем значения потока данных на входе. Для области Л„мы используем вызов ~д.з„~д1 (~н ~ВхОД~), чтобы получить значения потока данных на входе подобластей Л области Л„. Эти действия повторяются, пока не будут достигнуты базовые блоки в листьях иерархии областей. 810 Глава 9. Машинно-независимые оптимизации 9.7.4 Необходимые предположения о передаточных функциях Для анализа на основе областей требуется сделать определенные предположения о свойствах множества передаточных функций структуры.
В частности, нам нужны три примитивные операции над передаточными функциями: композиция, сбор и замыкание. Для структур потоков данных с использованием итеративного алгоритма требуется только первая из них. Композиция Передаточная функция последовательности узлов может быть получена путем композиции функций, представляющих отдельные узлы.
Пусть Л и ~г— передаточные функции узлов п1 и пг. Влияние выполнения п1 с последующим выполнением пг представлено как 1г о Л. Композиция функций рассматривалась в разделе 9.2.2, а пример использования достигающих определений был приведен в разделе 9.2.4. Вкратце повторим пройденное.
Пусть 8еп, и ИП, обозначают множества 8еп и И1 для Л. Тогда 1г с Л (х) = хепг 0 ((8еп, 0 (х — И11 )) — И1г) = = (сепг 0 (хеп, — И1г) ) 0 (х — (дпдз О Идг)) Таким образом, множествами реп и НП для 1г о Л являются сепг 0 (реп, — ИПг) и Ы1з О И1г соответственно. Та же идея применима и для любой передаточной функции вида 8еп-'и!11. Другие передаточные функции также могут быть замкнуты, но каждый случай следует рассматривать отдельно.
Сбор Сами по себе передаточные функции являются значениями полурещетки с оператором сбора ду. Сбор функций Л и !г, Лг у)г, определяется как (Л ду Уг) (х) = = Л (х) Л 5г (х), где Л вЂ” оператор сбора для значений потока данных. Оператор сбора для передаточных функций используется для объединения влияния альтернативных путей выполнения с одними и теми же конечными точками. Далее, где это нс будет приводить к неоднозначности, мы будем обозначать оператор сбора для передаточных функций без индекса просто как Л. В случае структуры достигающих определений мы имеем (Л л зг) (х) = Л (х) л Ь (х) = = (хепз 0 (х — !пП1)) 0 (8епг 0 (х — ИПг)) = = (8епз 0 сепг) 0 (х — (/адз П !пдг)) Иными словами, м ножествами 8еп и ИП для Л Л гг являются 8еп, 08еп и И11 ПИПг соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
