Explain

本片文章是對發表于 “ACM SIGPLAN NOTICES” 期刊的論文《Trace-based Just-in-Time Type Specialization for Dynamic Languages》的翻譯。

論文在 JavaScript 的解釋器中已經實現，作者將實現后的JIT編譯器叫做 TraceMonkey。LuaJIT 的實現與 TraceMonkey 有很多相似之處，所以這篇文章對于理解 LuaJIT很有幫助。

一、簡介

動態語?JavaScript、Python 和 Ruby 等語??常流?，因為它們表達能?強、?專業??也能輕松使?，并且部署起來就像分發源?件?樣簡單。它們既可?于?型腳本，也可?于復雜的應?程序。例如，JavaScript 是客戶端 Web 編程的事實標準并?于基于瀏覽器的?產?應?程序（例如 Google Mail、Google Docs 和 Zimbra Collaboration Suite）的應?程序邏輯。在這個領域，為了提供流暢的?戶體驗以及?持新?代應?程序，虛擬機必須提供較低的啟動時間和較?的性能。

靜態類型語?的編譯器依靠類型信息來?成?效的機器代碼。在 JavaScript 等動態類型編程語?中，表達式的類型可能會在運?時發?變化。這意味著編譯器?法再輕松地將操作轉換為針對某?特定類型的機器指令。如果沒有確切的類型信息，編譯器必須?成速度較慢的通?機器代碼，以處理所有潛在的類型組合。雖然編譯時靜態類型推斷可能能夠收集類型信息以?成優化的機器代碼，但傳統的靜態分析?常昂貴，因此不太適合 Web 瀏覽器的?度交互環境。

我們提出了?種基于跟蹤（trace-based）的動態語?編譯技術，該技術可以兼顧編譯速度和?成的機器代碼的出?性能。我們的系統使?混合模式執??法：系統在快速啟動的字節碼（bytecode）解釋器中開始運? JavaScript。在程序運?時，系統識別熱的（hot，即執?頻繁）的字節碼序列，記錄它們，并將它們編譯為快速本機代碼。我們將這樣的指令序列稱為跟蹤（trace）。

與基于方法（method-based）的動態編譯器不同，我們的動態編譯器以單個循環的粒度運行。這種設計選擇基于這樣的預期：程序大部分時間都花在熱循環上。即使在動態類型語言中，我們也期望熱循環大多是類型穩定的，這意味著值的類型是不變的。例如，我們期望以整數開始的循環計數器在所有迭代中都保持整數。當這兩個期望都成立時，基于跟蹤（trace-based）的編譯器可以用少量類型專門的、高效編譯的跟蹤（trace）來覆蓋程序執行。

每個編譯的跟蹤（trace）都涵蓋了程序中的一條路徑，并將值映射到類型。當 VM 執行編譯跟蹤時，它無法保證將遵循相同的路徑，也?法保證在后續循環迭代中會出現相同的類型。因此，記錄（record）和編譯跟蹤會推測，在循環的后續迭代中，路徑和類型將與記錄期間完全相同。

每個編譯的跟蹤都包含所有守衛（guards，用于檢查推測是否符合預期）來驗證推測。如果其中?個守衛失敗（即控制流不同，或者?成了不同類型的值），則跟蹤退出。如果退出變得熱（hot），VM 就會記錄（record）?個分支跟蹤（branch trace）從出?處開始覆蓋新路徑。這樣，VM 記錄了?個追蹤樹（trace tree）覆蓋循環中的所有熱路徑。

嵌套循環（nested loops）可能難以針對跟蹤 VM 進行優化。在一個簡單的實現中，內循環（inner loop）將首先變得熱，并且 VM 將從那里開始跟蹤。當內循環退出時，VM 將檢測到已采用不同的分支。VM 將嘗試記錄分支跟蹤，并發現跟蹤到達的不是內循環頭，而是外循環（outer loop）頭。此時，VM 可以繼續跟蹤，直到再次到達內循環頭，從而在內循環的跟蹤樹內跟蹤外循環。但這需要為內循環中的每個側出口（side exit）和類型組合（ type combination）跟蹤外循環的副本。本質上，這是一種意外尾部重復的形式，很容易溢出代碼緩存（ code cache）。或者，VM 可以簡單地停止跟蹤，并放棄跟蹤外循環。

我們通過記錄嵌套跟蹤樹（nested trace trees）來解決嵌套循環問題。我們的系統對內循環的跟蹤與原始版本完全相同。當到達外循環時，系統停?擴展內樹（inner tree），但隨后在外循環頭開始新的跟蹤。當外循環到達內循環頭時，系統會嘗試調用內循環的跟蹤樹。如果調用成功，VM 會將對內樹的調用記錄為外跟蹤的一部分，并正常完成外跟蹤。這樣，我們的系統可以跟蹤嵌套到任意深度和數量的循環，而不會導致過多的尾部重復。

這些技術允許 VM 動態地將程序轉換為嵌套的、類型專?化的跟蹤樹。由于跟蹤可以跨越函數調?邊界，我們的技術也可以實現內聯（inline）的效果。由于跟蹤沒有內部控制流連接，所以跟蹤生成的中間代碼是線性的，我們可以讓編譯器在線性時間內進行一些簡單的優化。因此，我們的跟蹤 VM 可以有效地執?在靜態優化設置中需要過程間分析的同類優化。這使得跟蹤成為?種有吸引?且有效的?具，可以對復雜的函數調?豐富的代碼進?類型專?化。

我們為現有的 JavaScript 解釋器 SpiderMonkey 實現了這些技術。我們將基于跟蹤的VM稱為TraceMonkey。TraceMonkey ?持 SpiderMonkey 的所有 JavaScript 特性，可使可追蹤程序的運?速度提? 2 到 20 倍。

二、一個跟蹤運行的示例

本節通過描述 TraceMonkey 如何執行示例程序來概述我們的系統。示例程序如下所示，使用嵌套循環計算前 100 個素數。

for (var i = 2; i < 100; ++i) {if (!primes[i])continue;for (var k = i + i; i < 100; k += i)primes[k] = false;
}

下圖的狀態機描述了 Trace Monkey 的主要活動以及導致轉換到新活動的條件，本節的敘述應與圖中的內容一起閱讀。在深色框中，TM 將 JS 作為編譯的跟蹤（complied trace）執行。在淺灰色框中，TM 在標準解釋器（interpret）中執行 JS。白框是開銷。因此，為了最大限度地提高性能，我們需要最大限度地增加在最暗的框中花費的時間，并最大限度地減少在白框中花費的時間。最好的情況是 loop edge 的類型與 entry 的類型相同——然后 TM 可以停留在本機代碼中，直到循環完成。

