C 言語で仮想マシンを実装するにはどうすればいいですか?

私は低レベルのアプリケーション (コンパイラ、インタープリタ、パーサー、仮想マシンなど) での作業が好きなので、C プログラミング言語で仮想マシンを構築する方法についての記事を書くと役立つと思いました。この記事を読めば、仮想マシンの仕組みを理解するだけでなく、低レベルのプログラミング プロセスについても理解できると思います。

コンテンツの準備

• 使用するコンパイラの種類: 軽量コンパイラである clang を使用していますが、任意の最新コンパイラを使用できます。
• テキスト エディター: C を書くときは、IDE を介してテキスト エディターを編集することをお勧めします。私は Emacs を使用します。
• 基本的なプログラミング知識: 変数、フロー制御、関数、構造体とは何かなど。
• GNU Make: GNU Make は主に実行可能プログラム (ライブラリ ファイル) の構築を自動化するために使用されます。これにより、コードをコンパイルするためにターミナルで同じコマンドを何度も記述する必要がなくなります。 Make の機能には、自動ビルドとインストールが含まれます。増分コンパイルと自動更新。 C/C++、Java、PHP などの複数の言語に適用可能。カスタム関数拡張のサポート (意味がある限り、Makefile に組み込むことができます)。

[[233734]]

なぜ仮想マシンを作成する必要があるのでしょうか?

仮想マシンを作成する必要がある理由はいくつかあります。

1. コンピューターの仕組みをより深く理解する必要があります。この記事は、コンピューターが低レベルでどのように動作するかを理解するのに役立ちます。仮想マシンは非常に単純な抽象化レイヤーを提供します。

2. ところで、仮想マシンについての知識を少し学びましょう。

3. プログラミング言語の仕組みを深く理解する。最近では、JVM、Lua VM、FaceBookのHip-Hop VM(PHP/Hack)など、さまざまな言語が仮想マシンを対象としています。

命令セット

命令セットは比較的単純なので、レジスタから値を移動したり、他の命令にジャンプしたりする方法など、簡単に概要を説明します。

仮想マシンにレジスタのセット A、B、C、D、E、F があり、これらは汎用レジスタであるため、何でも保存できるとします。これは、特殊目的レジスターとは異なります。例: x86 では、命令セットによって読み取り専用となる ip、flag、ds など。 VM がスタックベースの VM である場合、値をプッシュおよびポップできるスタックがあり、使用できるレジスタもあることを意味します。スタックベースの仮想マシンは、レジスタベースの仮想マシンよりも実装がはるかに簡単です。

以下は私が実装する命令セットの例です。

 5 ;スタックに5をプッシュする
10ポンドスタックに10をプッシュする
追加; 2つの値をポップする の上 トップ スタックの、スタックにプッシュする追加
ポップ;スタック上の値をポップし、デバッグ用に出力もします。
 0 を設定します。レジスタAを0に設定する
HLT ;プログラムを停止する

これが私の命令セットです。POP 命令はポップした命令を印刷しますが、その多くはデバッグ用であることに注意してください。 ADD は結果をスタックにプッシュするので、スタックから値をポップして、存在するかどうかを確認できます。レジスタにアクセスして書き込む方法を確認できるように、SET 命令も含めました。 MOV A, B (値 A を B に移動) などの命令を実行することもできます。HLT はプログラムの実行が終了したことを示す命令です。

仮想マシンはどのように機能しますか?

実際、仮想マシンはあなたが思っているよりもシンプルです。その動作モードは、「命令サイクル」という単純なルールに従います。全体のプロセスには、読み取り、デコード、実行という 3 つの主要な部分が含まれます。まず、命令セットを読み取り、次に命令をデコードして、デコードされた命令を実行する必要があります。

プロジェクト構造

プログラミングを始める前に、いくつかの準備が必要です。プロジェクトを入れるためのフォルダーが必要なので、~/Dev に入れたいと思っています。さらに、C コンパイラが必要です (clang 3.4 を使用しています)。ここでは、ターミナルでプロジェクトを設定する方法を説明します。すでに ~/dev/ ディレクトリがあることを前提としていますが、任意の場所に配置できます。

 $ cd ~/dev/
 $ mkdir mac
 $ cd mac
 $ mkdir src

上記は、~/dev ディレクトリに cd する方法です。まず、ディレクトリを作成します (VM を「mac」と呼びます)。次に、そのディレクトリに移動して src ディレクトリを作成します。ここにコードを保存します。

メイクファイル

私の makefile は比較的シンプルで、複数のファイルに分割する必要がないため何も含まれておらず、いくつかのフラグを使用してファイルをコンパイルするだけです。

 SRC_FILES = main.c
 CC_FLAGS = -Wall -Wextra -g -std=c11
 CC = カラン
 
全て：
    ${CC} ${SRC_FILES} ${CC_FLAGS} -o mac

今のところこれで十分でしょう。後からいつでも改善できますが、これで目的が達成されれば問題ないでしょう。

命令プログラミング

これで、仮想マシンのコードの作成を開始できます。まず、命令プログラミングを説明するには、命令が基本的に 0 から X までの数字であるため、列挙を使用する必要があります。基本的に、アセンブラはアセンブリ ファイルを受け取り、すべての操作を数値に変換します。たとえば、Mac 用のアセンブラ プログラムを作成すると、すべての MOV 操作が数値 0 に変換されます。

 typedef列挙型{
    PSH、
追加、
    ポップ、
セット、
    HLT
 } 命令セット;

これで、テスト プログラムを配列として保存し、5 と 6 を加算して POP 命令を使用して出力するなどの簡単なテスト プログラムを作成できます。必要に応じて、スタックの一番上の値を出力するコマンドを定義できます。

指示は配列に保存する必要があり、これはドキュメントの先頭で定義します。ただし、ヘッダー ファイルに配置することもできます。以下は私のテスト プログラムです。

 const intプログラム[] = {
    PSH、5、
    PSH、6、
追加、
    ポップ、
    HLT
 };

上記のプログラムは、5 と 6 をスタックにプッシュし、スタックから 2 つの値をポップする add 命令を実行し、それらを加算して結果をスタックにプッシュし戻します。次に結果がポップされ、デバッグの目的で、ポップ命令によって両方の値が出力されます。

***、HLT命令はプログラムを終了することを意味します。フローを制御したい場合は、いつでもプログラムを終了できます。ただし、何も指示しないと、仮想マシン *** は自然に終了します。

これで、仮想マシンの読み取り、デコード、実行のプロセスを実装しました。ただし、覚えておいてください。私は何も解読していません。生の指示を与えているだけです。

現在のコマンドを取得する

プログラムを配列として保存しているので、現在の命令を取得するのは簡単です。仮想マシンにはカウンターがあり、通常はプログラム カウンターと呼ばれますが、命令ポインターなどと呼ばれることもあり、通常はそれぞれ PC または IP と略されます。

今のところは、コードの先頭に ip という変数を作成し、それを 0 に設定するだけです。

整数ip = 0;

この ip は命令ポインターを表します。プログラム自体を整数配列として保存しているため、ip 変数は配列内のインデックスとして機能し、現在実行中の命令を示します。

整数ip = 0; 
 
 int main() {
 int instr = プログラム[ip];
 0を返します。
 }

変数 instr を印刷すると、変数 instr が列挙の最初の値であるため、PSH は 0 として表示されます。ただし、次のように検索関数を記述することもできます。

整数 フェッチ（）{
プログラム[ip]を返します。
 }

この関数は呼び出されると現在の命令を返します。では、次の指示が必要な場合はどうすればよいでしょうか?命令ポインタを増分するだけです。

 int main() {
 int x =フェッチ(); // ポシュ
    ip++; // 命令ポインタを増分する
int y =フェッチ(); // 5
 }

