2017-12-19

19日目: [コンパイラ] 字句解析

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

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

今日は字句解析をやる。まず昨日のサンプルコードを人力で字句解析し、コツを掴んだところで実装を説明する。

字句解析とは

昨日のサンプルコード

// C言語風コード
int main () {
  int a ;
  a = 3 ;
  return 0 ;
}

コードに出現する各単語に対し、トークン属性を付与することを字句解析というのだった。

f:id:kaitou_ryaku:20171219000027p:plain:w500

ここで(TYPE_KEYWORD, "int")のようなペアをトークンと呼び、緑字のTYPE_KEYWORDをトークン属性と呼ぶ。

属性の定義は、BNFで与えるのだった。

BNF (バッカス-ナウア記法)

BNFとは「文字列に属性を与える」ために「属性のマッチ条件を正規表現で定義」したものだった。そこでは「定義済みの属性」を他の属性の定義式中に埋め込むことができた。いわば正規表現の代入だ。

昨日のBNFは簡易版だったので、ここに正式版のBNFを貼っておく。

f:id:kaitou_ryaku:20171219062443p:plain

パイプ記号|は正規表現の or を表している。(hoge|piyo)*も正規表現と同じ。

また画像中にも書いたが * int や if という文字列の属性は、IDENTIFYではなくTYPE_KEYWORDやIF_KEYWORDとする * CHAR_ALPHABETとCHAR_NUMBERはIDENTIFYとNUMBERを定義するために導入した一時的属性なので、最終結果には残らない

という二点に気をつけよう。

minc言語誕生

ところで、ここで定義した言語はC言語のサブセットになっている。いや、サブセットというのもおこがましい。なんせ型はintしかないし、配列、ポインタ、構造体等は一切使えない。 #includeも#defineもないし、breakもswitchもない。

しかし、しかしだ！！

変数が使えて、整数が計算できて、関数を定義して呼び出すことも可能な言語になっている。しかもifとwhileが使えるので、構造化定理が発動してgoto文が不要になる。構造化プログラミングができるのだ。 C言語はウルトラリッチな超高級言語だが、今回の言語だって必要不可欠な機能は全ておさえていると思う。特に「アセンブラのコーディングが辛いのを改善する」という目的は十分に果たせる。立派だ。

立派なので名前をつけてやろう。名前はmincにしよう。 C言語を最小限にした言語という雰囲気で命名した。

字句解析 (人力)

字句解析のコツを掴むため、BNFで昨日のサンプルコードを人力解析してみる。

// C言語風コード
int main () {
  int a ;
  a = 3 ;
  return 0 ;
}

まず前処理として改行文字を空白文字に置換する。もしコメント行 // comment や /* comment */があれば、それも空白文字に置換する。

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

ここからBNFによる解析が始まる。まず一番最初にintがある。BNFを上から順に眺めると

TYPE_KEYWORD := "int"

が目に入るだろう。左辺と右辺を := で繋いだ。

次はintとmainの間だが、空白文字を見つけたら、そこまでの単語で字句解析を行い、空白文字はスキップする。つまりintとmainは別のトークンということだ。

次はmainが目に入る。一見すると、BNFの中にmainは見当たらない。しかしmやaといった単体の文字にはCHAR_ALPHABETという属性が定義されている。従ってmainはCHAR_ALPHABETの4連打ということになる。しかし注意したようにCHAR_ALPHABETは字句解析の最終結果に出現しないはずだった。あらためてBNFを見返すと、

IDENTIFY := CHAR_ALPHABET ( CHAR_NUMBER | CHAR_ALPHABET )*

が目に入る。従って mainの属性はIDENTIFYだと分かる。

さて次は(という文字に到達するが、これはBNF表でLPARENになっている。次は)で、RPARENだ。ここで、()の間には空白文字が入っていないかった。字句解析のコードを書く時は、 異なるトークンの間に空白文字が無いこともある ことに注意しなければならない。

この調子で進めていけば、記事冒頭の字句解析結果が得られる。コツは掴めたと思うので、人力から自動化に移ろう。

字句解析の実装

今からC言語でmincの字句解析プログラムを作成する。リポジトリはこれ。

全部追うのは大変なので、大まかな流れだけ書くことにする。

列挙型で属性にエイリアスを貼る

まず以下のような列挙型のTOKEN_KINDをinclude/common.hで宣言した。

typedef enum {
  TERM_OPERATOR   ,
  FACTOR_OPERATOR ,
  COMPARE_OPERATOR,
  ...
} TOKEN_KIND      ;

列挙型(enum)は馴染みがないかもしれないが、要するにTERM_OPERATORのような属性に対し、エイリアスとして整数を割り当てているイメージだ。雰囲気としては

#define TERM_OPERATOR    0
#define FACTOR_OPERATOR  1
#define COMPARE_OPERATOR 2
...

とするのに近い。

トークンの構造体

トークンは単語と属性のペアだった。これを表すために /include/common.hでTOKEN 構造体を宣言した。

typedef struct {
  int kind;
  char str[TOKEN_STRING_MAX_LENGTH];
} TOKEN;

kindの部分に、さっき列挙体で定義した整数(つまりトークンの属性)を入れ、 strの部分に、読んだ文字列を入れる。

コメントの読み飛ばし

mincコードの文字列を受け取り、「次の文字」を取得する関数を用意する。もうすこしちゃんと言うと、

コメント部分に遭遇すると、空白文字を返す
改行文字に遭遇すると、空白文字を返す
その他の文字に遭遇すると、そのまま1文字返す

という関数を作る。

これを src/lexer.cのget_next_char関数で定義した。

次のトークンを取得

mincコードの文字列を受け取り、「次のトークン」を返す関数を作る。その際に、さっき作ったget_next_char関数を呼び出すことでコメントをスキップできる。

これを src/lexer.cのget_next_token関数で定義した。

ここで、C言語のFILE構造体は「ファイルの中身の文字列」と「ファイルの読込現在地」という2つの情報を持つことに注意してほしい。 get_next_token関数は、ファイルの現在地から先方へと伸びるトークンを返す関数になっている。

extern TOKEN get_next_token(FILE *file) {
  TOKEN ret = initialize_token(); // TOKEN構造体を準備。

  int count = 0;
  char ch, ch_more;
  while (true) {          // 無限ループでファイルを1文字ずつ読み込む
    ch = get_next_char(file);

    // 空白文字を読み飛ばす
    if (isspace(ch)) {
      while (true) {
        ch = get_next_char(file);
        if (!isspace(ch)) break;
      }
    }

    if (ch == EOF) break; // ファイルの終端ならループを抜ける

    if      (ch == '+' || ch == '-') {
      add_char_to_token_str(&ret, &count, ch); // ret -> str[*count] = ch する関数
      ret.kind = TERM_OPERATOR;
      break;
    }

    else if (ch == '*' || ch == '/' || ch == '%') {
      add_char_to_token_str(&ret, &count, ch);
      ret.kind = FACTOR_OPERATOR;
      break;
    }
// 略
  }
  ret.str[count] = '\0';
  return ret;
}

全属性のパーサを貼るとえらいことになるので、 TERM_OPERATOR と FACTOR_OPERATOR の部分だけ抜粋した。

複雑な属性をパースするには文字列処理を工夫する必要がある。 BNFとにらめっこしながら頑張って作ろう。

全トークンの配列を取得

前節では、mincソースコードの文字列を入力し、トークンを1つ出力するget_next_token関数を作った。これをループで回せば、ソースコードをトークンの配列が得られる。

このあたりの処理は main関数の最初の方で行っている。

FILE *file;
file = fopen(argv[1], "r");

// 全トークンの数を数える。内部でget_next_tokenを回している
const int max_token_num = count_token_num(file);

// 全トークンの配列を作る
TOKEN *token;
token = (TOKEN *)malloc( sizeof(TOKEN)*max_token_num );
for (int i=0; i<max_token_num; i++) token[i] = get_next_token(file);

fclose(file);

まずトークンの数を数える。これはget_next_token関数を使えば簡単だ。
次にmallocでトークンの配列領域を確保した後、全トークンの配列を読み込む。これもget_next_tokenを使えば簡単に実現できる。

どうでもいい話

今回はBNFの定義に始まり、人力で字句解析し、さらに字句解析プログラムを概要をざっくりと説明した。

今日のところは肩慣らし。明日からの構文解析が本番。そこでは、今日作ったget_next_tokenの超絶複雑版を作る必要がある。心してかかろう。

2017-12-18

18日目: [コンパイラ] ソースコードから機械語までの道筋

アドベントカレンダー2017 低レイヤコンパイラ x86

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

昨日はx86のCPUをFPGA上に実装した。

今日からは、そのCPU上で動く機械語を吐くためのコンパイラを製作していく。昨日まではCPUだのx86だの馴染みのない世界の話を続けてきたが、一気に日常世界にワープした。

製作の準備として、今日はコンパイラ自作最速マスターをやろうと思う。

// 簡単なC言語のソースコード
int main () {
  int a ;
  a = 3 ;
  return 0 ;
}

