堆栈计算机的原理和实现

第三章 多堆栈、 0 操作数计算机

本章主要讨论按每二章分类的、属于MS0和ML0类的多堆栈、0- 操作数计算机。

在3.1中，我们将比较堆栈计算机与传统的 CISC 和 RISC 体系结构之间的区别。

在3.2中，我们将描述一个被称为 Canonical Stack Machine （规范堆栈计算机）的原型堆栈计算机结构，我们将给出方框图和实现的指令集。这种两堆栈的机器可以作为后面各章的真实堆栈计算机的起点。

在3.3中，我们将简单地讨论 Forth 程序设计语言。 Forth 是一种非传统的计算机程序设计语言，它使用一个双堆栈计算模型，鼓励使用很多的短小过程调用。许多 ML0 和 MS0 设计都发源于 Forth 语言，当然也非常适合于用 Forth 进行程序设计。

3.1 我们为什么对这类计算机感兴趣？

多堆栈、 0- 操作数计算机与其它计算机相比，有两个固有的优点： 0- 操作数寻址方式使指令尺寸最小，多个堆栈允许子程序调用和数据处理并发进行。这些特点和其它的特点使得程序代码短小、系统复杂度低、系统性能高。 MS0 和 ML0 之间的主要差异是 MS0 为了降低 CPU 的成本而使用了最少的资源来构造堆栈缓冲区，当然这样做也同时舍弃了一些性能。

我们将在第六章讨论堆栈计算机如何得到这些优点，现在，我们考察的是得到这些优点背后的细节。

首先，让我们汇总一下这些优点。

堆栈计算机通过两方面来缩小程序大小：一是通过鼓励更多地使用子程序来减少代码的大小，二是基于堆栈计算机指令短小的事实。小的程序尺寸减少了存储器成本、元件的数量和功耗，通过使用成本更有效的、更小的、更高速的存储器芯片来提高系统的速度。附加的优点包括在虚拟存储环境下更好的性能，几乎不需要为提高命中率而设计CACHE 。 0- 操作数计算机比其它机器有更小的代码尺寸。

降低系统复杂度也就减少了开发时间，也减少了芯片尺寸。这也为片上程序存储器和半定制特性留下了更多的芯片面积。

一个系统的性能不仅仅是指原始的执行速度，同时也包括整个系统的性能和系统在实际真实世界中的适应性。系统性能中的速度也不仅仅是指每秒钟可以执行多少条线性指令，更应该考虑分支和过程处理导致的性能降低。在堆栈计算机中， 0- 操作数寻址模式和更多地使用子程序调用以减少代码尺寸和系统复杂度的实际结果是：为应用程序改进了系统性能。

堆栈处理器支持高效率过程调用的另一个附加好处是从体系结构上鼓励程序员使用许多小的过程而改进了代码结构，通过鼓励更好的编码习惯而提高了可维护性，通过把小的子程序当成构建块来使用而提高了代码的可重用性。

3.2 一个原型化的规范堆栈计算机

在涉及真实的 MS0 和 ML0 设计细节之前，我们需要建立一定的基准，所以我们将考察一个规范的 ML0 计算机设计。这个设计尽可能地简单以便作为比较其它设计的共同出发点。

3.2.1 方框图

图 3.1 是规范堆栈计算机的方框图。图中的每个框代表了与 ML0 最基本组件对应的逻辑资源。这些组件是：数据总线，数据堆栈 DS ，返回堆栈 RS ，带有栈顶寄存器 TOS 的算术逻辑计算单元 ALU，程序计数器 PC，有指令寄存器 IR 的控制逻辑，以及输入输出部分 I/O 。

图 3.1 规范堆栈计算机

3.2.1.1 数据总线

为简单起见，规范堆栈计算机只有一个单一总线连接系统的所有资源。真实的处理器可以使用多条数据总线以便于指令读取和计算并行操作。在规范堆栈计算机中，数据总线在任何单操作周期中都允许单个的发送功能模块和单个的接收功能模块。

3.2.1.2 数据堆栈

