二進位翻譯( binary translation )有沒有成熟的現實應用？請介紹一下實現方式與性能瓶頸。?

01-24

binary translation成熟的現實應用很多。

Mac當年從Motorola 680x0架構過渡到Power架構的時候，Apple為了兼容老硬體架構上的應用，就搞了個模擬器，裡面包括從68k翻譯到PowerPC指令集的translator
十多年前曇花一現的PS1模擬器VGS，有完成度相當高的MIPS到x86 translator。順便提一句，VGS作者之一的Aaron Giles業餘時間也是MAME的主力開發人員。後來所在公司Connectix做了另外一款產品相信大家都聽說過：Virtual PC。最後被微軟收購了。
從PS1開始的主機模擬器為了提高性能通常都需要做binary translation，模擬器界有時也稱之為dynrec (dynamic recompiler)。
Intel在Android手機上推x86架構，雖然也有Android官方支持，但為了兼容更多隻提供ARM JNI庫的應用，也不得不搞了Houdini來做ARM到x86指令集的翻譯。

binary translator本身並不是性能的保證。寫得糟糕的translator，生成代碼的性能可能還趕不上合理優化的解釋器。我本人不是編譯器方面的專家，但曾經勉強寫過一個紅白機模擬器使用的6502(6527) CPU指令集到ARM的translator，能夠正常運行遊戲。在簡單翻譯不作優化的情況下，確實當年在Pocket PC上跑起來比之前的解釋器還慢一點。原因也不難理解，naive的translator雖然可以生成能夠順序執行的代碼，相比解釋器能省下花在反覆read-decode-dispatch上的開銷，但生成指令的大小也是暴漲，和解釋器相比完全不在一個級別上，對CPU的指令cache完全是折磨。特別是6502這種8位opcode的指令集，解釋器寫出來短小精幹，本身運行速度已經很快了。

binary translation的性能優化有些有趣的地方。和編譯器生成的中間代碼不同，機器代碼特別是算術運算代碼，通常都有影響標誌寄存器這麼一個副作用。以紅白機的6502為例，帶進位加法指令ADC會影響的標誌位包括N(符號位), V(溢出位), Z(零位), C(進位位) (喂)等等等等，而這些對標誌寄存器的修改很多時候並不會用到，就被後續指令覆蓋了。簡單的一對一翻譯就會生成大量無意義重複的標誌寄存器更新代碼，需要優化消除掉。

然後還有自修改代碼和錯位重用代碼這兩個毒瘤……所以難以避免有時候要fallback到解釋器上。

然後對遊戲主機模擬器而言還要計算cycles，考慮CPU和其他部件的時序同步，情況更加複雜。

前陣子剛好看過一篇Statically Recompiling NES Games into Native Executables with LLVM and Go，作者很強，用Golang + LLVM寫了一個靜態的紅白機遊戲到x86的翻譯器。文章有點長，值得一讀。順便提一句，對於自修改代碼和錯位重用代碼，作者也是不得不靠在運行時回退到內嵌的解釋器來處理。

Binary Translation是一個非常大的課題，如果要說得詳細了可以寫一本書。在這裡我們僅僅討論它的皮毛，也僅僅是大致勾畫出二進位翻譯器的運行結構。解釋有錯誤的地方還請各位斧正。

二進位翻譯器在業界已然有不少產品使用了，這裡只是簡單介紹幾個。BT之中最著名的可能是Qemu了。還有大家手中各式各樣的遊戲機模擬器也屬於BT，其中，Dolphin模擬器是最成熟的，現在最新的Dolphin已不再是解釋執行模擬器了，它已然加入了JIT優化。Intel曾開發過在X86 Android上運行ARM Android app的Houdini，但似乎由於性能問題已不再投入。在中國，計算所胡偉武他們正在做龍芯支持X86的工作（Zhang et al.

HERMES: A Fast Cross-ISA Binary
Translator with Post-Optimization, CGO"15），也相當不錯。

系統地講，現有的virtual machine在三個層次上：

機器層面，比如遊戲機模擬器
系統層面，比如X86 Macintosh運行Power架構的Mac app
應用層面，比如JVM

一般來說需要Binary translation（以下簡稱BT）的地方是guest代碼與host機器架構不同的時候（也可以是相同的架構，但那樣的翻譯大多出於安全或優化而言的，如著名HP Dynamo：Bala et al. Dynamo: A Transparent Dynamic Optimization System PLDI"2000）。

下面說說常用的二進位轉換的方法和需要注意的問題。BT在執行的過程中需要不做任何假定地考慮：

馮諾依曼結構計算機的數據和指令不分家，BT如何在執行的過程中區分哪些是數據，哪些是指令呢？
對會自我修改自我引用的的程序如何處理？
如何處理間接跳轉語句？
等等等等（一時半會想不起來）...

二進位轉換分兩種，一種是靜態轉換，另一種是動態轉換（JIT）。靜態轉換就是將guest machine的二進位可執行代碼翻譯成host machine的可執行代碼，動態轉換就是邊執行邊翻譯。對於靜態轉換來說，由於沒有運行時信息，一個不可能解決的問題是在編譯時如何知道間接跳轉的目標地址。如果需要完美地轉換，一個解決辦法是自帶一個解釋器，當程序跳轉到未被翻譯指令處時，就啟動解釋器引擎。當然，這樣其實還是需要即時轉換的; 另一個辦法比較極端，因為我們不知道哪些地址是指令，哪些是數據，我們只能假定所有地址都可以是指令來轉換。如果是特定用途的BT，不一定需要這麼嚴格的要求。