このソースコードがコンパイラ内部でどのように変換されていくか見てみよう。この内容は、明日以降やる内容のダイジェスト版になっている。

1日目: 字句解析

コンパイラに文字列が渡されると、まず初めに字句解析 (lexical analysis) が実行される。

字句解析とは、あるルールに従ってソースコード内の単語に属性を与えることだ。単語と属性のペアはトークンと呼ばれている。

ここでは以下のルールに従って字句解析を行う。

f:id:kaitou_ryaku:20171219000019p:plain

これはBNFという表記法で書かれた字句解析ルールで、左側で宣言された属性を、右側の正規表現(みたいなやつ)で定義している。 IDENTIFYとNUMBERの定義では、正規表現の(hoge|piyo)*が使われている。

BNFの重要なポイントは正規表現を代入できるところだ。 IDENTIFYとNUMBERの定義の中には、緑文字のCHAR_ALPHABETやCHAR_NUMBERが存在している。正規表現を使って正規表現を定義しているので、一種の代入とみなせるだろう。

このルールを用いてソースコードを字句解析した結果は

f:id:kaitou_ryaku:20171219000027p:plain

各単語に緑文字の属性が付与された。

2,3日目: 構文解析

突然だが、以下の英文を読んで欲しい。

No one in the neighbourhood believed him to be a genius even after he had achieved world-wide fame.

(彼が世界的な名声を得た後でさえ、近隣住民は誰も彼のことを天才だと思わなかった。)

この文章の主語は No one in the neighbourhood だ。 5単語で主語を構成しているが、その中の No one が名詞句で、in the neighbourhood は形容詞句になっている。

文全体:No one in the neighbourhood believed him to be ...
↓
(主語:No one in the neighbourhood, 動詞句:believed him to be, ...)
↓
(名詞句:No one , 形容詞句 in the neighbourhood)

つまり文章はツリー構造を形成している。文法規則に基づき、文章をツリー化することを構文解析という。文章内の各単語の属性(名詞、形容詞等の種類のこと)に対し、SVOやSVOCなどの構文解析ルールを適用することで、ツリー構造が明らかになる。

コンパイラは、これと全く同じ操作をソースコードに対して行っている。前節で行った字句解析は、No→形容詞, one→名詞という操作に対応している。字句解析の結果をもとに構文解析を実行し、ソースコードのツリー構造を明らかにしたい。

ここでの構文解析ルールとして以下のBNFを使うことにしよう。

f:id:kaitou_ryaku:20171219000040p:plain

左側の赤字は、右側の赤字と緑字を用いて再帰的に定義されている。英語に例えると、左辺の赤字で宣言したものは主語や名詞句、形容詞句に対応する。右辺の緑字は名詞や形容詞に対応し、トークン(単語)の属性を表している。混乱を避けるため、今後は緑字をトークン属性と呼び、赤字をノード属性と呼ぶことにする。

この構文解析ルールをもとにソースコードを解析した結果は

f:id:kaitou_ryaku:20171219000052p:plain

構文解析で得られたツリーのことを、解析木という。

4日目: 抽象構文木

解析木は構文解析ルールに基いてソースコードを厳密に解析したものだが、ややこしすぎる。例えば3や0が連なってる部分は不要だろう。

これらのナンセンスな部分を削除し、シンプルなツリーに変換したものを抽象構文木という。

f:id:kaitou_ryaku:20171219000101p:plain:w500

だいぶ見やすくなった。

5日目: シンボルテーブル

抽象構文木の赤枠のノードに着目して欲しい。これらは関数や変数の宣言を表すノードだ。

F_DEC: 関数宣言
V_DEC: 変数宣言
PROTOTYPE: 関数プロトタイプ

これら宣言を表すノードを処理し、情報をまとめたものをシンボルテーブルと呼ぶ。

f:id:kaitou_ryaku:20171219000112p:plain:w400

特に重要なのは、赤で書いた変数のアドレス。アセンブラコードを生成する際に、メモリ上の変数の値を[変数のアドレス]で参照することになる。

6日目: コード生成

抽象構文木に含まれる、宣言以外のノードを処理しよう。

ノード属性毎に処理方法をまとめたテンプレートを作っておくと、処理しやすい。

f:id:kaitou_ryaku:20171219000123p:plain:w600

抽象構文木の頂上はPROGRAMなので、最初に発動するテンプレートもPROGRAMになる。 PROGRAMの下のF_DECについては、シンボルテーブル作成時に処理済みなのでスキップする。次に発動するのはmain関数のテンプレート。こいつはPROGRAMテンプレートの(中のツリー処理)と書かれた部分に埋め込まれる。更にASSIGNやRETURNのテンプレートも発動し、main関数テンプレートの中に埋め込まれる。

こうした手順で抽象構文木にテンプレートを適用していくと、以下のアセンブラコードが生成される。

f:id:kaitou_ryaku:20171219000135p:plain:w300

ここまでくれば、一週間前に解説した x86の命令セット表を参照して即座に機械語に変換できる。

以上でコンパイラの動作説明は終わりだ。処理が数段階に別れているので、1日1ステップずつ詳細を解説しようと思う。

沿革

僕が始めてコンパイラを作ったのは2017年の2月だった。当時のコミットログを載せておく。

日付	時間	進捗
2/05 (日)	13:13	字句解析と構文解析のBNFを策定
2/07 (火)	02:47	字句解析が完了
2/08 (水)	10:41	解析木の生成ルーチンを作り始める
2/09 (木)	19:55	オレオレ単体テストフレームワークを追加
2/10 (金)	-----	解析木のテストコードを書きまくる
2/11 (土)	-----	解析木のコードを書きまくる。
2/12 (日)	-----	解析木がなんとなく完成する(バグだらけ)
2/12 (日)	22:31	抽象構文木の生成ルーチンを作り始める
2/15 (水)	05:27	抽象構文木の生成が完了
2/16 (木)	00:35	シンボルテーブルの作成を開始
2/17 (金)	09:02	シンボルテーブルの作成が完了
2/18 (土)	12:09	コード生成のルーチンを作り始める
2/19 (日)	02:37	関数の再帰呼出によるフィボナッチ数fib(10)=55のコードがコンパイルできた

ちょうど二週間で完成したらしい。一番しんどかったのは解析木の作成だった。今コミットログを見返しても、カオスすぎて何をやってるのかよくわからん。当時、「このままじゃヤバい、先に自動テスト環境を整えよう」という危機感でマクロによるオレオレテストフレームワークを作った。そしてテストコードを量産した後に、懸案の解析木を作るとうまくいった。

どうでもいい話

明日から解説するコンパイラはCで書かれているが、その理由は「Cっぽい言語のコンパイラをC言語で作っておけば、セルフコンパイルできるかも」という儚い夢に基づくものだった。「正規表現ライブラリを使うのは、コンパイラ内部処理を知るという主旨に反するので、禁じ手」というレギュレーションも課した。

こういう野心は大切だと思うけど、今思うと、もっと文字列処理に向いた言語を使ったほう良かったかもしれない。コンパイラの内部処理は変換の連続だし、関数型言語で書くのが簡単だったと思う。

ストイックなことを言えば、コンパイラを自作して内部処理を勉強する際に、既存のCコンパイラを使うのは反則だと思う。

例えば、標準出力の内部処理を理解したいとする。そのときに「C言語のprintf関数を使って標準出力を自作した。よって理解できた」はダメだよね。 printfによって、システムコールのwriteや、その先にあるCPUの割り込みint 0x80が隠蔽されている。 C言語を使っている限り、C言語が隠蔽してしまった構造は見えないのだ。そういう理由により、アセンブラだけで言語処理系を構築しないと真の理解には至らないはずだと思っている。

それでは、明日から字句解析をやっていこう～

2017-12-17

17日目: [x86] CPU (IA-32) をFPGAで製作

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

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

ちょうど1週間前に単純なCPUをFPGAで作った。

そして昨日は x86のエミュレータを完成させた。

この2つを組み合わせて、FPGA上で動くx86のCPUを作ろう。いよいよ本丸に切り込むぞ！！！

x86をHDLで記述する日本語書籍や解説記事は、いまのところ存在しないと思う。先陣を切った。

仕様

全命令を実装するのは大変なので、以下の表の赤い命令にしぼろう。

f:id:kaitou_ryaku:20171217222358p:plain

これらの命令さえあれば、再帰呼出しでフィボナッチ数が計算できる。

基本戦略

負担を軽減するため、前作CPU を改良し、機能を追加する形で実装しようと思う。

前作CPUの命令セットはこの記事に書いた。こいつとx86の相違点をまとめると

解説順	前作CPU	これから作るx86命令セットのCPU
1	レジスタが8bit。フラグはゼロフラグのみ	レジスタが32bit。フラグは4種類
2	クロック毎に全メモリを読む	必要な部分だけ読む
3	機械語の下位4bbitでオペランドを指定	ModRMでオペランドを指定
4	全ての演算処理を`always_comb`内で実行	演算処理を各モジュールに分離
5	条件付きジャンプ命令は`jz`だけ	フラグが増えたので、条件付きジャンプ命令も増える
6	関数呼出は未サポート。`ebp`レジスタは無い	`ebp`レジスタが存在し、`call`, `leave`, `ret`の3命令を含む
7	全演算が簡単につくれる	ModRMの入った演算がしんどい

相違点を中心に、今からソースコードを解説していく。

1. レジスタとフラグの拡張

レジスタの32bit化とフラグの拡張は簡単だ。前作CPUの7だったインデックスを31に変えるだけで済む。この処理は top.svの最初の方で行っている。

// レジスタの宣言
logic [31:0] eax; // FF
// ecx, edx, ebx, esp, ebp, esi, ediを略

logic [31:0] eip; // FF
logic cf, zf, sf, of; // wire

// レジスタ直前のワイヤの宣言
logic [31:0] next_eax; // wire
// ecx, edx, ebx, esp, ebp, esi, ediを略

logic [31:0] next_eip; // wire
logic next_cf, next_zf, next_sf, next_of;

2. メモリフェッチの改善

CPUで演算を行いたい。つまりクロックの立ち上がりでレジスタeaxを上書きしたい。そのためには、更新用のワイヤnext_eaxの電圧を作る組み合わせ回路が必要だった。

この組み合わせ回路は、前作CPUも今作のx86もmake_next_regというモジュール名で統一した。前回はこいつにメモリ全体を渡していた。前回CPUを作ったときの記事の下の方に書いたが、あまりにひどい処理だった。

メモリフェッチ処理を改善し、make_next_regに渡すメモリのサイズを小さくしたい。そのためには top.svの中でオペコードのワイヤを作って

// オペコードのワイヤを作成
logic [7:0] opecode;
assign opecode = memory[eip];

make_next_regの引数に入れて渡せば良い。

make_next_reg make_next_reg_0(
  // 略
  , opecode, imm8, imm32
  , mod, r, m, r_reg, m_reg
  // 略
  , eax, ecx, edx
  // 略
  , next_eax, next_ecx, next_edx
  // 略
);/*}}}*/

ここではopecode以外に、即値やらレジスタやら色々渡している。前回はopecodeを渡す代わりにmemoryを渡していた。とんでもないことだ。

3. ModRMでオペランドを指定

opecodeをmake_next_regに渡し、メモリフェッチを改善することができた。しかしメモリフェッチはopecodeと即値だけではない。ModRMを考慮しなければならない。

ModRMはややこしいので、make_next_regに渡す前に多数のワイヤを作成する必要がある。

そのため、まず top.svの中でModRM関連のワイヤを一挙に宣言する。これらをmake_modrmモジュールに渡すことで、ModRMに関する電圧値を得ている。

logic [ 1:0] mod;
logic [ 2:0] r;
logic [ 2:0] m;
logic [31:0] r_reg;
logic [31:0] m_reg;
logic [31:0] m_reg_plus_imm8 ; // M+imm8
logic [31:0] m_reg_plus_imm32; // M+imm32

logic [ 7:0] around_eip [6:0];
assign around_eip[0] = memory[eip+0];
assign around_eip[1] = memory[eip+1];
assign around_eip[2] = memory[eip+2];
assign around_eip[3] = memory[eip+3];
assign around_eip[4] = memory[eip+4];
assign around_eip[5] = memory[eip+5];

make_modrm make_modrm_0(
  around_eip,
  eax, ecx, edx, ebx, esp, ebp, esi, edi,
  // 略
  mod, r, m, r_reg, m_reg,
  m_reg_plus_imm8, m_reg_plus_imm32
);

modとrとmは分かるだろう。

r_regは3bitのrで指定されるレジスタの出口電圧を表している。m_regも同様。

m_reg_plus_imm8はm_regに1byteの即値imm8を足したものだ。 ModRMの絡んだ命令では、add [m_reg+imm8], Rのようにm_reg+imm8が頻出するので、あらかじめ作っておいた。

これらのワイヤの電圧値を、eip周辺のメモリの値around_eipを元に作成するモジュールがmake_modrmである。

make_modrmモジュールの実装を見てみると

module make_modrm (
// 略
);

  logic  [7:0] modrm;
  assign modrm = memory_eip[1];
  assign mod = modrm[7:6];
  assign r   = modrm[5:3];
  assign m   = modrm[2:0];

  // 略

  // always_comb内では、モジュールのoutputに直接接続できない。
  // なのでワイヤの end_r_reg を宣言して r_reg にかます
  logic [31:0] end_r_reg;
  assign r_reg = end_r_reg;

  // 略

  // end_r_reg に線をつなぐ
  always_comb begin
    case(r)
      3'b000: end_r_reg = eax;
      3'b001: end_r_reg = ecx;
      // 以下、edx, ebx, esp, ebp, esi, ediを同様に処理
    endcase

    //略

  end
endmodule

簡単のために省略改変して記載した。このコードは、ModRMの3bitのRに対応するレジスタを取得し、ワイヤのr_regに繋ぐモジュールだと思ってほしい。処理を追うと

入力のmodrmから、出力のmodとrとmを切り出す
ワイヤのend_r_regを宣言し、r_regの入力につなぐ
case文を使いたいので、always_combの中でend_r_regの入口に線をつなぐ

もちろんr_reg以外にも(m_regなど)作成すべき電圧値はある。実際のmake_modrmモジュールの中では、それらの必要な電圧値を全て作成している。

4. 演算処理を各モジュールに分離

前回作ったCPUのmake_next_regモジュールでは、always_combの中でオペコードによる場合分けを行っていた。 System Verilogの仕様上、alwaysの中ではモジュールを呼び出せないので、必要な演算処理を全てalways_comb中にべた書きする必要があった。いかにも不格好だ。

今回はスマートにやろう。命令毎にモジュールに分割する。

昨日のx86 エミュレータ製作を思い出してほしい。そこでは「演算処理の構造体を作り、配列にして、添字をオペコードにする」というテクニックを使っていた。

これと同様に「演算処理のワイヤを作り、配列にして、添字をオペコードにする」というテクニックを使えば、always_comb内のcase文を使うことなく分岐することが可能になる。

つまり

クロック毎に全種類の演算を行う
結果を「演算処理のワイヤの配列」に格納する。添字は計算種別に対応する1byteのオペコードにする
メモリから取得したオペコードをもとに、「欲しい計算結果のワイヤ」を得る
取得したワイヤの電圧値で、次回クロック立ち上がりの瞬間にレジスタを上書き

こうすることで「演算処理のワイヤを作る」部分を命令毎にモジュール化できて、可読性が向上する。

説明が抽象的でわかりにくいかもしれない。コードを見よう。

make_next_reg.sv の全体像を見ると

// opecode, eax等からwrite_flag, next_eax等を作る組み合わせ回路

