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!

$\endgroup$
4
  • $\begingroup$ But, as I understand it, such machines are limited to a single function, effectively. $\endgroup$
    – theDoctor
    Nov 12, 2021 at 12:22
  • $\begingroup$ You only need one function $\endgroup$
    – user253751
    Nov 12, 2021 at 12:28
  • $\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
    Nov 12, 2021 at 12:47
  • $\begingroup$ @user253751 The irony is that Alan Turing probably invented the subroutine. $\endgroup$
    – Pseudonym
    Nov 14, 2021 at 5:37

3 Answers 3

5
$\begingroup$

Note that Turing machines don't have any function calls, and they work just fine as Turing machines. Function calls are not a necessity for Turing-completeness. All non-recursive function calls can simply be inlined. Recursive functions can be translated to loops using an explicit stack, the same way the CPU actually executes them (see below).


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

(On a general-purpose CPU) 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.


Modern CPUs do also remember the last several return addresses in a special stack memory unit on the CPU. However, this is purely for speculative execution - an optimization. The CPU will start speculatively executing the code at the address stored in its own stack, while it waits to read the real address from memory. If it gets the address right, it has a head start.

Some non-von-Neumann machines, like some small microcontrollers, do have a special stack memory unit that is the only place the return addresses are stored. However, those aren't the general-purpose CPUs you're thinking of.

$\endgroup$
4
  • $\begingroup$ (+1), but I feel that referring to "the same way the CPU actually executes them" can only be understood if one already knows how function calls are actually realized on CPUs. The OP is precisely asking to describe that, which you do in the second part of your question. $\endgroup$
    – chi
    Nov 12, 2021 at 12:50
  • $\begingroup$ @chi I added (see below) to satisfy you. $\endgroup$
    – user253751
    Nov 12, 2021 at 12:51
  • $\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
    Nov 14, 2021 at 5:38
  • $\begingroup$ And of course reading the return address from the stack, the correct address will be predict 99.9% of the time. $\endgroup$
    – gnasher729
    Oct 13, 2023 at 21:40
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

$\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.

$\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.