しかくいさんかく

解答略のメモ

25日目: 自作コンパイラ、自作エミュ、自作CPUの結合

アドベントカレンダー2017 低レイヤ

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の25日目の記事です。

いよいよ最終日。

まず復習を兼ねて、今までの記事を振り返りながら、C言語から半導体までCPUの中を歩く。

最後に自作コンパイラ、自作エミュレータ、自作CPUを結合し、再帰関数でフィボナッチ数を計算する。

25日間の復習

アドベントカレンダーの 初日の記事 に

「普段目にする抽象的なプログラムコードから、CPU内の電圧変動が想像できるようになりたい。」

と書いたので、今までの記事を見返しつつ、C言語から半導体までレイヤーを降りてみる。

C言語からアセンブラまで (18日目-24日目)

C言語のサンプルコード

int main () {
  int a ;
  a = 3 ;
  return 0 ;
}

これを1週間かけてアセンブラに変換した。 作ったコンパイラのリポジトリはこれ。

(18日目) コンパイラ概論

C言語からアセンブラへの変換の概要をまとめた。

(19日目) 字句解析

BNFと呼ばれる、代入可能な正規表現を用いて属性を定義する表を導入した。 これを使ってソースコードに含まれる全単語に属性を付けた。

f:id:kaitou_ryaku:20171219000027p:plain:w300

(20-21日目) 構文解析

トークンの列を構文解析して解析木に変換した。 構文解析に用いたBNFと、再帰降下アルゴリズムで生成された解析木を貼っておく。

f:id:kaitou_ryaku:20171219073600p:plain:w300

f:id:kaitou_ryaku:20171219000052p:plain:w300

(22日目) 抽象構文木

前日の解析木から、冗長な情報を削除した抽象構文木を作った。

f:id:kaitou_ryaku:20171222225753p:plain:w300

(23日目) シンボルテーブル

前日の抽象構文木から、宣言系のノードをまとめたテーブルを作った。

f:id:kaitou_ryaku:20171219000112p:plain:w300

(24日目) コード生成

抽象構文木とシンボルテーブルから、x86のアセンブラのコードを作った。

まず以下のようなテンプレを用意した。

f:id:kaitou_ryaku:20171219000123p:plain:w300

抽象構文木をテンプレに突っ込んで生成された、アセンブラのコードは

bits 32
org 0x0
jmp _main_

_main_:
push ebp
mov ebp, esp
sub esp, 0x10
mov eax, 0x3
... (以下略) ...

これでコンパイラの内部処理を一通り追うことができた。

ここで本来は、アセンブラのコードをx86の機械語に変換するためのリンカを用意しなければならない。 しかし制作意義を見いだせなかったので、gccのリンカを使うことにした。自作したければ、↓の表を見れば簡単に作れる。

アセンブラから「動作」まで (11日目-17日目)

これらの問題と格闘した。

(11日目) x86の概要

x86のアセンブラを機械語に変換するための表を作った。

f:id:kaitou_ryaku:20171211195350p:plain:w500

結局、以下の機械語が得られる。

eb 00 55 89 e5 83 ec 10
b8 03 00 00 00 50 89 45
fc b8 00 00 00 00 50 58
eb 00 f4

(12日目) 数値の扱い

x86で数値を扱う際の注意点をまとめた。リトルエンディアンが気持ち悪かった。

f:id:kaitou_ryaku:20171212022844p:plain:w300

(13日目) ModRM

「誰と誰を足すか」を指定するためのオプションを説明した。

f:id:kaitou_ryaku:20171212024547p:plain:w300

(14日目) 関数呼出

関数呼出にはcall、leave、retの3命令を用いるのだった。

これらはスタックメモリへのpushとpop、そしてmovとjmp命令の組み合わせに過ぎなかった。

f:id:kaitou_ryaku:20171212031332p:plain:w300

(15日目) x86エミュレータの製作開始

リポジトリはこれ。 初日なので大枠を作った。メモリ地図が重要だった。

f:id:kaitou_ryaku:20171212033457p:plain:w300

(16日目) x86エミュレータが完成

昨日作った大枠から呼び出される、機械語の解釈器を作った。全体が完成した。

(17日目) x86 CPUをFPGAで実装

リポジトリはこれ。 実際に作ったのはアドベントカレンダーの開始直前。 ツイッターがバズって驚いた。

twitter.com

以上の工程で、自作コンパイラと、x86風の自作CPUが完成した。この記事の一番下で、これら2つを組み合わせて動作させる。

