А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 163
Текст из файла (страница 163)
Определение с! в этом проходе распространится в о!37 [16], па [23) и далее до ог3т [45), где оно должно будет подождать, поскольку !!ч [4] уже вычислено в данном проходе. При третьем проходе Н распространяется далее в пч [4),о0т [4), пч [10], ог3т [10) и пч [17), так что после трех проходов выясняется, что г! достигает блока 17.
о Из этого примера несложно вывести общий принцип. Если на рис. 9.23, а мы используем порядок "вглубь", то количество проходов, необходимое для распространения любого достигающего определения вдоль любого ацикличного пути, не более чем на единицу превышает число ребер пути, идущих от блока с ббльшим номером к блоку с меньшим. Зги ребра являются отступающими, так что необходимое количество проходов на единицу болыле глубины. Конечно, алгоритму 9.11, для того чтобы определить достижение всех определений, требуется один дополнительный проход, так что верхняя граница количества проходов, необходимых алгоритму с упорядочением блоков вглубь, в действительности на 2 превышает глубину.
Изучение" показало, что средняя глубина типичного графа потока равна 2.75. Таким образом, алгоритм сходится очень быстро. В случае задач в направлении, обратном к направлению потока, таких как анализ активных переменных, мы посещаем узлы в порядке, обратном порядку "вглубь". Таким образом, мы можем распространить использование переменной в блоке 17 в обратном направлении по пути 3 — 5 — г 19 — 35 — 16 -г 23 — 45 — 4 — 10 — 17 ' ГЗ.Е. Кппак "Ап е|пргпса! згпг!у от рОКТКАга ргоягапгт', Яа7пеаге — Ргасггсе аагу рхреглеасе 1:2 !!97!), рр. !05-!33.
801 9.б. Циклы в графах потоков за один проход до пч [4~, где мы должны дождаться следующего прохода, чтобы достичь опт [45]. При втором проходе мы достигаем пч [101, а на третьем проходим от Оит [35~ до О0т (31 В общем случае, если мы выберем порядок посещения узлов при проходе, обратный нумерации вглубь, то в связи с тем, что распространение в данной ситуации по уменьшающейся последовательности номеров выполняется за один проход, нам будет достаточно количества проходов, на единицу превышающего глубину. Описанная граница представляет собой верхнюю границу для всех задач, в которых циклические пути не добавляют информацию к анализу. В частных случаях, таких как задача о доминаторах, алгоритм сходится даже еще быстрее.
Если входной граф потока приводим, корректное множество доминаторов для каждого узла получается при первой итерации алгоритма потока данных, который посещает узлы в порядке в глубину. Если заранее не известно, приводим ли входной граф, потребуется дополнительная итерация для того, чтобы убедиться, что решение сошлось. 9.6.8 Упражнения к разделу 9.6 Упражнение 9.6.1. Для графа потока на рис. 9.10 (см. упражнения к разделу 9.1) выполните следующее. а) Вычислите отношение доминирования.
б) Найдите для каждого узла его непосредственный доминатор. в) Постройте дерево доминаторов. г) Найдите упорядочение вглубь графа потока. д) Укажите в вашем ответе к п. е наступающие, отступающие, поперечные ребра и ребра дерева. е) Является ли данный граф потока приводимым? ж) Вычислите глубину графа потока. з) Найдите естественные циклы в графе потока. Упражнение 9.6.2.
Повторите упражнение 9.6.1 для следующих графов потоков. а) Граф потока на рис. 9.3. б) Граф потока на рис. 8.9. в) Граф потока, разработанного вами при выполнении упражнения 8.4.1. 802 Глава 9. Машинно-независимые оптимизации г) Граф потока, разработанного вами при выполнении упражнения 8.4.2. ! Упражнение 9.6.3. Докажите справедливость следующих утверждений об отношении пот. а) Если а аот 6 и Ь аот с, то а г2от с (трапзитивность). б) Невозможно, чтобы одновременно выполнялось а аот 6 и 6 аот и, если только а не совпадает с 6 (антисимметрия).
в) Если а и 6 являются двумя доминаторами и, то должно выполняться либо а аот 6, либо Ь аот а. г) Каждый узел п, за исключением входного, имеет единственный непосредственпый доиииатор — доминатор, который ближе других к п вдоль любого ацикличного пути от входного узла к и. ! Упражнение 9.6.4. На рис. 9.42 приведено одно из представлений вглубь графа потока на рис. 9.38. Сколько имеется других представлений данного графа потока? Напомним, что представления различаются порядком дочерних узлов. !! Упражнение 9.6.5. Докажите, что граф потока приводим тогда и только тогда, когда граф потока ацикличен после удаления из него всех обратных ребер (у которых заголовок доминирует над хвостом). ! Упражнение 9.6.6.
Полный граф потока (сошр!е!е !!отч 8гарй) с и узлами содержит дуги ! — т' между любыми двумя узлами ! и ?' (в обоих направлениях). Для каких значений п такой граф является приводимым? ! Упражнение 9.6.7. Полный аииклический граф потока (сошр!е!е асус11с бов 8гарй) с и узлами 1,2,..., и содержит дуги ! — у' для всех узлов ! и з, таких, что ! < у. Узел 1 является входным. а) Для каких значений п такой граф является приводимым? б) Изменится ли ваш ответ на вопрос а, если к каждому узлу ! добавить петлю ! — ~ !? ! Упражнение 9.6.8.
Естественный цикл для обратного ребра п — 6 определен как 6 плюс множество узлов, которые могут достичь и, не проходя через 6. Покажите, что 6 доминирует над всеми узлами естественного цикла лля п — Ь. !! Упражнение 9.6.9. Мы утверждаем, что граф потока на рис. 9.45 неприводим. Если дуги заменить путями непересекающихся множеств узлов (за исключением конечных точек), то граф останется неприводимым.
В действительности узел 1 не обязан быть входным; он может быть любым узлом, достижимым из входного узла 803 9.7. Анализ ла основе областей по пути, промежуточные узлы которого не являются частью никакого из четырех явно показанных на рисунке путей. Докажите обратное — что любой неприводнмый граф потока содержит подграф наподобие показанного на рис.
9.45, но с дугами, которые могут быть заменены путями по непересекающимся множествам узлов, а узел ! быть любым узлом, достижимым из входной точки по пути, который не включает узлы из четырех других путей. !! Упражнение 9.6.10. Покажите, что любое представление вглубь любого неприводимого графа содержит отступающее ребро, не являющееся обратным. !! Упражнение 9.6.11.
Покажите, что если для любых функций )' и д и значения а выполняется условие )' (а) Л д (а) Л а < ~ (д (а)), то обобщенный итеративный алгоритм 9.25 с итерациями в порядке "вглубь*' сходится за количество проходов, на 2 превышающее глубину. ! Упражнение 9.6.12. Найдите неприводимый граф потока с двумя различными РЕБТ, которые имеют разную глубину. ! Упражнение 9.6.13. Докажите следующие утверждения. а) Если определение 4 находится в пч )В), то существует некоторый ациклический путь от блока, содержащего д, к блоку В, такой, что Н находится во всех множествах пч и опт вдоль этого пути. б) Если выражение х + у недоступно на входе в блок В, то существует некоторый ациклический путь, демонстрирующий этот факт.
Либо этот путь представляет собой путь из входного узла и не включает инструкции, которые уничтожают или генерируют х+ у, или путь ведет из блока, который уничтожает х + у и вдоль которого нет последующей генерации х + у. в) Если переменная х активна на выходе из блока В, то существует ацикли- ческий путь из В к использованию х, вдоль которого нет определений х.
9.7 Анализ на основе областей Итеративный алгоритм анализа потока данных, рассматривавшийся нами,— всего лишь один из подходов к решению задач потоков данных. Сейчас мы рассмотрим еще один подход — анализ на основе областей (ге81оп-Ьазед апа)уз!з). Вспомним, что в случае итеративного подхода мы создавали передаточную функцию для базовых блоков, затем находили решение путем многократного прохода по блокам.
Анализ на основе областей вместо передаточной функции для отдельных блоков находит передаточные функции, которые подытоживают выполнение 804 Глава 9. Машинно-независимые оптимизации все больших и больших областей программы. В конечном счете строится и применяется передаточная функция для всей процедуры целиком, применяя которую, мы непосредственно получаем требуемые нам значения потока данных. Структура потока данных, использующая итеративный алгоритм, определяется полурешеткой значений потока данных и семейством передаточных функций, замкнутых относительно композиции. Анализ же на основе областей требует большего количества элементов. Соответствующая структура включает как полурешетку значений потока данных, так и полурешетку передаточных функций, которая должна располагать оператором сбора, оператором композиции и оператором замыкания.
Все эти элементы будут рассмотрены нами в разделе 9.7.4. Анализ на основе областей в особенности применим к задачам потоков данных, в которых пути содержат циклы, которые могут изменять значения потоков данных. Оператор замыкания позволяет более эффективно по сравнению с итеративным анализом подытожить влияние цикла. Этот метод оказывается эффективным и при межпроцедурном анализе, когда передаточные функции, связанные с вызовом процедуры, могут рассматриваться так же, как и перелаточные функции, связанные с базовыми блоками.
9.7.1 Области В процессе анализа на основе областей программа рассматривается как иерархия областей (ге81оп), которые грубо можно считать частями графа потока, имею- шими единственную точку входа. Такая концепция рассмотрения кода как иерархии областей должна быть интуитивно понятна, поскольку процедура, составленная из блоков, естественным образом организуется в виде иерархии областей. Каждая инструкция в блочно-структурированной программе является областью, поскольку поток управления может достичь инструкции только через ее начало. Каждый уровень вложенности инструкций соответствует уровню в иерархии областей. Формально область (ге81оп) графа потока представляет собой набор узлов Х и ребер Е, таких, что 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
