V8 之旅：優化編譯器

原文出處： Jay Conrod   譯文出處： liuyanghejerry（@不編程不舒服斯基）  

在之前的兩篇文章中，我們討論了V8的Full Compiler和對象的內部表示。在幾年前，FC生成的原生代碼相對于JavaScript來說已經不錯了，但人們對性能的要求與日俱增，其速度標桿也越來越高，因此衍生出了Crankshaft。

本文來自Jay Conrod的A tour of V8: Crankshaft, the optimizing compiler，其中的術語、代碼請以原文為準。

Crankshaft是V8的優化編譯器。回憶一下，V8有兩個編譯器，另一個編譯器FC負責盡快生成未優化的代碼。對于只執行幾次的代碼，FC生成的代碼還是比較理想的。當FC產生的代碼運行過一段時間之后，V8會挑選出“熱門”的函數，重新用Crankshaft編譯。這大大提升了性能。

熱身完畢

如果只看腳本，很難說哪個函數最應當得到優化。V8使用一個運行時性能分析器在腳本運行的時候識別熱門的函數。

Crankshaft剛開始部署時，V8選擇在另一線程跑棧采樣分析器（stack sampling profiler）。幾乎每隔一段時間（桌面版本為1ms，移動版本為5ms）那個線程就被喚醒一次，然后向主線程發送SIGPROF信號。主線程的信號處理代碼會重置棧頂的高度（一般是一個標志棧結束的地址）。每當一個函數被調用以及每輪循環的時候，經過JIT的代碼會檢查是否達到棧頂，如果棧指針超過了棧頂，就會調用運行時來報錯。這給了性能分析器一個打斷腳本執行的時機。V8運行時會在檢查出棧溢出是因為信號SIGPROF時調用性能分析器，于是性能分析器就可以在這時看到棧頂的幾幀，然后標注這些函數進而優化。

這種性能分析器有幾個短板。由于采樣是幾近隨機的，性能因素并不主導采樣。盡管分析器在統計上傾向于挑選出最熱門的函數，但其可能在頁面每次重載時得出不同順序或不同次數的結果。想象一下當時的情景，性能測試的時候得出的是差異很大的結果，V8測試集當中的某些測試甚至能在多次運行時差距達50%。同時這種方案會因其打斷代碼執行的機制，在整體上對不含循環的大函數有失偏頗。

V8如今用基于計數的性能分析器（counter-based profiler）。每個經過FC的函數都包含一個計數器，當函數返回或完成一輪循環的時候，就會減少計數的值。而減多少則依據函數或循環的大小，因此這對于大函數和循環來說更加公平。分析器在計數減到0的時候調用，然后和棧采樣分析器類似（實際上更加出色），但更側重性能地選出熱門函數。另外這樣對于已優化的代碼來說沒有任何影響，因為只有未優化的代碼才會有計數器。

一旦一個函數被分析器標記為需要優化，指向其代碼的指針就會被改寫指向為一個V8內置的函數——LazyRecompile，來調用編譯器。這樣函數就會在下次調用時得到優化。

剖析Crankshaft

Crankshaft經過以下幾個階段生成代碼：

• 語法分析：這一階段負責將源代碼翻譯為AST。Crankshaft與FC共享同一個語法分析器，但出于空間占用考慮，V8并不保留任何編譯器所得到的AST（以及其他中間產物）。而且AST也不常用，生成也很容易。
• 作用域分析：在這一階段，V8將確定變量是如何被使用的，將其與各自的定義鏈接。局部變量、閉包變量、全局變量的對待方式會各不相同。這個階段也與FC共享。某些代碼的寫法（比如用eval動態引入變量）會使一個函數失去優化或內聯的資格。
• 圖生成：Crankshaft使用AST、作用域信息以及FC代碼反饋而來的類型信息，來構建Hydrogen控制流程圖。內聯也發生在這一階段。Hydrogen是Crankshaft中一個高層次、架構無關的中間代碼。
• 優化：絕大多數優化都基于Hydrogen控制流程圖發生在這一階段。這是Crankshaft唯一能夠與JS線程并行的時候。雖然本文撰寫時還不是并行的。
• 低級化：優化結束之后，Hydrogen外會生成一個Lithium圖。Lithium圖是一個低級且架構相關的中間代碼。寄存器的分配就是在這一階段施行的。
• 代碼生成：在這個最后階段中，Crankshaft按照Lithium圖中的每個指令發送原生指令。元數據，比如重定位信息以及去優化數據，也是在這一階段生成。完成之后，經過JIT的代碼會放在一個Code對象中，然后繼續腳本的執行。

