深入 MPE VFX 代码生成器

作者 Stephen Pelc ， MicroProcessor Engineering

Web: http://www.mpeltd.demon.co.uk

MPE VFX Forth代码生成器能够生成与许多 C 编译器质量相同的代码。在以前的文章中，我们曾经介绍过 VFX 系统的起源。本文讨论 VFX 代码生成器的内部结构和它产生的结果。

简介

多年以来，我们一直都在聆听关于解释性语言运行缓慢的抱怨， JAVA 丝毫没有减弱这一印象。 Forth 一直作为一种解释语言，但实际上它应该算是一种交互式的语言。不过，我们认为与其在那儿争论解释工作方式是否适当，还不如开发一种编译 Forth 系统，在保证编译速度和完全交互能力的同时，可以产生高质量的代码。

VFX 代码生成器已经和 ProForth VFX for Windows 结合，并即将加入 ProForth VFX for Linux ，与传统的商用优化 Forth 编译器相比，性能提高了大约 2-3 倍。 VFX 代码生成器也集成到了 MPE Forth 6 VFX 交叉编译器中，用于 ARM/StrongARM 、 Intel i32 体系结构、 Hitachi H8/300H 、 Motorola 68xxx 、 Coldfire 和 68HC12 处理器。

代码生成器的目标

•  好的代码质量 ；

•  比串线方式只增加很少的代码尺寸；

•  好的代码生成器的可移植性；

•  好代码生成器的可维护性；

好的代码质量绝不仅仅只是一个商业卖点，它能够减少移植一个 Forth 核心所必需的汇编代码的数量，因而降低移植的成本。

典型地， MPE VFX 的核心只有 10 多个 CODE 定义。从用户的观点看，好的代码质量也减少了汇编语言程序的编写量，对于嵌入式系统的开发者来说，除了最苛刻的中断代码，其它的部分都可以用 Forth 来写。

代码尺寸只能少量增加的要求是由 MPE Forth 交叉编译器早期用户提出的，他们不希望大量地增加目标代码尺寸。另外，小的代码对于嵌入式 RISC 也极为重要，因为后者的 CACHE 通常很小。

MPE 最近把 92000 行 Forth 程序从使用 DTC （直接串线编码方式）的 Forth 5.1 68K 交叉编译器移植到 MPE Forth 6.1 68K 编译器。使用相同的硬件，结果代码的运行速度快了好几倍，尺寸略有减小。

好的代码生成器的可移植性可以减少移植到新的目标处理器的实现成本，这包括代码生成器本身，也包括必须重写的目标代码的成本。另外，当增加新的特点时，代码生成器也应该很容易升级。

好的代码生成器的可维护性影响到代码的可靠性、生命期成本和正在进行的研发成本。

复杂性

代码生成方式的 Forth 编译器与经典的串线 Forth 编译器的复杂度完全不是一个量级。但是，传统的代码原语在一个新的目标系统上必须重新编写，测试和调试，这之间的权衡非常简单：最后增加的性能是否有价格吸引力，为一个新的目标系统编写交叉编译程序的成本是不是可以大大减少。

在为几个 RISC 和 CISC 体系结构以及寄存器数目有限的 CPU 比如 68HC12 编写了代码生成器之后，我们可以对以上问题做出肯定的回答。

可移植性

与本地子程序串线方式加简单的内嵌交叉编译器相比， MPE VFX 代码生成器编写的难度极大，但这可以在目标代码可移植性方面得到平衡。

VFX 代码生成器大部分是与 CPU 无关的，但是不同的 CPU 结构对此有一定的影响。总的来说，代码生成器的可移植性主要决定于实施优化的深度。

VFX 代码生成器是高度优化的，因而不同的 CPU 体系结构将影响代码生成器，比如：

•  可用寄存器的数量

•  有 / 没有自动增量 / 自动减量寻址方式

•  体系结构是 load/store 还是寄存器--存储器

•  CACHE 体系结构

VFX 的内部结构

由于这是一个商业产品，所以它的细节并不能详细公开。

只要可能，优化就推迟代码生成，然后处理信息，在过程退出时以一个规范的形式返回堆栈。这种折衷允许优化的 Forth 字和没有优化的 Forth 字按一致的方式使用。