module make_next_reg(
  output   wire        write_flag
  , output wire [31:0] write_addr
  , output wire [31:0] write_value
  // 略
  , output wire [31:0] next_eax
  // 略
);

  // next 更新用の多重ワイヤを宣言
  logic        end_write_flag[255:0];
  logic [31:0] end_write_addr[255:0];
  logic [31:0] end_write_value[255:0];
  logic [31:0] end_eax [255:0];
  // 略

  // 多重ワイヤのうち、opecodeに合致するものをnextに繋ぐ
  assign write_flag  = end_write_flag[opecode];
  assign write_addr  = end_write_addr[opecode];
  assign write_value = end_write_value[opecode];
  assign next_eax    = end_eax[opecode];
  // 略

  // 全種類の計算を実行。まずはaddの結果をend_***[01]に入れる
  inst_01_add_M_imm_R inst_01_add_M_imm_R_0(
    , mod, m, r_reg, m_reg                // modRM関連の他の引数を略
    , end_write_flag[8'h01], end_write_addr[8'h01], end_write_value[8'h01]
    , eax, ecx                            // レジスタ関連の引数を略
    , end_eax[8'h01], end_ecx[8'h01]      // レジスタ更新用ワイヤの引数を略
  );

  // 略 (jmpやmovの結果も、end_***[***]に入れる)
endmodule

「演算処理のワイヤの配列」はend_eax [255:0]などの、endで始まるワイヤ配列を指している。配列サイズを256にしたのは、オペコードが0x00から0xffまでの256種類(1byte)だからだ。

5. 条件付きジャンプ命令

さっきのコードの最後で、inst_01_add_M_imm_Rというモジュールをよtl出していた。こいつはadd [M+imm], Rという命令を処理するモジュールなのだが、ModRMが入っていてややこしい。詳細は記事の最後に回そう。

変わりに jcc imm32の命令を処理するモジュールの実装を見てみる。

// jcc imm32
module inst_0f_jcc_imm32(
  input    wire [31:0] imm8
  , input  wire [31:0] modrm_imm32
  , output wire        next_write_flag
  , output wire [31:0] next_write_addr
  , output wire [31:0] next_write_value
  , input  reg  [31:0] eax      // input ecx, edx, ... , of を略
  , output wire [31:0] next_eax // output next_ecx, next_edx, ... , next_of を略
);

  // eip以外は前回の値を保持
  assign next_write_flag  = 0;
  assign next_write_addr  = 0;
  assign next_write_value = 0;

  assign next_eax = eax;
  // ecx, edx, ... , of も同様に前回の値を保持する。略

  logic [31:0] e_eip;
  assign next_eip = e_eip;

  logic [31:0] no_jump;
  assign no_jump = eip + 6;

  logic [31:0] jump;
  assign jump = eip + 6 + modrm_imm32;

  always_comb begin
    case(imm8)
      8'h80: e_eip = (of == 1) ? jump : no_jump;
      8'h81: e_eip = (of == 0) ? jump : no_jump;
      8'h82: e_eip = (cf == 1) ? jump : no_jump;
      8'h83: e_eip = (cf == 0) ? jump : no_jump;
      // 他の条件付きジャンプは略
      default: e_eip = no_jump;
    endcase
  end
endmodule

jmp imm32の機械語命令を復習しよう。例えばメモリアドレス 0x12345678 に条件付きジャンプする命令だと

アドレス	`eip`						`no_jump`
名前	`opecode`	`imm8`	`modrm_imm32[3]`	`[2]`	`[1]`	`[0]`
中身	0f	80から8fの間	78	56	34	12	次の命令

このimm8の値に応じて、ジャンプの条件式(a>bかa<bか)が定まっている。

これを実現するために

メモリには何も書き込まない
eax, ecx 等のレジスタも前回の値を保持
フラグも変更しない
プログラムカウンタeipを、imm8とフラグを比較して書き換える

という処理を行っている。

6. 関数呼出

関数呼出の解説記事を読み返してほしいのだが、関数を呼ぶにはcallしてleaveしてretすればよかった。

これらの実装をメモしておく。

call

実装はこれ。この命令はpushで「callの次の命令」をスタックに積んだあと、jmp imm32するのと等価だった。

// module文を省略

assign next_write_flag  = 1;
assign next_write_addr  = esp-4;
assign next_write_value = eip+5; // call命令の一個下のeipを入れる

assign next_esp         = esp-4;
assign next_ebp         = ebp;
assign next_eip         = (eip+5) + imm32;
// 他のnext_***は前回の値を保持

leave

実装はこれ。この命令はmov esp, ebpしたあとpop ebpするのと等価だった。

// module文を省略
// next_write_***は前回の値を保持

assign next_esp = ebp+4;
assign next_ebp = ebp_leave_value;
assign next_eip = eip+1;
// 他のnext_***は前回の値を保持

ret

実装はこれ。この命令はpop eipと等価だった。

// module文を省略
// next_write_***は前回の値を保持

assign next_esp = esp+4;
assign next_ebp = ebp;
assign next_eip = stack_value;
// 他のnext_***は前回の値を保持

7. ModRMの入った演算

最後にadd [M+imm], R命令を処理するモジュールinst_01_add_M_imm_Rを説明する。

今日の記事の「4. 演算処理を各モジュールに分離」のところで出てきた命令だが、だいぶややこしい。 ModRMが入るとしんどいのだ。

inst_01_add_M_imm_Rの実装を見てみると

module inst_01_add_M_imm_R(
  input    wire [ 1:0] mod              // modRMのmod (0,1,2,3)
  , input  wire [ 2:0] m                // modRMのM (0~7)
  , input  wire [31:0] r_reg            // modRMのRで指定されるレジスタの出口
  , input  wire [31:0] m_reg            // modRMのMで指定されるレジスタの出口
  , input  wire [31:0] m_reg_plus_imm8  // M+imm8のメモリアドレス
  , input  wire [31:0] m_reg_plus_imm32 // M+imm32のメモリアドレス
  , input  wire [31:0] memval_m_reg     // [M] のメモリの値
  // modrm系のinputを略

  , output wire        next_write_flag  // メモリに書き込む時は1, さもなくば0
  , output wire [31:0] next_write_addr  // メモリに書き込むアドレス
  , output wire [31:0] next_write_value // メモリに書き込む値
  , input  reg  [31:0] eax              // eaxレジスタの出口
  // レジスタ系のinputを略

  , output wire [31:0] next_eax         // 次回クロックのeaxレジスタの入口
  // 更新用ワイヤのoutputを略
);

  // always_comb内で直接next_***に繋ぐことはできないので、e_***をかます
  logic        e_write_flag;
  logic [31:0] e_write_addr;
  logic [31:0] e_write_value;
  logic [31:0] e_eax;
  // 略

  assign next_write_flag  = e_write_flag;
  assign next_write_addr  = e_write_addr;
  assign next_write_value = e_write_value;
  assign next_eax         = e_eax;
  // 略

  // e_***に線を繋いで、間接的にnext_***を書き換え
  always_comb begin
    case(mod[1:0])

      // add [M], R の処理
      2'b00: begin
        e_write_flag  = 1;     // メモリの書き込みフラグを立てる
        e_write_addr  = m_reg; // 書き込むアドレスはレジスタMの値そのもの
        e_write_value = memval_m_reg + r_reg; // [M]=[M]+R

        e_eax = eax;   // eax, ecx, ... は前回の値を保持
        e_ecx = ecx;
        // 略
        e_edi = edi;

        // プログラムカウンタの更新
        // メモリ上の機械語は (HERE_ope) (ModRM) (NEXT_ope) なので+2する
        e_eip = eip+2;

        // 略
      end
      // modが01, 10, 11の処理は略
    endcase
  end
endmodule

混乱した場合は、今日の記事の「5. 条件付きジャンプ命令」のセクションを再読して欲しい。あそこではe_eipというワイヤを宣言し、always_comb中でその電圧値を作成していた。

そこで出てきたe_eipと全く同様に、e_write_flagやe_eaxを宣言し、always_comb中で電圧値を更新している。

重要なのはalways_combの中身だが、冗長になるので、mod=00に該当するadd [M], Rの処理だけを載せた。この場合

e_write_flag  = 1;     // メモリの書き込みフラグを立てる
e_write_addr  = m_reg; // 書き込むアドレスはレジスタMの値そのもの
e_write_value = memval_m_reg + r_reg; // [M]=[M]+R

always_comb中で、e_write_***のメモリ更新用ワイヤに電圧値を設定することで、メモリに値を書き込んでいる。

どうでもいい話

x86のCPUをFPGA上に実装する方法を書いたけど、一回の記事としては分量が多すぎたと思う。

よくわからなかった場合は前作CPUの作成記(前半) (後半)。を読み直して欲しい。複雑になっただけで、難しくなったわけではない。 ModRM周りを除けば前作CPUと全く変わらない。

今日でCPUの話題は終了だ。 x86のエミュレータも作ったし、FPGAで実装したし、一区切りつけるにはちょうどいい。明日からはコンパイラの自作だ。製作時の記憶がかなり失われているので、頑張らなきゃな。

2017-12-16

16日目: [x86] エミュレータ製作 (完成)

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

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

昨日の86のエミュレータ製作の続きをやる。

昨日の最後に解説した、機械語を順番に実行する部分を再掲すると

for (int i = 0; i < 100000; i++) {
  const int opecode = readmem_next_uint8(&emu);
  ope[opecode].func(&emu);
  if (opecode == 0xF4) break;
}

整数opecodeは、実行する機械語(1byte)を表す
この整数を配列の添字とするope[opecode]は、機械語を解釈実行する構造体を表す
構造体のメンバ関数funcにより、エミュレータの本体emuを更新

このループで、機械語のフェッチ→実行→フェッチ→実行を繰り返しているのだった。

今日は機械語を解釈する構造体opeを作る。これさえできれば、昨日の記事とあわせてエミュレータは完成だ。

`ope`構造体配列の初期化

昨日の「ニーモニックの解釈」のセクションに書いたように、main関数内で ope構造体を作成していた。

これを行うinitialize_OPECODE関数はここで定義されている。

void initialize_OPECODE(OPECODE ope[OPECODE_NUM]) {

  // デフォルトの関数ポインタを not_defined_halt にする
  for (int i=0; i<OPECODE_NUM; i++) {
  ope[i].mnemonic  = "NOT_DEFINED";
  ope[i].func      = not_defined_halt;
  }

  // calc
  ope[0x01].mnemonic = "add [M+imm], R";
  ope[0x01].func     = add_Mimm_R;
  ope[0x09].mnemonic = "or  [M+imm], R";
  ope[0x09].func     = or__Mimm_R;
  // 略
}

初めに、未定義関数を表すnot_defined_haltでope配列全体を初期化している。

その後、命令セット表の

オペコード	ニーモニック
0x01	add [M+imm], R
0x09	or [M+imm], R
...	...

これらの情報を元に、ope配列を上書きしている。

`ope`構造体のメンバ関数 `func`

実際に機械語命令を実行するのは、ope構造体のfuncだった。これは関数ポインタとして実装されていた。

つまりさっきのコードの

ope[i].func    = not_defined_halt;
ope[0x01].func = add_Mimm_R;
ope[0x09].func = or__Mimm_R;

これらの右辺値は機械語を実行する関数だ。

まずはデフォルトの not_defined_haltの実装を見てみると

static void not_defined_halt(EMULATOR *emu) {
  EXIT_MSG("opecode NOT DEFINED. halt\n");
}

未定義の機械語に遭遇すると、エラーメッセージをはいて強制終了する。ちなみにEXIT_MSG()は僕が適当に作った非標準的なマクロなので、参考にしないほうがいい。

add [M+imm], R を処理する関数

次に機械語0x01に対応する、 add_Mimm_R関数の定義を見てみる。

この命令は一昨日の記事の[M+imm], R 型のセクションで詳しく解説したので、再読してから以下のコードを見て欲しい。

ニーモニックとModRMに関する画像を再掲しておく。

f:id:kaitou_ryaku:20171212024547p:plain

これを処理する関数は

static void add_Mimm_R( EMULATOR *emu) {
  MODRM m = read_modrm(emu);

  if        (m.mod < 3) {
    // add [M+imm], R ; 01 b([00~10] R M) none/imm8/imm32
    const uint32_t mem = modrm_M_imm_to_addr(m, emu);
    const uint32_t src = readmem_uint32(mem, *emu);
    update_flag(src, *m.R, emu);
    writemem_uint32( mem, src + *m.R, emu);

  } else if (m.mod == 3) {
    // add M, R ; 01 b(11 R M)
    update_flag(*m.M, *m.R, emu);
    *m.M += *m.R;
  }
}

上から順に処理を見ていく。

ModRMの処理

add_Mimm_R関数内では、まず最初にMODRM mという構造体を定義している。 read_modrm関数は、メモリから次の1byte(8bit)を読み込み、MODRM構造体を返す関数だ。

MODRM 構造体の宣言は

typedef struct {
  uint8_t modrm;
  uint8_t   mod;
  uint8_t raw_r;
  uint8_t raw_m;
  uint32_t   *R;
  uint32_t   *M;
} MODRM;

メンバのmodrmはメモリの8bitの値そのもので、modとraw_rとraw_mはmodrmを三分割したビット列を表している。 *Rと*Mはemu構造体メンバに含まれる汎用レジスタeax等へのポインタである。 raw_r,raw_mとレジスタの対応は

`raw_r` or `raw_m`	レジスタ	`raw_r` or `raw_m`	レジスタ
000	eax	100	esp
001	ecx	101	ebp
010	edx	110	esi
011	ebx	111	edi

これを読み取る read_modrm関数は、ビット列をガチャガチャの操作して実装した。

[M+imm]のメモリアドレスを取得する処理

ModRMを取得したあとは、「何と何を足すか」をmodの値で場合分けしている。 modが0,1,2なら加算結果をメモリ[M+imm]に書き込み、3の場合はレジスタMに書き込む。

mod 二進表示	mod 十進表示	`[M+imm]`の型
00	0	[レジスタ]
01	1	[レジスタ+imm8]
10	2	[レジスタ+imm32]
11	3	レジスタ

メモリに書き込む部分の処理を見てみると

if (m.mod < 3) {
  // add [M+imm], R ; 01 b([00~10] R M) none/imm8/imm32
  const uint32_t mem = modrm_M_imm_to_addr(m, emu);
  const uint32_t src = readmem_uint32(mem, *emu);
  update_flag(src, *m.R, emu);
  writemem_uint32( mem, src + *m.R, emu);
}

まず[M+imm]に対応するメモリアドレスをmodrm_M_imm_to_addr関数で取得している。この関数の実装は

static uint32_t modrm_M_imm_to_addr(const MODRM m, EMULATOR *emu) {
  cut_esp_0x24(m.M, emu);
  uint32_t mem;
  if      (m.mod == 0) mem = *m.M;
  else if (m.mod == 1) mem = *m.M + (int8_t)readmem_next_uint8( emu);
  else if (m.mod == 2) mem = *m.M +         readmem_next_uint32(emu);
  else EXIT_MSG("ModRM Error. ModRM's M must be address. Therefore mod should not be 3\n");
  return mem;
}

最初にcut_esp_0x24を呼び出している。これはModRMのMがespレジスタを表す場合にSIB拡張が発動するので、その対応用の関数なのだが、うーむ。一昨日の記事の一番最後に書いたように、x86にはModRMを拡張したSIB拡張があり、それを無視する処理をcut_esp_0x24で行っている。要するに、ModRMの次に0x24という1バイトの値が来るので、それを読み飛ばす処理だ。この辺は深く考えないで欲しい。

cut_esp_0x24のあとは、メモリアドレスを表すmemを宣言し、ModRMを元に値を計算し、returnしている。素直な処理なので読めばわかるだろう。

加算結果をメモリに書き込む処理

まず、取得したアドレスmemの指すメモリの値を、readmem_uint32関数を用いてsrcに読み込む。次にModRMのRレジスタの値とsrcを足して、結果をwritemem_uint32でメモリに書き込んでいる。

その際、計算結果に応じてcarry, overflow, sign, zero の4つのフラグを更新しなければならない。この処理は update_flag関数で行っている。重要な部分だけ抜粋すると

// rnd1+rnd2でflagを更新
const int sign_1      = rnd1 >> 31;
const int sign_2      = rnd2 >> 31;

const uint64_t result = (uint64_t)rnd1 + (uint64_t)rnd2;
const int sign_result = (result >> 31) & 1;

FLAG flag = {0,0,0,0};
flag.carry    = (result >> 32) & 1;
flag.overflow = (sign_1 == sign_2 && sign_1 != sign_result);
flag.sign     = (sign_result == 1);
flag.zero     = (rnd1 + rnd2 == 0);

// あとはflagを`emu.eflags`に書き込むだけ

フラグ更新の詳細は、数値関係の記事の「キャリーフラグ」「オーバーフローフラグ」「比較条件」のセクションに詳しく書いた。まとめておくと

フラグ名	`rnd1+rnd2`の結果、フラグが立つ条件
carry	加算結果が符号なしの32bit整数からはみ出る
over flow	加算結果が符号付きの32bit整数をはみ出る
zero	加算結果が0になる
sign	加算結果が符号付き32bit整数の負値になる

キャリーフラグについては、加算時にbit拡張して桁あふれするか調べれば良い。

オーバーフローフラグについては、rnd1, rnd2の符号から予想される加算結果と、実際の結果が一致するか調べれば良い。もしrnd1 > 0, rnd2 > 0なら予想は正だし、rnd 1 < 0, rnd 2 < 0なら予想は負だ。従ってフラグの立つ(予想の外れる)条件は

sign_1 == sign_2
&&
sign_1 != sign_result

となる。

フラグの値が得られたので、最後にeflagsをflagで上書きする。大した処理ではないので説明は省く。

レジスタに書き込む処理

ここまでadd [M+imm], Rのmodが0,1,2の場合を見てきた。modが3の場合も一応見ておこう。この場合ニーモニックはadd M, Rとなる。レジスタとレジスタを足して、結果をレジスタに代入する命令だ。

else if (m.mod == 3) {
  // add M, R ; 01 b(11 R M)
  update_flag(*m.M, *m.R, emu);
  *m.M += *m.R;
}

update_flag関数でフラグを更新した後、素直に*m.M += *m.Rとしている。

sub命令とcmp命令

ここまで加算命令を見てきた。

今回つくるエミュレータの中で、加算以上に難しい命令はない。

命令セット表を再掲すると

f:id:kaitou_ryaku:20171211195350p:plain

他の重要な計算命令にsubとcmpがある。これらは、第二オペランドの符号を反転(2の補数)したあとに加算すれば実装できる。 2の補数の実装は

uint32_t neg_uint32(const uint32_t arg) {
  return bit_reverse_uint32(arg) + 1;
}

わざわざこんな関数作らず普通にマイナスしてもよいと思う。

push命令とpop命令

スタック領域はメモリの最後尾に準備されるので、push時にはespを減らし、pop時には増やせばよい。意味が分からなければ昨日の記事の「エミュレータのメモリに機械語を読み込む」のセクションを再読してほしい。

f:id:kaitou_ryaku:20171212033457p:plain

この緑のスタック領域に対し、pushやpopを実装する。

push eaxの実装は

static void push_eax(EMULATOR *emu) {
  *(emu -> esp) -= 4;
  writemem_uint32( *(emu -> esp), *(emu -> eax), emu);
}

pop eaxの実装は

static void pop_eax( EMULATOR *emu) {
  *(emu -> eax)  = readmem_uint32(  *(emu -> esp), *emu);
  *(emu -> esp) += 4;
}

スタックには4byte(32bit)の値を積むので、espは4ずつ増減している。

ジャンプ系命令

ジャンプ命令とは、次回読む機械語のアドレスを変更する命令であり、そのためにはプログラムカウンタのeipを変更すればよかった。

jmp imm32の実装は

// jmp
static void jmp_imm32(EMULATOR *emu) {
  // jmp  0x5 ; e8 05 00 00 00 (普通に命令更新した後のeipからの差分をimmで与える)
  uint32_t imm32 = readmem_next_uint32(emu);
  *(emu -> eip) += imm32;
}

jmp命令のオペランドは、次回読むメモリアドレスとの差分であり、さっき読んだメモリアドレスとの差分ではない。間違いやすいので、jmp 0 は nop と同じ と覚えるのが良いだろう。¹。この対応は自然だと思う。

条件付きジャンプは、フラグの値に応じてジャンプするかどうか決める命令だった。特に重要なのはjl, jge, jle, jgの四種類で、C言語のint型整数a,bとの対応がある。

機械語	ニーモニック	C言語
0x7c imm8	jl imm8	if (a < b)
0x7d imm8	jge imm8	if (a >= b)
0x7e imm8	jle imm8	if (a <= b)
0x7f imm8	jg imm8	if (a > b)

これらの実装のうち、jl imm8だけを書くと

static void jl__imm8(EMULATOR *emu) {
  //7c ff
  // cmp a, bにより a-b の結果でフラグ更新した後に実行

  const int8_t imm8 = readmem_next_uint8(emu);
  int SF = read_flag(FLAG_NAME_SIGN    , *emu);
  int OF = read_flag(FLAG_NAME_OVERFLOW, *emu);
  if (SF != OF) *(emu -> eip) += imm8;
}

ここでif (SF != OF)という条件式がif (a < b)に対応している。この証明は 4日前の記事の「符号付き整数の大小関係」のセクションに書いた。

関数呼出

2日前の記事でcall, leave, retの3つの命令を説明した。

結局これらの命令は、以下のスタックとレジスタの操作に分解できるのだった。

関数呼出	対応する操作
`call imm32`	`push eip+4`したあと`jmp imm32`
`leave`	`mov esp, ebp`したあと`pop ebp`
`ret`	`pop eip`

call imm32の実装は

static void call_imm32(EMULATOR *emu) {
  uint32_t imm32 = readmem_next_uint32(emu);
  *(emu -> esp) -= 4;
  writemem_uint32( *(emu -> esp), *(emu -> eip), emu);
  *(emu -> eip) += imm32;
}/*}}}*/

1行目のreadmem_next_uint32は、ジャンプしなかったと仮定した場合の、次回読み込む機械語のメモリアドレスを取得する関数。その後のスタック操作はpush命令の解説を読めば分かるだろう。

leaveの実装は

static void leave(EMULATOR *emu) {
  *(emu -> esp) = *(emu -> ebp);
  pop_ebp(emu);
}

retの実装は

static void ret_near(EMULATOR *emu) {
// pop eip
  *(emu -> eip) = readmem_uint32( *(emu -> esp), *emu);
  *(emu -> esp) += 4;
}

どちらも素直な処理なので、読めばわかると思う。

これでエミュレータは一通り完成した。めでたい。

どうでもいい話

駆け足だったが、x86のエミュレータ製作の重要なポイントは解説できたと思う。結果を表示する関数については全く触れなかったが、そこは各人の趣味にあわせて適当に作って欲しい。 main関数のループの中に、表示したい情報をprintfする関数を入れれば良い。

ところで、このアドベントカレンダーは低層(トランジスタ回路)から高層(C言語)に向かって毎日階段を登っている。エミュレータはその中間地点だ。しかしこれは、僕が実際に制作した順番とは大きく異なっている。

僕はまず最初にtd4と呼ばれる超単純なCPUのエミュレータ(1時間あれば作れる)を作った。そこでコツを掴んでからx86のエミュレータを作った²。一通り完成させた後に https://book.mynavi.jp/ec/products/detail/id=41347

という本の存在を知った。機械語命令表を関数ポインタで実装する手法を知り、目からウロコだった。switch文はいらんかったんや。。

振り返ると、低レイヤの入口として最も良い題材はエミュレータの製作だと思う。これをしっかり作ったことで、FPGAやコンパイラに挑戦する前段階として、CPUの挙動が直感的につかめるようになった。

そういうわけで、みんなもエミュレータを作ろう～

命令長は異なる。nopは1byteだが、jmp 0は即値の分だけ命令長が伸びる。↩
何事もトイモデルからスタートするのが、良いものを素早く作るための鉄則だと信じている。↩

2017-12-15

15日目: [x86] エミュレータ製作 (前半)

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

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

昨日まではx86の命令セットの解説をしていた。重要な命令は概ね紹介できたと思う¹。ざっくり振り返ると、CPUが実行できる命令は

機械語をメモリから読み込む
メモリorレジスタから値を読む
値を算術演算する
値をメモリorレジスタに入れる

これらの動作の組み合わせになっていた。

せっかく x86の命令を調べたし、それを再現するようなCPUを作りたくなる。いきなりFPGAで作っても良いのだが、あれはしんどいので、まず手始めにCPUと似た動作をするやつをソフトウェア的に作ろうと思う。要するに機械語を読み込んで命令を解釈し、算術演算に基づいてレジスタ/メモリの値を操作し、処理を終えたら次の機械語を読む、、、という動作を繰り返す、CPUと似た動きをするプログラムを作りたい。そうした疑似CPUのことをエミュレータという²。一口にエミュレータと言っても、どのレベルでCPUを再現するかに応じて種類がある。ストイックな順に並べると

トランジスタの電圧変動をリアルタイムで忠実に再現(超ストイック)
クロック毎のNANDゲートのOn/Offを再現(かなりストイック)
機械語を実行した結果、レジスタがどうなるかを再現

1や2のようなエミュレータを作るのは、FPGAでCPUを作るのと似た作業になるだろう。たとえば機械語のadd命令を再現するために全加算器を作る必要が生じる。これは大変だ。

今回は3番目の機械語を実行した結果、レジスタがどうなるかを再現するようなエミュレータを作ろうと思う。この場合、add命令を再現するのに全加算器はいらない。a=a+bのように普通に値を足せばよい。つまりレジスタとメモリの状態を再現するのが目的であり、そのための手段は問わない。

こういうエミュレータは簡単に作れて、しかも役立つ。ご利益を列挙すると

FPGAでCPUの回路を作る際に、回路シミュレータと自作エミュレータでメモリの値が一致するかチェックできる
ある機械語を実機で動作させる前に、自作エミュレータで結果をチェックできる
自作コンパイラの吐いたコードが正しく動くかチェックできる

要するにCPUとコンパイラのデバッグを行う時に、ものすごく役立つのだ。これらを自作したいのなら、あらかじめエミュレータを書いておくとスムーズに進むだろう。

タイトルでエミュレータなどと銘打ったが、実際に作るのはデバッガに近い。 C言語をgcc -gでコンパイルしてgdbでステップ実行し、i rでレジスタの状態を見るような感じ。

予定

今後の予定だが、まず今日はmain関数を解説し、エミュレータの大枠を説明する。明日は機械語の解釈部分を説明し、完成する見込み。前回FPGAでCPUを作ったときと全く同じ流れだ。

今日の内容を要約すると

エミュレータ本体の構造体 emu を初期化
外部ファイルからemu.memoryに機械語を読み込む
機械語を解釈する構造体 ope を初期化 (詳細は明日)
機械語をemu.memoryを行ずつ実行 (詳細は明日)
emuとopeを解法

これらを実行するC言語のプログラムを書いた。 Cを選んだ深い理由はないけど、後にCで書いた自作コンパイラを解説する予定なので、あわせておいた。

エミュレータの本体部分

解説に移る。リポジトリはこれだ。

今日はmain関数の中身を追うと言ったが、その最初の処理は

EMULATOR emu;
initialize_EMULATOR(&emu);

エミュレータ本体を表す構造体を作り、初期化している。この構造体は include/common.h で以下のように宣言されている。

typedef struct {
  uint32_t *eax;
  uint32_t *ecx;
  uint32_t *edx;
  uint32_t *ebx;
  uint32_t *esp;
  uint32_t *ebp;
  uint32_t *esi;
  uint32_t *edi;
  uint32_t *eip;
  uint32_t *eflags;
  uint8_t *memory;
} EMULATOR;

意味は 11日目の記事のレジスタの種類のセクションを読めばわかると思う。各種レジスタは32bit(4byte)で、メモリは8bit(1byte)の配列として実装した。 initialize_EMULATOR ではレジスタやメモリ(ややこしいので以下ではemu.memoryと書く)をmallocしてゼロで初期化している。ただしemu.espだけはemu.memoryのアドレスの最大値で初期化している。理由はスタックがメモリ空間の末尾に準備されるせい³なのだが、忘れた人のために次のセクションで詳しく説明する。

エミュレータのメモリに機械語を読み込む

emuを初期化したので、次は emu.memoryに機械語を読み込む。機械語のファイルを開いて、サイズ(全体で何バイトか?)をbin_sizeに格納した後、fread関数を使ってemu.memoryに中身を読み込んでいる。

FILE *bin;
bin = fopen(argv[1], "rb");

// 機械語のサイズを取得
fseek(bin, 0, SEEK_END);
const int bin_size = ftell(bin);
rewind(bin);

// 機械語をemu.memoryに読み込み
// INIT_EIP_ADDRESSはデフォルトで0
fread(emu.memory + INIT_EIP_ADDRESS, 1, bin_size, bin);
fclose(bin);

ここで重要なのは、emu.memoryのどこに機械語を読み込むかだ。例えば全メモリが1MB(0x000000から0xFFFFFF)だとすると

f:id:kaitou_ryaku:20171212033457p:plain

emu.memoryの0番地から正の方向に機械語ファイルの中身をコピー
開始時点のeipは0x000000
emu.memoryの0xFFFFFF番地から負の方向にスタック領域を確保
開始時点のespは0xFFFFFF

というメモリ配置になる。「関数本体」と「グローバル変数」で分けられているが、これは気にしなくて良い⁴。ひっくるめて「機械語ファイルの中身」だと思って欲しい。

ニーモニックの解釈

次は機械語命令を解釈する部分だ。これは配列と関数ポインタで実装した。

OPECODE ope[OPECODE_NUM];
initialize_OPECODE(ope);

たとえば1byteの機械語命令0x01を読み込んだ時に、ope[0x01]を使うことで処理が行えるようになっている。

構造体OPECODEは include/common.h で宣言されており

typedef struct {
  char     *mnemonic;
  void     (*func)();
} OPECODE;

重要なのはvoid (*func)());の部分。関数ポインタを使って、少々トリッキーなことをやっている。この辺の詳細は明日話すことにしよう。

