А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 133
Текст из файла (страница 133)
651 8.5. Оптимизация базовых блоков значение вычисляется. Таким образом, метод использования ориентированного ациклического графа не в состоянии обнаружить, что первая и четвертая инструкции в последовательности а=Ь+с Ь = Ь вЂ” с1 с=с+с1 е=Ь+с одинаковы и равны бс + сс. Иначе говоря, несмотря на то, что и Ь, и с между первой и последней инструкциями изменяются, их сумма остается той же, поскольку 6+ с = (6 — И) + (с + д). Ориентированный ациклический граф для этой последовательности показан на рис. 8.13, но в нем не видно ни одного общего подвыражения. Однако применение кориентированному ациклическому графу алгебраических тождеств, рассматривающееся в разделе 8.5.4, может выявить такую эквивалентность.
и Ьо СО аа Рис. 8.13. Ориентированный ацнклический граф для базового блока нз примера 8.11 8.5.3 Устранение неиспользуемого кода Операции над ориентированным ациклическим графом, соответствующие устранению неиспользуемого кода, могут быть выполнены следующим образом. Мы удаляем из ориентированного ациклического графа любой корень (узел без предков), с которым не связаны живые переменные. Повторное применение этого преобразования удалит из ориентированного ациклического графа все узлы, соответствующие неиспользуемому коду. Пример 8.12. Если на рис. 8.13 а и Ь вЂ” живые, а с и е -- нет, то можно тут же удалить корень с меткой е.
После этого узел с меткой с становится корнем и также может быть удален. Корни с метками а и Ь остаются, поскольку с каждым из них связана живая переменная. с 652 Глава 8. Генерация кода 8.5.4 Применение алгебраических тождеств Алгебраические тождества представляю~ еще один важный класс оптимизации базовых блоков.
Например, для устранения вычислений из базового блока могут применяться такие тождества, как х+0=0+х=х хх1=1хх=х х — 0 =- х х/1 =- х Еще один класс алгебраических оптимизаций включает локальное снижение стоимости вычислений, т.е. заменяет более дорогостоящие с вычислительной точки зрения операторы более дешевыми, как, например, ДОРОГОЙ ДЕШЕВЫЙ хя = ххх 2хх = х+х х/2 =- х х 0.5 Арифметические выражения должны аычисляться ао время компиляции гак жс, как они бы аычислялись ао время выполнения программы.
К. Томпсон (К. Тйогпрзоп) предложил элегантное решение этой проблемы, заключающееся а том, что консзантнос аыражснне компилируется, его нелевой код аыполняется и заменяется полученным результатом. Таким образом, компилятору ие надо аключагь и себя интерпретатор. з Однако аычитание может привести к переполнению или опусзошению, чего ие может произойти при применении команды сравнения. Третий класс оптимизаций — свертвшание констант (сопз1ап1 Го!Жпй), заключающееся в вычислении констант в процессе компиляции и замене константных выражений их значениями~.
Так, выражение 2* 3.14 можно заменить значением 6.28. На практике многие константные выражения возникают из-за частого использования в программах символьных констант. Процесс построения ориентированного ациклического графа может помочь нам в применении этих и других более общих алгебраических преобразований, таких как коммутативность и ассоциативность. Предположим, например, что в спецификации языка программирования указано, что операция умножения коммутативна, т.е, что х * д =- р * х.
Перед тем как создать новый узел с меткой *, левым дочерним узлом ЛХ и правым дочерним узлом Аг, мы проверяем, не существует ли уже такой узел. Однако в силу коммутативности умножения мы должны проверить также наличие узла с оператором *, левым дочерним узлом Аг и правым дочерним узлом М. Операторы отношений, такие как < и =, иногда генерируют неожиданные общие подвыражения. Например, условие х > у может быть также проверено путем вычитания аргументов и проверки кода условия, установленного при вычитанииз. 8.5.
Оптимизация базовых блоков 653 Таким образом, для х — у и х ) у может быть сгенерирован единственный узел ориентированного ациклического графа. Ассоциативные законы также могут применяться для выявления общих подвыражений. Например, если в исходном коде имеются присваивания а=Ь+с; е=с+с1+Ь| то может быть сгенерирован следующий промежуточный код: а=Ь+ с с=с+с[ е=С+Ь Если с вне этого блока не используется, то, воспользовавшись ассоциативностью и коммутативностью сложения, данную последовательность можно заменить следующей: а=Ь+с е=а+с[ Разработчик компилятора должен внимательно изучить спецификацию языка программирования, чтобы знать, какие изменения вычислений допустимы, поскольку [из-за возможных переполнений и опустошений) компьютерная арифметика не всегда подчиняется алгебраическим тождествам математики.
Например, стандарт языка программирования Гопгап указывает, что компилятор может вычислять любое математически эквивалентное выражение, обеспечивая неизменность примененных программистом скобок. Так, компилятор может вычислить х * у — х * х как х * (у — х), но не может вычислить а + (6 — с) как [а + 6) — с. Таким образом, компилятор языка программирования Гог[гап должен отслеживать наличие скобок в исходном тексте программы, чтобы оптимизировать ее в соответствии с определением языка программирования.
8.5.5 Представление обращений к массивам На первый взгляд может показаться, что команды с индексами массивов ничем не отличаются от других команд и могут рассматриваться как любые другие операторы. Рассмотрим, например, последовательность трехадресных инструкций х = а[х) а[э) = у х = а[х) Глава 8.
Генерация кода 654 Если рассматривать а [з] как операцию, включающую а и 1, подобную а+ г, то может показаться, что два использования а [ь] представляют собой общие подвыражения. В этом случае можно попытаться "оптимизировать" код, заменяя третью команду к = а [з] более простым присваиванием к = х. Но поскольку 3 может оказаться равным з, средняя команда может на самом деле изменить значение а [ з ], так что такая замена некорректна.
Правильный способ представления обращения к элементам массива в ориентированном ациклическом графе выглядит следующим образом. 1. Присваивание элемента массива наподобие х = а [ з ] представляется при помощи создания узла с оператором =[~ и двумя дочерними узлами, представляющими начальное значение массива, в данном случае ао, и индекс з. Переменная х становится меткой нового узла. 2.
Присваивание элементу массива наподобие а [ з ] = у представляется новым узлом с оператором []= и тремя дочерними узлами, представляющими ао, Э и у. Никакая переменная не выступает в качестве метки данного узла. Главное же в том, что создание этого узла аникяирует все созданные к э~ому моменту узлы, значения которых зависят от ао.
Аннулированный узел не может получать никакие метки, т.е. он не может стать общим подвыражением. Пример 8.13. Ориентированный ациклический граф для базового блока х = а[з] а[)] = у я = а[з] показан на рис. 8.14. Сначала создается узел Х для х, но, когда создается узел с меткой Ц=-, Х аннулируется. Таким образом, когда создается узел для я, он не может быть отождествлен с Ю, и в результате должен быть создан новый узел с теми же операндами ао и ]о. о Пример 8.14. Иногда узел должен быть аннулирован, несмотря на то что ни один из его дочерних узлов не имеет в качестве связанной с ним переменной массив наподобие ао в примере 8.13.
Узел может быть аннулирован, если имеет потомка, являющегося массивом, даже если ни один из его дочерних узлов не является узлом массива. Рассмотрим, например, трехадресный код Ъ=12+а х = Ь[з.] Ь[3] = у 655 8.5. Оптимизация базовых блоков ао то 1о Уа Рис. 8.14. Ориентированный ациклический граф для последовательности присваиваний с участием массива Здесь для повышения эффективности Ь определена как позиция в массиве а.
Например, если элементы а имеют размер 4 байт, то Ь представляет четвертый элемент а. Если з и З имеют одно и то же значение, то Ь [з ! и Ъ [э 1 представляют собой один и тот же элемент. Следовательно, третья команда, Ь[э 1 = у, аннулирует узел, с которым связана переменная х. Однако, как видно из рис. 8.15, как аннулированный, так и аннулирующий узлы не имеют дочернего узла ао— он является "внучатым" узлом для обоих указанных. го !2 ао то бо Уо Рис. 8.15. Узел, аииулнрующий использование массива, не обязан иметь его в качестве дочернего узла 8.5.6 Присваиваиие указателей и вызовы процедур Нам неизвестно, куда указывают р и с1 при косвенном присваивании с использованием указателя, как в следующих инструкциях: х=*р *ч=у 656 Глава х.
Генерация кода В сущности, х = *р представляет собой использование любой переменной, а *ц = у — возможное присваивание любой переменной. Следовательно, оператор =* должен принимать в качества аргументов все узлы, связанные в настоящий момент с идентификаторами, что оказывает существенное влияние на устранение неиспользуемого кода. И, что еще более важно, оператор *= аннулирует все прочие узлы в ориентированном ациклическом графе.
Глобальный анализ указателей иногда может ограничить множество переменных, на которые в данном месте кода может ссылаться некоторый указатель. Даже локальный анализ может ограничить область видимости указателя. Например, в случае последовательности р=ах *Р = У мы знаем, что только х, и никакая иная переменная, может получить значение у, так что нет необходимости в аннулировании узлов, кроме тех, с которыми связана переменная х. Вызовы процедур ведут себя во многом подобно присваиваниям с использованием указателей.
При отсутствии глобальной информации о потоках данных мы должны считать, что процедура использует и изменяет любые данные, к которым обращается. Таким образом, если процедура Р находится в области видимости переменной х, то вызов Р как использует узел с присоединенной переменной х, так и аннулирует его. 8.5.7 Сборка базового блока из ориентированного ациклического графа После выполнения всех возможных оптимизаций при построении ориентированного ациклического графа (или при работе с построенным ориентированным ациклическим графом) можно восстановить трехадресный код базового блока, для которого был построен этот ориентированный ациклический граф.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