数据堆栈是一个使用内部机制实现 LIFO 堆栈的存储器。通常的实现方法是使用传统的存储器配合一个增/减计数器用来产生存储器地址。数据堆栈允许两个操作：PUSH 和 POP 。 PUSH 操作在堆栈顶部分配一个新的单元，把数据总线上的值写入这个单元。 POP 操作把堆栈顶部的元素放到数据总线上，然后删除这个单元，把堆栈上的下一个元素露出来以便进行下一次操作。

3.2.1.3 返回栈

返回栈是使用与数据栈相同的方法实现的一个 LIFO 堆栈。唯一的区别是返回栈用于存储子程序的地址而不是指令的操作数。

3.2.1.4 ALU 和栈顶元素寄存器

ALU 功能块对两个数据元素执行算术和逻辑计算，两个数据元素中的一个是栈顶元素寄存器 TOS ，它保存着给程序员使用的数据堆栈上最顶端的元素。这样，实际的数据模块顶端元素是程序员可以见到的每二个元素，因为第一个元素是在 ALU 的一个寄存器 TOS 中。这种策略可以保证在对堆栈上的两个元素进行操作时，比如加法，能够使用单端口数据堆栈存储器。

ALU 支持任何计算所需要的原语操作。为了说明方便，只包括加法、减法、逻辑功能（ AND 、 OR 、 XOR ）、零测试。由于这里只是概念设计，所以算术操作都是整数。当然没有任何理由说不能给 ALU 扩展浮点算术操作。

3.2.1.5 程序计数器

程序计数器保存着将要执行的下一个指令的地址。 PC 可以从数据总线装入以实现分支，也可以在程序存储器顺序取下一个指令的时候增量。

3.2.1.6 程序存储器

程序存储器模块包括一个存储器地址寄存器(MAR)和一定数量的随机访问存储器单元。为了访问存储器， MAR 首先写入要读出或者存入的地址，然后在下一个系统周期，程序存储器单元或者从数据总线读入或者向数据总线写出数据。

3.2.1.7 I/O

和许多概念设计一样，我们对输入输出的讨论也将是一带而过的。这里能说明的只是 I/O 也是系统资源， I/O 模块处理这个任务，不过，说出这些也就足够了。

3.2.2 数据操作

表 3.1 给出了规范堆栈计算机的最小操作指令集，选择这样一个操作指令集的目的是解释计算机的使用 -- 很明显，对于高效率的程序执行并不是足够的。实际上我们没有包括乘法、除法和移位操作，原因还是为了简化。表述的方法参看 Forth 语言（见 3.3 ），这也是我们后面各章讨论时用到、被广泛使用的表达方法。值得注意的是， Forth 经常使用一些特殊的字符，比如用！（在 Forth 中读作“存储”）和 @( 在 Forth 中读作“读取” ) 。

表 3.1 规范堆栈计算机的指令集

3.2.2.1 逆波兰表示法

堆栈计算机使用后缀表示法执行数据处理操作符，这些操作符通常称为“逆波兰表示法（ RPN ）”。后缀操作的最明显特征是操作数在操作符之前。例如，传统的表达式（中缀）表示这样的内容：

(12 + 45) * 98

在这个表达式中，使用括号来强制加法在乘法之前计算。甚至在没有括号的表达式中，也有隐含的操作符优先级规定，例如，没有括号的乘法应该在加法之前计算。上面加了括号的表达式写成等效的后缀形式应该是：

98 12 45 + *

在后缀表示中，操作符对最近可见的操作数进行操作，隐含使用一个堆栈用于计算。在这个后缀的例子中，数 98 、 12 和 45 如图 3.2 所示推入堆栈，然后 + 操作对栈顶的两个元素（数 25 和 12 ）运算得结果 57 ，最后 * 操作对两个新的栈顶元素 57 和 98 操作，结果是 5586.

图 3-2 逆波兰表示法的例子

后缀表示法与中缀表示法相比，有一个很经济的地方，这就是它不需要任何操作符优先级，也不需要任何括号，它非常适合计算机的需要。事实上，编译器都是把 C 或者 FORTRAN 语言中的中缀表达式翻译成后缀机器代码的，只是有时用显式的寄存器分配来代替表达式堆栈。

