x86でFibonacci

最近, Cコンパイラの自作を始めました. そこでサポートしてるアセンブリがx86-64なので, アセンブリを理解する必要がりました. 折角なので, アセンブリを直接書いてfibonacciを作ってみようと思います.

雑設計

一応関数を分離して記述します.

.intel_syntax noprefix
.global main, fib

main:
    ...

fib:
    ...

実装

愚直に実装します. 条件分岐と再帰を書きます. ediレジスタの値を計算します. 引数をstackに詰んで引っ張り, cmpの演算結果に応じてL1, L2にjumpさせればOKです.

.intel_syntax noprefix
.global main, fib

main:
    push rbp
    mov rbp, rsp
    mov edi, 10 # index
    call fib
    pop rbp
    ret

fib:
    push rbp
    mov rbp, rsp
    push rbx
    sub rsp, 24
    mov DWORD PTR [rbp-20], edi
    cmp DWORD PTR [rbp-20], 1
    jg .L1
    mov eax, 1
    jmp .L2

.L1:
    mov eax, [rbp-20]
    sub eax, 1
    mov edi, eax
    call fib
    mov ebx, eax
    mov eax, DWORD PTR [rbp-20]
    sub eax, 2
    mov edi, eax
    call fib
    add eax, ebx

.L2:
    add rsp, 24
    pop rbx
    pop rbp
    ret

書けました.

index	0	1	2	3	4	5	6	7	8	9	10	...
value	1	1	2	3	5	8	13	21	34	55	89	...

0-indexedで考えると, 実行結果が89になっていれば良いですね. では, Linux環境*1で, gccを使ってアセンブリをコンパイルして動かしてみます.

無事に出力されました 🎉

*1:Docker, VM上で可