为ARM处理器实现Machine Forth「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

为 ARM 处理器实现 Machine Forth

作者 Reuben Thomas

Computer Laboratory, University of Cambridge

23rd August 1999

摘要

Fox 和 Moore[2] 最近提出了一种新的 Forth 虚拟机模型，称为 Machine Forth 。使用一个简单而具体的模型，据说它可以很容易地适应不同的硬件，不需要转向汇编器就可以产生效率很高的代码，它也努力成为一个优秀的 Forth 编译器的基础。本文讨论了一个 ARM 处理器实现 Forth 的方方方面，比较了一个基于 MF 的 Forth 系统和一个使用 ARM 机器模型实现的传统 Forth 系统。

1 介绍

1999 年 3 月，在 comp.lang.forth 有一个关于 Charles Moore 的 MachineForth 的讨论。这个虚拟机模型据说将用于他自己全部的 Forth 编程，并已经在如 F21 一类的几个硅片上实现了。

Jeff Fox 是 Moore 的助手，他说 Moore 认为 MF VM 对于 Forth 的底层程序员来说比经典的 Forth VM 好得多，它允许离机器更近，同时维护一个相同的虚拟处理机而不管它下面是什么样的真实处理器。另外，设计的简单性就意味着为了实现这个系统，所需要的工具不会多于一个小的宏汇编器。

由此而激发兴趣，我决定通过在 ARM 处理器上实现一个 Forth 来为我测试这个模型。我想看看像自动增量寻址一类的新指令是如何有利于程序设计的，而缺少 SWAP 和 ROT 一类的指令又是如何妨碍程序设计的，系统的实现有多么简单，在速度和代码密度方面与传统的 Forth 系统有什么差异。当然，我也关心为了适应 ARM 硬件， MF VM 模型需要有哪些改变。

我关于 MF Forth 的测试包括用 MF 写一个 Forth 编译器，它含有 Moore 的最小要求。（另一个显而易见的实验是把我平时使用的系统 — 一个扩展的 ANS 兼容系统 — 移植到 MF 上）。然后，我重新用 ARM 代码编写一个编译器，以比较直接为 ARM 编写系统和用 MF 编写之间的差异。在这两个系统上、在传统的 Forth 以及 C 编译器上都运行了基准测试程序。

以下的讨论假设读者熟悉 MF 模型以及 F21 的细节。从这里开始，“Machine Forth ”简写为“MF”，而我自己的版本，不好意思，就称为“MF32”吧。

机器模型的改变

由于我只有 F21 的规范作为 MF 的指导，我不知道 Moore 是否在传统的处理器上实现了 MF 。

数据宽度

由于 ARM 是32 位的体系结构，数据宽度变成 32 位。

测试进位

在 F21 处理器上，指令 C=0 对堆栈元素的一个扩展位进行测试。如果在传统的处理器上实现，这个指令将特别慢，所以把这个指令变成测试 T31 位，该位通常用来测试数值是否为负，这对于测试进位没有帮助，除非我们把寄存器视为 31 位长。不过对于 32 位精度乘法的需要通常比 20 寄存器要少。

堆栈

F21 处理器将它的堆栈放置在芯片上，所以它们是固定大小的；由于 ARM 没有硬件堆栈，它们可以是任何大小的。

子程序调用和返回

和通常的 RISC 处理器类似， ARM 并不自动地把子程序返回地址放到堆栈上，而是把它转移到一个寄存器中，这样就可以避免末端子程序进行存储器访问。由于将返回地址压栈总是很慢，并且每个调用都需要 8 个字节而不是 4 个字节，所以增加了一个新的寄存器 L （ LINK ） , 它像数据栈顶元素寄存器 T 一样缓冲返回栈顶元素。两个新的指令是 RET 和 ：（冒号），用于实现末端子程序优化。当考虑 L 寄存器的时候，与返回栈相关的指令其语义只需要有很小的变化。

字节寻址

由于 ARM 是字节寻址的，P的增量必须是 4，增加关于字节的读取和存储指令看起来是明智的。

乘法

ARM 有硬件乘法指令，所以 +* 可以被 * 代替（ +* 除了乘法之外，还有其它的用途，但是，当硬件能够提供乘法时，删除一个很少使用的指令看来是合理的）。

NOP

ARM 不需要 no-op 操作，所以删除了 NOP 指令。这在任何需要的时候都可以通过 PUSH POP 或者 DUP DROP 一类的短语进行模拟。

