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

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

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

状态机捕获代码生成器生成的指令，并通过在状态之间转换来记住 0 个或更多生成指令的序列。因此，状态隐式记住生成但未发出的指令的（短）序列;它还必须记住它捕获的指令的关键参数，例如寄存器名称，常量值和/或寻址模式和抽象目标存储器位置。特殊的启动状态会记住空的指令字符串。在任何时候，您都需要能够发出未发出的指令（“冲洗”）;如果你一直这样做，你的窥视孔生成器会捕获下一条指令，然后发出它，没有任何有用的工作。

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

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

• 刷新此状态表示的最左边的 0 个或更多（调用此 k）指令，并转换到下一个状态（表示 N-k+1）指令，该指令表示机器指令 I 的附加捕获。
• 刷新此状态表示的最左侧的 k 条指令，转换为表示其余 N-k 条指令的状态，然后重新处理指令 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解析器状态机的生成。我不打算在这里解释这一点：-}