А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 158
Текст из файла (страница 158)
На втором шаге выполняется поиск наиболее раннего разреза среди всех, которые устраняют как можно большее количество избыточных вычислений без дублирования кода и без внесения нежелательных вычислений. На этом шаге вычисления размещаются в точках программы, где значения их результатов впервые становятся ожидаемыми. На третьем шаге разрез перемещается вниз к точке, где любые задержки будут приводить либо к изменениям семантики программы, либо к появлению избыточности.
Четвертый, последний шаг представляет собой простой проход для очистки кода путем удаления присваиваний временным переменным, используемым только один раз. Каясдый 776 Глава 9. Машинно-независимые оптимизации шаг завершается проходом по потоку данных: второй и третий шаги представляют собой задачи в прямом направлении потока данных, а первый и четвертый |паги— в направлении, обратном направлению потока данных. Обзор алгоритма 1. Найти все выражения, ожидаемые в каждой точке программы, с использованием прохода в направлении, обратном потоку данных.
2. Второй шаг размещает вычисление там, где значения выражений впервые становятся ожидаемыми вдоль некоторого пути. После размещения копий выражения в местах, где выражение впервые становится ожидаемым, это выражение будет достулнььи в точке р программы, если оно было ожидаемо вдоль всех путей, достигающих р. Доступность может быть разрешена с использованием прохода в прямом направлении потока данных. Чтобы разместить выражения в как можно более ранних позициях, следует просто найти те точки программы, в которых выражения ожидаемы, но не доступны. 3.
Выполнение выражения, как только оно становится ожидаемым, может дать значение задолго до его использования. Выражение откладываемо (роз|ропаЫе) в точке программы, если оно ожидаемо, но еще не было использовано ни на каком пути, ведущем к этой точке. Найти откладываемые выражения можно с использованием прохода в прямом направлении потока данных. Выражения размещаются в тех точках программы, где они перестают быть откладываемыми. 4. Простой заключительный проход в направлении, обратном потоку данных, используется для устранения присваиваний временным переменным, которые используются в программе только один раз.
Предварительные шаги Теперь представим алгоритм отложенного перемещения кода полностью. Чтобы упростить задачу, полагаем, что изначально каждая инструкция содержится в базовом блоке, состоящем из одной этой инструкции, а новые вычисления выражений вносятся только в начало блока. Чтобы гарантировать, что такое упрощение не снижает эффективность алгоритма, мы вставляем новый блок между источником и приемником ребра, если приемник имеет более одного предшественника. Очевидно, что таким образом обрабатываются все критические ребра программы.
Семантика каждого блока В абстрагируется с использованием двух множеств: множество е изеп представляет собой множество выражений, вычисляемых в В, а е Ы/и — множество уничтоженных выражений, т.е. выражений, операнды которых определяются в В. Пример 9.26 будет использоваться в процессе рассмот- й~ Р о !! й» о Р й~ Е о ж а И Д О, л ж > ~О Р 4 Ф Я 2 й ОЭ > .Ф о й Ж Ы Й~ и й~ Ъ О а «3 й~ ъ Ъ ~й С), П~ Ъ Ъ с й~ ~О о о й~ Ъ ~3 !! й~ и Ъ Г~ ~и о и о э О~ х Ъ Щ С: Г э Щ Ъ ! Ъ с ы о о Х о Р' И Ф о Ф' К х о р й ж Р и о х ОХ Р, а О У м О' 779 9.5.
Устранение частичной избыточности Заполнение квадрата Ожидаемые выражения (иногда называемые в литературе очень занятыми выражениями (чегу Ьцау ехргеягйопз)) представляют собой тнп анализа потока данных, с которым мы ранее не сталкивались. Мы уже встречались с обратными структурами, такими как анализ живых переменных (раздел 9.2.5), и со структурами, оператором сбора в которых являлось пересечение, такими как доступные выражения (раздел 9.2.6), но сейчас мы впервые столкнулись с анализом, обладающим обоими этими свойствами. Почти все анализы, с которыми мы сталкивались, можно поместить в квадратную таблицу, разбив их на четыре группы — в зависимости от направления (прямое или обратное) и оператора сбора (объединение или пересечение).
Заметим также, что анализы с обьединением сводятся к вопросу о существовании пути, вдоль которого истинно некоторое условие, в то время как анализы с пересечением выясняют, истинно ли некоторое условие вдоль всех возможных путей. Ожидаемые выражения Вспомним, что выражение Ь + с является ожидаемым в точке р программы, если все пути, ведущие из точки р, в конечном счете вычисляют значение 6+ с с использованием значений 6 и с, доступных в этой точке.
На рис. 9.33, а все блоки, на входе в которые ожидается Ь + с, выделены серым цветом. Выражение Ь+ с ожидаемо в блоках Вз, В4, Вв, Ва, Вт и Вя. Оно не ожидаемо на входе в блок Вз, поскольку значение с переопределяется в этом блоке, а следовательно, значение Ь+ с, которое могло бы быть вычислено в начале блока Вз, не используется вдоль любого пути. Выражение Ь + с не является ожидаемым на входе в блок Вы поскольку оно не нужно вдоль пути от В1 к Вз (хотя и используется на пути В1 — Вь — Вв). Аналогично это выражение не является ожидаемым в начале блока Ва из-за ветвления от Ва к Вы.
Ожидаемость выражения может осциллировать вдоль пути, что на рисунке иллюстрируется путем Вт — ~ Ва — Вя. Уравнения потока данных для задачи ожидаемых выражений показаны на рис. 9.34, а. Анализ использует проход в обратном направлении. Ожидаемое выражение на выходе из блока В является ожидаемым на входе в этот блок, только если оно не входит в множество е кшн. Кроме того, блок В генерирует в качестве вновь используемых множество выражений е изен. На выходе из программы ни одно выражение не является ожидаемым.
Поскольку нас интересует поиск выражений, ожидаемых вдоль каждого последующего пути, оператор сбора представляет собой пересечение. Следовательно, внутренние точки должны быть 780 Глава 9. Машинно-независимые оптимизации инициализированы универсальным множеством (1, как в случае задачи о доступ- ных выражениях из раздела 9.2.6. Доступные выражения В конце второго шага копии выражения будут размещены в точках программы, где они впервые становятся ожидаемыми.
В данном случае выражение яш1яется доступным (ача11а61е) в точке р программы, если оно ожидаемо вдоль всех путей, достигающих р. Задача аналогична задаче о доступных выражениях из раздела 9.2.6. Передаточная функция, используемая здесь, немного отличается от передаточной функции для доступных выражений из раздела 9.2.6. Выражение доступно на выходе из блока, если оно 1) либо а) доступно на входе, либо б) находится в множестве ожидаемых выражений на входе (т.е. может стать доступным, если мы будем вычислять его здесь) 2) не уничтожается в блоке. Уравнения потока данных для доступных выражений показаны на рис. 9.34, б. Чтобы не запутаться в смысле обозначений ХЮ, к имени результата анализа добавлено [В] Зп.
При использовании стратегии наиболее раннего возможного размещения множество выражений, размещаемых в блоке В, т.е. еагйезг[В], определяется как множество ожидаемых, но еше не доступных выражений: еаВГезт [В] = апГГсюратей [В] Зп — амщфаЫе [В] Зп Пример 9.27. Выражение 6+с в графе потока на рис. 9.35 не является ожидаемым на входе в блок Вз, но ожидаемо на входе в блок В4. Однако нет необходимости вычислять выражение 6+ с в блоке В4, так как оно уже доступно благодаря блоку Вз. о Пример 9.28. На рис. 9.33, а затененными показаны блоки, для которых выражение 6+ с не является доступным; это блоки Вы Вз, Вз и Вз. Позиции раннего размещения представлены серыми прямоугольниками с черными тенями — это блоки Вз и Вз.
Заметим, например, что выражение 6+ с рассматривается как доступное на входе в блок В4, поскольку существует путь В1 — Вз — Вз ~ В4, вдоль которого 6+ с ожидаемо как минимум один раз (в данном случае — в Вз) и с начала блока Вз ни 6, ни с не переопределяются. о 9.5. Устранение частичной избыточности в, Рис. 9.35. Граф потока для примера 9.27, иллюстрирующий использование доступности Откладываемые выражения Третий шаг откладывает вычисления выражений иа как можно более поздний срок, сохраняя при этом семантику программы и минимизируя избыточность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