對於動態轉換來說，翻譯間接跳轉成為了可能。由於JIT的特性，對自我修改的程序也能夠處理了。以一個動態Binary Translator來說，一種實現方式的偽代碼是這樣的：

1. 程序執行流交給BT，BT獲得跳轉目標地址或入口地址(設名字為tgt) 2. BT以tgt所指指令為起始收集接下來的每一條指令，直到找到需要翻譯的一段guest指令塊 3. BT對在第2步獲得的block分析，優化，生成host代碼 3.1 對每一條跳轉語句，如果目標地址next_tgt已經被轉譯則更改跳轉地址至已轉譯地址 3.2 如果next_tgt未被轉譯過，則對該跳轉語句生成返回第1步的函數調用，並tgt=next_tgt 3.3 對間接跳轉，同樣生成一段返回BT的調用。BT查表得到next_tgt之後跳轉至第1步 5. BT將生成的block代碼段登記在自己系統里 6. 跳轉到生成的host代碼執行

在第二步收集的指令塊的方式決定了指令塊的結構，同時也決定了第3步能做哪些優化。通常要求生成的指令塊是一個super basic block。SBB與basic block不同的地方在於SBB允許指令流在SBB的中間跳轉出去，但因為它和BB一樣入口唯一中間沒有跳轉，仍然保持了塊內各指令間的依賴關係，故適合做小範圍的優化。
當發現程序有自我修改的行為的時候，BT需要將被改寫的指令塊重新轉譯。通常做法是在被改寫的指令塊頭插入跳轉語句轉入新生成的指令塊。BT還需要同時修改guest code，以防止自引用的代碼出錯。

性能與優化：

不要指望BT的性能會非常好，畢竟它是在跑一個虛擬機。一個na?vely寫成的BT要是有host machine的四分之一性能就算很不錯了。經過優化後，一般可以達到三分之一。Bansal et al.號稱他們用super-optimization可以達到平均三分之二的性能（Binary Translation Using Peephole Superoptimizers OSDI"08）。

BT的一個重要優化是用 Shadow Stack來預測返回指令的跳轉地址，這是BT overhead的一個非常大的一塊。注意到返回指令雖然是一條間接指令，通常是要用runtime helper來查表搜索跳轉地址的，開銷非常大。注意到程序運行時的call stack通常都保存得很完整，每一個函數結束時返回的地址通常都是caller的下一條指令。利用這一個穩定的性質，我們可以用一個緩存棧保存程序調用棧的返回地址。那麼下一次轉譯的返回指令就不需要再用helper查找跳轉地址了。原理如下：

對每個call jump指令，在跳轉的同時向ShadowStack這個BT維護的棧中壓入一個二元組，元素分別為guest的返回地址和host的返回地址（guestPC+1, hostPC+1）。
對每個return jump指令，查找SS棧頂的二元組。如果guestPC+1正好是返回地址寄存器RA的值，直接跳轉到hostPC+1; 否則彈出SS棧頂搜索下一個。如果超過一定次數或者SS棧為空則跳轉到helper查表。

針對不同的guest architecture還可以進行如下的性能優化（僅舉例）：

像ARM這樣的指令集帶有PC relative load，即類似ld r1,10(pc)，可以簡化。但要考慮程序的自我修改。
ARM指令都可以以零成本生成一個算術運算結果的status flag，即NZCV flags，用於比較判斷。如果host是像龍芯MIPS這樣自身不具有狀態寄存器的架構，維護NZCV的開銷可以算大頭，需要將不需要的狀態計算刪除。
如果host machine的寄存器數量低於guest machine（如X86模擬ARM），還需要做合理的register mapping，減少不必要的context switching開銷。

至於其餘的代碼生成優化，大家可以看上文提到的幾篇paper。Virtual Machines: Versatile Platforms for Systems and Processes這本書也是很好的資料。

各類虛擬機、模擬器就不用說了，valgrind這應該算成熟的現實應用了。

Intel confronts a big mobile challenge: Native compatibility

Intel 的 CPU 都是把 x86 指令翻譯（分解）成 RISC 指令再執行的，我想這個應該是二進位翻譯行之有效的最佳例子。

龍芯號稱也有這個能力。

至於其他處理器為什麼不支持，要麼是沒必要，要麼是沒授權。比如龍芯就不能翻譯 x86，因為 Intel 不允許。

x86 的硬體虛擬化是2006年才出現的，而x86虛擬化老大VMware是98年成立的，在x86硬體虛擬化出現之前所有VMware的產品不管是桌面產品還是伺服器產品就是用的BT技術, 所以BT技術絕對是成熟的。不僅如此，在伺服器虛擬化領域已經是一項過時的技術了。想了解原理可以參考虛擬機 (豆瓣)

qemu 比較好移植

現在的各種第三方android模擬器，包括海馬玩、夜神等，都是運行在x86的模擬器上，性能比運行在arm模擬器上好很多。這些模擬器為了支持很多包含arm指令的二進位文件，利用了一種二進位翻譯技術，叫arm translator。不然的話很多遊戲和軟體用不了