整個結構對于優化編譯器來說非常典型，然而某些方面可能會讓你驚訝。首先，Crankshaft并沒有一個真正的低級表達形式。Hydrogen和Lithium的指令基本上和JS中的操作相對應。在某些情況下，十來個原生指令才對應一個Lithium指令。這可能會導致生成出來的代碼中有一定的冗余。第二，Crankshaft一種指令調度都沒有。對于x86處理器來說不算大問題，因其最終是亂序執行；但對于一些相對簡單的RISC指令集架構，比如ARM，會造成一些麻煩。

這些缺點大多是因為Crankshaft在性能影響上的重要地位。JS代碼在Crankshaft執行時是中斷的，這就意味著Crankshaft必須盡快完成任務，而任何附加的階段和優化都可能得不償失。V8的開發者們正在為Crankshaft的并行上努力，但這一功能目前還沒有打開。V8的堆并不支持多線程訪問，而如果不訪問堆，則只有優化階段能夠并行。然而使堆變得線程安全是一項復雜的任務，可能會引入額外的同步負擔。

Hydrogen與Lithium

V8的高級中間代碼叫做Hydrogen，而低級中間代碼叫Lithium。如果你曾經用過LLVM，Hydrogen的結構看起來會有些熟悉。函數被表達為一個由一組區塊構成的流程圖，其中的每個區塊都包含一系列靜態單賦值形式（SSA）的指令。每條指令則包含一組操作符和一組操作符調用，因此你可以將其想象為一個疊在流程圖之上的數據流圖。每個Hydrogen指令表示一個較為高級的操作，比如算術運算、屬性的存/取、函數調用或者類型檢查。

大多數優化過程發生在Hydrogen身上或構造Hydrogen的時候。這是Crankshaft所執行的優化：

• 動態類型反饋：在圖生成的同時，大多數操作會特化為對一個類型的操作。這些類型在FC代碼的內聯緩存中得到。比如，如果IC實現的是一個讀取操作，而這個讀取只作用于一種對象的某個屬性，特化的Hydrogen代碼會將被優化為只處理這一種對象的代碼。為此，必要時會加入類型檢查。
• 內聯：發生在圖的生成階段。內聯的啟發規則非常簡單：基本上如果一個函數在調用時已知且內聯它是安全的，那么就內聯它。大函數（源碼中大于600個包括空格在內的字符，或超過196個AST節點）則不會內聯。最多只有196個語法節點可在一個函數中內聯。
• 形式推斷：Hydrogen支持三種寄存器中的值：標記值、整型值和雙精度浮點。所謂標記值，就是指這個值是封箱的。字符串和對象總是標記值，但數字則不一定。原生整型和雙精度浮點更有效率，但所有的值都必須在存到內存中或傳遞給另一個函數前標記。這一環決定了每個值應有的表達形式。
• 靜態類型推斷：這一步Crankshaft嘗試確定函數中各種值的類型。由于一次只能針對一個函數而且大多數操作（比如函數調用、屬性讀取）產生的類型無法推斷，這步效率很低。不過有些類型檢查會因為該值有精確的類型信息而省去。
• UInt32分析：V8使用31bits來表示小整數。其最低位保留給垃圾回收器用以判定它是指針還是數字（0表示數字，1表示指針）。Crankshaft可以使用全部32-bit來保存不經過內存的局部變量和臨時值，而當超出這一區間時，則需要特殊處理。語義上，JavaScript將所有數字都視為64位雙精度浮點，因此允許用整數來表達原本是錯誤的。但這一步將某些操作歸納為無符號的，于是微小的溢出并不會在這些特定情況下造成麻煩。這對于諸如密碼學、壓縮和圖形處理相關的程序來說非常有用。
• 標準化：這步是用來進行簡化的。它去掉了不必要的操作，并進行一些簡化。
• 值編號（GVN）：這是去除冗余的標準步驟。依次處理每個指令，當一個指令處理之后，會生成一個基于其操作、輸入以及任何相關數據的哈希值，插入到一個哈希表中。后續如果遇到同樣哈希值的指令，則GVN會刪除后續的那個。但每當遇到對該指令存在副作用的指令，則從哈希表中清除原先存入的這個指令。比如，對于兩個完全一樣的讀取操作來說，如果中間還有一個存儲操作，則這兩個讀取操作并不能合并。
  移出循環無關代碼（LICM）：這個和GVN同時執行。循環中并不依賴循環中其他代碼的指令，將被提到循環之前。對循環無關值的類型檢查也會被提到循環之前，但這可能會導致某些場景下并不會發生的類型檢查也被執行，因此編譯器會在這時趨于保守。