TraceMonkey 總是在字節碼（bytecode）解釋器中開始執行程序。每個循環后沿邊（ loop back edge）都是一個潛在的跟蹤點（ trace point）。當解釋器越過循環邊（loop edge）時，TraceMonkey 會調用跟蹤監視器（ trace monitor），它可能決定記錄或執行 native 跟蹤。在執行開始時，還沒有編譯跟蹤，因此跟蹤監視器會計算每個循環后沿邊執行的次數，直到循環變熱，目前在 2 次執行之后變熱。請注意，我們的循環編譯方式是，循環邊（loop edge）在進入循環之前被執行，因此第二次執行發生在第一次迭代之后。

以下是按外循環迭代分解的事件序列：

• i=2。這是外循環的第一次迭代。第 4-5 行的循環在第二次迭代時變得很熱，因此 TraceMonkey 在第 4 行進入記錄模式。在記錄模式下，TraceMonkey 會將跟蹤的代碼記錄在我們稱為 LIR 的低級編譯器中間表示中。LIR 跟蹤會對所有執行的操作和所有操作數的類型進行編碼。LIR 跟蹤還會對守衛（guards）進行編碼，這些守衛是用于檢查驗證控制流和類型是否與跟蹤記錄期間觀察到的控制流和類型相同。因此，在以后的執行中，當且僅當所有守衛指令都通過時，跟蹤才具有所需的程序語義。
  當執?返回到循環頭或退出循環時，TraceMonkey 停?記錄。在本例中，執?返回到第 4 ?的循環頭。
  記錄完成后，TraceMonkey 使用記錄的類型信息將跟蹤（trace）編譯為 native 代碼以進行優化。結果是一個本機代碼片段，如果解釋器 PC 和值的類型與跟蹤記錄開始時觀察到的相匹配，則可以輸入該片段。我們示例中的第一個跟蹤 $T_{45}$ 覆蓋了第 4 行和第 5 行。如果 PC 在第 4 行，i 和 k 是整數，并且 primes 是一個對象，則可以輸入此跟蹤。編譯 $T_{45}$ 后，TraceMonkey 返回到解釋器并循環回到第 1 行。

• i=3。現在第 1 行的循環頭已變為熱循環，因此 Trace Monkey 開始記錄。當記錄到達第 4 行時，Trace Monkey 觀察到它到達已被編譯為跟蹤的內循環頭，因此 TraceMonkey 嘗試將內循環嵌套在當前跟蹤（外循環的trace）中。首先是將內跟蹤作為子程序調用，這將執行第 4 行上的循環直至完成，然后返回到記錄器。TraceMonkey 驗證調用是否成功，然后將對內跟蹤的調用記錄為當前跟蹤的一部分。記錄持續到執行到第 1 行，此時 TraceMonkey 完成并為外循環 $T_{16}$ 編譯跟蹤。

• i=4。在此迭代中，TraceMonkey 調用 $T_{16}$。由于 i=4，因此采用第 2 行上的 if 語句，而此分支未在原始跟蹤中采用，因此這導致 $T_{16}$ 未通過守衛并從側面退出（side exit）。出口尚未熱，因此 TraceMonkey 返回到解釋器，解釋器執行 continue 語句。

• i=5。TraceMonkey 調用 $T_{16}$，后者又調用嵌套跟蹤 $T_{45}$。$T_{16}$ 循環回到其自己的標題，開始下一次迭代，而無需返回監視器（monitor）。

• i=6。在此迭代中，再次采用第 2 行的側出口（side exit）。這次，側出口變得很熱，因此記錄了一條覆蓋第 3 行并返回到循環頭的跟蹤 $T_{23,1}$。因此，$T_{23,1}$的末尾直接跳轉到 $T_{16}$ 的開頭。側出口已修補，因此在未來的迭代中，它直接跳轉到$T_{23,1}$。此時，TraceMonkey 已編譯足夠的跟蹤來覆蓋整個嵌套循環結構，因此程序的其余部分完全作為本機代碼運行。

三、跟蹤樹

在本節中，我們將描述跟蹤、跟蹤樹以及它們在運行時的形成方式。雖然我們的技術適用于任何動態語言解釋器，但為了使說明簡單，我們將假設使用字節碼（bytecode）解釋器來描述它們。

3.1 Traces

跟蹤只是一條程序路徑，它可能跨越函數調用邊界。TraceMonkey 專注于循環跟蹤（loop traces），它起源于循環邊（loop edge）并表示通過相關循環的單次迭代。

與擴展基本塊（extended basic block，編譯器設計中有此概念）類似，跟蹤僅在頂部進入，但可能有許多出口。與擴展基本塊相比，跟蹤可以包含連接節點。但是，由于跟蹤始終只遵循原始程序中的一條路徑，因此連接節點在跟蹤中無法識別，并且像常規節點一樣具有單個前趨節點。

類型化跟蹤（typed trace）是使用類型注釋跟蹤上的每個變量（包括臨時變量）的跟蹤。類型化跟蹤還具有一個類型映射（type map）的條目（entry），在定義跟蹤中使用的變量之前，提供所需的類型。例如，跟蹤可以具有類型映射（x：int，b：boolean），這意味著只有當變量 x 的值是 int 類型并且 b 的值是 boolean 類型時，才可以進入跟蹤。類型映射的條目非常類似于函數的簽名。

在本文中，我們僅討論類型化循環跟蹤，我們將其簡稱為“跟蹤”。類型化循環跟蹤的關鍵屬性是，可以使用與類型化語言相同的技術將它們編譯為高效的機器代碼。

在 TraceMonkey 中，記錄跟蹤使用的是 trace-flavored（跟蹤風格）的 SSA LIR（低級中間表示）。在 trace-flavored 的 SSA（或 TSSA）中，phi 節點僅出現在入口點，入口點可通過入口和循環邊（ loop edge）到達。重要的 LIR 原語（primitive）是常量值、內存加載和存儲（按地址和偏移量）、整數運算符、浮點運算符、函數調用和條件退出。類型轉換（例如整數到雙精度）由函數調用表示。這使得 TraceMonkey 使用的 LIR 獨立于源語言的具體類型系統和類型轉換規則。LIR 操作足夠通用，后端編譯器與語言無關。下列是一個示例跟蹤的LIR 。

