Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Yet another naive Fibonacci example
fib: # @fib
push rbp
push rbx
push rax
mov ebx, edi
inc dword ptr [rip + o]
mov ebp, 1
cmp ebx, 3
jl .LBB0_2
.LBB0_1: # %tailrecurse
lea edi, dword ptr [rbx - 1]
call fib
add ebx, -2
add ebp, eax
inc dword ptr [rip + o]
cmp ebx, 2
jg .LBB0_1
.LBB0_2: # %tailrecurse._crit_edge
mov eax, ebp
add rsp, 8
pop rbx
pop rbp
ret
o:
fib: # @fib
push rbp
push rbx
push rax
mov ebx, edi
inc dword ptr [rip + o]
mov ebp, 1
cmp ebx, 3
jl .LBB0_2
.LBB0_1: # %tailrecurse
lea edi, dword ptr [rbx - 1]
call fib
add ebx, -2
add ebp, eax
inc dword ptr [rip + o]
cmp ebx, 2
jg .LBB0_1
.LBB0_2: # %tailrecurse._crit_edge
mov eax, ebp
add rsp, 8
pop rbx
pop rbp
ret
o:
fib: # @fib
push rbp
push rbx
push rax
mov ebx, edi
inc dword ptr [rip + o]
mov ebp, 1
cmp ebx, 3
jl .LBB0_3
add ebx, 2
mov ebp, 1
.LBB0_2: # =>This Inner Loop Header: Depth=1
lea edi, [rbx - 3]
call fib
add ebp, eax
inc dword ptr [rip + o]
add ebx, -2
cmp ebx, 4
jg .LBB0_2
.LBB0_3:
mov eax, ebp
add rsp, 8
pop rbx
pop rbp
ret
o:
fib: # @fib
push rbp
push rbx
push rax
mov ebx, edi
inc dword ptr [rip + o]
mov ebp, 1
cmp ebx, 3
jl .LBB0_3
add ebx, 2
mov ebp, 1
.LBB0_2: # =>This Inner Loop Header: Depth=1
lea edi, [rbx - 3]
call fib
add ebp, eax
inc dword ptr [rip + o]
add ebx, -2
cmp ebx, 4
jg .LBB0_2
.LBB0_3:
mov eax, ebp
add rsp, 8
pop rbx
pop rbp
ret
o:
int o = 0;
int fib(int a) {
o++;
return a <= 2 ? 1 : fib(a - 1) + fib(a - 2);
}
import java.util.*;
public class Fib {
static int o = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long start = System.currentTimeMillis();
int answer = fib(n);
long end = System.currentTimeMillis();
System.out.printf("%d, run time: %dms, repeat times: %d\n", answer, (end - start), o);
}
public static int fib(int a) {
o++;
return a <= 2 ? 1 : fib(a - 1) + fib(a - 2);
}
}
fib:
add DWORD PTR o[rip], 1
cmp edi, 2
jle .L7
push r12
xor r12d, r12d
push rbp
lea ebp, [rdi-3]
push rbx
and ebp, 1
lea ebx, [rdi-1]
.L3:
mov edi, ebx
sub ebx, 2
call fib
add DWORD PTR o[rip], 1
add r12d, eax
cmp ebx, ebp
jne .L3
lea eax, [r12+1]
pop rbx
pop rbp
pop r12
ret
.L7:
mov eax, 1
ret
o:
fib:
push r15
push r14
push r13
push r12
push rbp
push rbx
sub rsp, 104
mov eax, DWORD PTR o[rip]
mov DWORD PTR [rsp+76], 0
add eax, 1
mov DWORD PTR o[rip], eax
cmp edi, 2
jle .L2
lea edx, [rdi-3]
lea esi, [rdi-2]
and edx, -2
mov DWORD PTR [rsp+72], esi
sub esi, edx
mov DWORD PTR [rsp+88], esi
.L19:
lea ecx, [rdi-1]
add eax, 1
mov edx, 1
cmp ecx, 2
jle .L3
mov esi, DWORD PTR [rsp+72]
and edi, 1
mov DWORD PTR [rsp+80], 0
mov DWORD PTR [rsp+92], edi
mov DWORD PTR [rsp+64], esi
.L18:
mov edi, DWORD PTR [rsp+64]
add eax, 1
mov edx, 1
cmp edi, 2
jle .L4
lea edx, [rdi-3]
lea ecx, [rdi-1]
mov DWORD PTR [rsp+68], 0
and edx, 1
mov DWORD PTR [rsp+52], ecx
mov DWORD PTR [rsp+84], edx
.L17:
mov ecx, DWORD PTR [rsp+52]
add eax, 1
mov edx, 1
cmp ecx, 2
jle .L5
lea edx, [rcx-3]
lea edi, [rcx-1]
mov DWORD PTR [rsp+56], 0
and edx, 1
mov DWORD PTR [rsp+40], edi
mov DWORD PTR [rsp+60], edx
.L16:
mov edi, DWORD PTR [rsp+40]
add eax, 1
mov edx, 1
cmp edi, 2
jle .L6
lea edx, [rdi-3]
lea ecx, [rdi-1]
mov DWORD PTR [rsp+44], 0
and edx, 1
mov DWORD PTR [rsp+28], ecx
mov DWORD PTR [rsp+48], edx
.L15:
mov ecx, DWORD PTR [rsp+28]
add eax, 1
mov edx, 1
cmp ecx, 2
jle .L7
lea edx, [rcx-3]
lea edi, [rcx-1]
mov DWORD PTR [rsp+32], 0
and edx, 1
mov DWORD PTR [rsp+16], edi
mov DWORD PTR [rsp+36], edx
.L14:
mov esi, DWORD PTR [rsp+16]
add eax, 1
mov edx, 1
cmp esi, 2
jle .L8
mov edx, esi
mov DWORD PTR [rsp+20], 0
lea r14d, [rsi-1]
sub edx, 3
and edx, 1
mov DWORD PTR [rsp+24], edx
.L13:
add eax, 1
mov r13d, 1
cmp r14d, 2
jle .L9
lea r15d, [r14-3]
lea ebp, [r14-1]
xor r13d, r13d
and r15d, 1
mov DWORD PTR [rsp+12], r15d
.L12:
add eax, 1
mov ebx, 1
mov DWORD PTR o[rip], eax
cmp ebp, 2
jle .L10
lea r12d, [rbp-3]
lea r15d, [rbp-1]
xor ebx, ebx
and r12d, 1
.L11:
mov edi, r15d
sub r15d, 2
call fib
add ebx, eax
mov eax, DWORD PTR o[rip]
add eax, 1
mov DWORD PTR o[rip], eax
cmp r12d, r15d
jne .L11
add ebx, 1
.L10:
add r13d, ebx
add eax, 1
sub ebp, 2
cmp DWORD PTR [rsp+12], ebp
jne .L12
add r13d, 1
.L9:
add DWORD PTR [rsp+20], r13d
add eax, 1
sub r14d, 2
cmp DWORD PTR [rsp+24], r14d
jne .L13
mov edx, DWORD PTR [rsp+20]
add edx, 1
.L8:
sub DWORD PTR [rsp+16], 2
add eax, 1
mov ecx, DWORD PTR [rsp+16]
add DWORD PTR [rsp+32], edx
cmp DWORD PTR [rsp+36], ecx
jne .L14
mov edx, DWORD PTR [rsp+32]
add edx, 1
.L7:
sub DWORD PTR [rsp+28], 2
add eax, 1
mov esi, DWORD PTR [rsp+28]
add DWORD PTR [rsp+44], edx
cmp DWORD PTR [rsp+48], esi
jne .L15
mov edx, DWORD PTR [rsp+44]
add edx, 1
.L6:
sub DWORD PTR [rsp+40], 2
add eax, 1
mov esi, DWORD PTR [rsp+40]
add DWORD PTR [rsp+56], edx
cmp DWORD PTR [rsp+60], esi
jne .L16
mov edx, DWORD PTR [rsp+56]
add edx, 1
.L5:
sub DWORD PTR [rsp+52], 2
add eax, 1
mov esi, DWORD PTR [rsp+52]
add DWORD PTR [rsp+68], edx
cmp DWORD PTR [rsp+84], esi
jne .L17
mov edx, DWORD PTR [rsp+68]
add edx, 1
.L4:
add DWORD PTR [rsp+80], edx
add eax, 1
sub DWORD PTR [rsp+64], 2
mov edx, DWORD PTR [rsp+64]
cmp DWORD PTR [rsp+92], edx
jne .L18
mov edx, DWORD PTR [rsp+80]
add edx, 1
.L3:
mov ecx, DWORD PTR [rsp+72]
mov esi, DWORD PTR [rsp+88]
add eax, 1
add DWORD PTR [rsp+76], edx
mov edi, ecx
mov DWORD PTR o[rip], eax
cmp ecx, esi
je .L2
sub ecx, 2
mov DWORD PTR [rsp+72], ecx
jmp .L19
.L2:
mov eax, DWORD PTR [rsp+76]
add rsp, 104
pop rbx
pop rbp
add eax, 1
pop r12
pop r13
pop r14
pop r15
ret
o:
fib PROC
push rdi
sub rsp, 32 ; 00000020H
inc DWORD PTR ?o@@3HA
mov edi, ecx
cmp ecx, 2
jg SHORT $LN3@fib
mov eax, 1
add rsp, 32 ; 00000020H
pop rdi
ret 0
$LN3@fib:
add ecx, -2
mov QWORD PTR [rsp+48], rbx
call ?fib@@YAHH@Z
lea ecx, DWORD PTR [rdi-1]
mov ebx, eax
call ?fib@@YAHH@Z
add eax, ebx
mov rbx, QWORD PTR [rsp+48]
add rsp, 32 ; 00000020H
pop rdi
ret 0
fib ENDP
# {method} 'fib' '(I)I' in 'Fib'
# parm0: rsi = int
# [sp+0x30] (sp of caller)
0x00000001066b2ac0: mov %eax,-0x14000(%rsp)
0x00000001066b2ac7: push %rbp
0x00000001066b2ac8: sub $0x20,%rsp ;*synchronization entry
; - Fib::fib@-1 (line 16)
0x00000001066b2acc: mov %esi,(%rsp)
0x00000001066b2acf: movabs $0x7aaadc910,%r10 ; {oop(a 'java/lang/Class' = 'Fib')}
0x00000001066b2ad9: mov 0x70(%r10),%r8d ;*getstatic o
; - Fib::fib@0 (line 16)
0x00000001066b2add: mov %r8d,%r11d
0x00000001066b2ae0: inc %r11d
0x00000001066b2ae3: mov %r11d,0x70(%r10) ;*putstatic o
; - Fib::fib@5 (line 16)
0x00000001066b2ae7: cmp $0x2,%esi
0x00000001066b2aea: jle 0x00000001066b2b93 ;*if_icmpgt
; - Fib::fib@10 (line 17)
0x00000001066b2af0: mov %esi,%ebp
0x00000001066b2af2: dec %ebp ;*isub
; - Fib::fib@19 (line 17)
0x00000001066b2af4: add $0x2,%r8d ;*iadd
; - Fib::fib@4 (line 16)
; - Fib::fib@20 (line 17)
0x00000001066b2af8: mov %r8d,0x70(%r10) ;*putstatic o
; - Fib::fib@5 (line 16)
; - Fib::fib@20 (line 17)
0x00000001066b2afc: mov %esi,%r10d
0x00000001066b2aff: add $0xfffffffffffffffe,%r10d
;*isub
; - Fib::fib@19 (line 17)
; - Fib::fib@20 (line 17)
0x00000001066b2b03: add $0xfffffffffffffffd,%esi ;*isub
; - Fib::fib@25 (line 17)
; - Fib::fib@20 (line 17)
0x00000001066b2b06: cmp $0x2,%ebp
0x00000001066b2b09: jle 0x00000001066b2b4b
0x00000001066b2b0b: mov %esi,0x8(%rsp)
0x00000001066b2b0f: mov %r10d,0x4(%rsp) ;*if_icmpgt
; - Fib::fib@10 (line 17)
; - Fib::fib@20 (line 17)
0x00000001066b2b14: mov %r10d,%esi
0x00000001066b2b17: callq 0x000000010668af60 ; OopMap{off=92}
;*invokestatic fib
; - Fib::fib@20 (line 17)
; - Fib::fib@20 (line 17)
; {static_call}
0x00000001066b2b1c: mov %eax,0xc(%rsp)
0x00000001066b2b20: mov 0x8(%rsp),%esi
0x00000001066b2b24: data32 xchg %ax,%ax
0x00000001066b2b27: callq 0x000000010668af60 ; OopMap{off=108}
;*invokestatic fib
; - Fib::fib@26 (line 17)
; - Fib::fib@20 (line 17)
; {static_call}
0x00000001066b2b2c: movabs $0x7aaadc910,%r10 ; {oop(a 'java/lang/Class' = 'Fib')}
0x00000001066b2b36: mov 0x70(%r10),%r8d ;*getstatic o
; - Fib::fib@0 (line 16)
; - Fib::fib@26 (line 17)
0x00000001066b2b3a: mov %eax,%ebp
0x00000001066b2b3c: add 0xc(%rsp),%ebp ;*iadd
; - Fib::fib@29 (line 17)
; - Fib::fib@20 (line 17)
0x00000001066b2b40: mov 0x4(%rsp),%r10d
0x00000001066b2b45: mov 0x8(%rsp),%esi
0x00000001066b2b49: jmp 0x00000001066b2b50
0x00000001066b2b4b: mov $0x1,%ebp ;*ireturn
; - Fib::fib@30 (line 17)
; - Fib::fib@20 (line 17)
0x00000001066b2b50: inc %r8d
0x00000001066b2b53: movabs $0x7aaadc910,%r11 ; {oop(a 'java/lang/Class' = 'Fib')}
0x00000001066b2b5d: mov %r8d,0x70(%r11) ;*putstatic o
; - Fib::fib@5 (line 16)
; - Fib::fib@26 (line 17)
0x00000001066b2b61: cmp $0x2,%r10d
0x00000001066b2b65: jle 0x00000001066b2b8a ;*if_icmpgt
; - Fib::fib@10 (line 17)
; - Fib::fib@26 (line 17)
0x00000001066b2b67: mov %r10d,0x4(%rsp)
0x00000001066b2b6c: data32 xchg %ax,%ax
0x00000001066b2b6f: callq 0x000000010668af60 ; OopMap{off=180}
;*invokestatic fib
; - Fib::fib@20 (line 17)
; - Fib::fib@26 (line 17)
; {static_call}
0x00000001066b2b74: mov %eax,0x4(%rsp)
0x00000001066b2b78: mov (%rsp),%esi
0x00000001066b2b7b: add $0xfffffffffffffffc,%esi ;*isub
; - Fib::fib@25 (line 17)
; - Fib::fib@26 (line 17)
0x00000001066b2b7e: nop
0x00000001066b2b7f: callq 0x000000010668af60 ; OopMap{off=196}
;*invokestatic fib
; - Fib::fib@26 (line 17)
; - Fib::fib@26 (line 17)
; {static_call}
0x00000001066b2b84: add 0x4(%rsp),%eax ;*iadd
; - Fib::fib@29 (line 17)
; - Fib::fib@26 (line 17)
0x00000001066b2b88: jmp 0x00000001066b2b8f
0x00000001066b2b8a: mov $0x1,%eax ;*ireturn
; - Fib::fib@30 (line 17)
; - Fib::fib@26 (line 17)
0x00000001066b2b8f: add %ebp,%eax ;*iadd
; - Fib::fib@29 (line 17)
0x00000001066b2b91: jmp 0x00000001066b2b98
0x00000001066b2b93: mov $0x1,%eax ;*if_icmpgt
; - Fib::fib@10 (line 17)
; - Fib::fib@26 (line 17)
0x00000001066b2b98: add $0x20,%rsp
0x00000001066b2b9c: pop %rbp
0x00000001066b2b9d: test %eax,-0x130dba3(%rip) # 0x00000001053a5000
; {poll_return}
0x00000001066b2ba3: retq ;*invokestatic fib
; - Fib::fib@20 (line 17)
; - Fib::fib@20 (line 17)
0x00000001066b2ba4: mov %rax,%rsi
0x00000001066b2ba7: jmp 0x00000001066b2bb6 ;*invokestatic fib
; - Fib::fib@20 (line 17)
; - Fib::fib@26 (line 17)
0x00000001066b2ba9: mov %rax,%rsi
0x00000001066b2bac: jmp 0x00000001066b2bb6 ;*invokestatic fib
; - Fib::fib@26 (line 17)
; - Fib::fib@20 (line 17)
0x00000001066b2bae: mov %rax,%rsi
0x00000001066b2bb1: jmp 0x00000001066b2bb6 ;*invokestatic fib
; - Fib::fib@26 (line 17)
; - Fib::fib@26 (line 17)
0x00000001066b2bb3: mov %rax,%rsi ;*invokestatic fib
; - Fib::fib@26 (line 17)
; - Fib::fib@20 (line 17)
0x00000001066b2bb6: add $0x20,%rsp
0x00000001066b2bba: pop %rbp
0x00000001066b2bbb: jmpq 0x00000001066b5660 ; {runtime_call}
[Stub Code]
0x00000001066b2bc0: movabs $0x0,%rbx ; {no_reloc}
0x00000001066b2bca: jmpq 0x00000001066b2bca ; {runtime_call}
0x00000001066b2bcf: movabs $0x0,%rbx ; {static_stub}
0x00000001066b2bd9: jmpq 0x00000001066b2bd9 ; {runtime_call}
0x00000001066b2bde: movabs $0x0,%rbx ; {static_stub}
0x00000001066b2be8: jmpq 0x00000001066b2be8 ; {runtime_call}
0x00000001066b2bed: movabs $0x0,%rbx ; {static_stub}
0x00000001066b2bf7: jmpq 0x00000001066b2bf7 ; {runtime_call}
[Exception Handler]
0x00000001066b2bfc: jmpq 0x00000001066b26e0 ; {runtime_call}
[Deopt Handler Code]
0x00000001066b2c01: callq 0x00000001066b2c06
0x00000001066b2c06: subq $0x5,(%rsp)
0x00000001066b2c0b: jmpq 0x000000010668bb00 ; {runtime_call}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment