下一個目標

回想多數高階語言會先編譯到中介表示法（intermediate representation, IR），再進一步編譯到組語。 接下來兩週我們要學 Hack 的 IR——Hack VM—— 並寫一個 VM 翻譯器（VM translator）把 Hack VM 程式碼 編譯成組語。

為什麼要用 IR？

IR 讓編譯工作乾淨地切成三段：

許多語言的編譯器可以（也確實）共用同一個 IR： 基於既有 IR 做新編譯器時只需要寫前端； ISA／微架構更新時只需要改後端—— 這些工作（大致上）只要做一次，而不是每個編譯器各做一次。

真實世界的 IR

• LLVM：從零設計的通用開源 IR，力求適用於盡可能多的語言。 多數新編譯器都做成 LLVM 的前端。

• GIMPLE：GCC（最重要）的 IR。GCC 在 C 與 C++ 效能上與 LLVM 系編譯器不相上下，且對老舊架構的支援明顯更強。

• JVM：Java 的 IR。Java 完全不用編譯器後端， 而是跑一個 VM 直接執行 IR——保證了可攜性，但犧牲效能。

虛擬機（Virtual Machines）

回想 Hack 中，組語、ISA 與微架構的設計緊緊綁在一起： 決定支援哪些指令時，得在三者間妥協—— 寫組語時什麼有用、什麼塞得進 16 位元的字、什麼在微架構容易實作。

另一種虛擬機

本課程關心的是 IR 的 VM（多半永遠不會做成真硬體）。 但真實架構的 VM 也很常用，用途例如： 執行不受信任的軟體（隔離真正的作業系統與硬體）； 多台實體機器跑同步的虛擬伺服器副本以便故障轉移； 一台實體超級電腦跑多個 VM 做分散式高效能運算（AWS、BC4）； 從外部分析運行中的作業系統（找安全漏洞）； 跑其他架構的原生軟體（如行動裝置開發測試）。 （投影片還挖苦了某遊戲引擎的按安裝收費政策—— VM 可以自動大量安裝來灌爆帳單，這正是該政策荒謬之處。） 在編譯器情境以外聽到「虛擬機」，多半指的是這種！

Hack VM 的目標與非目標

非目標（要到課程最後用高階語言 Jack 才實現）： 人類友善的程式碼（變數名、for/while 迴圈——VM 程式碼 本來就該由編譯器產生）；運算式的直接寫法； 具型別的變數（字串、陣列）；抽象資料型別（C 的 struct）； 執行期記憶體配置（C 的 malloc）。

Hack VM I：結構、算術與邏輯

堆疊機與堆疊複習

追蹤 push(2)、push(5)、pop()、push(4)、push(42)、pop()：

（JVM 也是堆疊機，所以這樣做有充分的現實理由！）

虛擬記憶體

在組語中我們用實體記憶體——每個位址就是送往 實體晶片上實體閂鎖的邏輯訊號（ROM 或 RAM）。 IR 應該可攜，所以改用虛擬記憶體： 行為像實體記憶體（每個位址存一個字）， 但不管每個位址實際存放在哪裡。 （ISA 相依的）VM 翻譯器會在編譯時把虛擬位址映射到實體位址。

Hack VM 有 8 個獨立的虛擬記憶體庫， VM 翻譯器會把它們映射到底層 RAM 的不同段（segment， 連續區塊）。本章先看兩個：

• local：區域變數的通用儲存空間；

• constant：在每個 15 位元位址 \(i\) 存放常數 \(i\)。 這塊「記憶體」唯讀，不對應任何實體 ROM 或 RAM ——它是把常數帶上堆疊的語法手段。

語法：push 與 pop

投影片的完整追蹤範例（local 33..37 初值 451、1138、0、0、13）：

堆疊運算

所有算術運算都經由堆疊進行。例如 add （無引數）：彈出堆疊頂兩個值、相加、把結果推回堆疊。 其他運算的做法與語法完全相同。 不能直接對 local 裡的兩個值相加—— 必須先推上堆疊。

邏輯比較同理：eq 彈出兩個值、判斷是否相等、把結果推回。

完整範例：複合邏輯測試

