# 2017q3 Homework3 (simulator)
###### tags: `sysprog2017` `dev_record`
contributed by <`HTYISABUG`>
---
## 瞭解指令集
在開始使用之前, 需要先瞭解指令集
在 `README.md` 中有列出一部份指令的 opcode 以及用途,
但閱讀 `tests` 資料夾中的範例程式碼時發現有些指令未被列出
在 `opcode.def` 中找到了所有可用指令的列表
```csv=
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
```asm=
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` 的陣列來取代
- 已修正
```c=
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` 設定預設數值
```c=
...
} 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], "-")) {
...
```
在初始化虛擬環境後, 加入是否使用預設參數的判斷
```c=
vm_env *env = vm_new();
if (default_value_opt)
vm_set_default_value(env, default_value);
```
設定實作
```c=
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 存入表格
```c=
/* 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` 以便標記位址
標籤去除後組譯行為與原本相同
```c=
/* 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
```c=
/* 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 可以改寫成
```asm=
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]