<p>A compiler I'm writing generates the following x86-64 assembly (AT&amp;T syntax) for a recursive factorial function. I convert the assembly into an ELF executable using <code>gcc</code>. But, when I execute it, the output is always some garbage number and not the desired output <code>120</code>.</p>
<p>Source Code:</p>
<pre class="lang-rust prettyprint-override"><code>fn factorial(num: i32) -&gt; i32 {
    if num == 0 {
        return 1;
    } else {
        return num * factorial(num - 1);
    }
}

fn main() {
    println(factorial(5));
}
</code></pre>
<p>Generated Assembly:</p>
<pre><code>.globl factorial, main
.format_number:
        .string &quot;%d\n&quot;
factorial:
        pushq %rbp
        movq  %rsp, %rbp
        subq  $4, %rsp           # allocating 4 bytes for parameter num
        movl  %edi, -4(%rbp)
        pushq %rbx
        pushq %r12
        pushq %r13
        pushq %r14
        pushq %r15
        movl  -4(%rbp), %ebx
        movl  $0, %r10d
        cmpl  %r10d, %ebx
        jne   .L0
        movl  $1, %ebx
        movl  %ebx, %eax
        jmp   .factorial_epilogue
        jmp   .L1
.L0:
        movl  -4(%rbp), %ebx
        andq  $-16, %rsp
        movl  -4(%rbp), %r10d
        movl  $1, %r11d
        subl  %r11d, %r10d
        movl  %r10d, %edi
        pushq %r10
        pushq %r11
        call  factorial
        popq  %r11
        popq  %r10
        movl  %eax, %r11d
        imull %ebx, %r11d
        movl  %r11d, %eax
        jmp   .factorial_epilogue
.L1:
.factorial_epilogue:
        popq  %r15
        popq  %r14
        popq  %r13
        popq  %r12
        popq  %rbx
        movq  %rbp, %rsp
        popq  %rbp
        ret
main:
        pushq %rbp
        movq  %rsp, %rbp
        subq  $0, %rsp
        pushq %rbx
        pushq %r12
        pushq %r13
        pushq %r14
        pushq %r15
        andq  $-16, %rsp
        movl  $5, %ebx
        movl  %ebx, %edi
        pushq %r10
        pushq %r11
        call  factorial
        popq  %r11
        popq  %r10
        movl  %eax, %r11d
        andq  $-16, %rsp
        movl  %r11d, %esi
        leaq  .format_number(%rip), %rax
        movq  %rax, %rdi
        xor   %eax, %eax
        call  printf@PLT
.main_epilogue:
        popq  %r15
        popq  %r14
        popq  %r13
        popq  %r12
        popq  %rbx
        movq  %rbp, %rsp
        popq  %rbp
        ret
.data
</code></pre>
<p>I thought this was an issue with stack alignment during function calls and fixed it with <code>andq  $-16, %rsp</code> before every function call to align the stack pointer to a 16 byte boundary. Now, <code>memcheck</code> does not detect any errors but the output is still some garbage number. The same assembly was working fine when all the numbers were 8 byte values but I don't understand why it doesn't work when numbers are 4 byte values. Anyone know how to find what's wrong in the generated assembly?</p>
<p>Edit: Currently, the code generator attempts to align the stack by doing an <code>andq</code> before every function call. Then, the function prologue pushes 5 * 8 bytes (callee saved registers) and also allocates the exact amount of space required for local variables. For example, it allocates 40 + 4 bytes if the function has an <code>i32</code> parameter only.</p>

