А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 136
Текст из файла (страница 136)
г) Если же приведенные ситуации не осуществляются, то требуется сгенерировать команду сохранения БТ и, Л для сохранения копии и в ее местоположении в памяти. Эта операция называется сбросом (зр)11). Поскольку Л может одновременно хранить несколько переменных, приведенные выше шаги следует повторить для всех таких переменных и. Среди регистров выбирается один из тех, у которых количество одновременно хранимых переменных минимально. Теперь рассмотрим выбор регистра Л . Почти все варианты при этом те же, что и для у, так что упомянем только имеющиеся отличия. Е Поскольку вычисляется новое значение переменной х, регистр, в котором хранится единственная переменная х, всегда годится в качестве Л,.
Это утверждение справедливо даже тогда, когда х является одним из у или з, поскольку наша машинная команда допускает совпадение двух регистров в одной команде. 667 8.6. Простой генератор кола 2. Если р не используется после команды 1 в смысле, описанном для переменной и в пункте Зы, и Л хранит только одну переменную р, то Л, также может использоваться в роли Л, То же самое относится и к г и Л,. Последним рассмотрим частный случай, когда 1 представляет собой команду копирования х = р. Регистр Ля выбирается„как и ранее, после чего мы всегда выбираем Л, = Л . 8.6.4 Упражнения к разделу 8.6 Упражнение 8.6.1. Для каждой из приведенных ниже инструкций присваивания на языке программирования С сгенерируйте трехадресный код в предположении, что все элементы массива — целые числа размером по 4 байт.
В частях г и д считаем, что а, Ь и с — константы, указывающие положения первых [с индексом О) элементов массивов с данными именами, как и во всех предыдущих примерах обрашения к массивам в данной главе. а) х = а + Ь*с; б) х = а/(Ь+с) — с[*(е+й)г в)х = а[х] + 1; г) а[з ] = Ь[с[з.]]; д) а[~.] [З] = Ь[~.] [х] + с[!с] [2] ! е) *р++ = *Ч++' Упражнение 8.6.2.
Повторите части г и д упражнения 8.6.1 в предположении, что массивы а, Ь и с доступны через указатели соответственно ра, рЬ и рс, указывающие на положения первых элементов массивов. Упражнение 8.6.3. Преобразуйте трехадресный код из упражнения 8.6.1 в машинный код для модели машины из этого раздела. Вы можете использовать столько регистров, сколько вам надо. Упражнение 8.6.4. Преобразуйте трехадресный код из упражнения 8.6.1 в машинный код с помощью простого алгоритма генерации кода из данного раздела в предположении доступности трех регистров.
Приведите дескрипторы регистров и адресов после каждого шага алгоритма. Упражнение 8.6.5. Повторите упражнение 8.6.4 при условии доступности только двух регистров. 668 Глава 8. Генерация кода 8.7 Локальная оптимизация В то время как большинство промышленных компиляторов дают хороший код путем тщательного выбора команд и распределения регистров, некоторые компиляторы используют иную стратегию: они генерируют простейший код, а затем повышают его качество, применяя "оптимизирующие" преобразования целевой программы. Термин "оптимизирующий" в данном случае несколько неверен, поскольку не гарантируется, что полученный в результате код будет более оптимален с той нли иной точки зрения.
Тем не менее многие простые преобразования могут существенно улучшить время работы нли размер целевой программы. Простым, но эффективным методом локального улучшения целевого кода является локальиия оптимизация !реер)о)е орйппха!юпз), которая выполняется путем перемещения по целевой программе окна ("реер)зо!е" — "глазка") и изучения команд в его пределах с дальнейшей заменой последовательностей команд более быстрыми или более короткими там, где это возможно. Локальная оптимизация зачастую применима непосредственно после генерации промежуточного кода для усовершенствования промежуточного представления.
Глазок представляет собой небольшое перемещающееся по программе окно. Код в этом окне не обязательно непрерывен, хотя некоторые реализации и выдвигают такое требование. Характерным для локальной оптимизации является то, что каждое улучшение кода может создать условия для дополнительных улучшений.
Вообще говоря, для получения максимального эффекта необходимы повторяющиеся проходы по целевому коду. В этом разделе мы приведем следующие примеры преобразования программ, характеризующие локальную оптимизацию: ° устранение излишних инструкций; ° оптимизация потока управления; ° алгебраические упрощения; ° использование машинных идиом. 8.7.1 Устранение излишних загрузок и сохранений Если в целевой программе нам встречается последовательность команд 10 ВО, а ЯТ а, ВО то можно удалить команду сохранения, поскольку при ее выполнении первая команда гарантирует, что значение а уже загружено в регистр ВО. Заметим, что если «Дословно — "оптимизация смотрового отверстия".
— Прим. лер 669 8.7. Локальная оптимизация бы команда сохранения имела метку, то мы не могли бы быть уверены, что первая команда всегда выполняется немедленно перед второй, так что удаление второй команды было бы ошибочным. Иными словами, чтобы такое преобразование было безопасным, обе команды должны находиться в одном базовом блоке. Излишние загрузки и сохранения такого вида не генерируются при использовании простого алгоритма из предыдущего раздела. Однако простейший наивный алгоритм генерации кода наподобие алгоритма из раздела 8.1.3 может генерировать излишние последовательности, подобные рассмотренной. 8.7.2 Устранение недостижимого кода Еще одной возможностью локальной оптимизации является удаление недостижимых команд.
Команда без метки, следующая непосредственно за безусловным переходом, может быть удалена. Эта операция может быть повторена для удаления последовательности команд. Например, в целях отладки большая программа может использовать фрагменты кода, которые выполняются только тогда, когда переменная с1е1эпд равна 1.
В промежуточном представлении такой код может выглядеть следующим образом: Ьй с1еЬпд == 1 дото Ь1 досо Ь2 Ь1: Вывод отладочной информации Ь2: Очевидной локальной оптимизацией является устранение переходов через переходы. Независимо от того, какое значение имеет переменная г1еЬпд, приведенную последовательность можно заменить такой последовательностью: 11 с1еЬид 1= 1 досо Ь2 Вывод отладочной информации Если в начале программы переменная с1е1эпд установлена равной О, то распространение констант преобразует эту последовательность в 11' О != 1 добро Ь2 Вывод отладочной информации Ь2: Теперь аргумент первой инструкции всегда истинен, так что вся инструкция может быть заменена безусловным переходом доСо Ь2.
Тогда все инструкции, выводящие отладочную информацию, являются недостижимыми и могут быть удалены. Глава 8. Генерация кода 670 8.7.3 Оптимизация потока управления Алгоритмы генерации промежуточного кода часто приводят к коду, в котором имеются условные и безусловные переходы к командам-переходам. Такие излишние переходы могут быть устранены либо в промежуточном, либо в целевом коде путем локальной оптимизации следующих видов. Мы можем заменить последовательность переходов доСо 1,1 1 1: яоСО Ь2 последовательностью добро 12 11: ЯОСО 12 Если после такой замены переходы к 1.1 отсутствуют, команду 11: пото 12 можно убрать из целевого кода, если ей предшествует безусловный переход.
Аналогично последовательность тй а < Ь дото 1.1 Ь1: добро Ь2 может быть заменена последовательностью тй а < Ь доЬо Ь2 11: добро 12 Наконец, предположим, что есть только один переход к 1.1 и что 1.1 предшествует безусловный переход. Тогда последовательность доКо Ь1 11: 1Й а < Ъ доСо 12 ХЗ: может быть заменена последовательностью тй а < Ь дота 12 дог.о 13 13: 671 8.7. Локальная оптимизация Хотя число инструкций в этих двух последовательностях и одинаково, иногда безусловный переход во второй последовательности может оказаться пропущен, но в первой последовательности он выполняется всегда. Таким образом, код второй последовательности эффективнее кода первой с точки зрения времени выполнения.
8.7.4 Алгебраические упрошения и снижение стоимости В разделе 8.5 мы рассматривали алгебраические тождества, которые могут использоваться для упрощения ориентированных ациклических графов. Эти алгебраические тождества могут использоваться и при локальной оптимизации для устранения трехадресных команд наподобие х : = х + О илн х : = х * 1 в пределах окна. Аналогично снижение стоимости может применяться локально, заменяя дорогие с точки зрения времени выполнения, используемых ресурсов и других характеристик команды целевой машины эквивалентными более дешевыми.
Одни машинные команды значительно дешевле других и часто используются как частный случай более дорогих операторов. Например, хз всегда дешевле вычислить как к * х, чем путем вызова подпрограммы возведения в степень. Умножение или деление чисел с фиксированной точкой на степень двойки дешевле реализовать как сдвиг.
Деление чисел с плавающей точкой на константу, реализованное как умножение на другую константу, также может оказаться более дешевым. 8.7.5 Использование машинных идиом Целевая машина может иметь аппаратные команды, эффективно реализующие ряд специфических операций. Определение ситуаций, позволяющих использовать специальные машинные команды, может существенно сократить время выполнения кода. Например, ряд машин имеет режимы адресации с автоувеличением или автоуменьшением, при которых к операнду прибавляется (или вычитается из него) единица до или после использования его значения. Использование таких режимов существенно повышает качество кода для внесения в стек или снятия с него, выполняемых, например, при передаче параметров процедуре. Эти режимы могут также использоваться в коде для инструкций наподобие х = х + 1.
8.7.6 Упражнения к разделу 8.7 Упражнение 8.7.1. Разработайте алгоритм для устранения излишних команд в окне, перемешающемся по целевому коду. Упражнение 8.7.2. Разработайте алгоритм для выполнения оптимизации потока управления в окне, перемещающемся по целевому коду. 672 Глава 8. Генерация кода Упражнение 8.7.3. Разработайте алгоритм, который будет выполнять простые алгебраические упрошения и снижение стоимости в окне, перемещаюшемся по целевому коду. 8.8 Распределение и назначение регистров Команды, включающие в качестве операндов только регистры, выполняются быстрее, чем аналогичные команды с ячейками памяти в качестве операндов.
На современных машинах эта разница в скорости может достигать порядка по величине. Следовательно, эффективное использование регистров — жизненно важная составляющая генерации хорошего целевого кода. В этом разделе представлены различные стратегии принятия решения о том, какие значения в программе должны находиться в регистрах Граспределение регистров) и в каком регистре должно храниться каждое значение (назначение регистров).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