OS 访问

增加了一个 SWI 指令以允许 ARM 的 SWI （软件中断指令）实现对操作系统的访问。

2 修订的 VM 模型

数据元素

栈 ： 数据栈 S， 返回栈 R

寄存器 ： T 、 L 、 A 、 P

2.2 执行循环

执行在 P 处的指令，如果指令没有修改 P 则 P = P + 4 ，重复

2.3 指令集

表 1 给出了指令集和它的语义。第一列给出了指令的名字，第二列是立即操作数的数目。它们被称为 V1 、V2 、…… 第三列给出了语义。使用如下的简化表示：“PUSH X TO T”意味着 “压 T 到堆栈 S ，将 X 的值置入 T”， “POP T TO X ”意味着“计算 X ，将 X 的值存入T ，从 S 中弹出 T”。

指令 操作数 Operation

# 1 push V to T

else 1 jump to V

T=0 1 jump to V if T = 0

C=0 1 jump to V if T31 = 0

call 1 set L to P_ 4, jump to V

ret 0 set P to L

: 0 push L to R

; 0 pop P from R

A@ 0 push A to T

A! 0 pop T to A

@A 0 push [A] to T

!A 0 pop T to [A]

B@A 0 push [A]0-7 to T

B!A 0 pop T0-7 to [A]0-7

@A+ 0 push [A] to T, add 4 to A

!A+ 0 pop T to [A], add 4 to A

B@A+ 0 push [A]0-7 to T, add 1 to A

B!A+ 0 pop T0-7 to [A]0-7, add 1 to A

pop 0 push L to T, pop R to L

push 0 push L to R, pop T to L

@R+ 0 push [L] to T, add 4 to L

!R+ 0 pop T to [L], add 4 to L

B@R+ 0 push [L]0-7 to T, add 1 to L

B!R+ 0 pop T0-7 to [L]0-7, add 1 to L

com 0 one’s complement T

2* 0 shift T one place left

2/ 0 shift T arithmetically one place right

* 0 set T to [S] = T, pop S

-or 0 set T to exclusive-or of [S] and T, pop S

and 0 set T to and of [S] and T, pop S

+ 0 set T to [S]_ T, pop S

dup 0 push T to T

over 0 push S to T

drop 0 pop T from S

swi 3 pop V2 arguments from T into ARM registers R0 to RV2-1,

call SWI V1, push V3 results from ARM registers R0 to RV3-1 to T

表 1 MF32 指令集

3 汇编器

正如所承诺的那样，写汇编器很容易。我增加了常用的汇编控制结构以实现 IF …… THEN 条件和 BEGIN …… REPEAT/AGAIN/UNTIL 循环，增加了MF基于 -IF 的变体。

在完成了编译器之后，我为汇编器增加了一个简单的窥孔优化以删除PUSH-POP 对；这可能比其它的汇编器需要更多的时间才能工作，但是代码却变短了。

4 编译器

编译器为最小的解释环境提供了足够的工具：一个解释器/编译器、数值输入和输出、具有创建一个新定义的字典能力。

5 Machine Forth 的困难

起步

正如预先看到的那样，由于不熟悉堆栈和算术操作符，代码很难编写，我发现很难记住 A@/A! 和 @A/!A 都是干什么的，我偶尔通过把后者作为 @A+/!A+ 才成功地记住了它们。

随着时间的推移，我开始发现一些普遍的习惯用法，比如使用 A 和 R 堆栈来改变元素的序列，有时使用 R 来存储循环计数和终值， DUP BEGIN DROP 去除条件循环的标志（因为 MF 的 IF 和 -IF 指令不弹出 T ）。

考虑可移植性

不管从 MF 中得到了什么感觉，我发现在考虑如何最好地实现一个字时，如果不去比较不同的 MF 指令序列与 ARM 翻译之间的差异是非常困难的。例如，在我的 MF32 实现中，为了在堆栈顶得到常数 0 ，使用 0 常数定义的方法是最快的。在 F21 中，使用 DUP DUP – 可能是最好的。这看起来似乎与 MF 的可移植性相矛盾，尽管在不同的体系结构中使用不同的代码序列可以得到相同的结果。然而，这个问题在任何的可移植语言中都会出现，不过在 MF 这种简单的结构中更加明显罢了。

指令 CACHE 同步

