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

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

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

Энкодер звонит на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» в таблице шаблонов - это переменная для замены любого целочисленного значения.