HackMD2016q3 Homework5 (rubi)
contributed by<SwimGlass>, <carolc0708>
作業說明 A10: rubi
讀懂DynASM
- 目的: 將 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 指令 來量測時間
pi.rb:
real 0m3.342s
user 0m3.320s
sys 0m0.000s
執行時間大約 3 秒左右
優化實驗
- 在
parser.dasc中，觀察程式
skip():
int32_t skip(char *s)
{
if (!strcmp(s, tok.tok[tok.pos].val)) {
tok.pos++;
return 1;
}
return 0;
}
isassign():
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() 直接做優化，找有沒有更適合短字串的比較方式
- 參考資料，重新實作加速版的字串比較: 直接比較第一個字元，若不相同就不用在做下去
#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 優化
- 參考資料，做fast compare: 這個程式有bug
- 在
expr.dasc中
primExpr():
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 等。
typedef struct { char val[32]; int nline; } Token;
struct {
Token *tok;
int size, pos;
} tok;
想法是可以去重新設計紀錄 token 的資料結構
還要看懂lex中怎麼紀錄tok!!!Carol Chen
- 在
dasm_x86.h中
dasm_put():
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;
}
