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

我正在为Pascal的子集编写一个编译器。 编译器为制造的机器生成机器指令。 我想为这种机器语言编写一个窥视孔优化器，但是我在替换一些更复杂的模式时遇到了麻烦。

窥孔优化器规范

我研究了几种不同的编写窥视孔优化器的方法，并且我已经确定了一种后端方法：

• 每次生成机器指令时，Encoder都会调用emit()函数。
• emit(Instruction currentInstr)检查窥视孔优化表：
  • 如果当前指令与模式的尾部匹配：
    1. 检查先前发出的匹配说明
    2. 如果所有指令都与模式匹配，则应用优化，修改代码存储的尾端
  • 如果未找到优化，则照常发出指令

目前的设计方法

这个方法很简单，这是我遇到麻烦的实现。 在我的编译器中，机器指令存储在Instruction类中。 我写了一个InstructionMatch类，它存储了用于匹配机器指令的每个组件的正则表达式。 如果模式匹配某些机器指令instr则其equals(Instruction instr)方法返回true 。

但是，我无法完全应用我的规则。 首先，我觉得根据我目前的做法，我最终会得到一堆不必要的物品。 鉴于窥视孔优化数字的完整列表可以编号大约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 nd 

（n通常表示字数，d表示地址位移）。 语法x: 表示指令存储在代码存储区中的地址x 。

因此，当LOADL操作码为5时，指令LOADL 17相当于整机指令5 0 0 17 （ n和r在该指令中未使用）

我的问题

所以，考虑到这个背景，我的问题是：当我需要将先前指令的部分包含在替换中的变量时，如何有效地匹配和替换模式？ 例如，我可以简单地替换LOADL 1; add所有实例LOADL 1; add 使用增量机器指令LOADL 1; add – 我不需要执行此前任何操作的任何部分。 但是我不知道如何在替换模式中有效地使用我的第二个例子的’x’和’y’值。

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

Answer 1

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

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

状态机捕获代码生成器生成的指令，并通过在状态之间转换来记住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; } 

#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解析器状态机生成。 我不打算在这里解释一下： – }