三たび、RISC-Vシミュレータの作り方〜紅玉と錆と霊薬と〜

こんにちは。 Ruby x Agile というグループに所属しながらRubyにまつわる記事を一つも書いていない気がするe.mattsanです。今回もRuby以外のお話です。

RISC-Vシミュレータ作り、おさらい
プログラミング言語Elixir
RV32Simを実行する
RV32Sim.Register
RV32Sim.Memory
RV32Sim.Instruction
- add
- beq
RV32Sim.CPU
RV32Sim
プログラミング言語には意外な側面がある

RISC-Vシミュレータ作り、おさらい

今、なにやらRISC-Vシミュレータ作りが流行っているようです。局所的かもしれませんけれども、流行っていることにします。

所属する事業部の母語であるRubyでの実装や、近年なにかと注目を集めているRustの実装は、それぞれの特徴を見せてくれました。

しかし、シミュレータの実装により適した言語をわたしは知っています。

Elixirです。

プログラミング言語Elixir

「Elixir」と聞いて、どのような特徴が思い浮かぶでしょうか。

関数型言語
軽量プロセスによる平行処理
クラッシュしてもプロセスが蘇る耐障害性
Rubyライクな構文のErlang

他にも、Webアプリケーションのフレームワーク「Phoenix」や、組み込み向けのフレームワーク「Nerves」の動きも活発で、最近ではデスクトップアプリケーションにまで版図を広げようとしています。

そんな中、あまり語られない特徴があります。それは「ビット列操作が得意」という点です。より正確にはElixirがというよりも、その下地となるErlangがビット列操作を得意としている、と言った方がよいかもしれません。

Erlangは、スウェーデンの通信機器メーカー、エリクソン社を出自としています。データ通信では、効率のよいデータ転送を行うために、無駄なビットを送信しないよう、データはビット単位で詰め込まれます。そのため通信機器のソフトウェアではビット列操作が欠かせません。そのような環境で生まれたErlangも、ビット列操作を得意としています。

わたしがかつて携帯端末の開発に携わっていたころ、サードパーティーから購入したC言語のASN.1のライブラリに悪戦苦闘したのですが、Erlangではそれが標準装備されているほどです。

そしてErlangの系譜に連なるElixirもまたビット列操作を得意としています。

RV32Simを実行する

どれくらい得意なのか、RISC-Vシミュレータの実装で見てゆきましょう。

コードの全体は、GitHub Gist に公開しました。

RISC-V subset simulator in Elixir · GitHub

ROMイメージは、はたけやまさんが公開してくださっているリポジトリの内容を拝借します。

GitHub - thata/rv32sim: RISC-V(RV32I subset) Simulator

thata/rv32sim を git clone したら、そのディレクトリに GitHub Gist のファイル rv32sim.exs を置いてください。

Elixir がインストールされている環境で、次のようにコマンドを入力すると、ROMの内容を解釈して実行してくれます。

$ elixir -r rv32sim.exs -e 'RV32Sim.run("sample/hello.rom")'
HELLO WORLD!!
--------------------------------------------------------------------------------------------
x0  = x00000000 (0)  x1  = x00000000 (0)  x2  = x00000000 (0)  x3  = x10000000 (268435456)
x4  = x00000000 (0)  x5  = x0000000a (10) x6  = x00000000 (0)  x7  = x00000000 (0)
x8  = x00000000 (0)  x9  = x00000000 (0)  x10 = x00000000 (0)  x11 = x00000000 (0)
x12 = x00000000 (0)  x13 = x00000000 (0)  x14 = x00000000 (0)  x15 = x00000000 (0)
x16 = x00000000 (0)  x17 = x00000000 (0)  x18 = x00000000 (0)  x19 = x00000000 (0)
x20 = x00000000 (0)  x21 = x00000000 (0)  x22 = x00000000 (0)  x23 = x00000000 (0)
x24 = x00000000 (0)  x25 = x00000000 (0)  x26 = x00000000 (0)  x27 = x00000000 (0)
x28 = x00000000 (0)  x29 = x00000000 (0)  x30 = x00000000 (0)  x31 = x00000000 (0)
--------------------------------------------------------------------------------------------
pc = x8c (140)

実行できることが確認できたところで、実装のポイントを解説して行きたいと思います。

