?

轉(zhuǎn)載自 ---- 作者：RednaxelaFX -> rednaxelafx.iteye.com

?

1、解析器與解釋器

解析器是parser，而解釋器是interpreter。兩者不是同一樣?xùn)|西，不應(yīng)該混用。

前者是編譯器/解釋器的重要組成部分，也可以用在IDE之類(lèi)的地方；其主要作用是進(jìn)行語(yǔ)法分析，提取出句子的結(jié)構(gòu)。廣義來(lái)說(shuō)輸入一般是程序的源 碼，輸出一般是語(yǔ)法樹(shù)（syntax tree，也叫parse tree等）或抽象語(yǔ)法樹(shù)（abstract syntax tree，AST）。進(jìn)一步剝開(kāi)來(lái)，廣義的解析器里一般會(huì)有掃描器（scanner，也叫tokenizer或者lexical analyzer，詞法分析器），以及狹義的解析器（parser，也叫syntax analyzer，語(yǔ)法分析器）。掃描器的輸入一般是文本，經(jīng)過(guò)詞法分析，輸出是將文本切割為單詞的流。狹義的解析器輸入是單詞的流，經(jīng)過(guò)語(yǔ)法分析，輸出 是語(yǔ)法樹(shù)或者精簡(jiǎn)過(guò)的AST。
（在一些編譯器/解釋器中，解析也可能與后續(xù)的語(yǔ)義分析、代碼生成或解釋執(zhí)行等步驟融合在一起，不一定真的會(huì)構(gòu)造出完整的語(yǔ)法樹(shù)。但概念上說(shuō)解析器就是用來(lái)抽取句子結(jié)構(gòu)用的，而語(yǔ)法樹(shù)就是表示句子結(jié)構(gòu)的方式。關(guān)于邊解析邊解釋執(zhí)行的例子，可以看看 這帖 的計(jì)算器。）
舉例：將i = a + b * c作為源代碼輸入到解析器里，則廣義上的解析器的工作流程如下圖：

其中詞法分析由掃描器完成，語(yǔ)法分析由狹義的解析器完成。
（嗯，說(shuō)來(lái)其實(shí)“解析器”這詞還是按狹義用法比較準(zhǔn)確。把掃描器和解析器合起來(lái)叫解析器總覺(jué)得怪怪的，但不少人這么用，這里就將就下吧 =_=
不過(guò)近來(lái)“ scannerless parsing ”也挺流行的：不區(qū)分詞法分析與語(yǔ)法分析，沒(méi)有單獨(dú)的掃描器，直接用解析器從源碼生成語(yǔ)法樹(shù)。這倒整個(gè)就是解析器了，沒(méi)狹不狹義的問(wèn)題）

后者則是實(shí)現(xiàn)程序執(zhí)行的一種實(shí)現(xiàn)方式，與編譯器相對(duì)。它直接實(shí)現(xiàn)程序源碼的語(yǔ)義，輸入是程序源碼，輸出則是執(zhí)行源碼得到的計(jì)算結(jié)果；編譯器的輸入 與解釋器相同，而輸出是用別的語(yǔ)言實(shí)現(xiàn)了輸入源碼的語(yǔ)義的程序。通常編譯器的輸入語(yǔ)言比輸出語(yǔ)言高級(jí)，但不一定；也有輸入輸出是同種語(yǔ)言的情況，此時(shí)編譯 器很可能主要用于優(yōu)化代碼。
舉例：把同樣的源碼分別輸入到編譯器與解釋器中，得到的輸出不同：

值得留意的是，編譯器生成出來(lái)的代碼執(zhí)行后的結(jié)果應(yīng)該跟解釋器輸出的結(jié)果一樣——它們都應(yīng)該實(shí)現(xiàn)源碼所指定的語(yǔ)義。

在很多地方都看到解析器與解釋器兩個(gè)不同的東西被混為一談，感到十分無(wú)奈。
最近某本引起很多關(guān)注的書(shū)便在開(kāi)篇給讀者們當(dāng)頭一棒，介紹了“ JavaScript解析機(jī)制 ”。“編譯”和“預(yù)處理”也順帶混為一談了，還有“預(yù)編譯” 0_0
我一直以為“預(yù)編譯”應(yīng)該是 ahead-of-time compilation 的翻譯，是與“即時(shí)編譯”（just-in-time compilation，JIT）相對(duì)的概念。另外就是PCH（precompile header）這種用法，把以前的編譯結(jié)果緩存下來(lái)稱(chēng)為“預(yù)編譯”。把AOT、PCH跟“預(yù)處理”（ preprocess ）混為一談?wù)媸窃幃悺Ｋ懔耍疫€是不要淌這渾水的好……打住。


2、“解釋器”到底是什么？“解釋型語(yǔ)言”呢？

很多資料會(huì)說(shuō)，Python、Ruby、JavaScript都是“解釋型語(yǔ)言”，是通過(guò)解釋器來(lái)實(shí)現(xiàn)的。這么說(shuō)其實(shí)很容易引起誤解：語(yǔ)言一般只會(huì)定義其抽象語(yǔ)義，而不會(huì)強(qiáng)制性要求采用某種實(shí)現(xiàn)方式。
例如說(shuō)C一般被認(rèn)為是“編譯型語(yǔ)言”，但C的解釋器也是存在的，例如 Ch 。同樣，C++也有解釋器版本的實(shí)現(xiàn)，例如 Cint 。
一般被稱(chēng)為“解釋型語(yǔ)言”的是主流實(shí)現(xiàn)為解釋器的語(yǔ)言，但并不是說(shuō)它就無(wú)法編譯。例如說(shuō)經(jīng)常被認(rèn)為是“解釋型語(yǔ)言”的 Scheme 就有好幾種編譯器實(shí)現(xiàn)，其中率先支持 R6RS 規(guī)范的大部分內(nèi)容的是 Ikarus ，支持在x86上編譯Scheme；它最終不是生成某種虛擬機(jī)的字節(jié)碼，而是直接生成x86機(jī)器碼。

解釋器就是個(gè)黑箱，輸入是源碼，輸出就是輸入程序的執(zhí)行結(jié)果，對(duì)用戶(hù)來(lái)說(shuō)中間沒(méi)有獨(dú)立的“編譯”步驟。這非常抽象，內(nèi)部是怎么實(shí)現(xiàn)的都沒(méi)關(guān)系，只 要能實(shí)現(xiàn)語(yǔ)義就行。你可以寫(xiě)一個(gè)C語(yǔ)言的解釋器，里面只是先用普通的C編譯器把源碼編譯為in-memory image，然后直接調(diào)用那個(gè)image去得到運(yùn)行結(jié)果；用戶(hù)拿過(guò)去，發(fā)現(xiàn)直接輸入源碼可以得到源程序?qū)?yīng)的運(yùn)行結(jié)果就滿(mǎn)足需求了，無(wú)需在意解釋器這個(gè) “黑箱子”里到底是什么。
實(shí)際上很多解釋器內(nèi)部是以“編譯器+虛擬機(jī)”的方式來(lái)實(shí)現(xiàn)的，先通過(guò)編譯器將源碼轉(zhuǎn)換為AST或者字節(jié)碼，然后由虛擬機(jī)去完成實(shí)際的執(zhí)行。所謂“解釋型語(yǔ)言”并不是不用編譯，而只是不需要用戶(hù)顯式去使用編譯器得到可執(zhí)行代碼而已。