v0 := ld state[748]		// load primes from the trace activation recordst sp[0], v0		// store primes to interpreter stack
v1 := ld state[764]		// load k from the trace activation record
v2 := i2f(v1)			// convert k from int to doublest sp[8], v1		// store k to interpreter stackst sp[16], 0		// store false to interpreter stack
v3 := ld v0[4]			// load class word for primes
v4 := and v3, -4		// mask out object class tag for primes
v5 := eq v4, Array		// test whether primes is an arrayxf v5				// side exit if v5 is false
v6 := js_Array_set(v0, v2, false)	// call function to set array element
v7 := eq v6, 0			// test return value from callxt v7				// side exit if js_Array_set returns false.

字節碼解釋器通常以盒裝格式（boxed format，即帶有附加類型標記位（attached type tag bits），可以理解為集合）表示各種復雜數據結構（例如哈希表）中的值。由于跟蹤旨在表示消除所有復雜性的高效代碼，因此我們的跟蹤盡可能多地對簡單變量和數組中的未裝箱（unboxed）值進行操作。跟蹤將其所有中間值記錄在一個小的活動記錄（activation record）區域中。為了使跟蹤中的變量訪問速度更快，跟蹤還通過取消裝箱并將它們復制到其活動記錄來導入本地和全局變量。因此，跟蹤可以使用來自 native 活動記錄的簡單加載和存儲來讀取和寫入這些變量，而不受解釋器使用的裝箱機制的影響。當跟蹤退出時，VM 會將值從此 native 存儲位置裝箱并將它們復制回解釋器結構。

對于源程序中的每個控制流分支，記錄器都會生成條件退出 LIR 指令。如果所需的控制流與跟蹤記錄時的控制流不同，則這些指令將從跟蹤中退出，從而確保跟蹤指令僅在應該運行時運行。我們將這些指令稱為守衛（guard）指令。

我們的大多數跟蹤都表示循環并以特殊的循環 LIR 指令結束，這種LIR 指令只是一個無條件分支到跟蹤的頂部，因此跟蹤僅通過守衛指令返回或結束循環。

現在，我們描述記錄跟蹤生成LIR時所執行的部分關鍵優化。所有這些優化都通過專門針對當前跟蹤，將復雜的動態語言構造簡化為簡單的類型構造。每個優化都需要守衛指令來驗證它們對狀態的假設并在必要時退出跟蹤。

類型特化（Type specialization）

所有 LIR 原語（primitives）都適用于特定類型的操作數。因此，LIR 跟蹤必然是類型特化的，編譯器可以輕松生成不需要類型分派（type dispatch）的轉換。典型的字節碼解釋器會隨每個值攜帶標記位（tag bits），并且在執行任何操作前，必須先檢查標記位、動態分派（dynamically dispatch），再屏蔽標記位以恢復未標記的值，使用未標記的值執行操作，然后對計算的結果重新應用標記。

下圖是 SpiderMonkey JavaScript 解釋器中的標記值。測試標記、解箱（unboxing，提取未標記的值）和裝箱（boxing，創建標記值）是顯著的開銷，避免這些開銷是跟蹤編譯的一個主要優點。

LIR 忽略操作本身以外的所有內容。一個潛在的問題是，某些操作可能會產生不可預測類型的值。例如，從對象讀取的值可能會產生任何類型，而不一定是記錄期間觀察到的類型。記錄器生成的守衛指令，如果操作產生的值與記錄期間看到的值的類型不同，則有條件退出。這些守衛指令保證只要執行在跟蹤中，值的類型就與跟蹤的類型相匹配。當 VM 沿著此類類型守衛觀察到 side exit 時，會記錄源自 side exit 位置的新類型跟蹤，從而捕獲所討論操作的新類型。

對象特化。在 JavaScript 中，名稱查找語義很復雜，并且可能很昂貴，因為它們包括對象繼承和 eval 等特性。要評估像 o.x 這樣的對象屬性讀取表達式，解釋器必須搜索 o 及其所有原型和父級的屬性映射。屬性映射可以用不同的數據結構（例如，每個對象的哈希表或共享哈希表）實現，因此搜索過程還必須根據搜索過程中找到的每個對象的表示進行分派。TraceMonkey 可以簡單地觀察搜索過程的結果并記錄最簡單的 LIR 以訪問屬性值。例如，搜索可能會在 o 的原型中找到 o.x 的值，它使用共享哈希表表示將 x 放在屬性 vector 的slot 2 中。然后，記錄可以生成僅用兩到三個加載即可讀取 o.x 的 LIR：一個用于獲取原型，可能一個用于獲取屬性值 vector ，還有一個用于從 vector 中獲取slot 2。與原始解釋器代碼相比，這是一個巨大的簡化和加速。繼承關系和對象表示在執行過程中可能會發生變化，因此簡化的代碼需要守衛指令來確保對象表示相同。在 TraceMonkey 中，對象的表示被分配了一個稱為對象形狀（object shape）的整數鍵。因此，守衛??是對對象形狀的簡單相等性檢查。

數字特化。JavaScript 沒有整數類型，只有 Number 類型，即一組 64 位 IEEE-754 浮點數（“雙精度數”）。但許多 JavaScript 運算符（尤其是數組訪問和按位運算符）實際上都是對整數進行操作，因此它們首先將數字轉換為整數，然后將任何整數結果轉換回雙精度數。顯然，想要快速運行的 JavaScript VM 必須找到一種直接對整數進行操作的方法，并避免這些轉換。在 TraceMonkey 中，我們支持兩種數字表示：整數和雙精度數。解釋器盡可能多地使用整數表示，無法用整數表示則切換為雙精度數的表示。啟動跟蹤時，可能會導入某些值并將其表示為整數。對整數的某些操作需要守衛，例如，將兩個整數相加可能會產生一個對于整數表示來說太大的值（加法溢出）。

函數內聯。LIR 跟蹤可以跨越任一方向的函數邊界，從而實現函數內聯。需要記錄函數入口和出口用來復制參數和返回值的 mov 指令，然后，編譯器使用復制傳播優化這些 mov 語句。為了能夠返回到解釋器，跟蹤還必須生成 LIR 來記錄已進入和退出調用棧幀（call frame）。frame 入口和出口 LIR 保存的信息足以允許稍后恢復解釋器調用堆棧（call stack），并且比解釋器的標準調用代碼簡單得多。如果輸入的函數不是常量（在 JavaScript 中包括任何按函數名調用），記錄器還必須發出 LIR 來確保該函數是相同的。

guard 和 side exit。上面描述的每個優化都需要一個或多個守衛來驗證在進行優化時所做的假設，守衛只是一組執行測試和條件退出的 LIR 指令。exit 分支到一個側出口（side exit），這是 LIR 的一小段跟蹤外（off-trace）片段，它返回一個指向一個結構的指針，該結構描述退出的原因以及出口點處的解釋器 PC 和恢復解釋器狀態結構所需的任何其他數據。

中止（abort）。有些構造很難在 LIR 跟蹤中記錄。例如，eval 或對外部函數的調用可能會以不可預測的方式改變程序狀態，使得跟蹤器難以知道當前類型映射以繼續跟蹤。跟蹤實現還可以有許多其他限制，例如，小內存設備可能會限制跟蹤的長度。當發生任何阻止實現繼續跟蹤記錄的情況時，實現將中止跟蹤記錄并返回到跟蹤監視器。

3.2 Trace Trees

特別簡單的循環，即控制流、值類型、值表示和內聯函數都是不變的循環，可以用單個跟蹤來表示。但大多數循環至少有一些變化，因此程序將從主跟蹤中獲取側出口（ side exit）。當側出口變得熱時，TraceMonkey 會從該點開始新的分支跟蹤（branch trace），并修補側出口以直接跳轉到該跟蹤。這樣，單個跟蹤可以根據需要擴展為單入口、多出口的跟蹤樹。

本節介紹如何在執行過程中形成跟蹤樹。目標是在執行過程中形成覆蓋程序所有熱路徑的跟蹤樹。

開始一棵樹。樹總是從循環頭開始，因為它們是尋找熱路徑的天然位置。在 TraceMonkey 中，循環頭（后向分支的目標）的字節碼很容易被檢測出來。當給定的循環頭執行了一定次數（當前實現中為 2 次）時，TraceMonkey 會開始一棵樹。開始一棵樹只是意味著開始記錄當前點和類型映射的跟蹤，并將該跟蹤標記為樹的根（root）。每棵樹都與一個循環頭和類型映射相關聯，因此給定的循環頭可能會有多棵樹。

關閉循環。跟蹤記錄可以以多種方式結束。

• 理想情況下，跟蹤到達循環頭時，其類型映射與入口（entry）相同，這稱為類型穩定（type-stable）的循環迭代。在這種情況下，跟蹤的結尾可以直接跳轉到開頭，因為所有值表示都與進入跟蹤所需的完全相同。跳轉甚至可以跳過通用的代碼，這些代碼會將當前跟蹤結束時的狀態復制到跟蹤的活動記錄中。
• 在某些情況下，跟蹤可能會到達具有不同類型映射的循環頭，這種情況有時會在循環的第一次迭代中觀察到。循環中的某些變量最初可能未定義，然后在第一次循環迭代期間將它們設置為具體類型。在記錄這樣的迭代時，記錄器無法將跟蹤鏈接回其自己的循環頭，因為它是類型不穩定的。相反，迭代以側出口終止，該出口始終會失敗并返回到解釋器。同時，使用新的類型映射記錄新的跟蹤。每次將額外的類型不穩定跟蹤添加到區域時，都會將其退出類型映射與所有現有跟蹤的入口映射進行比較，以防它們相互補充。通過這種方法，我們能夠覆蓋類型不穩定的循環迭代，只要它們最終形成穩定的平衡。
• 最后，跟蹤可能會在到達循環頭之前退出循環，例如因為執行到達 break 或 return 語句。在這種情況下，VM 只需退出跟蹤監視器即可結束跟蹤。

如前所述，我們可能會推測性地選擇在跟蹤上將某些 Number（雙精度）類型的值表示為整數。當我們觀察到 Number 類型的變量在跟蹤入口處包含整數值時，我們就會這樣做。如果在跟蹤記錄期間意外地為變量分配了一個非整數值，我們必須將變量的類型擴展為 Number，則記錄的跟蹤將會變得類型不穩定，因為它以整數值開始，但以雙精度值結束。這代表了錯誤的推測，因為在跟蹤入口處，我們將 Number 類型的值特化為整數，假設在循環邊（loop edge）我們會再次在變量中找到一個整數值，從而允許我們關閉循環。為了避免將來涉及此變量的推測失敗，并獲得類型穩定的跟蹤，我們注意到，所討論的變量有時在我們稱為“oracle”的建議數據結構中保存非整數值。

在編譯循環時，我們在將值專門化為整數之前咨詢 oracle。只有當 oracle 不知道有關該特定變量的不利信息時，才會對整數進行推測。每當我們意外地編譯出一個由于對 Number 類型變量的錯誤推測而導致類型不穩定的循環時，我們就會立即觸發新跟蹤的記錄，該跟蹤將基于現在更新的 oracle 信息以雙精度值開始，從而變為類型穩定。

擴展樹。側出?會通向循環中具有不同類型或表?的路徑，因此，為了完全覆蓋循環，VM 必須記錄從所有側出口開始的跟蹤。這些跟蹤的記錄方式與根跟蹤（root trace）非常相似：每個側出口都有一個計數器，當計數器達到熱度閾值時，開始記錄。記錄停止的方式與根跟蹤完全相同，使用根跟蹤的循環頭作為要達到的目標。

我們的實現不會在所有側出口處擴展。只有當側出口用于控制流分支并且側出口不離開當前循環時，它才會擴展。特別是，我們不想沿著通向外循環的路徑擴展跟蹤樹，因為我們希望通過樹嵌套在外跟蹤樹中覆蓋此類路徑。

下圖是一顆有兩個跟蹤（trace）的跟蹤樹（trace tree），一個主干跟蹤（trunk trace）和一個分支跟蹤（branch trace）。主干分支包含包含一個守衛（guard），分支跟蹤附著于該守衛上。分支跟蹤包含一個守衛，守衛失敗后會觸發 side exit。主干跟蹤和分支跟蹤都返回（loop back）到樹錨點（tree anchor），即蹤跡樹的起點。

3.3 黑名單（Blacklisting）

有時，程序會遵循或生成無法編譯成跟蹤的路徑，這通常是由于實現中的限制。TraceMonkey 目前不支持記錄任意異常的拋出和捕獲，之所以選擇這種設計權衡，是因為 JavaScript 中異常通常很少見。如果程序選擇大量使用異常，若我們反復嘗試記錄此路徑的跟蹤并反復失敗，這將突然產生懲罰性（punishing）的運行時開銷，因為每次觀察到拋出異常時我們都會中止跟蹤。

因此，如果熱循環包含始終失敗的跟蹤，則 VM 的運行速度可能會比基本解釋器還要慢得多：VM 反復花時間嘗試記錄跟蹤，但永遠無法運行任何跟蹤。為了避免這個問題，每當 VM 即將開始跟蹤時，它都必須嘗試預測它是否會完成跟蹤。