• 范圍分析：這步會確定每個整數操作的上限和下限。這樣就有可能去掉一些溢出檢查。在實踐中，這個并不太精確。
• 去除冗余的數組范圍檢查：去掉某些已在數組元素訪問中執行過的多余數組范圍檢查。
• 后推數組下標計算：這一步會反轉LICM對一些非常簡單的表達式（如數組下標增加或減去一個常數）的效果。所有V8支持的架構都有指令來完成尋址時對下標的簡單加減，因此提前這些代碼通常也沒什么大的好處。
• 去除無效代碼：這是一種清理工作。它會移除掉Hydrogen指令中無效或者沒有副作用的部分。這些指令往往是其他優化所產生的副產品，而程序員自己所寫的無效代碼則不包含在內：V8可能會在函數運行的過程當中，在優化代碼和未優化代碼之間切換，而如果優化后的代碼缺失了某個未優化代碼所需要的值，則可能會造成崩潰。（譯注：也就是說，在Crankshaft看來可能無效的代碼，很可能只是整個腳本的一部分，而整個腳本中的其它未優化部分，實際是需要那部分看似無效的代碼的。）

Lithium是V8的低級、機器相關的中間代碼。實際上它并不是特別的低級：每個Hydrogen指令至多被低級化為一個Lithium指令。有些Hydrogen指令，例如HConstant、HParameter原封不動變成了Lithium指令。其他一些Hydrogen指令會被低級化為某些由操作數銜接起來的指令（而在Hydrogen中它們本是直接相連的）。這里的操作數可能是常數、寄存器，或者棧槽。寄存器分配器將決定每個操作數的類型和其存放位置。大多數指令只支持寄存器操作數，因此寄存器分配器需要在這些操作數中間增加存取的指令。

原生代碼將從Lithium指令得出。簡單的Lithium指令可能只對應一條原生指令，而某些復雜的Lithium指令則會對應10-20條原生指令（ARM如此，其他架構可能有差異）。

