Description

Code Trace – main()

Code Trace – lexer(const char*)
 Token:
 Identifier(x), Assign(=), Identifier(y), PostInc(++), Add(+),

Code Trace – lexer(const char*)
 lexer不會辨認是PostInc還是PreInc，只會辨認為”++”。
 方便起見，統一設kind = PreInc，PostDec/PreDec同理。
 lexer不會辨認是Plus還是Add，只會辨認為”+”。
 方便起見，統一設kind = Plus，Minus/Sub同理。
 在parser建完AST的時候，這些就會全部被定位出來。
Code Trace – token_list_to_arr(Token**)

Code Trace – parser(Token*, size_t)
 lexer無法辨別的PLUS/ADD和MINUS/SUB，在parser先行辨別。
 辨別後再呼叫parse正式開始構建AST。

switch (S) { case STMT: …… case EXPR: …… case ASSIGN_EXPR:
…… case ADD_EXPR:
…… case ……
…… case PRI_EXPR:
…… }
Code Trace – parse(Token*, int, int, GrammarState)
遵照grammar rule構建AST。
回傳當前範圍建出的AST arr的範圍: 左界 當前的state
Code Trace – parse(Token*, int, int, GrammarState)
 先嘗試走ASSIGN_EXPR -> UNARY_EXPR ASSIGN ASSIGN_EXPR的路線。
 找不到(if (nxt != -1))則當作ADD_EXPR往下走。
ASSIGN_EXPR
→ ADD_EXPR
| UNARY_EXPR ASSIGN ASSIGN_EXPR ;
case ASSIGN_EXPR:
if ((nxt = findNextSection(arr, l, r, condASSIGN)) != -1) { now = new_AST(arr[nxt].kind, 0);
now->lhs = parse(arr, l, nxt – 1, UNARY_EXPR); now->rhs = parse(arr, nxt + 1, r, ASSIGN_EXPR); return now;
}
return parse(arr, l, r, ADD_EXPR);
 其餘state類似。
Code Trace – parse(Token*, int, int, GrammarState)
 第1/2個TODO在這裡！
 完成MUL_EXPR的parse 完成UNARY_EXPR的parse
MUL_EXPR → …
; UNARY_EXPR
→ … ;
case MUL_EXPR:
// TODO: Implement MUL_EXPR.
// hint: Take ADD_EXPR as reference.
case UNARY_EXPR:
// TODO: Implement UNARY_EXPR.
// hint: Take POSTFIX_EXPR as reference.
 Hint:
 參考grammar rule
 參考其他state如何進行
Code Trace – semantic_check(AST*)
 檢查有沒有semantical error。
 ‘=’的左邊只能是Identifier或是被括號層層包圍的Identifier。
 ((((((z)))))))=x+y
 ‘++’/’–‘的底下只能是Identifier或是被括號層層包圍的
Identifier。
 ((((x))))++, –(((((y))))), ++z
Code Trace – semantic_check(AST*)
 第3個TODO在這裡！
 ASSIGN已經完成了，完成剩餘部份的semantic_check code。
 Hint:
 還剩下INC/DEC的部份
 semantic_check需要檢查所有AST node，如何做到?
// Operand of INC/DEC must be an identifier or identifier with on e or more parentheses.
// TODO: Implement the remaining semantic_check code. // hint: Follow the instruction above and ASSIGNpart code to implement.
// hint: Semantic of each node needs to be checked recursively (f rom the current node to lhs/mid/rhs node).
Code Trace – codegen(AST*)
 給定AST root，生出對應的ASM。
 第4個TODO在這裡！
 完成整個codegen
 codegen形式自由，你可以改parameter、return type，甚至整個結構
 其實你想重寫一份都可以
 直接輸出ASM，或是寫個ASM structure方便管理?
 Hint:
 整顆AST這麼大，我應該從哪開始生起?
void codegen(AST *root) {
// TODO: Implement your codegen in your own way.
}
Code Trace – utility interfaces
 提供各式各樣的function以利實作。
 err(x):
 輸入的expression不符合grammar / 無法通過semantic check時呼叫。
 DEBUG改為1可以方便看到錯誤產生在code的哪一行，上傳前要改回0。
#define err(x) { puts(“Compile Error!”); if(DEBUG) { fprintf(stderr, “Error at line: %d “, __LINE__); fprintf(stderr, “Error message: %s “, x);
} exit(0);
}
#define DEBUG 0
Code Trace – debug interfaces 提供debug function以利除錯。 將Token array與其長度

AST。
ISA Introduction
 包含7種instruction:
 add 加法運算 sub 減法運算 mul 乘法運算
 div 除法運算
 rem 模運算(%)
 load 將指定位置的memory資料存進指定位置的register中 store 將指定位置的register資料存進指定位置的memory中
ISA Introduction
 add: 花費10 cycle。
 add r0 r2 r7: 將r2與r7的值相加，並存在r0中。
 若r2=10, r7=1024, add執行完後，r0=r2+r7=1034。
 add r0 1 2: 將r0的值設為1+2。
 輸入的數值只能是非負整數(register和memory存的value沒關係)。
 其他的(sub, mul, div, rem)也類似。
 sub: 花費10 cycle
 mul: 花費30 cycle
 div: 花費50 cycle
 rem: 花費60 cycle
