概要

コード生成で生成したバイトコードを実行する仮想マシンを実装する．JVMなど，多くの仮想マシンがスタックマシンでの実行を採用しているので，ここでもスタックマシンで仮想マシンを実装する．この仮想マシンでは，とりあえず代入と加算，組み込み関数としてint print()だけ実行できるようにする．なお，printは引数を取れないので，実行しても実行できてるかどうかわからないため，呼び出されたら"hoge"とだけ出るようにする．

各種構造体の定義

まず，仮想マシン，値，定数，関数に対応する構造を定義する．

値の定義

この仮想マシンでは，値として整数と実数が存在するので．値を表現する構造を共用体で定義する．

svm.h

typedef union {
    int    ival;
    double dval;
} SVM_Value;

このSVM_Valueが，スタックに積まれたり，変数に格納される実体となる．

定数の定義

定数はコンパイルした時点で個数やそれぞれの型と値が決まっている．したがって，値と型情報を管理する．

svm.h

typedef enum {
    SVM_INT = 1,
    SVM_DOUBLE,
} SVM_ConstantType;

typedef struct {
    SVM_ConstantType type;
    union {
        int c_int;
        int c_double;
    } u;
} SVM_Constant;

バイトコードを実行するときには，バイナリーに含まれる定数を読み出し．この構造体(の配列)にそれぞれの値を格納する．

関数の定義

組み込み関数の型をを定義する．関数を実行するには，値への参照，引数の数，そして後述する仮想マシンへの参照を取れるようにし，返り値としてSVM_Valueを返すようにする．

svm.h


typedef enum {
    NATIVE_FUNCTION,
    CSUA_FUNCTION
} FunctionType;

typedef SVM_Value (*SVM_NativeFunction)(SVM_VirtualMachine* svm, 
                                        SVM_Value* values, int arg_count);

typedef struct {
    FunctionType  f_type;
    char         *name;
    int           arg_count;
    union {
        SVM_NativeFunction n_func;
    } u;
} SVM_Function;

また，この関数ではまだ独自関数が定義できないが，今後の拡張を考慮してFunctionTypeも定義しておく．

仮想マシンの定義

仮想マシンでは，定数．グローバル変数(のための領域)，バイトコード，スタック，プログラムカウンタ，スタックポインタ，関数を管理する．また，デバックのための情報として．スタックに積まれた値の型を記憶しておく

svm.h

struct SVM_VirtualMachine_tag {
    uint32_t      constant_pool_count;     // 定数の数
    SVM_Constant  *constant_pool;          // 定数
    uint32_t       global_variable_count;  // グローバル変数の数
    SVM_Value     *global_variables;       // グローバル変数
    uint8_t       *global_variable_types;  // グローバル変数の型情報
    uint32_t       code_size;              // バイトコードサイズ
    uint8_t       *code;                   // バイトコード
    uint32_t      function_count;          // 関数の数
    SVM_Function  *functions;              // 関数
    uint32_t       stack_size;             // スタックサイズ
    uint8_t       *stack_value_type;       // スタックに積まれる値の型
    SVM_Value     *stack;                  // スタック
    uint32_t       pc;                     // プログラムカウンタ
    uint32_t       sp;                     // スタックポインタ
};

仮想マシンの初期化

仮想マシンの初期化では，
1. バイナリから定数を読み込む
2. グローバル変数を初期化
3. バイトコードの読み込み
4. 組み込み関数を追加
5. スタックを確保

という処理を行う．1, 2に関しては．必要な情報はすべてバイナリに含まれているので．バイナリフォーマットを解析して値をセットするなり，型に応じて初期値を0か0.0にすればよい．3も同様に，バイナリのバイトコードが格納されている部分からバイトコードをコピーする．4に関しては．組み込み関数を登録する関数を用意し．名前とともに関数ポインタを追加する．最後に，必要なスタックのサイズがバイナリに含まれているので．その分だけスタック用のSVM_Value領域を確保する．

svm.c