前面描述的规范堆栈计算机被设计成直接执行后缀操作符，不需要编译器处理寄存器分配。

3.2.2.2 算术和逻辑操作符

为了完成基本的算术运算，规范堆栈计算机要求算术和逻辑运算符，下面对每一条指令进行讨论，并使用寄存器传输级伪码进行描述，它们将是自解释的，比如，第一个运行符是加法：

对于 + 操作，用户可见的栈顶 2 个元素 N1 N2 弹出后相加，结果 N3 压入堆栈。从实现的角度看，这意味着弹出 DS （它给出 N1 ）并与包含 N2 的 TOSREG 的值相加，其结果是 N3 留在 TOSEG 寄存器中，作为用户可见的数据栈顶。被 POP （ DS ）访问的 DS 元素实际是程序员可见的次栈顶，但却是实际硬件堆栈的顶元素。把 TOSEG 作为堆栈顶寄存器的表示与 POP （ DS ）是一致的。注意把 TOSREG 作为一个元素的堆栈缓冲区后， POP N2 和后面 PUSH N3 的操作就可以省略了。

我们可以清楚地看到，在执行这些操作的时候，使用栈顶元素寄存器可以节省大量的工作。

3.2.2.3 堆栈处理操作

纯堆栈计算机有一个问题，就是它们在算术操作时只能访问栈顶的两个元素。于是，需要一些额外的指令来为其它的操作准备操作数。当然，应该说某些基于寄存器的计算机也需要花费大量的指令做寄存器到寄存器的拷贝工作以便为操作做准备，所以，哪一种方法更好的问题就变得比较复杂了。

下面这些指令都与处理堆栈元素相关。

本指令和下面一些指令的定义中都使用了 TOSREG <= POP(DS) 这种表示方法。为了完成这个操作，需要把数据堆栈的信息放到数据总线上，然后通过 ALU 执行一个哑操作（比如加 0 ）放到栈顶元素寄存器中。

当我们观察上面的定义时，发现 OVER 从概念上看起来很简单，然而操作却非常复杂，它需要临时存储 N2 。在实际的机器中，可以增加一个或者几个临时存储寄存器以减少 OVER SWAP 和其它堆栈操作的负担。

指令 >R 和它对应的 R> 允许在数据栈和返回栈之间交换数据。这种技术通过把数据栈元素放到返回栈上来访问隐藏在堆栈中两个元素以上深度的数据。

3.2.2.4 存储器读取

尽管所有的算术和逻辑运算都是对堆栈上的数据元素进行操作的，但这些数据却必须在操作之前从存储器读到堆栈上或者在操作之后把信息存储到存储器中。规范堆栈计算机使用简单的 LOAD/SATORE 体系结构，所以只有单个的装入指令 @ 和单个的存储指令 ! 。

由于指令没有操作数字段，存储器的地址是从堆栈上得到的。这对数据结构的访问非常方便，因为堆栈可以用来保存访问数组元素下标的指针。由于存储器必须访问两次，一次用于指令读取，一次用于数据，所以执行这些指令需要两个存储器周期。

3.2.2.5 文字量

有时需要把一个常数放到堆栈上，完成这个功能的指令被称为常数指令，在基于寄存器的计算机中也常常被称为装入常数指令。常数指令使用两个连续的指令字：一个用于实际的指令，另一个是压入堆栈的常数。常数需要两个存储器周期，一个用于指令，一个用于存储器元素。

这个实现假设在当前的操作码执行之后，PC已经指向了下一个指令的位置。

3.2.3 指令执行

到现在为止，我们都忽略了一个指令是如果实际地从程序存储器读取和执行的，这个执行过程包含典型的指令取指、译码和执行序列。

3.2.3.1 程序计数器

程序计数器是一个寄存器，它是记录下一个被执行指令的指针。在取指之后，程序计数器自动增量以指向存储器的下一个字。在分支或者子程序调用的情况下，程序计数器用分支的目的地址值装入。

3.2.3.2 条件分支