では、これをどのように自動化するのでしょうか?プログラムは HLT 命令を通過するまで停止しないことがわかっているので、プログラム自体は *** ループです。

 #include <stdbool.h> 
 
 bool 実行 = true ; 
 
 int main() {
    （実行中）{
 int x =フェッチ();
       (x == HLT) 実行中 = false の場合;
       ip++;
    }
 }

私が現在やろうとしているのは、各命令をループして、命令の値が HLT であるかどうかを確認し、そうであればループを停止し、そうでない場合は繰り返し続けることです。

指示の評価

これは仮想マシンの動作の鍵となります。実際、仮想マシンは非常にシンプルです。巨大な switch ステートメントを記述できます。これを行う目的は、走行速度を速めることです。対照的に、すべての命令と、execute メソッドを使用する抽象クラスまたはインターフェースには HashMap を使用する必要があります。

switch ステートメント内の各ケースは列挙で定義したディレクティブであり、この eval 関数は単純なディレクティブ引数を使用してディレクティブを評価します。オペランドを使用していない限り、この関数では命令ポインタの増分を実行しないでください。

 void eval( int instr) {
    スイッチ（命令）{
ケースHLT:
        実行中 = false ;
        壊す;
    }
 }

この関数を VM のメイン ループに追加します。

 bool 実行 = true ;
整数ip = 0; 
 
 // 命令列挙型
// 評価関数 
 //取得 関数  
 
 int main() {
    （実行中）{
        eval(フェッチ() );
        ip++; // 繰り返しごとに IP を増分する
    }
 }

スタック

しかし、他の命令を追加する前に、スタックが必要です。スタックは非常に単純なデータ構造です。リンクリストの代わりにこの配列を使用します。スタックのサイズは固定されているので、サイズ変更を心配する必要はありません。リンク リストの代わりに配列を使用すると、キャッシュ効率の点で利点が得られます。

プログラム配列のインデックスに ip を使用したのと同様に、スタック配列内の位置を示すスタック ポインター (sp) が必要になります。

以下は、私のスタックの 1 つのデータ構造の詳細なリストです。

 [] // 空の
 
 PSH 5 //スタックの**一番上**に5を置く
[5] 
 
 PSH 6 // 6オン トップ スタックの
[5, 6] 
 
 POP //上から6をポップします 
 [5] 
 
 POP // 5をポップする
[] // 空の
 
 PSH 6 // 6 をプッシュします...
 [6] 
 
 PSH 5 // など
[6, 5]

スタックに従ってプログラムを分解してみましょう。

 PSH、5、
 PSH、6、
追加、
ポップ、
 HLT

まずスタックに 5 をプッシュします。

 [5]

次に、6 をスタックにプッシュします。

 [5, 6]

次に、add 命令はそれらの値をポップして加算し、最終的に結果をスタックにプッシュします。

 [5, 6] 
 
 //一番上の値を取り出し、それをaという変数に格納します
a = ポップ; // a には6 が含まれています
[5] // スタックの内容
 
 //一番上の値をポップし、それをb という変数に格納します
b = ポップ; // bには5が含まれています
[] // スタックの内容
 
 // ここでbとaを追加します。逆に行うことに注意してください。
 // これは問題ではないが、他の潜在的な命令では
//例えば5を6で割ると  6/5と同じではありません
結果 = b + a;
 push result // 結果をスタックにプッシュする
[11] // スタックの内容

スタック ポインターがどこで機能するかわかりますか?スタック ポインターは -1 に設定されており、空であることを意味します。 C では配列はゼロインデックスなので、sp が 0 の場合、配列のメモリはゼロに設定されていないため、C コンパイラによってスローされるランダムな数値に設定されます。

ここで 3 つの値をスタックにプッシュすると、sp は 2 になります。つまり、3 つの値を持つ配列は次のようになります。

      -> スペース -1
   プシュ -> スポ 0
   プシュ -> スペル 1
   プシュ -> スペ3 
 
 spはここにポイントします（sp = 2）
      |
      五