設 local 3 \(= 64\)、local 5 \(= 256\)。 要測試 \((\texttt{local 3} > 42)\) and \((\texttt{local 3} < \texttt{local 5} - 100)\)： 分別測試兩個條件、再 and 起來 （記住 and／or／not 既是逐位元也是邏輯運算！）。

push local 3      // 64
push constant 42
gt                // 64>42: true
push local 3      // 64
push local 5      // 256
push constant 100
sub               // 256-100=156
lt                // 64<156: true
and               // true

注意「先算 \(\texttt{local 5} - 100\) 留在堆疊上、再 lt」 的模式：子運算式的結果自然地留在堆疊頂， 等著被外層運算取用——這正是堆疊機讓運算式編譯變乾淨的原因。

Hack VM II：分支與記憶體

標籤與 goto

Hack VM 怎麼處理迴圈與條件？跟組語一樣——用跳躍。 現在改叫 goto，因為它們不再只對應單一一條機器碼指令。

if-goto 的用法對應組語的 D;JNE，差別是： 比較對象是堆疊頂而不是 \(D\)； 且語言內建了真正的邏輯運算子 gt、eq、lt、and、or、 not 來取代各種跳躍條件—— 不再需要七種 jump，一種 if-goto 搭配比較運算就夠。

pointer 與 this：執行期定址

用 local 只能存取執行前就知道的位址， 這會造成問題：假設記憶體裡存了一個陣列，想取它的第 local 0 個元素——但 push local (local 0) 不是合法 VM 碼！

push constant 2048  // 0x0800
push local 0
add                 // 堆疊：(local 0) + 0x0800
pop pointer 0       // this i 現在映射到 (local 0)+0x0800+i
push this 0         // 陣列第 (local 0) 個元素上堆疊

I/O 與 that

I/O 可以用同一招存取螢幕 \(RAM[\texttt{0x4000}\)–\(\texttt{0x5FFF}]\) 與鍵盤 \(RAM[\texttt{0x6000}]\)……對吧？ 可以，但惱人的是不能用 this。 之後會看到 this 在編譯抽象資料型別（如 C 的 struct）時 有特殊角色，所以不能映射到任意記憶體段（第 11 週就懂了）。 目前只需知道：

八個虛擬記憶體段

已見過 local、constant、this、 that、pointer。剩下三個：

• argument：函式呼叫開始時持有該次呼叫的引數， 不可寫入。（詳見下週。）

• static：內容跨函式呼叫持續存在 （之後用於高階語言的 static 與全域變數）。

• temp：行為與 local 完全相同但小得多， 作為高階語言編譯器編譯單一指令時的「工作空間」， 不用打擾 local 的內容。

（對照：local 在函式呼叫開始時是空的， 函式返回時內容被丟棄。）

投影片同時把 fill.asm（按鍵時全螢幕變白、 否則全黑）改寫成 fill.vm 做對照—— 用 that 掃描螢幕記憶體、用 if-goto 做迴圈， 行數遠少於組語版。

實作 Hack VM 翻譯器

Hack VM 的權杖

沒有新東西——你已經知道詞法器怎麼運作， 所以這部分作業已經幫你寫好了。 組譯器在詞法階段建了標籤符號表；這裡不需要 （除非想做好錯誤處理，而我們不想）。為什麼？ 因為 VM 的 label X 可以直接翻譯成組語的 (X)、goto X 翻成 @X + 0;JMP ——把「解析標籤位址」的工作下放給組譯器就好， VM 翻譯器根本不必知道標籤在哪。

Hack VM 的文法

Hack VM 的文法有很多種寫法，以下是其中一種：

這其實比 Hack 組語簡單得多——它是 LL(1) 文法： 每個 \(\textcolor{ntred}{\langle\text{\itshape instruction}\rangle}\) 怎麼解析，看第一個權杖就知道。 （對照：組語因為 DM=M+D 需要 LL(2)。） 難的部分其實是把 VM 指令翻譯成組語！

配置記憶體：基底位址與位移

把虛擬記憶體映射到實體記憶體（配置記憶體） 的一般做法與 this/that 相同。 假設要把 local 映射到實體記憶體： 選一個 RAM 位址（例如 300），然後 local 0 \(\mapsto RAM[300]\)、 local 1 \(\mapsto RAM[301]\)、……、 local \(k \mapsto RAM[300 + k]\)。