機械語を実行

最後に、 emu.memoryに読み込んだ機械語を実行していく。

for (int i = 0; i < 100000; i++) {
  const int opecode = readmem_next_uint8(&emu);
  ope[opecode].func(&emu);
  if (opecode == 0xF4) break;
}

forループの中では、まずemu.memoryのemu.eip番地のアドレスを参照し、opecodeという変数に入れている。たとえばopecodeの値が64の場合、16進数で0x40なので、ope[opecode]はinc eaxという処理に対応する。

ループの最後にbreak文がある。これはもし読み込んだ機械語が0xF4ならばニーモニックはhltなので、停止処理を実行している。

以上でエミュレータの動作の大枠は説明できたと思う。

明日はOPECODEの構造体の中身を説明する予定。

割り込みやブート関係の命令は完全に無視している。↩
x86のエミュレータというと、ブート処理やIO、割り込み周りもちゃんと作ってる雰囲気がただようので怒られそう。「これからFPGAで作るx86サブセットCPUの、レジスタとメモリをシミュレーションするやつ」と言えばたぶん怒られない。↩
FPGAでCPUを作った時もそうしていた。↩
コンパイラ製作のコード生成パートで、このへんの問題と向き合うことになる。↩

2017-12-14

14日目: [x86] 関数呼出

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

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

