А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 145
Текст из файла (страница 145)
Значение переменной 1 присваивается переменной с вместо выражения Н+ е на рис. 9.6, б. Поскольку 713 9.1. Основные источники оптимизации управление может достичь выражения с = 6+е как после присваивания переменной а, так и после присваивания 6, было бы некорректно заменять выражение с = с(+е присваиванием с = а или с = Ъ. П б) а) Рнс. 9.6.
Копирования, добавленные в процессе устране- ния общих подвыражений Идея, лежащая в основе преобразования распространения копий, заключается в применении с вместо и везде, где это возможно, после инструкции копирования и = ч. Например, присваивание х = сз в блоке Вб на рис. 9.5 является копированием. Применение распространения копий к Вб дает в результате код, показанный на рис. 9.7. Такое преобразование может показаться никаким не улучшением кода, но, как мы увидим в разделе 9.1.6, оно дает нам возможность удалить присваивание х. х = ~3 а(с21 = сб а(с41 = сз досо Вз Рнс. 9.7.
Базовый блок Вб после распространения копий 9.1.6 Удаление бесполезного кода Переменная в некоторой точке программы считается лсивой (1(че), или активной, если ее значение будет использовано в программе в последующем; в противном случае она считается мертвой (г(еаб). Очередная идея оптимизации касается мертвого, или бесполезного, кода, т.е. кода, вычисляющего значения, которые никогда не будут использованы.
Хотя программист вряд ли будет создавать такой код умышленно, он может возникнуть в результате предшествующих преобразований. Пример 9.4. Предположим, что переменная с(еЪпд может принимать значения ТЕ()Е или РА1 ЯЕ в различных точках программы и используется в инструкциях типа Н (с(еЪпд) ртхпт. 714 Глава 9. Машинно-независимые оптимизации Может оказаться, что компилятор сможет выяснить, что всякий раз по достижении этого кода с(еЬцд принимает значение ГАЬЯЕ независимо от реальной последовательности ветвления программы.
Если преобразование распространения копий заменяет с(еЬцд значением РЛ1 ЯЕ, инструкция ргфпс оказывается мертвой, так как не может быть достигнута. В результате мы можем удалить и проверку, и инструкцию вывода из объектного кода. В общем случае выяснение в процессе компиляции того факта, что значение выражения — константа, и использование вместо выражения этой константы называется дублированием констант (сопя(ап( (оЫшй). и Одно из преимушеств распространения копий состоит именно в том, что зачастую оно превращает инструкцию копирования в мертвый код.
Например, распространение копий с последующим удалением бесполезного кода приводит к устранению присвоения х и преобразованию кода на рис. 9.7 в код а(с2] = с5 а(с4] = сЗ досо Вз Он представляет собой дальнейшее улучшение блока Вь на рис. 9.5. 9.1.7 Перемещение кода Циклы являются очень важным объектом приложения усилий оптимизации, в особенности внутренние циклы, на выполнение которых тратится основное время работы программы.
Это время может быть уменьшено, если уменьшить количество инструкций во внутреннем цикле, даже ценой увеличения кода вне его. Важным изменением, уменьшающим количество кода в цикле, является иеремеи(ение кода. Это преобразование берет из цикла выражение, приводящее к одному и тому же результату независимо от того, сколько раз выполняется цикл (вычисление, инвариантное относительно цикла (]пор-1пчапап( сошрп(айоп)), и размещает его перед циклом. Заметим, что понятие "перед циклом" предполагает существование входа в цикл, т.е.
базового блока, в который ведут все переходы извне цикла (см. раздел 8.4.5). Пример 9.5. Например, вычисление атй — 2 является инвариантом цикла в сле- дующей конструкции: иЬ11е(1 <= 11щ1с — 2) /* Инструкции, не изменяющие 11щйс */ Перемещение кода преобразует эту инструкцию в эквивалентный код С = 11щ1С вЂ” 2; нЬ11е(1 <= с) /* Инструкции, не изменяющие 11щйс нлн с */ 715 9.1. Основные источники оптимизации Теперь вычисление 1пжйг — 2 выполняется однократно, до входа в цикл.
Ранее при выполнении п итераций цикла требовалось п + 1 раз вычислить значение 1пвй — 2. и 9.1.8 Переменные индукции и снижение стоимости Другая важная оптимизация состоит в поиске переменных индукции в циклах и оптимизации их вычислений. Переменная т называется "переменной индукции", если существует положительная или отрицательная константа с, такая, что всякий раз при присваивании х ее значение увеличивается на с.
Например, в цикле, содержащем Вз на рис. 9.5, переменными индукции являются 1 и 12. Переменные индукции могут быть вычислены при помощи единственного увеличения (сложения или вычитания) в каждой итерации цикла. Преобразование снижения стоимости (з1гепд1й гедпсйоп) состоит в замене дорогой операции, такой как умножение, более дешевой, такой как сложение. Однако переменная индукции не только позволяет нам выполнить снижение стоимости; зачастую можно обойтись только одной переменной из группы переменных индукции, значения которых остаются неизменными в пределах итерации цикла.
При работе с циклами лучше работать "изнутри наружу", т.е. начинать со внутренних циклов и последовательно двигаться ко все большим охватывающим циклам. Посмотрим, как можно применить указанную оптимизацию к примеру быстрой сортировки, начиная с одного из вложенных циклов, а именно — состоящего из одного блока Вз. Заметим, что переменные з и г4 остаются неизменными в пределах итерации; всякий раз значение з уменьшается на 1, а значение г4 уменьшается на 4, поскольку этой переменной присваивается значение 4 * з. Данные переменные з и 14 образуют хороший пример пары переменных индукции.
При наличии двух или более переменных индукции в цикле можно отбросить все, кроме одной. Во внутреннем цикле Вз мы не можем полностью отказаться от 1 или 14: переменная 14 используется в блоке Вз, а переменная з — в блоке В». Однако можно проиллюстрировать снижение стоимости и часть процесса устранения переменных индукции. В конечном счете переменная 1 будет удалена при рассмотрении внешнего цикла, состоящего нз базовых блоков Вз, Вз, В4 и Вз. Пример 9.6. Поскольку очевидно, что после присваивания переменной 14 на рис. 9.5 выполняется соотношение г4 = 4 * 1 и переменная 14 не изменяется в цикле, состоящем из блока Вз, сразу после инструкции З = 2-1 должно выполняться соотношение г4 = 4 * 1+ 4.
Следовательно, можно заменить присваивание Г4 = 4*2 на Г4 = Г4-4. Единственная проблема в том, что при первом входе в блок Вз переменная 14 не содержит значения. Поскольку при входе в базовый блок Вз должно выполняться соотношение 14 = 4*), поместим инициализацию переменной 14 в конце блока, где выполняется 716 Глава 9. Машинно-независимые оптимизации инициализация з, что показано на рис. 9.8 дополнением к блоку Вы выделенным пунктиром. Хотя мы и добавили одну команду, которая однократно выполняется в блоке Вы замена умножения вычитанием ускорит объектный код, если умножение требует больше времени, чем сложение и вычитание, что справедливо для множества машин.
и в, Рис. 9.8. Снижение стоимости, примененное к 4 *з в базовом блоке Вз Завершим этот раздел еще одним примером — удаления переменной индукции. В этом примере 1 и з рассматриваются в контексте внешнего цикла, состоящего из блоков Вз, Вз, В4 и Вз. Пример 9.7. После снижения стоимости, примененного ко внутренним цикламВз и Вз, единственное использование 1 и з находится в блоке В4, где сравниваются значения этих переменных.
Мы знаем, что значения 1 и г2 удовлетворяют соот- 717 9.!. Основные источники оптимизации ношению 12 = 4 * г, а значения 3 и 14 — соотношению г4 = 4 * з. Таким образом, вместо проверки 1 > з может использоваться проверка 12 > г4. После выполнения этой замены 1 в блоке Вз и у в блоке Вз становятся мертвыми переменными, а присваивание им в этих блоках — мертвым кодом, который может быть удален.
Получающийся в результате граф потока показан на рис. 9.9. и В, Рис. 9.9. Граф потока после устранения переменных индукции Рассмотренные нами преобразования кода оказались весьма эффективными. На рис. 9.9 количество команд в базовых блоках Вз и Вз снизилось с 4 до 3 по сравнению с исходным графом потока на рис. 9.3. В базовом блоке Вз количество команд сократилось с 9 до 3, а в базовом блоке Вв — с 8 до 3. Правда, блок Вг при этом вырос с 4 команд до 6, но он выполняется в данном фрагменте только один раз, так что на общее время выполнения фрагмента размер блока Вг влияет очень мало.
718 Глава 9. Машинно-независимые оптимизации 9.1.9 Упражнения к разделу 9.1 Упражнение 9.1.1. Ддя графа потока, представленного на рис. 9.10, выполните следующее. Рис. 9.10. Граф потока к упражнению 9.1.1 а) Найдите циклы в этом графе потока. б) Инструкции 1 и 2 в базовом блоке Вз представляют собой инструкции копирования, в которых а и б получают константные значения. Для каких использований а и 6 можно выполнить размножение копирований и заменить этн использования переменных использованиями констант? Выполните такую замену везде, где это возможно. в) Найдите глобальные общие подвыражения в каждом цикле. г) Найдите все переменные индукции для каждого цикла. Убедитесь, что вы учли все константы, внесенные в п.
б. 719 9.2. Введение в анализ потоков данных д) Найдите для каждого цикла вычисления, инвариантные относительно этого цикла. Упражнение 9.1.2. Примените преобразования из этого раздела к графу потока на рис. 8.9. Упражнение 9.1.3. Примените преобразования из этого раздела к графу потока из а) упражнения 8.4.1; б) упражнения 8.4.2. Упражнение 9.1.4. На рис.
9.11 приведен промежуточный код для вычисления скалярного произведения векторов А и В. Оптимизируйте насколько возможно этот код путем устранения общих подвыражений, снижения стоимости и устранения переменных индукции. с[р = О. О 1: с1 = 1*8 Г2 = А[с1] с3 = 1*8 с4 = В[ТЗ) г5 = г2*с4 с[р = с[р+с5 1+1 1й 1<п добро Ь Рис. 9.11. Промежуточный код вычисления скалярною произведения 9.2 Введение в анализ потоков данных Все оптимизации, рассматривавшиеся в разделе 9.1, зависят от анализа полгоков данньп. Анализ потоков данных (г[а1а-Йод апа1уяз) означает методы, собирающие информацию о потоках данных вдоль путей выполнения программы. Например, один из способов реализации устранения глобальных общих подвыражений требует от нас определить, вычисляют ли два текстуально одинаковых выражения одно и то же значение при любом из возможных путей выполнения программы. В качестве другого примера, если результат присваивания не используется ни в одном из последующих путей выполнения программы, это присваивание можно удалить как мертвый код.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