硬體限制與段長度

Hack VM 的八個段各有 64KB 記憶體（32,768 個 16 位元字）， 堆疊還可以無限高；但 Hack CPU 總共只支援 64KB—— 總得有取捨。（這不是 Hack VM 特有的： 多數計算模型都假設無限儲存——圖靈機有無限長的紙帶、 C 程式對 malloc 總量沒有硬上限。）

解法：給每個段一個長度，禁止存取超過長度的區域。 例如給 local 長度 5，就只允許 local 0 到 local 4； 「local 5 的位置」就能拿去當（例如） argument 的基底位址。

Hack 的記憶體配置慣例

這些細節是我們這個 Hack VM 實作特有的 （不是 Hack VM 本身的一部分，但 Nand2tetris 的 VM 模擬器假設它們）。 組語那些還沒解釋的神祕關鍵字（除了 SP） 全都是存放段基底位址的變數：

• local 的基底位址存在 \(RAM[1]\) = LCL；

• argument 的基底位址存在 \(RAM[2]\) = ARG；

• pointer 固定配置在基底 3、長度 2： pointer 0（= this 的基底）就是 \(RAM[3]\) = THIS； pointer 1（= that 的基底）就是 \(RAM[4]\) = THAT；

• temp 固定配置在基底 5、長度 8；

• static 固定配置在基底 16、長度 240。 編譯 Foo.vm 時，static 5 應映射到 組語變數 Foo.5（解釋見下週！）；

• constant 不出現在實體記憶體。

目前假設 \(RAM[1\text{--}4]\) 在執行開始時已被初始化成合理的值 （提供的測試腳本會做這件事！）。

實作堆疊

堆疊也配置固定段：基底 256、長度 1792。 堆疊頂再往上一格的位址存在 \(RAM[0]\) = SP （Stack Pointer）。

嚴格說 local 與 argument 也會存成堆疊的 子段——但這週先不用擔心！

延伸補充：VM 指令的組語翻譯範例

投影片說「難的是翻譯本身」但把細節留給作業。 以下是三個代表性翻譯（標準 Nand2tetris 做法）， 展示每條 VM 指令如何展開成一段組語：

@7
D=A      // D = 7
@SP
A=M      // A = SP（堆疊頂上一格）
M=D      // RAM[SP] = 7
@SP
M=M+1    // SP++

@LCL
D=M      // D = local 的基底位址
@2
D=D+A    // D = 基底 + 2
@R13
M=D      // R13 = 目標位址
@SP
M=M-1    // SP--
A=M
D=M      // D = 彈出的值
@R13
A=M
M=D      // RAM[基底+2] = 值

@SP
M=M-1    // SP--
A=M
D=M      // D = y（先彈出）
@SP
M=M-1    // SP--
A=M
M=D+M    // RAM[SP] = x + y（結果原地放回）
@SP
M=M+1    // SP++

Hack VM 記憶體總覽

第五週的「神祕關鍵字」至此全部解密： SP、LCL、ARG、THIS、 THAT 是 VM 實作的基礎設施， R0–R15 中 5–12 給 temp、 13–15 給翻譯器自用。

綜合練習題（附詳解）

練習 1：堆疊追蹤

初始堆疊為空，local 0 \(= 10\)、local 1 \(= 20\)。 逐步寫出每條指令後的堆疊與 local 內容：

push local 0
push local 1
push local 0
pop local 1
add
pop local 0

練習 2：運算元順序

(a) push constant 3、push constant 1、sub 之後堆疊頂是什麼？ (b) 要計算 \(5 - \texttt{local 2}\)，指令順序怎麼寫？ (c) neg 與 not 對值 \(3\) 各得到什麼（16 位元）？

練習 3：運算式編譯

寫出計算 \((\texttt{local 0} + \texttt{local 1}) \mathbin{\&} (\texttt{local 0} - 7)\) 並把結果存入 local 2 的 VM 碼。

push local 0
push local 1
add             // local 0 + local 1
push local 0
push constant 7
sub             // local 0 - 7
and             // 兩者逐位元 AND
pop local 2

練習 4：true 與 false 的表示