那么虛擬機(jī)（ virtual machine ，VM） 又是什么？在許多不同的場(chǎng)合，VM有著不同的意義。如果上下文是Java、Python這類(lèi)語(yǔ)言，那么一般指的是高級(jí)語(yǔ)言虛擬機(jī)（high-level language virtual machine，HLL VM），其意義是實(shí)現(xiàn)高級(jí)語(yǔ)言的語(yǔ)義。VM既然被稱(chēng)為“機(jī)器”，一般認(rèn)為輸入是滿(mǎn)足某種指令集架構(gòu)（ instruction set architecture ，ISA）的指令序列，中間轉(zhuǎn)換為目標(biāo)ISA的指令序列并加以執(zhí)行，輸出為程序的執(zhí)行結(jié)果的，就是VM。源與目標(biāo)ISA可以是同一種，這是所謂same-ISA VM。
前面提到解釋器中的編譯器的輸出可能是AST，也可能是字節(jié)碼之類(lèi)的指令序列；一般會(huì)把執(zhí)行后者的程序稱(chēng)為VM，而執(zhí)行前者的還是籠統(tǒng)稱(chēng)為解釋器 或者樹(shù)遍歷式解釋器（tree-walking interpreter）。這只是種習(xí)慣而已，并沒(méi)有多少確鑿的依據(jù)。只不過(guò)線(xiàn)性（相對(duì)于樹(shù)形）的指令序列看起來(lái)更像一般真正機(jī)器會(huì)執(zhí)行的指令序列而已。
其實(shí)我覺(jué)得把執(zhí)行AST的也叫VM也沒(méi)啥大問(wèn)題。如果認(rèn)同這個(gè)觀點(diǎn)，那么把 DLR 看作一種VM也就可以接受了——它的“指令集”就是樹(shù)形的Expression Tree。

VM并不是神奇的就能執(zhí)行代碼了，它也得采用某種方式去實(shí)現(xiàn)輸入程序的語(yǔ)義，并且同樣有幾種選擇：“編譯”，例如微軟的.NET中的CLR；“解 釋”，例如CPython、CRuby 1.9，許多老的JavaScript引擎等；也有介于兩者之間的混合式，例如Sun的JVM， HotSpot 。如果采用編譯方式，VM會(huì)把輸入的指令先轉(zhuǎn)換為某種能被底下的系統(tǒng)直接執(zhí)行的形式（一般就是native code），然后再執(zhí)行之；如果采用解釋方式，則VM會(huì)把輸入的指令逐條直接執(zhí)行。
換個(gè)角度說(shuō)，我覺(jué)得采用編譯和解釋方式實(shí)現(xiàn)虛擬機(jī)最大的區(qū)別就在于是否存下目標(biāo)代碼：編譯的話(huà)會(huì)把輸入的源程序以某種單位（例如 基本塊 / 函數(shù)/方法/trace等）翻譯生成為目標(biāo)代碼，并存下來(lái)（無(wú)論是存在內(nèi)存中還是磁盤(pán)上，無(wú)所謂），后續(xù)執(zhí)行可以復(fù)用之；解釋的話(huà)則把源程序中的指令是逐 條解釋?zhuān)簧梢膊淮嫦履繕?biāo)代碼，后續(xù)執(zhí)行沒(méi)有多少可復(fù)用的信息。有些稍微先進(jìn)一點(diǎn)的解釋器可能會(huì)優(yōu)化輸入的源程序，把滿(mǎn)足某些模式的指令序列合并為“超 級(jí)指令”；這么做就是朝著編譯的方向推進(jìn)。后面講到解釋器的演化時(shí)再討論超級(jí)指令吧。

如果一種語(yǔ)言的主流實(shí)現(xiàn)是解釋器，其內(nèi)部是編譯器+虛擬機(jī)，而虛擬機(jī)又是采用解釋方式實(shí)現(xiàn)的，或者內(nèi)部實(shí)現(xiàn)是編譯器+樹(shù)遍歷解釋器，那它就是名副其實(shí)的“解釋型語(yǔ)言”。如果內(nèi)部用的虛擬機(jī)是用編譯方式實(shí)現(xiàn)的，其實(shí)跟普遍印象中的“解釋器”還是挺不同的……

