Eu estou escrevendo um compilador para um subconjunto de Pascal. O compilador produz instruções de máquina para uma máquina confeccionada. Eu quero escrever um otimizador olho mágico para esta linguagem de máquina, mas estou tendo problemas para substituir alguns dos padrões mais complicados.

Especificação do otimizador Peephole

Eu pesquisei várias abordagens diferentes para escrever um otimizador de olho mágico e resolvi uma abordagem de back-end:

O codificador faz uma chamada para umemit() função toda vez que uma instrução de máquina é gerada.emit(Instruction currentInstr) verifica uma tabela de otimizações do olho mágico:Se a instrução atual corresponder à cauda de um padrão:Verificar instruções anteriormente emitidas para correspondênciaSe todas as instruções corresponderem ao padrão, aplique a otimização, modificando a extremidade final do armazenamento de códigoSe nenhuma otimização foi encontrada, emita a instrução como de costumeAbordagem de design atual

O método é bastante fácil, é a implementação com a qual estou tendo problemas. No meu compilador, as instruções da máquina são armazenadas em umInstruction classe. Eu escrevi umInstructionMatch A classe armazena expressões regulares destinadas a combinar cada componente de uma instrução de máquina. Estáequals(Instruction instr) retornos do métodotrue se os padrões combinarem com alguma instrução da máquinainstr.

No entanto, não consigo administrar totalmenteAplique as regras que tenho. Primeiramente, eu sinto que, dada a minha abordagem atual, vou acabar com uma confusão de objetos desnecessários. Dado que uma lista completa de números de otimizações do olho mágico pode numerar cerca de 400 padrões, isso vai ficar fora de controle rapidamente. Além disso, eu não posso realmente conseguir substituições mais difíceis trabalhando com essa abordagem (veja "Minha pergunta").

Abordagens alternativas

Um documento que li contém instruções anteriores em uma longa string, usando expressões regulares para corresponder e substituir, e convertendo a string de volta em instruções de máquina. Isto pareceu uma má abordagem para mim, por favor corrija-me se estiver errado.

Padrões de exemplo, sintaxe de padrão

<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>

Observe que cada um desses padrões de exemplo é apenas uma representação legível por humanos do seguinte modelo de instrução da máquina:

<code>op_code register n d
</code>

(n geralmente indica o número de palavras e d um deslocamento de endereço). A sintaxex: <instr> indica que a instrução é armazenada no endereçox no armazenamento de código.

Então, a instruçãoLOADL 17 é equivalente à instrução completa da máquina5 0 0 17 quando oLOADL opcode é 5 (n er não são utilizados nesta instrução)

Minha pergunta

Então, considerando esse pano de fundo, minha pergunta é a seguinte: Como eu efetivo a correspondência e a substituição de padrões quando preciso incluir partes de instruções anteriores como variáveis ​​na minha substituição? Por exemplo, posso simplesmente substituir todas as instâncias deLOADL 1; add com a instrução de incremento da máquina - não preciso de nenhuma parte das instruções anteriores para fazer isso. Mas estou sem saber como usar efetivamente os valores 'x' e 'y' do meu segundo exemplo no padrão de substituição.

editar: Devo mencionar que cada campo de umInstruction class é apenas um inteiro (como é normal para instruções de máquina). Qualquer uso de 'x' ou 'y' na tabela de padrões é uma variável para representar qualquer valor inteiro.