static void parse(uint8_t* buf, SVM_VirtualMachine* svm) {
    uint8_t* pos = buf;
    parse_header(&pos);
    svm->constant_pool_count = read_int(&pos);           // 定数の数を読み込む
    svm->constant_pool = (SVM_Constant*)MEM_malloc(sizeof(SVM_Constant) * 
                           svm->constant_pool_count);    // 定数のための領域を確保
    uint8_t type;
    for (int i = 0; i < svm->constant_pool_count; ++i) {  // 定数をロードする
        switch(type = read_byte(&pos)) {
            case SVM_INT: {
                int v = read_int(&pos);
                svm->constant_pool[i].type = SVM_INT;
                svm->constant_pool[i].u.c_int = v;
                break;
            }
            case SVM_DOUBLE: {
                double dv = read_double(&pos);
                svm->constant_pool[i].type = SVM_DOUBLE;
                svm->constant_pool[i].u.c_double = dv;                
                break;
            }
            default: {
                fprintf(stderr, "undefined constant type\n in parse");
                exit(1);
            }
        }
    }

    svm->global_variable_count = read_int(&pos);                 // グローバル変数の数を読み込む
    svm->global_variables = (SVM_Value*)MEM_malloc(sizeof(SVM_Value) * 
                                    svm->global_variable_count); // グローバル変数の領域を確保
    svm->global_variable_types = (uint8_t*)MEM_malloc(sizeof(uint8_t) * 
                                    svm->global_variable_count);
    for (int i = 0; i < svm->global_variable_count; ++i) {       // グローバル変数の型を読み込む
        svm->global_variable_types[i] = read_byte(&pos);        
    }

    svm->code_size = read_int(&pos);
    svm->code = (uint8_t*)MEM_malloc(svm->code_size);
    memcpy(svm->code, pos, svm->code_size);       // バイトコードの読み込み
    pos += svm->code_size;
    svm->stack_size = read_int(&pos);            // スタックサイズの読み込み     
}


static void init_svm(SVM_VirtualMachine* svm) {
    svm->stack = (SVM_Value*)MEM_malloc(sizeof(SVM_Value) * svm->stack_size); // スタックの確保
    svm->stack_value_type = (uint8_t*)MEM_malloc(sizeof(uint8_t) * svm->stack_size);
    svm->pc = 0;                     // プログラムカウンタの初期化
    svm->sp = 0;                     // スタックポインタの初期化


    for (int i = 0; i < svm->global_variable_count; ++i) {  // グローバル変数の初期化
        switch(svm->global_variable_types[i]) {
            case SVM_INT: {
                svm->global_variables[i].ival = 0;
                break;
            }
            case SVM_DOUBLE: {
                svm->global_variables[i].dval = 0.0;
                break;
            }
            default: {
                fprintf(stderr, "no such svm type\n");
                exit(1);
            }
        }
    }    
}

仮想マシンの実行

仮想マシンが実行するバイトコードの構成は，基本的に1バイトのオペレータと，(存在する場合は)2バイトのオペランド(BigEndian)なので，基本的には以下のような動作になる

1バイトのオペレータ読みこみ
必要に応じて2バイトのオペランド読み込み
オペレータの種類に応じた操作
1に戻る．ただし，プログラムカウンタがコードサイズを超えたら終了．

そのため，1と2の処理を関数にしておくと便利が良い．

svm.c

static uint8_t fetch(SVM_VirtualMachine* svm) {
    return svm->code[svm->pc++];
}

static uint16_t fetch2(SVM_VirtualMachine* svm) {
    uint8_t v1 = fetch(svm);
    return (v1 << 8) | fetch(svm);
}

次に，3に関する処理は様々だが，スタックへのPUSH/POP, 定数の読み出し，グローバル変数の読み書きは共通して行うことが予想できるので，それらも関数にしておく

svm.c

// 定数からSVM_Constantのポインタを返す
static SVM_Constant* read_static(SVM_VirtualMachine* svm, uint16_t idx) {
    return &svm->constant_pool[idx];
}

// 定数からint型の値を返す
static int read_static_int(SVM_VirtualMachine* svm, uint16_t idx) {
    return read_static(svm, idx)->u.c_int;
}
// スタックにint型の引数を積む．
static void push_i(SVM_VirtualMachine* svm, int iv) {
    svm->stack[svm->sp].ival = iv;
    svm->stack_value_type[svm->sp] = SVM_INT;
    svm->sp++;
}
// スタックからint型の値を取り出して返す．
static int pop_i(SVM_VirtualMachine *svm) {
    --svm->sp;
    return svm->stack[svm->sp].ival;
}

// head(SVM_Value)からoffsetを指定して，int型の値を書き込む
static void write_i(SVM_Value* head, uint32_t offset, uint32_t idx, int iv) {
    head[offset+idx].ival = iv;
}
// head(SVM_Value)からoffsetを指定して，int型の値を取り出す
static int read_i(SVM_Value* head, uint32_t offset, uint32_t idx) {
    return head[offset+idx].ival;
}

