Оптимизация с помощью глазка - это метод оптимизации, выполняемый на небольшом наборе инструкций, генерируемых компилятором; небольшой набор известен как глазок или окно. [1]
Оптимизация с помощью глазка включает в себя замену небольшого набора инструкций на эквивалентный набор, который имеет лучшую производительность.
Например:
- вместо того, чтобы помещать регистр A в стек и затем немедленно выталкивать значение обратно в регистр A, оптимизация с помощью глазка удалит обе инструкции;
- вместо добавления A к A оптимизация с помощью глазка может выполнить арифметический сдвиг влево;
- вместо умножения регистра с плавающей запятой на 8, оптимизация с помощью глазка может масштабировать показатель степени регистра с плавающей запятой на 3; а также
- вместо умножения индекса на 4, добавления результата к базовому адресу, чтобы получить значение указателя, а затем разыменования указателя, оптимизация с помощью глазка может использовать режим аппаратной адресации, который достигает того же результата с помощью одной инструкции.
Термин оптимизация с помощью глазка был введен Уильямом Маршаллом МакКиманом в 1965 году [2].
Правила замены
Общие методы, применяемые при оптимизации глазок: [3]
- Нулевые последовательности - Удалите ненужные операции.
- Объединить операции - заменить несколько операций одним эквивалентом.
- Алгебраические законы - используйте алгебраические законы, чтобы упростить или изменить порядок инструкций.
- Инструкции для особых случаев - Используйте инструкции, предназначенные для особых случаев операндов.
- Операции в адресном режиме - используйте режимы адреса для упрощения кода.
Могут быть и другие виды оптимизации глазок.
Примеры
Замена медленных инструкций на более быстрые
Следующий байт-код Java
...загрузить 1загрузить 1мул...
можно заменить на
...загрузить 1обманмул...
Этот вид оптимизации, как и большинство оптимизаций с помощью глазка, делает определенные предположения об эффективности инструкций. Например, в этом случае предполагается, что dup
операция (которая дублирует и выталкивает верхнюю часть стека ) более эффективна, чем aload X
операция (которая загружает локальную переменную, идентифицированную как, X
и помещает ее в стек).
Удаление избыточного кода
Другой пример - устранение избыточных хранилищ нагрузки.
а = Ь + с; д = а + е;
просто реализуется как
MOV b , R0 ; Копируем b в регистр ADD c , R0 ; Добавьте c в регистр, регистр теперь b + c MOV R0 , a ; Скопируйте регистр в MOV a , R0 ; Скопируйте a в регистр ADD e , R0 ; Добавьте e в регистр, теперь регистр a + e [(b + c) + e] MOV R0 , d ; Скопируйте реестр в d
но может быть оптимизирован для
MOV b , R0 ; Копируем b в регистр ADD c , R0 ; Добавьте c в регистр, который теперь равен b + c (a) MOV R0 , a ; Скопируйте регистр в ADD e , R0 ; Добавьте e в регистр, который теперь равен b + c + e [(a) + e] MOV R0 , d ; Скопируйте реестр в d
Удаление избыточных инструкций стека
Если компилятор сохраняет регистры в стеке перед вызовом подпрограммы и восстанавливает их при возврате, последовательные вызовы подпрограмм могут иметь избыточные инструкции стека.
Предположим, компилятор генерирует следующие инструкции Z80 для каждого вызова процедуры:
PUSH AF PUSH BC PUSH DE PUSH HL ВЫЗОВ _ADDR POP HL POP DE POP BC POP AF
Если бы было два последовательных вызова подпрограмм, они бы выглядели так:
PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 POP HL POP DE POP BC POP AF PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR2 POP HL POP DE POP BC POP AF
Последовательность POP regs, за которой следует PUSH для тех же регистров, обычно избыточна. В случаях, когда это избыточно, оптимизация глазком удалит эти инструкции. В примере это приведет к тому, что в глазке появится еще одна избыточная пара POP / PUSH, и они будут удалены в свою очередь. Предполагая, что подпрограмма _ADDR2 не зависит от предыдущих значений регистров, удаление всего избыточного кода в приведенном выше примере в конечном итоге оставит следующий код:
PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 CALL _ADDR2 POP HL POP DE POP BC POP AF
Выполнение
Современные компиляторы часто реализуют оптимизацию глазка с помощью алгоритма сопоставления с образцом . [4]
Смотрите также
- Оптимизаторы объектного кода , обсуждение общей алгоритмической эффективности
- Capex Corporation - произвела оптимизатор COBOL , ранний оптимизатор объектного кода мэйнфреймов для IBM Cobol
- Супероптимизация
- Digital Research XLT86 , оптимизирующий компилятор от исходного кода к исходному.
Рекомендации
- ^ Мучник, Стивен Стэнли (1997-08-15). Расширенный дизайн и реализация компилятора . Academic Press / Морган Кауфманн . ISBN 978-1-55860-320-2.
- ^ МакКиман, Уильям Маршалл (июль 1965 г.). «Глазковая оптимизация». Коммуникации ACM . 8 (7): 443–444. DOI : 10.1145 / 364995.365000 .
- ^ Фишер, Чарльз Н .; Cytron, Ron K .; ЛеБлан-младший, Ричард Дж. (2010). Создание компилятора (PDF) . Эддисон-Уэсли . ISBN 978-0-13-606705-4. Архивировано из оригинального (PDF) на 2018-07-03 . Проверено 2 июля 2018 .
- ^ Ахо, Альфред Вайно ; Лам, Моника Син-Линг ; Сетхи, Рави ; Ульман, Джеффри Дэвид (2007). «Глава 8.9.2« Генерация кода мозаикой входного дерева ». Компиляторы - принципы, методы и инструменты (PDF) (2-е изд.). Pearson Education . п. 540. Архивировано (PDF) из оригинала 10.06.2018 . Проверено 2 июля 2018 .
Внешние ссылки
- Универсальный оптимизатор глазка copt от Кристофера В. Фрейзера
- Оригинальная бумага
Словарное определение оптимизации глазка в Викисловаре