基于栈与基于寄存器的指令集架构
⽤C的语法来写这么⼀个语句：
C代码
1. a = b + c;
如果把它变成这种形式：
add a, b, c
那看起来就更像机器指令了，对吧？这种就是所谓“三地址指令”（3-address instruction），⼀般形式为：
op dest, src1, src2
许多操作都是⼆元运算+赋值。三地址指令正好可以指定两个源和⼀个⽬标，能⾮常灵活的⽀持⼆元操作与赋值的组合。ARM处理器的主要指令集就是三地址形式的。
C⾥要是这样写的话：
C代码
1. a += b;
变成:
add a, b
这就是所谓“⼆地址指令”，⼀般形式为：
op dest, src
它要⽀持⼆元操作，就只能把其中⼀个源同时也作为⽬标。上⾯的add a, b在执⾏过后，就会破坏a原有的值，⽽b的值保持不变。x86系列的处理器就是⼆地址形式的。
上⾯提到的三地址与⼆地址形式的指令集，⼀般就是通过“基于寄存器的架构”来实现的。例如典型的RISC架构会要求除load和store以外，其它⽤于运算的指令的源与⽬标都要是寄存器。
显然，指令集可以是任意“n地址”的，n属于⾃然数。那么⼀地址形式的指令集是怎样的呢？
想像⼀下这样⼀组指令序列：
add 5
sub 3
这只指定了操作的源，那⽬标是什么？⼀般来说，这种运算的⽬标是被称为“累加器”（accumulator）的专⽤寄存器，所有运算都靠更新累加器的状态来完成。那么上⾯两条指令⽤C来写就类似：
C代码
1. acc += 5;
2. acc -= 3;
只不过acc是“隐藏”的⽬标。基于累加器的架构近来⽐较少见了，在很⽼的机器上繁荣过⼀段时间。
那“n地址”的n如果是0的话呢？
看这样⼀段Java字节码：
Java bytecode代码
1. iconst_1
2. iconst_2
3. iadd
4. istore_0
注意那个iadd（表⽰整型加法）指令并没有任何参数。连源都⽆法指定了，零地址指令有什么⽤？？
零地址意味着源与⽬标都是隐含参数，其实现依赖于⼀种常见的数据结构——没错，就是栈。上⾯的iconst_1、iconst_2两条指令，分别向⼀个叫做“求值栈”（evaluation stack，也叫做operand stack“操作数栈”或者expression stack“表达式栈”）的地⽅压⼊整型常量1、2。iadd指令则从求值栈顶弹出2个值，将值相加，然后把结果压回到栈顶。istore_0指令从求值栈顶弹出⼀个值，并将值保存到局部变量区的第⼀个位置（slot 0）。
零地址形式的指令集⼀般就是通过“基于栈的架构”来实现的。请⼀定要注意，这个栈是指“求值栈”，⽽不是与系统调⽤栈（system call stack，或者就叫system stack）。千万别弄混了。有些虚拟机把求值栈实现在系统调⽤栈上，但两者概念上不是⼀个东西。
由于指令的源与⽬标都是隐含的，零地址指令的“密度”可以⾮常⾼——可以⽤更少空间放下更多条指令。因此在空间紧缺的环境中，零地址指令是种可取的设计。但零地址指令要完成⼀件事情，⼀般会
⽐⼆地址或者三地址指令许多更多条指令。上⾯Java字节码做的加法，如果⽤x86指令两条就能完成了：
X86 asm代码
1. mov  eax, 1
2. add  eax, 2
（好吧我犯规了，istore_0对应的保存我没写。但假如局部变量⽐较少的话也不必把EAX的值保存（“溢出”，register spilling）到调⽤栈上，就这样吧 =_=
其实就算把结果保存到栈上也就是多⼀条指令⽽已……）
⼀些⽐较⽼的解释器，例如 在1.9引⼊ 作为新的VM之前的解释器，还有SquirrleFish之前的⽼JavaScriptCore，它们内部是树遍历式解释器；解释器递归遍历树，树的每个节点的操作依赖于解释其各个⼦节点返回的值。这种解释器⾥没有所谓的求值栈，也没有所谓的虚拟寄存器，所以不适合以“基于栈”或“基于寄存器”去描述。
⽽像V8那样直接编译JavaScript⽣成机器码，⽽不通过中间的字节码的中间表⽰的JavaScript引擎，它
内部有虚拟寄存器的概念，但那只是普通native编译器的正常组成部分。我觉得也不应该⽤“基于栈”或“基于寄存器”去描述它。
V8在内部也⽤了“求值栈”（在V8⾥具体叫“表达式栈”）的概念来简化⽣成代码的过程，使⽤所谓“虚拟栈帧”来记录局部变量与求值栈的状态；但在真正⽣成代码的时候会做窥孔优化，消除冗余的push/pop，将许多对求值栈的操作转变为对寄存器的操作，以此提⾼代码质量。于是最终⽣成出来的代码看起来就不像是基于栈的代码了。
关于JavaScript引擎的实现⽅式，下⽂会再提到。
基于栈与基于寄存器架构的VM，⽤哪个好？
如果是要模拟现有的处理器，那没什么可选的，原本处理器采⽤了什么架构就只能以它为源。但HLL VM的架构通常可以⾃由构造，有很⼤的选择余地。为什么许多主流HLL VM，诸如JVM、CLI、CPython、CRuby 1.9等，都采⽤了基于栈的架构呢？我觉得这有三个主要原因：
·实现简单
由于指令中不必显式指定源与⽬标，VM可以设计得很简单，不必考虑为临时变量分配空间的问题，求值过程中的临时数据存储都让求值栈包办就⾏。
更新：回帖中cscript指出了这句不太准确，应该是针对基于栈架构的指令集⽣成代码的编译器更容易实现，⽽不是VM更容易实现。
·该VM是为某类资源⾮常匮乏的硬件⽽设计的
这类硬件的存储器可能很⼩，每⼀字节的资源都要节省。零地址指令⽐其它形式的指令更紧凑，所以是个⾃然的选择。
·考虑到可移植性
处理器的特性各个不同：典型的CISC处理器的通⽤寄存器数量很少，例如32位的 就只有8个32位通⽤寄存器（如果不算EBP和ESP那就是6个，现在⼀般都算上）；典型的RISC处理器的各种寄存器数量多⼀些，例如 有16个32位通⽤寄存器，Sun的 在⼀个寄存器窗⼝⾥则有24个通⽤寄存器（8 in，8 local，8 out）。
假如⼀个VM采⽤基于寄存器的架构（它接受的指令集⼤概就是⼆地址或者三地址形式的），为了⾼效执⾏，⼀般会希望能把源架构中的寄存器映射到实际机器上寄存器上。但是VM⾥有些很重要的辅助数据会经常被访问，例如⼀些VM会保存源指令序列的程序计数器（program counter，PC），为了效率，这些数据也得放在实际机器的寄存器⾥。如果源架构中寄存器的数量跟实际机器的⼀样，或者前
者⽐后者更多，那源架构的寄存器就没办法都映射到实际机器的寄存器上；这样VM实现起来⽐较⿇烦，与能够全部映射相⽐效率也会⼤打折扣。
如果⼀个VM采⽤基于栈的架构，则⽆论在怎样的实际机器上，都很好实现——它的源架构⾥没有任何通⽤寄存器，所以实现VM时可以⽐
较⾃由的分配实际机器的寄存器。于是这样的VM可移植性就⽐较⾼。作为优化，基于栈的VM可以⽤编译⽅式实现，“求值栈”实际上也可以由编译器映射到寄存器上，减轻数据移动的开销。
回到主题，基于栈与基于寄存器的架构，谁更快？看看现在的实际处理器，⼤多都是基于寄存器的架构，从侧⾯反映出它⽐基于栈的架构更优秀。
⽽对于VM来说，源架构的求值栈或者寄存器都可能是⽤实际机器的内存来模拟的，所以性能特性与实际硬件⼜有点不同。⼀般认为基于寄存器的架构对VM来说也是更快的，原因是：虽然零地址指令更紧凑，但完成操作需要更多的load/store指令，也意味着更多的指令分派（instruction dispatch）次数与内存访问次数；访问内存是执⾏速度的⼀个重要瓶颈，⼆地址或三地址指令虽然每条指令占的空间较多，但总体来说可以⽤更少的指令完成操作，指令分派与内存访问次数都较少。
这⽅⾯有篇被引⽤得很多的论⽂讲得⽐较清楚，，是在VEE 2005发表的。VEE是Virtual Execution En
vironment的缩写，是ACM下SIGPLAN组织的⼀个会议，专门研讨虚拟机的设计与实现的。可以去这个会议往年的论⽂，很多都值得读
基于栈与基于寄存器架构的VM的⼀组图解
要是拿两个分别实现了基于栈与基于寄存器架构、但没有直接联系的VM来对⽐，效果或许不会太好。现在恰巧有两者有紧密联系的例⼦——JVM与Dalvik VM。JVM的字节码主要是零地址形式的，概念上说JVM是基于栈的架构。Google Android平台上的应⽤程序的主要开发语⾔是Java，通过其中的来运⾏Java程序。为了能正确实现语义，Dalvik VM的许多设计都考虑到与JVM的兼容性；但它却采⽤了基于寄存器的架构，其字节码主要是⼆地址/三地址混合形式的，乍⼀看可能让⼈纳闷。考虑到Android有明确的⽬标：⾯向移动设备，特别是最初要对ARM提供良好的⽀持。ARM9有16个32位通⽤寄存器，Dalvik VM的架构也常⽤16个虚拟寄存器（⼀样多……没办法把虚拟寄存器全部直接映射到硬件寄存器上了）；这样Dalvik VM就不⽤太顾虑可移植性的问题，优先考虑在ARM9上以⾼效的⽅式实现，发挥基于寄存器架构的优势。
Dalvik VM的主要设计者在Google I/O 2008上做过⼀个的演讲；同⼀演讲也在Google Developer Day 2008 China和Japan等会议上重复过。这个演讲中Dan特别提到了Dalvik VM与JVM在字节码设计上的区别，指出Dalvik VM的字节码可以⽤更少指令条数、更少内存访问次数来完成操作。（看不到YouTube的请⾃⾏想办法）
x86架构和arm架构区别眼见为实。要⾃⼰动⼿感受⼀下该例⼦，请先确保已经正确安装JDK 6，并从获取Android SDK 1.6R1。连不上官⽹的也请⾃⼰想办法。创建Demo.java⽂件，内容为：
Java代码
1. public class Demo {
2.    public static void foo() {
3.        int a = 1;
4.        int b = 2;
5.        int c = (a + b) * 5;
6.    }
7. }
通过javac编译，得到Demo.class。通过javap可以看到foo()⽅法的字节码是：
接着⽤Android SDK⾥platforms\android-1.6\tools⽬录中的dx⼯具将Demo.class转换为dex格式。转换时可以直接以⽂本形式dump 出dex⽂件的内容。使⽤下⾯的命令：
可以看到foo()⽅法的字节码是：
（原本的输出⾥还有些code-address、local-snapshot等，那些不是字节码的部分，可以忽略。）
让我们看看两个版本在概念上是如何⼯作的。
JVM：
（图中数字均以⼗六进制表⽰。其中字节码的⼀列表⽰的是字节码指令的实际数值，后⾯跟着的助记符则是其对应的⽂字形式。标记为红⾊的值是相对上⼀条指令的执⾏状态有所更新的值。下同）
说明：Java字节码以1字节为单元。上⾯代码中有11条指令，每条都只占1单元，共11单元==11字节。
Java bytecode代码
1. 0:  iconst_1
2. 1:  istore_0
3. 2:  iconst_2
4. 3:  istore_1
5. 4:  iload_0
6. 5:  iload_1
7. 6:  iadd
8. 7:  iconst_5
9. 8:  imul
10. 9:  istore_2
11. 10: return
Command prompt代码
1. dx --dex --verbose --dump-to= --dump-method=Demo.foo --verbose-dump Demo.class
Dalvik bytecode代码
1. 0000: const/4      v0, #int 1 // #1
2. 0001: const/4      v1, #int 2 // #2
3. 0002: add-int/2addr v0, v1
4. 0003: mul-int/lit8  v0, v0, #int 5 // #05
5. 0005: return-void
程序计数器是⽤于记录程序当前执⾏的位置⽤的。对Java程序来说，每个线程都有⾃⼰的PC。PC以字节为单位记录当前运⾏位置⾥⽅法开头的偏移量。
每个线程都有⼀个Java栈，⽤于记录Java⽅法调⽤的“活动记录”（activation record）。Java栈以帧（frame）为单位线程的运⾏状态，每调⽤⼀个⽅法就会分配⼀个新的栈帧压⼊Java栈上，每从⼀个⽅法返回则弹出并撤销相应的栈帧。
每个栈帧包括局部变量区、求值栈（JVM规范中将其称为“操作数栈”）和其它⼀些信息。局部变量区⽤于存储⽅法的参数与局部变量，其中参数按源码中从左到右顺序保存在局部变量区开头的⼏个slot。求值栈⽤于保存求值的中间结果和调⽤别的⽅法的参数等。两者都以字长（32位的字）为单位，每个slot可以保存byte、short、char、int、float、reference和returnAddress等长度⼩于或等于32位的类型的数据；相邻两项可⽤于保存long和double类型的数据。每个⽅法所需要的局部变量区与求值栈⼤⼩都能够在编译时确定，并且记录在.class ⽂件⾥。
在上⾯的例⼦中，Demo.foo()⽅法所需要的局部变量区⼤⼩为3个slot，需要的求值栈⼤⼩为2个slot。Java源码的a、b、c分别被分配到局部变量区的slot 0、slot 1和slot 2。可以观察到Java字节码是如何指⽰JVM将数据压⼊或弹出栈，以及数据是如何在栈与局部变量区之前流动的；可以看到数据移动的
次数特别多。动画⾥可能不太明显，iadd和imul指令都是要从求值栈弹出两个值运算，再把结果压回到栈上的；光这样⼀条指令就有3次概念上的数据移动了。
对了，想提醒⼀下：Java的局部变量区并不需要把某个局部变量固定分配在某个slot⾥；不仅如此，在⼀个⽅法内某个slot甚⾄可能保存不同类型的数据。如何分配slot是编译器的⾃由。从类型安全的⾓度看，只要对某个slot的⼀次load的类型与最近⼀次对它的store的类型匹配，JVM的字节码校验器就不会抱怨。以后再时间写写这⽅⾯。
Dalvik VM：
说明：Dalvik字节码以16位为单元（或许叫“双字节码”更准确 =_=|||）。上⾯代码中有5条指令，其中mul-int/lit8指令占2单元，其余每条都只占1单元，共6单元==12字节。
与JVM相似，在Dalvik VM中每个线程都有⾃⼰的PC和调⽤栈，⽅法调⽤的活动记录以帧为单位保存在调⽤栈上。PC记录的是以16位为单位的偏移量⽽不是以字节为单位的。
与JVM不同的是，Dalvik VM的栈帧中没有局部变量区与求值栈，取⽽代之的是⼀组虚拟寄存器。每个⽅法被调⽤时都会得到⾃⼰的⼀组虚拟寄存器。常⽤v0-v15这16个，也有少数指令可以访问v0-v255范围内的256个虚拟寄存器。与JVM相同的是，每个⽅法所需要的虚拟寄存器个数都能够在编译时确定，并且记录在.dex⽂件⾥；每个寄存器都是字长（32位），相邻的⼀对寄存器可⽤于保存64位数据。⽅法的参数按源码中从左到右的顺序保存在末尾的⼏个虚拟寄存器⾥。
与JVM版相⽐，可以发现Dalvik版程序的指令数明显减少了，数据移动次数也明显减少了，⽤于保存临时结果的存储单元也减少了。
你可能会抱怨：上⾯两个版本的代码明明不对应：JVM版到return前完好持有a、b、c三个变量的值；⽽Dalvik版到return-void前只持有b 与c的值（分别位于v0与v1），a的值被刷掉了。
但注意到a与b的特征：它们都只在声明时接受过⼀次赋值，赋值的源是常量。这样就可以对它们应⽤ ，将
替换为
然后可以再对c的初始化表达式应⽤常量折叠，进⼀步替换为： Java代码
1. int c = (a + b) * 5;
Java代码
1. int c = (1 + 2) * 5;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。