Try   HackMD

2017q3 Homework3 (simulator)

tags: sysprog2017 dev_record

contributed by <HTYISABUG>

瞭解指令集

在開始使用之前, 需要先瞭解指令集
在 README.md 中有列出一部份指令的 opcode 以及用途,
但閱讀 tests 資料夾中的範例程式碼時發現有些指令未被列出
在 opcode.def 中找到了所有可用指令的列表











name,  opcode, has_op1, has_op2, has_result
halt,       0,       0,       0,          0
add,        1,       1,       1,          1
sub,        2,       1,       1,          1

...

jmp,       10,       1,       0,          0
call,      14,       1,       0,          0
ret,       15,       0,       0,          0

這份檔案中定義了指令的 opcode 與 prototype

實作 Fibonacci 數列

為了加快編程速度, 先將各版本用 C 寫一遍
再利用老師在你所不知道的 C 語言：編譯器和最佳化原理篇中提到的
GCC 編譯參數 -fdump-tree-cfg= 輸出 Basic Block
最後再轉換為模擬器可用的組合語言

應該提及詳細資訊，如何從 3-address code 轉換，又如何寫出給定 ISA 的組合語言程式

:notes: jserv

Iterative




















add     $0  $0  #4      ; n assignment
jge     #4  #4          ; if (n >= 0) goto 4
print   "n is less than 0"
halt
call    #7              ; call fib(n)
print   #2              ; print rtn
halt
add     $0  $-1 #8      ; <bb1> pre = -1
add     $0  $1  #9      ;       res = 1
add     $0  $0  #10     ;       i = 0
jmp     #15             ;       goto bb3
add     #8  #9  #11     ; <bb2> tmp = pre + res
add     $0  #9  #8      ;       pre = res
add     $0  #11 #9      ;       res = tmp
add     $1  #10 #10     ;       i++
sub     #4  #10 #11     ; <bb3> tmp = n - i
jge     #11 #11         ;       if (i <= n) goto bb2
add     $0  #9  #2      ; <bb4> rtn = res
ret

注意合理的輸入數值範圍

:notes: jserv

觀察主程式碼

vm.[ch]

  • vm_value
    • vm 通用數值型別
  • vm_operand
    • vm 通用暫存器型別
  • vm_inst
    • vm 通用指令型別
  • vm_opcode_impl
    • 覺得這型別似乎沒必要存在, 在整份程式碼中實際上沒起到作用
    • 這型別只在 _vm_env 中用到
    • 可以用 vm_handler 的陣列來取代
    • 已修正




typedef struct {
    int opcode; /* 這根本沒被使用到 */
    vm_handler handler;
} vm_opcode_impl;
  • vm_handler <- void (*) (VM_HANDLER_ARGS)
    • Instruction implement 的通用 function pointer
  • DISPATCH
    • 對應 CPU 中 PC 遞增並解碼的步驟
  • BEGIN_OPCODES
    • 紀錄標示所有 inst. implement 執行的位址的 label
    • 並在紀錄完後直接開始執行所有指令
    • 搭配 computed goto 以陣列管理 label
  • vm_run
    • 利用 goto 來避開 branch 判斷, 可以避開 branch miss 增加的 cycles !
  • HANDLER
    • 發現冗贅程式碼!
    • 這個 def 不僅完全沒有用到, OPCODE 所傳回的型別中實際上也沒有 handler 這個 member
    • 已修正

請提交 pull request 來修正
"jserv"

opcode.[ch]

  • 定義所有 opcode
  • 定義所有 instruction implement

as.[ch]

  • 解析組語

加入命令列參數

加入命令列參數 -i 設定預設數值











