Компилятор написан на Java: реализация оптимизатора Peephole

Ответ 1

Легкий способ сделать это - реализовать оптимизатор подглядывания как конечный конечный автомат.

Мы предполагаем, что у вас есть генератор исходного кода, который генерирует команды, но не испускает их, и процедуру генерации, которая отправляет фактический код в поток объекта.

Конечный автомат записывает инструкции, которые генерирует генератор кода, и запоминает последовательности из 0 или более сгенерированных инструкций путем перехода между состояниями. Таким образом, состояние неявно запоминает (короткую) последовательность генерируемых, но не испускаемых команд; он также должен помнить ключевые параметры команд, которые он захватил, например, имя регистра, постоянное значение и/или режимы адресации и абстрактные целевые ячейки памяти. Специальное начальное состояние запоминает пустую строку инструкций. В любой момент вы должны иметь возможность испускать неиспользуемые инструкции ( "флеш" ); если вы делаете это все время, ваш генератор глазок захватывает следующую инструкцию, а затем испускает ее, не делая никакой полезной работы.

Чтобы сделать полезную работу, мы хотим, чтобы машина фиксировала как можно более продолжительную последовательность. Поскольку обычно существует множество видов машинных инструкций, в качестве практического вопроса вы не можете запомнить слишком много подряд, или конечный автомат станет огромным. Но практично помнить последние два или три для наиболее общих машинных инструкций (загрузка, добавление, cmp, ветвь, хранилище). Размер машины действительно будет определяться длиной самой длинной оптимизации глазок, которую мы хотим сделать, но если эта длина равна P, вся машина не должна быть P-состояниями глубоко.

Каждое состояние имеет переход к следующему состоянию на основе "следующей" инструкции, которую я произвел генератором кода. Представьте, что состояние представляет собой захват N инструкций. Варианты перехода:

• сбросить самые левые 0 или более (назовите это k) инструкции, которые это состояние представляет, и перейти к следующему состоянию, представляя N-k + 1, инструкции, которые представляют дополнительный захват машинной команды I.
• сбросить самые левые k команд, которые представляет это состояние, переход в состояние который представляет остальные инструкции N-k и инструкцию по обработке I.
• полностью очистить состояние и испустить команду I. Вы действительно можете сделайте это только в начальном состоянии].

При очистке k-инструкций то, что на самом деле испускается, является оптимизированной версией тех k. Вы можете вычислить все, что хотите, при выдаче таких инструкций. Вам также необходимо помнить о необходимости "сдвигать" параметры для остальных инструкций.

Все это довольно легко реализуется с помощью переменной состояния оптимизатора подглядывания и оператором case в каждой точке, где ваш генератор кода создает следующую инструкцию. Оператор case обновляет состояние оптимизатора гладкости и реализует операции перехода.

Предположим, что наша машина является дополненной машиной стека, имеет

 PUSHVAR x
 PUSHK i
 ADD
 POPVAR x
 MOVE x,k

но генератор необработанного кода генерирует только команды чистого стека, например, он вообще не генерирует инструкцию MOV. Мы хотим, чтобы оптимизатор глазок выполнял это.

О нас, о которых мы заботимся, относятся:

 PUSHK i, PUSHK j, ADD ==> PUSHK i+j
 PUSHK i, POPVAR x ==> MOVE x,i 

Наши переменные состояния:

 PEEPHOLESTATE (an enum symbol, initialized to EMPTY)
 FIRSTCONSTANT (an int)
 SECONDCONSTANT (an int)

Наши заявления о случаях:

GeneratePUSHK:
    switch (PEEPHOLESTATE) {
        EMPTY: PEEPHOLESTATE=PUSHK;
               FIRSTCONSTANT=K;
               break;
        PUSHK: PEEPHOLESTATE=PUSHKPUSHK;
               SECONDCONSTANT=K;
               break;
        PUSHKPUSHK:
        #IF consumeEmitLoadK // flush state, transition and consume generated instruction
               emit(PUSHK,FIRSTCONSTANT);
               FIRSTCONSTANT=SECONDCONSTANT;
               SECONDCONSTANT=K;
               PEEPHOLESTATE=PUSHKPUSHK;
               break;
        #ELSE // flush state, transition, and reprocess generated instruction
               emit(PUSHK,FIRSTCONSTANT);
               FIRSTCONSTANT=SECONDCONSTANT;
               PEEPHOLESTATE=PUSHK;
               goto GeneratePUSHK;  // Java can't do this, but other langauges can.
        #ENDIF
     }

  GenerateADD:
    switch (PEEPHOLESTATE) {
        EMPTY: emit(ADD);
               break;
        PUSHK: emit(PUSHK,FIRSTCONSTANT);
               emit(ADD);
               PEEPHOLESTATE=EMPTY;
               break;
        PUSHKPUSHK:
               PEEPHOLESTATE=PUSHK;
               FIRSTCONSTANT+=SECONDCONSTANT;
               break:
     }  

  GeneratePOPX:
    switch (PEEPHOLESTATE) {
        EMPTY: emit(POP,X);
               break;
        PUSHK: emit(MOV,X,FIRSTCONSTANT);
               PEEPHOLESTATE=EMPTY;
               break;
        PUSHKPUSHK:
               emit(MOV,X,SECONDCONSTANT);
               PEEPHOLESTATE=PUSHK;
               break:
     }

GeneratePUSHVARX:
    switch (PEEPHOLESTATE) {
        EMPTY: emit(PUSHVAR,X);
               break;
        PUSHK: emit(PUSHK,FIRSTCONSTANT);
               PEEPHOLESTATE=EMPTY;
               goto GeneratePUSHVARX;
        PUSHKPUSHK:
               PEEPHOLESTATE=PUSHK;
               emit(PUSHK,FIRSTCONSTANT);
               FIRSTCONSTANT=SECONDCONSTANT;
               goto GeneratePUSHVARX;
     }

#IF показывает два разных стиля переходов, один из которых потребляет сгенерированный инструкция, а другая - нет; либо работает для этого примера. Когда вы закончите с несколькими сотнями из этих случаев, вы обнаружите, что оба типа удобны, а версия "не потреблять" помогает вы сохраняете свой код меньше.

Нам нужна рутина, чтобы очистить оптимизатор глазок:

  flush() {
    switch (PEEPHOLESTATE) {
        EMPTY: break;
        PUSHK: emit(PUSHK,FIRSTCONSTANT);
               break;
        PUSHKPUSHK:
               emit(PUSHK,FIRSTCONSTANT),
               emit(PUSHK,SECONDCONSTANT),
               break:
      }
      PEEPHOLESTATE=EMPTY;
      return; }

Интересно рассмотреть, что делает этот оптимизатор головок со следующим сгенерированным кодом:

      PUSHK  1
      PUSHK  2
      ADD
      PUSHK  5
      POPVAR X
      POPVAR Y

Что делает вся эта схема FSA, это скрыть соответствие шаблонов в переходах состояний и ответ на сопоставленные шаблоны в случаях. Вы можете закодировать это вручную, и это быстро и относительно легко кодировать и отлаживать. Но когда число случаев становится большим, вы не хотите создавать такой конечный автомат вручную. Вы можете написать инструмент для создания этого конечного автомата; Хорошим фоном для этого будет генерация машинного генератора FLEX или LALR. Я не собираюсь объяснять это здесь: -}