---

一篇阅读笔记
http://km.oa.com/group/2178/articles/show/145691?kmref=search&from_page=1&no=1

早期:遍历语法树

Js引擎最早使用的是遍历语法树方式
（syntax tree walker）

分为两步

• 词法分析
• 语法分析

词法分析

i = a + b * c;
转换
"i", "=", "a", "+", "b", "*", "c";

语法分析

　执行这条语句，就是遍历这颗语法树的过程。遍历语法树的过程在程序设计上一般采用访问者模式（vistor pattern）来实现。要遍历这颗语法树，只要将根节点传给visit函数， 然后这个函数递归调用相应子节点的visit函数，如此反复直到叶子节点。例如，在这个例子中根节点是个赋值语句，他知道应该计算出右边表达式的值，然后赋给左边的地址；而在计算右边表达式的时候，发现是一个加法表达式，于是接着递归计算加法表达式的值，如此递归进行直到这颗树的叶子节点，然后一步步回溯，将值传到到根节点，就完成了一次遍历，也即完成了一次执行。
　　要执行一棵语法树，实际上是一个后序遍历树的过程。以上面这个例子，要计算赋值语句，先计算加法表达式，那就必须先计算乘法表达式，也就是说只有子结点计算好了之后，父节点才能计算，典型的后序遍历。
　　

---

中期：字节码（bytecode）

在引擎的语境下，字节码指的是虚拟机执行的中间指令集。
如：

• Java编译器把Java编译成Java字节码，然后在Java虚拟机中执行
• ActiveScript，转换成字节码，在FLASH虚拟机中执行

分类

• 基于栈stack-based
• 基于寄存器register-based

如果在后序遍历这棵树后，生成对应的后缀记法（逆波兰式）的操作序列，然后在执行时，直接解释执行这后缀记法的操作序列。那么就把这种树状结构，变换成了一种线性结构。这种操作序列就是字节码（bytecode），这种执行方式就是字节码解释方式（bytecode interpreter）。

　
传统的字节码设计大多是基于栈的，这种方式将所有的操作数和中间表示都保存在一个数据栈中。
如语句：c = a + b，转换后的字节码如下：

LOAD a  # 将a推入栈顶
LOAD b  # 将b推入栈顶
ADD     # 从栈顶弹出两个操作数，相加后，将结果推入栈顶
STORE c  #将栈顶数据保存到C中

基于寄存器的字节码通过寄存器（register）保存操作数。这里与汇编代码中的寄存器是两个概念。寄存器可以想象成是一个固定数组。上例转换成基于寄存器的代码如下：

ADD c, a, b   # 两个操作数分别存在a和b中，将结果放在c中。

栈式字节码每条的指令更短(目的地址不用显式表示)，但是总的指令条数更多。
栈式虚拟机实现比寄存器式简单。
Flash Player的ActionScript虚拟机Tamarin、Firefox的JagerMonkey采用的是栈式设计；webkit，carakan采用寄存器方式。
字节码是需要在虚拟机中执行的，而虚拟机的执行过程与CPU过程类似，也是取指，解码，执行的过程。通常情况下，每个操作码对应一段处理函数，然后通过一个无限循环加一个switch的方式进行分派。如:

这里的vpc是一个字节码数组的指针，作用与PC寄存器类似，称作虚拟PC（virtual program counter）。字节码序列直接描述要执行的动作，去除语法信息；执行一条字节码语句，只是一次的内存访问（取指令）加上一次间接跳转（分派处理函数），比访问语法树中节点的开销要小。因此，字节码方式与遍历语法树相比在性能上有很大的提升。虽然从语法树生成字节码需要时间，但是这一段时间可以从直接执行字节码所获得的性能提升上得到补偿。毕竟在实际的代码中，不会所有的代码都只被执行一次。而且生成了字节码之后，就可以对于这种中间代码进行各种优化，比如常量传播，常量折叠，公共子表达式删除等等。当然这些优化都是有针对性和选择性的，毕竟优化的过程也是需要消耗时间的。而这些优化要想直接在语法树上进行几乎是不可能的。