我們的預測算法基于將嘗試過但失敗的跟蹤列入黑名單。當 VM 無法完成從給定點開始的跟蹤時，VM 會記錄產生的失敗。VM 還設置了一個計數器，這樣它就不會嘗試記錄從該點開始的跟蹤，直到再經過幾次（在我們的實現中為 32 次）。此回退（backoff）計數器提供臨時條件，以防止跟蹤結束。例如，循環在啟動期間的行為可能與在穩定狀態執行期間的行為不同，在給定的失敗次數(在我們的實現中是2次)之后，VM將片段標記為黑名單，這意味著VM將永遠不會在該點再次開始記錄。

在實施這一基本策略后，我們觀察到，對于被列入黑名單的小循環，系統可能花費大量時間來查找循環片段并確定它已被列入黑名單。我們現在通過修補字節碼來避免該問題。我們定義了一個額外的無操作字節碼來指示循環頭。每次解釋器執行無操作的循環頭時，VM 都會調用跟蹤監視器。要將片段列入黑名單，我們只需將循環頭無操作替換為常規無操作，這樣解釋器將永遠不會再調用跟蹤監視器。

有一個相關問題我們尚未解決，當循環滿足以下所有條件時，就會發生這種情況：

• VM 可以為循環形成至少一個根跟蹤。
• 至少有一個熱 side exit，VM 無法完成跟蹤。
• 循環體很短。

在這種情況下，VM 將反復傳遞循環頭、搜索跟蹤、找到它、執行它，然后返回到解釋器。對于較短的循環體，查找和調用跟蹤的開銷很高，并且導致性能甚至比基本解釋器更慢。到目前為止，在這種情況下，我們已經改進了實現，以便 VM 可以完成分支跟蹤，但很難保證這種情況永遠不會發生。作為未來的工作，可以通過檢測和列入黑名單的循環來避免這種情況，對于這些循環，平均跟蹤調用在返回解釋器之前執行少量字節碼。

四、嵌套跟蹤樹

下圖a是嵌套循環的控制流圖，內層循環內有一個 if 語句；圖b是應用于嵌套循環的基本跟蹤樹編譯，內樹（t2）一旦沿其循環條件守衛退出，就會返回到外樹（t1）上。解釋器執行時，內循環（循環頭位于 i2）首先變熱，并且跟蹤樹在該位置生成根結點。例如，第一個記錄的跟蹤可能是通過內循環的循環，{$i_2、i_3、i_5、\alpha$}，$\alpha$符號用于表示跟蹤循環回到樹錨點（tree anchor）。

當執行離開內循環時，基本設計有兩個選擇。首先，系統可以停止跟蹤并放棄編譯外循環，這顯然是一個不理想的解決方案。另一個選擇是繼續跟蹤，在內循環的跟蹤樹內編譯外循環的跟蹤。

例如，程序可能在 $i_5$ 處退出并記錄包含外循環的分支跟蹤：{$i_5、i_7、i_1、i_6、i_7、i_1、\alpha$}。沿著該路徑執行一段時間后，程序可能會在 $i_2$ 處采用另一個分支，然后退出，此時又要記錄另一個包含外循環的分支跟蹤：{$i_2、i_4、i_5、i_7、i_1、i_6、i_7、i_1、\alpha$}。因此，外循環被記錄和編譯兩次，并且兩個副本都必須保留在跟蹤緩存（trace cache）中。一般來說，如果循環嵌套深度為 k，并且每個循環都有 n 條路徑（幾何平均值），則這種簡單的策略會產生 $O(n^k)$ 條跟蹤，這很容易填滿跟蹤緩存。

為了有效地執行帶有嵌套循環的程序，跟蹤系統需要一種用 native 代碼覆蓋嵌套循環的技術，而不會出現指數級的跟蹤重復。

4.1 Nesting Algorithm

關鍵見解是，如果每個循環都由它自己的跟蹤樹來表示，那么每個循環的代碼只能包含在它自己的樹中，并且外循環路徑不會被重復。另一個關鍵的事實是，我們不是在跟蹤可能具有不可歸約（irreduceable，這里指的是循環有兩個或者兩個以上的進入點，例如使用 goto 進去 for 或 while）控制流圖的任意字節碼，而是由編譯器為具有結構化（structured，可以對分支循環等進行歸約，golang、lua都是結構化的）控制流的語言生成的字節碼。因此，給定兩個循環邊，系統可以容易地確定它們是否嵌套以及哪個是內循環。利用這些知識，系統可以分別編譯內外循環，并使外循環的跟蹤調用內循環的跟蹤樹。

構建嵌套跟蹤樹的算法如下。我們完全按照基本跟蹤系統的方式從循環頭開始跟蹤，當我們退出循環時（通過將解釋器 PC 與循環邊給出的范圍進行比較來檢測），停止跟蹤。算法的關鍵步驟發生在我們記錄循環 $L_R$ 的跟蹤（R是正在記錄的循環）并到達另一個循環 $L_O$ 的頭部（O是R的內循環，有可能已經編譯跟蹤，也有可能沒有）時。請注意，$L_O$ 必須是 $L_R$ 的內循環，因為我們在退出循環時會停止跟蹤。

• 如果 $L_O$ 具有類型匹配的編譯跟蹤樹，我們將 $L_O$ 稱為嵌套跟蹤樹。如果調用成功，則我們將調用記錄在 $L_R$ 的跟蹤中。在將來的執行中，$L_R$ 的跟蹤將直接調用內跟蹤。
• 如果 $L_O$ 還沒有類型匹配的編譯跟蹤樹，我們必須先獲得它，然后才能繼續。為了做到這一點，我們只需中止（abort）記錄第一個跟蹤，跟蹤監視器將看到內循環頭，并立即開始記錄內循環。我們原則上可以只暫停外循環的記錄，而不是去中止，但這需要實現能夠同時記錄多個跟蹤，從而使實現變得復雜化，同時只能節省解釋器中的幾次迭代，所以沒有必要暫停。

如果嵌套中的所有循環都是類型穩定的，則循環嵌套不會產生重復。否則，如果循環嵌套深度為 k，并且每個循環都以 m 個不同的類型映射（幾何平均值）進入，那么我們將 $O(m^k)$ 個編譯最內層循環的副本。只要 m 接近 1，生成的跟蹤樹將是可處理的。