即使是在只處理常規使用的優化代碼當中，你也會因JavaScript腳本最終產生的復雜代碼而咋舌。舉例來說，以下是為一個JS對象增加一個屬性的代碼：

 ;; HCheckNonSmi: 檢查低位，確定目標是整數
    ;; 整數的最低位總是0
     40  tst r0, #1
     44  beq +188 -> 232

    ;; HCheckMaps: 將目標的Map與已知Map對比
     48  ldr r9, [r0, #-1]
     52  movw ip, #41857             ;; object:  <Map(elements=3)>
     56  movt ip, #17120
     60  cmp r9, ip
     64  bne +172 -> 236

    ;; HCheckPrototypeMaps: 檢查目標的原型鏈，
    ;; 以防有同名的只讀屬性
     68  movw r2, #38241             ;; object:  Cell for  <an Object>
     72  movt r2, #15696
     76  ldr r2, [r2, #+3]
     80  ldr r1, [r2, #-1]
     84  movw ip, #41937             ;; object:  <Map(elements=3)>
     88  movt ip, #17120
     92  cmp r1, ip
     96  bne +144 -> 240
    100  movw r2, #46869             ;; object:  <an Object>
    104  movt r2, #14674
    108  ldr r1, [r2, #-1]
    112  movw ip, #36057             ;; object:  <Map(elements=3)>
    116  movt ip, #17120
    120  cmp r1, ip
    124  bne +116 -> 240

    ;; HConstant: 這才是我們要存儲的值
    128  mov r1, #198

    ;; HStoreNamedField: 以下是存儲操作
    ;; 首先，讀取Transition的Map
    132  movw r9, #41977             ;; object:  <Map(elements=3)>
    136  movt r9, #17120

    ;; 接著，將其存入該對象的首字
    140  str r9, [r0, #-1]

    ;; 可能還需要將Map的變動通知垃圾回收器
    ;; 這里是一個寫操作的內存屏障，
    ;; 遞增標記需要這樣的保證
    144  sub r2, r0, #1
    148  bfc r9, #0, #20
    152  ldr r9, [r9, #+12]
    156  tst r9, #4
    160  beq +36 -> 196
    164  mov r9, r0
    168  bfc r9, #0, #20
    172  ldr r9, [r9, #+12]
    176  tst r9, #8
    180  beq +16 -> 196
    184  movw ip, #37056
    188  movt ip, #10611
    192  blx ip

    ;; 現在我們終于可以存儲那個屬性了
    ;; 因為這次存儲的是整數，無需通知垃圾回收器
    ;; 但通常這里還需要另一個內存屏障
    196  str r1, [r0, #+11]

棧上替換

我們講性能分析器時說過，經過分析器標記的函數，編譯器會在下一次調用時對其進行優化編譯，而當編譯工作結束后，運行時即會載入新的優化代碼來執行。對于大多數函數來說，這種機制已經足夠好了，但對于包含熱門循環，且只運行一次的函數來說，這個機制就有瑕疵了。

function calledOnce() {
    for (var i = 0; i < 100000; i++)
    // ... 這里是需要優化的部分
}

這類函數仍然需要優化，因此一種略復雜的機制應運而生。如果性能分析器被觸發時，一個函數已被標記為需要優化但還沒有再次被調用，則分析器會嘗試棧上替換。分析器會直接調用Crankshaft，立即生成出優化代碼；當Crankshaft執行完畢時，V8會依據原先包含該函數的棧幀中的其他代碼，構造一個新的棧幀來存放優化后的代碼。這時將舊的棧幀彈出，壓入新的棧幀，恢復腳本的運行。

這一過程需要兩個編譯器的支持。FC需要產生包含該棧幀中其他值的位置信息，而Crankshaft需要生成這些值即將存放的新位置的信息。同時，Crankshaft還需要生成額外的“接入層”，來將這些值從棧幀讀取到正確的寄存器當中。

去優化

上面提到過，Crankshaft生成的代碼只是特化針對于FC所遇到的類型，因此Crankshaft無法處理所有可能的值。我們需要一種機制來在遇到未知類型和算術運算溢出時優雅降級，換用FC的代碼。這種機制就叫做去優化。通常去優化就是進行棧上替換的逆操作。然而這里面有個小問題：Crankshaft支持內聯，因此類型問題有可能會在內聯代碼之內發生。這時去優化過程將不得不對多個棧幀進行操作。

為了使去優化器的工作更加容易，Crankshaft會生成去優化的輸入數據，每個去優化可能發生的地方，都會有相應的命令關聯。去優化器將通過這些命令，來將寄存器、棧槽等從優化代碼中的值，轉換為未優化代碼中的值。每條命令都包含有與棧相關的操作，比如“從寄存器r6中獲取值，將其封箱為數字，然后壓入下一棧槽”。去優化器的任務就是尋找正確的命令，將其執行，然后彈出優化的棧幀，壓入相應未優化的棧幀。

總結

Crankshaft是V8的秘密武器。通過運行時的性能分析器，V8能夠檢測出最需要優化的函數。由于V8的去優化隨時可能需要將代碼降為未優化代碼，Crankshaft可以在一定程度上具有推斷能力，只優化特定情況下的代碼。

在將來，Crankshaft很可能會并行。由于可以騰出更多的時間優化更多的代碼，這能夠讓V8的性能更高。