Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2007年09月18日(火) Low-Level Haskell Programming

x86のオペコード体系がだんだん綺麗に見えてきた。

[]Haskellとインラインアセンブリ(構築編) Haskellとインラインアセンブリ(構築編)を含むブックマーク Haskellとインラインアセンブリ(構築編)のブックマークコメント

前回の内容を踏まえて、今回は、Haskellで記述されたアセンブリプログラムアセンブルして、それを前回述べた方法を用いて実行することを目標とする。


本項ではHaskell上でアセンブリプログラムを記述するための言語を構築し、それに対するアセンブラを作成する。


記述の利便性のため、Haskell上で構築する言語モナドで構成する。普通アセンブラで扱えるような形で記述できればうれしい。

foo :: CodeBlock (IO Int)
foo = assemble $ do
  movl eax 777
  movl eax ecx
  movl eax (mem(eax))
  movl eax (mem(eax,ebx))
  movl eax (mem(eax,(ebx,4)))
  movl eax (mem(eax,4))
  movl eax (mem(eax,ebx,777))
  movl eax (mem(eax,(ebx,8),777))
  ret

サイズ指定を容易にするため、gasのようにニモニックでオペランドサイズを指定することにする。そのほかの部分はintel形式を模倣する。このようにコードを記述できてそれを実行できるようにすべく以降で定義をしてゆく。


まず、アセンブリプログラムを表すAsmモナドを定義する。Asmモナド

type Asm a = RWS () [Mnemonic] AsmState a

このように定義した。RWSモナドは、ReaderWriterState能力を持つモナドで、今回のアセンブラではアセンブリの中間コード(上でのMnemonic)を出力するためのWriterと状態を扱うためにStateを利用する。Asmモナドは一塊のコードを示し、これをassembleにかけることによって関数というまとまった単位コードアセンブルされるものとする。


Mnemonicは次のように定義した。

data Mnemonic =
    Imp Mne
  | Uni Mne Size Operand
  | Bin Mne Size Operand Operand
  | Tri Mne Size Operand Operand Operand
  | Rel Mne LabelID
  | Abs Mne CodeBlock
  | Label LabelID

Impはオペランドなしの命令。Uni,Bin,Triはそれぞれオペランドが1,2,3個の命令。RelとAbsは後述。Labelはラベルの定義。


サイズは、1,2,4,8バイトのいずれか。

data Size = SByte | SWord | SDWord | SQWord deriving (Show)

x86オペランドは、レジスタと即値とメモリアドレスがあり、アドレッシングモードは、(ベースレジスタ)+(インデックスレジスタ)*(スケール(1,2,4 or 8))+(ディスプレースメント)の形および、このうち1つ以上が欠けた形を取る。

data Operand =
    Imm Int
  | Reg RegName
  | Mem Address

data Address =
  Address (Maybe RegName) (Maybe (RegName,Int)) Displacement

実際にアセンブリを記述する際はmovlなどのヘルパ関数を用いる。この際、利便性のために引数オーバーロードしてほしい(数値が書かれていれば即値など)。アドレスを指すためにはmemという関数を用いる。これを用いなくても(eax,(ebx,2),1)のような形であればmovlなどで直接オーバーロードできるが、(eax)というような形は(つまり1-tupleは)eaxと区別できないのでそれらを区別するために用いる。引数オーバーロードするために次のようなクラスを定義する。

class AddrMode a where
  toArgument :: a -> Operand

instance Integral a => AddrMode a where
  toArgument n = Imm $ fromIntegral n

instance AddrMode RegName where
  toArgument r = Reg r

instance AddrMode Address where
  toArgument a = Mem a

instance AddrMode Operand where
  toArgument o = o

これでmovlが定義可能になる。

movl :: (AddrMode a, AddrMode b) => a -> b -> Asm ()
movl = tell [ Bin Mov SDWord (toArgument a) (toArgument b) ]

他の命令も同様に定義できる。


