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

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

Спецификация оптимизатора глазка

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

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

Текущий дизайн подход

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

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

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

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

Примеры шаблонов, синтаксис шаблона

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]

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

op_code register n d

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

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

Мой вопрос

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

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