独自命令セットのCPUの製作(8日目-10日目)

↑でx86風のCPUが完成したわけだが、これはかなり複雑で作るのが大変だった。 そこで今回のアドベントカレンダーでは、x86に取り掛かる前に、プロトタイプとして簡単な命令セットのCPUを作ったのだった。

(8日目) 命令セットの策定

mov, add, sub, cmp, push, pop, jmp, jz, jnz, hlt

の命令セットを持つ8bitのCPUを定義した。

命令の種類は少ないが、十分な汎用性を備えており何でも計算できる。

(9日目) 独自命令セットCPUの製作開始

リポジトリはこれ。 エミュレータ製作の初日と同様に、大枠を作った。 メモリやクロックを用意し、CPUと電圧値をやりとりできるようにした。

(10日目) 独自命令セットCPUが完成

エミュレータ製作の二日目と同様に、機械語の解釈部分を作った。 これは組み合わせ回路になるので、HDLのalways_combブロック内に書く必要があった。

完成後、とりあえずフィボナッチ数を計算した。

twitter.com

機械語からDフリップフロップまで(4日目-7日目)

CPUの回路構成の説明に全力投球した。

極論すると、CPUはDフリップフロップのループであった。

(7日目) 本格的なCPUの回路構成

要するにCPUとは、メモリに格納された機械語を取得し、実行し、取得し、実行し、、、を繰り返す回路だった。

f:id:kaitou_ryaku:20171207221231p:plain:w300

右の線はメモリに繋がっている。 カウンタには読み込むべきメモリのアドレスが保持されている。 命令の実行が終わると「+1」でインクリメントされる。

メモリも含め、コンピュータの全景を一枚にまとめると

f:id:kaitou_ryaku:20171207220420p:plain:w300

(6日目) ALU

ALUとは計算回路のことだった。

特に複数桁を足すための全加算器が重要だった。

f:id:kaitou_ryaku:20171204033024p:plain:w300

(5日目) レジスタの選択

計算回路はCPUの本質ではない(超暴論)ので、取り外して考えると、 mov命令だけが実行できるCPUになる。

見やすさのためにメモリも取っ払うと

f:id:kaitou_ryaku:20171204032911p:plain:w300

これは変数 a, b, c, dの間で値をコピー(mov命令)する回路だ。

コピー元は線Syの電圧値で指定し、コピー先を線Sxの電圧値で指定する。 メモリはこれらの線に繋がっている。

つまり機械語(バイナリ)は、SxとSyの電圧値に対応している。

指定に用いたMUXはマルチプレクサと呼ばれる回路素子で、if 文的な役割を果たしている。

f:id:kaitou_ryaku:20171203220435g:plain:w300

(4日目) 1bit反転CPU

マルチプレクサはCPUの本質ではない(超暴論)ので、取り外して考える。

見やすさのために変数を1種類(aだけ)にする。

さらにNOTゲートを挟むと

f:id:kaitou_ryaku:20171203034104g:plain:w300

今まで変数と読んできた長方形は、Dフリップフロップと呼ばれる回路素子だ。

  • クロックが上がる瞬間に、入力(D)が出力(Q)にコピーされる
  • その瞬間以外は、入力を変えても出力は変わらない

という性質を持つ。結果、回路の挙動は

CPUとは、このように代入→計算→代入→計算→...を繰り返す回路のことだった。

極論すると、CPUとは、Dフリップフロップの出口を入口に繋いだループ回路である。

Dフリップフロップから半導体まで(2,3日目)

DフリップフロップやNANDゲートの半導体構成を説明した。

(3日目) Dフリップフロップ

Dフリップフロップの実装は

f:id:kaitou_ryaku:20171202132712g:plain:w300

つまりNANDゲートとNOTゲートで構成されている。

(2日目) 半導体素子

NANDゲートとNOTゲートの実装は

f:id:kaitou_ryaku:20171201224454p:plain:w150 f:id:kaitou_ryaku:20171201224413p:plain:w150

NOTゲートの回路を、簡略化せずにきちんと描くと

f:id:kaitou_ryaku:20171201224351p:plain:w200

ここに出現するトランジスタは、p型半導体とn型半導体を組み合わせて、以下のように作られている。

f:id:kaitou_ryaku:20171202002144p:plain:w400

さらに下の階層に進むには、量子力学と統計力学の知識が必要になる。 本気でやるなら、周期ポテンシャル下の(多体相関を繰り込んだ)シュレディンガー方程式を解いて、バンド図を描き、輸送係数を調べる必要がある。

