А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 168
Текст из файла (страница 168)
9.59. Код на рнс. 9.55, присваивания в котором заменены аффинными выражениями оз ссылочных переменных ( н з Предостережение о передаточных функциях для отображений значений В нашем определении передаточных функций от символических отображений имеется тонкость, заключающаяся в выборе способа выражения результата вычисления. Если т — отображение входа передаточной функции, гп (т) просто означает "какое бы значение переменная а ни принимала на входе". Мы пытаемся выразить результат передаточной функции как аффинное выражение от ссылочных переменных, используемых входным отображением. Вы должны правильно интерпретировать выражения наподобие 7" (т) (а), где г' — передаточная функция, зп — отображение, а к — переменная.
Как принято в математике, мы применяем функции слева направо, так что сначала вычисляется значение ('(т), которое представляет собой отображение. Поскольку отображение является функцией, оно затем может быть применено к переменной х для получения значения. !. Если я не является инструкцией присваивания, то 7', является тождественной функцией. ного выражения значений справа от знака присваивания. Значения всех остальных переменных остаются неизменными. Передаточная функция инструкции з, обозначаемая как 7„определяется следующим образом.
826 Глава 9. Машинно-независимые оптимизации 2. Если з — инструкция присваивания переменной х, то т(о) для всех переменных в ф х; со + с1т(у) + сгт(з) если х присваивается со + с1у+ сгз, (с1 = О, или т (у) ф млл) и (сг = О, или т (з) ф нлл); 1,(т)(х) = ЖАА в противном случае. Выражение со+ с1 т (у) + сгт (а) предназначено для представления всех возможных видов выражений, включающих произвольные переменные у и з из правой части присваивания переменной х, которые являются аффннными преобразованиями значений этих переменных.
Во многих случаях одна или несюлью из констант со, с1 и сг равны О. Пример 9.56. В случае присваивания х = у+а со = 0 и с1 = сг = 1. Если присваивание — х = у/5, то со = сг = О, а с1 = 1/5. а Композиция передаточных функций Для вычисления гг о гы где (~ и гг определены в терминах входного отображения т, мы подставляем вместо значения т (о;) в определении Ь определение г1 (т) (о;). Все операторы над значениями нлл заменяются нлл, т.е. 1. если гг(т) (о) = 1члл, то (гг с ~г) (т) (о) = хлл; 2. если гг (т) (о) = со + 2, с;т (о,), то хлл, если г1(т)(о,) = 1члл для некоторых 1 ф О, с, ф 0 со + 2т, с;Л(т)(о,) в противном случае.
(Уг о 1!Нткс) = Пример 9.57. Передаточные функции блоков из примера 9.54 могут быть вычислены путем композиции передаточных функций инструкций, составляющих блоки. Эти передаточные функции показаны на рис. 9.60. а Решение задачи потока данных Для входных и выходных значений потока данных блока Вз на гтй итерации внутреннего цикла и на 1-й итерации внешнего цикла используем обозначения пч,1[Вз] и ООт; [Вз]. Для тех же значений на 1-й итерации внешнего цикла в других блоках используем обозначения пч, [Вь] и опт, [Вь].
Можно также показать, что символические отображения, показанные на рис. 9.58, удовлетворяют ограничениям, навязанным передаточными функциями и показанным на рис. 9.61. 827 9.8. Символический анализ Рис. 9.60. Передаточные функции нз примера 9.54 для всех Вь 1<1<10 1<1<100 2 <7 <10 2 < 1 < 100 1 < 1 < 100 Рнс. 9.6! . Ограничения, которые удовлетворяются на каждой итерации вложенных циклов Первое ограничение гласит, что выходное отображение базового блока получается путем применения передаточной функции блока ко входному отображению. Остальные ограничения говорят о том, что выходное отображение базового блока должно быть не меньше, чем входное отображение следующего блока в порядке выполнения.
Заметим, что наш итеративный алгоритм потока данных не позволяет получить приведенное решение из-за отсутствия концепции выражения значений потока данных через номер выполняемой итерации. Для поиска подобных решений, как вы увидите в следующем разделе, может применяться анализ на основе областей.
9.8.3 Символический анализ на основе областей Можно расширить анализ на основе областей, описанный в разделе 9.7, для поиска выражений переменных на 1-й итерации цикла. Символический анализ на основе областей имеет восходящий и нисходящий проходы, как и другие алгоритмы на основе областей. Восходящий проход суммирует влияние области при помощи передаточной функции, которая получает символическое отображение на входе н возвращает символическое отображение на выходе. При нисходящем проходе значения символического отображения распространяются вниз ко внутренним областям. Различие заключается в обработке циклов. В разделе 9.7 влияние циклов подытоживается при помошн оператора замыкания.
Для данного цикла с телом 1' его замыкание 7'* определяется как бесконечный сбор всех возможных количеств применений 1. Однако для поиска переменных индукции надо определить, является опт [Вь] опт [В1] опт, [Вг] опт.у . [Вз] ость ш [Вз] опт,, [В4] = Хв (пч [Вь]) э пч~ [Вг] ~ эвй 1 [Вз] ~ ) пчо [Вз], ~) Щ [В4], ) пч, [Вг], 828 Глава 9. Машинно-независимые оптимизации ли значение переменной аффинной функцией от количества выполненных итераций, Символическое отображение должно быть параметризовано количеством выполненных итераций.
Более того, если мы знаем общее количество выполненных итераций цикла, то можем использовать это число для поиска значений переменных индукции после цикла. Так, в примере 9.54 мы утверждали, что а имеет значение г после выполнения г-й итерации. Поскольку цикл состоит из 100 итераций, по его завершении значение а должно быть равно 100. Далее мы определим примитивные операторы сбора и композиции передаточных функций для символического анализа, а затем покажем, как они используются при выполнении анализа переменных индукции на основе областей. Сбор передаточных функций При вычислении сбора двух функций значение переменной равно балл, если только две функции не отображают переменную на одно и то же значение, и это значение не равно млл.
Таким образом, ); (т) (и), если )1 (т) (и) = )з (т,) (с), ()1 Л Уя) (гп) (и) = ~ нАА в противном случае. Параметризованные композиции функций Чтобы выразить переменную как аффинную функцию от индекса цикла, требуется вычислить влияние композиции функции, взятой некоторое количество раз. Если влияние одной итерации подытоживается передаточной функцией )', то влияние выполнения 1 итераций для некоторого г > 0 обозначается как )'. Заметим, что при г = 0 мы получаем тождественную функцию: ~' = У" = Е Переменные в программе разделяются на следующие категории.
1. Если ~ (т) (гс) = гп (х) + с, где с — константа, то ~' (гп1 (х) = т (х) + с1 для каждого значения ю'. > О. Мы говорим, что х является базовой переменной индукции (Ьаз1с 1пбпсйоп чапаЫе) цикла, тело которого представлено передаточной функцией 1. 2. Если г' (т) (ш) = т (ш), то г" (пв) (т) = т (х) для всех г > О. Переменная:с остается неизменной после любого количества итераций цикла с передаточной функцией 1.
Мы говорим, что х является сичволической констаншой цикла. 3. Если )' (т) (к) = со + с1пт (х1) + . + с„т (ж„), где каждая переменная хь является либо базовой переменной индукции, либо символической константой, то при г > 0 ~' (т) (х) = со + с1 )'* (т) (х1) + . + с„,1"' (т) (х„) 829 9.8. Символический анализ Мы говорим, что х также является переменной индукции, но не базовой. Заметим, что приведенная формула не применима при 1 =- О. 4. Во всех прочих случаях ~' (т) (х) = 1члл. Чтобы найти влияние выполнения фиксированного количества итераций, надо просто заменить 1 этим числом. В случае, когда количество итераций неизвестно, 1' дает значение в начале последней итерации. В этом случае инвариантными относительно цикла переменными являются только те переменные, значения которых могут быть выражены в аффинном виде: т (о), если 1 (т) (и) = т (е), (т) (о) = нлл в противном случае. Пример 9.58.
Для самого внутреннего цикла из примера 9.54 влияние выполнения 1 > О итераций подытоживается в Я,. Из определения ~из мы видим, что а и Ь являются символическими константами, с — базовой переменной индукции, поскольку на каждой итерации она увеличивается на 1. Переменная Н является переменной индукции, поскольку она является аффинной функцией от символической константы 6 и базовой переменной индукции с. Таким образом, т (а), Ув, ( ) ( ') = т (Ь), т(с) + г, т(6) + т(с) + г, Если мы не можем сказать, сколько выполняется итераций блока Вз, то для выражения условий в конце цикла мы должны использовать не ~', а 1'*. В нашем случае мы получим если е = а, если о = Ь, если е = с, Уй, (т) (е) = мАА, если и = и.
Алгоритм, основанный на областях Алгоритм 9.59. Символический анализ на основе областей Вход: приводимый граф потока С. Выход: символические отображения пч [В) для каждого блока В из С. Метод: вносим следующие изменения в алгоритм 9.53. т (а), т (6), 1ЧАА, если е = а, если е = 6, если и = с, если е = д. взо Глава 9. Машинно-независимые оптимизации 1. Изменяем способ построения передаточной функции для области цикла. В исходном алгоритме мы использовали передаточную функцию ~й1и]В] для отображения символического отображения на входе области цикла В на символическое отображение на входе области тела Я после выполнения неизвестного количества итераций.
Она определена как замыкание передаточной функции, представляющей все пути, ведущие назад ко входу в цикл, как показано на рис. 9.50, б. Здесь же мы определяем ~й; 1и]В] как представляющую влияние выполнения от начала области цикла до входа в т-ю итерацию, т.е. г — 1 г'й,йиг]я] = Л Уо;ост]В] т Предшеетвеииики В ззтоловкв Я в й 2. Если количество итераций области известно, итог области вычисляем, заменяя з фактическим количеством итераций. 3. При нисходящем проходе для того, чтобы найти символическое отображение, связанное со входом т'-й итерации цикла, вычисляем 1й0,1и]В].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
