開發紀錄(sandbox)

sysprog21/moxiebox

Toolchain:

crosstool-ng

先安裝工具
$ ./bootstrap
$ ./configure

過程中缺少工具
$ sudo apt-get install gperf
$ sudo apt-get install bison
$ sudo apt-get install help2man
$ sudo apt-get install libncurses5-dev 
接著
$ make 
$ sudo make install
$ mkdir -p ~/build-toolchain
$ cd ~/build-toolchain
$ ct-ng moxie-none-moxiebox
$ ct-ng build

PATH設定

export PATH=$PATH:~/x-tools/moxie-none-moxiebox/bin

實作 Fibonacci 數列

參考你所不知道的C語言：遞迴呼叫篇撰寫 C 語言程式，並透過 __attribute__((optimize("O0"))) 取消最佳化，或者於 CFLAG 內新增 -o0 參數

Tail recursion





int __attribute__((optimize("O0"))) fib_tail_recursion(int n, int a, int b)
{
    if (n == 0) return a;
    return fib_tail_recursion(n - 1 , b, a + b);
}

參考 moxie-none-moxiebox-gcc 產生的組合語言程式碼，以此為基礎去觀察並優化

$ moxie-none-moxiebox-gcc -S fib_tail_recursion.c
$ cat fib_tail_recursion.s

觀察

Callee saved

透過 moxie-none-moxiebox-gcc 產生的組合語言程式碼發現暫存器內的值是由 Callee 函式儲存進堆疊內







fib_tail_recursion:
    dec	$sp, 24
    sto.l	12($fp), $r0
    sto.l	16($fp), $r1
    sto.l	20($fp), $r2
    ...
    ...

instruction set

這一份透過 moxie-none-moxiebox-gcc 產生的組合語言程式碼主要使用到
dec 、 sto.l 、 ldo.l 、 mov 、 add 、 jsra
比較不熟悉的是 jsra 這個可以 jump 到 subroutine 的指令，透過 gdb 可以觀察到 jsra 會儲存 $fp 以及 return address(也就是 $pc 進入函式前所指的下一條指令) 到堆疊，然後把 $fp 和 $sp 指向堆疊頂端，結束時配合 ret 離開 subroutine














































(gdb)i r
$fp            0x129b4	0x129b4
$sp            0x129a8	0x129a8
$r0            0xa	10
...
... 
$pc            0x11a6	0x11a6 <main+20>
$cc            0x0	0

(gdb)disas
Dump of assembler code for function main:
   0x00001192 <+0>:	dec	$sp, 0xc
   ...
=> 0x000011a6 <+20>:	jsra	0x1158 <fib_tail_recursion>
   0x000011ac <+26>:	sto.l	0xfffc($fp), $r2
   ...
   0x000011b2 <+32>:	ret
End of assembler dump.

(gdb)x/3xw $fp
0x129b4:	0x00000000	0x0000103e	0x00000000

(gdb) si
0x00001158 in fib_tail_recursion () 

(gdb)i r
$fp            0x1299c	0x1299c
$sp            0x1299c	0x1299c
$r0            0xa	10
...
...
$pc            0x1158	0x1158 <fib_tail_recursion>
$cc            0x0	0

(gdb)disas
Dump of assembler code for function fib_tail_recursion:
=> 0x00001158 <+0>:	dec	$sp, 0xc
   0x0000115a <+2>:	sto.l	0xc($fp), $r0
   ...
   ...
   0x00001190 <+56>:	ret
End of assembler dump.

(gdb)x/3xw $fp
0x1299c:	0x000129b4	0x000011ac	0x00000000

修改

透過 moxie-none-moxiebox-gcc 產生的組合語言程式碼取消最佳化後有一些顯而易見可以手動優化的地方，主要修改冗餘的暫存器使用以及過大的堆疊空間，Github

Iterative












int __attribute__((optimize("O0"))) fib_iterative (int n)
{
    int pre = -1;
    int result = 1;
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        sum = result + pre;
        pre = result;
        result = sum;
    }
    return result;
}

參考 moxie-none-moxiebox-gcc 產生的組合語言程式碼

$ moxie-none-moxiebox-gcc -S fib_iterative.c
$ cat fib_iterative.s

觀察

過多 stack 存取

透過 moxie-none-moxiebox-gcc 產生的組合語言程式碼取消最佳化後有過多 stack 存取













fib_iterative:
    dec	$sp, 16
    sto.l	12($fp), $r0
    ldi.l	$r0, -1
    sto.l	-4($fp), $r0
    ldi.l	$r0, 1
    sto.l	-8($fp), $r0
    xor	$r0, $r0
    sto.l	-16($fp), $r0
    xor	$r0, $r0
    sto.l	-12($fp), $r0
    ...
    ...

修改

由於 Iterative 版本不像遞迴版本需要大量使用 stack ，暫存器的數量就足夠紀錄變數，因此使用較多的暫存器來取代 stack，Github







fib_iterative:
    ldi.l	$r2, -1
 	ldi.l	$r3, 1
 	xor	$r4, $r4
 	xor	$r1, $r1
    ...
    ...

Recursive






int __attribute__((optimize("O0"))) fib_recursive(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib_recursive(n - 1) + fib_recursive (n - 2);
}