代码生成器作为从源程序到二进制代码变换中的一部分，这个主题全部包含在编译程序的教科书中。开始，代码生成器作为三个代码生成过程的中间结果：

•  词法优化，也称为源代码重写；

•  原语代码生成；

•  顺序重排和窥孔优化；

现在，正如下面将要解释的，我们用几个简单的代码生成器自身的特例分析来说明通过第一个和最后一个步骤得到的巨大收益。

VFX 代码生成器可以分成以下几个部分：

Control API 系统界面

Stack model 跟踪数据栈的内容

Stack shuffle 把堆栈恢复到规范的状态

Class generators 可交换的对，特例

Special cases 文字量，条件分支

Control API

控制 API 是 VFX 代码生成器与其它 Forth 系统之间的接口。除了通过字典头（含有一个到代码生成器的指针）以及 COMPILE ，其它的接口都是关于优化控制的，包括优化的深度和各种优化的使能和禁止。

在交叉编译器的 VFX 代码生成器中，控制 API 还包括 CPU 版本的选择，比如在 68K 家族中，有些版本具有不同的扩充指令。

Stack model

VFX 代码生成器推迟代码生成直到 CODE 层面。这就避免了大量的状态跟踪和代码移动。纯的堆栈操作比如 SWAP 和 DUP 只是简单地改变堆栈模型，保持资源使用的跟踪。

分类代码生成器使用这个信息访问实际的数据。 RIP 和重入代码作为特殊情况处理，对于一个典型的 CPU ，这种情况大约只有 10 个左右。

Stack shuffle

在许多处理器体系结构中，把项目保持在寄存器中是有益的。在大多数 VFX 实现中，包括了一个规范方法，它把栈顶元素保存在某个寄存器中，其它元素通过数据堆栈指针索引访问。这个状态在过程进入和退出以及基本块的边界是被强制要求的。恢复这个规范状态是 shuffle 子程序的工作。

这个子程序极为复杂，为了保证可移植性和可靠性，需要花费几个月的时间来开发算法。它将影响几乎全部的 VFX 代码生成器数据结构。

Class generators

许多代码生成器可以按它们的功能分组。例如，有一组操作可以“二元等效”，这意味着 a op b 与 b op a 是相同的。只要 CPU 的指令集允许，所有这些代码的生成都可以通过不同参数的分类子程序得到。

VFX 状态

除了堆栈模型本身， VFX 也记录了像返回栈状态一类的信息。在某些 CPU 比如 68HC12 中，最后使用的索引寄存器被跟踪。如果一个数据项从返回栈移出，则这个定义就被标记成“不能内嵌”。这就允许一些运行时间动作比如字符串处理可以用高级定义编码，保证一些棘手的 Michael Gassanenko's BackForth 扩展可以没有错误地在 ProForth VFX for Windows 中被编译。

这个状态信息可以被代码生成器内部使用，也可以被外部子程序使用。比如一个定义是否可以内嵌的固定信息就保存在这个字的字典头中。

Special cases

有一些特例可以非常简单地通过保持状态信息并在特定的环境下重新安排代码来处理。一个例子是 DOES> >R 序列的代码生成，另一个是比较引起的条件分支 > IF 。在第一种情况下，最有效的代码序列与 CREATE 地址被留在数据栈顶上的情况下不同。在第二种情况下，如果分支，则产生 ANS “良好风格的标志”代码就是多余的。

启发

当几个代码生成器完成并测试之后，我们花费了许多时间来研究不同情况和编码风格条件下的代码输出。我们也不可避免地研究了客户没有优化的代码。

有两个原因导致了低效率。一是由于我们忽略了 CPU 的特性，二是由于我们忽略了一些可以进一步优化的特殊情况。

在 68HC12 中，这种情况特别突出。这个芯片只有很少的寄存器和有限的 16 位操作。通过对代码生成器 2-3 遍的研究，我们达到了这样的程度：客户不再使用汇编语言编写对端口的访问代码，而全部使用高级定义来编码。

第二级优化

二进制内嵌

短的定义在某些特定的情况下可以作为内嵌代码复制。这是一个为避免调用和返回开销而广泛使用的技术，不过在 ProForth VFX for Windows 的代码生成器中，已经在很大程度上被源码内嵌所取代。