以上で低レイヤの解説は終了。

最後に、今までに作成したものを結合してみる。

自作コンパイラ + 自作エミュレータ

10番目のフィボナッチ数を計算するコード(C言語)

int fib(int n);

int main() {
  // 10番目のフィボナッチ数を計算
  int a;
  a = fib(10);

  return a;
}

// 再帰的にフィボナッチ数を計算
int fib(int n) {
  int ret; // ここに計算結果を入れる

  // 前回と前々回のフィボナッチ数を足す
  if (n > 2) {
    ret = fib(n-2) + fib(n-1);
  }

  // fib(1)とfib(2)は1とする
  else {
    if (n == 2) {
      ret = 1;
    }
    else {
      if (n == 1) {
        ret = 1;
      }
    }
  }
  return ret;
}

要するに変数aに10番目のフィボナッチ数を代入するプログラムだ。 else ifが実装されてないので少々読みにくいが、我慢して欲しい。

これを自作コンパイラの minc (リポジトリ) でコンパイルする。

$ ./minc.out fibonacci.c fibonacci.asm

これを機械語に変換して 自作x86エミュレータ (リポジトリ) 上で実行すると

$ nasm fibonacci.asm -o fibonacci.bin
$ ./x86-simulator.out fibonacci.bin

実行結果の末尾を見てみると

Count    : 005078
Operation: 00001E : 0xE9 (jmp imm32)

--- FLAG ---
CF:0 ZF:0 SF:0 OF:0

--- REGISTER ---
eax: 0x00000037
ecx: 0x00000000
edx: 0x0000000A
ebx: 0x00000000
esp: 0x000003E8
ebp: 0x000003FC
esi: 0x00000000
edi: 0x00000000
eip: 0x000000E2

--- STACK MEMORY ---
0003E0: FC 03 00 00 37 00 00 00 37 00 00 00 00 00 00 00
0003F0: 00 00 00 00 00 00 00 00 37 00 00 00 00 00 00 00

重要なのはREGISTERの部分。 eaxの値が0x00000037になっている。 つまり16進数で37、10進数だと16*3+7で55になる。

ところでフィボナッチ数は

1, 1, 2, 3, 5, 8, 13, 21, 34, 55

おお！！10番目のフィボナッチは55だ。 エミュレータで正しく計算できているし、コンパイルには成功したようだ。

命令実行回数はCount: 005078で、約五千回程度。

自作コンパイラ + 自作CPU

さっきのコードを機械語にして自作CPU (リポジトリ) で動かしてみる。

波形シミュレータによる結果は

f:id:kaitou_ryaku:20171225074347p:plain

eaxに0x00000037が入ってる。正しくフィボナッチ数が計算できたようだ。

命令の終了時刻は、約50,780ナノ秒だ。 1クロック10ナノ秒なので、エミュレータによる命令実行回数に一致している。 これは作成したCPUがシングルクロックプロセッサ、つまり1クロック毎に1つの機械語命令を実行しているせいだ。 普通のCPUだと「クロック数 = 命令実行数」みたいな対応関係はないので、注意する必要がある。

これをFPGAの実機で動かしたい。。。が、無理だった。 CPU回路の論理合成には成功したものの、メモリ容量が足りず、インプリメントに失敗した。

(以下は完全に推測だが)メモリが足りなかったのはシングルクロックプロセッサが原因ではないかと考えている。 今回のCPUは1クロックでフェッチすべきメモリデータが多すぎて、データバスが120本という意味不明な構成になっている。 その結果、論理合成時にメモリ機能をフリップフロップで構成しようとして、資源が足りずにエラーをはいてる気がする。

解決するには、1クロックで1byteずつフェッチするようなステートマシンを作ってアドレスバスの本数を減らせば、メモリがメモリアレイで構成されて、問題が解決する。かも。

まぁでも波形シミュレータ上では動いてたし、よしとしよう。 そもそもフィボナッチは 10日目に作ったFPGAのCPU で既に動いてる(下のツイート)し。 全然悔しくないもん(悔しい)1。

twitter.com

最後に

予想外に多くの方々に読んでいただけたようで、感無量です。

最後に一言だけ。

一連の記事は、あくまで私的なメモです。

初心者が書いた記事なので、誤りが多数含まれているはずです。 この記事を盲目的に信じるのはマジでヤバイので、しっかりした教科書を読むべきです。

それでは25日間、ありがとうございました。

  1. ツイートのCPUは、x86ではなく独自命令セットを策定して作ったやつ。フィボナッチもループで計算している。↩