漫谈Stack-Based VM的设计(1)
Stack-based VM（栈式虚拟机）是一种用栈结构来管理指令执行和内存操作的虚拟机模型。可以把它想象成一个"叠盘子"的机器——每次操作都从栈顶取数据，结果也放回栈顶，使用者不需要关心数据存储在哪里。
它的核心特点是：所有算术运算、逻辑运算、函数调用等操作，都通过压栈（push）和弹栈（pop）来完成。比如计算"1+2"，会先把1和2压入栈，然后执行加法指令，从栈顶弹出两个数相加，再把结果3压回栈顶。这种设计让指令集变得非常简洁（每条指令通常只有操作码，不需要指定操作数地址），但相比寄存器式VM，因为频繁的栈操作会产生额外开销，执行效率相对较低。
很多编程语言的运行时环境都采用这种模型，因为它实现简单、跨平台性好，适合作为中间表示层。
这里说的"栈"指的是操作数栈（operand stack），用于临时存放计算过程中的数据，和程序调用栈（call stack）是分开的。
怎么设计一个最小的VM
VM 的本质
一个 VM 至少需要三样东西：指令序列（Bytecode）、执行状态（State）、解释循环（Fetch → Decode → Execute）。
所以最小 VM 可以被描述为：
while (true):
instr = code[ip]
ip++
execute(instr)
区别只在于：状态如何组织。
为什么选择 Stack-Based？
在 Stack-Based VM 中，核心状态是一个操作数栈（Operand Stack）和一个指令指针（IP）。指令隐式地从栈中取操作数、把结果放回栈中。
例如：
PUSH 1
PUSH 2
ADD
执行过程：
stack: []
PUSH 1 -> [1]
PUSH 2 -> [1, 2]
ADD -> pop 2, pop 1, push 3 -> [3]
Stack-Based VM 最重要的特点：指令不需要显式指定操作数位置。
关于 Stack-Based VM 的 PUSH、POP 和 DUP 指令
为什么在很多 Stack-Based VM 的指令中看不到 PUSH 指令？
Stack-Based VM 一定存在 push 行为，只是：push 往往是"指令的副作用"，而不是一个独立、频繁出现的显式操作。所以不会单独设计一个 PUSH 指令。
例如：
LOAD_CONST 42 → push 常量
ADD → push 运算结果
CALL → push 返回值
因此说：push 指令隐藏在几乎其他所有指令中。
POP 指令用于控制副作用，必不可少。如：
CALL f
POP
如果不关心 f 的返回值，就必须显式丢弃它。
DUP 指令是用于值共享，如计算 x + x：
LOAD x
DUP
ADD
没有 DUP 指令，就必须重新计算或重新加载，或者设计一个 ADD 的变体。
总结一下：值的产生 = 自动 push，值的消费 = pop，值的复用 = dup。这使得 Stack-Based VM 的指令集可以极小化。
常见指令汇总
为了方便参考，这里列出 Stack-Based VM 中出现频率较高的指令及其栈效果：
| 指令 | 描述 | 栈效果 |
|---|---|---|
LOAD_CONST x |
将常量 x 压入栈 | [] → [x] |
LOAD var |
将变量 var 的值压入栈 | [] → [val] |
POP |
弹出栈顶元素并丢弃 | [a] → [] |
DUP |
复制栈顶元素 | [a] → [a, a] |
ADD |
弹出两个数，将和压入栈 | [a, b] → [a+b] |
SUB |
弹出两个数，将差压入栈 | [a, b] → [a-b] |
MUL |
弹出两个数，将积压入栈 | [a, b] → [a*b] |
CALL f, n |
调用函数 f，消费 n 个参数，压入返回值 | [arg1..n] → [ret] |
RET |
从当前函数返回 | [ret] → []（回到调用者栈帧） |
从 Lisp（Scheme）的视角看 Stack-Based VM
Lisp / Scheme 是理解栈式 VM 的理想语言，原因在于它的语义天然匹配栈模型：表达式为中心、一切都有返回值、嵌套结构直接对应栈的入栈出栈顺序。
一个简单的例子：
(+ (* 2 3) 4)
编译为 Stack-Based Bytecode：
LOAD_CONST 2
LOAD_CONST 3
MUL
LOAD_CONST 4
ADD
Stack 的变化如下：
[]
[2]
[2, 3]
[6] ← MUL 弹出 2 和 3，压入 6
[6, 4]
[10] ← ADD 弹出 6 和 4，压入 10
可以看出，Scheme 表达式的嵌套层次结构，恰好对应了栈的时序。内层表达式 (* 2 3) 先执行并将结果留在栈上，外层表达式 (+ ... 4) 再消费它。
再看一个函数调用的例子：
(f (+ 1 2))
LOAD_CONST 1
LOAD_CONST 2
ADD
CALL f, 1
这里参数 (+ 1 2) 先被计算并留在栈顶，然后 CALL 指令直接从栈上取走它作为参数。如果是多参数调用，比如 (f (+ 1 2) (* 3 4))，参数会按顺序依次计算并压入栈，最后一个 CALL f, 2 一次性取走两个参数。这种机制让函数调用的编译变得非常自然。
Stack-Based VM 的优缺点
Stack-Based VM 的优点在于：指令集简单；Bytecode 体积小（很多场景看中这个优点）；编译器实现容易；非常适合解释执行；天然匹配表达式语言。
Stack-Based VM 的缺点在于：指令条数多；频繁 push / pop；对 JIT 和 CPU pipeline 不友好（你主动想要优化难，现代 CPU 也难高效执行）；隐式数据依赖，优化困难（在编译器层面）。
Stack-Based VM 以外的 VM
除了栈式 VM，另外两种常见的架构值得了解。
Register-Based VM（寄存器式虚拟机）：它的核心区别在于，指令会显式指定操作数所在的寄存器编号，而不是隐式地从栈顶取数据。比如同样的 1+2，栈式 VM 需要 PUSH 1; PUSH 2; ADD，而寄存器式 VM 只需要一条指令：ADD R0, R1, R2（将 R0 和 R1 的值相加，结果放到 R2）。这样指令条数少、数据依赖显式，对优化和调度友好，但每条指令的体积会更大（需要编码寄存器编号）。Dalvik VM（Android）和 Lua VM 都是典型的寄存器式 VM。
混合设计：有些 VM 会在不同层级混合两种方式。比如底层用栈式的字节码表示（利用其体积小的优势），但在 JIT 编译或运行热路径时，将栈式代码转换为寄存器式的中间表示来做优化和代码生成。这种方式试图兼顾两者的优势。
现实世界中的 Stack-Based VM
很多 Scheme VM 都是经典的 Stack-based VM。
传统的 JVM 是标准的栈式虚拟机，应该也是最具影响力的。（Android 上的 Dalvik VM 则是 Register-based VM。）
在文曲星上有个 LavaX，可以编译运行 C 代码，它的运行时也是 Stack-Based VM，现在在 GitHub 上可以找到相关资料。
历史上 Stack-Based CPU
除了软件实现的 Stack-Based VM，还有硬件级的实现。
Burroughs B5000 系列：人类历史上最成功、最纯粹的栈式 CPU 架构之一。它的指令集和内存管理都围绕栈来设计，对后续栈式体系结构的研究有深远影响。
Forth 处理器：为 Forth 语言量身定制的硬件实现，栈操作是第一公民。
早期 HP 计算器 CPU：其后续型号迁移至 ARM 架构时，据报道通过软件层模拟原有的栈式执行环境，保持了用户体验的连续性。
Stack-Based VM 对编译器的挑战
Stack-Based VM 看起来是对编译器友好的，但一旦考虑到优化、JIT、跨平台性能，它一点都不简单。
隐式操作数依赖： 栈式虚拟机的指令不显式指定操作数位置，都隐式地从栈顶获取。这使得数据流分析变得困难，编译器很难追踪值的来源和去向，进而影响依赖分析、死代码消除等优化。
局部性差： 频繁的栈操作（push/pop）导致内存访问模式不规则。即使是简单的表达式计算也需要多次内存读写，cache 命中率通常低于寄存器式 VM。
冗余的栈操作： 典型的栈式字节码包含大量冗余操作。例如计算 (a+b)*(c+d) 需要：load a, load b, add, load c, load d, add, multiply，中间结果反复入栈出栈。
难以进行寄存器分配： 传统的寄存器分配算法（如图着色）依赖于明确的变量生命周期分析。栈式架构中变量通过栈槽间接访问，难以应用这些成熟技术。
指令调度受限： 由于严格的栈顺序依赖，指令重排序空间很小。即使两个计算逻辑上独立，也可能因为栈状态而无法并行或乱序执行。
尽管如此，业界也发展出了一些有效的优化手段：栈到寄存器映射，将栈顶几个元素映射到物理寄存器；窥孔优化，识别常见的指令模式并替换为更高效的序列；JIT 编译，运行时将热点代码翻译成寄存器式的机器码；中间表示转换，先转换为 SSA 形式再优化，最后再生成栈式代码。