一個重要的細節是，對內跟蹤樹的調用必須像函數調用點（call-site）一樣：它必須每次都返回到同一點。嵌套的目標是使內循環和外循環獨立；因此，當調用內樹時，它必須每次都以相同的類型映射退出到外樹中的同一點。因為我們無法真正保證這個屬性，所以我們必須在調用后對其進行守衛，如果屬性不成立，則從側面退出（side exit）。內樹不返回同一點的一個常見原因是，如果內樹采取了一個新的 side exit，而它從未編譯過該跟蹤。此時，解釋器 PC 位于內樹中，因此我們無法繼續記錄或執行外樹。如果在記錄期間發生這種情況，我們將中止外跟蹤，以便讓內樹有機會完成增長（growing，內樹采取了新的 side exit，要將其編譯成跟蹤，所以內樹會生長出新的子結點）。然后，外樹的未來執行將能夠正確完成并記錄對內樹的調用。如果在執行外樹的編譯跟蹤期間發生內樹側退出，我們只需退出外跟蹤并開始在內樹中記錄新分支。

下圖展示了一個包含兩個嵌套循環的循環的控制流圖（左）及其對應的嵌套跟蹤樹（右）。外跟蹤樹調用兩個內嵌套跟蹤樹，并在它們的側出口位置放置守衛。

我們通過允許由于類型不匹配而無法自循環的跟蹤來處理類型不穩定的循環。隨著這種跟蹤的積累，我們嘗試連接它們的循環邊，以形成可以執行而無需因類型問題側退出到解釋器的跟蹤樹組。這對于嵌套跟蹤樹尤其重要，其中外部樹嘗試調用內部樹（或在這種情況下，是內部樹的森林），因為內部循環通常在初始迭代中具有未定義的值，這些值在第一次迭代后會變為具體值。

4.2 Blacklisting with Nesting

黑名單算法需要修改才能很好地與嵌套配合使用。問題是外循環跟蹤經常在啟動期間中止（abort，因為內樹不可用或從側面退出），這將導致它們很快被基本算法列入黑名單。

觀察到一個關鍵點，當外跟蹤由于內樹尚未準備好而中止時，這種情況可能只是暫時的。因此，只要我們能夠為內樹建立更多跟蹤，我們就不應該將此類中止計入黑名單。

在我們的實現中，當外層樹在內層樹上中止時，我們會像往常一樣增加外層樹的黑名單計數器，并停止編譯。當內層樹完成跟蹤時，我們會減少外層循環上的黑名單計數器，“原諒（forgiving）”外層循環先前的中止。我們還撤消了回退（backoff），以便外層樹可以在我們下次到達時立即開始嘗試編譯。

五、跟蹤樹優化

5.1 Optimizations

由于跟蹤的 LIR 是 SSA 形式，并且沒有連接點和 $?$ 節點（LuaJIT 的 IR 有PHI），因此某些優化易于實現。為了獲得良好的啟動性能，優化必須運行迅速，因此我們選擇了一小部分優化。我們將優化實現為流水線（pipelined）過濾器，以便它們可以獨立開啟和關閉，并且所有優化僅在跟蹤上進行兩次循環 pass：一次前向和一次后向。

每當跟蹤記錄器發出一條 LIR 指令時，該指令立即傳遞到前向流水線中的第一個過濾器。因此，前向過濾器優化在記錄跟蹤時執行。每個過濾器可以將每條指令不變地傳遞到下一個過濾器，寫入不同的指令到下一個過濾器，或者根本不寫入指令。例如，常量折疊過濾器可以將類似v13 := mul 3, 1000的乘法指令替換為常量指令v13 = 3000。

我們目前應用四個前向過濾器：

• 對于沒有浮點指令的ISA（指令集架構），軟浮點過濾器將浮點 LIR 指令轉換為整數指令序列。
• 常量子表達式消除（CSE）。
• 表達式簡化，包括常量折疊和一些代數等式（例如，a - a = 0）。
• 源語言語義特定的表達式簡化，主要是允許將 DOUBLE 替換為 INT 的代數等式。例如，LIR 將 INT 轉換為 DOUBLE 然后再轉換回來的指令將被此過濾器刪除。

當跟蹤記錄完成后，nanojit運行后向優化過濾器。這些過濾器用于需要后向程序分析的優化。當運行后向過濾器時，nanojit一次讀取一條 LIR 指令，并將讀取到的指令通過流水線傳遞。

我們目前應用三個后向過濾器：

• 無用數據棧存儲消除。LIR跟蹤編碼了許多存儲到解釋器棧位置的操作。但在退出跟蹤之前（由解釋器或其他跟蹤）這些值從未被讀取。因此，在下次退出之前被覆蓋的棧存儲是無用的。在未來退出時位于解釋器棧頂部之外的位置的存儲也是無用的。
• 無用調用棧存儲消除。這與上述優化相同，但應用于用于函數調用內聯的解釋器調用棧。
• 無用代碼消除。這會消除存儲到從未使用的值的任何操作。

當一條LIR指令成功從后向過濾器管道中讀取（pulled）后，nanojit的代碼生成器會為其生成本機機器指令。

5.2 Register Allocation

我們使用一個簡單的貪婪（greedy，不需要考慮整體，局部最優即可）寄存器分配器，它對跟蹤 LIR 進行單次反向遍歷（這個過程與機器指令生成器集成）。當分配器處理類似 $v_3=add{v}_1,v_2$ 的指令時，它已經為 $v_3$ 分配了一個寄存器。如果 $v_1$ 和 $v_2$還沒有被分配寄存器，分配器會為每個未分配的值分配一個空閑寄存器。如果沒有空閑寄存器，則會選擇一個值進行溢出（spilling）。我們使用一種選擇“最舊的”寄存器中保存的值的啟發式（heuristic）方法來決定哪個值進行溢出。

啟發式方法考慮在當前指令之后立即將寄存器中的值 $v$ 的集合 R 進行溢出。設 值 $v_m$ 為每個值 $v$ 所引用的當前指令之前的最后一條指令。然后，啟發式方法選擇 $v_m$ 最小的 $v$。這種做法的動機是，通過單次溢出釋放一個寄存器，并盡可能長時間地保持該寄存器空閑。

如果在這個點需要溢出值 $v_s$，我們會在當前指令之后生成恢復代碼。相應的溢出代碼在最后一次使用 $v_s$ 的位置之后生成。分配給 $v_s$ 的寄存器在之前的代碼中被標記為空閑，因為這個寄存器現在可以自由使用，而不會影響后續代碼。

六、Implementation

