А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 150
Текст из файла (страница 150)
Как и в случае достигающих определений, граничное условие — Онт !ВХОД1 = кэ, поскольку при выходе из входного узла доступных выражений нет. Наиболее важное отличие состоит в том, что оператор сбора в данном случае — не объединение, а пересечение. Пересечение множеств используется потому, что выражение доступно в начале блока только тогда, когда оно доступно в конце всех его предшссэ вснников (в отличие от определения, которое достигает начала блока, если дости1 ает конца хотя бы одного из его предшественников).
Использование оператора С! вместо 0 делает поведение уравнений для доступных выражений отличающимся от поведения уравнений для достигающих определений. В то время как ни одно из множеств не представляет собой единственное решение, в случае дос~игающих определений мы получаем наименьшее решение, соответствующее определению достижимости, и получаем его, начиная с предположения о недостижимости чего бы то ни было в какой угодно точке, а затем "наращиваем" ею. При этом подходе мы никогда не предполагаем, что определение д можсз достичь гочки р, до тех пор, пока не будет найден реальный путь распространения г! до р. В отличие от этого для уравнений доступных выражений мы хотим получить решение с наибольшими множествами доступных выражений, а потому начинаем со слишком большою приближения н идем по пути сю уменыпения.
ТЗ8 Глава 9. Машинно-независимые оптимизации Может показаться неочевидным, что, начав с предположения "доступно все (т.е. множество сГ) и везде, за исключением конца входного блока" и удаляя только те выражения, для которых мы находим пути, по которым они становятся недоступны, мы получим множество истинно доступных выражений. В случае доступных выражений консервативным является получение подмножества точного множества доступных выражений, и это именно то, что мы делаем. Аргументом в пользу консервативности подмножеств является наше предполагаемое использование информации для замены вычисления доступного выражения предварительно вычисленным значением. Отсутствие информации о доступности выражения только предотвратит возможное изменение кода, в то время как предположение о доступности выражения, когда на самом деле это не так, может привести к некорректному изменению программы, которое изменит вычисляемые ею результаты.
Пример 9.16. Рассмотрим единственный блок Вз на рис. 9.19, чтобы проиллюстрировать влияние начального приближения опт [Вз] на пч [Вз]. Обозначим через С и К соответственно е яелп, и е /иПп,. Уравнениями потока данных для блока Вз являются 1х [Вз] = 013т [Вз] Й Опт [Вз] опт[В,] = О О [пч[В,] — К) Эти уравнения могут быть переписаны в виде рекуррентных соотношений, в которых Ху и Оу означают з-е приближения пч [Вз] и опт [Вз] соответственно: Р+' = 00Т[В1] ОО' о"" = а и ф+' — к) Рнс. 9.19. Инициализация множеств опт значениями И слишком ограничивающая 739 9.2. Введение в анализ потоков данных Почему работает алгоритм дла доступных выражений Мы должны пояснить, почему выбор начальных значений опт (за исключением входного блока), равных У, множеству всех выражений, приводит к консервативному решению уравнений потока данных, т.е.
что все найденные доступные выражения действительно доступны. Во-первых, поскольку в данной схеме потока данных операцией сбора является пересечение, любая причина, по которой выражение х+ у не является доступным в некоторой точке, будет распространяться по графу потока по всем доступным путям, пока выражение х + у не будет вычислено заново и не станет вновь доступным. Во-вторых, есть только две причины, по которым х+ у может быль недоступно. 1.
х + у уничтожается в блоке В, поскольку х или у определено без последующего вычисления х + у. В этом случае при первом применении передаточной функции 1п выражение а + у будет удалено из опт [В]. 2. т+ у никогда не вычисляется вдоль некоторого пути. Поскольку х + у никогда не появляется в опт [Вход] и никогда не генерируется вдоль рассматриваемого пути, можно показать по индукции по длине нуги, что х + у в конечном счете будет удалено из множеств пч и оп г вдоль этого пути. Таким образом, по окончании внесения изменений решение, полученное итеративным алгоритмом на рис.
9.20, будет включать только истинно доступные выражения. Начав с Оо = Э, мы получим 1' = Опт [В~] О Оо = О. Однако, если начать с Оо = У, то получим 1' = опт [В~] О Оо = опт [В~], как и должно было быть. Интуитивно решение, полученное при Оо = С~, более желательно, поскольку корректно отражает тот факт, что выражения в опт [В~] и не уничтоженные в Вз, остаются доступны в конце Вз. и Алгоритм 9.17. Доступные выражения Вход: граф потока, у которого для каждого блока В вычислены е Ы1п и е яелп. Начальный блок — Вп Выход: пч [В] и оот [В], множества выражений, доступных на входе и выходе из каждого блока В графа потока. Метод: выполняется алгоритм, приведенный на рис.
9.20. Пояснение шагов этого алгоритма аналогично пояснению к алгоритму на рис. 9.14. и 740 Глава 9. Машинно-независимые оптимизации Оот[Вход] = О; 1ог (каждый базовый блок В, отличный от входного) оот [В] = (т; ттЫ1е (внесены изменения в опт) 1ог (каждый базовый блок В, отличный от входного) ! опт [В] = е яелн а (пч [В] — е И11н ). Рис. 9.20. Итеративный алгоритм лля вычисления доступных выражений 9.2.7 Резюме В этом разделе мы рассмотрели три примера задач потоков данных: достигающие определения, активные переменные н доступные выражения. Как подытожено на рис.
9.21, каждая задача задается областью определения значений потока данных, его направлением, семейством передаточных функций, граничными условиями и оператором сбора. Обобщенно оператор сбора обозначен как Л. В последней строке таблицы показаны инициализирующие значения, использующиеся в итеративных алгоритмах.
Эти значения выбираются таким образом, чтобы алгоритм находил наиболее точное решение уравнений. Говоря строго, данный выбор не является частью определения задачи потока данных; это артефакт, необходимый для итеративного алгоритма ее решения.
Например, мы видели, как передаточная функция базового блока может быть получена путем композиции функций отдельных инструкций блока; аналогичный композиционный подход может использоваться и для вычисления передаточной функции для всей процедуры или для вычисления передаточной функции от входа процедуры до любой точки программы. Этот подход будет рассмотрен в разделе 9.7. 9.2.8 Упражнения к разделу 9.2 Упражнение 9.2.1. Для графа потока на рис.
9.! 0 (см. упражнения к разделу 9. ! ) вычислите а) множества яеп и lпд для каждого блока; б) множества !м и опт для каждого блока. Упражнение 9.2.2. Для графа потока на рис. 9.10 вычислите множества е вел, е ЫП, пч и Оцт для доступных выражений. Упражнение 9.2.3. Для графа потока на рис. 9.10 вычислите множества с1е7; изе, !н и оот для анализа активных переменных. .а Ъ х А х с с Х о о о с о Р с Сб РЪ ~ Х (И ~ о й~ Е а с~ ( М о Ю о с х й о.
с Ф о Ф О М с с о с с о о о с й Б о ~о С~ о с о с а\ о ь о с с 742 Глава 9. Машинно-независимые оптимизации ! Упражнение 9.2.4. Предположим, что У вЂ” множество комплексных чисел. Какие из приведенных операций могут служить в качестве оператора сбора для полурешетки на Ъ"? а) Сложение (а + 16) Л (с + м!) = (а + с) + г (6+ а). б) Умножение (а + !6) Л (с + 1г!) = (ас — ЬП) + г (ай + 6с). в) Покомпонентный минимум (а+16) Л (с+ Ы) = ппп(а, с) + !ваш(Ь,П).
г) Покомпонентный максимум (а+ 16) Л (с+ Ы) = шах(а, с) + гтах(6, д). ! Упражнение 9.2.5. Утверждается, что если блок В состоит из и инструкций и 1-я инструкция имеет множества яеп; и 1аПо то передаточная функция для блока В имеет множества яепв и Й?1в, определяемые как 1аПв = Ы11~ 0ЫПз О. 0Й?1 яепв — — яеп„0 (~еп„~ — Й?1„) 0 (Пепб а — ЙП„~ — 1аП„) 0 0 0 (ееп~ — ЙПз ЙПз ' — ЙПп) Докажите это утверждение по индукции по и. ! Упражнение 9.2.6. Докажите по индукции по числу итераций цикла Гог в строках 4-6 алгоритма 9.11, что нн одно из множеств пч или опт никогда не уменьшается. Иначе говоря, если в какой-то момент определение помещено в одно из этих множеств, то в последующем оно никогда не будет из него удалено. ! Упражнение 9.2.7.
Покажите корректность алгоритма 9.11, т.е. покажите, что а) если определение г! помещается в пч [Х] или опт [В], то существует путь от Ы к началу или концу блока В соответственно, вдоль которого переменная, определенная в П, не может быть переопределена; б) если определение д не помещается в пч [Ж] нли опт [В], то не существует пути от д к началу или концу блока В соответственно, вдоль которого переменная, определенная в д, не может быть переопределена. 1 Упражнение 9.2.8. Докажите следующие утверждения об алгоритме 9,14. а) Множества пч и опт никогда не уменьшаются.
б) Если переменная х помещена в пч [В] или опт [В], то существует путь от начала или конца блока В соответственно, вдоль которого х может быть использована. 743 9.3. Основы анализа потока данных в) Если переменная х не помещена в пч [В] или опт[В], то не существует пути от начала или конца блока В соответственно, вдоль которого х может быть использована. ! Упражнение 9.2.9. Докажите следующие утверждения об алгоритме 9.17. а) Множества пч и Оит никогда не растут; т.е.
последовательные значения этих множеств являются подмножествами !не обязательно истинными) их предыдущих значений. б) Если выражение е удалено из пч [В] или опт(В], то существует путь от входа графа потока к началу или концу блока В соответственно, вдоль которого е либо никогда не вычисляется, либо после его последнего вычисления один из его аргументов может быть переопределен. в) Если выражение е остается в пч [В] или опт (В], то вдоль каждого пути от входа графа потока к началу или концу блока В соответственно вычисляется е, и после его последнего вычисления ни один из его аргументов не может быть переопределен. ! Упражнение 9.2.10. Проницательный читатель заметит, что в алгоритме 9.11 можно сэкономить некоторое время путем инициализации опт (В] значением яелп для всех блоков В.
Аналогично в алгоритме 9.14 можно инициализировать пч [В] значением яелп. Мы не поступаем так из соображений единообразия в изложении темы, как будет видно при рассмотрении алгоритма 9.21. Однако можно ли в алгоритме 9.17 инициализировать множества оит [В] значениями е яелп? Поясните ваш ответ. ! Упражнение 9.2.11. Наши анализы потоков данных не используют преимущества семантики условных выражений. Предположим, в конце базового блока обнаружена проверка наподобие хй (х < 10) досо Как можно воспользоваться тем, что проверка т ( 10 означает углубление наших знаний о достигающих определениях? Под углублением знаний здесь предполагается, что мы устраняем некоторые достигающие определения, которые в действительности не в состоянии достичь определенной точки программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