なお、以降解説する部分のみを掲載しています。コードの全容はGitHub Gistをご参照ください。

RV32Sim.Register

レジスタを表現するモジュール RV32Sim.Register です。

32ビットのレジスタが32本ですので、これを32×32=1024ビットのビット列で表現することにします。

初期化

32ビットを単位として、32ワードのビット列を生成します。

  def new do
    <<0::32-unit(32)>>
  end

これは、次のような構造になっています。

<<, >>
- ビット列を構築する記号。この括弧で囲まれた値がビット列の表現になります
0
- ビット列の値。上位ワードは自動的に0が充填されるので、これですべてのワードに0が設定されます
32
- 32ワード。ワードのビット数は後続の単位で指定されます
unit(32)
- 単位ビット数（1ワードのビット数）を指定

読み出し

第1引数にレジスタのビット列、第2引数にレジスタの番号を指定して、番号の位置のレジスタの値を取得する関数を定義します。このとき0番目のレジスタが指定されたときには0を返すようにしています。

ここで早速ビット列のパタンマッチングが出てきました。

  def get(_, 0), do: 0

  def get(registers, number) do
    <<_::size(number)-unit(32), result::32, _::bytes>> = registers
    result
  end

パタンマッチングはElixirプログラミングの各所で現れますが、ビット列に対しても利用できるという特徴があります。この特徴によって、ビット列から柔軟に値を取り出すことを可能にしています。

次の例では、32ビットの値を3つの変数にマッチさせることで、先頭から8ビット、16ビット、8ビットの値を取り出しています。

<<a::1-unit(8), b::1-unit(16), c::1-unit(8)>> = <<0x12345678::1-unit(32)>>
# a => 18 (0x12)
# b => 13398 (0x3456)
# c => 120 (0x78)

上の例では先のコードに合わせて unit オプションを指定しましたが、サイズがわかっている場合には、単純にビット数を記述するだけでかまいません。

# デフォルトの単位は 8 ビットなので、a と c は 8 ビットの値になる
<<a, b::16, c>> = <<0x12345678::32>>

レジスタ読み出し関数は、次のようなパタンマッチングを行なっています。

_::size(number)-unit(32)
- 先頭のレジスタの値を、ワイルドカード _ にマッチさせて読み捨てています。ワード数を変数で指定する場合、_::number と記述することはできず _::size(number) としなければなりません
result::32
- 取得する32ビットの値を result に束縛します
_::bytes
- 残りのビット列を _ にマッチさせて読み捨てます。bytes と記述することで長さを指定しない任意のバイト列（8ビット単位の値の並び）にマッチさせることができます

最後に関数の値として、整数値 result を返します。

書き込み

書き込みは、読み込みと逆の操作で、番号の位置の値を読み捨て、書き込む値を元の値の左右のビット列の間にはさみ込んだビット列を生成することで実現します。

  def set(registers, number, value) do
    <<left::size(number)-unit(32), _::32, right::bytes>> = registers
    <<left::size(number)-unit(32), value::32, right::bytes>>
  end

すでに気づかれている方もいらっしゃると思いますが、レジスタに値を書き込むたびに新しいビット列が生成されています。頻繁に値を更新する今回のようなケースには、この方法はあまり適していない可能性があります。

今回は、インパクト重視で、この方法で押し通します。

RV32Sim.Memory

メモリを表現するモジュール RV32Sim.Memory です。読み書きを行う基本的な作りはレジスタと変わりありません。

初期化

512バイトのビット列を生成します。

引数で初期値となるバイナリを受け取ります。残りの部分を0で埋めるため、引数で受け取ったバイナリに、8ビットを単位として512からバイナリのサイズを引いたもののを連結します。

  def new(binary) do
    rest_size = (512 - String.length(binary))
    binary <> <<0::size(rest_size)-unit(8)>>
  end

ここで <> はバイナリを連結する演算子です。

Elixirには、ファイルの内容を読み込む関数 File.read! が標準で用意されています。この関数はファイルの内容を読み込み、それをバイナリとして返してくれます。

RV32Sim.Memory.new にこの関数が返す値を渡すことで、メモリの先頭側にファイルの内容を格納した512バイトのビット列を得ることができます。

# ファイルの内容を読み込んだメモリの内容を表すビット列を取得する
memory = RV32Sim.Memory.new(File.read!(filename))

