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

Question

我正在为Pascal的子集编写一个编译器.编译器为成型机器生成机器指令.我想为这种机器语言编写一个窥视孔优化器,但是我无法替换一些更复杂的模式.

窥孔优化器规范

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

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

目前的设计方法

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

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

因此,当操作码为5(并且在该指令中未使用)时,该指令LOADL 17等效于整机指令5 0 0 17LOADLnr

我的问题

所以,考虑到这个背景,我的问题是:当我需要将先前指令的部分包含在替换中的变量时,如何有效地匹配和替换模式？例如,我可以简单地用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解析器状态机生成.我不打算在这里解释一下: - }