[1、5、9]
 0 1 2 <- 配列インデックスまたは  「アドレス」  

ここで、スタックから一度ポップし、スタック ポインターの先頭をデクリメントする必要があります。たとえば、次にスタックから 9 をポップしたい場合、スタックの一番上は 5 になります。

 spはここにポイントします（sp = 1）
        |
        五
    [1, 5]
     0 1 <- これらは配列のインデックスです

したがって、スタックの一番上に何があるかを知りたいときは、sp の現在の値を確認するだけで済みます。これでスタックの仕組みが理解できたと思います。

今度はそれを C 言語で実装します。 C 言語でスタックを実装するのは非常に簡単です。 ip と同様に、sp 変数と配列も定義する必要があります。この配列がスタックです。

整数ip = 0;
整数sp = -1;
整数スタック[256]; 
 
 ...

ここで、スタックに値をプッシュする場合は、スタック ポインターをインクリメントしてから、現在の sp に値を設定します。

このコマンドの順序は非常に重要です。最初に値を設定し、次に sp を増分すると、インデックス -1 のメモリに書き込むため、動作が悪くなります。

 // s = -1 です
sp++; // 0 の場合
スタック[sp] = 5; //スタック[0]に値を設定-> 5
 //トップ スタックは現在[5]

eval 関数では、次のようにスタックをプッシュできます。

 void eval( int instr) {
    スイッチ（命令）{
ケースHLT: {
            実行中 = false ;
            壊す;
        }
 PSHの場合: {
            sp++;
            スタック[sp] = プログラム[++ip];
            壊す;
        }
    }
 }

これは前の eval 関数とは多少異なることがはっきりとわかります。まず、各ケース ブロックを中括弧で囲みます。これを実行する目的が理解できないかもしれませんが、これにより、各ケースのスコープ内で変数を定義できるようになります。変数を今すぐ定義する必要はありませんが、将来必要になる可能性があり、定義しておくと、すべてのケース ブロックを一貫したスタイルに保つことが容易になります。

次に、PSH命令に必要なオペランドを担当するprogram[++ip]式があります。プログラムは配列に格納されているため、PSH 命令はオペランドを取得する必要があります。オペランドは本質的にはパラメータであり、関数を呼び出すときにパラメータを渡すことができるのと同じです。この状況は、値 5 をスタックにプッシュする (PSH, 5) と呼ばれます。命令ポインタ ip を増やすことでオペランドを取得できます。 ip が 0 の場合、PSH 命令が実行されたことを意味し、次にスタックにプッシュされた値を取得します。これは、IP アドレスを自動的に増やすことによって実現できます。これが完了したら、次の命令にジャンプする必要があります。そうしないと、奇妙なエラーが発生します。もちろん、sp++をstack[++sp]に簡略化することもできます。

プログラム = [ PSH, 5, PSH, 6, ]
            0 1 2 3 
 
押すとき:
 ip は 0から始まります(PSH)
 ip++なのでipは1になります（5）
 sp++、割り当てる 空間 スタック上
stack[sp] = program[ip]、スタックに値5を置く

POP 命令は非常に単純で、スタック ポインターを減算するだけです。ただし、ポップ命令でポップされたばかりの値、つまりスタックからポップされた値を出力したい場合は、依然として多くの作業を行う必要があります。

ケースPOP: {
    //スタックの値をval_poppedに格納し、スタックポインタをデクリメントします
int val_popped = スタック[sp --];   
 
    // それを印刷します!
    printf( "ポップされた%d\n" , val_popped);
    壊す;
 }

*** は ADD 命令です。 ADD 命令は、2 つの数値 (繰り上がりなし) を加算するコンピュータ命令です。これは少し難しいように思えるかもしれません。ここで、いくつかの変数を導入するため、case ブロックを中括弧内に配置するというトリックが役立ちます。