読み出し

レジスタと同じ要領で、指定された位置の値を読み出します。ただし、値はメモリ上にリトルエンディアンで格納する必要があるので、little で修飾しています。

  def load(memory, address) do
    <<_::size(address)-unit(8), result::little-32, _::bytes>> = memory
    result
  end

書き込み

こちらもレジスタと同じ要領で、指定された位置に値を書き込みます。 little で修飾するのも読み出しと同じです。

  def store(memory, address, value) do
    <<left::size(address)-bytes, _::32, right::bytes>> = memory
    <<left::bytes, value::little-32, right::bytes>>
  end

Memory-mapped I/O

今回のシミュレータでは、メモリ空間にI/Oが割り当てられています。これは特定のアドレスに対して読み書きが行われた場合に、I/O処理を実行することで実現できます。

記述が前後してしまいましたが、特定のアドレスにマッチングさせる必要があるので、ここに書いた load, store は、先に記載した同名の関数よりも先に記述しておく必要があります。

  def load(_, 0x10000000) do
    <<c, _::bytes>> = IO.read(1)
    c
  end
  
  def store(memory, 0x10000000, value) do
    IO.write(<<value>>)
    memory
  end

RV32Sim.Instruction

インストラクションを扱うモジュール RV32Sim.Instruction です。

CPUの挙動を正しくシミュレートするならば、デコードと評価をきちんと分離すべきところかもしれませんが、ビット列のパタンマッチングの特徴を見せつけるべく、今回はデコードと評価を同時に行なっています。

なおGitHub Gistに公開しているElixirのコードには、以前の記事と同じ種類のインストラクションを実装していますが、この記事ではその中から2つを例に挙げて解説します。

RISC-Vのインストラクションの詳細については、以前の記事からの再掲になりますが、リファレンスを参照ください。

riscv-card/riscv-card.pdf at master · jameslzhu/riscv-card · GitHub

add

一つ目の例は、二つのレジスタの値を加え、もう一つのレジスタに結果を格納する add です。

add は R-type のインストラクションなので、最上位ビットから順に funct7 : 7ビット、rs2 : 5ビット、rs1 : 5ビット、funct3 : 3ビット、rd : 5ビット、opcode : 7ビットという並びになっています。

また opcode = 0b0110011, funct3 = 0x0, funct7 = 0x00 と定義されています。

31〜25	24〜20	19〜15	14〜12	11〜07	06〜00
funct7 `0x00`	rs2	rs1	funct3 `0x0`	rd	opcode `0b0110011`

メモリから取り出した32ビットの値をビット列として、それをそのまま関数 eval の第1引数に渡します。第2引数はレジスタを表すビット列、第3引数はメモリを表すビット列です。

  # add
  def eval(<<0x00::7, rs2::5, rs1::5, 0x0::3, rd::5, 0b0110011::7>>, registers, memory) do
    registers = set(registers, rd, get(registers, rs1) + get(registers, rs2))
    {4, registers, memory}
  end

rs2, rs1, rd は変数にマッチさせていて、それぞれ5ビットの整数値として取り出すことができます。

これらをレジスタ番号として、レジスタから値を取り出し、加算し、結果をレジスタに設定します。

戻り値は、次に実行するインストラクションのアドレス（相対アドレスで指定）、更新されたレジスタ、更新されたメモリ、の3つ組みのタプルを返却するようにしました。

戻り値に次のインストラクションの相対アドレスを返すようにした理由は、次の例で解説します。

beq

二つ目の例は、二つのレジスタの値を比較し、一致していれば即値で指定する相対アドレスにジャンプし、そうでなければ何もしない beq です。

beq は B-type のインストラクションです。 B-type のインストラクションは immediate を持ちますが、細切れになって格納されていて、必要な値を取り出すにはこれらを並べ替えて連結しなければなりません。

31〜25	24〜20	19〜15	14〜12	11〜07	06〜00
imm[12\|10:5]	rs2	rs1	funct3 `0x0`	imm[4:1\|11]	opcode `0b1100011`