今日は関数をやる。

関数呼出と聞くと高度で抽象的な処理を彷彿させるが、決してそんなことはない。 x86パートに入る前にFPGAでCPUを自作したが、実はあのショボいCPUでも関数は実装可能だ。ジャンプ命令とスタックメモリさえあれば、関数はつくれる。

今日の目的は、Cのような高級言語における関数が機械語レベルでどのように実装されているのか理解し、call、ret、leave命令を使って関数が書けるようになることだ。

関数の意義

そもそも、なぜ関数が必要なのか考えたい。 C言語で関数を使うメリットとして簡単に思いつくのは「可読性の向上」とか「モジュールの再利用性を高める」だと思う。しかしそうした目的で関数を使う場合、代わりにコードをコピペしても動作するだろう。極論、関数は不要だ。

関数の重要な点は再帰呼出しにあると(僕は勝手に)思う。

「ある数字aを再帰呼出しで求める。この処理をループに変形するには、aの値をあらかじめ知っておく必要がある」

みたいな状況では、再帰関数を使わないと計算のしようがない。そういう背景があるので、エミュレータとコンパイラが完成した暁には、フィボナッチ数を再帰呼び出しで計算するプログラムを動かす予定だ。ちなみに4日ほど前にCPUを作った際も、最後にフィボナッチ数を計算したが、あれは再帰呼出しではなく「前回と前々回の値を保存」する方式で計算していた。