ISA Introduction
 load: 花費200 cycle
 load r1 [4]: 將memory [4]的值存進register r1中。
 若[4]=18, load執行完後，r1=18。 store: 花費200 cycle
 store [8] r3: 將register r3的值存進memory [8]中。
 若r3=-12, store執行完後，[8]=-12。
ISA Introduction
 變數: 僅x, y, z三個，分別存在memory [0], [4], [8]中。
 register限制: 可使用r0 – r255，但使用r8或以上的register將會有penalty。
 mul cycle為30，但若是mul r0 r12 r13，則cycle倍增為60。
 “Compile Error!”: 程式吃到錯誤的expression時應輸出此instruction。
 可以直接使用Macro err(x)來輸出並結束程式。
Assembly Compiler
 ASMC – Assembly Compiler，逐行輸入ASM，直到EOF時會吐出x, y, z最後的值與總耗費cycle數。
 x, y, z初始設定為2, 3, 5
 x, y, z可自訂初值，詳細設定參考github page。
 由於是用C++編寫，編譯請照github page上的步驟做。
 務必利用ASMC做debug，會有極大的幫助。
評分
 占總成績 8%
 一共24個testcases，其中有6個basic testcases公布在github page上。
 24筆testcases全過的同學中，總耗費cycle數最低的前10%會拿到總成績2分的 bonus。
 使用ASMC搭配python script做評分，一切以ASMC的輸出為準。
 評分時(x,y,z)初始值不會是(2,3,5)，而是[-100,100]的隨機值。偷吃步不用想了
Submission / Demo
 11/18(三) 晚上11:59前繳交code
 上傳到iLMS並命名為mini1.c
 demo time: 11/19(四) 晚上06:40起
 務必出席，若有事無法前來請事先告知。
 Demo結束後會在一定時間內公布通過的測資數與cycle數比賽的結果。
 若違反上述規則(未命名成mini1.c / 未出席demo …etc)，TA有權斟酌扣分。情節重大者(抄襲 …etc)可能會重罰或上報校方。

補充 – optimization
 盡可能地透過重新編排、計算已知等手段，使ASM得以能夠在減少總耗費cycle數的同時保持著運算的正確性。
 通常在codegen生完ASM時才進行。
Token *content = lexer(input);
size_t len = token_list_to_arr(&content); AST *ast_root = parser(content, len);
semantic_check(ast_root);
codegen(ast_root);
optimization通常在這裡 free(content);
freeAST(ast_root);

補充 – optimization
div r0 r0 10 mul r0 r0 5 rem r0 r0 2 sub r0 r0 31 store [0] r0
(x*(y/(z%5))))))) ))))))))
可以算的先算掉，能少掉很多inst
x=5+x y=x*x-(12*12)
補充 – optimization
load r0 [0] load r1 [4]
x=(2+3)/10*5%2-31
x=(x+(y-
(z*(x/(y%(z+(x-
(y*(z/(x%(y+(z-
(x*(y/(z%5))))))) ))))))))
x=5+x y=x*x-(12*12)
補充 – optimization
load r0 [0] load r1 [4]
x=(2+3)/10*5%2-31
x=(x+(y-
(z*(x/(y%(z+(x-
(y*(z/(x%(y+(zload r0 [8]
(x*(y/(z%5))))))) rem r0 r0 5
)))))))) load r1 [4] div r0 r1 r0 ……
x=5+x 不相關的insts可以交換，而不影響結果 y=x*x-(12*12)

y=x*x-(12*12)

補充 – optimization
x=(x+(y-
(z*(x/(y%(z+(x-
……
(y*(z/(x%(y+(zadd r0 0 3
(x*(y/(z%5))))))) store [0] r0
))))))))
x=3optimization
add r0 0 3
z=z*(z-z) store [0] r0
不影響最後結果的expression可以拿掉
x=y++ x=3
補充 – optimization
x=(x+(y-
(z*(x/(y%(z+(x-
(y*(z/(x%(y+(z-
(x*(y/(z%5))))))) )))))))) x=3
store [8] r0
未知的variable也可以得到已知的結果
x=y++ x=3
補充 – optimization

x=3
補充 – optimization
x=(x+(y-load r0 [4]
(z*(x/(y%(z+(x-add r0 r0 1
(y*(z/(x%(y+(z-store [4] r0
(x*(y/(z%5)))))))store [0] r0
))))))))add r0 0 3 x=3store [0] r0
optimization
z=z*(z-z)load r0 [4]
add r0 r0 1
store [4] r0
x=y++add r0 0 3 x=3 store [0] r0
依然能優化，存值最後做就好
如果中間還有用到x，務必要在register留下紀錄

補充 – optimization
 哪些可以省略? 哪裡可以縮短? reg用得太多怎麼處理?
 Compiler課程會講更多有關optimization的細節。
 Instruction數量減少與cycle減少之餘，最重要的是保持正確性。