とはいえ、ここまで見てきたように、Elixir であればビット列の分割も連結も得意です。加えて、符号付きを表す signed で修飾することで、自動的に符号付きと扱ってくれます。

  # beq
  def eval(<<imm12::1, imm10::6, rs2::5, rs1::5, 0x0::3, imm4::4, imm11::1, 0b1100011::7>>, registers, memory) do
    # 細切れのビットを集め、符号付き13ビットの値として imm に束縛する
    <<imm::signed-13>> = <<imm12::1, imm11::1, imm10::6, imm4::4, 0::1>>
    relative_address = if get(registers, rs1) == get(registers, rs2), do: imm, else: 4
    {relative_address, registers, memory}
  end

ここで、二つのレジスタの値が等しければ imm の値を、そうでなければ 4 を返しています。

ちなみに。冒頭の説明で、二つのレジスタの値が一致しない場合には何もしないとしましたが、「何もしない」は「次のインストラクションのアドレスにジャンプする」と解釈しても、ふるまいに違いはないはずです。

つまりこのインストラクションは、常に「次に実行するインストラクションの相対アドレスを結果として返す」ものとして扱っても問題ありません。このため、比較の結果が一致不一致のどちらであっても、戻り値の相対アドレスの値をプログラムカウンタに加えればよい、ということになります。

RV32Sim.CPU

CPU 本体です。

RV32Sim.Register, RV32Sim.Memory, RV32SimInstruction を利用して、停止命令（5回のNOP）に遭遇するまでメモリに格納された内容を連続して実行します。プログラムカウンタの更新もここで行なっていますが、beq のところで説明した通り、インストラクションの評価結果のアドレスを加算するだけなので、とてもシンプルになっています。

defmodule RV32Sim.CPU do
  alias RV32Sim.{Register, Memory, Instruction}

  def run(pc, memory) do
    run(pc, Register.new(), memory, 0)
  end

  defp run(pc, registers, memory, 5), do: {pc, registers, memory}

  defp run(pc, registers, memory, nop_count) do
    instruction = Memory.load(memory, pc)

    {relative_address, registers, memory} =
      Instruction.eval(<<instruction::32>>, registers, memory)

    run(pc + relative_address, registers, memory, count_nop(instruction, nop_count))
  end

  defp count_nop(0b0000_0000_0001_0011, n), do: n + 1
  defp count_nop(_, _), do: 0
end

停止処理が、個人的にいまひとつ綺麗に書けなかったので、これは次回への宿題としたいと思います。

RV32Sim

最後にシミュレータのエントリポイントです。

ROMイメージのファイルを読み込み、メモリに格納して、CPUを走らせます。停止したら、レジスタの内容を出力して終了です。

defmodule RV32Sim do
  alias RV32Sim.{Register, Memory, CPU}

  def run(filename) do
    memory = Memory.new(File.read!(filename))
    {pc, registers, _memory} = CPU.run(0, memory)

    Register.dump(registers)

    :io.format("pc = x~.16b (~b)~n", [pc, pc])
  end
end

範囲外へのアクセスなどエラー処理を省略したためというのもありますが、ここまでで150行ほどのコードになりました。

プログラミング言語には意外な側面がある

例えば、C言語のマクロを利用した変態プログラムや、C++のテンプレートを利用した変態プログラムなどを見るにつけ、「なんでこんな仕組みを用意した？」と首を傾げることがあったりします。でもそれは、変態コードを書くために実装されたはずはなく、求められて実装されたはずです。それらの仕組みが、例えばライブラリの中で、効果的に利用されているのかもしれません。

なぜこのような仕組みがあるのか、その出自を調べて考えてみるのも、面白いと思います。

お気に入りのプログラミング言語を限界まで使いこなしてみませんか？

株式会社永和システムマネジメントアジャイル事業部では、エンジニアを絶賛募集しています。

さまざまな背景を持つ方々も歓迎です。応募エントリお待ちしております！

agile.esm.co.jp

ESM アジャイル事業部開発者ブログ

永和システムマネジメントアジャイル事業部の開発者ブログです。

三たび、RISC-Vシミュレータの作り方〜紅玉と錆と霊薬と〜

RISC-Vシミュレータ作り、おさらい

プログラミング言語Elixir

RV32Simを実行する

RV32Sim.Register

初期化

読み出し

書き込み

RV32Sim.Memory

初期化

読み出し

書き込み

Memory-mapped I/O

RV32Sim.Instruction

add

beq

RV32Sim.CPU

RV32Sim

プログラミング言語には意外な側面がある