// グローバル変数のインデックスを指定してint型の値を書き込む
static void write_global_i(SVM_VirtualMachine* svm, uint32_t idx, int iv) {
    write_i(svm->global_variables, 0, idx, iv);
}
// グローバル変数のインデックスを指定して，int型の値を取り出す
static int read_global_i(SVM_VirtualMachine* svm, uint32_t idx) {
    return read_i(svm->global_variables, 0, idx);
}

実装は見たままだけど，write_i/read_iは再利用できるように定義した．というのも，スタックでもグローバル変数でも，結局はSVM_Value*の配列なので，使い回せるようにした．

ここまでを踏まえて，仮想マシンのメインルーチンは以下のようになる．

svm.c

static void svm_run(SVM_VirtualMachine* svm) {    
    bool running = true;

    uint8_t op = 0;
    while(running) {
        switch (op = fetch(svm)) {
            case SVM_PUSH_INT: { // push from constant pool
                uint16_t s_idx = fetch2(svm);
                int v = read_static_int(svm, s_idx);
                push_i(svm, v);
                break;
            }
            case SVM_POP_STATIC_INT: { // save val to global variable
                uint16_t s_idx = fetch2(svm); 
                int iv = pop_i(svm);
                write_global_i(svm, s_idx, iv);
                break;
            }
            case SVM_PUSH_STATIC_INT: {
                uint16_t s_idx = fetch2(svm);
                int iv = read_global_i(svm, s_idx);
                push_i(svm, iv);
                break;
            }
            case SVM_ADD_INT: {
                int iv1 = pop_i(svm);
                int iv2 = pop_i(svm);
                push_i(svm, (iv1+iv2));
                break;
            }
            case SVM_PUSH_FUNCTION: {
                uint16_t idx = fetch2(svm);
                push_i(svm, idx);
                break;
            }
            case SVM_INVOKE: {
                uint16_t f_idx = pop_i(svm);                
                switch (svm->functions[f_idx].f_type) {
                    case NATIVE_FUNCTION: {
                        SVM_Value val = svm->functions[f_idx].u.n_func(svm, 
                                &svm->stack[svm->sp], 
                                svm->functions[f_idx].arg_count);
                        svm->sp -= svm->functions[f_idx].arg_count;
                        svm->stack[svm->sp++] = val;                        
                        break;
                    }
                    default: {
                        fprintf(stderr, "no such function type in invoke\n");
                        exit(1);
                    }
                }
                break;
            }
            case SVM_POP: {
                pop_i(svm);
                break;
            }
            default: {
                fprintf(stderr, "unknown opcode: %02x in svm_run\n", op);
                show_status(svm);                
                exit(1);                
            }
        }                              
        running = svm->pc < svm->code_size;
    }
    show_status(svm);
}

細かい説明は省略するが，基本的には先に述べたとおりの振る舞いをするように実装している．

以下のコマンドを実行すると，次のような結果を得る

>./svm a.csb
C A P H E S U A 
constant_pool_count = 2
global_variable_count = 2
INT
INT
code_size = 27
stack_size = 4
hoge
< show SVM status >
-- global variable ---
[0:svm_int] = 9
[1:svm_int] = 9

--- stack ---
no allocated memory

わかりにくいけれど，もとのプログラムが

int print();
int j;
int i;
i = 4;
j = i = i + 5;
print();

だったので，グローバル変数に9が代入されていることでうまく動いていることが分かる．

また，解説には書いていないが，svm単体でディスアセンブルする機能を実装した

>./svm -d a.csb
disasm
C A P H E S U A 
constant_pool_count = 2
global_variable_count = 2
INT
INT
code_size = 27
stack_size = 4
push_int            0000   010000
pop_static_int      0001   090001
push_static_int     0001   070001
push_int            0001   010001
add_int                    0b
pop_static_int      0001   090001
push_static_int     0001   070001
pop_static_int      0000   090000
push_function       0000   2b0000
invoke                     2c
pop                        2a
no allocated memory

ここまでの実装/実行は，以下のコマンドで試すことができる．

>git clone https://github.com/hiro4669/csua.git
>cd csua
>git branch begin_svm origin/begin_svm
>git checkout begin_svm
>make
>./comp/cgent ./comp/tests/prog4.cs
>cp a.csb ./svm
>cd svm
>./svm a.csb
(略)
> ./svm -d a.csb
(略)

目次に戻る