2017q3 Homework3 (simulator)

contributed by <zhanyangch>

分析 full-stack-hello 程式架構

driver 中負責讀取使用者的輸入，並呼叫對應的函式

• as.c 將虛擬機器的組合語言組譯成機器碼，並且提供寫入、讀取 elf 檔案
• elf.c 處理 elf 所需要的 header
• opcode.c 實做虛擬機器指令集(不包含 j type)
• vm.c 實做虛擬機器環境、j type 指令

觀察虛擬機器執行

driver.c 可以接受不同的參數，先不看跟 elf 有關的部份
case ASSEMBLE_AND_EVAL

   case ASSEMBLE_AND_EVAL: {
        vm_env *env = vm_new();
        assemble_from_fd(env, in_fd);
        hook_opcodes(env);
        vm_run(env);
        vm_free(env);
        break;
    }

• 首先先建立虛擬機器的環境

struct __vm_env {
    vm_inst insts[INSTS_MAX_SIZE];             /* Program instructions */
    vm_value cpool[CPOOL_MAX_SIZE];            /* Constant pool */
    vm_value temps[TEMPS_MAX_SIZE];            /* Temporary storage */
    vm_opcode_impl impl[OPCODE_IMPL_MAX_SIZE]; /* OPCODE impl */
    vm_regs r;
    int insts_count;
    int cpool_count;
    int temps_count;
};

• 觀察 vm_regs 可以發現此 sturct 主要紀錄程式的狀態，而一般運算的 register 則是在 temps 內。

 typedef struct {
    size_t pc;    // program counter.
    size_t sp;    // stack runs from the end of 'temps' region.
    size_t from;  // the immediate PC before last branch/return.
    size_t to;    // the immediate PC after last branch/return.
} vm_regs;

• assemble_from_fd 此函式將指令的 operand 建立對應的 vm_inst 放入 env 的 insts 中，遇到常數時會呼叫 vm_add_const 將常數加入 env 的 cpool。
• hook_opcodes：將 opcode 的實做放入 env 的 impl
• vm_run：包含每個 opcode 對應的 label 利用 gcc 提供的 Labels-as-Values可以使用
  &&OP_CODE 得到 label address，放入 dispatch table 中，在每一個 instruction 的結尾執行 DISPATCH
  ，此方式稱為 direct threaded code
• vm_free 釋放記憶體空間

指令形式

• 算術運算

• add $40 $2 #1
$: 常數
  #: 暫存器(temps)

• conditional jump

• jz #1 #14
#1: 暫存器(temps)
  #14: 條件成立時跳到第14個指令

接受 command line 參數

參考st9007a的共筆
接受"–input <value>"的參數將 #0 初始化成<value>
首先在 driver.c 中 加入讀取 –input，在這裡使用 strtol 而非 atoi，原因是 atoi 對於無法處理的字串會回傳 0，但無法區別 0 是因為輸入錯誤或是數字 0而產生，因此無法偵測到錯誤，使用 strtol *pEnd 會被設為讀取完數字後的下一個字元，在這裡 pEnd 若非 '\0'，則代表沒有成功讀取數字

else if (!strcmp(argv[i], "--input")) {
    char *pEnd;
    if (!argv[i + 1])
        FATAL(-1, "--input need a integer as argument, see -h\n");
    temp_init_val = strtol(argv[++i], &pEnd, 10);
    if (*pEnd)
        FATAL(-1, "--input need a integer as argument, see -h\n");
} 

依據給定的 coding style，用 4-spaces 來排版上述程式碼
"jserv"

在 vm.[ch] 中加入 vm_set_temp_value

inline void vm_set_temp_value(vm_env *env, int id, int val)
{
    env->temps[id].type = INT;
    env->temps[id].value.vint = val;
}

driver.c 中呼叫 vm_set_temp_value

    case ASSEMBLE_AND_EVAL: {
        vm_env *env = vm_new();
        vm_set_temp_value(env, 0, temp_init_val);
        assemble_from_fd(env, in_fd);
        hook_opcodes(env);
        vm_run(env);
        vm_free(env);
        break;
    }