...

} else if (!strcmp(argv[i], "-i")) {
    if (i++ == argc - 1)
        FATAL(-1, "Missing default value, see -h\n");
    default_value = atoi(argv[i]);
    default_value_opt = 1;
} else if (!strcmp(argv[i], "-")) {

...

在初始化虛擬環境後, 加入是否使用預設參數的判斷




vm_env *env = vm_new();
if (default_value_opt)
    vm_set_default_value(env, default_value);

設定實作






void vm_set_default_value(vm_env *env, int arg)
{
    env->temps[0].type = INT;
    env->temps[0].value.vint = arg;
}

實作 label 功能

為了辨認各個標籤所指向的位址, 在虛擬環境 vm_env 中追加一個 label-address 表
在進行組譯之前先將所有程式碼掃過一遍, 提取 label
將 label 做 hash 並對表格大小取 mod 存入表格






































/* as.c line 324-354 */
static void get_label_from_line(vm_env *env, char *line, size_t addr)
{         
    char *line_backup = strdup(line);
    char *label = quoted_strsep(&line, ":");

    /*
     * label 獨立一行 & 無任何後贅
     * or
     * label 後有任何非 '\0' 字元
     */
    if (strlen(label) + 1 == strlen(line_backup) || strcmp(line, "") != 0) {
      label = quoted_strsep(&label, " ");
      vm_add_label(env, label, addr);
    }    

    free(line_backup);
}        
           
void make_table_from_fd(vm_env *env, int fd)
{
    char *line = NULL;
    size_t size = 0;
    FILE *fp = fdopen(fd, "r");
    size_t addr = 0;

    while (getline(&line, &size, fp) != -1) {
      if (line[0] == ';' || line[0] == '\n')
          continue;
      line[strcspn(line, "\r\n")] = 0;
      get_label_from_line(env, line, addr++);
    }    

    free(line);

    rewind(fp);
}

在組譯時, 如果遇到標籤就將其去除
如果標籤為獨立一行, 會在這一行插入 OP_NOP 以便標記位址
標籤去除後組譯行為與原本相同































/* as.c line 251-279 */
if (strlen(label) + 1 == strlen(line_backup)) {
    vm_inst new_inst;
    const struct instruction *inst = find_inst("nop");

    memset(&new_inst, 0, sizeof(vm_inst));
    new_inst.opcode = inst->opcode;
    vm_add_inst(env, new_inst);

    free(line_backup);

    return;
} else if (strcmp(line, "") != 0) {
    mnemonic = quoted_strsep(&line, " ");
    if (strcmp(line, "") == 0) {
        vm_inst new_inst;
        const struct instruction *inst = find_inst("nop");

        memset(&new_inst, 0, sizeof(vm_inst));
        new_inst.opcode = inst->opcode;
        vm_add_inst(env, new_inst);

        free(line_backup);

        return;
    }
} else {
    line = label;
    mnemonic = quoted_strsep(&line, " ");
}

最後在 make_operand 時, 如果收到的字串能在表格內搜索到
則將字串轉換成對應的位址作為 operand









/* as.c line 194-200 */
addr = vm_label2addr(env, data);

if (addr != -1) {
    op.type = TEMP;
    op.value.id = addr;
    break;
}

如此一來 vm_env 就支援 label 了
之前的 fib-iterative 可以改寫成



















        jge     #0  start       ; if (n >= 0) goto 4
        print   "n is less than 0"
        halt
start:  call    fib             ; call fib(n)
        print   #2              ; print rtn
        halt
fib:    add     $0  $-1 #8      ; <bb1> pre = -1
        add     $0  $1  #9      ;       res = 1
        add     $0  $0  #10     ;       i = 0
        jmp     bb3             ;       goto bb3
bb2:    add     #8  #9  #11     ; <bb2> tmp = pre + res
        add     $0  #9  #8      ;       pre = res
        add     $0  #11 #9      ;       res = tmp
        add     $1  #10 #10     ;       i++
bb3:    sub     #0  #10 #11     ; <bb3> tmp = n - i
        jge     #11 bb2         ;       if (i <= n) goto bb2
        add     $0  #9  #2      ; <bb4> rtn = res
        ret

不用再算那些行號了

寫完這段後去看了其他人的共筆
發現其他人都用其他 prefix 當作辨識符
HTYISABUG

其他

do{} while(0); 是為了避免單行 if 沒加大括弧造成巨集不完整的手法(參考此處) <- dangling else
HMKRL

Last changed by 
 
TSUNGYU HSIEH
0
478
Published on HackMD