用Java编写的编译器：窥孔优化器实现

Question

我正在为Pascal的子集编写编译器。编译器为一台组装好的机器生成机器指令。我想为此机器语言编写一个窥孔优化器，但是我无法替换一些更复杂的模式。

窥孔优化器规格

我研究了几种编写窥孔优化器的方法，并且选择了后端方法：

• emit()每当要生成机器指令时，编码器都会调用函数。
• emit(Instruction currentInstr) 检查猫眼优化表：
  • 如果当前指令与模式的尾部匹配：
  • 检查先前发出的说明是否匹配
  • 如果所有指令都与该模式匹配，则应用优化，修改代码存储区的末尾
  • 如果未找到优化，则照常发出指令

当前的设计方法

该方法很容易，这是我遇到的麻烦。在我的编译器中，机器指令存储在一个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: <instr>指示该指令存储在x代码存储区中的地址处。

所以，指令LOADL 17相当于完整的机器指令5 0 0 17，当LOADL操作码是5（n和r在该指令是未使用）

我的问题

因此，在这样的背景下，我的问题是：当我需要在替换中包括先前指令的一部分作为变量时，如何有效地匹配和替换模式？例如，我可以简单地将所有实例替换LOADL 1; add为增量机器指令-我不需要前面指令的任何部分来执行此操作。但是我对如何在替换模式中有效使用第二个示例的“ x”和“ y”值感到困惑。

编辑 ：我应该提到一个Instruction类的每个字段只是一个整数（这对于机器指令来说是正常的）。模式表中对“ x”或“
y”的任何使用都是代表任何整数值的变量。

Answer 1

一种简单的方法是将窥视孔优化器实现为有限状态机。

我们假设您有一个原始代码生成器，该 生成 器 生成 指令但不 发出 指令，还有一个 发出 例程，该例程将实际代码发送到对象流。

状态机捕获代码生成器生成的指令，并通过在状态之间进行转换来记住0个或多个生成的指令的序列。因此，状态会隐式记住已生成但未发出的指令的（简短）序列；它还必须记住已捕获指令的关键参数，例如寄存器名称，常数值和/或寻址模式以及抽象目标存储器位置。特殊的开始状态会记住指令的空字符串。在任何时候，您都需要能够发出未被忽略的指令（“刷新”）；如果您一直这样做，则窥孔生成器会捕获下一条指令，然后发出该指令，而不会做任何有用的工作。

为了完成有用的工作，我们希望机器捕获尽可能长的序列。由于通常有多种类型的机器指令，因此实际上您不会连续记住太多，否则状态机将变得巨大。但是，记住最常见的机器指令（装入，添加，cmp，分支，存储）的最后两三个是实用的。机器的大小实际上取决于我们要进行的最长窥孔优化的长度，但是，如果该长度为P，则整个机器不必处于P状态深。

根据我的代码生成器生成的“下一条”指令，每个状态都转换为下一状态。想象一个状态代表捕获N条指令。过渡选项包括：

• 刷新该状态表示的最左边的0个或多个（称为k）指令，并转换到表示N-k + 1的下一个状态，该指令表示对机器指令I的附加捕获。
• 刷新该状态表示的最左边的k条指令，转换到表示其余Nk条指令的状态，然后重新处理指令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;
     }

我们需要一个例程来冲洗窥视孔优化器：

  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解析器状态机的生成。我不在这里解释：-}