實作一個簡單的 virtual machine

萬事起頭難

雖然標題是《實作一個簡單的 virtual machine》, 不過其實已經有現成的程式碼了, 這篇主要在討論這個 virtual machine 的設計。

對虛擬機器 (virtual machine 後文以 vm 簡稱) 一直很好奇, 買了 2 本 jvm 的書籍 (fig 1), 不過對 java 實在提不起什麼興趣, 只看過封面。而 sicp chapter 5 也有介紹 vm, 不過 scheme 語法和寫程式的思維太奇怪了, 很難頓悟, 我努力了很久, 沒什麼大突破。

《手把手教你构建 C 语言编译器 - 手把手教你构建 C 语言编译器（2）——虚拟机》提供了一個很簡單的 vm 實作。總共只要 4 個暫存器, pc, sp, bp, ax, 再搭配上 38 個指令, 就可以將 c 語言的部份語法結果執行在這台 vm 上, 實在是太神了, 重點是她很簡單, 可以在短時間內學成。我打算以這系列來學習編譯器, 就先從 vm 這章開始吧!

這個 vm 雖然簡單, 但沒簡單到看過去就能理解, 我一開始先觀察 source code 和轉成 machine code 之間的對應關係, 試著去理解裡頭的 38 個指令, 不過人家把 vm 的 code 都寫完了, 那我要幹嘛? 我想辦法把她看懂, 並實作了除錯命令, 類似 gdb 的指令, 原本只是為了方便我學習這個 vm, 後來愈幹愈起勁, 就變成這樣了。我還加入 break pointer 和 continue 等命令, 好像搞錯學習方向了。

原文已經對這些指令有了些許介紹, 我補充一下自己的心得:

1. IMM arg,
2. JMP arg,
3. CALL arg:
   push 下一個 pc (function return 後回 pop 這個值到 pc), 將目前的 pc 改成 arg 的值。
   
4. JZ arg:
5. JNZ arg:
6. LEA arg: 使用 bp 來存取 function 裡頭的區域變數, 取出這些區域變數的位址, 存到 ax。
   ex:
   

   void f1()
   {
     int i,j;
     i=5;
     j=6;
     printf("%d\n", i, j);
   }
   

   LEA 0xffffffff(-1) 就是將 i 變數的位址存到 ax (bp 指到的位址減一, 但是 bp 是 int*, 所以其實是減四)。
   
7. ENT arg: push bp; bp = sp; sp = sp - ent_arg
8. LEV arg: sp = bp; bp = pop_stack; pc = pop_stack (這是 call 指令先 push 下一個要執行的指令而來的值)
9. ADJ arg: function 的參數是用 push 到 stack 傳入的, 所以在執行完這個 function 後, 要用 ADJ 加回 stack 的指標。
   ex: push arg1; push arg2; push arg3; call func; adj 3
10. LI ,
11. LC ,
12. SI: pop_stack, 將 ax 的值存到 pop_stack 的位址上。
    

    int main(int argc, char **argv)
      {
        int i;
    
        i=2;
        return 0;
      }
      

    i=2; 會用到 SI
    
13. SC ,
14. PUSH: 先將 sp - 4 byte, 在把 ax 的值存到 sp 指到的 stack。
    ex: *--sp=ax
15. OR ,
16. XOR ,
17. AND ,
18. EQ ,
19. NE ,
20. LT ,
21. GT ,
22. LE ,
23. GE ,
24. SHL ,
25. SHR ,
26. ADD:
    pop_stack 的那個值 + ax 的值
    
27. SUB ,
28. MUL ,
29. DIV ,
30. MOD ,
31. OPEN,
32. READ,
33. CLOS,
34. PRTF,
35. MALC,
36. MSET,
37. MCMP,
38. EXIT

本來這程式是可以自己編譯自己的 (中國術語是「自舉」), 不過再被我加入了一堆亂七八糟的程式碼後, 已經沒辦法這樣做了。

下方的影片展示這個 debug 功能, 很類似 gdb 吧!



我 fork 了原作者的專案:
https://github.com/descent/write-a-C-interpreter

fig 1. java virtual machine books