А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 154

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 154)

Максимальная фиксированная точка и реп!ение сбором по путям Заметим, что в мог-решении в случае наличия циклов коли ьество рассматриваемых путей остается неограниченным. Таким образом, мог-определение само по себе не приводит к алгоритму. Итеративный алгоритм не должен начинаться с поиска всех путей, ведущих к базовому блоку, перед тем как применять оператор сбора. Вместо этого 1. итеративный алгоритм посещает базовые блоки нс обязательно в порядке их выполнения; 2. в каждой точке слияния алгоритм применяет оператор сбора к значениям потока данных„ полученным к этому моменту; нскоторые из этих значе- 758 Глава 9.

Машинно-независимые оптимизации ний бьши искусственно введены при инициализации, а не представляют результат выполнения программы от начала к рассматриваемой точке. Так как же соотносятся решение сбором по путям и решение, получаемое алгоритмом 9.21? Начнем рассмотрение с порядка обхода узлов. В пределах итерации мы можем посетить базовый блок до посещения его предшественников. Если таковым предшественником является входной узел, опт [Вход] инициализирован корректным константным значением.

Остальные узлы инициализированы значением Т, не меньшим, чем окончательный ответ. Монотонность обеспечивает при использовании Т в качестве входных данных получение результата, не меньшего, чем искомое решение. В этом смысле можно говорить о Т как о не представляющем никакой информации. Вг Рнс. 9.24. Граф потока, иллюстрирующий влияние раннего сбора по путям В чем выражается ранее применение оператора сбора? Рассмотрим простой пример, показанный на рис.

9.24, и предположим, что интересующее нас значение — п4 [В4]. В соответствии с определением мОР [В4] = ((~Вх,Ь ) ЦВ Л~г))(СВХОД) В итеративном алгоритме при посещении узлов в порядке Вы Вз, Вз, В4 Р1 [В4] = 1Вз (УВг (ггвход) Л ДВд (ггвход))) В то время как оператор сбора применяется в конце мор-определения, итеративный алгоритм применяет его раньше. Ответ при этом получается одинаковым, только если структура потока данных дистрибутивна. Если структура потока данных монотонна, но не дистрибутивна, то пч [В4] ( мор [В4].

Вспомним, что в общем случае решение пч [В] безопасно (консервативно), если для всех базовых блоков В пч[В] ( пзвм.(В]. 759 9.3. Основы анализа потока данных Представим набросок доказательства того, что в общем случае решение максимальной фиксированной точки, получаемое итеративным алгоритмом, всегда безопасно. Простая индукция по 1 показывает, что значения, полученные после ! итераций, не превосходят результата сбора по всем путям длиной ! и менее. Однако итеративный алгоритм завершается, только если он достигает того же ответа, что и при неограниченном количестве итераций, Таким образом, результат оказывается не большим, чем мог-решение. Поскольку мог < !пеА~., а мн' < мог, мы получаем мгг < !пиль, а следовательно, решение максимальной фиксированной точки, получаемое при использовании итеративного алгоритма, является безопасным.

9.3.5 Упражнения к разделу 9.3 Упражнение 9.3.1. Постройте диаграмму решетки для произведения трех решеток, каждая из которых основана на одном определении 4, 1 = 1, 2,3. Как ваша диаграмма соотносится с диаграммой на рис. 9.22? ! Упражнение 9.3.2. В разделе 9.3.3 мы доказали, что если структура имеет конечную высоту, то итеративный алгоритм сходится. Далее приведен пример, в котором структура не имеет конечной высоты и итеративный алгоритм не является сходящимся.

Множество значений $' представляет собой неотрицательные целые числа, а оператор сбора — минимум. Имеется три передаточные функции, а именно 1. тождественность ~г(х) = х; 2. "половина" 1п (х) = х,12; 3. "единица" 1о(х) = 1. Множество передаточных функций Г состоит из трех указанных функций н всевозможных их композиций. а) Опишите множество Е. б) Что собой представляет отношение < в данной схеме? в) Приведите пример графа потока с присоединенными передаточными функциями, для которого алгоритм 9.2! не сходится. г) Является ли данная структура монотонной, дистрибутивной? ! Упражнение 9.3.3. Мы доказали, что алгоритм 9.2! сходится, если структура монотонна и имеет конечную высоту.

Вот пример структуры, иллюстрирующей важность монотонности (конечности высоты оказывается недостаточно). Область 760 Глава 9. Машинно-независимые оптимизации определения 1' = (1, 2), оператор сбора — минимум, а множество функций Е состоит из тождественной функции ©) и функции "переключения" (,1з (х) = 3 — з), которая меняет 1 на 2 и наоборот.

а) Покажите, что эта структура имеет конечную высоту, но не монотонна. б) Приведите пример графа потока и назначения передаточных функций, такой, что алгоритм 9.21 не сходится. ! Упражнение 9.3.4. Пусть мог, [В] — сбор по всем путям длиной 1 или менее от входа до базового блока В. Докажите, что после 1 итераций алгоритма 9.21 пч [В] ( мог; [В].

Покажите также как следствие, что если алгоритм 9.21 сходится, то он сходится к результату, который не превышает (в смысле отношения () могрешение. ! Упражнение 9.3.5. Предположим, что множество функций Е структуры содержит только функции вида дел-)гй, т.е. область определения $' является показательным множеством некоторого множества, а Г" (х) = С О (х — К) для некоторых множеств С и К.

Докажите, что если оператор сбора представляет собой а) объединение или б) пересечение, то описанная структура дистрибутивна. 9.4 Распространение констант Все рассматривавшиеся в разделе 9.2 схемы в действительности представляют собой простые примеры дистрибутивных структур с конечной высотой. Таким образом, применение к ним итеративного алгоритма 9.21 как в прямом, так и в обратном направлениях, приводит в каждом случае к мог-решению. В этом разделе мы поближе познакомимся с полезной структурой потока данных, обладаюшей более интересными свойствами. Вспомним, что распространение констант (сопззап1 ргорадайоп), или "дублирование констант" (сопз1аШ то!йцд), заменяет выражения, которые при выполнении всякий раз вычисляют одну и ту же константу, самой этой константой.

Описанная ниже структура распространения констант отличается ог уже рассматривавшихся задач потоков данных тем, что а) имеет неограниченное множество возможных значений потока данных даже для фиксированного графа потока и б) не является дистрибутивной. Распространение констант является прямой задачей потока данных. Полу- решетка, представляюшая значения потока данных, и семейство передаточных функций будут представлены далее.

9.4. Распространение констант 9.4.1 Значения потока данных для структуры распространения констант Множество значений потока данных представляет собой решетку произведения, в которой имеется по одному компоненту для каждой переменной программы. В решетку для единственной переменной входит следующее. !. Все константы подходяшего для данной переменной типа.

2. Значение мАС, означающее "не константу" (попа-сопвшпс). Переменная отображается на это значение, если выясняется, что она не имеет константного значения. Это может происходить потому, что переменной может быть присвоено входное значение либо она может быть вычислена из переменной, не являющейся константой, а также на разных путях, приводящих к одной и той же точке программы, ей могут присваиваться разные константы. 3.

Значение глчпег, которое означает "не определена" (илдебпед). Переменная получает это значение, если пока что о ней ничего нельзя утверждать наверняка; вероятно, пока что не найдено определение, достигающее рассматриваемой точки. Заметим, что мАс и 0хпее — это не одно и то же, это сушественно разные вещи. млс говорит о том, что имеется много путей определения переменной, так что мы знаем, что она не может быть константой; 1дЧПЕР же говорит о том, что мы знаем о переменной слишком мало, чтобы считать ее чем бы то ни было. Полурешетка для типичной целочисленной переменной показана на рис. 9.25.

Характеристики

Список файлов книги