0
$\begingroup$

Besides basic instructions for a general-purpose computer (binary arithmetic, move instruction, and jump on condition), it seems you can't implement a universal turing machine (is that even the right term?) without something more. That something is the ability to do arbitrary levels of function calls, I believe, yet how does a CPU implement them?

Setting a return address before jumping to the function code works for one call, but what if there are nested function calls? How will the CPU keep track of all the return addresses?

Is there a return address stack on the CPU (limited to memory on chip), or is it emulated in software at the assembler using regular RAM?

(In case it matters, I'll ask on behalf of Intel 8088 or 80x86 CPUs.)

Thanks!

Improve this question
$\endgroup$
2
  • $\begingroup$ @theDoctor Yes, a TM is limited to one specific function, but that function could be "simluate TM number $n$ on input $x$", making the TM universal. Each CPU is similarly limited to computing one specific function: executing machine language, which makes the CPU "universal", in some sense. $\endgroup$
    – chi
    Commented Nov 12, 2021 at 12:47
  • $\begingroup$ @user253751 The irony is that Alan Turing probably invented the subroutine. $\endgroup$
    – Pseudonym ♦
    Commented Nov 14, 2021 at 5:37

3 Answers 3

Reset to default
5
$\begingroup$

A typical 32-bit CALL instruction simply does the following:

  • Decrement the stack pointer by 4
  • Write the address of the next instruction at the address stored in the stack pointer (i.e. WriteMemory(ESP, EIP); - EIP having already been incremented to the next instruction)
  • Set the program counter to the address being called (i.e. EIP := Operand;)

and the RET (return) instruction does the following:

  • Set the program counter to the value stored in memory at the address stored in the stack pointer (i.e. EIP := ReadMemory(ESP);)
  • Increment the stack pointer by 4

There is no special hardware stack. There are instructions designed for use with a stack in normal memory (PUSH, POP, CALL, RET, ENTER, LEAVE, and the ESP and EBP registers and associated addressing modes). It's the software's responsibility to set aside some memory space for the stack. Software is also mostly responsible for deciding how to use it - if you want to write a program with no function calls, more power to you. There are some cases where the CPU will use the stack anyway - like interrupt handling - so even if you didn't use the stack in your software you'd want to set aside a small amount of space for interrupts. Interrupts are not required for Turing-completeness. Other architectures, like ARM, don't need a stack for interrupts - it's purely a design choice.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Just one more thing: It's worth looking at the assembly output of real programs to learn about how real CPUs handle things such as functions/subroutines. See, for example, godbolt.org $\endgroup$
    – Pseudonym ♦
    Commented Nov 14, 2021 at 5:38
3
$\begingroup$

Is there a return address stack on the CPU (limited to memory on chip), or is it emulated in software at the assembler using regular RAM?

Yes.

  • Some processors do not have a stack (and need to emulate it using RAM for everything)
  • Some have a fixed size stack
  • Most use general purpose ram via a stack register
  • Some have a stack that is partially in CPU cache and partially in RAM.

80x86 uses a stack pointer register SS:(E)SP

Improve this answer
$\endgroup$
1
$\begingroup$

Worth mentioning is what POWER and PowerPC do: These processors have a special register intended for returning from a call. There is an instruction BL (Branch and Link) which jumps to the address of a subroutine, and leaves the address of the instruction after the BL instruction in the "Link" register. The function that was called can store that address on the stack and later read it from the stack and return.

However, you always end up with a function that doesn't call any other function, a so-called "leaf" function. So if you call a leaf function that function will not do anything with the contents of the Link register other than using it to return to the caller, so calling leaf functions is quite a bit faster. (These processors use another trick: They always have something like 100 byte or so reserved on the stack beyond what is actually needed. So if a leaf function doesn't need more than these 100 bytes on the stack, it just uses the spare space and doesn't bother allocating or deallocating any stack space. So that saves quite a bit of space again).

The effect of this is that especially for small functions, there is practically no overhead for calling them instead of inlining. The total cost can be just a "branch and link" instruction plus an instruction to jump back through the link register. And because this is all done by the independent branch unit, it basically takes no time whatsoever.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.