實作 Fibonacci 數列

iterative

目前採用 int 儲存計算結果，因此當輸入超過 46 時會產生 integer overflow

需要指出目前採用的 LP64 資料模型下，int 實質為 32-bit，而 fib(46) 尚在 32-bit 能表示的數值範圍內。

另外，除了給予輸入數值範圍的提示，也需要提出後續數值表示法的調整方案。

jserv

jz #0 #11
jlt #0 #16    ;check #0 >= 0
sub $46 #0 #4
jlt #4 #16    ;check #0 <= 46

sub #0 $1 #0

or $0 $0 #1; #1=0
or $1 $0 #2; #2=1
;for
add #1 #2 #3 ; fib = # 1+ #2
or #2 $0 #1  ;#1 = #2
or #3 $0 #2  ;#2 = fib
sub #0 $1 #0
jgt #0 #7

print #3
halt
;if #0 = 0 ,  print 0
print #0
halt
;limit n:0~46
print "Please use 0~46 as an input value."
halt

Recursive

jz #0 #10
jlt #0 #11 ;check #0 >= 0
sub $46 #0 #4
jlt #4 #11 ;check #0 <= 46

or $0 $0 #3 ;#3 for ans
call #12    ;call f(n)

print #3
halt
;if #0 = 0, print 0
print #0
halt
;limit n:0~46
print "Please use 0~46 as an input value."
halt

xor #0 $1 #5 ;check #0 == 1 
jz #5 #15    ;if true, do #3+=1
jmp #17      ;return
add #3 $1 #3 
ret

jz #0 #19 ;if true, return
jmp #20   ;call f(n-1), f(n-2)
ret 

sub #0 $1 #0
call #12
sub #0 $1 #0
call #12
add #0 $2 #0
ret

新增 label 的支援

• 觀察並修改 Add label support

原本的跳躍指令只能接受跳到某個絕對位置，但在寫程式時，若要新增或刪除指令，則需要將跳躍指令的參數做大量修改，藉由新增對 label 的支援，可以由組譯器幫忙計算跳躍的位置。

組譯的實做方法如下：

1. 當遇到 jmp :<label> 時新增vm_operand * label_reference，使用指標紀錄該 operand 的位置、label 的名稱

• as.c

static inline vm_operand make_operand(vm_env *env, char *line, const char *data)
{
    /*...*/
    case ':':
    op.type = LABEL;
    op.label = rm_comment_strdup(data + 1);
    break;
    /*...*/
}

• vm.c

size_t vm_add_inst(vm_env *env, vm_inst inst)
{
    env->insts[env->insts_count] = inst;
    if (inst.op1.type == LABEL)
        vm_add_label_ref(env,&env->insts[env->insts_count].op1);
    if (inst.op2.type == LABEL)
        vm_add_label_ref(env,&env->insts[env->insts_count].op2);
    return env->insts_count++;
}

2. 當遇到 <label>: 時新增 vm_label labels，紀錄 label 的名稱、當下的 pc

• vm.c

size_t vm_add_label(vm_env *env, char *label) {
    if (vm_find_label(env, label) != -1)
        FATALX(1, "Label '%s' redefinition\n", label);
    env->labels[env->labels_count].label = strdup(label);
    env->labels[env->labels_count].next_pc = env->insts_count;
    return env->labels_count++;
}

修正上述訊息的文法錯誤

jserv

3. 當讀取完整份檔案後，將每一個 label_reference 找到對應的 vm_label，將其 value.id 改為 vm_label 內紀錄的 pc 值

• vm.c

void vm_register_label(vm_env *env)
{
   for (int i = 0; i < env->label_refcnt; ++i) {
        env->label_ref[i]->value.id = vm_find_label(env, env->label_ref[i]->label);
        if(env->label_ref[i]->value.id == -1)
            FATALX(1,"Label Register Error: Label \"%s\" not found\n", env->label_ref[i]->label);
    }
}