他のメリットとしては、関数を使えば実行ファイルのサイズが小さくなる(ことがある)。デメリットとしては、関数を使わなかった場合と比べて実行速度が遅くなる(ことがある)¹。

引数も返値もない関数

本題に移る。引数も返値もないC言語の関数を考える。

void FUNC(void) {
  いろいろやる;
}

この関数の呼び出しを機械語で実装したいのだが、絵で説明すると

f:id:kaitou_ryaku:20171212031332p:plain

どうだゴチャゴチャしているだろう。そしてさらにゴチャゴチャした話が今から展開される。そこでまず太字の部分だけ読んで、流れを掴んで欲しい。

図の見方だが、上部が関数の呼出元で、下部が関数の本体に対応している。次にニーモニックの列を見て欲しのだが、pushとpopとmovとjmp命令しかない。たった4種類の命令だけで関数は実現できる。

最上段を見ると、espとebpのレジスタにはSとBが入っており、スタックメモリには----が入っている。 espはスタックポインタなので、その値は----の左端のメモリアドレスに一致している。

今から関数を使ってゴチャゴチャと処理を行うわけだが、 最終的に現在(関数呼出前)のespとebpとスタックメモリを復元する義務がある。

次にpush NEXTという命令を実行すると、 esp=S-4、ebp=Bとなり、スタックにNEXTの位置のメモリアドレスが入る。スタックはpushされると負の方向に伸びていくことを思い出してくれ。重要なのは、このpush命令は関数から帰還する場所をメモ (call)するための処理という点だ。

そして次の命令でFUNCの位置にジャンプ (call)する。関数の中に入った。

FUNCのラベルに移動したらpush ebpが実行され、続いてmov ebp, espが実行される。この2つの命令は、計算前のebpとespの値をメモするための処理である。 espの値をebpにメモし、ebpの値をスタックメモリ上にメモしたわけだ。今後スタックに値を追加してespの値を変えたとしても、ebpに書かれたスタックアドレスの情報は保持されるので、復元の義務を果たすことができる。

レジスタとスタックの復元準備が整ったので、心置きなく計算できる。スタックにガンガン値を追加して、レジスタも使って計算を実行しよう。ただしebpの値を変更すると元の状態を復元できなくなるので、変えてはならない。

計算を終えたら、まずmov esp, ebpを実行してespの値を計算前に戻す (leave)。この操作により、計算でグチャグチャになった(図中の????の)スタックメモリを無視することができる。

次にpop ebpを実行して、ebpの値を関数呼出前に戻す (leave)。

最後にpop eipを実行してプログラムカウンタにNEXTを入れることで、関数の呼出元に帰還しつつ、espの値が関数呼出前に戻る (ret)。

話をまとめると、以下のようなアセンブラコードを書けば関数呼出が実現できる。

call FUNC     ; 帰還するアドレスをメモしてFUNCにジャンプ
...           ; いずれここに帰還
...
...

FUNC:
push ebp      ; 呼出時のebpをメモ
mov  ebp, esp ; 計算前のespをメモ

いろいろやる

leave         ; espを計算前に戻し、ebpを呼出時に戻す
ret           ; 帰還し、espを呼出時に戻す

引数と返値の処理

ここまで引数返値なしの関数を見てきたが、次は

int function(int a, int b, int c) {
  return a+b+c;
}

という関数を考えたい。さっきと違って引数と返値がついている。

この関数を実現するには

push cの値    ; 3番目の引数をスタックに詰む
push bの値    ; 2番目の引数をスタックに詰む
push aの値    ; 1番目の引数をスタックに詰む
call FUNC     ; 帰還するアドレスをメモしてFUNCにジャンプ
...           ; いずれここに帰還
...           ; 関数の返値はeaxに入る
...

FUNC:
push ebp      ; 呼出時のebpをメモ
mov  ebp, esp ; 計算前のespをメモ

a+b+cを頑張って計算
引数aの値は[ebp+8] で参照
引数aの値は[ebp+12]で参照
引数aの値は[ebp+16]で参照
計算結果をeaxに入れる

leave         ; espを計算前に戻し、ebpを呼出時に戻す
ret           ; 帰還し、espを呼出時に戻す

コードの1行目を見れば分かる通り、引数はスタックに積んで関数に渡す。順番には少し注意がいる。

注意してほしいのは、espとebpとスタックメモリは呼出前の状態に戻さないといけないが、eaxは変更されてもよいので、返値をeaxのレジスタに入れて呼び出し元に渡している。

値渡しと参照渡し

C言語で関数を呼び出す際に、「値渡し」と「参照渡し」がある。

int main(void) {
  int a = 1;
  hoge(a);  // 値渡し
  piyo(&a); // 参照渡し
}

今日書いた説明に基づくと、両者の違いは関数をcallする前に

渡し方	スタックに入る値	呼出先での値の取得
値渡し	1	`a`の値は`[ebp+8]`で取得
参照渡し	aのメモリアドレス	`a`のメモリアドレスは`[ebp+8]`で取得

となる。

配列int a[10]を関数に渡す時は、参照渡しでa[10]に対応するメモリ領域の最初のアドレスをスタックに積み、関数本体にジャンプしている。

