この記事は Rust Advent Calendar 2020 ならびに CyberAgent Developers Advent Calendar 25日目の記事です。
今年のはじめの頃になりますが、『CPUの創り方』という本に載っている TD4 という CPU を実装してみました。TD4 は「とりあえず動作するだけの4bit CPU」の略です。この本に載っている CPU エミュレータを実際に実装してみました。ただし、本書には GUI が載っていましたが、それは省略しました。
「最近話題の RISC-V などの CPU エミュレータを作ってみたいものの、いきなり作るにはハードルが高い。何か簡単なもので素振りをして CPU の動作の仕組みをまずは知りたい」という方にはかなりオススメできる教材だと思います。私自身、TD4 のエミュレータを実装してみて CPU の動作原理やコンセプトがわかり、その後製作中の RISC-V エミュレータに生きているように思います。
今回私が実装したものは下記です。だいたい1日くらいで実装できました:
この記事では、まず CPU の動作原理について TD4 を通じて簡単に解説し、Rust による実装例を見ていきます。また実装したインタプリタについても簡単に解説を加える予定です。
今回の記事では Rust を用いた実装になっていますが、Rust 以外の言語でもまったく問題なく実装できる内容だと思っています。たとえば Python や Java 、Go のようなアプリケーション向けの言語であっても問題なく実装できるはずです。Rust のシステムプログラミング言語としての側面を利用した実装箇所は今回はないためです*1。
このブログでは恒例行事になっていますが、すべての解説を盛り込んだためかなりのボリュームになっています。お好きなところをかいつまんでお読みください。
リポジトリ
方針
今回のエミュレーションの方針は、クロックごとのレジスタ内の値を再現することとしました。本書を読むと、実際は CPU を論理回路から作り上げて再現することも可能なのですが、今回は命令を書いてそれを読み込ませるとレジスタに値を読み込んで計算などを行ってくれるという部分を再現することとしました。
予備知識
TD4 のような小さな題材であっても、基本的なアイディアは実際の CPU とそう相違ないはずです。TD4 を元に、CPU に関しての予備知識を少し書いておきたいと思います。
fetch-decode-execute サイクル
CPU は、fetch-decode-execute というステップを踏みながら計算を実行します*2。
- fetch: メモリ上からプログラムを読み出すフェーズ。
- decode: 取り出した命令を元に内部的にどういった処理に対応するかを紐付け、行う計算を確定するフェーズ。
- execute: 2で確定した計算を実際に実行するフェーズ。
このサイクルをプログラムが終了するまで実行し続けます。
今回の TD4 エミュレータも同様にこのサイクルを実行して計算を行うように実装しました。
ROM
TD4 では ROM (Read-Only Memory) と呼ばれる領域にプログラムを書き出し、そこからプログラムを1行1行読み取って計算処理を行います。
Rust ではたとえば下記のようにして表現されており、ここにプログラムの内容（今回はバイナリ表現）が入っています。
pub struct Rom { pub memory_array: Vec<u8>, // ここに [00000000, 00010000, 11100001] のような形でプログラムが入っている。 }
現在どの番地のプログラムを読み出しているかについては、プログラムカウンタ（pc）と呼ばれるフラグによって管理されます。先ほどの fetch-decode-execute サイクルが1サイクル終了するとプログラムカウンタが足され、次のプログラムを読み出し、ということを ROM の配列が終了するまで行うことになります。
プログラムは「オペレーションコード」と「イミディエイトデータ」と呼ばれる領域に分けて書かれています。
たとえば、00000001 という値があったときには、TD4 は 0000 をオペレーションコード、0001 をイミディエイトデータとして解釈します。ちなみにオペレーションコード 0000 は TD4 では A レジスタ（このあと説明します）の値とイミディエイトデータの ADD 命令を意味します。
レジスタ
一言で言うなら CPU における記録領域のようなものです。
TD4 では A レジスタと B レジスタという2つのレジスタが用意されています。このレジスタに計算途中の内容を出し入れしながら、計算処理を次々行っていきます。
I/O ポート
これは CPU に対して入力を与えたり、あるいは演算の結果を出力するために使用するポートです。TD4 の場合は CPU から直接 I/O が出るという構成を取っているようです。これは規模の小さい CPU で多く採用されている方式だそうです。
TD4 の命令
TD4 では加算命令（add）、レジスタの値の転送命令（mov）、入出力ポートのやりとり（in, out）、ジャンプ命令（jmp, jnc）の4つの動作が組み込まれています。
実際の CPU になってくると、これらに四則演算が追加されたり、浮動小数点演算が追加されたりと高機能になっていきます。
こうした命令はプログラム側に書かれており、CPU の役割は命令を解釈し計算処理を実行していくことにあたります。
CPU エミュレータの実装
それでは CPU エミュレータの実装の紹介に移っていきましょう。
データ構造を用意する
CPU エミュレータを作り始めた際によかった手順としては、まずデータ構造を用意し、その後に一気にそれらを紐付けていくという方法でした*3
最初に命令を表現する enum を用意しました。OpCode という enum です。なお num_derive という便利なトレイトを今回は使用しています。
use num_derive::FromPrimitive; #[derive(Debug, PartialEq, FromPrimitive)] pub enum Opcode { AddA = 0b0000, AddB = 0b0101, MovA = 0b0011, MovB = 0b0111, MovA2B = 0b0001, MovB2A = 0b0100, Jmp = 0b1111, Jnc = 0b1110, InA = 0b0010, InB = 0b0110, OutB = 0b1001, OutIm = 0b1011, }
各命令の詳しい内容は省略しますが、TD4 では12個の命令を実装すればいったん動くようにできています。ということで、enum を12個用意しました。
また、レジスタも用意します。レジスタは A レジスタ、B レジスタ以外に、キャリーフラグとプログラムカウンタを持っています。
#[derive(Clone)] pub struct Register { register_a: u8, // register a register_b: u8, // register b carry_flag: u8, // carry flag pc: u8, // program counter }
I/O ポートも用意します。TD4 では入力と出力をもっているので、それらを用意します。
pub struct Port { input: u8, output: u8, }
ROM も用意します。これは先ほどもご紹介しましたがもう一度ここに貼っておきます。プログラムの内容そのものを保持しています。
pub struct Rom { pub memory_array: Vec<u8>, }
エントリポイント
今回のプログラムのエントリポイントとして重要なのは CpuEmulator という構造体です。これが実質エミュレータの構造を表現しています。ここに、先ほども説明した fetch-decode-execute サイクルを表現していくとスムーズでした。
まず CPU エミュレータ自体は下記のような構造体です*4。
pub struct CpuEmulator { register: RefCell<Register>, port: RefCell<Port>, rom: RefCell<Rom>, }
まず fetch です。ここでは現状のプログラムカウンタの値を確認し、プログラムカウンタに該当するプログラムを ROM から読み取ります。
(...)
fn fetch(&self) -> u8 {
let pc = self.register.borrow().pc();
if self.rom.borrow().size() <= pc {
return 0;
}
let code = self.rom.borrow().read(pc);
code
}
(...)
次は decode です。ここでバイナリ形式になっているオペレーションコードを解読して、先ほども紹介した内部表現（enum Opcode）に変換をかけます。
(...)
fn decode(&self, data: u8) -> Result<(Opcode, u8), EmulatorErr> {
let op = data >> 4;
let im = data & 0x0f;
if let Some(opcode) = FromPrimitive::from_u8(op) {
match opcode {
Opcode::AddA
| Opcode::AddB
| Opcode::MovA
| Opcode::MovB
| Opcode::MovA2B
| Opcode::MovB2A
| Opcode::Jmp
| Opcode::Jnc
| Opcode::OutIm => Ok((opcode, im)),
Opcode::InA | Opcode::InB | Opcode::OutB => Ok((opcode, 0)),
}
} else {
// never comes
Err(EmulatorErr::new("No match for opcode"))
}
}
(...)
最後は exec です。先ほどの decode の結果をもとに、その Opcode に対応した関数を実行させます。
(...)
pub fn exec(&self) -> Result<(), EmulatorErr> {
loop {
let data = self.fetch();
let (opcode, im) = self.decode(data)?;
match opcode {
Opcode::MovA => self.mov_a(im),
Opcode::MovB => self.mov_b(im),
Opcode::AddA => self.add_a(im),
Opcode::AddB => self.add_b(im),
Opcode::MovA2B => self.mov_a2b(),
Opcode::MovB2A => self.mov_b2a(),
Opcode::Jmp => self.jmp(im),
Opcode::Jnc => self.jnc(im),
Opcode::InA => self.in_a(),
Opcode::InB => self.in_b(),
Opcode::OutB => self.out_b(),
Opcode::OutIm => self.out_im(im),
};
// To prevent infinite loop
if opcode != Opcode::Jmp && opcode != Opcode::Jnc {
self.register.borrow_mut().incr_pc();
}
if self.does_halt() {
return Ok(());
}
}
}
(...)
細々とした各関数の実行内容については、こちらのコードをご覧いただくと、各々の命令がどういった処理を行っているかについて概略を掴むことができるかと思います。
実行自体は、CpuEmulator::with で CpuEmulator の構造体を生成したあとに exec() 関数を呼び出すことによって行われます。program という箇所に、たとえば [00110011, 00000001] のようなバイナリが入ってきて、これを解釈して計算処理が走るというのが、このエミュレータの大まかな構造です。
(...)
let rom = Rom::new(program);
let register = Register::new();
let port = Port::new(0b0000, 0b0000);
let emulator = CpuEmulator::with(register, port, rom);
match emulator.exec() {
Ok(_) => (),
Err(err) => panic!("{:?}", err),
}
(...)
命令コンパイラの実装
さてここからは、本などには載っていない独自コンテンツになります。命令をアセンブラのように書くと、中でコンパイルして CPU エミュレータ用のプログラムに変え、シームレスに計算処理まで紐付けられる実装を追加してみました。
設計
今回の TD4 エミュレータは、バイナリを渡す必要があります。これでも十分楽しめるのですが、せっかくなのでアセンブラのような書き味の形式のファイルを用意して、それを読み込むとコンパイルが走ってバイナリ表現に変えてくれる形式にしてみたら、より使いやすいエミュレータになるのではないかと思いました。
具体的には、下記のようなファイルを読み込ませると、中で加算処理を行い加算結果を返してくれるというようなものです（コメント部分は実際のファイルには入れられません）。
mov A 0001 // 0001 という値を A レジスタに転送する add A 0001 // A レジスタの値と 0001 を加算する mov B A // A レジスタの値を B レジスタに転送する out B // B レジスタの内容を出力する
このファイルを sasm（simple assembly の略のつもり）という拡張子に変えたテキストファイルにして保存しておき、TD4 エミュレータに読ませると、あとは中で任意の計算処理を走らせるようにしました。
なお、出来としてはおもちゃレベルのもので、エラーハンドリングなども結構雑に作ってあります。意図しない構文を入れると普通に落ちると思います。
パース部分の実装
よくあるコンパイラのパーサーのデザインだと思いますが、下記のような構造体を用意しました。私は 9cc を作ったことがあるのですが、それを一部真似しました。
pub struct Parser { pos: usize, // 今どの番地を読んでいるのかを保持する source: Vec<String>, // ファイルから読み込んだ内容を文字列で保持する }
このアセンブラの内容はとてもシンプルなので、空白部分 split をかければ、欲しい内容は一通り抽出できてしまいます。たとえば
mov A 0001
この場合ですと、空白で split をかけると、mov, A, 0001 という文字列が取得できます。TD4 の場合、命令がとても単純なので、たとえば mov の後ろには必ず A か B という文字列が来ているはず、といった感じでシンプルに条件分岐をしながらパースしていくと、一通り命令をパースして解釈できるようになります。
mov の場合のパースの実装例は、たとえば下記のようになっています。パース関数はこちらにあります。
(...)
pub fn parse(&mut self) -> Result<Vec<Token>, EmulatorErr> {
let mut result = Vec::new();
loop {
let op = self.source.get(self.pos);
if op.is_none() {
break;
}
let op = op.unwrap();
if op == "mov" {
self.pos += 1;
let lhs = self
.source
.get(self.pos)
.ok_or_else(|| EmulatorErr::new("Failed to parse mov left hand side value"))?;
self.pos += 1;
let rhs = self
.source
.get(self.pos)
.ok_or_else(|| EmulatorErr::new("Failed to parse mov right hand side value"))?;
let token = if lhs == "B" && rhs == "A" {
Token::MovBA
} else if lhs == "A" && rhs == "B" {
Token::MovAB
} else {
Token::Mov(
Register::from(lhs.to_string()),
self.from_binary_to_decimal(rhs)?,
)
};
result.push(token);
}
(...)
最終的な結果は Token と呼ばれる enum に詰めて返しています。この enum は Opcode とは別物にしてあって、下記のような定義にしました。
pub enum Register { A, B, } pub enum Token { Mov(Register, u8), MovAB, MovBA, Add(Register, u8), Jmp(u8), Jnc(u8), In(Register), OutIm(u8), OutB, }
そしてこの Token は、のちのコンパイルフェーズで一旦バイナリ表現に変換されます。
コンパイル部分の実装
Token ごとに所定のバイナリに変換していきます。たとえば add A 0001 とあったら、まず A レジスタ値との加算命令をしめすバイナリ 0000 とイミディエイトデータ 0001 をくっつけるイメージです。
(...)
pub fn compile(&self, tokens: Vec<Token>) -> Result<Vec<u8>, EmulatorErr> {
if tokens.is_empty() {
return Err(EmulatorErr::new(
"Failed to start to compile because token list is empty.",
));
}
let mut result = Vec::new();
for token in tokens {
let program = match token {
Token::Mov(Register::A, im) => self.gen_bin_code(0b0011, im),
Token::Mov(Register::B, im) => self.gen_bin_code(0b0111, im),
Token::MovAB => self.gen_bin_code_with_zero_padding(0b0001),
Token::MovBA => self.gen_bin_code_with_zero_padding(0b0100),
Token::Add(Register::A, im) => self.gen_bin_code(0b0000, im),
Token::Add(Register::B, im) => self.gen_bin_code(0b0101, im),
Token::Jmp(im) => self.gen_bin_code(0b1111, im),
Token::Jnc(im) => self.gen_bin_code(0b1110, im),
Token::In(Register::A) => self.gen_bin_code_with_zero_padding(0b0010),
Token::In(Register::B) => self.gen_bin_code_with_zero_padding(0b0110),
Token::OutB => self.gen_bin_code_with_zero_padding(0b1001),
Token::OutIm(im) => self.gen_bin_code(0b1011, im),
};
result.push(program);
}
Ok(result)
}
(...)
あとは gen_bin_code などの関数が、指定のバイナリを生成して返すというイメージです。イミディエイトデータを受け取らない命令も TD4 にはあるのですが、その場合は 0000 で詰めればよいことに仕様上なっているので、それ用の関数も用意しました。
やってみた感想
コンピュータの内部については、これを実装してみるまでは全然知らない状態でした。何がどこから読み込まれて計算処理が行われるのかについて、あまり理解できていませんでした。
まず、CPU エミュレータを実装してみたことによって fetch-decode-execute サイクルに関して知ることができ、「このようにしてコンピュータは動いているのか！」と身を持って理解できたように思います。
コンパイラのフェーズは、単に空白を split しただけですし、登場してくる文字列もパターンがかなり定まりきったものを使っただけなので、そこまで難しいことはしていないのですが、自分で1からこうしたコンパイラやインタプリタを作るのは楽しいですね。
ちょっとやってみたいなと思ったものの、実力が足りずにできなかったなと思っているものは、今回用意したアセンブラを吐くプログラミング言語を自分で設計して、そのコンパイラを実装してみるというものです。まだまだプログラミング言語そのものに対する理解や、文法の設計経験などが足りないため難しいです。が、いつか取り組めたらいいなと思いました。
次は RISC-V のエミュレータにもチャレンジしてみています。命令数ははるかに多いですし、考慮しなければならない内容やコードベースもこの TD4 エミュレータと比較すると比ではないくらいに多いのですが、がんばって作りきろうと思っています。
