# 2017q3 Homework3 (simulator)
###### tags: `sysprogram`
contributed by <`st9007a`>
## [Github](https://github.com/st9007a/full-stack-hello)
## 開發環境
```
Linux 4.4.0-92-generic
Ubuntu 16.04.1 LTS
CPU family: 6
CPU model: 94
CPU model name: Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
```
## 解析原始碼
在 `full-stack-hello` 這個 repo 中,主要以 `driver.c` 這支程式為操作的主體,其他程式提供相關的函式:
- `vm`:虛擬機器,內涵虛擬機器的架構, 運作
- `opcode`:自訂指令集,以及相關實作,實作主要用於虛擬機器
- `as`:組譯器,用於組譯自訂指令集,產生對應的 object file
- `elf`:提供產生 object file 相關的函式
### vm 架構
vm 架構可以從 `vm_env` 以及 `vm_regs` 來得知
```clike
typedef struct {
size_t pc; // program counter.
size_t sp; // stack runs from the end of 'temps' region.
size_t from; // the immediate PC before last branch/return.
size_t to; // the immediate PC after last branch/return.
} vm_regs;
struct __vm_env {
vm_inst insts[INSTS_MAX_SIZE]; /* Program instructions */
vm_value cpool[CPOOL_MAX_SIZE]; /* Constant pool */
vm_value temps[TEMPS_MAX_SIZE]; /* Temporary storage */
vm_opcode_impl impl[OPCODE_IMPL_MAX_SIZE]; /* OPCODE impl */
vm_regs r;
int insts_count;
int cpool_count;
int temps_count;
}
```
register:
- pc:program counter,指向目前執行的指令的位置
- sp:stack pointer,指向目前 stack 最後的位置
- from:指向最後一個 branch/return 之前的 pc 所指向的位置
- to:指向最後一個 branch/return 之後的 pc 所指向的位置
storage:
- insts:紀錄 program 中每個 instruction
- cpool:儲存 program 中使用的常數
- temps:從 0 開始記錄暫存的變數,從尾端開始則是 stack,用於處理 call 跟 ret 指令 (類似 heap 與 stack 的關係,但是 heap 的部分不一樣)
:::danger
在給定的指令集中,規範了 heap 嗎?
:notes: jserv
:::
其他:
- impl:instruction 的 opcode 對應的實作 ( handler ),在啟動虛擬機時,handler 會 hook 到對應的 opcode
:::danger
應該一併提及如何從 `opcode.def` 產生對應 `opcode.h` 的過程,以及搭配 computed goto 實作更高效的 opcode dispatch。
參見: [Computed goto for efficient dispatch tables](https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables)
:notes: jserv
:::
### 補充 - 自訂指令集
在 vm 中所使用的指令集被定義於 `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
mul, 11, 1, 1, 1
div, 12, 1, 1, 1
mod, 13, 1, 1, 1
and, 16, 1, 1, 1
or, 17, 1, 1, 1
not, 18, 1, 1, 0
xor, 19, 1, 1, 1
lsl, 20, 1, 1, 1
lsr, 21, 1, 1, 1
asr, 22, 1, 1, 1
print, 3, 1, 0, 0
jlt, 4, 1, 1, 0
jle, 5, 1, 1, 0
jz, 6, 1, 1, 0
jge, 7, 1, 1, 0
jgt, 8, 1, 1, 0
jnz, 9, 1, 1, 0
jmp, 10, 1, 0, 0
call, 14, 1, 0, 0
ret, 15, 0, 0, 0
```
從欄位可以很容易得知,裡面分別定義該指令的名字, opcode, 以及 oprand,接著 `opcode.h` 這支檔案可以透過 `opcode.def` 以及 `scripts/gen_opcode.py` 來自動產生,簡單列一下 `gen_code.py` 的架構如下:
```
OPCODE : class
-__gt__ : function
-__init__ : function
-__repr__ : function
-__str__ : function
+main : function
+write_opcode : function
```
`OPCODE` 這個 class 存著 instruction 的設定,透過 `main()` 將 `opcode.def` 的設定放進 `OPCODE` 中,接著 `write_opcode()` 利用所有 `OPCODE` 來產生出 `opcode.h`
這樣的作法讓指令集的擴增修改變的很靈活,只需在 `opcode.def` 中加入新的指令設定,然後在 `opcode.c` 中實作該指令的行為,最後在 `hook_opcodes()` 中把實作 hook 到對應的 opcode 就完成了
:::danger
TODO: 釐清以下議題:
1. instruction encoding 的長度,如 [Stored Program and Instruction Representation](http://www.eecg.toronto.edu/~moshovos/ECE243-2008/l19-instruction-representation-stored-program.html) 的分析;
2. 作為一個 register-based virtual machine (而非 stack-based, 如 Java VM),能否進一步縮減編碼的空間開銷,進而提升 code density 呢?
:notes: jserv
:::
### vm 運作
vm 的運作有使用到大量的 macro
```clike
void vm_run(vm_env *env)
{
BEGIN_OPCODES;
OP(ADD) : VM_CALL_HANDLER();
OP(SUB) : VM_CALL_HANDLER();
OP(MUL) : VM_CALL_HANDLER();
OP(DIV) : VM_CALL_HANDLER();
OP(MOD) : VM_CALL_HANDLER();
OP(AND) : VM_CALL_HANDLER();
OP(OR) : VM_CALL_HANDLER();
OP(NOT) : VM_CALL_HANDLER();
OP(XOR) : VM_CALL_HANDLER();
OP(LSL) : VM_CALL_HANDLER();
OP(LSR) : VM_CALL_HANDLER();
OP(ASR) : VM_CALL_HANDLER();
OP(PRINT) : VM_CALL_HANDLER();
OP(JLT) : VM_JLT();
OP(JLE) : VM_JLE();
OP(JZ) : VM_JZ();
OP(JGE) : VM_JGE();
OP(JGT) : VM_JGT();
OP(JNZ) : VM_JNZ();
OP(JMP) : GOTO(OPCODE.op1.value.id);
OP(CALL) : VM_CALL(OPCODE.op1.value.id);
OP(RET) : VM_RET();
OP(HALT) : goto terminate;
END_OPCODES;
terminate:
return;
}
```
- BEGIN_OPCODES:產生 op label set,並且跳到第一個 instruction 對應的 op label
- OP:產生對應的 label
- VM_CALL_HANDLER, VM_CALL, VM_RET, VM_J\*:根據 instruction 執行不同 handler
- OPCODE:取得目前 pc 指向的位置的 instruction
- OPCODE_IMPL:取得對應的 handler
- DISPATCH:將 pc 指向下一個 instruction,並且跳到對應的 label 執行
- GOTO:將 pc 指向特定位置,並將 pc 轉跳前後所指的位置存入暫存器 from, to
:::danger
這段程式碼使用到 [threaded code](https://en.wikipedia.org/wiki/Threaded_code) 的技巧,請以對應的 direct threading 解釋其效益,並對照單純的 switch-case,在效能上的落差
:notes: jserv
:::
### 補充 - opcode dispatch
vm 的運作會將要執行的檔案處理成 bytecode 存放在 `vm_env` 這個結構中,執行時每次根據 pc 指向的位置去取得 bytecode 形式的 instruction 然後跳到對應的程式碼來執行該指令 ( 具體運作程式碼在上一小節 )
從 vm 的運作方式可以知道,如何根據目前的 opcode 跳到對應的程式碼的實作會影響 vm 的效能,根據 [Computed goto for efficient dispatch tables](https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables) 這篇提到了兩種實作方式,switch - case 以及 computed goto
switch - case 透過一個無窮迴圈內含一個 switch 來判斷目前的 bytecode 應該執行什麼程式,類似的實作還有 [這篇](http://bartoszsypytkowski.com/simple-virtual-machine/),程式碼大致如下:
```clike
while (1) {
switch (instr[pc++]) {
case OP_1:
OP_1();
break;
case OP_2:
OP_2();
break;
...
}
}
```
computed goto 是 <s>C 語言的 feature</s> GCC extension,參照 [gcc - labels as values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html),可以將 label 的 address 存入 `void *` 型態的 pointer 中,用法如下:
```clike
void *ptr = &&label;
...
goto *ptr;
```
也能一次跟陣列搭配使用,先前提到的 `opcode.h` 中就有使用到
```clike
static void *array[] = { &&foo, &&bar, &&hack };
...
goto *array[0];
```
而使用 computed goto 來進行 opcode dispatch 的話,程式碼大致如下:
```clike
static void *op_labels = { &&OP_1, &&OP_2, .... };
#define DISPATCH() goto *op_labels[instr[pc++]]
...
OP_1:
OP_1();
DISPATCH();
OP_2:
OP_2();
DISPATCH();
...
```
這兩種的效能比較可以從兩個地方來看:
- bounds checking
- branch prediction
bounds checking 是在 switch 中執行的一個環節,每次迴圈中檢查是否有 default case 的狀況,在參考資料中提到,即使程式中的 switch 沒有用到 default case,compiler 在編譯時還是會產生強制檢查的程式,所以 switch 會較 computed goto 多花一個 bounds checking 的步驟
branch prediction 的部分,switch 需要預測接下來跳到哪個分支 case,而 computed goto 則是在每個 instruction 預測下一個 instruction,這之中比較直覺的想法是 computed goto 的可以根據上個指令來預測,但是 switch 的每次預測沒辦法根據上個指令,因此在 branch prediction accuracy 上 computed goto 會比較高
根據上述兩點來看,computed goto 是比較有效率的實作方式
:::danger
TODO: 研讀 [Stack caching for interpreters](https://dl.acm.org/citation.cfm?id=207165) 論文,思考進一步透過 caching top-of-stack 來提升效能的機制。
:notes: jserv
:::
## 接受輸入參數
作業要求讓 vm 可以接受輸入參數,所以決定將輸入參數存入 vm 中的 `#0` 位置,在 `vm.h` 及 `vm.c` 加入一個可以設定 `temps` 的值的函式
```clike
inline void vm_set_temp_value(vm_env *env, int pos, int val)
{
vm_value v = {.type = INT};
v.value.vint = val;
env->temps[pos] = v;
}
```
然後在 `driver.c` 中解析 `argv` 的部份加入 `--input` 的判斷
```clike
int vm_init_val = 0;
...
else if (!strcmp(argv[i], "--input")) {
if (!argv[i + 1])
FATAL(-1, "--input need a integer as argument, see -h\n");
vm_init_val = atoi(argv[++i]);
}
...
```
接著在 `driver.c` 中初始化 vm 的下一行都強制設定 `#0`
```clike
vm_env *env = vm_new();
vm_set_temp_value(env, 0, vm_init_val);
```
最後在 `Makefile` 中加入 Fibonacci 數列的相關操作
```
TEMP0 ?= 1
IN_FILE ?= ./tests/fib-iterative.s
fib: $(EXEC)
@./$(EXEC) --input $(TEMP0) $(IN_FILE)
```
:::danger
參照 [simple.vm](https://github.com/skx/simple.vm) 引入 fuzz testing
:notes: jserv
:::
## Fibonacci 數列
### Iterative
```
; if #0 = 0, just print 0
xor #0 $0 #1
jz #1 #13
sub #0 $1 #0
; f0 = 0, f1 = 1
or $0 $0 #1
or $1 $0 #2
; iteration
add #1 #2 #3
or $0 #2 #1
or $0 #3 #2
sub #0 $1 #0
jz #0 #11
jgt #0 #5
; print result
print #3
halt
; print result if input = 0
print $0
halt
```
這是一個簡易版本的 iterative 實作,輸入參數存放在 `#0`,輸出結果存放在 `#3`,`#1` 跟 `#2` 一開始分別存放 $f(0)$ 跟 $f(1)$ 的答案,其中 xor 跟 or 指令分別是拿來替代 x86 instruction set 中的 cmp 以及 mov
### Recursive
```
; init result at #3
or $0 $0 #3
; f0 = 0, f1 = 1
or $0 $0 #1
or $1 $0 #2
call #6
; print result
print #3
halt
; recursion
xor #0 #2 #5
jz #5 #9
jnz #5 #11
add #3 #2 #3
ret
xor #0 #1 #5
jz #5 #14
jnz #5 #15
ret
sub #0 $1 #0
call #6
sub #0 $1 #0
call #6
add #0 $2 #0
ret
```
接著是簡易版本的 recursive 實作,輸入參數存放在 `#0`,輸出存放在 `#3`,recursive 的部分可以看成一個 function,這個 function 的 input 也是 `#0`,每次都會比較 input 是否為 0 或 1,是的話就將$f(0)$ 或 $f(1)$ 加進去 `#3`,不是的話就呼叫 f( `#0` - 1 ) 跟 f( `#0` - 2 ),由於在呼叫的過程中 `#0` 的值會不斷減少,所以最後要加回來
### Tail Recursion
```
; init
or $0 $0 #1
or $0 $1 #2
or $0 $0 #3
; call func
call #6
print #3
halt
; tail recursion
xor #0 $0 #4
jz #4 #9
jnz #4 #11
or #1 $0 #3
ret
xor #0 $1 #4
jz #4 #14
jnz #4 #16
or #2 $0 #3
ret
; #1 = #2, #2 = #1 + #2
or #1 $0 #5
or #2 $0 #1
add #2 #5 #2
sub #0 $1 #0
call #6
ret
```
tail recursion 跟一般遞迴的差在於它會把目前為止累積的答案傳給下一個遞迴的 function call,這樣的作法可以減少遞迴的重複運算,這裡的實作參考了 [Tail recursion for fabonacci](http://www.geeksforgeeks.org/tail-recursion-fibonacci/),初始設定 `#1 = f(0) = a, #2 = f(1) = b, #0 = n`,然後每次遞迴會執行:
```clike
int fib(int n, int a = 0, int b = 1)
{
if (n == 0)
return a;
if (n == 1)
return b;
return fib(n - 1, b, a + b);
}
```
:::danger
計算和比較 tail recursion 運用後,實際 cycle count 的落差
:notes: jserv
:::
### Fast doubling
```
xor #0 $0 #1
jz #1 #32
; init variable
or $1 $0 #1 ; t0 = 1
or $1 $0 #2 ; t1 = 1
or $1 $0 #3 ; t3 = 1
or $0 $0 #4
or $1 $0 #5 ; i = 1
; while (i < n)
or #0 $0 #6 ; copy input to #6
sub #6 #5 #6
jlt #6 #30
jz #6 #30
; if ((i << 1) <= n)
or #0 $0 #6
lsl #5 $1 #7
sub #7 #6 #7
jgt #7 #25
mul #2 #2 #4 ; t4 = t1 * t1
mul #1 #1 #7 ; tmp = t0 * t0
add #4 #7 #4 ; t4 += tmp
mul $2 #2 #3 ; t3 = t1 * 2
sub #3 #1 #3 ; t3 -= t0
mul #1 #3 #3 ; t3 *= t0
or $0 #3 #1 ; t0 = t3
or $0 #4 #2 ; t1 = t4
lsl #5 $1 #5 ; i <<= 1
jmp #7
; else
or $0 #3 #1 ; t0 = t3
or $0 #4 #3 ; t3 = t4
add #4 #1 #4 ; t4 += t0
add #5 $1 #5 ; i += 1
jmp #7
print #3
halt
print $0
halt
```
fast doubling 是基於 Fabonacci Q-Matrix 推導出來的,主要有兩個公式:
$F(2k) = F(k) \times (2F(k + 1) - F(k))$
$F(2k + 1) = F(k + 1)^2 + F(k)^2$
然後參考 [你所不知道的C語言:遞迴呼叫篇](https://hackmd.io/s/rJ8BOjGGl#fibonacci-sequence) 中的程式碼,將其轉換成組合語言版本
## Profiler
為了能計算總共使用的 instructions 數量,寫一個 `profiler.c`:
```clike
static uint32_t exec_instr_cnt = 0;
inline void profiling()
{
#if defined(profile)
exec_instr_cnt++;
#endif
}
void show_profiling_info()
{
printf("Instructions: %u\n", exec_instr_cnt);
}
```
然後在每個 handler 相關的 macro 都加入 `profiling();`,最後在 `vm_run()` 加入程式碼:
```clike
void vm_run(vm_env *env)
{
...
END_OPCODES;
terminate:
#if defined(profile)
show_profiling_info();
#endif
return;
}
```
如此就能透過 `Makefile` 來決定是否開啟 profiler
以下簡單顯示結果:
```
$ ./as_exec --input 20 tests/fib-iterative.s
6765
Instructions: 120
$ ./as_exec --input 20 tests/fib-recursive.s
6765
Instructions: 183492
$ ./as_exec --input 20 tests/fib-tailrecursion.s
6765
Instructions: 241
$ ./as_exec --input 20 tests/fib-fastdoubling.s
6765
Instructions: 208
```
## Add Label Support
由於在測試組合語言過程中頻繁修改程式碼,每次改完都要注意 call 跟 j type 指令有沒有跳錯位置,工作效率不佳,因此決定先把 label 功能加上去,看了 [Add label support](https://github.com/jserv/full-stack-hello/pull/30) 後,參考裡面的一些設計,如:使用 `:` 當作 label 的 prefix
接著 label 的實作策略用 two-pass assembler 的運作原理:掃程式碼一遍,把所有 label 跟對應的位置放在 symbol table,再掃程式碼一遍,把 call 跟 j type 指令跳的 label 根據 symbol table 轉成對應的位置
對應的程式碼寫在 `as.c` 中:
```clike
struct __symbol_table {
char *labels[SYMBOL_TABLE_SIZE];
int address[SYMBOL_TABLE_SIZE];
int count;
};
static symbol_table symtab = {.count = 0};
static void insert_to_symtab(char *label, int address)
{
assert(symtab.count < SYMBOL_TABLE_SIZE);
for (int i = 0; i < symtab.count; i++) {
assert(strcmp(label, symtab.labels[i]) != 0);
}
symtab.labels[symtab.count] = strdup(label);
symtab.address[symtab.count] = address;
symtab.count++;
}
static int search_symtab(char *label)
{
for (int i = 0; i < symtab.count; i++) {
if (strcmp(symtab.labels[i], label) == 0)
return symtab.address[i];
}
return -1;
}
static void lookup_address(vm_env *env)
{
vm_inst *inst = NULL;
for (int i = 0; (inst = get_vm_inst(env, i)) != NULL; i++) {
if (inst->op1.type == LABEL) {
int new_addr = search_symtab(inst->op1.value.label);
assert(new_addr != -1);
inst->op1.value.id = new_addr;
}
if (inst->op2.type == LABEL) {
int new_addr = search_symtab(inst->op2.value.label);
assert(new_addr != -1);
inst->op2.value.id = new_addr;
}
}
}
```
主要是新增了 symbol table 的結構,以及對 symbol table 的操作,`lookup_address()` 是上面提到的掃第二次程式碼時對其做 label 替換的函式,細節程式碼可以參照 [github](https://github.com/st9007a/full-stack-hello/commit/150ec6d4bf4bf9e64349d49de1d5a0e30b8a901d)
最後測試一下:
```
call :testcall
print "fail"
halt
testcall print "call success"
jmp :testjmp
print "fail"
halt
testjmp print "jmp success"
or $0 $0 #0
jz #0 :testjz
print "fail"
halt
testjz print "jz success"
add $1 #0 #0
jnz #0 :testjnz
print "fail"
halt
testjnz print "jnz success"
jge #0 :testjge1
print "fail"
halt
testjge1 print "jge success"
sub #0 $1 #0
jge #0 :testjge2
print "fail"
halt
testjge2 print "jge success"
jle #0 :testjle1
print "fail"
testjle1 print "jle success"
sub #0 $1 #0
jle #0 :testjle2
print "fail"
halt
testjle2 print "jle success"
jlt #0 :testjlt
print "fail"
halt
testjlt print "jlt success"
add #0 $2 #0
jgt #0 :testjgt
print "fail"
halt
testjgt print "jgt success"
halt
```
執行結果:
```
$ ./as_exec tests/label.s
call success
jmp success
jz success
jnz success
jge success
jge success
jle success
jle success
jlt success
jgt success
```
## 效能比較
首先先比較有效範圍內(0 ~ 46)四種演算法所花費的指令數量,這裡只顯示(0 ~ 40):
![](https://i.imgur.com/SU9DayC.png)
可以看到 recursive 的指令數量是指數成長,這也符合 recursive 的時間複雜度為 $O(2^n)$,而 iterative 跟 tail recursion 的時間複雜度為 $O(n)$,所以是線性成長,但是由於 tail recursion 每次 iteration 做的指令比較多,所以斜率比較大
接著 fast doubling 在迴圈中的行為是先用每次迴圈乘 2 跳到最接近輸入的值之後再做改成每次迴圈加 1,所以會出現驟降的現象,驟降會發生在輸入值剛好是 2 的指數的時候
為了更仔細比較 iterative 跟 fast doubling 的差異,在不考慮 integer overflow 的狀況下,比較輸入數值 0 ~ 20000 的指令數量:
![](https://i.imgur.com/kyJyZ26.png)
可以看到在大部分的情況下,fast doubling 的指令數量小於 iterative 的指令數量,尤其是輸入數值越接近 $2^n$,差異越大
:::danger
參照之前學生的報告 [Fibonacci fast doubling: ARM assembly 實作](https://www.slideshare.net/erickitten/fibonacci-fast-doubling),引入 clz 一類的指令,可再提升 fast doubling 的效能
:notes: jserv
:::
## Fast Doubling with CLZ
參考 [Fibonacci fast doubling: ARM assembly 實作](https://www.slideshare.net/erickitten/fibonacci-fast-doubling),引入 clz 指令,在 opcode.def 加入 clz 指令:
```
clz, 23, 1, 1, 0
```
接著在 `opcode.c` 實作,這裡使用 built in function 來實作:
```clike
static void clz_impl(VM_HANDLER_ARGS)
{
if (VM_T(op1) == INT && VM_T(op2) == INT) {
VM_INT(op2) = __builtin_clz(VM_INT(op1));
} else {
UNIMPL;
}
}
```
有了 clz 指令後,寫一個 fast doubling with clz 的版本:
```
xor $0 #0 #1
jz #1 :output
clz #0 #1
sub $30 #1 #1
or $1 $0 #2
or $1 $0 #3
xor $1 #0 #4
jz #4 :exit
fib lsl #3 $1 #4
sub #4 #2 #4
mul #4 #2 #4
mul #2 #2 #6
mul #3 #3 #5
add #5 #6 #5
or #5 $0 #3
or #4 $0 #2
lsr #0 #1 #5
and #5 $1 #5
jz #5 :no_adv
add #2 #3 #4
or #3 $0 #2
or #4 $0 #3
no_adv jz #1 :exit
sub #1 $1 #1
jmp :fib
exit or #2 $0 #0
output print #0
halt
```
它的原理是利用 clz 算出最高有效位右邊的 bit 數,接著利用 bit-shift 從最高有效位開始一個一個往右檢查,每檢查一個 bit 就做 1 次 fast doubling 運算,如果檢查到的 bit 為 1,就做一次 $f(n) = f(n-1) + f(n-2)$ 的計算
這樣的作法大幅減少了原本版本 fast doubling 的 else condition 的計算,下圖為輸入數值 0 ~ 1000 原本的 fast doubling 跟 clz 版的 fast doubling 比較
![](https://i.imgur.com/00Cxaqj.png)
由於原本的 else condition 所做的運算開銷非常大,引入 clz 重新實作後,指令數量大幅的減少
## 參考資料
[stackoverflow - Are the shift operators (<<, >>) arithmetic or logical in C?](https://stackoverflow.com/questions/7622/are-the-shift-operators-arithmetic-or-logical-in-c)
[Linux 的目的檔](http://ccckmit.wikidot.com/lk:objfile)
[stackexchange - What exactly is virtual machine bytecode ?](https://softwareengineering.stackexchange.com/questions/231054/what-exactly-is-virtual-machine-bytecode)
[Simple Virtual Machine](http://bartoszsypytkowski.com/simple-virtual-machine/)
[gcc - labels as values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html)
[stackoverflow - What is tail recursion ?](https://stackoverflow.com/questions/33923/what-is-tail-recursion)
[Tail recursion for fabonacci](http://www.geeksforgeeks.org/tail-recursion-fibonacci/)
[Stack based vs Register based Virtual Machine Architecture, and the Dalvik VM](https://markfaction.wordpress.com/2012/07/15/stack-based-vs-register-based-virtual-machine-architecture-and-the-dalvik-vm/)
[Fibonacci fast doubling: ARM assembly 實作](https://www.slideshare.net/erickitten/fibonacci-fast-doubling)