Оптимизация кода
Если посмотреть на первоначально сгене─
рированный нашим компилятором пи-код,то мы
увидим, что он крайне неоптимален - ни по
памяти, ни по быстродействию. В нём очень
много обращений к стеку, использование то─
лько одного регистра,масса повторных вычи─
слений и т.д. Сразу при разборе операторов
генерировать оптимальный код мы не могли,
т.к. просматривали каждый токен последова─
тельно, рекурсивно спускаясь по вызывающи─
мся конструкциям ЯВУ. Теперь необходимо
сделать несколько видов оптимизаций, чтобы
привести код в более-менее опрятный вид и
приемлемое быстродействие. Конечно,довести
до почти идеала,который можно создать про─
граммированием вручную на ассемблере, нам
не удастся, но приблизиться к нему можно.
При программировании на ассемблере вручную
человек уже заранее видит многие возможные
"узкие места" в быстродействии или памяти
и подстраивает структуру кода под них. В
случае компилятора это сделать невозможно,
мы целиком зависим от конструкций ЯВУ.
В ZX Like Pascal реализованы следующие
виды оптимизаций:
-свёртка констант;
-упрощение выражений перекидыванием
операндов из стека в регистры (удаление
лишних push/pop);
-удаление повторных присваиваний и чте─
ний переменных;
-быстрое умножение и деление на числа
степени 2, а также быстрое умножение на
некоторые часто используемые числа;
-удаление повторных расчётов индексов
массивов.
Оставлены за рамками известные также
методы оптимизации,как анализ общих подвы─
ражений, объединение/расщепление циклов и
индуктивность переменных (математическая
зависимость от других переменных,например,
зависимость в циклеa[i] от i ).Они требу─
ют более глубокого анализа исходного кода
на ЯВУ, нужно просматривать структуры опе─
раторов, их вложенность и взаимодействие.
Хотя у меня частично это сделано для уда─
ления повторных расчётов индексов масси─
вов. Также для Спектрума не очень нужно
расщепление (раскрытие) циклов, т.к. для
конструкций ЯВУ они требуют много памяти,
а критичные к быстродействию процедуры
(вывод в цикле знакомест спрайтов, карт и
т.д.) уже зашиты в ассемблерной библиотеке
ZX Like Pascal, их на ЯВУ писать не имеет
смысла.
Первые три вида оптимизаций выполняются
на локальном уровне.Просматривается неско─
лько соседних команд пи-кода как бы через
"глазок" (по-научному, peephole-оптимиза─
ции), чтобы увидеть,можно ли с ними произ─
вести какую-либо трансформацию для оптими─
зации. В частности,они могут быть заменены
одной командой или более короткой последо─
вательностью команд.
Таких часто встречающихся шаблонов-за─
мен команд в моём компиляторе получилось
около 20. Причем после каждого прохода оп─
тимизации необходимо делать новый проход
по коду, т.к. предыдущая оптимизация могла
породить новые последовательности команд,
которые можно опять оптимизировать.Простой
абстрактный пример - убрали ближайшие ко─
мандыpush hl и pop hl, увидели на следую─
щем проходе, что можно убрать обрамлявшие
ихpush hl/pop hl.
Шаблоны замен команд следующие:
Конструкция ЯВУ
Последовательность
команд пи-кода,
сгенерированная Заменяющая
при разборе кон- команда
струкции ЯВУ или пи-кода
после предыдущей
оптимизации
Эквивалентный Эквивалентный
код на код на
ассемблере ассемблере
...+number
Push (0,'') LoadConstAdd
LoadConst (number,'')
(number,'')
PopAdd (0,'')
push hl ld de,number
ld hl,number add hl,de
pop de
add hl,de
...+name_var
Push (0,'') LoadVarAdd
LoadLabel (0,name_var)
(0,name_var)
LoadNumber (0,'')
PopAdd (0,'')
push hl
ld hl,name_var
ld e,(hl) ld de,
inc hl (name_var)
ld d,(hl) add hl,de
ex de,hl
pop de
add hl,de
...-number
Push (0,'') LoadConstSub
LoadConst (number,'')
(number,'')
PopSub (0,'')
push hl ld de,number
ld hl,number and a
pop de sbc hl,de
ex de,hl
and a
sbc hl,de
...-name_var
Push (0,'') LoadVarSub
LoadLabel (0,name_var)
(0,name_var)
LoadNumber (0,'')
PopSub (0,'')
push hl
ld hl,name_var
ld e,(hl) ld de,
inc hl (name_var)
ld d,(hl) and a
ex de,hl sbc hl,de
pop de
ex de,hl
and a
sbc hl,de
...*number
Push (0,'') LoadConstMul
LoadConst (number,'')
(number,'')
PopMul (0,'')
push hl ld de,number
ld hl,number call mul
pop de
call mul
...*name_var
Push (0,'') LoadVarMul
LoadLabel (0,name_var)
(0,name_var)
LoadNumber (0,'')
PopMul (0,'')
push hl
ld hl,name_var
ld e,(hl) ld de,
inc hl (name_var)
ld d,(hl) call mul
ex de,hl
pop de
call mul
.../number
Push (0,'') LoadConstDiv
LoadConst (number,'')
(number,'')
PopDiv (0,'')
push hl ld de,number
ld hl,number call div
pop de
ex de,hl
call div
.../name_var
Push (0,'') LoadVarDiv
LoadLabel (0,name_var)
(0,name_var)
LoadNumber (0,'')
PopDiv (0,'')
push hl
ld hl,name_var
ld e,(hl) ld de,
inc hl (name_var)
ld d,(hl) call div
ex de,hl
pop de
ex de,hl
call div
...%number
Push (0,'') LoadConstMod
LoadConst (number,'')
(number,'')
PopDiv (0,'')
push hl ld de,number
ld hl,number call div
pop de ex de,hl
ex de,hl
call div
ex de,hl
...%name_var
Push (0,'') LoadVarMod
LoadLabel (0,name_var)
(0,name_var)
LoadNumber (0,'')
PopDiv (0,'')
push hl
ld hl,name_var
ld e,(hl) ld de,
inc hl (name_var)
ld d,(hl) call div
ex de,hl ex de,hl
pop de
ex de,hl
call div
ex de,hl
number1+number2
LoadConst LoadConst
(number1,'') (number1+
LoadConstAdd number2,'')
(number2,'')
ld hl,number1 ld hl,
ld de,number2 number1+
add hl,de number2
number1-number2
LoadConst LoadConst
(number1,'') (number1-
LoadConstSub number2,'')
(number2,'')
ld hl,number1 ld hl,
ld de,number2 number1-
and a number2
sbc hl,de
number1*number2
LoadConst LoadConst
(number1,'') (number1*
LoadConstMul number2,'')
(number2,'')
ld hl,number1 ld hl,
ld de,number2 number1*
call mul number2
number1/number2
LoadConst LoadConst
(number1,'') (number1/
LoadConstDiv number2,'')
(number2,'')
ld hl,number1 ld hl,
ld de,number2 number1/
call div number2
number1%number2
LoadConst LoadConst
(number1,'') (number1%
LoadConstMod number2,'')
(number2,'')
ld hl,number1 ld hl,
ld de,number2 number1%
call div number2
ex de,hl
name_var:=...
LoadLabel PopStoreVar
(0,name_var) (0,name_var)
PopStoreNumber
(0,'')
ld hl,name_var
pop de pop hl
ld (hl),e ld
inc hl (name_var),hl
ld (hl),d
чтение значения переменной
LoadLabel LoadVar
(0,name_var) (0,name_var)
LoadNumber (0,'')
ld hl,name_var
ld e,(hl) ld hl,
inc hl (name_var)
ld d,(hl)
ex de,hl
чтение только что записанной переменной
PopStoreVar PopStoreVar
(0,name_var) (0,name_var)
LoadVar
(0,name_var)
pop hl pop hl
ld (name_var),hl ld
ld hl,(name_var) (name_var),hl
name_var:=number
Push (0,'') StoreVar
PopStoreVar (0,name_var)
(0,name_var)
push hl ld
pop hl (name_var),hl
ld (name_var),hl
Шаблонами-заменами производятся первые
три вида оптимизации: свёртка констант,
упрощение выражений перекидыванием операн─
дов из стека в регистры и удаление повто─
рных присваиваний и чтений переменных.
Например, конструкция a:=4+(2+3) после
разбора и генерации кода будет выглядеть
так:
LoadConst (4,'')
Push (0,'')
LoadConst (2,'')
Push (0,'')
LoadConst (3,'')
PopAdd (0,'')
PopAdd (0,'')
Push (0,'')
LoadLabel (0,'_a')
PopStoreNumber (0,'')
Теперь применяем шаблоны-замены, тогда
последовательные превращения нашего кода
будут такими:
LoadConst (4,'')
Push (0,'')
LoadConst (2,'')
LoadConstAdd (3,'')
PopAdd (0,'')
Push (0,'')
LoadLabel (0,'_a')
PopStoreNumber (0,'')
---
LoadConst (4,'')
Push (0,'')
LoadConst (5,'')
PopAdd (0,'')
Push (0,'')
LoadLabel (0,'_a')
PopStoreNumber (0,'')
---
LoadConst (4,'')
LoadConstAdd (5,'')
Push (0,'')
LoadLabel (0,'_a')
PopStoreNumber (0,'')
---
LoadConst (9,'')
Push (0,'')
LoadLabel (0,'_a')
PopStoreNumber (0,'')
---
LoadConst (9,'')
Push (0,'')
PopStoreVar (0,'_a')
---
LoadConst (9,'')
StoreVar (0,'_a')
Или на ассемблере:
ld hl,9
ld (_a),hl
Четвертый вид оптимизации - быстрое ум─
ножение и деление на числа степени 2, а
также быстрое умножение на некоторые часто
используемые числа - реализуется непосред─
ственно в ассемблерных процедурах в библи─
отеке.В коде процедуры на ассемблере перед
"честным" умножением (или делением) на
произвольное число производится проверка
операндов, не равен ли один из них числу
степени 2 или часто используемому числу (в
ZX Like Pascal это0,1,2,3,4,5,8,10,15,16,
20,32,50,64,100,128,256 ).Если условие вы─
полняется, то происходит вызов соответст─
вующей подпроцедуры короткого умножения
(деления). Таким образом,библиотечная про─
цедура позволяет производить короткое ум─
ножение или деление всех встреченных зна─
чений в регистрах (переменных),а не только
заранее заданных констант в коде ЯВУ. Для
умножения или деления на константы в ЯВУ
можно было бы дополнительно ввести оптими─
зирующие команды пи-кода (в ZX Like Pascal
не реализовано).
Для пятого вида оптимизации - удаления
повторных расчётов индексов массивов,- как
уже было написано выше, необходим анализ
соседних конструкций ЯВУ. Расчёт индексов
массива производится командами пи-кода для
расчёта выражений, т.к. индексы могут рас─
считываться с использованием любых значе─
ний констант,переменных и даже других яче─
ек массивов (при синтаксическом разборе
вызываются рекурсивно). Каждый раз, как
встречается расчёт индекса массива,в нашем
первоначально сгенерированном пи-коде за─
ново вычисляется выражение для его расчё─
та.Например,в конструкцииif a[i+1]>b then
a[i+1]:=a[i+1]+b; расчёт индексаi+1 будет
производиться трижды. Необходимо такие по─
вторные расчёты устранять, рассчитывать
значение индекса только один раз, запоми─
нать в памяти, а потом при повторе брать
готовое значение из памяти.
Для анализа соседних конструкций необ─
ходимо в командах пи-кода пометить их на─
чала и концы, а также их заголовки. Для
этого я применил псевдокоманды пи-кода
(маркеры), которые вставляются при разборе
операторов так же, как и другие команды, а
затем перед проведением других видов опти─
мизаций удаляются или не учитываются. На
линейных участках кодаStatement расчёты
индексов будут идти подряд, и здесь мы то─
чно можем производить сокращение расчётов.
Но в начале разветвлений кода мы будем ос─
тавлять полные расчёты индексов, если они
встречаются - в заголовках операторовIf,
Case, For, While, Repeat или в начале про─
цедур. Также в промежуточных операторах
могут встретиться изменения переменных,ко─
торые участвуют в расчёте индексов, в этом
случае сокращение расчётов также не произ─
водится.
Вот алгоритм поиска и сокращения повто─
рных расчётов индексов массивов в последо─
вательности команд пи-кода:
1.Заполняем маркеры начала и конца для
последовательностей команд Statement, If,
Case, For, While, Repeat, вызова процедур,
расчётов индексов массивов Selector;
2.Находим новый конец расчёта индексов
массива (идём с начала последовательности
пи-кода);
3.Сравниваем с предыдущим расчётом ин─
дексов покомандно. Если не совпали, то на
п.2;
4.Находим все переменные в выражениях,
участвующих в расчёте индексов (Selector);
5.Флаг перехода через Statement := 0
(т.е. флаг, показывающий выход за линейный
блок операторов);
6.Идём назад покомандно от начала рас─
чёта индексов;
7.Если встретили изменение переменной,
участвующей в расчёте индексов, в последо─
вательности команд Push (0,''), LoadLabel
(0,name_var) и PopStoreNumber (0,''),то
на п.2;
8.Если встретили маркер начала For,
While, Repeat, вызова процедуры,то на п.2;
9.Если встретили маркер конца If, Case,
For, While, Repeat, вызова процедуры,то на
п.2;
10.Если встретили маркер конца заголов─
ка If, Case, то флаг:=0;
11.Если встретили маркер начала State─
ment, то флаг:=1;
12. Если встретили конец предыдущего
расчёта индексов и флаг=0, то замена те─
кущего расчёта индексов на последовате─
льность команд LoadLabel (0,temp_index),
LoadNumber (0,'') и переход на п.2;
13.Переход на п.6.
Заключение
Мы рассмотрели методы генерации и опти─
мизации кода на конкретных примерах, испо─
льзуемых в компиляторе усечённого Паскаля
- ZX Like Pascal. Методом рекурсивного
спуска, просматривая токены друг за другом
в исходном коде программы на ЯВУ, мы доби─
раемся до всех вложенных конструкций и вы─
ражений, вставляя одновременно подходящие
команды пи-кода в их линейную последовате─
льность.При оптимизации пи-кода в основном
просматриваются шаблонные последовательно─
сти команд и заменяются на более оптималь─
ные. Надеюсь, статья поможет и вам создать
свой компилятор!
В заключение хочу порекомендовать книгу
Никлауса Вирта"Построение компиляторов",
М., 2010. В ней подробно описаны все этапы
разбора конструкций ЯВУ и генерации кода,
немного затронута оптимизация. Приведён
полный исходный код для компилятора языка
Оберон, написанного на самом Обероне (!),
который является "продвинутым" продолжени─
ем языка Паскаль.
Other articles:
