0

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:

  • Why is ebp being pushed here? I see pop for that so it kinda makes no sense to me to push something to stack without popping it.
  • In the explanation part, what is that eip and where is it even pushed into the stack?

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
Erik Eidt
  • 23,049
  • 2
  • 29
  • 53
iSuckAtAssembly
  • 11
  • 2
  • 1
    There is `pop ebp` at the end. `eip` is the instruction pointer, it's pushed automatically by `call`. – Jester Jan 01 '22 at 16:25
  • 3
    Please [edit] your question and copy the relevant code snippets from the external resource into your post so your question can be understood even when the link goes down. – fuz Jan 01 '22 at 16:25
  • ebp is popped once in end_factorial and pushed as many times as factorial is called, what happens to the rest of those pushes? – iSuckAtAssembly Jan 01 '22 at 16:33
  • 2
    Since for each call there is a return, it's balanced. – Jester Jan 01 '22 at 19:22
  • 2
    You seem to be thinking that `end_factorial:` is like a separate function, but it's not. It's just a label. If the `je` is taken, we get to `end_factorial` and do the pop; if not then `end_factorial` is reached after `imul %ebx, %eax`, and the pop is done in that case as well. There's no imbalance. – Nate Eldredge Jan 01 '22 at 19:23
  • (And if you're worried about the `push %eax` looking unbalanced, `mov %ebp, %esp` effectively cleans it up.) – Nate Eldredge Jan 01 '22 at 19:26
  • 2
    The neat thing about recursion, in assembly language as well as others, is that there is nothing special to do. A function call is coded exactly the same, whether it's a call to a different function or a recursive call to this one. – Nate Eldredge Jan 01 '22 at 19:27
  • oh god that was stupid, yes i thought end_factorial was a different function for some reason. thanks a lot – iSuckAtAssembly Jan 02 '22 at 01:00
  • Also I noticed an answer saying ebp is a call-preserved register. If I use let's say edx who isn't call preserved, I don't need to do all that pushing and popping right? – iSuckAtAssembly Jan 02 '22 at 01:04
  • Yes, if you use `%edx` you would not have to push & pop it the way that `%ebp`. However, now you have a different problem. Since `%edx` is call clobbered, it won't have the right value after the call, so the `mov` right before the `imul` won't work. – Erik Eidt Jan 02 '22 at 15:57

2 Answers2

1

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.

ecm
  • 2,583
  • 4
  • 21
  • 29
Erik Eidt
  • 23,049
  • 2
  • 29
  • 53
0

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

Programmerabc
  • 329
  • 2
  • 10