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

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

Спецификация оптимизатора скважины

Я исследовал несколько различных подходов к написанию оптимизатора глазка и остановился на внутреннем подходе:

Энкодер звонит наemit() функция каждый раз, когда должна быть сгенерирована машинная инструкция.emit(Instruction currentInstr) проверяет таблицу оптимизации глазка: Если текущая инструкция соответствует хвосту шаблона: Проверьте ранее выпущенные инструкции для соответствия Если все инструкции соответствуют шаблону, примените оптимизацию, изменив хвостовую часть хранилища кода Если оптимизация не найдена, выведите инструкцию как обычно Текущий подход к дизайну

Метод достаточно прост, у меня проблемы с реализацией. В моем компиляторе машинные инструкции хранятся вInstruction учебный класс. Я написалInstructionMatch class хранит регулярные выражения, предназначенные для соответствия каждому компоненту машинной инструкции. Этоequals(Instruction instr) метод возвращаетtrue если шаблоны соответствуют какой-то машинной инструкцииinstr.

Однако я не могу полностьюподать заявлени У меня есть правила. Прежде всего, я чувствую, что, учитывая мой нынешний подход, я получу беспорядок ненужных объектов. Учитывая, что полный список чисел оптимизации глазка может насчитывать около 400 шаблонов, это быстро выйдет из-под контроля. Более того, я не могу получить более сложные замены, работая с этим подходом (см. «Мой вопрос»).

Альтернативные подходы

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

Примеры шаблонов, синтаксис шаблонов
<code>x: JUMP x+1; x+1: JUMP y  -->  x: JUMP y
LOADL x; LOADL y; add     -->  LOADL x+y
LOADA d[r]; STOREI (n)    -->  STORE (n) d[r]
</code>

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

<code>op_code register n d
</code>

(n обычно обозначает количество слов, а d - смещение адреса). Синтаксисx: <instr> указывает, что инструкция хранится по адресуx в магазине кодов.

Так, инструкцияLOADL 17 эквивалентно полной машинной инструкции5 0 0 17 когдаLOADL код операции 5 n а такжеr не используются в этой инструкции)

Мой вопро

Итак, учитывая этот фон, у меня такой вопрос: как мне эффективно сопоставлять и заменять шаблоны, когда мне нужно включить части предыдущих инструкций в качестве переменных в моей замене? Например, я могу просто заменить все экземплярыLOADL 1; add с машинной инструкцией приращения - мне не нужна никакая часть предыдущих инструкций для этого. Но я не знаю, как эффективно использовать значения 'x' и 'y' моего второго примера в шаблоне подстановки.

редактироват: Я должен упомянуть, что каждое полеInstruction class - это просто целое число (как обычно для машинных инструкций). Любое использование «x» или «y» в таблице шаблонов - это переменная для замены любого целочисленного значения.

Ответы на вопрос(1)

Решение Вопроса

в виде конечного автомата.

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

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

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

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

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

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

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

Предположим, что наша машина - это машина с расширенным стеком,

 PUSHVAR x
 PUSHK i
 ADD
 POPVAR x
 MOVE x,k

instructions, но генератор необработанного кода генерирует только машинные инструкции чистого стека, например, он вообще не генерирует команду 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 показывает два разных стиля переходов, один из которых использует сгенерированную инструкцию, а другой - нет; либо работает для этого примера. Когда вы получите несколько сотен таких операторов case, вы обнаружите, что оба типа удобны, а версия «не потреблять» поможет вам уменьшить код.

Нам нужна процедура для очистки оптимизатора глазка:

  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. Я не собираюсь объяснять это здесь: -}

 David Cain11 мая 2012 г., 05:35
Вау, это довольно тщательный ответ. Спасибо за предложение, я обязательно рассмотрю этот подход в своем дизайне.

Ваш ответ на вопрос