I'm trying to write a recursive factorial program in x64 assembly. For some reason, no matter what I do, I always get a result of 1. I realize that I don't necessarily need to declare a local variable, but I do it because I'm writing a compiler (for simplicity).
.section .data
outfmt: .asciz "%d\n"
.section .text
.extern printf
.global main
fact:
addq $16, %rsp
movq %rdi, 0(%rsp) # Convert parameter to local var.
movq 0(%rsp), %rax # Move rdi into rax.
movq $1, %rbx # Move 0 into rbx.
cmp %rax, %rbx # If rdi <= 1, return 1.
jle if
jmp else
else:
subq $1, 0(%rsp) # n = n - 1
call fact # Call fact
imulq 0(%rsp), %rax # Multiply n with fact n - 1
jmp factend
if:
movq $1, %rax # Return 1
jmp factend
factend:
subq $16, %rsp
ret
main:
movq $5, %rdi
call fact
movq %rax, %rsi
leaq outfmt, %rdi
movq $0, %rax
call printf
ret
CodePudding user response:
Here are the bugs I see:
You are manipulating the stack backwards. The stack on x86 grows downwards, so you should subtract from
%rsp
on entry to a function, and add when you return.cmp %rax, %rbx ; jle if
is backwards. It will jump toif
whenrbx <= rax
but you want the other way around, so you probably wantcmp %rbx, %rax
.The
Jcc
mnemonics are designed to be intuitive with Intel syntax, where you would writecmp rax, rbx ; jle if
to jump whenrax <= rbx
. AT&T reverses the operands ofcmp
like every other instruction, which unfortunately means the conditional jump mnemonics no longer match.You forgot to load the argument into
%rdi
before callingfact
recursively. You probably wantmovq 0(%rsp), %rdi
if you are going to stick with your scheme of keeping the variable on the stack.Off-by-one error. You subtract 1 from your variable before calling
fact
recursively, so it is the equivalent ofreturn (x <= 1) ? 1 :(x-1)*fact(x-1);
. This mean your program will compute the factorial of 4 instead of 5.You are not maintaining 16-byte stack alignment as required by the SysV ABI (which I assume you are following): Why does the x86-64 / AMD64 System V ABI mandate a 16 byte stack alignment? In particular, you call the library function
printf
with the stack misaligned, which can cause it to crash. You need to adjust the stack pointer down by 8 bytes inmain
before callingprintf
. A simple way is to push and pop some register at the beginning and end ofmain
.You don't maintain stack alignment in
fact
either, but in this case it is harmless sincefact
doesn't call any function except itself. However if it did, e.g. if you added aprintf
for debugging, you would have problems.The
fact
function clobbers%rbx
which is specified as call-preserved in the ABI. This may cause a crash or other misbehavior whenmain
returns.