<div dir="ltr"><div><div><div>In the Zig frontend, we know at compile-time the entire call graph. This means we know stack size for all functions and therefore the upper bound stack usage.<br><br></div>Recursive calls can have a runtime-decided stack usage, and therefore I am adding a frontend feature that will heap-allocate memory to use for some function calls.<br><br></div>The idea is that recursion adds cycles to the call graph, and we know at compile-time for a given cycle which of the function calls enters the cycle. Therefore, we want to heap-allocate enough memory for the stack of 1 cycle, only in the function call that enters the cycle. So, that function call must set a new stack pointer and then restore it after returning.<br><br></div><div>What is the best way to represent such a function call in LLVM IR?<br><br></div><div>Here's a way that will work, but keep reading for why this is not ideal:<br><br><br>; example address of top of new stack to use - assume the caller has<br>; figured out how much to allocate and has this address ready<br>@new_sp = internal unnamed_addr global i64 3735928559, align 8<br><br>; Function Attrs: nobuiltin nounwind<br>define void @entry() #2 {<br>Entry:<br>  %0 = call i64 asm "", "={sp}"()<br>  %1 = load i64, i64* @new_sp, align 8<br>  call void @cycleEntry(i64 %0, i64 %1)<br>  ret void<br>}<br><br>; Function Attrs: nobuiltin nounwind<br>define internal void @cycleEntry(i64, i64) unnamed_addr #2 {<br>Entry:<br>  call void asm sideeffect "   # set the new base pointer for this function\0A   movq %rsi, %rbp\0A   # store stack pointer of this function for later\0A   movq %rsp, (%rsi)\0A   # save this new stack pointer for use later\0A   movq %rsp, r11\0A   # compute the new stack pointer for this function\0A   subq %rdi, %rsi\0A   addq %rsp, %rsi  \0A   movq %rsi, %rsp\0A   # copy args that were passed via the old stack to the new stack\0A   # %r11 marches towards %rdi which is the source addresses\0A1:\0A   cmpq %rdi, %r11\0A   je 2\0A   movq (%r11), %r12\0A   movq %r12, (%rsi)\0A   addq $$0x8, %rsi\0A   addq $$0x8, %r11\0A   jmp 1\0A2:", "~{r11},~{r12}"()<br><br><br>  ; function body goes here<br><br><br>  call void asm sideeffect " movq (%rbp), %rsp", ""()<br>  ret void<br>}<br><br></div><div><br></div><div>To make the assembly more readable, I'll include the source that generated this:<br><br><br>var new_sp: usize = 0xdeadbeef;<br><br>export fn entry() void {<br>    const sp = asm ("" : [ret] "={sp}" (-> usize));<br>    cycleEntry(sp, new_sp);<br>}<br><br>extern fn cycleEntry(<br>    old_sp: usize,     // %rdi<br>    new_sp_arg: usize, // %rsi<br>) void {<br>    asm volatile (<br>        \\   # set the new base pointer for this function<br>        \\   movq %%rsi, %%rbp<br><br>        \\   # store stack pointer of this function for later<br>        \\   movq %%rsp, (%%rsi)<br><br>        \\   # save this new stack pointer for use later<br>        \\   movq %%rsp, r11<br><br>        \\   # compute the new stack pointer for this function<br>        \\   subq %%rdi, %%rsi<br>        \\   addq %%rsp, %%rsi  <br>        \\   movq %%rsi, %%rsp<br><br>        \\   # copy args that were passed via the old stack to the new stack<br>        \\   # %%r11 marches towards %%rdi which is the source addresses<br>        \\1:<br>        \\   cmpq %%rdi, %%r11<br>        \\   je 2<br>        \\   movq (%%r11), %%r12<br>        \\   movq %%r12, (%%rsi)<br>        \\   addq $0x8, %%rsi<br>        \\   addq $0x8, %%r11<br>        \\   jmp 1<br>        \\2:<br>    ::: "r11", "r12");<br><br>    // function body<br><br>    asm volatile (<br>        \\ movq (%%rbp), %%rsp<br>    );<br>}<br><br><br></div><div>I haven't tested this yet, but already there are a lot of problems:<br><br>* It is not portable. This is an x86_64 implementation and it depends on %rbp, because we're not sure how many bytes LLVM will subtract from %rsp in the epilogue, and we must include the prologue/epilogue in order to know how much to offset %rsp in the new stack.<br><br>* The side-effect assembly is hostile to the optimizer. This is unfortunate because it is not fundamentally necessary. All in all this is just a function call where the stack pointer is provided by the caller. If LLVM understood this as a calling convention we could make this code friendly to the optimizer.<br><br>* LLVM could generate a more efficient function call. This implementation copies the stack frame of cycleEntry needlessly. We don't know which bytes are allocated for parameters and which bytes are allocated for the call frame. But LLVM would know this information if it was a calling convention.<br><br><br></div><div>So my questions for the mailing list are:<br><br> 1. Is there a way to accomplish this with existing LLVM API?<br></div><div> 2. If not, what would be the best way to support this use case, and would such modifications to LLVM be welcome?</div><div><br></div><div>Regards,<br></div><div>Andrew<br></div><div><br></div><div><br></div></div>