有一个问题是任何的 StrongARM 动态代码生成器所必须解决的，这就是它的指令 CACHE 不能与数据 CACHE 自动同步，一个简单和安全的解决方法就是增加一个字 CODE!, 它在地址存入时同步，构造并使用它存入字典（在 MF32 中还有另外一个字就是 THEN ）。

增加原语

我发现我需要几个 MF 没有提供的功能。我增加了 negate 、 minus 、 or 、 lshift 和 rshift 。我采用的笨拙的规则是：如果一个字用 ARM 指令来写可以比用 MF32 来写少几个指令，我就用 ARM 编码。

事实上，所有以上提及的都是作为内嵌原语实现的，好像它们是 MF32 汇编器的一部分。

其它用汇编编码的字

有几个写给 comp.lang.forth 的邮件对省略 SWAP 进行了冗长的讨论。我没有参与这种讨论，而是在我的系统中增加了 SWAP ，不过它只用了 4 次；其它时候通过一个局部交换，在 A 或者在返回栈中结束，将更加有效。其它的附加原语也很少使用，一般使用 2 – 3 次，唯一的一个例外是 OR ，它使用了 8 次。

EXECUTE 、 MIN 和依赖 OS 的 EMIT 、 SPACE 、 CR 和 BYE 也是用 ARM 汇编写成的。对于 EXECUTE 需要特别说明 : 在 F21 处理器中它是简单的 push ret, 但在 MF32 中却比较困难，尽管可以做。你可以进行一个练习，但在看第 9 部分的答案之前，先思考一下。

缺乏堆栈捣弄

MF 缺乏捣弄堆栈的字，这就给一般的 Forth 程序员增加了压力，要求他们避免捣弄堆栈，并且更加强烈地要求进行因子分解。初看起来这是一个紧箍咒，但我发现只有 1 、 2 个字由于缺少 PICK 和 ROLL （ NUMBER 特别狡猾）而变得难于编写。尽管如此，我仍然不习惯于 MF 。

除法

对于数值的输入和输出来说，除法是必须的。 MF 和 ARM 都没有除法指令，所以我使用除法子程序。

读写堆栈指针

一个严重的缺憾是 MF 不能够读写堆栈指针：它对于在 QUIT 中实现 DEPTH 复位堆栈非常重要。而在 F21 处理器中，由于堆栈是用硬件实现的，所以不太重要，但对于软件来说，这就非常不同了，因为这可以防止存储器泄漏。我避免这个问题的方法是：让 QUIT 简单地分支到初始化代码，重新设置堆栈指针。

6 ARM Forth

在结束了 ARM 的 MF32 之后，我用 ARM 代码编写了编译器。这听起来像 Moore 所谓的“硬件 Forth”, 但有一个不同：当 CMForth 编译器的硬件结构由一个机器指定时（在这种情况下， 是NOVIX Forth 芯片）， ARM 的 Machine Forth 是严格地与 Machine Forth 一致的，仅仅是使用 ARM 机器模型而不再是 MF 模型。

代码不仅更小，至少更容易编写（实际上，许多字第一次工作，它们不是 MF32 版本的本地码翻译，而是完全重写以便能够利用 ARM 的优点）。 ARM 小而且规则的指令集在代码尺寸上完全可以与 Machine Forth （它含有大约 20 条基本指令）相比，但它有更丰富的算术和逻辑操作、寻址模式和 Machine Forth 没有的特性，比如条件执行。

另一方面，由于 ARM 是基于寄存器的机器，这就导致两个编译器：有些字在交互环境中非常有用，比如 DUP 和 + , 但是在编译代码中却很少使用，在编译代码中，需要开发寄存器的寻址能力。

7 MF32 和 ARM Forth 的比较

尺寸

表 2 给出了 MF32 和 ARM Forth 系统的一些比较。表中指出代码密度是每个 MF32 指令为 1.5 ARM 指令或者说是 6 个字节。

表 2: MF32 和 ARM Forth 的比较

窥孔优化节省了大约 100 条指令，相当于全部生成代码的 9%。

但是我们同时也看到， ARM Forth 比 MF32 多 66 条指令，因为 ARM 芯片的汇编器比 Machine Forth 汇编器更复杂，二进制代码小了 32 单元，包含 326 个更小的代码。此外，许多在两个系统中都有的指令，用 ARM 指令比用 MF32 指令要小。似乎 ARM 的代码密度是 MF32 的两倍。

速度