為了證明我們方法的有效性，我們為 SpiderMonkey JavaScript 虛擬機實現了一個基于跟蹤的動態編譯器。SpiderMonkey 是嵌入在 Mozilla 的 Firefox 開源 Web 瀏覽器中的 JavaScript VM，全球有超過 2 億用戶使用它。SpiderMonkey 的核心是用 C++ 實現的字節碼解釋器。

在 SpiderMonkey 中，所有 JavaScript 值都由 jsval 類型表示。jsval 是一個機器字長（machine word），其中最多 3 個最低有效位是類型標記（ type tag），其余位是數據。jsvals 中包含的所有指針都指向按 8 字節邊界對齊的 GC 控制塊。

JavaScript 對象的值是名稱（name，是個字符串）到任意值的映射。它們在 SpiderMonkey 中以兩種方式的其中一種表示。

• 大多數對象由一個共享的結構描述表示，稱為對象形狀（object shape），它使用哈希表將屬性名稱映射到數組索引。我對描述的這個結構的理解是：array 存放對象，對象在 array 中的 index 所謂 hash 的 value，對象的 name 作為 hash 的key，這樣便可以實現對對象的快速訪問。
• 對象保存了指向其形狀（shape）的指針，以及保存自身屬性值的數組。具有大量獨特屬性名稱集的對象會直接將它們的屬性存儲在哈希表中。

垃圾收集器是一種精確、non-generational、stop-theworld的標記清除（mark-and-sweep）收集器。

在本節的其余部分，我們將討論 TraceMonkey 實現的關鍵領域。

6.1 Calling Compiled Traces

編譯后的跟蹤信息存儲在一個跟蹤緩存（trace cache）中，通過解釋器的 PC 和類型映射進行索引。跟蹤信息被編譯后，可以使用標準的 native 調用約定（例如x86上的FASTCALL）作為函數調用。

解釋器必須命中循環邊（loop edge）并進入監視器才能首次調用 native 跟蹤。監視器計算當前類型映射，檢查跟蹤緩存中是否存在與當前PC和類型映射對應的跟蹤信息，如果找到，就執行該跟蹤信息。

為了執行跟蹤，監視器必須構建一個跟蹤活動記錄（ trace activation record），包含導入的局部變量和全局變量、臨時堆棧空間以及 native 調用的參數空間。局部和全局變量值隨后從解釋器狀態復制到跟蹤活動記錄中。然后，跟蹤信息像正常的C函數指針一樣被調用。

當跟蹤調用返回時，監視器恢復解釋器狀態。首先，監視器檢查跟蹤退出的原因，并在需要時應用黑名單。然后，根據需要彈出或合成解釋器的 JavaScript 調用堆棧幀。最后，將導入的變量從跟蹤活動記錄復制回解釋器狀態。

至少在當前的實現中，這些步驟有一定的運行時間成本，因此盡量減少解釋器與跟蹤之間的轉換是提升性能的關鍵。我們的實驗（見下圖）表明，對于可以很好地跟蹤的程序，這種轉換發生的頻率較低，因此對總運行時間的影響不大。在一些程序中，由于中止操作阻止系統記錄熱點側退出的分支跟蹤，這種成本可能會上升到總執行時間的10%。

6.2 Trace Stitching

從跟蹤切換到分支跟蹤（側出口處產生）時，可以避免通過監視器調用跟蹤的成本，這種特性被稱為跟蹤拼接（trace stitching）。在側出口（side exit）處，退出的跟蹤只需要將活躍（ live，對照活躍變量來理解）的寄存器攜帶值寫回其跟蹤活動記錄。在我們的實現中，具有相同類型映射的跟蹤活動記錄布局是相同的，因此跟蹤活動記錄可以立即被分支跟蹤重用。

在具有分支跟蹤樹且跟蹤較小的程序中，跟蹤拼接有明顯的成本。雖然寫入內存然后很快讀取回來的操作預計會有很高的L1緩存命中率，但對于小型跟蹤來說，增加的指令數量有明顯的成本。此外，如果寫入和讀取在動態指令流中非常接近，我們發現當前的x86處理器通常會產生6個周期或更多的延遲（例如，如果指令使用不同的基寄存器且其值相同，處理器可能無法立即檢測到地址相同）。

替代方案是重新編譯整個跟蹤樹，從而實現跨跟蹤的寄存器分配。缺點是樹的重新編譯時間隨著跟蹤數量的增加呈二次方增長。我們認為，每次添加分支時重新編譯跟蹤樹的成本將是不可承受的。這個問題可以通過僅在特定點或僅對非常熱（hot）和穩定的樹進行重新編譯來緩解。

未來，多核硬件預計將會普及，使后端（background）對樹重新編譯變得具有吸引力。在一個密切相關的項目中，后端重新編譯在具有許多分支跟蹤的基準測試中實現了高達1.25倍的加速。我們計劃將這一技術應用于TraceMonkey作為未來的工作。

6.3 Trace Recording

跟蹤記錄器（trace recorder）的工作是發射（emit）與當前運行的解釋器字節碼（bytecode）跟蹤具有相同語義的 LIR。一個好的實現應該對非跟蹤解釋器性能影響較小，并為實現者提供維護語義等價的便捷方式。

在我們的實現中，對解釋器的唯一直接修改是在循環邊（loop edge）調用跟蹤監視器（trace monitor），即在循環每次都會經過的地方加個熱點計數器（counter）。在我們的基準測試結果中（見 6.1 的圖），在監視器中花費的總時間（包括所有活動）通常少于5%，因此我們認為解釋器的影響要求得到了滿足。遞增循環命中計數器是昂貴的，因為這需要我們在跟蹤緩存（trace cache）中查找循環，但我們已經調整了我們的循環，使其在第二次迭代時迅速變熱并進行跟蹤。命中計數器的實現可以改進，這可能會給我們帶來小幅的整體性能提升，并且在調整熱度閾值方面提供更多的靈活性。一旦一個循環被列入黑名單，我們將永遠不會為該循環調用跟蹤監視器（見 3.3 節）。

記錄通過指針交換活動（activated），該指針設置解釋器的調度表（ dispatch table）以調用每個字節碼的單個“中斷（interrupt）”例程。中斷例程首先調用一個特定字節碼（bytecode-specific）的記錄例程（recording routine）。然后，在必要時關閉記錄（如，跟蹤結束）。最后，它跳轉到標準的解釋器字節碼實現。一些字節碼對類型映射有影響，這些影響在執行字節碼之前無法預測（例如，調用String.charCodeAt，如果索引參數超出范圍，則返回整數或NaN）。對于這些情況，我們安排解釋器在執行字節碼后再次調用記錄器。由于這種鉤子（hook）相對較少，我們將它們直接嵌入解釋器，并添加一個運行時檢查以查看記錄器當前是否處于活動狀態。