可以舉這樣一個(gè)例子：ActionScript 3，一般都被認(rèn)為是“解釋型語(yǔ)言”對(duì)吧？但這種觀點(diǎn)到底是把FlashPlayer整體看成一個(gè)解釋器，因而AS3是“解釋型語(yǔ)言”呢？還是認(rèn)為 FlashPlayer中的虛擬機(jī)采用解釋執(zhí)行方案，因而AS3是“解釋型語(yǔ)言”呢？
其實(shí)Flash或Flex等從AS3生成出來(lái)的SWF文件里就包含有AS字節(jié)碼（ActionScript Byte Code，ABC）。等到FlashPlayer去執(zhí)行SWF文件，或者說(shuō)等到AVM2（ActionScript Virtual Machine 2）去執(zhí)行ABC時(shí)，又有解釋器和JIT編譯器兩種實(shí)現(xiàn)。這種需要讓用戶(hù)顯式進(jìn)行編譯步驟的語(yǔ)言，到底是不是“解釋型語(yǔ)言”呢？呵呵。所以我一直覺(jué)得“編 譯型語(yǔ)言”跟“解釋型語(yǔ)言”的說(shuō)法太模糊，不太好。
有興趣想體驗(yàn)一下從命令行編譯“裸”的AS3文件得到ABC文件，再?gòu)拿钚姓{(diào)用AVM2去執(zhí)行ABC文件的同學(xué)，可以從 這帖 下載我之前從源碼編譯出來(lái)的AVM2，自己玩玩看。例如說(shuō)要編譯一個(gè)名為test.as的文件，用下列命令：

Command prompt代碼 ?

1. java?-jar?asc.jar?-import?builtin.abc?-import?toplevel.abc?test.as??

就是用ASC將test.as編譯，得到test.abc。接著用：

Command prompt代碼 ?

1. avmplus?test.abc??

就是用AVM2去執(zhí)行程序了。很生動(dòng)的體現(xiàn)出“編譯器+虛擬機(jī)”的實(shí)現(xiàn)方式。
這個(gè)“裸”的AVM2沒(méi)有帶Flash或Flex的類(lèi)庫(kù)，能用的函數(shù)和類(lèi)都有限。不過(guò)AS3語(yǔ)言實(shí)現(xiàn)是完整的。可以用print()函數(shù)來(lái)向標(biāo)準(zhǔn)輸出流寫(xiě)東西。
Well……其實(shí)寫(xiě)Java程序不也是這樣么？現(xiàn)在也確實(shí)還有很多人把Java稱(chēng)為“解釋型語(yǔ)言”，完全無(wú)視Java代碼通常是經(jīng)過(guò)顯式編譯步驟才得到.class文件，而有些JVM是采用純JIT編譯方式實(shí)現(xiàn)的，內(nèi)部沒(méi)解釋器，例如 Jikes RVM 。我愈發(fā)感到“解釋型語(yǔ)言”是個(gè)應(yīng)該避開(kāi)的用語(yǔ) =_=

關(guān)于虛擬機(jī)，有本很好的書(shū)絕對(duì)值得一讀，《虛擬機(jī)——系統(tǒng)與進(jìn)程的通用平臺(tái)》（Virtual Machines: Versatile Platforms for Systems and Processes）。國(guó)內(nèi)有影印版也有中文版，我是讀了影印版，不太清楚中文版的翻譯質(zhì)量如何。據(jù)說(shuō)翻譯得還行，我無(wú)法印證。


3、基于棧與基于寄存器的指令集架構(gòu)

用C的語(yǔ)法來(lái)寫(xiě)這么一個(gè)語(yǔ)句：

C代碼 ?

1. a?=?b?+?c;??

如果把它變成這種形式：
add a, b, c
那看起來(lái)就更像機(jī)器指令了，對(duì)吧？這種就是所謂“三地址指令”（3-address instruction），一般形式為：
op dest, src1, src2
許多操作都是二元運(yùn)算+賦值。三地址指令正好可以指定兩個(gè)源和一個(gè)目標(biāo)，能非常靈活的支持二元操作與賦值的組合。ARM處理器的主要指令集就是三地址形式的。

C里要是這樣寫(xiě)的話(huà)：

C代碼 ?

1. a?+=?b;??

變成:
add a, b
這就是所謂“二地址指令”，一般形式為：
op dest, src
它要支持二元操作，就只能把其中一個(gè)源同時(shí)也作為目標(biāo)。上面的add a, b在執(zhí)行過(guò)后，就會(huì)破壞a原有的值，而b的值保持不變。x86系列的處理器就是二地址形式的。

上面提到的三地址與二地址形式的指令集，一般就是通過(guò)“基于寄存器的架構(gòu)”來(lái)實(shí)現(xiàn)的。例如典型的RISC架構(gòu)會(huì)要求除load和store以外，其它用于運(yùn)算的指令的源與目標(biāo)都要是寄存器。

顯然，指令集可以是任意“n地址”的，n屬于自然數(shù)。那么一地址形式的指令集是怎樣的呢？
想像一下這樣一組指令序列：
add 5
sub 3
這只指定了操作的源，那目標(biāo)是什么？一般來(lái)說(shuō)，這種運(yùn)算的目標(biāo)是被稱(chēng)為“累加器”（accumulator）的專(zhuān)用寄存器，所有運(yùn)算都靠更新累加器的狀態(tài)來(lái)完成。那么上面兩條指令用C來(lái)寫(xiě)就類(lèi)似：

C代碼 ?

1. acc?+=?5;??
2. acc?-=?3;??

只不過(guò)acc是“隱藏”的目標(biāo)。基于累加器的架構(gòu)近來(lái)比較少見(jiàn)了，在很老的機(jī)器上繁榮過(guò)一段時(shí)間。

那“n地址”的n如果是0的話(huà)呢？
看這樣一段Java字節(jié)碼：

Java bytecode代碼 ?

1. iconst_1??
2. iconst_2??
3. iadd??
4. istore_0??

注意那個(gè)iadd（表示整型加法）指令并沒(méi)有任何參數(shù)。連源都無(wú)法指定了，零地址指令有什么用？？
零地址意味著源與目標(biāo)都是隱含參數(shù)，其實(shí)現(xiàn)依賴(lài)于一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)——沒(méi)錯(cuò)，就是棧。上面的iconst_1、iconst_2兩條指令，分別 向一個(gè)叫做“求值棧”（evaluation stack，也叫做operand stack“操作數(shù)棧”或者expression stack“表達(dá)式棧”）的地方壓入整型常量1、2。iadd指令則從求值棧頂彈出2個(gè)值，將值相加，然后把結(jié)果壓回到棧頂。istore_0指令從求值 棧頂彈出一個(gè)值，并將值保存到局部變量區(qū)的第一個(gè)位置（slot 0）。
零地址形式的指令集一般就是通過(guò)“基于棧的架構(gòu)”來(lái)實(shí)現(xiàn)的。請(qǐng)一定要注意，這個(gè)棧是指“求值棧”，而不是與系統(tǒng)調(diào)用棧（system call stack，或者就叫system stack）。千萬(wàn)別弄混了。有些虛擬機(jī)把求值棧實(shí)現(xiàn)在系統(tǒng)調(diào)用棧上，但兩者概念上不是一個(gè)東西。

由于指令的源與目標(biāo)都是隱含的，零地址指令的“密度”可以非常高——可以用更少空間放下更多條指令。因此在空間緊缺的環(huán)境中，零地址指令是種可取 的設(shè)計(jì)。但零地址指令要完成一件事情，一般會(huì)比二地址或者三地址指令許多更多條指令。上面Java字節(jié)碼做的加法，如果用x86指令兩條就能完成了：

X86 asm代碼 ?

1. mov??eax,? 1 ??
2. add??eax,? 2 ??

（好吧我犯規(guī)了，istore_0對(duì)應(yīng)的保存我沒(méi)寫(xiě)。但假如局部變量比較少的話(huà)也不必把EAX的值保存（“溢出”，register spilling）到調(diào)用棧上，就這樣吧 =_=
其實(shí)就算把結(jié)果保存到棧上也就是多一條指令而已……）

一些比較老的解釋器，例如 CRuby 在1.9引入 YARV 作 為新的VM之前的解釋器，還有SquirrleFish之前的老JavaScriptCore，它們內(nèi)部是樹(shù)遍歷式解釋器；解釋器遞歸遍歷樹(shù)，樹(shù)的每個(gè)節(jié) 點(diǎn)的操作依賴(lài)于解釋其各個(gè)子節(jié)點(diǎn)返回的值。這種解釋器里沒(méi)有所謂的求值棧，也沒(méi)有所謂的虛擬寄存器，所以不適合以“基于棧”或“基于寄存器”去描述。

而像V8那樣直接編譯JavaScript生成機(jī)器碼，而不通過(guò)中間的字節(jié)碼的中間表示的JavaScript引擎，它內(nèi)部有虛擬寄存器的概念，但那只是普通native編譯器的正常組成部分。我覺(jué)得也不應(yīng)該用“基于棧”或“基于寄存器”去描述它。
V8在內(nèi)部也用了“求值棧”（在V8里具體叫“表達(dá)式棧”）的概念來(lái)簡(jiǎn)化生成代碼的過(guò)程，使用所謂“虛擬棧幀”來(lái)記錄局部變量與求值棧的狀態(tài)；但 在真正生成代碼的時(shí)候會(huì)做窺孔優(yōu)化，消除冗余的push/pop，將許多對(duì)求值棧的操作轉(zhuǎn)變?yōu)閷?duì)寄存器的操作，以此提高代碼質(zhì)量。于是最終生成出來(lái)的代碼 看起來(lái)就不像是基于棧的代碼了。