ベルおよびジャンプ命令は次のように記述できるようにする。

hoge = assemble $ do
  l <- genLabel
  label l
  ...
  jmp l

genLabelでラベルIDを生成して、それを用いてラベル定義やジャンプ、条件ジャンプを記述する。ラベルIDを文字列にしてユーザが指定の文字列でラベルを記述できるようにしてもよかったが、後のことを考えるとこちらのほうが有利と判断した。


call命令に関してはローカルなラベルではなくて、他の関数を呼び出せなければいけない。他の関数はCodeBlock型で示される同じくアセンブラで生成された機械語列であるとする。

foo = assemble $ do
  ...

bar = assemble $ do
  ...
  call foo
  ...

このように定義すると、例えば上の場合だと、barアセンブルの際にfooの値が必要になる、つまり、fooのアセンブルが終わっている必要がある。あるいは、fooの値はメモリの先頭なのであるから、ポインタの値だけでも決まっている必要がある。これは再帰的に参照している場合に問題になる。それを許す実装も不可能ではないが、必要以上に複雑になるので、ここでは再帰的な参照は許さないものとする。ただし、直接的な再帰は利用される機会も多いのでselfという特別な名前を用いて行えるようにしておく。相互再帰に関しては、今のところおいておく。


このようにAsmモナドを定義すると、これを実行することによってMnemonicの列が得られる。あとは得られたMnemonicをバイト列にしてやればよい(と一言で言っているが、ここが一番大変)。


そのようにしてできたのがこちらである。命令はごく少数しかサポートしていないのであしからず

http://fxp.infoseek.ne.jp/tmp/asm/AsmX86.zip


コード例をいくつか示す。

前回手書きしたコードと同じもの。

import AsmX86

bar :: CodeBlock (IO Int)
bar = assemble $ do
  movl eax 777
  ret

階乗

fact :: CodeBlock (Int -> IO Int)
fact = assemble $ do
  l <- genLabel
  movl eax (mem(esp,4))
  subl eax 1
  jnz l
  movl eax 1
  ret
  label l
  pushl eax
  call self
  popl ecx
  addl ecx 1
  imull eax ecx
  ret

呼び出し例

main = do
  ret <- exec fact 10
  print ret

実行例

$ ghc --make Main.hs

[1 of 2] Compiling AsmX86 ( AsmX86.hs, AsmX86.o )

[2 of 2] Compiling Main ( Main.hs, Main.o )

Linking Main.exe ...

$ ./Main

3628800

このようにごく自然に呼び出せる(くれぐれもx86以外で実行しないように)。


以上のようにHaskell用インラインアセンブリを定義することができたが、AsmモナドHaskell上で構築するものであり、その際にはフルスペックHaskell能力が利用可能である。つまり、これを用いると一般的なマクロアセンブラ能力あるいはそれ以上に便利な機能が実装できる可能性がある。AsmはモナドでありHaskell普通に扱えるデータであるので、これを用いてより抽象的なブロックが作れるだろうし、AsmモナドStateを加えればより便利な機能が実装できるかもしれない。そこで、次回はそちらの方向に話をすすめて、アセンブラをより使いやすいものへと変化させたい。

desumasudesumasu 2007/09/19 07:58 tanakhさんがされていることと同じようなことが、Harpyというプロジェクトで行われているようです。もしご存じでなければ、参考までに。

http://uebb.cs.tu-berlin.de/harpy/

tanakhtanakh 2007/09/20 09:48 これは知りませんでした。確かに同じような書き方で書けるようになっていますね。実装の方法とかがだいぶ違うようなので、参考にさせて頂きます。

通りすがり通りすがり 2007/10/02 11:56 Haskellでインラインアセンブリとは素晴らしいですね。感動しました。実行時動的アセンブリコード生成ということで、C++で似たようなものがありますのでご紹介いたします。
http://homepage1.nifty.com/herumi/soft/xbyak.html

トラックバック - http://d.hatena.ne.jp/tanakh/20070918