Дикий ум - Генерация и оптимизация кода в компилятора (часть 2).

<b>Дикий ум</b> - Генерация и оптимизация кода
в компилятора (часть 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. В ней подробно описаны все этапы
разбора  конструкций ЯВУ и генерации кода,
немного  затронута  оптимизация.  Приведён
полный исходный  код для компилятора языка
Оберон, написанного  на самом Обероне (!), 
который является "продвинутым" продолжени─
ем языка Паскаль.