Search code examples
functionassemblymips

What exactly is the difference between leaf functions and non leaf functions?


As far as I know, the main difference between leaf functions and non-leaf functions is that leaf functions do not call another function, and non-leaf functions call for other functions. Therefore, leaf functions do not require things like

begin
push  $ra

~ ( some random bits of code) ~

pop   $ra
end

But what exactly does it mean to 'call for a function'? It seems like I only know the difference between those two as a definition, and not really understand the whole thing.


Solution

  • A leaf function doesn't use jal, or anything else that would run any code you can't see when writing that function. That's what it means to not call any other functions.

    In the tree of function calls your program could or does make (more generally a call graph), it's a leaf node. It has callers but no callees. If you're looking at C source vs. asm, inlining small functions can make non-leaf C functions into asm leaf functions.

    Thus it doesn't have to save / restore $ra on the stack, it can just leave its own return address in that register and return to its own caller with jr $ra, without having used $ra for any other return address in the meantime. There will never be another function's stack frame below it on the callstack.

    A large function might want to use a lot of registers, so it might actually save/restore $ra, and maybe some of $s0..$s7 just to use them as scratch space. But MIPS has lots of registers, so usually leaf functions can get their work done just fine using only $t0..$t9, $v0..1, $a0..3, and $at without needing to touch stack space. Except maybe for local arrays if it needs more scratch space than registers, or space that can be indexed.


    A system call doesn't really count as a call if you do it directly with syscall so a leaf function can make a system call. (Most real-world systems are like MARS/SPIM in the fact that the kernel saves all registers around syscall, except for the return value.)

    But if you call a wrapper function like jal read defined in libc (on a Unix system for example, not in MARS/SPIM) then that's a real function and you have to assume it follows the standard calling convention, like leaving garbage in all of the $t0..9 and $a / $v registers, as well as $ra.

    The only exception might be some private helper functions where this function knows which registers they do/don't use, so you could look at a jal helper as just part of the implementation of this leaf function. In that case you would still have to manage $ra, maybe saving it in $t9 or something.


    Related: MIPS: relevant use for a stack pointer ($sp) and the stack for an example of a non-leaf function using stack space to save stuff across two calls to unknown functions.

    BTW, MIPS doesn't have push and pop instructions. You normally addiu $sp, $sp, -16 or however much stack space you need, and use sw to store into the space reserved. You wouldn't separately sub or add between every load and store.

    And end isn't a real thing in MIPS assembly; you need to run an instruction that jumps back to your caller such as jr $ra. Or tailcall some other function, like j foo or b foo, to effectively call it with the return address being the one your caller originally passed.