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

窥孔优化器规格

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

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

最佳答案

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

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

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

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

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

 PUSHVAR x
 PUSHK i
 ADD
 POPVAR x
 MOVE x,k

 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

关于java - 用Java编写的编译器: Peephole optimizer implementation，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10542082/