C言語では構造体を値渡しで関数に渡すことができる。この場合、構造体のメンバをかたっぱしからスタックに積みまくった後に、関数本体にジャンプしている。つまり機械語レベルでは、構造体を値渡しする関数は引数を大量にとる関数とよく似ている。

引数の数が増えると、ジャンプの前に引数をpushする回数が増えるので、実行速度は遅くなりがちだ²。

その他

ここで説明した関数の呼出規約はcdeclと呼ばれるもので、x86のC言語の標準的な呼出規約になっている。他にも様々な呼出規約があるので、コレが唯一の正解というわけではない。

今日までで、一通り x86の命令セットを解説し終えた。

明日からは、いよいよx86のエミュレータを作るぞ。

優秀なコンパイラが最適化すると、この辺のメリットデメリットの話は何とも言えなくなる。↩
しかしそのへんはコンパイラの最適化が働き、引数の数が少なければスタックの代わりにレジスタに値を割り当てることがある。↩

2017-12-13

13日目: [x86] ModRM

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

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

昨日は数値についてまとめた。

今日はModRMを説明する。

ModRMを一言で表すと、必須オプションだ。たとえばadd命令の場合、何と何を足すかを指定するのがModRMの役目と言える。

add命令

具体的に説明するため、考える対象をadd命令に絞る。一昨日のx86の命令セット表の最上段左側のadd命令を切り出すと

f:id:kaitou_ryaku:20171212024535p:plain:w300

機械語の0x01はニーモニックのadd [M+imm], Rに対応し、0x03はadd R, [M+imm]に対応する。ここで[hoge]はメモリのhoge番地を表している。つまりadd [M+imm], Rを数式的に書くと(M+imm)番地のメモリ = (M+imm)番地のメモリ + Rになり、メモリの値を変更する命令になっている。

一方add R, [M+imm]ではメモリの値は変更されない。

これらを表に記すと

機械語	ニーモニック
0x01 ???? ...	add, [address], register
0x03 ???? ...	add, register, [address]

????の部分をうまく調整することで何と何を足すか指定できる。この指定子がModRMだ。

[M+imm], R 型

add [M+imm], R命令(機械語0x01)を知るための画像を用意した。これをじーっくり眺めて欲しい。

f:id:kaitou_ryaku:20171212024547p:plain

右列は機械語を1byteずつ区切ったものだ。最初に0x01、次に1byteのModRMが来て、最後に即値(無い場合もある)が来る。

ModRMについては、中央のカラフルな列を見れば分かるように、最初の2bitがmod、次の3bitがR、最後の3bitがMと命名されている。

左列の下四段のニーモニックを見ると、[M+imm]の形式が異なっている。これらの形式はmodで指定される。

mod	`[M+imm]`の型
00	[レジスタ]
01	[レジスタ+imm8]
10	[レジスタ+imm32]
11	レジスタ

RとMについては、以下のようにレジスタと対応している。

R or Mの2進表示	レジスタ
000	eax
001	ecx
010	edx
011	ebx
100	esp
101	ebp
110	esi
111	edi

なんだかややこしいが、そういう仕様なので仕方ない。

R, [M+imm] 型

機械語0x03、つまりadd R, [M+imm]の命令を見てみる。

f:id:kaitou_ryaku:20171212024554p:plain

さっきの[M+imm], Rと比較すると、Rと[M+imm]の位置が入れ替わっただけだ。 ModRMの役割は全く同じなので、説明は略す。

なおadd以外の命令(subやcmpやmovなど)についても、命令セット表に[M+imm], RやR, [M+imm]が出てきたら、ModRMは今説明したadd命令とおなじ型になる。

ModRMの精神について述べると、modは挙動の種類を指定し、Rはレジスタを指定し、Mはメモリを指定する。この雰囲気を掴むと納得しやすい。

Rで計算種別を指定する型

今までに解説した2タイプのModRMが分かれば、ほぼ困らない。しかし他の型のModRMもいるので、軽く説明しておく。

命令セット表の8段目の左側0x81, 0x83の命令は、calcになっている。

f:id:kaitou_ryaku:20171212024602p:plain:w300

これらはadd ecx, 即値やsub edx, 即値を計算する命令だ。

この場合は、ModRMのRで計算の種類を指定し、Mでレジスタを指定する。

2進表示	オペコード(R)	レジスタ(M)
000	add	eax
001	or	ecx
010	adc	edx
011	sbb	ebx
100	and	esp
101	sub	ebp
110	xor	esi
111	cmp	edi

なお、modは11に固定しておく¹。最後に、calc eax, imm32型の命令については、機械語0x81ではなく機械語0x05等も使用できる。つまりeaxだけ例外扱いされているのだ²。こういう例外は辛い。

即値を2つ取る型

mov [M+imm], imm32_next

というタイプのニーモニックは、アセンブルすると

0xc7 ModRM imm imm32_next

となる。この場合のModRMは:

ModRM	説明
mod	`[M+imm]`の形式を`add`命令の場合と同様に指定
R	000で固定。ということにしてくれ
M	レジスタの種類を`add`命令の場合と同様に指定

どうでもいい話

今日のModRMの解説で、 x86の命令セット表の大半は理解できるようになったと思う。

残りはcall, leave, retだけだ。これらは関数呼び出しのための命令で、少しややこしいので明日説明する。

今まで見てきたように、x86は各命令のサイズがバラバラだ。 hltのように1byteの命令もあれば、add [eax+0x12345678], 0x1234のような10byte命令もある。これをちゃんと読み取るCPUをFPGAで書くのは、結構難しい。 3日前に作ったCPUは、異サイズの命令読み取りの部分でずるいことをして、問題を回避していた。

MIPSならば、この辺の面倒な問題が起きない³のでCPUを作りやすい。逆に言うとx86がしんどいのだ。x86の辛さを表すエピソードを紹介すると

#低レイヤ x86-32bitの機械語で、movの引数に[esp]がくる場合が気持ち悪い。例えばmov [レジスタ] imm32型の命令で、[esa]や[ebp]ならModRMの後に即値がくる。しかし [esp]の場合はModRMのあとに余計な0x24が入る。こういう例外はやめて
— 解答略 (@kaitou_ryaku) 2017年2月1日

SIB拡張のためにどれかのレジスタを読み換える必要があったがESPが一番1バイト長くなっても支障なかったからね
スタック上にローカル変数展開するにもEBP相対のアドレッシングで読み書きすれば十分だしね https://t.co/a46ddBAzhq
— (:∠) まぐろ㌠ (@MagurosanTeam) 2017年4月10日

辛い。

さっきMはメモリを指定すると書いたので、ここでのMも[M+imm]という形のニーモニックになりそうだ。しかしx86命令セットの拡張に次ぐ拡張の結果、安直な期待はしばしば裏切られる。チェックが必要だ。↩
90から97までのxchg命令でも、eaxだけ特例扱いされている。↩
多分↩

2進表示	オペコード(R)	レジスタ(M)
000	add	eax
001	or	ecx
010	adc	edx
011	sbb	ebx
100	and	esp
101	sub	ebp
110	xor	esi
111	cmp	edi

2進表示	オペコード(R)	レジスタ(M)
000	add	eax
001	or	ecx
010	adc	edx
011	sbb	ebx
100	and	esp
101	sub	ebp
110	xor	esi
111	cmp	edi

字句解析とは

BNF (バッカス-ナウア記法)

minc言語誕生

字句解析 (人力)

字句解析の実装

列挙型で属性にエイリアスを貼る

トークンの構造体

コメントの読み飛ばし

次のトークンを取得

全トークンの配列を取得

どうでもいい話

1日目: 字句解析

2,3日目: 構文解析

4日目: 抽象構文木

5日目: シンボルテーブル

6日目: コード生成

沿革

どうでもいい話

仕様

基本戦略

1. レジスタとフラグの拡張

2. メモリフェッチの改善

3. ModRMでオペランドを指定

4. 演算処理を各モジュールに分離

5. 条件付きジャンプ命令

6. 関数呼出

call

leave

ret

7. ModRMの入った演算

どうでもいい話

ope構造体配列の初期化

ope構造体のメンバ関数 func

add [M+imm], R を処理する関数

ModRMの処理

[M+imm]のメモリアドレスを取得する処理

加算結果をメモリに書き込む処理

レジスタに書き込む処理

sub命令とcmp命令

push命令とpop命令

ジャンプ系命令

関数呼出

どうでもいい話

予定

エミュレータの本体部分

エミュレータのメモリに機械語を読み込む

ニーモニックの解釈

機械語を実行

関数の意義

引数も返値もない関数

引数と返値の処理

値渡しと参照渡し

その他

add命令

[M+imm], R 型

R, [M+imm] 型

Rで計算種別を指定する型

即値を2つ取る型

どうでもいい話

`ope`構造体配列の初期化

`ope`構造体のメンバ関数 `func`

2進表示	オペコード(R)	レジスタ(M)
000	add	eax
001	or	ecx
010	adc	edx
011	sbb	ebx
100	and	esp
101	sub	ebp
110	xor	esi
111	cmp	edi