我们把两个基准程序分别在 MF32 系统、 ARM Forth 系统、一个本地码子程序串线 ANSI Forth 编译器（ aForth 0.75, 可以从 http://sc3d.org/rrt/ 得到）和 GNU C 上运行。第一个代码是一个简单的随机数发生器，如图 1 所示（考虑篇幅的原因我们略去了 C 代码，它是一个 ANS Forth 版本的文字翻译，可以在 Machine Forth 发布中得到）。

表 3: 随机数基准测试

表 4 : 素数基准测试

第一次测试运行了 10,000,000 次循环 , 第二次是一个简单的素数查找器，查找到了 10000 素数（最好是运行一些著名的基准测试，比如 Ertl 的整数测试集，但是没有足够的时间把它们翻译成 Machine Forth 和 ARM Forth ）。

ARM Forth 是最小和最快和版本，但是令人惊奇的是 ANSI Forth 代码也比 MF32 版本更小而且更快（素数基准测试花费了大约 60%的时间用于执行软件除法子程序，所以这是不重要的，尽管在随机数基准测试中也表现了同样的倾向）。

在本文的一个早期版本中，我曾经愚蠢地写下了“MF32 的速度将明显地位于子程序串线和本地码编译器之间”。尽管通过几个基准测试就否定这一结论同样是愚蠢的，但是 MF 说明的速度和代码密度需要进一步考察，至少在典型的桌面体系结构中应该如此（在 INTEL 的实现中，也发现了类似的代码密度见 comp.lang.forth ）。

图 1 随机数基准测试程序

编程的舒适性

ANSI Forth 和 MF32 在编程的舒适性上是相同的。与具有编写编译程序的经验相反， ARM Forth 比较困难。 ARM 代码也比 Forth 更长更难读，实际上， ARM Forth 更难因子化，因为在 ARM Forth 中，返回标志的定义将要自然地修改 ARM 寄存器而不是在栈顶返回一个标志值，但这在当前是不可能的，因为标志阻止了跨子程序的调用。也许这一点是需要改变的。

然而，这样比较 Machine Forth 和 ARM 代码是不公平的，因为前者是为 MF 而设计的，后者却不是。使用一个更自然的编码风格， ARM 汇编将和 Machine Forth 一样容易写，并且如果从一个传统的 Forth 编译器内部来使用它，它也是可以交互式测试的。

8. 结论

本文只是一个很少经验的总结，通过写一个编译器来得到关于 Forth 编程的结论总是不明智的。很明显， MF 容易实现，但那只是从机器模型的角度来观察而得到的结论。对于我来说， Machine Forth 落入了两难的选择：对于高级代码，我更愿意编写完全标准的 Forth ，对于低级代码，我更愿意有强大的，高速的、紧缩的汇编器（当然是在一个 Forth 编译器中使用）。

这个印象也许来自我已经广泛编程的处理器（6502、MC68000 和 ARM ）都有小的和简单的指令集。对于一个不熟悉的处理器，特别是对于那些大的和复杂的指令集的处理器，与学习本地汇编语言相比， MF 的简单性也许可以帮助我们更快地产生合理的代码。

MF 的可移植性也可以作为它的特点被提及，不过那只是编写高级代码时的一个优点；当 MF 作为汇编语言的替代时，编码就无论如何也是机器相关的，这里谈论可移植性就没有任何意义了。

然而， MF 也的确提供了一些有益的思想。对于那些不能提供优化器的小 Forth 编译器，显式地使用地址锁存器就是提高性能的最简单方法。更有趣的是它非破坏性的条件测试可以很容易地用于传统的 Forth 中。

所以， MF 的新颖性和传统简单性的混合进行仔细研究并混合是有益的，尽管我不会因为这些就放弃了 Forth 和汇编器的传统组合。

9 练习的答案

EXECUTE 可以这样地用 MF32 写出

A! pop A@ push push ;

10 感谢

Jeff Fox was kind enough to read and comment on the paper, a referee made several helpful comments, Hanno Schwalm pointed out the weakness of the primes benchmark, and Marcel Hendrix asked for the comparison with C.

References

[1] M. Anton Ertl. Performance of Forth systems, 1996. http://www.complang.

tuwien.ac.at/forth/performance.html.

[2] Charles Moore and Jeff Fox. Preliminary specification of the F21, 1995. http:

//pisa.rockefeller.edu:8080/MISC/F21.specs.

[3] VLSI Technology Inc., Eaglewood Cliffs, NJ. Acorn RISC Machine family Data Manual,

1990.