# 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 語言：編譯器和最佳化原理篇](https://hackmd.io/s/Hy72937Me)中提到的
GCC 編譯參數 `-fdump-tree-cfg=` 輸出 Basic Block
最後再轉換為模擬器可用的組合語言
:::danger
應該提及詳細資訊，如何從 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

:::danger
注意合理的輸入數值範圍

: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 來修正
> [name="jserv"][color=red]

### 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 當作辨識符
> [name=HTYISABUG]

---

## 其他

> `do{} while(0);` 是為了避免單行 if 沒加大括弧造成巨集不完整的手法([參考此處](https://stackoverflow.com/questions/923822/whats-the-use-of-do-while0-when-we-define-a-macro)) <- **dangling else**
> [name=HMKRL]