为了实现判断，计算机必须必须有某种进行条件分支的方法。规范堆栈计算机使用的也许是最简单的方法：条件分支通过判断栈顶元素是否为 0 而执行。这种分支可以省去条件代码，也允许实现所有的控制流结构。

3.2.3.3 子程序调用

最后，规范计算机必须有一种方法来实现高效率的子程序调用。因为有一个专用的返回栈，子程序调用只是简单地把当前程序计数器的值压入堆栈，然后把新的值装入程序计数器。我们假设用作子程序调用的指令能够在一个指令字中指定全部的子程序地址，忽略从指令中分离出代码实际地址字段的过程。为了完成这个功能，我们后面章节讨论的实际机器只需要很小的硬件开销。

子程序返回简单地从返回栈的顶部得到返回地址，并把这个地址放到程序计数器中。由于数据参数是在数据栈上维护的，子程序返回不需要操作指针或者存储器位置。

3.2.3.4 使用硬连线还是微码来实现指令

规范堆栈计算机由于考虑从概念上进行简化，当然不需要考虑实现方面的问题，但是设计折衷的一个主要考虑就是真实的实现。其中的一个问题是使用硬连线还是微码控制，这两种技术的介绍可以见 (Koopman 1987a).

硬连线的设计通常更快，也能得到更有效的空间性能。为性能而增加的成本通常是增加译码电路设计的复杂性，一个主要的风险是：如果在一个产品的设计周期结束时改变了指令集，则就要求重新设计整个控制逻辑。

对于一个堆栈计算机来说，它的指令集非常简单，通常没有其它计算机体系结构中常见的操作数/类型方面的组合爆炸现象。由于这个原因，硬连线方式的堆栈计算机就相对更直接。

作为一个附加的优点，如果一个堆栈计算机有16位指令或者更多的位长度，用于指定可用编码的指令位与字的长度相比就很小。硬连线实现的堆栈计算机可以利用这个特点使用预编码的指令格式以进一步简化设计并提高灵活性。预编码（也称为非编码）指令的格式与微码格式类似，通过特定的位来指示特定的动作。这就能够把几个独立的操作组合在一个指令中（比如 DUP 和 [EXIT] ）。

如果 16 位的指令也显得浪费，就选择固定长度的指令以简化译码，并允许子程序调用以相同于其它指令的长度来进行编码。一个编码子程序调用的简单策略是设置最高位为 0 来指定子程序调用（15 位的地址字段）或者 设置最高位为 1 用于编码（给出 15 位的非编码指令字段）。通常，固定长度指令速度上的优点和压缩多个操作指令的可能性使我们有理由选择固定长度指令格式。在堆栈计算机上使用非编码硬连线技术最早开始于 Novix NC4016 ，以后就为其它设计所用。

由于使用硬连线指令译码实现堆栈计算机有这么多的好处，我们很可能会自然地想到，那就再也不会使用微码方式来实现堆栈计算机了。但是，使用微码方式实现也有几个优点。

微码方式的主要优点是灵活性。由于一个非编码硬连线指令中许多组合位都没有使用，微码计算机就可以使用不多的几个位来指定相同的操作，包括执行一系列堆栈功能的优化指令。这种体系结构为用户指定操作码留下了空间。一个微码计算机可以有几个复杂的、多周期的用户指定的指令，而使用硬连线技术实现会很不方便。如果一些或者全部的微码存储器都是用 RAM 构成的，由还可以为每个用户甚至每个应用定制指令。

使用微码方式的一个潜在缺点是为了弥补访问微码存储器而产生的速度方面的损失，通常需要建立一个微码取指流水线。这就可能使指令的执行时间多于一个周期，反之，硬连线的机器都优化成单周期执行。

不过话又说回来，这也不是什么真正的缺点。如果把处理器速度与存储器的速度进行适当的匹配，许多处理器都可以在单个存储器访问周期中执行两个内部操作。于是不论是硬连线设计还是微码设计都可以在一个存储器周期中执行一个指令。此外，由于微码可以在每个存储器周期中活动多达两次，就有更多的机会优化代码并执行用户定制的指令。

实际是，微码实现对于分离元件设计更为方便，所以它们是板级应用；大多数的单芯片设计都是硬连线的。