場合 追加： {
    //まずスタックをポップして次のように保存します  'あ'  
 int a = スタック[sp --];   
 
    //次に上部をポップします スタックから取り出して保存する  'ブ'  
 int b = スタック[sp --];   
 
    //その後 結果を追加してスタックにプッシュする
int結果 = b + a;
    sp++; // スタックポインタを**前に**インクリメント
    スタック[sp] = 結果; //値を一番上に設定する スタックの
 
    // 完了しました!
    壊す;
 }

始める前に、いくつかの操作の順序が重要であることに注意してください。

 5 / 4 != 4 / 5

スタックは LIFO (先入れ先出し) です。つまり、最初に 5 がプッシュされ、次に 4 がプッシュされた場合、最初に 4 がポップされ、次に 5 がポップされます。pop() / pop() を実行した場合、間違った式が生成されるため、順序を正しくすることが重要です。

登録する

レジスタは仮想マシンではオプションであり、実装が簡単です。先ほど、A、B、C、D、E、F の 6 つのレジスタが必要になる可能性があると述べました。命令セットを実装するのと同じように、列挙体を使用してこれらを実装します。

 typedef列挙型{
   A、B、C、D、E、F、
   レジスタ数
} レジスタ;

しかし、ここにはちょっとしたトリックがあり、列挙された *** には NUM_OF_REGISTERS が表示されます。この関数はレジスタのサイズを取得するために使用できますが、他のレジスタを追加した場合でも、そのサイズを取得できます。

レジスタを配列に格納します。これは、A = 0、B = 1、C = 2 などの列挙を使用するためです。したがって、レジスタ A を設定する場合は、register[A] = some_value と記述するだけです。

 intレジスタ[レジスタ数];

レジスタ A の値を出力します。

 printf( "%d\n" , レジスタ[A]); //レジスタAの値を出力します

命令ポインタ

現在の命令を指す分岐命令ポインターがあることに留意してください。これは仮想マシンのソースコードなので、命令ポインタをレジスタとして使用し、仮想マシンプログラムからさまざまな操作を読み取って実行できるようにするのが最適です。

 typedef列挙型{
    A、B、C、D、E、F、PC、SP、
    レジスタ数
} レジスタ;

ここで、これらの命令とスタック ポインターを実際に使用するためにコードを移植する必要があります。これを行う最も簡単な方法は、スタックの最上部にある sp 変数と ip 変数を削除し、次の定義に置き換えることです。

 #define sp (レジスタ[SP])
 #define ip (レジスタ[IP])

こうすることで、多くのコードを書き直す必要がなくなり、完璧に実行されます。欠点は、スケーラビリティがあまり高くなく、一部のコードが難読化される可能性があることです。そのため、このアプローチの使用はお勧めしませんが、単純な VM の場合は使用しても問題ないかもしれません。

コードの分岐に関してヒントを紹介します。新しい IP レジスタを使用すると、この IP に異なる値を書き込むことで分岐することができます。次の例を試して、何ができるかを確認してください。

 10ポンド
IP 0 を設定

これは、多くの人がよく知っている基本的な手順に似ています。

 10 「Hello, World」を印刷する 
 20ゴートー10

ただし、スタックには常にプッシュされているため、スタックにプッシュされた量がスペースの量を超えると、スタック オーバーフローが発生します。

各「単語」は命令なので、プログラムは次のようになります。

              ;これらは指示です
10ポンド0 1
 20ポンド2 3
 IP 0を設定します。 4 5 6

2 番目の命令セットにジャンプしたい場合は、IP レジスタを 0 ではなく 2 に設定します。

要約する

この記事を読んだ後、プロジェクトのルートディレクトリで make を実行すると、仮想マシン ./mac を実行できます。

ソースコードはgithubでこちらからご覧いただけます。 MOV および SET 命令を含む VM の更新バージョンを確認する場合は、mac-improved ディレクトリを確認してください。この記事で実装したVMのソースコードはmac.cにあります。