雖然將解釋器與記錄器分離減少了單個代碼的復雜性，但也需要仔細的實現和廣泛的測試以實現語義等價。在某些情況下，實現這種等價性是困難的，因為 SpiderMonkey 采用了 fat-bytecode（我理解是在字節碼的編碼中嵌入更多的信息）設計，這被發現對純解釋器性能有益。

在 fat-bytecode 設計中，單個字節碼可以實現復雜的處理（例如，getprop字節碼，它實現了完整的 JavaScript 屬性值訪問，包括緩存和密集數組訪問的特殊情況）。 fat-bytecode 有兩個優點：較少的字節碼意味著較低的調度成本，較大的字節碼實現為編譯器提供了更多優化解釋器的機會。

fat-bytecode 對TraceMonkey來說是個問題，因為它們需要記錄器以相同的方式重新實現相同的特殊情況邏輯。此外，這些優點被削弱了，因為：

• 在編譯的跟蹤中調度成本完全消除；
• 跟蹤僅包含一個特殊情況，而不是解釋器的大量代碼；
• TraceMonkey在運行解釋器上花費的時間更少。

我們解決這些問題的一種方法是將某些復雜字節碼在記錄器中實現為簡單字節碼序列。以這種方式表達原始語義并不太困難，記錄簡單字節碼要容易得多。這使我們能夠保留 fat-bytecode 的優點，同時避免它們在跟蹤記錄中的一些問題。這對于回歸解釋器的 fat-bytecode 特別有效，例如，通過調用對象上的已知方法將對象轉換為原始值，因為它允許我們內聯此函數調用。

需要注意的是，我們僅在記錄期間將較大（fat）的操作碼分割為較薄（thinner）的操作碼。在純粹解釋執行時（即，已被列入黑名單的代碼），解釋器直接且有效地執行較大（fat）的操作碼。

6.4 Preemption

與許多虛擬機一樣，SpiderMonkey需要定期搶占（Preemption）用戶程序。主要原因是防止無限循環的腳本鎖定主機系統，還有就是要安排GC。

在解釋器中，這通過設置一個“立即搶占（preempt now）”標志來實現，該標志在每次向后跳轉時都會被檢查。這一策略被延續到 TraceMonkey：虛擬機在每個循環邊處插入一個搶占標志的守衛。我們測量了大多數基準測試，這個額外的守衛導致的運行時間增加不到1%。在實際操作中，這個成本僅在具有非常短循環的程序中是可檢測的。

我們測試并拒絕了一個解決方案，該方案通過將循環邊編譯為無條件跳轉并在需要搶占時將跳轉目標修補為退出例程來避免守衛。這種解決方案可能使正常情況下略微更快，但搶占變得非常慢。實現起來也非常復雜，尤其是在搶占后嘗試重新啟動執行時。

6.5 Calling External Functions

像大多數解釋器一樣，SpiderMonkey擁有一個外部函數接口（FFI，foreign function interface），允許它調用C內建函數和主機系統函數（例如，網頁瀏覽器控制和DOM訪問）。FFI對于 JS 可調用函數有一個標準的簽名，其關鍵參數是一個裝箱值（boxed values）數組。使用FFI調用的外部函數通過解釋器API與程序狀態交互（例如，從參數讀取屬性）。還有一些不使用FFI但以相同方式與程序狀態交互的解釋器內建函數，例如用于迭代器對象的 CallIteratorNext 函數。TraceMonkey必須支持這個FFI，以加速在熱點循環中與主機系統交互的代碼。

從 TraceMonkey 調用外部函數可能會很困難，因為跟蹤不會在退出前更新解釋器狀態。特別是，外部函數可能需要調用堆棧或全局變量，而它們可能是過時的。

對于過時的調用堆棧問題，我們重構了一些解釋器API實現函數，以按需重新生成解釋器調用堆棧。我們開發了一個C++靜態分析，并注釋了一些解釋器函數，以驗證在需要使用調用堆棧時調用堆棧已被刷新。為了訪問調用堆棧，函數必須被注釋為 FORCESSTACK 或 REQUIRESSTACK。這些注釋也需要用于調用 REQUIRESSTACK 函數，這些函數被認為是遞歸訪問調用堆棧。FORCESSTACK 是一個可信注釋，僅應用于5個函數，表示該函數刷新調用堆棧。REQUIRESSTACK 是一個不可信注釋，表示該函數只能在調用堆棧已被刷新時調用。

同樣，我們檢測主機函數何時嘗試直接讀取或寫入全局變量，并強制當前運行的跟蹤側退出（side exit）。這是必要的，因為我們在跟蹤執行期間將全局變量緩存并解箱（unbox）到活動記錄中。由于主機函數很少訪問調用堆棧和全局變量，這些安全機制不會顯著影響性能。

另一個問題是外部函數可以通過調用腳本重新進入解釋器，而這些腳本可能再次需要訪問調用堆棧或全局變量。為了解決這個問題，我們讓虛擬機在編譯的跟蹤運行時每當解釋器重新進入時設置一個標志。每次調用外部函數時都會檢查此標志，如果已設置，則在返回外部函數調用后立即退出跟蹤。有許多外部函數很少或從不重新進入，它們可以毫無問題地被調用，只有在必要時才會導致跟蹤退出。

FFI的裝箱值（boxed values）數組要求有性能成本，因此我們定義了一個新的FFI，允許C函數用其參數類型進行注釋，這樣跟蹤器可以直接調用它們，無需不必要的參數轉換。目前，我們不支持直接從跟蹤調用本地屬性獲取和設置重寫函數或DOM函數。這些功能的支持計劃在未來工作中實現。

6.6 Correctness（正確性）

在開發過程中，我們能夠使用現有的 JavaScript 測試套件，但大多數套件并未針對跟蹤虛擬機設計，且包含的循環很少。

一個對我們幫助很大的工具是Mozilla的 JavaScript 模糊測試器 JSFUNFUZZ，它通過嵌套隨機語言元素生成隨機 JavaScript 程序。我們修改了 JSFUNFUZZ，使其生成循環，并更加深入地測試我們懷疑會暴露實現缺陷的某些結構。例如，我們懷疑TraceMonkey在處理類型不穩定的循環和大量分支代碼時存在錯誤，經過專門修改的模糊測試器確實揭示了幾個回歸問題，我們隨后進行了修正。