字节码方式相对于遍历语法树已经前进了一大步，但是在分派方式上还可以再改进。Switch Loop分派方式每次处理完一条指令后，都要回到循环的开始，处理下一条，并且每次switch操作，都是一次线性搜索（现代编译器一般都能对switch语句进行优化， 以消除线性搜索开销，但这种优化只限于特定条件，如case的数量和值的跨度范围等），对于一般的函数，只有有限的几个switch case，尚可接受，但是对于虚拟机来说，有上百个switch case并且频繁地执行，执行一条指令就需要一次线性搜索，还是太慢了。如果能用查表的方式直接跳转，就可以省去线性搜索的过程了。于是在字节码的分派方式上，新的改进称作Direct Threading。

Direct
Threading，这里的threading与我们通常理解的线程没有任何关系，可以理解成是针线中的那个“线”。以这种方式执行时，每执行完一条指令后不是回到循环的开始，而是直接跳到下一条要执行的指令地址。这种方式就比原来的Switch
Loop方式有效许多。但是要想有效的实现Direct Threading，需要用到一个gcc的扩展“Labels As
Values”，普通的goto语句的标号是在编译时指定的，但是利用“Labels As
Values”扩展，goto语句的标号是就可以在运行时计算（这种goto语句也叫Computed
Goto），利用这个特性就可以很容易地实现Direct
Threading。（想在windows平台用这个特性，也有几个GCC的windows移植版本，如MinGW, Cygwin等）
右图中的Direct Threading方式已经没有了循环和switch分支，所有的字节码分派就是通过“goto *vpc++”进行的。

在引入即时编译（JIT）之前，Direct Threading方式是字节码解释器最有效和最块的分派方式。对于一般的JavaScript运算，这种方式足够用了。但是解释执行方式肯定比不上直接执行二进制代码。于是接下来即时编译（JIT）技术被引入了JavaScript引擎。

---

现在：即时编译Just-In-Time

字节码指令--->本地机器码

JIT这种技术本身很古老，可以追溯到60年代的LISP语言；现代的大部分运行时环境（runtime environment），如微软的.NET框架和大多数的Java实现都是依赖JIT技术来提高性能。在JavaScript引擎中引入JIT是在2008年开始的。
JIT是一种提高性能的方法。通常一个程序有两种方式执行：静态编译和解释执行。静态编译就是在运行前先将源代码（如c，c++）针对特定平台（如x86,arm，mips）编译成机器代码，在运行时就可以直接在相应的平台上执行；
而解释执行则是每次运行的时候，将每条源代码（如python, javascript）翻译成相应的机器码并立刻执行，并不保存翻译后的机器码，周而复始。可以看到解释执行的运行效率很低，因为每次执行都需要逐句地翻译成机器码然后执行；而静态编译在运行前就编译成相应平台的代码。但是静态编译使得平台移植性很差，也无法实施运行时优化，而且对于动态语言（弱类型语言），变量的类型在运行前未知，很难做到静态编译。JIT编译则是这两种方式的混合，在运行时将源代码翻译成机器码（这一点与解释执行类似），但是会保存已翻译的机器代码，下次执行同一代码段时无需再翻译（这又与静态编译类似）。
在实际的实现中，对于简单的指令，如mov，就直接即时编译，inline到机器码中；对于复杂的指令，如add指令，会对它的常用方式（如操作数是数值或字符串）直接生成对应的机器码，对于add的其他不常用情况（如一个操作数是数值，另一个是字符串）则是生成一条call本地调用。
字节码编译成本地机器码（JIT的过程）需要消耗执行时间，所以不是对所有代码都会生成机器码，而是只对热点（hot spot）片段进行即时编译，同时在运行中会随时跟踪热点的状态，如果热点的程度越高（被执行得越频繁），实施的优化也越激进。

以firefox为例，在开始执行时，将源代码生成字节码，然后解释执行字节码，在执行过程中，如果发现一条路径多次执行（比如一个循环体），那么就标记为“HOT”，同时将这条路径上的代码即时编译成机器码，当下次再运行到这条路径时，就直接运行机器码。
在上图判断热点的虚框中，如果一个路径被执行了超过16次（比如“循环”迭代了超过16次），或一个函数被调用超过16次，那么就进行即时编译；否则解释执行。