(a) 為什麼 Hack VM 用 0xFFFF 表示 true 而不是 1？ (b) 設堆疊頂是 gt 的結果，接著執行 not。 這在邏輯上等價於什麼比較？ (c) 若某語言用 1 當 true，and 還能兼作邏輯運算嗎？

練習 5：RPN 轉換

把運算式 \(((a + b) - c) > (d \mathbin{|} e)\) 轉成 VM 碼， 其中 \(a\)–\(e\) 分別是 local 0–local 4。

push local 0    // a
push local 1    // b
add
push local 2    // c
sub             // (a+b)-c
push local 3    // d
push local 4    // e
or              // d|e
gt              // ((a+b)-c) > (d|e)

練習 6：迴圈翻譯

把下列 C 程式翻成 Hack VM（i 用 local 0、 sum 用 local 1）：

sum = 0;
for (i = 10; i > 0; i--) { sum += i; }

push constant 0
pop local 1        // sum = 0
push constant 10
pop local 0        // i = 10
label LOOP
push local 0
push constant 0
gt                 // i > 0 ?
not                // 取反：i <= 0 ?
if-goto END        // 條件不成立就離開
push local 1
push local 0
add
pop local 1        // sum += i
push local 0
push constant 1
sub
pop local 0        // i--
goto LOOP
label END

練習 7：陣列存取

陣列存放在 \(RAM[\texttt{0x0900}]\) 起。寫 VM 碼完成 arr[local 2] = arr[local 2] + 1（假設不出界）。

push constant 2304   // 0x0900
push local 2
add
pop pointer 0        // this 0 -> arr[local 2]
push this 0
push constant 1
add
pop this 0           // 寫回同一位置

練習 8：this vs that

(a) 為什麼把螢幕塗黑的程式必須用 that 而不能用 this？ (b) 寫 VM 碼把螢幕的第一個字（\(RAM[16384]\)）設為全 1（\(-1\)）。

push constant 16384
pop pointer 1        // that 0 -> RAM[16384]
push constant 0
not                  // 0xFFFF（-1，全 1）
pop that 0           // 螢幕第一個字 = 全黑

練習 9：基底與位移

某次執行中 \(RAM[1] = 317\)、\(RAM[2] = 310\)、\(RAM[3] = 3000\)、 \(RAM[4] = 16384\)。求下列虛擬位址對應的實體位址： (a) local 4；(b) argument 1； (c) this 12；(d) that 100； (e) temp 3；(f) pointer 1。

練習 10：記憶體映射

(a) 編譯 Foo.vm 時 static 5 映射到哪裡？ 為什麼用組語變數而不是固定位址？ (b) R13–R15 的用途是什麼？ 在練習哪一題的翻譯範例中出現過？ (c) 堆疊段最多能長到哪？再長會發生什麼事？

練習 11：SP 機制

初始 \(SP = 258\)、\(RAM[256] = 17\)、\(RAM[257] = 3\)。 逐步寫出執行 push constant 9、add、 pop local 0（設 \(\texttt{LCL} = 300\)）後 \(SP\) 與相關 RAM 的值。

練習 12：端到端翻譯

把 VM 指令 push temp 3 翻譯成 Hack 組語。 提示：temp 是固定段。

@8
D=M      // D = RAM[8]（temp 3 的值）
@SP
A=M
M=D      // RAM[SP] = D
@SP
M=M+1    // SP++

附錄：速查表

Hack VM 指令總表

二元運算：\(y\) = 先彈出、\(x\) = 後彈出，計算 \(x \circ y\)。

八個虛擬記憶體段

記憶體映射總表

名詞中英對照

參考資料

• John Lapinskas, Virtual machines and intermediate representations／The Hack VM I & II／ Implementing the Hack VM translator（9-1 至 9-4）， COMSM1302, University of Bristol.

• Nisan & Schocken, The Elements of Computing Systems （nand2tetris），Ch. 7–8（Virtual Machine I & II）.

• LLVM Project, LLVM Language Reference Manual （真實世界 IR 的規格範例）.

• Shi, Casey, Ertl & Gregg, Virtual Machine Showdown: Stack versus Registers, ACM TOPLAS, 2008（堆疊機 vs 暫存器機的實測研究）.

• WebAssembly Design Rationale （現代堆疊機 IR 的設計取捨）.