Info Guide
#11
05 июля 2015 |
|
Дикий ум - Генерация и оптимизация кода в компилятора (часть 2).
Оптимизация кода Если посмотреть на первоначально сгене─ рированный нашим компилятором пи-код,то мы увидим, что он крайне неоптимален - ни по памяти, ни по быстродействию. В нём очень много обращений к стеку, использование то─ лько одного регистра,масса повторных вычи─ слений и т.д. Сразу при разборе операторов генерировать оптимальный код мы не могли, т.к. просматривали каждый токен последова─ тельно, рекурсивно спускаясь по вызывающи─ мся конструкциям ЯВУ. Теперь необходимо сделать несколько видов оптимизаций, чтобы привести код в более-менее опрятный вид и приемлемое быстродействие. Конечно,довести до почти идеала,который можно создать про─ граммированием вручную на ассемблере, нам не удастся, но приблизиться к нему можно. При программировании на ассемблере вручную человек уже заранее видит многие возможные "узкие места" в быстродействии или памяти и подстраивает структуру кода под них. В случае компилятора это сделать невозможно, мы целиком зависим от конструкций ЯВУ. В 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. В ней подробно описаны все этапы разбора конструкций ЯВУ и генерации кода, немного затронута оптимизация. Приведён полный исходный код для компилятора языка Оберон, написанного на самом Обероне (!), который является "продвинутым" продолжени─ ем языка Паскаль.
Другие статьи номера:
Похожие статьи:
В этот день... 10 октября