關(guān)于JavaScript引擎的實(shí)現(xiàn)方式，下文會(huì)再提到。


4、基于棧與基于寄存器架構(gòu)的VM，用哪個(gè)好？

如果是要模擬現(xiàn)有的處理器，那沒(méi)什么可選的，原本處理器采用了什么架構(gòu)就只能以它為源。但HLL VM的架構(gòu)通常可以自由構(gòu)造，有很大的選擇余地。為什么許多主流HLL VM，諸如JVM、CLI、CPython、CRuby 1.9等，都采用了基于棧的架構(gòu)呢？我覺(jué)得這有三個(gè)主要原因：

·實(shí)現(xiàn)簡(jiǎn)單
由于指令中不必顯式指定源與目標(biāo)，VM可以設(shè)計(jì)得很簡(jiǎn)單，不必考慮為臨時(shí)變量分配空間的問(wèn)題，求值過(guò)程中的臨時(shí)數(shù)據(jù)存儲(chǔ)都讓求值棧包辦就行。
更新：回帖中cscript指出了這句不太準(zhǔn)確，應(yīng)該是針對(duì)基于棧架構(gòu)的指令集生成代碼的編譯器更容易實(shí)現(xiàn)，而不是VM更容易實(shí)現(xiàn)。

·該VM是為某類(lèi)資源非常匱乏的硬件而設(shè)計(jì)的
這類(lèi)硬件的存儲(chǔ)器可能很小，每一字節(jié)的資源都要節(jié)省。零地址指令比其它形式的指令更緊湊，所以是個(gè)自然的選擇。

·考慮到可移植性
處理器的特性各個(gè)不同：典型的CISC處理器的通用寄存器數(shù)量很少，例如32位的 x86 就只有8個(gè)32位通用寄存器（如果不算EBP和ESP那就是6個(gè)，現(xiàn)在一般都算上）；典型的RISC處理器的各種寄存器數(shù)量多一些，例如 ARM 有16個(gè)32位通用寄存器，Sun的 SPARC 在一個(gè)寄存器窗口里則有24個(gè)通用寄存器（8 in，8 local，8 out）。
假如一個(gè)VM采用基于寄存器的架構(gòu)（它接受的指令集大概就是二地址或者三地址形式的），為了高效執(zhí)行，一般會(huì)希望能把源架構(gòu)中的寄存器映射到實(shí)際 機(jī)器上寄存器上。但是VM里有些很重要的輔助數(shù)據(jù)會(huì)經(jīng)常被訪(fǎng)問(wèn)，例如一些VM會(huì)保存源指令序列的程序計(jì)數(shù)器（program counter，PC），為了效率，這些數(shù)據(jù)也得放在實(shí)際機(jī)器的寄存器里。如果源架構(gòu)中寄存器的數(shù)量跟實(shí)際機(jī)器的一樣，或者前者比后者更多，那源架構(gòu)的寄 存器就沒(méi)辦法都映射到實(shí)際機(jī)器的寄存器上；這樣VM實(shí)現(xiàn)起來(lái)比較麻煩，與能夠全部映射相比效率也會(huì)大打折扣。
如果一個(gè)VM采用基于棧的架構(gòu)，則無(wú)論在怎樣的實(shí)際機(jī)器上，都很好實(shí)現(xiàn)——它的源架構(gòu)里沒(méi)有任何通用寄存器，所以實(shí)現(xiàn)VM時(shí)可以比較自由的分配實(shí) 際機(jī)器的寄存器。于是這樣的VM可移植性就比較高。作為優(yōu)化，基于棧的VM可以用編譯方式實(shí)現(xiàn)，“求值棧”實(shí)際上也可以由編譯器映射到寄存器上，減輕數(shù)據(jù) 移動(dòng)的開(kāi)銷(xiāo)。

回到主題，基于棧與基于寄存器的架構(gòu)，誰(shuí)更快？看看現(xiàn)在的實(shí)際處理器，大多都是基于寄存器的架構(gòu)，從側(cè)面反映出它比基于棧的架構(gòu)更優(yōu)秀。
而對(duì)于VM來(lái)說(shuō)，源架構(gòu)的求值棧或者寄存器都可能是用實(shí)際機(jī)器的內(nèi)存來(lái)模擬的，所以性能特性與實(shí)際硬件又有點(diǎn)不同。一般認(rèn)為基于寄存器的架構(gòu)對(duì) VM來(lái)說(shuō)也是更快的，原因是：雖然零地址指令更緊湊，但完成操作需要更多的load/store指令，也意味著更多的指令分派（instruction dispatch）次數(shù)與內(nèi)存訪(fǎng)問(wèn)次數(shù)；訪(fǎng)問(wèn)內(nèi)存是執(zhí)行速度的一個(gè)重要瓶頸，二地址或三地址指令雖然每條指令占的空間較多，但總體來(lái)說(shuō)可以用更少的指令完 成操作，指令分派與內(nèi)存訪(fǎng)問(wèn)次數(shù)都較少。
這方面有篇被引用得很多的論文講得比較清楚， Virtual Machine Showdown: Stack Versus Registers ，是在VEE 2005發(fā)表的。VEE是Virtual Execution Environment的縮寫(xiě)，是ACM下SIGPLAN組織的一個(gè)會(huì)議，專(zhuān)門(mén)研討虛擬機(jī)的設(shè)計(jì)與實(shí)現(xiàn)的。可以去找找這個(gè)會(huì)議往年的論文，很多都值得讀。


5、樹(shù)遍歷解釋器圖解

在演示基于棧與基于寄存器的VM的例子前，先回頭看看更原始的解釋器形式。
前面提到解析器的時(shí)候用了i = a + b * c的例子，現(xiàn)在讓我們來(lái)看看由解析器生成的AST要是交給一個(gè)樹(shù)遍歷解釋器，會(huì)如何被解釋執(zhí)行呢？

用文字說(shuō)不夠形象，還是看圖吧：

這是對(duì)AST的后序遍歷：假設(shè)有一個(gè)eval(Node n)函數(shù)，用于解釋AST上的每個(gè)節(jié)點(diǎn)；在解釋一個(gè)節(jié)點(diǎn)時(shí)如果依賴(lài)于子樹(shù)的操作，則對(duì)子節(jié)點(diǎn)遞歸調(diào)用eval(Node n)，從這些遞歸調(diào)用的返回值獲取需要的值（或副作用）——也就是說(shuō)子節(jié)點(diǎn)都eval好了之后，父節(jié)點(diǎn)才能進(jìn)行自己的eval——典型的后序遍歷。
（話(huà)說(shuō)，上圖中節(jié)點(diǎn)左下角有藍(lán)色標(biāo)記的說(shuō)明那是節(jié)點(diǎn)的“內(nèi)在屬性”。從 屬性語(yǔ)法 的 角度看，如果一個(gè)節(jié)點(diǎn)的某個(gè)屬性的值只依賴(lài)于自身或子節(jié)點(diǎn)，則該屬性被稱(chēng)為“綜合屬性”（synthesized attribute）；如果一個(gè)節(jié)點(diǎn)的某個(gè)屬性只依賴(lài)于自身、父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)，則該屬性被稱(chēng)為“繼承屬性”（inherited attribute）。上圖中節(jié)點(diǎn)右下角的紅色標(biāo)記都只依賴(lài)子節(jié)點(diǎn)來(lái)計(jì)算，顯然是綜合屬性。）

SquirrelFish之前的JavaScriptCore、CRuby 1.9之前的CRuby就都是采用這種方式來(lái)解釋執(zhí)行的。

可能需要說(shuō)明的：
·左值與右值
在源代碼i = a + b * c中，賦值符號(hào)左側(cè)的i是一個(gè)標(biāo)識(shí)符，表示一個(gè)變量，取的是變量的“左值”（也就是與變量i綁定的存儲(chǔ)單元）；右側(cè)的a、b、c雖然也是變量，但取的是它 們的右值（也就是與變量綁定的存儲(chǔ)單元內(nèi)的值）。在許多編程語(yǔ)言中，左值與右值在語(yǔ)法上沒(méi)有區(qū)別，它們實(shí)質(zhì)的差異容易被忽視。一般來(lái)說(shuō)左值可以作為右值使 用，反之則不一定。例如數(shù)字1，它自身有值就是1，可以作為右值使用；但它沒(méi)有與可賦值的存儲(chǔ)單元相綁定，所以無(wú)法作為左值使用。
左值不一定只是簡(jiǎn)單的變量，還可以是數(shù)組元素或者結(jié)構(gòu)體的域之類(lèi)，可能由復(fù)雜的表達(dá)式所描述。因此左值也是需要計(jì)算的。

·優(yōu)先級(jí)、結(jié)合性與求值順序
這三個(gè)是不同的概念，卻經(jīng)常被混淆。通過(guò)AST來(lái)看就很容易理解：（假設(shè)源碼是從左到右輸入的）
所謂 優(yōu)先級(jí) ，就是不同操作相鄰出現(xiàn)時(shí)，AST節(jié)點(diǎn)與根的距離的關(guān)系。優(yōu)先級(jí)高的操作會(huì)更遠(yuǎn)離根，優(yōu)先級(jí)低的操作會(huì)更接近根。為什么？因?yàn)檎肁ST是以后序遍歷求值的，顯然節(jié)點(diǎn)離根越遠(yuǎn)就越早被求值。
所謂 結(jié)合性 ，就是當(dāng)同類(lèi)操作相鄰出現(xiàn)時(shí)，操作的先后順序同AST節(jié)點(diǎn)與根的距離的關(guān)系。如果是左結(jié)合，則先出現(xiàn)的操作對(duì)應(yīng)的AST節(jié)點(diǎn)比后出現(xiàn)的操作的節(jié)點(diǎn)離根更遠(yuǎn)；換句話(huà)說(shuō)，先出現(xiàn)的節(jié)點(diǎn)會(huì)是后出現(xiàn)節(jié)點(diǎn)的子節(jié)點(diǎn)。
所謂 求值順序 ，就是在遍歷子節(jié)點(diǎn)時(shí)的順序。對(duì)二元運(yùn)算對(duì)應(yīng)的節(jié)點(diǎn)來(lái)說(shuō)，先遍歷左子節(jié)點(diǎn)再遍歷右子節(jié)點(diǎn)就是左結(jié)合，反之則是右結(jié)合。
這三個(gè)概念與運(yùn)算的聯(lián)系都很緊密，但實(shí)際描述的是不同的關(guān)系。前兩者是解析器根據(jù)語(yǔ)法生成AST時(shí)就已經(jīng)決定好的，后者則是解釋執(zhí)行或者生成代碼而去遍歷AST時(shí)決定的。
在沒(méi)有副作用的環(huán)境中，給定優(yōu)先級(jí)與結(jié)合性，則無(wú)論求值順序是怎樣的都能得到同樣的結(jié)果；而在有副作用的環(huán)境中，求值順序會(huì)影響結(jié)果。

賦值運(yùn)算雖然是右結(jié)合的，但仍然可以用從左到右的求值順序；事實(shí)上Java、C#等許多語(yǔ)言都在規(guī)范里寫(xiě)明表達(dá)式的求值順序是從左到右的。上面的例子中就先遍歷的=的左側(cè)，求得i的左值；再遍歷=的右側(cè)，得到表達(dá)式的值23；最后執(zhí)行=自身，完成對(duì)i的賦值。
所以如果你要問(wèn)：賦值在類(lèi)似C的語(yǔ)言里明明是右結(jié)合的運(yùn)算，為什么你先遍歷左子樹(shù)再遍歷右子樹(shù)？上面的說(shuō)明應(yīng)該能讓你發(fā)現(xiàn)你把結(jié)合性與求值順序混為一談了。

看看Java從左到右求值順序的例子：

Java代碼 ?

1. public ? class ?EvalOrderDemo?{??
2. ???? public ? static ? void ?main(String[]?args)?{??
3. ???????? int []?arr?=? new ? int [ 1 ];??
4. ???????? int ?a?=? 1 ;??
5. ???????? int ?b?=? 2 ;??
6. ????????arr[ 0 ]?=?a?+?b;??
7. ????}??
8. }??

由javac編譯，得到arr[0] = a + b對(duì)應(yīng)的字節(jié)碼是：

Java bytecode代碼 ?

1. //?左子樹(shù)：數(shù)組下標(biāo)??
2. //?a[ 0 ]??
3. aload_1??
4. iconst_0??
5. ??
6. //?右子樹(shù)：加法??
7. //?a??
8. iload_2??
9. //?b??
10. iload_3??
11. //?+??
12. iadd??
13. ??
14. //?根節(jié)點(diǎn)：賦值??
15. iastore??

6、從樹(shù)遍歷解釋器進(jìn)化為基于棧的字節(jié)碼解釋器的前端

如果你看到樹(shù)形結(jié)構(gòu)與后序遍歷，并且知道后綴記法（或者逆波蘭記法， reverse Polish notation ）的話(huà)，那敏銳的你或許已經(jīng)察覺(jué)了：要解釋執(zhí)行AST，可以先通過(guò)后序遍歷AST生成對(duì)應(yīng)的后綴記法的操作序列，然后再解釋執(zhí)行該操作序列。這樣就把樹(shù)形結(jié)構(gòu)壓扁，成為了線(xiàn)性結(jié)構(gòu)。
樹(shù)遍歷解釋器對(duì)AST的求值其實(shí)隱式依賴(lài)于調(diào)用棧：eval(Node n)的遞歸調(diào)用關(guān)系是靠調(diào)用棧來(lái)維護(hù)的。后綴表達(dá)式的求值則通常顯式依賴(lài)于一個(gè)棧，在遇到操作數(shù)時(shí)將其壓入棧中，遇到運(yùn)算時(shí)將合適數(shù)量的值從棧頂彈出進(jìn)行 運(yùn)算，再將結(jié)果壓回到棧上。這種描述看起來(lái)眼熟么？沒(méi)錯(cuò)，后綴記法的求值中的核心數(shù)據(jù)結(jié)構(gòu)就是前文提到過(guò)的“求值棧”（或者叫操作數(shù)棧，現(xiàn)在應(yīng)該更好理解 了）。后綴記法也就與基于棧的架構(gòu)聯(lián)系了起來(lái)：后者可以很方便的執(zhí)行前者。同理，零地址指令也與樹(shù)形結(jié)構(gòu)聯(lián)系了起來(lái)：可以通過(guò)一個(gè)棧方便的把零地址指令序 列再轉(zhuǎn)換回到樹(shù)的形式。

Java字節(jié)碼與Java源碼聯(lián)系緊密，前者可以看成后者的后綴記法。如果想在JVM上開(kāi)發(fā)一種語(yǔ)義能直接映射到Java上的語(yǔ)言，那么編譯器很好寫(xiě)：秘訣就是后序遍歷AST。
那么讓我們?cè)賮?lái)看看，同樣是i = a + b * c這段源碼對(duì)應(yīng)的AST，生成Java字節(jié)碼的例子：

（假設(shè)a、b、c、i分別被分配到局部變量區(qū)的slot 0到slot 3）
能看出Java字節(jié)碼與源碼間的對(duì)應(yīng)關(guān)系了么？
一個(gè)Java編譯器的輸入是Java源代碼，輸出是含有Java字節(jié)碼的.class文件。它里面主要包含掃描器與解析器，語(yǔ)義分析器（包括類(lèi)型 檢查器/類(lèi)型推導(dǎo)器等），代碼生成器等幾大部分。上圖所展示的就是代碼生成器的工作。對(duì)Java編譯器來(lái)說(shuō)，代碼生成就到字節(jié)碼的層次就結(jié)束了；而對(duì) native編譯器來(lái)說(shuō)，這里剛到生成中間表示的部分，接下去是優(yōu)化與最終的代碼生成。

如果你對(duì) Python 、 CRuby 1.9 之類(lèi)有所了解，會(huì)發(fā)現(xiàn)它們的字節(jié)碼跟Java字節(jié)碼在“基于棧”的這一特征上非常相似。其實(shí)它們都是由“編譯器+VM”構(gòu)成的，概念上就像是Java編譯器與JVM融為一體一般。
從這點(diǎn)看，Java與Python和Ruby可以說(shuō)是一條船上的。雖說(shuō)內(nèi)部具體實(shí)現(xiàn)的顯著差異使得先進(jìn)的JVM比簡(jiǎn)單的JVM快很多，而JVM又普遍比Python和Ruby快很多。

當(dāng)解釋器中用于解釋執(zhí)行的中間代碼是樹(shù)形時(shí)，其中能被稱(chēng)為“編譯器”的部分基本上就是解析器；中間代碼是線(xiàn)性形式（如字節(jié)碼）時(shí)，其中能被稱(chēng)為編 譯器的部分就包括上述的代碼生成器部分，更接近于所謂“完整的編譯器”；如果虛擬機(jī)是基于寄存器架構(gòu)的，那么編譯器里至少還得有虛擬寄存器分配器，又更接 近“完整的編譯器”了。


7、基于棧與基于寄存器架構(gòu)的VM的一組圖解

要是拿兩個(gè)分別實(shí)現(xiàn)了基于棧與基于寄存器架構(gòu)、但沒(méi)有直接聯(lián)系的VM來(lái)對(duì)比，效果或許不會(huì)太好。現(xiàn)在恰巧有兩者有緊密聯(lián)系的例子——JVM與 Dalvik VM。JVM的字節(jié)碼主要是零地址形式的，概念上說(shuō)JVM是基于棧的架構(gòu)。Google Android平臺(tái)上的應(yīng)用程序的主要開(kāi)發(fā)語(yǔ)言是Java，通過(guò)其中的 Dalvik VM 來(lái) 運(yùn)行Java程序。為了能正確實(shí)現(xiàn)語(yǔ)義，Dalvik VM的許多設(shè)計(jì)都考慮到與JVM的兼容性；但它卻采用了基于寄存器的架構(gòu)，其字節(jié)碼主要是二地址/三地址混合形式的，乍一看可能讓人納悶。考慮到 Android有明確的目標(biāo)：面向移動(dòng)設(shè)備，特別是最初要對(duì)ARM提供良好的支持。ARM9有16個(gè)32位通用寄存器，Dalvik VM的架構(gòu)也常用16個(gè)虛擬寄存器（一樣多……沒(méi)辦法把虛擬寄存器全部直接映射到硬件寄存器上了）；這樣Dalvik VM就不用太顧慮可移植性的問(wèn)題，優(yōu)先考慮在ARM9上以高效的方式實(shí)現(xiàn)，發(fā)揮基于寄存器架構(gòu)的優(yōu)勢(shì)。
Dalvik VM的主要設(shè)計(jì)者 Dan Bornstein 在Google I/O 2008上做過(guò)一個(gè) 關(guān)于Dalvik內(nèi)部實(shí)現(xiàn) 的 演講；同一演講也在Google Developer Day 2008 China和Japan等會(huì)議上重復(fù)過(guò)。這個(gè)演講中Dan特別提到了Dalvik VM與JVM在字節(jié)碼設(shè)計(jì)上的區(qū)別，指出Dalvik VM的字節(jié)碼可以用更少指令條數(shù)、更少內(nèi)存訪(fǎng)問(wèn)次數(shù)來(lái)完成操作。（看不到Y(jié)ouTube的請(qǐng)自行想辦法）

眼見(jiàn)為實(shí)。要自己動(dòng)手感受一下該例子，請(qǐng)先確保已經(jīng)正確安裝JDK 6，并從 官網(wǎng) 獲取Android SDK 1.6R1。連不上官網(wǎng)的也請(qǐng)自己想辦法。

創(chuàng)建Demo.java文件，內(nèi)容為：

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. }??

通過(guò)javac編譯，得到Demo.class。通過(guò)javap可以看到foo()方法的字節(jié)碼是：

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??

接著用Android SDK里platforms\android-1.6\tools目錄中的dx工具將Demo.class轉(zhuǎn)換為dex格式。轉(zhuǎn)換時(shí)可以直接以文本形式dump出dex文件的內(nèi)容。使用下面的命令：

Command prompt代碼 ?

1. dx?--dex?--verbose?--dump-to=Demo.dex.txt?--dump-method=Demo.foo?--verbose-dump?Demo.class??

可以看到foo()方法的字節(jié)碼是：

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??

（原本的輸出里還有些code-address、local-snapshot等，那些不是字節(jié)碼的部分，可以忽略。）

讓我們看看兩個(gè)版本在概念上是如何工作的。
JVM：

（圖中數(shù)字均以十六進(jìn)制表示。其中字節(jié)碼的一列表示的是字節(jié)碼指令的實(shí)際數(shù)值，后面跟著的助記符則是其對(duì)應(yīng)的文字形式。標(biāo)記為紅色的值是相對(duì)上一條指令的執(zhí)行狀態(tài)有所更新的值。下同）
說(shuō)明：Java字節(jié)碼以1字節(jié)為單元。上面代碼中有11條指令，每條都只占1單元，共11單元==11字節(jié)。
程序計(jì)數(shù)器是用于記錄程序當(dāng)前執(zhí)行的位置用的。對(duì)Java程序來(lái)說(shuō)，每個(gè)線(xiàn)程都有自己的PC。PC以字節(jié)為單位記錄當(dāng)前運(yùn)行位置里方法開(kāi)頭的偏移量。
每個(gè)線(xiàn)程都有一個(gè)Java棧，用于記錄Java方法調(diào)用的“活動(dòng)記錄”（activation record）。Java棧以幀（frame）為單位線(xiàn)程的運(yùn)行狀態(tài)，每調(diào)用一個(gè)方法就會(huì)分配一個(gè)新的棧幀壓入Java棧上，每從一個(gè)方法返回則彈出并撤銷(xiāo)相應(yīng)的棧幀。
每個(gè)棧幀包括局部變量區(qū)、求值棧（JVM規(guī)范中將其稱(chēng)為“操作數(shù)棧”）和其它一些信息。局部變量區(qū)用于存儲(chǔ)方法的參數(shù)與局部變量，其中參數(shù)按源碼 中從左到右順序保存在局部變量區(qū)開(kāi)頭的幾個(gè)slot。求值棧用于保存求值的中間結(jié)果和調(diào)用別的方法的參數(shù)等。兩者都以字長(zhǎng)（32位的字）為單位，每個(gè) slot可以保存byte、short、char、int、float、reference和returnAddress等長(zhǎng)度小于或等于32位的類(lèi)型的 數(shù)據(jù)；相鄰兩項(xiàng)可用于保存long和double類(lèi)型的數(shù)據(jù)。每個(gè)方法所需要的局部變量區(qū)與求值棧大小都能夠在編譯時(shí)確定，并且記錄在.class文件 里。
在上面的例子中，Demo.foo()方法所需要的局部變量區(qū)大小為3個(gè)slot，需要的求值棧大小為2個(gè)slot。Java源碼的a、b、c分 別被分配到局部變量區(qū)的slot 0、slot 1和slot 2。可以觀察到Java字節(jié)碼是如何指示JVM將數(shù)據(jù)壓入或彈出棧，以及數(shù)據(jù)是如何在棧與局部變量區(qū)之前流動(dòng)的；可以看到數(shù)據(jù)移動(dòng)的次數(shù)特別多。動(dòng)畫(huà)里可 能不太明顯，iadd和imul指令都是要從求值棧彈出兩個(gè)值運(yùn)算，再把結(jié)果壓回到棧上的；光這樣一條指令就有3次概念上的數(shù)據(jù)移動(dòng)了。

對(duì)了，想提醒一下：Java的局部變量區(qū)并不需要把某個(gè)局部變量固定分配在某個(gè)slot里；不僅如此，在一個(gè)方法內(nèi)某個(gè)slot甚至可能保存不同 類(lèi)型的數(shù)據(jù)。如何分配slot是編譯器的自由。從類(lèi)型安全的角度看，只要對(duì)某個(gè)slot的一次load的類(lèi)型與最近一次對(duì)它的store的類(lèi)型匹 配，JVM的字節(jié)碼校驗(yàn)器就不會(huì)抱怨。以后再找時(shí)間寫(xiě)寫(xiě)這方面。

Dalvik VM：

說(shuō)明：Dalvik字節(jié)碼以16位為單元（或許叫“雙字節(jié)碼”更準(zhǔn)確 =_=|||）。上面代碼中有5條指令，其中mul-int/lit8指令占2單元，其余每條都只占1單元，共6單元==12字節(jié)。
與JVM相似，在Dalvik VM中每個(gè)線(xiàn)程都有自己的PC和調(diào)用棧，方法調(diào)用的活動(dòng)記錄以幀為單位保存在調(diào)用棧上。PC記錄的是以16位為單位的偏移量而不是以字節(jié)為單位的。
與JVM不同的是，Dalvik VM的棧幀中沒(méi)有局部變量區(qū)與求值棧，取而代之的是一組虛擬寄存器。每個(gè)方法被調(diào)用時(shí)都會(huì)得到自己的一組虛擬寄存器。常用v0-v15這16個(gè)，也有少數(shù) 指令可以訪(fǎng)問(wèn)v0-v255范圍內(nèi)的256個(gè)虛擬寄存器。與JVM相同的是，每個(gè)方法所需要的虛擬寄存器個(gè)數(shù)都能夠在編譯時(shí)確定，并且記錄在.dex文件 里；每個(gè)寄存器都是字長(zhǎng)（32位），相鄰的一對(duì)寄存器可用于保存64位數(shù)據(jù)。方法的參數(shù)按源碼中從左到右的順序保存在末尾的幾個(gè)虛擬寄存器里。
與JVM版相比，可以發(fā)現(xiàn)Dalvik版程序的指令數(shù)明顯減少了，數(shù)據(jù)移動(dòng)次數(shù)也明顯減少了，用于保存臨時(shí)結(jié)果的存儲(chǔ)單元也減少了。

你可能會(huì)抱怨：上面兩個(gè)版本的代碼明明不對(duì)應(yīng)：JVM版到return前完好持有a、b、c三個(gè)變量的值；而Dalvik版到return-void前只持有b與c的值（分別位于v0與v1），a的值被刷掉了。
但注意到a與b的特征：它們都只在聲明時(shí)接受過(guò)一次賦值，賦值的源是常量。這樣就可以對(duì)它們應(yīng)用 常量傳播 ，將

Java代碼 ?

1. int ?c?=?(a?+?b)?*? 5 ;??

替換為

Java代碼 ?

1. int ?c?=?( 1 ?+? 2 )?*? 5 ;??

然后可以再對(duì)c的初始化表達(dá)式應(yīng)用常量折疊，進(jìn)一步替換為：

Java代碼 ?

1. int ?c?=? 15 ;??

把變量的每次狀態(tài)更新（包括初始賦值在內(nèi)）稱(chēng)為變量的一次“定義”（definition），把每次訪(fǎng)問(wèn)變量（從變量讀取值）稱(chēng)為變量的一次“使用”（use），則可以把代碼整理為“使用-定義鏈”（簡(jiǎn)稱(chēng)UD鏈， use-define chain ）。顯然，一個(gè)變量的某次定義要被使用過(guò)才有意義。上面的例子經(jīng)過(guò)常量傳播與折疊后，我們可以分析得知變量a、b、c都只被定義而沒(méi)有被使用。于是它們的定義就成為了無(wú)用代碼（dead code），可以安全的被消除。
上面一段的分析用一句話(huà)描述就是：由于foo()里沒(méi)有產(chǎn)生外部可見(jiàn)的副作用，所以foo()的整個(gè)方法體都可以被優(yōu)化為空。經(jīng)過(guò)dx工具處理后，Dalvik版程序相對(duì)JVM版確實(shí)是稍微優(yōu)化了一些，不過(guò)沒(méi)有影響程序的語(yǔ)義，程序的正確性是沒(méi)問(wèn)題的。這是其一。

其二是Dalvik版代碼只要多分配一個(gè)虛擬寄存器就能在return-void前同時(shí)持有a、b、c三個(gè)變量的值，指令幾乎沒(méi)有變化：

Dalvik bytecode代碼 ?

1. 0000 :?const/ 4 ??????v0,?#int? 1 ?//?# 1 ??
2. 0001 :?const/ 4 ??????v1,?#int? 2 ?//?# 2 ??
3. 0002 :?add-int??????v2,?v0,?v1??
4. 0004 :?mul-int/lit8?v2,?v2,?#int? 5 ?//?# 05 ??
5. 0006 :?return-void??

這樣比原先的版本多使用了一個(gè)虛擬寄存器，指令方面也多用了一個(gè)單元（add-int指令占2單元）；但指令的條數(shù)沒(méi)變，仍然是5條，數(shù)據(jù)移動(dòng)的次數(shù)也沒(méi)變。

題外話(huà)1：Dalvik VM是基于寄存器的，x86也是基于寄存器的，但兩者的“寄存器”卻相當(dāng)不同：前者的寄存器是每個(gè)方法被調(diào)用時(shí)都有自己一組私有的，后者的寄存器則是全局 的。也就是說(shuō)，Dalvik VM字節(jié)碼中不用擔(dān)心保護(hù)寄存器的問(wèn)題，某個(gè)方法在調(diào)用了別的方法返回過(guò)來(lái)后自己的寄存器的值肯定跟調(diào)用前一樣。而x86程序在調(diào)用函數(shù)時(shí)要考慮清楚 calling convention ，調(diào)用方在調(diào)用前要不要保護(hù)某些寄存器的當(dāng)前狀態(tài)，還是說(shuō)被調(diào)用方會(huì)處理好這些問(wèn)題，麻煩事不少。Dalvik VM這種虛擬寄存器讓人想起一些實(shí)際處理器的“寄存器窗口”，例如SPARC的 Register Windows 也是保證每個(gè)函數(shù)都覺(jué)得自己有“私有的一組寄存器”，減輕了在代碼里處理寄存器保護(hù)的麻煩——扔給硬件和操作系統(tǒng)解決了。 IA-64 也有寄存器窗口的概念。

題外話(huà)2：Dalvik的.dex文件在未壓縮狀態(tài)下的體積通常比同等內(nèi)容的.jar文件在deflate壓縮后還要小。但光從字節(jié)碼 看，Java字節(jié)碼幾乎總是比Dalvik的小，那.dex文件的體積是從哪里來(lái)減出來(lái)的呢？這主要得益與.dex文件對(duì)常量池的壓縮，一個(gè).dex文件 中所有類(lèi)都共享常量池，使得相同的字符串、相同的數(shù)字常量等都只出現(xiàn)一次，自然能大大減小體積。相比之下，.jar文件中每個(gè)類(lèi)都持有自己的常量池，諸 如"Ljava/lang/Object;"這種常見(jiàn)的字符串會(huì)被重復(fù)多次。Sun自己也有進(jìn)一步壓縮JAR的工具，Pack200，對(duì)應(yīng)的標(biāo)準(zhǔn)是 JSR 200 。它的主要應(yīng)用場(chǎng)景是作為JAR的網(wǎng)絡(luò)傳輸格式，以更高的壓縮比來(lái)減少文件傳輸時(shí)間。在 官方文檔 提到了Pack200所用到的壓縮技巧，

可見(jiàn).dex文件與Pack200采用了一些相似的減小體積的方法。很可惜目前還沒(méi)有正式發(fā)布的JVM支持直接加載Pack200格式的歸檔，畢竟網(wǎng)絡(luò)傳輸才是Pack200最初構(gòu)想的應(yīng)用場(chǎng)景。

再次提醒注意， 上面的描述是針對(duì)概念上的JVM與Dalvik VM，而不是針對(duì)它們的具體實(shí)現(xiàn) 。實(shí)現(xiàn)VM時(shí)可以采用許多優(yōu)化技巧去減少性能損失，使得實(shí)際的運(yùn)行方式與概念中的不完全相符，只要最終的運(yùn)行結(jié)果滿(mǎn)足原本概念上的VM所實(shí)現(xiàn)的語(yǔ)義就行。

===========================================================================

上面“簡(jiǎn)單”的提了些討論點(diǎn)，不過(guò)還沒(méi)具體到JavaScript引擎，抱歉。弄得太長(zhǎng)了，只好在這里先拆分一次……有些東西想寫(xiě)的，洗個(gè)澡又忘記了。等想起來(lái)再補(bǔ)充 orz
“簡(jiǎn)單”是相對(duì)于實(shí)際應(yīng)該掌握的信息量而言。上面寫(xiě)的都還沒(méi)撓上癢癢，心虛。
Anyway。根據(jù)拆分的現(xiàn)狀，下一篇應(yīng)該是討論動(dòng)態(tài)語(yǔ)言與編譯的問(wèn)題，然后再下一篇會(huì)看看解釋器的演化方法，再接著會(huì)看看JavaScript引擎的狀況（主要針對(duì)V8和Nitro，也會(huì)談?wù)凾amarin。就不討論JScript了）。

關(guān)于推薦資料，在 “我的收藏”的virtual machine標(biāo)簽 里就有不少值得一讀的資料。如果只是對(duì)JavaScript引擎相關(guān)感興趣的話(huà)也可以選著讀些。我的收藏里還有v8和tamarin等標(biāo)簽的，資料有的是 ^ ^

能有耐心讀到結(jié)尾的同學(xué)們，歡迎提出意見(jiàn)和建議，以及指出文中的錯(cuò)漏 ^_^
不像抓到蟲(chóng)就給美分的大師，我沒(méi)那種信心……錯(cuò)漏難免，我也需要進(jìn)一步學(xué)習(xí)。拜托大家了～

P.S. 畫(huà)圖真的很辛苦，加上JavaEye的帶寬也不是無(wú)限的……所以拜托不要直接鏈接這帖里的圖 <(_ _)>
有需要原始圖片的可以跟我聯(lián)系。我是畫(huà)成多幀PNG然后轉(zhuǎn)換為GIF發(fā)出來(lái)的。上面的PNG圖片都還保留有原始的圖層信息，要拿去再編輯也很方便 ^ ^

更新1：
原本在樹(shù)遍歷解釋器圖解的小節(jié)中，我用的是這幅圖：

其實(shí)上圖畫(huà)得不準(zhǔn)確，a、b、c的右值不應(yīng)該畫(huà)在節(jié)點(diǎn)上的；節(jié)點(diǎn)應(yīng)該只保存了它們的左值才對(duì)，要獲取對(duì)應(yīng)的右值就要查詢(xún)變量表。我修改了圖更新到正文了。原本的圖里對(duì)i的賦值看起來(lái)很奇怪，就像是遍歷過(guò)程經(jīng)過(guò)了兩次i節(jié)點(diǎn)一般，而事實(shí)不是那樣的。

虛擬機(jī)隨談（一）