А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 153
Текст из файла (страница 153)
Итеративное решение обобщенной задачи пояска данных Вход: структура потока данных со следующими компонсн гам и. 1. граф потока данных с отдельно помеченными входным и выхолпым узлами; 2. направление потока данных Й; 3. множество значений 1', 4. оператор сбора А; 5. множество функций Г, где гп из Е представляет собой псрслагочную функцию для блока В; 6.
константное значение пвхол или цвмход из Г, предстае1я<о<псе собой граннчн<го условие для прямой и обратной структуры соотвсзствснно. Выход: значения из 1' для пч [В] и 0<от[В] для каждого блока В в графе потока данных. Метод: алгоритмы для решения прямой и обратной задач потока данных показаны на рис.
9.23, а и б соответственно. Как и в случае хорошо знакомых итеративных алгоритмов для потоков данных из раздела 9.2, мы вычисляем <м и о<эт для каждого блока как ряд последовательных приближений. о Можно записать прямую и обратную версии алгоритма 9.21 с функцией, реализующей оператор сбора, в качестве параметра. В качестве параметра выступает и функция, реализующая передаточную функцию для каждого блока. Сам граф потока и граничное значение также являются параметрами. Таким образом, разработчик компилятора может избежать записи базового итеративного алгоритма для каждой структуры потока данных, используемой на стадии оптимизации. Можно воспользоваться рассматривавшейся абстрактной схемой для доказательства ряда полезных свойств итеративного алгоритма.
754 !) 2) 3) 4) 5) б) а) Итеративный алгоритм для прямой задачи потока данных 1. Если алгоритм 9.21 сходится, то получающийся результат является решением уравнений потоков данных. 2. Если структура монотонна, то найденное решение оказывается максимальной фиксированной точкой (шахнпшп Йхебро!и!) уравнений потоков данных. Максимальная фиксированная точка представляет собой решение, обладающее тем свойством, что в любом другом решении значения пч [В] и Опт [В] не превышают (в смысле оператора () соответствующих значений максимальной фиксированной точки. 3. Если полурешетка структуры монотонна и имеет конечную высоту, то алгоритм гарантированно сходится.
Докажем указанные свойства для прямой структуры. Доказательство для обратной структуры, по сути, то же самое. Показать первое свойство очень просто. Если при выходе из некоторой итерации цикла чпЫ!е уравнения не удовлетворяются, то в Оит (в прямом случае) или в пч (в обратном случае) будет внесено по крайней мере одно изменение, так что потребуется вновь вернуться в цикл и выполнить очередную его итерацию. Чтобы доказать второе свойство, сначала покажем, что значения пч[В] и Опт [В] для любого В в процессе выполнения итераций алгоритма могут толь- 1) 2) 3) 4) 5) 6) Глава 9.
Машинно-независимые оптимизации Оит [ВХОД] = пв,„л,. 1ог (каждый базовый блок В, отличный от входного) ООт [В] = Т; пгп11е (внесены изменения в Оит) 1ог (каждый базовый блок В, отличный от входного) ( ЛЧ [В] — ~ Р— препп~епевенннк ВООт [Р] Оит[В] =- (В(!и[В]); цЧ [ВЫХОЛ] = пВыхоп 1ог (каждый базовый блок В, отличный от выходного) лч [В] = Т; зч)з1!е (внесены изменения в !и) 1ог (каждый базовый блок В, отличный от выходного) ( ОПТ [В] = Л — преемник ВПЧ [Я! пч[В] = (В(опт[В]); б) Итеративный алгоритм для обратной задачи потока данных Рис. 9.23.
Прямая и обратная версии итеративного алгоритма 755 9ль Основы анализа потока данных ко уменьшаться (в смысле отношения < для решетки). Это утверждение можно доказать по индукции. БАзис в качестве базиса индукции надо показать, что значения пч (В) и опт [В] после первой итерации не больше, чем инициализируюшие значения. Это утверждение тривиально, поскольку пч [В) и опт [В) для всех блоков В, отличающихся от входного, инициализируются значением Т. Индукция: предположим, что после и-й итерации все значения не больше значений после (Й вЂ” 1)-й итерации, и покажем, что то же самое выполняется и на (й + 1)-й итерации по отношению к /с-й.
Строка 5 на рис. 9.23, а содержит пч [В) = ' 'Р— предшественник сзошт [Р) Воспользуемся обозначениями пч [В]' и огзт[В)' для значений пч [В) и опт[В) после итерации г. Если опт [Р) < огзт [В), то в силу свойств оператора сбора пч [В] +~ < пч [В) . Далее, строка 6 гласит опт [В) = 1п (пч [В) ] В силу монотонности из пч [В] ~~ < пч [В) вытекает Огзт [В]~ ~~ < Огзт [В]~. Заметим, что любые изменения значений пч [В) и огзт [В) обязаны удовлетворять уравнению.
Операторы сбора возвращают наибольшую нижнюю границу своих операндов, а передаточные функции возврашают только решения, согласующиеся с самим блоком и заданными входными данными. Таким образом, по завершении работы итеративного алгоритма в результате должны получиться значения, которые как минимум не меньше соответствующих значений любого другого решения, т.е.
результатом работы алгоритма 9.21 является максимальная фиксированная точка уравнений. Наконец, рассмотрим третье утверждение, в котором структура потока данных имеет конечную высоту. Поскольку значения каждого и~ [В) и огзт[В) при каждом изменении уменьшаются, а алгоритм завершает свою работу при отсутствии изменений, он гарантированно сходится после количества итераций, не превышающего произведения высоты структуры и количества узлов графа потока. 9.3.4 Смысл решения потока данных Мы знаем, что решение, найденное при помощи итеративного алгоритма, представляет собой максимальную фиксированную точку, но что представляет собой данное решение с точки зрения семантики программы? Чтобы понять решение схемы потока данных (Р, г', К, Л), опишем вначале, каким должно быть идеальное решение структуры.
Мы покажем, что в общем случае это идеальное решение не может быть получено, но алгоритм 9.21 дает нам консервативное приближение к этому идеалу. 756 Глава 9. Машинно-независимые оптимизации Идеальное решение Без потери общности будем считать, что интересующая нас структура потока данных является задачей прямого потока. Рассмотрим входную точку базового блока В.
Идеальное решение начинается с поиска всех возможных путей выполнения, ведущих от входной точки программы к началу В. Путь "возможен", только если некоторое вычисление программы следует в точности по этому пути. Идеальное решение должно вычислить значение потока данных в конце каждого возможного пути и применить к найденным значениям оператор сбора для получения их наибольшей нижней границы. Тогда никакое выполнение программы не в состоянии привести к меньшему значению для данной ее точки.
Кроме того, эта граница плотная; не существует большего значения потока данных, которое являлось бы наибольшей нижней границей значения, вычисленного по всем возможным путям графа потока к базовому блоку В. Попытаемся определить идеальное решение более формально. Пусть ~В— передаточная функция для каждого баювого блока В в графе потока. Рассмотрим путь Р = Вход — В1 — Вз - — Вь з — Вь от входного узла к некоторому блоку Вы Путь программы может содержать циклы, так что в пути Р один и тот же базовый блок может появляться неоднократно.
Определим передаточную функцию з'р для Р как композицию з'В,, з'В„..., з'Вь, Обратите внимание, что уВ, не является частью данной композиции, отражая тот факт, что путь достигает начала базового блока Ввы но не его конца. Значение потока данных, создаваемое этим путем, представляет собой (р (пвкод), где пвход— результат константной передаточной функции, представляющей начальный входной узел.
Идеальным результатом для блока В, таким образом, является Л Л (пвход) пэеАь [В[ =- Р— возможный пугь оз вколв к В Мы заключаем, что в терминах теоретического частичного порядка решетки < для рассматриваемой структуры ° любой ответ, больший, чем пэель, неверен; ° любое значение, меньшее, чем идеальное, илн равное ему, консервативно, т.е. безопасно. ~заметны, что в прямой задаче значение юни. (В] соответствует значению пч (В]. В обратной задаче, которую мы здесь не рассматриваем, мы бы определнлн ювль (В] как идеальное значение опт [В].
Интуитивно значение, более близкое к идеальному, является более точным.ч Чтобы увидеть, почему любые решения должны не превосходить идеальное, заметим, что для любого блока любое решение, большее, чем пэбл~., может быть 757 9хй Основы анализа потока данных получено путем игнорирования некоторого пути выполнения, по которому может пойти программа; мы не можем гарантировать, что вдоль этого пути не произойдет что-то, что сделает недействительным все улучшения программы, которые могли бы быть сделаны на основе большего решения.
И наоборот, любое решение, меньшее, чем !пеле, может рассматриваться как включающее некоторые пути, либо не существующие в графе потока, либо существующие, но гакис, по которым программа никогда не проследует. Это меньшее решение допускает только те преобразования, которые корректны для всех возможных выполнений программы, но может запрещать некоторые из преобразований, разрешенных решением 1ОЕл1.. Решение сбором по путям Однако, как говорилось в разделе 9.1, поиск всех возможных путей выполнения — задача неразрешимая. Следовательно, гребустся поиск приближенного решения.
В абстракции потока данных мы полагаем, что может быль пройден каждый путь в графе потока. Таким образом, мы можем определить решение сбором по путям (шее!-очег-ра1йз) для В как МОЕЯ = /~ 11 1пнх„,) П- путь от вховв ь Н Заметим, что, как и в случае идеального решения, мО1х !!З,~ в прямой структуре дает значения для ея 1В1: в случае обратного потока мог!В~ представляют собой значения О11т 1В1 Рассматриваемые в решении мОЕ пути прсдставлянп собой надмпожсство всех путей, которые могут быть выполнены.
Таким образом, решение мог собирает вместе не только значения потоков данных всех выполнимых путей, но и дополнительные значения, связанные с путями, которые не могут быть выполнены. Сбор идеального решения и дополнительных членов не можез дать решение, большее идеального. Таким образом, для всех В выполняется соотноьпсние мОР 1В) < 1пел$. !В1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
