CODEWITHSUNDEEP
recursionassemblyx86
iSuckAtAssembly
iSuckAtAssembly

Reputation: 11

Need help understanding recursion in x86 assembly

So i have this thing for college where I need to make a simple recursion. Seems fine I can do that in 20 mins in C. Howeeever they didn't teach us at the course about recursive functions in assembly sooo i looked it up on google. I found only this - https://scottc130.medium.com/recusive-functions-in-x86-assembly-5ba412bc7957 - and I have a few questions:

I think I might have understood slightly but I'd rather have it dumbed down a bit.


factorial:
    pushl %ebp
    movl %esp, %ebp

    movl 8(%ebp), %eax
    cmpl $1, %eax
    je end_factorial

    decl %eax
    pushl %eax
    call factorial

    movl 8(%ebp), %ebx
    imul %ebx, %eax

end_factorial:
    movl %ebp, %esp
    popl %ebp
    ret

Upvotes: 0

Views: 2550

Answers (2)

Erik Eidt
Erik Eidt

Reputation: 26646

Why is ebp being pushed here?

The programmer/compiler is using %ebp as a frame pointer.  Since %ebp is a call-preserved register, in order to use it, its original value must be preserved first, so that this original value can be restored to that register before returning.

The frame pointer is used in a displacement addressing mode to access parameters and local variables.  It is not always necessary to use a frame pointer in 32-bit x86 code because the stack pointer can be used as the base register instead (with an adjusted displacement value), yet still common practice.  Historically, the 16-bit 8086 did not support the stack pointer as a base register in displacement addressing, so a frame pointer was required for that.  See here for more discussion, especially on how a frame pointer was needed on the 16-bit 8086.

ebp is popped once in end_factorial and pushed as many times as factorial is called, what happens to the rest of those pushes?

The processor does not see labels — they are removed by the assembler during the production of machine code.

The processor only sees machine code instructions, and thus, only machine code instructions influence the flow of control.

Every machine code instruction informs the processor what instruction to run next.  Many instructions simply tell the processor to proceed with the next sequential instruction — and imull does that.  The je instruction says to either jump to the label (condition true) or else continue sequentially (condition false).

So, when you're interpreting the flow of control in assembly language, mind that labels do nothing with/for the processor — labels only inform the assembler of numbers to use when encoding real machine code instructions that use a label and they are otherwise removed and not seen by the processor.

end_factorial is a part of factorial, and will execute by either the change in flow of control caused by the je end_factorial, or by the sequential flow of control from after the imull, depending on conditional logic (whether at the base condition or not).

In the explanation part, what is that eip and where is it even pushed into the stack?

%eip is the instruction pointer, also known as the program counter in other architectures.  It is the register that sequences the instructions.  The call instruction pushes the return address onto the stack, effectively suspends execution of the caller, and transfers control to the callee, which accomplishes at least the control flow part of a function call.  When the callee is ready to return to the caller, it uses ret which takes the return address value off of the stack and puts it into the instruction pointer register — that effectively terminates the callee and also resumes the caller, at the instruction after the call.  The return address can be thought of as a (hidden from C) parameter passed from caller to callee, so that the same callee can return to any caller at any call site.

For example, main could call factorial twice, from two different places in main, and each invocation would provide a different return address value, so that the suspended main is resumed following the proper call site (the one that invoked this call to factorial).  Further, main can call factorial, and also main can call foo which can call factorial.  The return address mechanism supports general purpose returning to the proper caller.

Upvotes: 2

Programmerabc
Programmerabc

Reputation: 327

The pushing and poping of the ebp is a part of calling conventions in x86-64 machine but I am really not sure how much do you need it to make a simple recursive function.

When you call a function in x86 a caller and callee convention is followed where some register are saved by caller and some by callee.In addition, there are some stack usage and restoration process while\after calling a function.

This link explains everything about stack and calling conventions in x86-64

Upvotes: 0

Related Questions