Pages

Saturday, October 29, 2011

Extending Gforth with the Code Word

很久沒發文了,但一直都有記錄筆記的習慣,原本也是打算整理好發表的,但常常寫到一半就去做其他事了,所以積了不少未完成的稿XD 這次出清一篇筆記,來談談 forth 中的 code word。

一般對於 forth 系統的擴展有兩種方式,最方便的當然是定義新的 colon word,另一種則是實作比較低階的 code word。

code word 代表的是低階實作,也就是直接跟底層平台對話。以 lisp-based forth 為例,其實就是把 lisp vm 當作(虛擬)硬體平台,因此 code word 作用大概就是產生一堆 lisp form,而 x86 native forth 當然就是產生 x86 machine code 了。

簡單地說,code word 需要負責兩件事:

  • 產生 native code
  • 讓 forth 可以順利執行這些 native code

產生 native code 的工作通常會由一個 target assembler 負責。這也是為什麼一個完整的 forth system 多半會提供自己的 assembler。雖然 forth 已經是可擴展的設計,但在需要直接操作宿主平台時,可能會需要寫成 code word 比較方便。

比較麻煩的是第二點,讓 forth 可以順利執行的關鍵在於不能干擾系統運作。forth 本身雖然是 stack vm,但還是有幾個基本的暫存器,一般在 x86 上會對應到實際的暫存器。依照實作模型的不同,可能會需要佔用 2 至 5 個不等。在 code word 中必須妥善管理這幾個暫存器,不是單純 pushapopa 就可以解決的。最常見的狀況,就是維護 SP 的值 (forth 中的 SP 暫存器,非 x86 的),確保參數可以正常傳遞,不會發生 underflow;以分支指令來說可能需要修改 IP 的值,只要改錯暫存器就會發生災難。因此第一步就是找出這幾個暫存器的對應關係。

在一般的 forth 系統中,通常會提供一個叫做 see 的 disassembler,可以透過它來猜出系統的規劃。Gforth 套件提供了好幾種實作,由於接下來的實驗在不同實作中會有不同結果,為了方便解說只使用 gforth-fast。在 Gforth 中,第一個建議觀察的是什麼事都不會做的 noop

see noop
Code noop
( $804B1BF )  add     esi , # 4  \ $83 $C6 $4
( $804B1C2 )  mov     ebx , dword ptr FC [esi]  \ $8B $5E $FC
( $804B1C5 )  mov     eax , ebx  \ $89 $D8
( $804B1C7 )  jmp     804B03C  \ $E9 $70 $FE $FF $FF
end-code

從這邊可以猜到不做事的時候,系統大概會使用 eaxebxesi,然後跳到某個位址繼續執行。因此觀察其他 word 的時候就可以先去除這幾個動作,找出真正關鍵的操作。接下來建議的是 dupdrop。這兩個 word 是基本的堆疊操作,可以直接找出 SP 在哪,甚至可以看出是否有加入 TOS (Top Of Stack) 的快取設計,也就是將 TOS 放在特定的暫存器以減少一次記憶體操作。

see drop
Code drop
( $804C836 )  add     edi , # 4  \ $83 $C7 $4
( $804C839 )  add     esi , # 4  \ $83 $C6 $4
( $804C83C )  mov     ebp , dword ptr [edi]  \ $8B $2F
( $804C83E )  mov     ebx , dword ptr FC [esi]  \ $8B $5E $FC
( $804C841 )  mov     eax , ebx  \ $89 $D8
( $804C843 )  jmp     804B03C  \ $E9 $F4 $E7 $FF $FF
end-code

drop 的內容可以看到除了 noop 以外,還操作了 edi,沒有意外的話 SP 就是它了。同時也知道堆疊往低位址成長 (因為 drop 相當於做了一次 stack pop)。作為佐證可以再觀察一下 dup,應該會看到減少 edi 內容值的運算:

see dup
Code dup
( $804C85D )  sub     edi , # 4  \ $83 $EF $4
( $804C860 )  add     esi , # 4  \ $83 $C6 $4
( $804C863 )  mov     dword ptr 4 [edi] , ebp  \ $89 $6F $4
( $804C866 )  mov     ebx , dword ptr FC [esi]  \ $8B $5E $FC
( $804C869 )  mov     eax , ebx  \ $89 $D8
( $804C86B )  jmp     804B03C  \ $E9 $CC $E7 $FF $FF
end-code

看起來的確有移動 edi 內容的操作。另外還看到奇怪的動作,把 edp 的內容搬進 stack top - 1 的位置,並不是移動到 stack top,推測 可能有 TOS 的設計。

要證實這一點,可以再看一下 swap+ 這幾個會影響 TOS 的 word。

see +
Code +
( $804B918 )  add     ebp , dword ptr 4 [edi]  \ $3 $6F $4
( $804B91B )  add     esi , # 4  \ $83 $C6 $4
( $804B91E )  add     edi , # 4  \ $83 $C7 $4
( $804B921 )  mov     ebx , dword ptr FC [esi]  \ $8B $5E $FC
( $804B924 )  mov     eax , ebx  \ $89 $D8
( $804B926 )  jmp     804B03C  \ $E9 $11 $F7 $FF $FF
end-code

看來的確是把運算後的結果 (TOS) 直接放到 ebp 了,而不是放在記憶體中。拿到 SPTOS 後就可以試著增加一個 code word 看看了。首先用最簡單的 dup 操作來驗證前面的猜測,實作一個有相同操作的 _dup

code _dup
    bp di ) mov
    4 # di sub
    next
end-code

3 _dup .s

可以看到堆疊中的確出現兩個 3 了。不過看起來自己實作的 _dup 好像比原版的 dup 還要精簡一點。另外也可以寫個 _+ 看看:

code _+
    4 # di add
    di ) bp add
    next
end-code

2 3 _+ .s

結果也正確無誤,留下一個 5。到這邊已經可以做很多事了。不過偶爾可能會需要 RP,所以從 >r 找到 RP 放在記憶體的某處。查找的過程不再列出,同樣複製一個相同的 _>r 來驗證看看:

code _>r
    4 # $3c sp d) sub
    3c sp d) bx mov
    bp bx ) mov

    4 # di add
    di ) bp mov
    next
end-code

為了維護 return stack, >rr> 通常要平衡使用才不會破壞系統運作,所以我將自己實作的 _>r 搭配系統的 r> 一起使用,測試過可以正常執行。

除了這幾個重要的暫存器外,還有一個 IP,可以透過觀察 branch 找到,這裡就不再贅述了。不過還有一件重要的事需要特別提出來討論。在整理這篇筆記的過程中,我發現一個嚴重的問題:以前實驗的結果,在 0.7.0 版的 gforth-fast 可以正常運作,但換成 0.7.9 版卻無法動作,後來試了一下 0.6.2 也同用無法執行。查了文件才知道原因在於 c compiler 版本。由於不同版本的編譯器執行 register allocation 結果可能不同,會產生出完全不一樣的 forth vm,這點是特別要注意的。前面列出來的結果是在 gcc 4.4.4 建立出來的 gforth-fast 0.7.9 的環境重新實驗的。如果使用到的暫存器剛好都是自由的 (不被系統使用),換系統時就不需要再調整程式了。

雖然聽起來有點糟,但對我來說也不算什麼大問題就是了。畢竟 forth 在各系統間的相容性本來就不能期待,會想使用 code word 的人大概對正在使用的系統也有一定的掌握能力了,這樣程度的相容性問題應該都有能力處理。


會翻出這篇筆記,主要是看到有人做了一個 benchmark,gforth-fast 需要的時間是其他 forth 的好幾倍,想試試把幾個關鍵處改寫成 code word,看有沒有機會加速。最後實驗的結果是... 不行!

囧rz...

非但沒變快,反而更慢了XD 也許 Gforth 在切換成 code word 可執行環境時做了很多事,因此效能不如全部都使用 colon word;也許是 instruction miss 等原因造成的吧。這個一時興起的實驗提醒了我在選系統時要記得同時測試一下 code word 的使用,暫時還是先把 Gforth 的 assembler 當作 cross assembler 使用吧。

No comments:

Post a Comment