源代码内嵌

Forth 的能力很大程度上来自于它的可再用的短定义。这些定义可以产生高密度的代码，但是无法避免堆栈规范化的开销。

不考虑结构化定义是否实用，我们来看许多代码的形式：

: foo \ addr n - n'?

2 cells + @ +

;

: boo \ addr n - n'

4 cells + @ +

;

: bar \ addr ?n

0

over foo

swap boo

;

当仅仅使用二进制内嵌时（ ProForth VFX for Windows v3.22 ）结果如下：

FOO

( 004922A8 8B5B08 ) MOV EBX, [EBX+08]

( 004922AB 035D00 ) ADD EBX, [EBP]

( 004922AE 8D6D04 ) LEA EBP, [EBP+04]

( 004922B1 C3 ) NEXT,

( 10 bytes )

BOO

( 004922D0 8B5B10 ) MOV EBX, [EBX+10]

( 004922D3 035D00 ) ADD EBX, [EBP]

( 004922D6 8D6D04 ) LEA EBP, [EBP+04]

( 004922D9 C3 ) NEXT,

( 10 bytes )

BAR

( 004922F8 8D6DF8 ) LEA EBP, [EBP+-08]

( 004922FB C7450000000000 ) MOV DWord Ptr [EBP],00000000

( 00492302 895D04 ) MOV [EBP+04], EBX

( 00492305 8B5B08 ) MOV EBX, [EBX+08]

( 00492308 035D00 ) ADD EBX, [EBP]

( 0049230B 8D6D04 ) LEA EBP, [EBP+04]

( 0049230E 8B4500 ) MOV EAX, [EBP]

( 00492311 895D00 ) MOV [EBP], EBX

( 00492314 8BD8 ) MOV EBX, EAX

( 00492316 8B5B10 ) MOV EBX, [EBX+10]

( 00492319 035D00 ) ADD EBX, [EBP]

( 0049231C 8D6D04 ) LEA EBP, [EBP+04]

( 0049231F C3 ) NEXT,

( 40 bytes )

二进制内嵌扩展代码到 40 字节，而源码内嵌的结果非常不同。 FOO 和 BOO 的定义不变而 BAR 的代码已经完全不同。

BAR

( 004923C8 8BD3 ) MOV EDX, EBX

( 004923CA 8B5B08 ) MOV EBX, [EBX+08]

( 004923CD 83C300 ) ADD EBX, 00

( 004923D0 8B5210 ) MOV EDX, [EDX+10]

( 004923D3 03DA ) ADD EBX, EDX

( 004923D5 C3 ) NEXT,

( 14 bytes )

甚至这里也仍然可以通过改变寄存器分配策略和特殊情况“ + ”的代码生成来进一步改进目标代码。这个例子说明了特殊情况问题，和 CPU 寄存器数目有限（通常 8 个或者更少）的通用寄存器分配问题。

如果寄存器的分配太自由，堆栈溢出的频率将更高，导致更大和更慢的代码。如果它们分配过于受限，又会导致上面讨论的问题。

源码内嵌允许把因子作为源代码的宏来处理。一般认为这样做将导致代码尺寸的增加，但实际情况并不是这样，特别是对于继承编码。许多这样的小因子都做很少的事情，比如增加一个偏移量。在编译的时候，不管是内嵌还是调用，优化器都要创建规范的堆栈格式。在调用之后，优化器必须从规范的堆栈中取出项目。当作为源码嵌入处理时，通过对因子的编辑可以使VFX 优化器实现全范围优化。

结果

ProForth VFX for Windows 的代码生成质量可以与其它的几个优化编译器在相同的机器上进行比较

这些测试的源码可以从网站上下载

结论

MPE VFX 代码生成器产生的代码与最新的商用编译器相比，整数基准测试中，要快 3-5 倍。

这个代码生成器是可移植的，已经引入到 ProForth VFX for Windows 和 MPE VFX Forth 交叉编译器之中。代码生成器的开发成本可以通过结果的性能和目标代码的可维护性和可移植性的提高得到补偿。

Forth 实现

Forth 系统实现

为 ARM 处理器实现 Machine Forth