<memory-management><recursion><assembly><code-generation>
X86-64 Assembly for Recursive Functions
CC BY-SA 4.0
2023-07-19T04:04:33.670Z
[Whether or not this question is on-topic is currently being discussed on meta here.](https://langdev.meta.stackexchange.com/q/546/861)
Alexis King
CC BY-SA 4.0
2023-07-19T15:19:02.210Z
I think this question as it stands is off topic. You could make it on topic by talking about how the assembly code is generated. Otherwise it just reads as debug my fibonacci program written in assembly.
Bruce Adams
CC BY-SA 4.0
2023-07-19T18:33:59.460Z
Added some details about code generation to make it more on topic.
Veera Sivarajan
<p>Your way of aligning the stack messes with the restoration of saved registers. You should keep track of stack alignment in the compiler, and manage it with <code>sub</code> and <code>add</code> before and after every <code>call</code>. Currently, you don't reverse your change to <code>rsp</code>, nor have a simple way to</p>

CC BY-SA 4.0
2023-07-19T06:25:48.367Z
2023-07-19T06:25:48.367Z
abel1502
# X86-64 Assembly for Recursive Functions
Posted by: username_0 on 2023-07-19
A compiler I'm writing generates the following x86-64 assembly (AT&T syntax) for a recursive factorial function. I convert the assembly into an ELF executable using gcc. But, when I execute it, the output is always some garbage number and not the desired output 120.
Source Code:
fn factorial(num: i32) -> i32 {
    if num == 0 {
        return 1;
    } else {
        return num * factorial(num - 1);
    }
}

fn main() {
    println(factorial(5));
}

Generated Assembly:
.globl factorial, main
.format_number:
        .string "%d\n"
factorial:
        pushq %rbp
        movq  %rsp, %rbp
        subq  $4, %rsp           # allocating 4 bytes for parameter num
        movl  %edi, -4(%rbp)
        pushq %rbx
        pushq %r12
        pushq %r13
        pushq %r14
        pushq %r15
        movl  -4(%rbp), %ebx
        movl  $0, %r10d
        cmpl  %r10d, %ebx
        jne   .L0
        movl  $1, %ebx
        movl  %ebx, %eax
        jmp   .factorial_epilogue
        jmp   .L1
.L0:
        movl  -4(%rbp), %ebx
        andq  $-16, %rsp
        movl  -4(%rbp), %r10d
        movl  $1, %r11d
        subl  %r11d, %r10d
        movl  %r10d, %edi
        pushq %r10
        pushq %r11
        call  factorial
        popq  %r11
        popq  %r10
        movl  %eax, %r11d
        imull %ebx, %r11d
        movl  %r11d, %eax
        jmp   .factorial_epilogue
.L1:
.factorial_epilogue:
        popq  %r15
        popq  %r14
        popq  %r13
        popq  %r12
        popq  %rbx
        movq  %rbp, %rsp
        popq  %rbp
        ret
main:
        pushq %rbp
        movq  %rsp, %rbp
        subq  $0, %rsp
        pushq %rbx
        pushq %r12
        pushq %r13
        pushq %r14
        pushq %r15
        andq  $-16, %rsp
        movl  $5, %ebx
        movl  %ebx, %edi
        pushq %r10
        pushq %r11
        call  factorial
        popq  %r11
        popq  %r10
        movl  %eax, %r11d
        andq  $-16, %rsp
        movl  %r11d, %esi
        leaq  .format_number(%rip), %rax
        movq  %rax, %rdi
        xor   %eax, %eax
        call  printf@PLT
.main_epilogue:
        popq  %r15
        popq  %r14
        popq  %r13
        popq  %r12
        popq  %rbx
        movq  %rbp, %rsp
        popq  %rbp
        ret
.data

I thought this was an issue with stack alignment during function calls and fixed it with andq  $-16, %rsp before every function call to align the stack pointer to a 16 byte boundary. Now, memcheck does not detect any errors but the output is still some garbage number. The same assembly was working fine when all the numbers were 8 byte values but I don't understand why it doesn't work when numbers are 4 byte values. Anyone know how to find what's wrong in the generated assembly?
Edit: Currently, the code generator attempts to align the stack by doing an andq before every function call. Then, the function prologue pushes 5 * 8 bytes (callee saved registers) and also allocates the exact amount of space required for local variables. For example, it allocates 40 + 4 bytes if the function has an i32 parameter only.
**Tags:** memory-management recursion assembly code-generation
> **Comments:**
> **username_1**: [Whether or not this question is on-topic is currently being discussed on meta here.](https://langdev.meta.stackexchange.com/q/546/861)  
> **username_2**: I think this question as it stands is off topic. You could make it on topic by talking about how the assembly code is generated. Otherwise it just reads as debug my fibonacci program written in assembly.  
> **username_0**: Added some details about code generation to make it more on topic.  
---
## 1 answers
### Answer by username_3 on 2023-07-19. Score: 4 | Accepted answer
Your way of aligning the stack messes with the restoration of saved registers. You should keep track of stack alignment in the compiler, and manage it with `sub` and `add` before and after every `call`. Currently, you don't reverse your change to `rsp`, nor have a simple way to
---
