А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 152
Текст из файла (страница 152)
Мы рассматриваем только "половинные*' решетки, в которых имеется только один из операторов сбора или объединения. Таким образом, рассматриваемые нами полурешетки являются ппирешеткаии сбора (шее( яепп1ап)сез). Можно также говорить о полуре1аел)ках объес)инения ((о)п зеш(1а(бсез), у которых существует только один оператор объединения; имеется ряд кни); в которых при анализе программ используется понятие полурешеток объединения.
Но поскольку традиционно литература. посвященная потокам данных говори г о решетках сбора, в данной книге мы поступим так же. опушены ребра от .т к Гп если на лиаграмме имеется иной путь от т, к Гь Таким обРазом, хотЯ (г)(,с1з,дз) < (И(), мы не изобРажаем это РебРо из-за наличиЯ, например, пути, идущего через (с1), а)з). Рис. 9.22. Решегка подмножеств определений 749 9,3. Основы анализа потока данных Решетки произведений Хотя на рис. 9.22 имеется только три определения, диаграмма решетки типичной программы может оказаться существенно большей. Множество значений потока данных является показательным множеством определений, и при наличии в программе п определений содержит 2" элементов. Однако определение достигает точки программы независимо от достнжимости других определений.
Таким образом, решеткуа определений можно рассматривать как полученную в резулыаге "произведения" простых решеток для каждого из определений. Если бы в программе имелось только одно определение 4, то решетка ильела бы два элемента— пустое множество (), являющееся верхним элементом, и нижний элемент (с1). Формально можно построить решетки произведений следующим образом. Предположим, что (А, ЛА) и (В, Лн) — (полу)решетки.
Решетка произведения 1ргос)пег 1арбсе) этих двух решеток определяется следующим образом. 1. Областью определения решетки произведения является А х В. 2. Оператор сбора Л решетки произведения определяется следующим образом. Если (а, Ь) и (а', Ь') являются элементами области определения решетки произведения, то (а, Ь) Л (а, Ь ) = (а Л 4 а, Ь Лн Ь ) (9.2) Очень просто выразить частичный порядок < для решетки произведения в терминах частичных порядков <4 и <н для А и В: (аз Ь) < (а', Ь') тогда и только тогда, когда а <4 а' и Ь <н Ь' 19.3) Чтобы понять, почему (9.3) следует из 19.2), заметим, что (а, Ь) Л (а', Ь') = (а Ли а, Ь Лн Ь') 'Здесь и далее мы часто опускаем приставку "полу", поскольку решетки наподобие рассматриваемой имеют оба оператора, даже если одним мы и не пользуемся.
Следует заметить, что на такой диаграмме ясно видны результаты операции сбора. Поскольку х Л у представляет собой наибольшую нижнюю границу, всегда имеется большее г, к которому ведут пути от х и у. Например, если х — (с)з), а у — (с1з), то л на рис. 9.22 представляет собой (Ны дз), что логично, так как оператор сбора представляет собой объединение. Верхний элемент множества всегда находится наверху в диаграмме, так что от элемента Т существуют пути к каждому из остальных элементов.
Аналогично нижний элемент находится внизу в решетке, и к этому элементу 3 имеется путь от каждого из остальных элементов. 750 Глава 9. Машинно-независимые оптимизации Можно задаться вопросом "При каких условиях (а Л4 а', Ь Лп Ь') = (а,6)?" Это соотношение выполняется в точности тогда, когда а ЛА а' = и и Ь Лн 6' = 6. Но эти два условия те же, что и а <л а' и Ь <и Ь'. Произведение решеток — операция ассоциативная, так что можно показать, что правила (9.2) и (9.3) распространяются на любое количество решеток, т.е. если даны решетки (А„Л;), г = 1,2,...,к, то произведение всех /с решеток в указанном порядке имеет область определения А, х Аз х х Аы оператор сбора, определяемгяй как (аыаз,...,аь) Л (ЬыЬз,...,Ьь) = (а1 Л Ьыаз Л Ьз,...,аь Л Ьь), и частичный порядок (аы аъ, аь) < (Ьы Ьг,..., Ьь) тогда и только тогда, когда а, < 6, для всех г Высота полурешетки Получить информацию о скорости сходимости алгоритма анализа потока данных можно путем изучения связанной с ним полурешетки.
Восходящей кепочкой в частично упорядоченном множестве (К, <) является последовательность, в которой хз < хз « .. х„. Высота полурешетки представляет собой наибольшее количество отношений < в восходящей цепочке, т.е. высота на единицу меньше количества элементов в такой цепочке. Например, высота полурешетки достигающих определений программы с п определениями равна и.
Показать сходимость итеративного алгоритма потока данных существенно проще, если полурешетка имеет конечную высоту. Ясно, что конечную высоту имеет полурешетка, состоящая из конечного множества значений; возможна также ситуация, когда решетка с бесконечным количеством значений также имеет конечную высоту. Соответствующим примером является решетка, используемая в алгоритме распространения констант, который будет подробно рассмотрен в разделе 9А.
9.3.2 Передаточные функции Семейство передаточных функций Е: Ъ' — 1' в структуре патока данных обладает следующими свойствами. 1. Г содержит тождественную функцию 1, такую, что 1(х) = х для всех х из Ъ'. 2. Е замкнуто относительно композиции, т.е. для любых двух функций г" и д из Е функция 6, определяемая как 6 (х) = д (г' (з)), также принадлежит Е. 751 9.3. Основы анализа потока данных Пример 9.19.
В случае достигающих определений тождественная функция г представляет собой частный случай, когда лен и й!1 являются пустыми множествами. Замкнутость относительно композиции фактически была показана в разделе 9.2.4; вкратце повторим здесь это доказательство. Предположим, что у нас есть функции !~ (х) = С10 (х — К ) и !г(х) = Сг 0 (х — Кг) Тогда Ь (Л (х)) = Сг 0 ((С10 (х — К|)) — Кг) Правая часть приведенной формулы алгебраически эквивалентна (С, 0 (С1 — Кг) ) 0 (х — (К1 0 Кг) ) Если положить К = К1 0 Кг и С = Сг 0 (С1 — Кг), то композиция функций !1 и !г принимает вид ! (х) = С О (х — К), что делает ее принадлежащей семейству К. Если рассмотреть доступные выражения, то можно применить те же аргументы, которые использованы для достигающих определений, и показать как наличие тождественной функции в семействе Г, так и его замкнутость относительно композиции.
и Монотонные структуры Чтобы итеративный алгоритм потока данных работал, структура потока данных должна удовлетворять еще одному условию. Мы говорим, что структура монотонна, если при применении любой передаточной функции ! из г к двум членам г', первый из которых не превышает второй, полученный результат для первого члена не превышает результат вычислений для второго члена. Формально структура потока данных (27, г', 'г", Л) монотонна, если из х < у следует ! (х) < ! (у) для всех х и у из Ъ' и ! из г (9.4) Монотонность может быть определена и следующим эквивалентным образом: !(хну) < !(х) Л !(у) для всех х и у из Ъ' и ! из г (9.5) Уравнение (9.5) гласит, что если собрать два значения и применить передаточную функцию !, то результат не превзойдет результат, полученный путем применения ! к отдельным значениям с последующим их сбором.
Эти два определения монотонности кажутся слишком различными, так что они оба оказываются весьма полезны — в разных ситуациях мы будем пользоваться разными определениями. Ниже приведен набросок доказательства их эквивалентности. 752 Глава 9. Машинно-независимые оптимизации Сначала выведем (9.5) из (9.4). Поскольку х Л у представляет собой наибольшую нижнюю границу х и у, мы знаем, что хЛу<хихЛу<у Таким образом, согласно (9.4) 1 (х Л у) < 1(х) и 1 (х Л у) < ) (р) Поскольку 1" (х) Л 1 (у) представляет собой наибольшую нижнюю границу 1'(х) и 1' (у), мы получаем (9.5). Теперь предположим, что выполняется (9.5), и докажем, что при этом выполняется (9.4). Мы принимаем, по .г < р, и используем (9.5) для того, чтобы заключить, что 1' (х) < 1' (у), что докажет (9.4). Уравнение (9.5) гласиг, что 1(.гЛу) < 1(х)Л /,'р) Но поскольку мы предположили, что з '- у, но определению .г л у -: х.
Таким образом, (9.5) приходит к виду / (т) < 1 (х) Л 1 (у) Поскольку 1 (х) Л 1' (у) представляет собой наиболыную нижнюю границу 1'(х) и 1' (у), мы знаем, что 1' (х) Л 1' (у) < 1' (у). Таким образом. Х (х) : Х (х) ' 1'(у) < 1 (у) и из (9.5) следует (9.4). Дистрибутивные структуры Зачастую структура удовлетворяет более строгому, чем (9 5), условию, которое мы называем условием дисв~рнбутнвносвш: Г (х Л и) =- Г (х) л Г (у) для всех:г и у из 1' и,г из К Безусловно, если а = б, то в соответствии со свойством ндемпотентности иЛБ = о.
так что а < 6. Таким образом, листрибутнвность влечет за собой монотонность (однако обратное неверно). Пример 9.20. Пусть р и х — множества определений в структуре достигающих определений. Пусть 1' — функция, определяемая уравнением Г (х) =- С 0 (х — К) для некоторых множеств определений С и К. Можно убедиться, что структура достигающих определений удовлетворяет условию дистрибутивности, проверив, что С 0 ((у 0 ") — К) = (С 0 (у — К)) 0 (С 0 (г — К)) 753 9.3. Основы анализа потока данных Зто уравнение только кажется страшным. Начнем с определений, входящих в С. Очевидно, что эти определения входят в множества, определяемые как левой, так и правой частями уравнения.
Таким образом, необходимо рассмотреть толы<о определения, не входящие в С. В этом случае можно убрать С из уравнения и проверить выполнение уравнения (у О .) — К =- (р — К) О (- — К) Это тождество элементарно проверяется при помощи диаграммы Вепна. 9.3.3 Итеративный алгоритм в обобщенной структуре Можно обобщить алгоритм 9.11 для работы с большим количеством задач потоков данных. Алгоритм 9.21.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
