Factorial program in x64 assembly always returning 1?

Question

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

Answer 1

Here are the bugs I see:

1. 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.

2. cmp %rax, %rbx ; jle if is backwards. It will jump to if when rbx <= rax but you want the other way around, so you probably want cmp %rbx, %rax.

   The Jcc mnemonics are designed to be intuitive with Intel syntax, where you would write cmp rax, rbx ; jle if to jump when rax <= rbx. AT&T reverses the operands of cmp like every other instruction, which unfortunately means the conditional jump mnemonics no longer match.

3. You forgot to load the argument into %rdi before calling fact recursively. You probably want movq 0(%rsp), %rdi if you are going to stick with your scheme of keeping the variable on the stack.

4. Off-by-one error. You subtract 1 from your variable before calling fact recursively, so it is the equivalent of return (x <= 1) ? 1 :(x-1)*fact(x-1);. This mean your program will compute the factorial of 4 instead of 5.

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 in main before calling printf. A simple way is to push and pop some register at the beginning and end of main.

   You don't maintain stack alignment in fact either, but in this case it is harmless since fact doesn't call any function except itself. However if it did, e.g. if you added a printf for debugging, you would have problems.

6. The fact function clobbers %rbx which is specified as call-preserved in the ABI. This may cause a crash or other misbehavior when main returns.