Js引擎解析執行 閱讀筆記

Js引擎解析執行 閱讀筆記

---

一篇閱讀筆記
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次，那么就進行即時編譯；否則解釋執行。