3.2.4 状态改变

在实时控制应用中，一个重要的考虑因素是处理器如何处理中断和任务切换。规范堆栈计算机特定的指令集在一个特定的范围内回避了这个问题，所以我们来讨论处理这些问题的标准方法以便为今后的设计比较建立一个基准。

使用独立堆栈存储器的堆栈计算机有一个隐含的责任：在任务改变时把堆栈交换到程序存储器，这种工作需要保存大量的状态信息。我们将看到这种状态改变怎样在大多数情况下得以避免。第六章讨论了能够进一步减少任务切换负担的更好技术。

3.2.4.1 堆栈溢出 / 下溢中断

中断或者是由于异常事件引起的，比如堆栈溢出，或者是被 I/O 服务请求引起。所有这些事情都要求在不打断当前任务流的情况下快速地处理。

在堆栈计算机中，堆栈溢出/下溢是到目前为止最常见的异常情况，所以它将被作为一个例子用于说明中断是如何处理的。

当应用程序用完了堆栈存储器时，就会发生堆栈的溢出/下溢。对于这种情况有几个可能的响应：忽略溢出并让软件崩溃（实现起来很容易，但效果并不怎么样），或者用一个致命错误来停止程序，或者把堆栈存储器的一部分复制到程序存储器中并允许程序继续执行。很明显，最后这种方法有最大的灵活性，在某些环境中实现更简单，但是一个致命的执行错误可能被接受。

其它的异常情况比如存储器奇偶错误也可以被系统处理。

异常情况的处理需要许多时间，但是它们都有共同的性质：要求在处理时完整地保存当前状态，以使得任务在可能的情况下重新启动。在堆栈计算机上，这些条件并不要求处理器动作，而仅仅是强制硬件产生一个对情况处理编码的子程序调用。

3.2.4.2 I/O 服务中断

I/O 服务在实时控制系统中是一个要求快速执行的潜在的经常事件。幸运的是，中断通常只需要很小的处理器资源，几乎不需要临时存储器。由于这个原因，堆栈计算机把中断作为一个硬件产生的子程序调用来对待。

这些子程序调用把参数压入堆栈，执行它们的计算，然后执行一个子程序返回以重新启动被中断的程序。唯一的限制是中断服务程序不能在堆栈上留下“垃圾”。

在堆栈计算机上处理中断比在传统计算机上处理所花的代价要低得多，这有几个原因：因为堆栈是自动分配存储器的，所以不需要保存寄存器；因为分支条件是作为标志保存在堆栈上的，也不需要保存条件寄存器；多数堆栈处理器只使用很小的数据流水线，或者根本就没有流水线，所以在收到中断时也就不需要保存流水线的状态。

3.2.4.3 任务切换

处理器为了表现出多个程序同时执行的效果，需要在程序之间进行转换，这时就会产生任务间的切换。在任务切换时被停止处理的程序状态必须被保存以便于后来恢复。被启动程序的状态在恢复执行前必须被放到机器适当的位置。

实现任务切换的传统办法是用一个定时器，在每个时钟 TICK 的时候交换任务，有时还需要满足优先级和任务调度算法。在一个简单的处理器中，用于保存堆栈和存储器的状态、或者在每次上下文交换时重新装入都是一个巨大的负担。解决的方法之一是编写“轻量级”任务，它们只使用很少的堆栈空间。这些任务可以把它们自己的参数放在现有堆栈元素的上面，当任务结束时移去它们，这样就避免了“重量级”进程潜在地、更昂贵地保存和恢复堆栈。

另一个解决方案是为多个任务提供多个堆栈指针，并指向相同的堆栈存储器硬件。

3.3 Forth 程序设计语言概览

3.3.1 Forth 作为一个通用的串线

由于现代的堆栈处理器都源自 Forth 程序设计语言，所以我们现在就简单地介绍一下这种程序设计语言。

Forth 程序设计语言是 Charles Moore 发明的 (Moore 1980) ，用于小型计算机控制天文台的射电望远镜。正因为如此， Forth 强调效率、紧缩、灵活和高效率的软件和硬件交互。同时， Forth 也非常强大，可以并已经被应用于大量的通用编程任务：数据库管理、会计软件、字处理、图形、专家系统和科学计算。

