# 2016q3 Homework5 (rubi) contributed by<`SwimGlass`>, <`carolc0708`> [作業說明 A10: rubi](https://hackmd.io/s/SyWEhlDJx) ## 讀懂DynASM https://hackmd.io/s/rkBOQ9okx * 目的: 將 brainfuck 的 interpreter 轉為 jit-compiler ## 程式架構分析 ### expr.dasc 翻譯所有符號運算子 * static inline int32_t isIndex() * static void primExpr() * static void mulDivExpr() * static void addSubExpr() * static void logicExpr() * void compExpr() ### parser.dasc 翻譯文字，如函式名稱、while、puts * char* getString() * Variable *getVar(char *name) * static Variable *appendVar(char *name, int type) * func_t *getFunc(char *name) * static func_t *appendFunc(char *name, int address, int espBgn, int args) * static int32_t make_break() * static int32_t make_return() * int32_t skip(char *s) * int32_t error(char *errs, ...) * static int eval(int pos, int status) * static Variable *declareVariable() * static int ifStmt() * static int whileStmt() * static int32_t functionStmt() * int expression(int pos, int status) : all * static char *replaceEscape(char *str):處理跳脫字元 * int (*parser())(int *, void **) : main * int32_t isassign() * int32_t assignment() ### stdlib.dasc 將 assembly 裡架構類似的 standard function 定義在一起 ，如 printf、fopen、rand * int make_stdfunc(char *name) ## 使用 gprof 分析 rubi 程式 執行 `dfs.rb` 結果: ``` Flat profile: Each sample counts as 0.01 seconds. no time accumulated % cumulative self self total time seconds seconds calls Ts/call Ts/call name 0.00 0.00 0.00 1928 0.00 0.00 skip 0.00 0.00 0.00 221 0.00 0.00 dasm_put 0.00 0.00 0.00 126 0.00 0.00 isassign 0.00 0.00 0.00 60 0.00 0.00 primExpr 0.00 0.00 0.00 59 0.00 0.00 mulDivExpr 0.00 0.00 0.00 57 0.00 0.00 getVar 0.00 0.00 0.00 55 0.00 0.00 expression 0.00 0.00 0.00 52 0.00 0.00 addSubExpr 0.00 0.00 0.00 45 0.00 0.00 compExpr 0.00 0.00 0.00 45 0.00 0.00 logicExpr 0.00 0.00 0.00 18 0.00 0.00 dasm_growpc 0.00 0.00 0.00 17 0.00 0.00 assignment 0.00 0.00 0.00 10 0.00 0.00 appendVar ``` 執行 `pi.rb` 結果: ``` Flat profile: Each sample counts as 0.01 seconds. no time accumulated % cumulative self self total time seconds seconds calls Ts/call Ts/call name 0.00 0.00 0.00 1383 0.00 0.00 skip 0.00 0.00 0.00 182 0.00 0.00 dasm_put 0.00 0.00 0.00 98 0.00 0.00 isassign 0.00 0.00 0.00 55 0.00 0.00 primExpr 0.00 0.00 0.00 54 0.00 0.00 getVar 0.00 0.00 0.00 43 0.00 0.00 mulDivExpr 0.00 0.00 0.00 35 0.00 0.00 expression 0.00 0.00 0.00 34 0.00 0.00 addSubExpr 0.00 0.00 0.00 31 0.00 0.00 compExpr 0.00 0.00 0.00 31 0.00 0.00 logicExpr 0.00 0.00 0.00 21 0.00 0.00 assignment 0.00 0.00 0.00 11 0.00 0.00 appendVar 0.00 0.00 0.00 11 0.00 0.00 dasm_growpc ``` 可以觀察到，最常被呼叫的函式為 `skip()`、 `dasm_put()` 、 `isassign()` 、 `primExpr()` 所以先以上述函式做為效能改善的目標 ## 量測 rubi 程式優化前的執行時間 * 使用 [time 指令](http://stackoverflow.com/questions/556405/what-do-real-user-and-sys-mean-in-the-output-of-time1) 來量測時間 `pi.rb`: ``` real 0m3.342s user 0m3.320s sys 0m0.000s ``` 執行時間大約 3 秒左右 ## 優化實驗 * 在 `parser.dasc`中，觀察程式 `skip()`: ```C= int32_t skip(char *s) { if (!strcmp(s, tok.tok[tok.pos].val)) { tok.pos++; return 1; } return 0; } ``` `isassign()`: ```C= int32_t isassign() { char *val = tok.tok[tok.pos + 1].val; if (!strcmp(val, "=") || !strcmp(val, "++") || !strcmp(val, "--")) return 1; if (!strcmp(val, "[")) { int32_t i = tok.pos + 2, t = 1; while (t) { val = tok.tok[i].val; if (!strcmp(val, "[")) t++; if (!strcmp(val, "]")) t--; if (!strcmp(val, ";")) error("%d: invalid expression", tok.tok[tok.pos].nline); i++; } if (!strcmp(tok.tok[i].val, "=")) return 1; } else if (!strcmp(val, ":") && !strcmp(tok.tok[tok.pos + 3].val, "=")) { return 1; } return 0; } ``` 可以發現有大量的 `strcmp()`，決定對 `strcmp()` 直接做優化，找有沒有更適合短字串的比較方式 * 參考[資料](http://leto.net/docs/C-optimization.php)，重新實作加速版的字串比較: 直接比較第一個字元，若不相同就不用在做下去 ```C= #define QUICK_STRCMP(a, b) (*(a) != *(b) ? \ (int) ((unsigned char) *(a) - \ (unsigned char) *(b)) : \ strcmp((a), (b))) ``` 在此把整段程式中的 `strcmp()` 都改掉。 執行 `pi.rb` 程式，並量測時間: ``` real 0m3.285s user 0m3.284s sys 0m0.000s ``` 時間快了 `0.1` 秒 * [使用 SSE 對 strcmp 優化](https://www.strchr.com/strcmp_and_strlen_using_sse_4.2) * 參考[資料](http://mgronhol.github.io/fast-strcmp/)，做fast compare: 這個程式有bug --- * 在 `expr.dasc`中 `primExpr()`: ```C= if (isdigit(tok.tok[tok.pos].val[0])) { // number? | mov eax, atoi(tok.tok[tok.pos++].val) } else if (skip("'")) { // char? | mov eax, tok.tok[tok.pos++].val[0] skip("'"); } else if (skip("\"")) { // string? // mov eax string_address | mov eax, getString() } else if (isalpha(tok.tok[tok.pos].val[0])) { // variable or inc or dec char *name = tok.tok[tok.pos].val; Variable *v; if (isassign()) assignment(); else { tok.pos++; if (skip("[")) { // Array? if ((v = getVar(name)) == NULL) error("%d: '%s' was not declared", tok.tok[tok.pos].nline, name); compExpr(); | mov ecx, eax if (v->loctype == V_LOCAL) { | mov edx, [ebp - v->id*4] } else if (v->loctype == V_GLOBAL) { // mov edx, GLOBAL_ADDR | mov edx, [v->id] } ``` 除了大量呼叫`skip()`以外，也經常用到儲存 token 的資料結構 `tok.tok[tok.pos]`。 * token 的資料結構定義在 `rubi.h` 中，目的是用來記錄 `lex()` (定義在 `lex.c`) 過程當中， rubi程式各種可能出現的 token 的集合，例如 +、-、puts、printf 等。 ```C= typedef struct { char val[32]; int nline; } Token; struct { Token *tok; int size, pos; } tok; ``` 想法是可以去重新設計紀錄 token 的資料結構 >還要看懂lex中怎麼紀錄tok!!![name=Carol Chen] --- * 在 `dasm_x86.h` 中 `dasm_put()`: ```C= while (1) { int action = *p++; if (action < DASM_DISP) { ofs++; } else if (action <= DASM_REL_A) { int n = va_arg(ap, int); b[pos++] = n; switch (action) { case DASM_DISP: if (n == 0) { if ((mrm&7) == 4) mrm = p[-2]; if ((mrm&7) != 5) break; } case DASM_IMM_DB: if (((n+128)&-256) == 0) goto ob; case DASM_REL_A: /* Assumes ptrdiff_t is int. !x64 */ case DASM_IMM_D: ofs += 4; break; case DASM_IMM_S: CK(((n+128)&-256) == 0, RANGE_I); goto ob; case DASM_IMM_B: CK((n&-256) == 0, RANGE_I); ob: ofs++; break; case DASM_IMM_WB: if (((n+128)&-256) == 0) goto ob; case DASM_IMM_W: CK((n&-65536) == 0, RANGE_I); ofs += 2; break; case DASM_SPACE: p++; ofs += n; break; case DASM_SETLABEL: b[pos-2] = -0x40000000; break; /* Neg. label ofs. */ case DASM_VREG: CK((n&-8) == 0 && (n != 4 || (*p&1) == 0), RANGE_VREG); if (*p++ == 1 && *p == DASM_DISP) mrm = n; continue; } ```