附录 B 包括了 Forth 语言的操作原语列表。

使用 Forth 语言编程的一些优点包括：程序易于模块化、易于调试，极其灵活、非常快的编译/编辑/测试周期，在大量计算机之间高度的可移植性，紧缩的源代码和目标代码 (Jonak 1986) 。 Kogge (1982) 描述了串线代码软件环境，强调了 Forth 语言的底层机制。

3.3.2 Forth 语言虚拟机

为了解决最初的望远镜控制问题， Forth 需要几个重要的品质：它必须适合实时控制，很高的交互性以便于非程序员使用，必须满足几个存储器限制条件。

向这个目标进发，这种语言有两个主要的特点：使用串线代码和 0- 操作数堆栈指令。为了从语言操作方面建立概念，把 Forth 虚拟机作为计算模型。这种 Forth 虚拟机有两个堆栈：数据栈和返回栈。 Forth 程序实际是在主机的硬件上对 MS0 机器代码所做的一个模拟。 Forth 程序由很小的子程序组成，这些子程序只是调用其它子程序或者堆栈操作指令原语。程序的组成像一棵树，每个子程序调用都基于下层子程序一个小的子集。

很明显， Forth 是我们已经讨论的 0- 操作数规范堆栈计算机的自然的汇编语言。

我们应该注意到，尽管处理器设计成 Forth 处理器，它仍然有能力执行任何其它高级语言，这是因为 Forth 的原语是在很低的级别上定义的，它对应的机器代码操作在任何堆栈计算机上都是存在的。这样，宣称是“Forth 计算机”的计算机通常也适合其它高级语言。

3.3.2.1 堆栈体系结构 /RPN

Forth 语言的原语包括了所有在表 3.1 中所列的规范堆栈计算机的操作，没有被 `[...]' 括起来的名字都与 Forth 的功能精确对应。

带括号的名字 [IF] 、 [CALL] 、 [EXIT] 和 [LIT] 自动地编译到内部函数用以支持程序运行。例如， [IF] 是编译器遇到条件分支时编译成执行条件分支， [CALL] 在遇到一个非原语操作时引用一个 Forth 字， [EXIT] 被定义结束的字编译或者一个字 EXIT 时编译。最后，如果程序中遇到一个常数值比如1234时 [LIT] 被编译。

有几个 Forth 结构，比如 LOOP 、变量和常数，并不直接被规范堆栈计算机支持，但是可以使用几个简单的操作来模拟。很明显，一个 Forth 语言计算机应该提供对常用 Forth 结构的直接支持。

3.3.2.2 短的、常用的过程调用

Forth 程序与其它语言程序的主要区别是高频率的子程序调用。好的程序设计风格鼓励使用小的子程序进行增量式程序开发和测试。子程序通常含有5或者10个指令。统计频率显示如果程序中大约有50%指令是子程序调用，则认为是正常的。

这种软件环境允许非常快速和精确地构造程序，在存储器能力受到限制的环境中特别有效，这同时也鼓励了通过快速子程序调用的方式来使用计算机。

3.3.3 强调交互性和灵活性

Forth 程序设计语言的一个主要优点是在其开发环境中各个级别的交互性，开发工具包括一个集成的增量编译器和一个编辑器允许交互式地测试和单独修改过程。鼓励编写小的过程和模块代码能够在开发过程中方便和快速地测试，在第一次编写之后，就很少需要再定位这个字。大多数 Forth 程序员都表示在大范围的应用程序中， Forth 语言可以比其它语言减少10倍的开发时间。

Forth 程序强调灵活地解决问题。因为 Forth 是一个可扩展的语言，新的数据结构、控制结构可以加入到语言中以支持专门的应用领域。这种灵活性允许通过一个或者两个程序员去解决用其它语言、靠一大堆程序员才能解决的问题，减少项目管理的开销，大大提高生产率。 Forth 并没有努力地用于大规模的程序开发，所以它在大规模的应用程序中的效率还没有被认知。